稀疏子空间聚类_范文大全

稀疏子空间聚类

【范文精选】稀疏子空间聚类

【范文大全】稀疏子空间聚类

【专家解析】稀疏子空间聚类

【优秀范文】稀疏子空间聚类

范文一:稀疏子空间聚类算法 投稿:戴覿觀

稀疏子空间聚类算法与模型建立

稀疏子空间聚类是一种基于谱聚类的子空间聚类方法,

基本思想:假设高位空间中的数据本质上属于低维子空间,能够在低维子空间中进行线性表示,能够揭示数据所在的本质子空间, 有利于数据聚类.

本方法是, 对给定的一组数据建立子空间表示模型,寻找数据在低维子空间中的表示系数, 然后根据表示系数矩阵构造相似度矩阵, 最后利用谱聚类方法如规范化割(Normalized cut, Ncut)[22] 获得数据的聚类结果。

基本原理

稀疏子空间聚类[32] 的基本思想是: 将数据 xiS表示为所有其他数据的线性组合, xiZijxj (1)

ji

并对表示系数施加一定的约束使得在一定条件下对所有的xjS, 对应的Zij0。将所有数据及其表示系数按一定方式排成矩阵 ,则式(1)等价于 XXZ (2)

且系数矩阵ZRNN 满足: 当xi 和xj属于不同的子空间时, 有Zij0. 不同于用一组基或字典表示数据, 式(2)用数据集本身表示数据, 称为数据的自表示. 若已知数据的子空间结构, 并将数据按类别逐列排放, 则在一定条件下可使系数矩阵Z具有块对角结构, 即

Z10Z00Z2000 (3) Zk

这里Z(1,,k) 表示子空间S中数据的表示系数矩阵; 反之, 若Z 具有块对角结构, 这种结构揭示了数据的子空间结构. 稀疏子空间聚类就是通过对系数矩阵Z采用不同的稀疏约束, 使其尽可能具有理想结构, 从而实现子空间聚类.

Elhamifar 等[32] 基于一维稀疏性提出了稀疏子空间聚类(Sparse subspace clustering,SSC) 方法, 其子空间表示模型为

minZ1 s.t.ZXXZ,Zii0 (4)

该模型利用稀疏表示(SR) 迫使每个数据仅用同一

子空间中其他数据的线性组合来表示. 在数据所属的子空间相互独立的情况下, 模型(4) 的解Z具有块对角结构, 这种结构揭示了数据的子空间属性: 块的个数代表子空间个数, 每个块的大小代表对应子空间的维数, 同一个块的数据属于同一子空间. 注意, 模型中的约束Zii0 是为了避免平凡解, 即每个数据仅用它自己表示, 从而Z 为单位矩阵的情形. 稀疏子空间聚类综述 王卫卫1 李小平1 冯象初1 王斯琪1

32 Elhamifar E, Vidal R. Sparse subspace clustering. In: Pro-ceedings of the 2009 IEEE Computer Society Conferenceon Computer Vision and Pattern Recognition (CVPR).Miami, FL, USA: IEEE, 2009. 2790¡2797

稀疏最优化模型

位于线性或仿射子空间集合的高维数据可以稀疏地被同一个子空间的点线性或者仿射表示。通过文献[9]中稀疏表示技巧获得高维数据的稀疏表示。

设有N个D维数据yii1,处于R 空间的n个线性子空间Sll1中,子空间的维数分别为NDn

dlln1,定义一个矩阵Y为:

Y[y1yN][Y1Yn] 其中,YRMNl矩阵。

对于每个数据点都可以被一些除它以外的数据点表示,即yiYci,cii0,其中Ci[c1c2cN]RNN,该表示是任意的并存在一个最稀疏的形式。为了获得每个数据点的最稀疏的表示,选择最小化其l0范数对其进行凸松弛处理。稀疏最优化模型为: min1s.t.YYC,diag(C)0

将已获得的稀疏系数矩阵C应用到谱聚类算法中,从而对数据进行聚类,称为稀疏子空间聚类算法。谱聚类算法

谱聚类[11]是建立在图谱理论基础上的一种重要的数据聚类方法,首先根据给定的样本数据集建立数据间的相似度矩阵,然后构造加权图,通过寻找图的最优划分实现数据聚类的目的。

非正则化Laplacian LDW

正则化Laplacian Lxym:D1/2LD1/2ID1/2WD1/2 Lrw:D1LID1W 其中,D度矩阵为对角矩阵,对角线上的元素为d1,d2,,dnw

j1nij。L对应于划分准则

RatioCut【12】,而正则化:Laplacian对应于划分准则Ncut[12]。根据Laplacian矩阵的选择不同[12],衍生出三个谱聚类算法,一种非正则化谱聚类,两种正则化谱聚类[6,13]。

谱聚类算法寻求相似加权图的最优划分,要求类间切割权值最小而类内相似权值最大。然而非正则化

谱聚类有时不能满足类内相似权值最大这个要求,而正则化谱聚类能够很好的满足这两个条件。因此,正则化谱聚类算法优于非正则化谱聚类算法。

一种改进的稀疏子空间聚类算法 欧阳佩佩,赵志刚,刘桂峰(青岛大学信息工程学院,青岛266071

[6] Ng A,Weiss Y,Jordan.On spectral clustering:analysis and an algorithm [J].Neural Information Processing Systems,2001:849-856.

[9] Elhamifar E,Vidal R.Sparse subspace clustering:Algorithm,theory,and applications[J].IEEE Transactions on Pattern Analysis and

Machine Intelligence,2013,35(11):2765-2781.

[11]von Luxburg U,A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416.

[12]Boyd S,Parikh N,Chu E,et al.Distributed optimization and statistical learning via the alternating direction method

of multipliers[J].

Foundations and Trends in Machine Learning,2010,3(1):1-122.

[13]Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Trans.on Pattern Analysis and Machine Intelligence,2000,2(8):888-905.

以上所述的稀疏子空间聚类模型通常采用交替方向法(Alternating direction method, ADM)[74]来求解, 需要大量的迭代, 同时复杂度较高。

我们选用ADM的改进算法,ADMM(交替方向乘子法)。交替方向乘子法是求解分散式优化问题的方法之一,它收敛性好,鲁棒性强,且不要求子优化模型目标函数严格凸和有限,近年来越来越受关注。其标准形式[17]如下:minf(x)g(z)

s.t.AxBzc

xRn;zRm;ARpn;BRpm;cRp ;f,g为凸函数。

n当 f,g函数在RR上为凸函数时,算法能收敛到最优解[17]。需特别注意的是

ADMM 不要求f,g函数有限,因此f,g除了可以表示每个子系统的目标函数外,还可以表示每个子系统的等式或不等式约束,这时,当每个子系统约束不越限时, f0,g0,否则 f,g。

[11] Chen C.Non-convex economic dispatch:A direct search approach[J].Energy Conversion and Management,2007,48(1):219-225.

基于交替方向乘子法的动态经济调度分散式优化 李佩杰,陆镛,白晓清,韦化

求解:

范文二:图像分割的加权稀疏子空间聚类方法 投稿:周嗹嗺

第 3 6卷

第 3 期 

系 统 工 程 与 电子 技 术 

Sys t e ms   En gi ne e r i ng   a nd   El e c t r oni c s  

Vo1 . 36   No .3   M ar c h   2 Ol4  

2 0 1 4年 3月  

文章编号 : i 0 0 i - 5 0 6 X ( 2 0 1 4 ) 0 3   0 5 8 0   0 6  

网址 : www . s y s — e l e . c o n  r

图像 分 割 的加 权 稀疏 子 空 间聚 类 方 法 

李  涛 , 王 卫卫 ,翟   栋 ,贾西西 

( 西安 电子科 技大 学数 学 与统计 学院 ,陕西 西安 7 1 0 1 2 6 )  

摘  要 : 在 稀 疏 子 空 间 聚 类 算 法 的基 础 上 , 提 出一 种 基 于 加 权 稀 疏 子 空 间 聚 类 的 图像 分 割 方 法 。利 用加 权 的  稀 疏 约 束 使 得 特 征 数 据 能 够 更 好 地 被 同 一 子 空 间 内相 似 性 高 的 特 征 数 据 线 性 表 示 , 系数 矩 阵 在 类 间 更 为 稀 疏 。  

实验 表 明 , 给 出的 加 权 稀 疏 子 空 间 聚 类 方 法 对 于 干 净 数 据 和 带 噪 声 的 数 据 都 能 得 到 较 高 的 数 据 聚 类 准 确 率 , 对自   然 图像 能 够 得 到 比 较 符 合 人 眼视 觉 特 性 的 分 割 结 果 。  

关 键 词 :图像 分 割 ; 子 空 间 聚 类 ;加 权 稀 疏 

中图分类号 : T P   3 9 1  

文献标志码 : A  

D O I : 1 0 . 3 9 6 9 / j . i s s n . 1 0 0 1 — 5 0 6 X . 2 0 1 4 . 0 3 . 2 6  

W e i g ht e d — s pa r s e   s u b s pa c e   c l u s t e r i n g   me t h o d   f o r   i ma g e   s e g me n t a t i o n  

LI   Ta o ,W ANG  We i — we i ,ZH AI   Do n g,J I A  Xi — x i  

( S c h o o l   o f   S a t h e ma t i c s   a n d   S t a t i s t i c s ,Xi di a n   Un i v e r s i t y,Xi ’ a n   7 1 0 1 2 6,Ch i n a )  

Ab s t r a c t :On   t h e   b a s i s   o f   s p a r s e   s u b s p a c e   c l u s t e r i n g   a l g o r i t h m ,a   n o v e l   i ma g e   s e g me n t a t i o n   me t h o d   b a s e d   o n   we i g h t e d — s p a r s e   s u b s p a c e   c l u s t e r i n g   i s   p r

e s e n t e d . By   t h e   c o n s t r a i n t s   o f   we i g h t e d — s p a r s i t y,e a c h   f e a t u r e   d a t a   c a n   b e   l i ne a r l y   r e p r e s e n t e d   b y   a   f e w  mo s t   s i mi l a r   f e a t u r e   d a t a   wi t h i n   t h e   s a me   s u b s p a c e ,a n d   t h e   r e s u l t i n g   c o e fi —  

c i e n t   ma t r i x   s p a r s e   i n t e r — c l a s s .Ex p e r i me n t s   s h o w  t h a t   t h e   p r o p o s e d   we i g h t e d — s p a r s e   s u b s p a c e   c l u s t e r i n g   me t h —  

o d   c a n   o bt a i n   h i g h e r   c l u s t e r i n g   a c c u r a c y   t h a n   t h e   s t a t e   o f   a r t   me t h o d s   f o r   b o t h   c l e a n   a n d   n o i s y   d a t a .S e g me n t a —   t i o n   r e s u l t s   b y   u s i n g   t h i s   me t h o d   o n   n a t u r a l   c o l o r   i ma g e s   s h o w  g o o d   v i s u a l   c o n s i s t e n c y .   Ke y wo r d s :i ma g e   s e g me n t a t i o n;s u b s p a c e   c l u s t e r i n g;we i g h t e d   s p a r s e  

0  引   言 

图像 分 割 是 把 图像 分 成 若 干个 特 定 的 区 域 或 提 取 感 兴 

趣 目标 的 过 程 , 是 图 像 分 析 和 理 解 以及 计 算 机 视 觉 的 基 础 。  

的相似度 矩阵是此类方 法的关键 , 也是 一大挑 战 。   子 空 间 聚类 是 一 种 新 的谱 聚类 方 法 , 若 数 据 分 布 在 一 些 

线性或仿射子空间的并上 , 子 空 间 聚类 比 其 他 聚类 方 法 能 得 

到 更 好 的 聚 类 效 果 。其 中 文 献 E 1 2 —1 3 ] 提 出 的 稀 疏 子 空 间  聚类( s p a r s e   s u b - s p a c e   c l u s t e r i n g , S S C ) 方 法和 文献 [ 1 4—1 5 ]  

提 出的 低 秩 子 空 间 聚 类

方 法 通 过 稀 疏 表 示 ( s p a r s e   r e p r e s e n —   t a t i o n , S R ) 或低 秩表 示 ( 1 o w   r a n k   r e p - r e s e n t a t i o n , L R R ) 构 造 

自2 0世 纪 6 O年 代 以来 图 像 分 割 问 题 得 到 了 大 量 研 究 , 出   现 了许 多 有效 的模 型 与 算 法 , 如 基 于 边 界 的 分 割 方 法 

基于变分 、 偏 微 分 方 程 的方 法 

、  

、 基 于阈值 的分割 方法E 。  

和 基 于数 据 聚 类 的 方 法  ”   等。   谱 聚类 是 建 立 在 图 谱 理 论 基 础 上 的一 种 重 要 的 数 据 聚 

类方法 , 首 先 根 据 给 定 的 样 本 数 据 集 建 立 数 据 间 的 相 似 度 

相似度矩阵 , 这 种 相 似 度 矩 阵 在 理 想 情 况 下 具 有 块 对 角 结 

构, 能够 准 确 地 刻 画 数 据 的 子 空 间 属性 , 一 般 情 况 下 比高 斯 相  似度 矩 阵 有更 好 的 稀疏 性 。具 体 来 讲 , S S C利 用 部 分 数 据 作 为 

矩阵 , 然后构造 加权 图, 通 过 寻 找 图 的 最 优 划 分 实 现 数 据 聚 

类 的 目的 。此 方 法 的 优 点 是 直 接 对 相 似 度 矩 阵 进 行 分 析 ,  

字典( 即求 某 一数 据 的表 示 系 数 时用 其 他 数据 作 为 字 典 ) , 以 及 

l 。范数 或 者 l   范 数对表示系数进行稀 疏约束 , 使 得 每 个 数 据 

不需要样 本服从特 定分 布 , 理 论 上 能 对 任 意 形 状 的 样 本 空  间 进 行 分 割 。谱 聚 类 方 法 的 关 键 是 构 造 相 似 度 矩 阵 , 一 个  典 型 的相 似 度 量 为 高 斯 相 似 度 函 数 , 虽 然 该 函 数 使 谱 聚 类 

方 法 取 得 了一 些 成 功 , 但 尺 度 参 数  的 选 取 问 题 使 该 函 数 

尽 可能 用 同 一子 空 间 的数 据 线性 表 示 , 而 与不 同子空 间 的数 据 

无关 ; 低秩 子 空 间 聚类 利 用 所 有 数 据 作 为 字 典 , 并 对 所 有 数 据 

在该字 典下的表示系数联合 附加低秩约束 , 以达到同样的 目  

的 。稀 疏 表 示对 系 数 没有 显 式 的全 局 约束 , 低 秩 表 示 是 一种 全  

具 有 明显 的 局 限性 , 而 且 由 此 得 到 的 相 似 度 矩 阵 是 非 稀 疏  的, 给 谱 聚 类 算 法 造 成 计 算 负 担 。构 造 稀 疏 的 、 对 参 数 稳 定 

局 约束 , 但 当数 据有 噪声 时表 示 系 数稀 疏 性 差 。  

图 像 分 割 通 常 是 基 于 图像 的 某 些 特 征 进 行 分 割 , 常 用 

收 稿 日期 : 2 0 1 3—0 6  0 8 ;修 回 日期 : 2 0 1 3—1 1—2 4 ; 网络 优 先 出版 日期 : 2 0 1 4—0 3 —1 1 。  

网 络 优 先 出 版

地 址 : h t t p : / / www. c n k i . n e t / k c ms / d e t a i l / 1 1 . 2 4 2 2 . TN. 2 0 1 4 0 3 1 1 . 1 5 3 8 . 0 2 7 . h t ml  

基金项 目: 国家 自然科 学 基 金 ( NS F C 6 1 1 7 9 0 4 0 , N   F C 6 1 1 0 5 0 1 1 , NS F C 6 1 2 7 1 2 9 4 ) ; 教 育部 博 士 学科 点 专 项 科研 基 金 ( 2 0 1 3 4 4 0 8 1 1 0 0 0 1 ) 资助 课 题 

第 3 期 

李 涛 等 :图像 分 割 的加 权 稀 疏 子 空 间 聚 类 方 法  两 种 聚 类 方 法 分 别 利 用 稀 疏 表 示 和 低 秩 表 示 得 到 系 数  矩阵 【 , , 然 后 构 造 相 似 度 矩 阵 

w 一  ( 5 )  

的 特 征 有 图像 灰 度 及 其 统 计 量 、 图像局部 几何 特征 、 颜 色 直  方图、 局 部 二元 模式 、 尺度不 变 特征 、 纹 理 特 征 等 。 图像 分  割 的本 质 是 对 特 征 数 据 聚 类 的 过 程 , 因 此 数 据 聚 类 与 图 像 

分割有 着 自然 的联系 。本 文研究 图像 分割 的稀疏 子空 间聚 

类方法 。如前所述 , 子 空 间 聚 类 方 法 的 基 本 假 设 是 所 有 数  据 来 自若 干 线 性 或 仿 射 子 空 间 的并 。对 图像 的 特 征 数 据 来  讲, 这一假设 不一定 准确 成 立 , 因此, 本 文 给 出 一 个 加 权 稀  疏子空 间表示模 型 , 优点 有 两方 面 : 一方面, 本 文 采 用 高 斯 

相似度作 为权重 , 这是 一种全局相 似度 , 从 而 加 权 稀 疏 是 对 

最 后用 N o r ma l i z e d   c u t s( N c u t )   算 法 得 到 最 终 的聚 类 结 果 。  

1 . 2 加 权 稀 疏 子 空 间聚 类 

在 实 际应 用 中 , 由 L RR 得 到 的 相 似 度 矩 阵 稀 疏 性 较  差, S S C对 噪 声 敏 感 , 另外 对 图像分 割 来讲 , 特 征 数 据 不 一 

定 准 确 满 足 子 空 间 聚类 的 假 设 , 因此 , 本 文 给 出 一 个 加 权 稀 

疏 子空间表示 模型 , 权 重 的 引 入 有 利 于 使 得 数 据 尽 可 能 被  最 相 似 的 数 据 线 性 表 示 。利 用 高 斯 相 似 度 函数 

数据 的一种全局 约束 , 弥补 了稀疏 是一种 局部 约束 的不足 ;  

另一方 面 , 权 重 的 引 入 有 利 于 使 稀 疏 子 空 间 聚 类 和 图 像 分  割结果对 前述假 设更 加鲁 棒 。实 验结 果表 明 , 本 文 给 出 的  加 权 稀 疏 子 空 间 聚类 具 有 良好 的 聚 类 性 能 , 对 噪 声 有 更 好 

一  p f 一业  

\   o 

1  

/  

( 6 )  

式中, d   和d , 是 2个 数 据 样 本 , 对z  范 数 加

权 , 建 立 如 下 加 

的鲁棒性 , 对于 彩色 自然 图像有很好 的分割效 果 。  

权 稀 疏 表 示 模 型 

1 数 据 的 加 权 稀 疏 聚 类 

设有 N 个 M 维数 据 d   ∈R  , i 一1 , …, ~( N>M) , 由 

m i n >  土 J   U j  J , s . t . d   一D u   ,   一0  

。   j   Wj i  

i一 1, … , N 

( 7 )  

这些 数据构 造一个 矩 阵 , 记为 D一[ d   ,   , …, d   ] ∈R   。  

假设 这些数 据来 自 n ( n ≥1 ) 个 相 互 独 立 的 线 性 或 仿 射 子 空  间的并 s — US   。子 空 间聚 类 的 目的是 , 寻 找 数 据 指 标 集  { 1 , 2 , …, N} 的 一 个 划 分 C一 { C   , C 。 , …, C   } , 使得 C   对 应 

模 型 中相 似 度 越 大 则 权 重 越 小 , 相 似 度 越 小 则 权 重 越  大, 因 此 加 权 稀 疏 约 束 有 利 于 使 得 数 据 尽 可 能 被 最 相 似 的  数据线 性表示 , 与不相 似的数据无 关 。   模 型 求 解 时 常 转 换 为 如 下 模 型 

m i n ∑ 

1 +圳  一d   l 。 , s . t . “   一0 ( 8 )  

于子空间 s   (   一1 , …, , z ) 中数据的下标 , 且 >: c z — N。  

i 一 1  

式中, i 一1 , 2 , …, N,  > 0为 参 数 。 本 文 利 用 C VX— MAT—   L AB工 具 包 逐 步 迭 代 求 出 U  的最 优 近 似 解 。   利 用式 ( 5 ) 构造 相似 度矩 阵 , 利 用 成熟 的谱 聚类 算 法 ,   如规 范化割 ( Ne u t ) 就可 以得到最终 聚类结果 。  

1 . 1 低 秩 和 稀 疏 子 空 间 聚 类 

L R R_ 1  从 表 示 系 数 矩 阵 的全 局 出 发 , 利 用 表 示 系 数 矩  阵的低秩 约束 , 使 得 数 据 尽 可 能 被 同 一 子 空 间 的 数 据 线 性 

表 示 。模 型可 表 示 为 

mi n{ l 【 ,l   U 

S .t . D — D U  (1 )  

2 基 于加 权 稀 疏 子 空 间 聚 类 的 图像 分 割 

图像 分 割 的 本 质 是 对 特 征 数 据 聚 类 的 过 程 , 本 文 利 用 上 

式中, l I・l   表 示 矩 阵 的核 范数 。实 际应 用 中需 要考 虑  l

到数 据 中的噪声或其他 干扰 , 又 将 模 型 修 正 为 

节 给 出 的加 权 稀 疏 子 空 间 聚 类 方 法 进 行 图 像 分 割 。需 要 

解 决 两 个 问题 : 首 先是 聚类对 象 的选择 问题 , 对 图 像 分 割 来  讲, 由 于人 类 视 觉 是 以像 素 组 为 单 位 识 别 目标 的 , 若 以 单 个 

mi n  U   l   +  l l   l D— D U—E   l  

+  l l   l E   l  ,  

( 2 )  

像素为对象 , 会 给聚类 过程 带来 巨大 的计 算压 力 , 而且单个  像素不具有视 觉意义 。因此 , 本文对 图像 进行 过分割 , 把 图 

像 分 成 一 些 均 匀 的块 , 以像 素 块 的 特 征 作 为 聚 类 对 象 。文 献  E 1 7  ̄ ¥ r ] 用N c u t 方 法 将 图像 分 为很 细 小 的块 , 得 到 图像 的 超 像  素, 这些 超 像 素 中含 有 图像 的各 种细 节 。文献 [ - 1 8 1 利 用 边 界 概  率 方法 使 图 像 内部 的 边缘 清 晰 和准 确 , 尽 量避 免 图像 边 缘 被 分  割 开 的现 象 。本 文 结合 这 2种方 法 , 利用 边 界 概率 得 到 较 为 清  晰 和准 确 的 图像 边 缘 , 然后 利 用 N c u t 得 到 合适 的超像 素 块 。   另 一 个 关 键 问 题 是 超 像 素 的特 征 选 择 。 在 图 像 分 割 中  常 用 的 特 征 有 多种 , 例 如 纹 理 特 征 和 局 部 二 元 模 式 直 方 图  主 要 用 于 纹 理 图像 的 分 割 ; 图像 灰 度 及 其 统 计 量 、 尺 度 不 变  特征等 主要用 于灰度 图像 的分 割 ; 本 文 主 要 考 虑 彩 色 图像  

式 中 , l   E   l   l ,   一∑   / ∑( E   )   用 来 度 量 噪 声 或 野 点 带  

来 的误差 ;   >o ;  > O 。  

S S C   利用所 有数 据作 为 字典 线性 表 示 每个 数 据 , 利 

用表示 系数 的稀 疏约束使 得数据尽 可能被 同一 子空 间的数 

据 线 性 表 示 。在 求 解 数 据 d   的稀 疏表 示 时 , 为 了 避 免 平 凡  解, 字 典 中需 要 排 除 d   , 等价 于强制 d   的表示 系数 l l   =( 1 l   H :   一, H  )   的第 i 个 分量为 0 , 模 型 可 表 示 为 

mi n   l   l l l  l   1  S . t .d  一 D u   , H  一 0  

Hi  

( 3 )  

式 中, i 一1, 2, …, N。  

模 型求解 时常转换 为如下模 型 :   mi n   J   l U   l   l 1 十 ^l   l D u   一d  l   l 2 , U  一 0   ( 4 )  

的分割 问题 , 对于彩色 自然 图像 , 彩 色是最易 于 区分不 同 目  

标 的特 征 之 一 , 利 用 颜 色 直 方 图作 为 特 征 , 能 直 观 地 表 示 超 

式中, i 一1 , 2 , …, N,  > 0为 参 数 , 该 参 数 起 到 平 衡 两 项 的  作 用 。求 解 模 型 ( 4 ) 得到 l l   ∈R  , 把 所 有 系 数 排 成 一 个 矩  阵, 记 作  U— E u 1 ,   , …, l f   ]∈ RN   N  

像素 的颜色分 布 , 有 利 于将 其 分 到 相应 的颜 色 子 空 间 中

。   因此本 文选择颜 色直方 图作 为超像素 的特征 。当然本 文给 

出 的 模 型 和 方 法 也 适 用 于纹 理 图 像 和 灰 度 图 像 的 分 割 。  

范文三:稀疏子空间聚类的惩罚参数自调整交替方向法 投稿:邵柞柟

计算机技术与发展第24卷摇第11期摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇Vol.24摇No.11

2014年11月Nov.摇2014COMPUTERTECHNOLOGYANDDEVELOPMENT

稀疏子空间聚类的惩罚参数自调整交替方向法

姚摇刚,杨摇敏

(南京邮电大学自动化学院,江苏南京210023)

摘摇要:稀疏子空间聚类是利用子空间并集中数据向量的稀疏表示,从而将数据划分到各自子空间,该类方法关键是求出最优稀疏解。文中采用交替方向法求稀疏解,交替方向法把复杂问题分解成简单的、有效求解的子问题,达到最优速度。在交替方向法求解过程中,通常惩罚因子是恒定不变的。文中提出一种惩罚因子参数自调整策略,根据每次迭代信息,调整惩罚因子参数。基于运动分割数据和Hopkins数据库实验,结果表明在迭代次数和运算时间上,稀疏子空间聚类的交替方向法及其惩罚参数自调整策略比传统算法有很大提高,而且对噪声数据也非常有效。关键词:子空间聚类;稀疏表示;L1范数正则化;交替方向法

中图分类号:TP301摇摇摇摇摇摇文献标识码:A摇摇摇摇摇摇摇文章编号:1673-629X(2014)11-0131-04doi:10.3969/j.issn.1673-629X.2014.11.033

AlternatingDirectionMethodofSelf-adjustingPenaltyParametersof

SparseSubspaceClustering

(CollegeofAutomation,NanjingUniversityofPostsandTelecommunications,

Nanjing210023,China)

YAOGang,YANGMin

Abstract:Sparsesubspaceclusteringusesthesparserepresentationofvectorslyingonaunionofsubspacetoclusterthedataintoseparatesubspaces.Thekeyofthisalgorithmistofindtheoptimalsparsesolution.AlternatingDirectionMethod(ADM)isappliedtosolvesparseprobleminthispaper.ADMdividesthecomplexproblemintosimpleandeffectivelysolvingsub-problemtoachieveoptimalspeed.IntheprocessoftheADMsolving,thepenaltyfactorisconstant.Inthispaper,apenaltyfactorself-adjustingstrategyisproposed,accordingtotheeachiterativeinformation,adjustthepenaltyfactorparameters.TheexperimentbasedonmotiondivisiondataandHop鄄kinsdatabaseshowsthattheproposedmethodhasgreatimprovementiniterationtimesandcomputingtimecomparedwithtraditionalal鄄gorithms,isalsovalidfornoisydata.

Keywords:subspaceclustering;sparserepresentation;L1normregularization;alternatingdirectionmethod

0摇引摇言

在聚类分析中,高维数据聚类是聚类分析技术的难点和重点,子空间聚类[1]是实现高维数据集聚类的有效途径。子空间聚类常见算法有基于谱聚类算法[2],谱聚类的关键是相似矩阵构造;而近年来,随着稀疏学习的流行,相似矩阵构造常有基于稀疏表示的

[3]

稀疏表示。然后在谱聚类框架下,对数据进行划分。这种方法能有效克服数据噪声。文中主要研究稀疏子空间聚类算法。

近年来,压缩感知中稀疏优化[5-6]越来越流行,交替方向法[7-8]也备受关注。交替方向法常用于求解具有可分离结构的目标函数凸优化问题。文中采用交替方向法处理稀疏子空间聚类[9]问题。稀疏子空间聚类的关键是最优稀疏求解,一般转化为L1范数问题,常用内点算法CVX优化工具包求解。但是内点算法在处理一定规模的问题时,会花费很大的计算量。文中采用交替方向法求解L1范数,在求解中,一般惩罚因

和基于低秩描述的

[4]

法利用稀疏表示对低维子空间的数据进行聚类。子空间并集里每个点,可用空间里所有点构成的字典来稀疏表示。因此关键是找到子空间里每个特征点的最优

。稀疏表示的子空间聚类算

收稿日期:2013-12-03摇摇摇摇摇摇修回日期:2014-03-13摇摇摇摇摇摇网络出版时间:2014-07-28基金项目:江苏省自然科学基金(BK2011758);南京邮电大学攀登计划(NY212066)

作者简介:姚摇刚(1988-),男,江苏宝应人,硕士研究生,研究方向为图像处理与模式分类;杨摇敏,副教授,从事计算机视觉和图像理解的研

究工作。

网络出版地址:http://www.cnki.net/kcms/detail/61.1450.TP.20140728.1224.030.html

摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第24卷·摇13摇2·

子是常数不变的。文中研究了一种惩罚因子参数自调整策略,其根据一种更新规则,惩罚因子参数可以自适应改变,这样加快了收敛速度。

文中主要先对稀疏子空间模型进行介绍,然后提出解决模型中最稀疏解的交替方向法及惩罚因子参数自调整策略,最后基于运动分割数据仿真实验与Hop鄄比。

kins数据库[10],给出了改进算法与原算法实验结果对

量{ui}

伊k的矩阵;

(4)把k个特征(列)向量排列在一起组成一个N(5)把生成矩阵每一行看作k维空间中的一个向输出:数据集Y的n子集划分y1,y2,…,yn。

k

i=1

;

量,使用k-means算法聚类成n类。

2摇稀疏子空间模型求解

稀疏子空间模型一般常用内点算法CVX优化工具包求解,文中用交替方向及其改进算法对其求解。1摇稀疏子空间聚类模型

稀疏子空间聚类是一种基于稀疏表示的子空间聚

类算法。假设数据集Y=[yy1,y2,…,yN]沂RM伊N对于每个数据样本i而言,直接使用原始数据集作为冗余字典,得每个数据点的稀疏表示ci:

摇s.t.摇

Y掖minC=,ZYC业

椰C+椰0+

姿Z

2

z

椰Z椰2F(1)

摇其中摇Cii=0摇i=1,2,…,N,C是样本yi基于数据集Y的稀疏表示;

即表示矩阵中非零元个数;

椰·椰椰·椰0表示l0范数,式F为Frobenius范数。

(1)是非凸的并且是一个NP-hard问题,常使

用凸松弛方式(用l1范数替代原有的l0范数),将上述非凸优化转变如下:

摇s.t.摇

Ymin掖C,Z业椰C椰1+姿

2

z椰Z椰2F(2)

C=YC+iZ

ii=0摇=1,2,…,N

求解上式得到每个数据点的稀疏表示,构造相似

度矩阵W=[w定义如下:

1,w2,…,wN]沂WN伊N。为了使W对称,W=C+C

T

从另一方面说,节点i和j之间边的权重等(3)

cij+cji本y。这里W由n个独立子空间生成,每个样

i可以由属于同一个子空间的其他样本进行稀疏重构,属于不同子空间的样本的稀疏表示系数为零。

在相似度矩阵W上用谱聚类算法[2]进行划分。算法1:谱聚类算法(SpectralClustering)。输入:n个线性子空间{Si}

ni=1

组成的数据点

{yi

}

Ni(1)=1

构造基于数据集Y的相似矩阵W;

L=I(2)-D计算相似矩阵-1/2WD1/2,D沂WW的N伊NLaplacian为对角矩阵矩阵,,对角元素其中矩阵

Dii=

(3)移j

W

ij

求出;

L的前n个特征值,以及其对应的特征向

2.1摇交替方向法

首先根据式(2)的等式约束,可以消除目标函数

的Z,并引入辅助矩阵A沂RN伊N写成如下形式:

,那么公式(2)可以重摇摇

min椰C姿2

z

s.t.A(C=,A)

C

椰1+

椰Y-YA椰2F(4)

摇引进矩阵摇Cii=0摇i=1,2,…,N驻沂RN伊N拉格朗日乘子,可以得到增广

拉格朗日函数:

L(C,A,驻)=椰C椰1+

姿z

椰Y-YA椰2F+掖驻,A-C业2

+

其中,籽为惩罚因子;掖·业表示标准内积2

椰A-C椰2F(5)

。通过固定(Ck摇摇

-姿,驻k),对L关于A求导可得:摇摇摇摇z[YT摇籽[(AYk+-1YA(k+1)-Ck]=)]+驻k+

0(6)化简可得:

(姿zYTY+籽I)Ak+1=姿zYTY+籽Ck-驻k

一般情况下,YTY为对角阵时,可以得到Ak+(7)

1的封闭解:

Ak+1=(姿zYTY+籽I)-1·(姿zYTY+籽Ck-驻k)

固定(Ak+1以得到其封闭解,驻k:C),k+1对=LJ关于-diag(C求导得到J),其中

Ck+1[5](8)

,可

J=壮1k+1

(A

+驻k

)(9)

其中,壮浊如下形式:

(·)是收缩阈值操作符,其可以定义成壮浊(x)={

x-浊,x>浊

x0,+others

浊,x<-浊

(10)

这里的x可以是数字,向量或是一个矩阵。

当得到(Ck+1如下:

,Ak+1)时,可以更新拉格朗日乘子,

第11期摇摇摇摇摇摇摇摇摇摇摇摇摇姚摇刚等:稀疏子空间聚类的惩罚参数自调整交替方向法·133·

驻k+1=驻k+籽(Ak+1-Ck+1)

迭代次数。迭代停止标准为椰Ak-Ck椰¥臆着,

{10-3,10-4}

这三步不断重复执行直到收敛完成或达到设定的

(11)endwhile

输出:最优稀疏系数矩阵C*=Ck。

椰Ak-Ak-1椰¥臆着。其中着表示容错率,一般取着沂(2)的过程。

,下面算法展示了交替方向法执行式子

3摇实验仿真与分析

为了测试交替方向法及其改进算法与传统算法对比效果,将稀疏子空间聚类应用于视频点特征运动分割[12-13]中。假设F帧图像中有N个特征点,运动分割问题可以通过提取跟踪视频序列中f=1,2,…,F帧的N个特征点{xfi沂R2}

称为一个特征轨迹[14],与视频里F帧特征点xfi组成的

Ni=1

算法2:稀疏求解的ADM算法。初始化:k=0,C0,A0,驻0为0。

while椰Ak-Ck椰¥逸着,椰Ak-Ak-1椰¥逸着做下来解决。每个数据点yi也被

面操作:

(1)(姿通过求解下列等式更新+籽I)Ak+1=姿TY+Ak+1

zYTYzY籽Ck-驻k

+1壮(A(2)更新Ck:Ck+1=J-diag(J),其中J=1k+1驻k

+

(3)更新籽

)驻k+1

k+1

-C

k+1

)

end(4)输出while

k=K+1

:驻

=驻k

+籽(A

k+1

:最优稀疏系数矩阵C*=Ck2.2摇惩罚参数自调整策略

在交替方向算法中,惩罚因子籽是固定不变的。

但是可以观察到固定的惩罚因子的交替方向法收敛很慢,而且选择一个最优的惩罚因子很困难。所以文中研究了对于惩罚因子籽的自调整策略[11]籽。

k+1=min(籽其中,籽是max{,籽茁籽k),茁的值定义如下:

(12)

茁=

maxk}的上限{

茁1,0,k其他

当籽max(椰Ck+1-Ck椰,椰Ak+1-Ak椰)<着2

其中,茁(13)

0选;着逸1是常数。实际应用中变化的茁是首这种方法根据迭代停止标准来平衡误差并且引进2为常数,文中此处取着2=10-4。几个参数。

算法3:稀疏求解的惩罚参数自调整交替方向法。初始化:k=0,C0whileA-Ck

椰,A0,着驻0和籽k

,椰Ak

0。

k-1

¥-A面操作:

椰逸椰¥逸着做下

(1)k+1

(姿通过求解下列等式更新T

Y+籽=姿AzYkI)A

k+1

zYT

Y+籽kCk

-驻

k

-diag(J),其中J=壮(A(2)更驻新k

Ck+1:Ck+1=J1k+1籽+

籽(3)(4)更新k

)驻

k+1

:驻

k+1

=驻k

+籽k(A

k+1

-C

k+1

)

(5)籽kk=+1K=+min(1

籽max,茁籽k)2F维向量相对应y,定义如下:

i=[xT所以,所有帧的特征点组合成一个1

i,xT2i,…,xTFi

]2F伊N的矩阵

Y=[y1,y2,…,yN]为一个字典,求出每个特征点的稀疏表示,在稀疏子空间聚类算法中C,于是形,Y作成(2)的凸优化问题。

实验软件平台为Matlab7.10,硬件平台为Intel

Pentium统的笔记本双核。CPU,2.如图13所示GHz,2,给出了三个测试视频点特GB内存,WindowsXP系征序列[15]中的3帧

图1摇三个视频点特征序列分割聚类效果图

(只显示其中三帧)

表1列出了3个视频中每个视频的帧和特征点的数量。对于每个视频系列,用稀疏子空间算法来对跟踪每个帧中的特征点进行分割聚类。用不同颜色标记‘+爷区分表1摇。

三个视频序列的帧数与特征点数

视频序列1

视频序列2

视频序列3

帧数3017100特征点数

136

63

73

摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第24卷·摇13摇4·

摇摇表2为三种算法在聚类误差,迭代次数和迭代时间上的对比。子空间聚类的误差定义如下:

子空间聚类误差=

错分类点的数

特征点的总数

对于传统的内点优化算法,在算法效率上有很大的提高。文中在交替方向法基础上提出惩罚参数自调整策略,使迭代次数相应减少并使运行时间有较大的降低,说明该策略有较好的改进效果。稀疏子空间聚类的交替方向法的快速和并行计算方法,有待进一步研究。

参考文献:

[1]摇VidalR.Subspaceclustering[J].IEEESignalProcessingMa-[2]摇vonLuxburgU.Atutorialonspectralclustering[J].Statisticsgazine,2011,28(2):52-68.

表2摇三种算法平均子空间误差率、平均迭代

次数和平均运行时间对比(1)

算法名称

CVX工具内点优化算法

交替方向法平均子空间聚类误差率0.2560平均迭代次数91118平均运行时间60.3230.484参数自调整交替方向法

34

0.135

摇空间聚类误差率摇如表2所示,、交替方向法及其改进算法迭代次数还是运算时间,都比传统的,无论在子内点优化算法有较大的改进提高。这里CVX内点优化算法的迭代次数小于交替方向法,是因为内点算法每次迭代都要经过两次求导,所以精度上会相对提高点,但是缺点就是每次迭代花费时间比较长,而改进的算法在迭代时间和每次迭代效率都比CVX内点算法和交替方向法有较大提升。

为了进一步验证文中提出的方法,使用公共的运动分割测评库—Hopkins数据库[10]进行对比实验分析,验证文中提出的方法的鲁棒性和有效性。Hopkins包含了155个运动视频序列,其中有120个视频序列包含两个运动物体,35个视频序列包含三个刚性运动物体。包含两个运动物体的视频序列有256个特征点和30帧。包含三个运动物体视频序列有398个特征点和29帧。将文中提出的方法与传统方法应用于此数据库,如表3所示。

表3摇三种算法平均子空间误差率、平均迭代

次数和平均运行时间对比(2)

两个运动物体

三个运动物体

算法名称

平均子空

平均子间聚类误

平均迭平均运空间聚类平均迭平均运差率代次数行时间

误差率代次数行时间CVX点优化算法工具内0.18162152.730.32244267.47交替方向法0.031071.30.061283.85参数自调整交替方向法

0.03

33

0.38

0.05

36

0.90

摇类误差率摇实验进一步表明、迭代次数和平均运行时间都比交替方向法,文中提出的改进算法在平均聚和传统的内点算法有较大的改进。

4摇结束语

文中针对交替方向法进行改进,从实验结果得出,交替方向法是目前较好求解稀疏系数的优化算法,相

[3]摇ElhamifarandComputing,2007,17(4):395-416.ofIEEEconferenceE,VidalR.onSparsecomputersubspacevisionclustering[C]//Proc

[4]摇tion.Liu[s.l.]:IEEE,2009:2790-2797.andpatternrecogni鄄mentationGuangcan,LinZhouchen,YongYu.Robustsubspaceseg鄄

ternationalbyconferencelow-rankonrepresentation[machinelearning.C]//ProcHaifa:of27thNationalin鄄[5]摇Science文再文[J].运筹学学报,Foundation,2010:663-670.

印卧涛,,2012,16(3):49-64.

刘摇歆,等.压缩感知和稀疏优化简介[6]摇TropptionofJlinearA,WrightinverseSJ.problems[ComputationalJ].ProceedingsmethodsforofsparsetheIEEE,

solu鄄

[7]摇2010,98(6):948-958.

YangL1-problemsJunfeng,ZhangincompressiveYin.Alternatingsensing[directionJ].algorithmsfor

[8]摇cessingIEEESignalPro鄄YuanselectionXiaoming.Letters,2012,20(1):63-66.

models[J].AlternatingJournalofdirectionScientificmethodComputing,2012,51forcovariance

[9]摇(2):261-273.

Elhamifartheory,andE,VidalR.Sparsesubspace[10]nalysisapplications[J].IEEETransactionsclustering:algorithm,

onPatternA鄄TrontionsegmentationR,VidalandMachineR.AbenchmarkIntelligence,2013,35(11):2765-2781.

forthecomparisonof3-Dmo鄄

[11]puteralgorithms[C]//Procofconferenceoncom鄄Linvisionandpatternrecognition.[s.l.]:IEEE,2007.

directionZhouchen,Liutation[Cmethod]//ProceedingswithRisheng,SuadaptiveofadvancespenaltyZhixun.forLinearizedlow-rankalternating

represen鄄processingsystems.[s.l.]:[s.n.],2011:612-620.inneuralinformation[12]LauermotionF,SchnorrsegmentationC.Spectral[C]//ProcclusteringofIEEEoflinear12thsubspacesinternational

for

[13]conference青摇波,杨晨辉oncomputer,陈摇涛vision..基于分割的复杂运动跟踪的研究Kyoto:IEEE,2009:678-685.[14][J].王洪斌计算机技术与发展,李摇华.基于运动轨迹聚类的运动分割,2009,19(4):157-159.机应用,2003,23(10):1-3.

[J].计算[15]SugayabodyY,KanataniK.Multi-stageoptimizationformulti-tionandmotionSystems,2004,E-87D(7):1935-1942.

segmentation[J],IEICETransactionsonInforma鄄

稀疏子空间聚类的惩罚参数自调整交替方向法

作者:作者单位:刊名:英文刊名:年,卷(期):

姚刚, 杨敏, YAO Gang, YANG Min

南京邮电大学 自动化学院,江苏 南京,210023计算机技术与发展

Computer Technology and Development2014(11)

技术与发展 2014(11)

引用本文格式:姚刚.杨敏.YAO Gang.YANG Min 稀疏子空间聚类的惩罚参数自调整交替方向法[期刊论文]-计算机

范文四:迭代加权的稀疏子空间聚类 投稿:程巭差

摘要:文章提出了一种迭代加权的稀疏子空间的聚类算法。通过在数据集的实验,发现迭代加权稀疏子空间聚类算法极大降低了稀疏子空间的聚类算法的错误率,但并不增加算法的计算复杂度。

  关键词:迭代;稀疏子空间;聚类

  中图分类号:TP301 文献标识码:A 文章编号:1009-3044(2015)28-0030-02

  1 子空间聚类

  在这一节中,文章简要介绍下稀疏子空间聚类算法。在1.2节中文章介绍加权[?1] 最小化框架、所要解决的问题以及解决问题的算法。

  1.1 稀疏子空间聚类

  在这一节中,文章简要介绍SSC算法。该种算法采用稀疏表示方式,构建了相似图或多个子空间中数据点集聚类的亲和矩阵。

  考虑一系列点[Y=[y1,y2,…,yn]],其中[yi∈?m],[yi]为原始空间的低维子空间中的第[i]个数据点。SSC算法在这些数据点中寻求自身相似性,这需要通过解决下面的最优化问题:

  [minC1 s.t. Y=YC,diag(C)=0] (1)

  其中,[C∈?n×n]是数据点集[Y]的稀疏表示矩阵。那么,该稀疏表示矩阵[C]用来把高维空间分割成多个低维子空间。

  在SSC算法中,后置处理步骤就是子空间聚类。

  SSC是通过解决下面[?1]最小化问题:

  [min(C,E,Z) C1+λeE1+λz2Z2F s.t. Y=YC+E+Z,1TC=1T, diag(C)=0.] (2)

  其中,变量矩阵[E]表示数据的稀疏外围,变量矩阵[Z]表示数据的噪声或误用。

  参数[λe>0]和[λz>0]在目标函数中起着平衡作用。注意到最优目标函数(2)是凸优化变量,因此,可以使用凸程序工具(具体参考[1])有效解决。

  1.2 加权稀疏子空间

  在理想情况下,在公式(1)中,对所有的[j∈S1]令[cij=0]。但是对于真实的数据SSC算法可能并不能确定理想的解决方案。我们可以用加权的[?1]最小框架代替[?1]最小框架,这将可能地改善子空间聚类的性能。正如所讨论的,加权矩阵的更新是建立在[PW1]解的前一次迭代上。

  下面是我们的加权稀疏子空间框架:

  [min(C,E,Z) W⊙C1+λeE1+λz2Z2F s.t. Y=YC+E+Z,1TC=1T, diag(C)=0.] (3)

  在仿射的情况下,上面提出的框架可以用下面的描述:

  [min(C,E,A) W⊙C1+λeE1+λz2Y-YZ-E2F s.t. AT1=1,A=C-diag(C).] (4)

  其中,[A]是通过在所要优化的变量的硬阈值得到更快的更新值的一个辅助矩阵。将所有的元素设置为一个加权矩阵。因此,上述框架是一个简单的[?1]最小化问题。它是凸的,可以通过凸程序算法(具体见参考文献[2][3])有效的解决。

  2 实验和讨论

  对于所有的算法,我们使用它们作者所提供的代码。所有的参数的选择都是在最终平均聚类错误率最低时。使用的是Matlab2014b,Intel(R) Core(TM) i7-4770K CPU 3.50GHz 12GB RAM。

  对于Hopkins 155数据集:在LRR算法中,我们使用[λ=4]。在LSR算法中,作者在LSR问题上应用了两种不同的方法,分别为LSR1和LSR2。最好的性能是在[λ=0.0048](LSR1)和[λ=0.0046](LSR2)取的。在SMR算法中,我们使用[α=20]。在SSC算法中,我们使用[α=800]。另外,为了数值稳定性,我们使用[ε1=0.001],[ε2=0.02]。

  在我们的试验中,表1显示的是使用原始2F维特征轨迹。表2显示的是通过PCA将2F维投影到4n维子空间,n代表移动物体的数目。在这里,我们使用相同的参数。有如下的结论:

  (1) 在2F和4n情况下,所有的算法取得低的平均错误率(低于5%)。但是,相比于已经存在的算法,最近提出的SMR算法和本文中的RSSC算法取得低于1%的错误率。这些结果说明了RSSC算法在运动分割中有很强的稳定性。

  (2) 在原始2F原始运动追踪的情况下,使用RSSC算法所得到的2个运动物体聚类错误率从1.53%降到0.64%,3个运动物体聚类错误率从4.4%降到2.01%。对于整个Hopkins 155数据集,SSC算法平均聚类错误率为2.28%,RSSC算法的为0.95%。对于投影到4n维数特征追踪,对两个物体和三个物体分别使用RSSC算法得到的聚类错误率从1.69%和4.38%分别降到0.83%和2.50%。对于整个Hopkins 155数据集平均聚类错误率:SSC算法的为2.29%,RSSC算法的为1.21%。结果表明RSSC算法通过加权迭代[?1]最小比SSC算法性能更优。

  参考文献:

  [1] Elhamifar E,Vidal R.Sparse subspace clustering: algorithm, theory, and applications[J].IEEE Trans,Pattern Anal. Mach. Intell. 2013,35 (11):2765�C2781.

  [2] Boyd S P, Vandenberghe L.Convex Optimization[M].Cambridge University Press,2004.

  [3] Boyd S, Parikh N, Chu E.Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn. 2011,3 (1):1�C122.

  [4] Liu G, Lin Z, Yu Y.Robust subspace segmentation by low-rank representation[C].ICML, 2010.

范文五:高维稀疏数据对象——属性的零子空间分析 投稿:汪梇梈

高维稀疏数据对象——属性的零子空间分析

[摘要]针对高维稀疏数据对象-属性子空间的优化问题,本文从稀疏性的角度提出了RZABUBS算法,通过剔除零子空间实现子空间的优化,并通过实验研究证明了该算法的有效性。

[关键词]高维稀疏数据;零子空间;子空间优化;高维数据预处理

Zero-Subspace of High Dimensional Sparse Data Object-Attribute

Zhu Qin 1,2 ,Gao Xuedong 1,Wu Sen 1,Dai Aiming1

(1. School of Economics and Management, University of Science and Technology Beijing, 10083

2. School of Science, Nanchang University, 330031)

Abstract:As far as optimization subspace of High dimensional sparse data object-attribute is concerned, from the point of sparseness RZABUBS algorithm is proposed to achieve subspace optimization by removing the zero subspace in the paper, and the experimental studies demonstrate that the effectiveness of the proposed algorithm.

Keywords: High dimensional sparse data, Zero-subspace, Subspace optimization, Preprocessing high dimension data

1 引言

在数据挖掘的应用中,有一类数据如:购文档数据、空间数据、时间序列数据、基因序列等,其对象数目可达几百甚至上千,同时拥有成千上万个属性,我们将这类对象、属性数量特别大的数据对象称为高维数据(High Dimension Data,HDD)[1]。

高维数据与低维数据在许多方面表现出不同的特性,如稀疏性以及“维度效应”现象[2]等。子空间聚类算法[3]的提出在一定程度上解决了这一问题,正在成为当前一个研究的热点[4-14]。

现有的算法大都多数关注的是子空间的获取,而忽略了子空间的优化, 这是不完备的[15]。

本文提出一种剔除零子空间算法(A Removing Zero-subspace Algorithm Based on Unique Binary Sequence Code, RZABUBS),实现高维稀疏对象-属性子空间的优化。

2 问题描述

2.1 高维稀疏数据

有一类数据,其对象的数目很多,用来描述对象的属性也很多,但是对于每一个对象来说具有属性值的属性个数占总属性个数的比例很小。例如钢铁企业中,有很多的客户(对象)和很多的产品(属性),各个客户购买的产品一般很少,而且各客户购买的产品种类也有很大不同。

定义1(稀疏特征):假设有n个对象,描述第i个对象的m个属性值分别对应于区间变量值xi1,xi2,…,xi m,将其转换为二态变量并表示为yi1,yi2,…,yi m,转换方法为:

其中 {1,2,…,n}; {1,2,…,m}。yij, {1,2,…,n}; {1,2,…,m}表明了各个对象在个属性上的稀疏情况,称为第i个对象在第j个属性上的稀疏特征。如果yij=1,表明第i个对象在第j个属性上是非稀疏的;如果yij=0,则表明第i个对象在第j个属性上是稀疏的。实际上从客户购买产品的角度来看,如果yij=1,表明第i个客户购买了第j种产品;如果yij=0,表明第i个客户没有购买第j种产品。

在文献[16]中,上述问题被称为具有“高维稀疏数据”的问题。

2.2零子空间

由于高维稀疏数据中存在大量的零属性值,则经过数据预处理获得的子空间中存在稀疏子空间,甚至包括属性值全为零的子空间。

定义2(零子空间)全部元素都是零值构成的子空间,我们称之为“零子空间”。 ,零子空间记为: 。

在高维数据挖掘中, 将数据点对数据挖掘的过程中起作用、对最终挖掘结果的产生有贡献的维, 称为非冗余属性,否则就是冗余属性。高维稀疏数据中存在大量的零属性值,故这些具有零属性值的属性是冗余属性,也可以说具有零属性

值的属性是冗余属性的一个特例。冗余属性不仅数据挖掘增加算法不必要的开销,而且影响算法处理效果和性能。因此,剔除零子空间是优化稀疏子空间的一种必要途径,对提高子空间质量具有重要意义。

3 RZABUBS算法

本文将基于二进制数代码提出稀疏特征值的计算公式,并根据稀疏特征值的取值情况,判断是否存在零子空间:假设对象-属性空间为m×n维,如果p个对象的稀疏特征值中存在连续q个零值( ),则存在p×q维的零子空间 。

即:D=count(O1 OR O2 OR…OR Om)

其中O1, O2… Om分别为对象1,2,…m对应稀疏特征值的二进制编码序列,OR 为布尔或运算, count(*) 统计运算结果中含0的总个数。

若 ,则对象a和对象b构成的空间中存在如表1的零子空间 。

例如:表2是6个对象,8个属性构成的稀疏对象-属性空间。

则对象O4和O5的二进制代码为:O4=11111000, O5=10011000,

D=count(O4OR O5)= count (( 11111000) OR(10011000))= count ( 11111000)=3

故对象O4和O5中存在3个连续零:A6, A7 和A8 ,因此,存在一个2×3的零子空间 ,如表3所

4 算法应用

图1是高维稀疏数据:30个对象45个属性取值的情况,下面就以这30×45的对象-属性空间为例,运用算法进行剔除零子空间实现优化子空间的实验。经过对象-属性空间分割数据预处理后,得到相应的子空间,如图2。

从图可以看出,30×45的对象-属性空间经过分割技术的数据预处理后,获得的子空间包括两类:一类为零子空间和非零子空间。

本文运用RZABUBS算法,获得D1,D2,D3,D4和D5是零子空间。剔

除这些零子空间后,原对象-属性空间由最终可以分解的子空间主要有3个低维子空间,维数分别为:10×13,7×12和11×16,如图3所示。因此,原对象-属性的子空间得到了优化,子空间的质量获得了提高。

5.结束语

高维稀疏数据集在日常生活中占的比重越来越大,对这些数据进行预处理显得尤为重要, 故子空间的研究受到越来越多的关注。本文从稀疏性的角度提出了RZABUBS算法,通过剔除零子空间实现子空间的优化,提高子空间的质

量, 最终提高数据预处理的效果。

参考文献:

[1] Jiawei Han, Micheline Kamber. 数据挖掘概念与技术(范明,孟小峰等译)

[M].北京:机械工业出版社,2001

[2] Yang Q, Wu X. 10 challenging problems in data mining research[J]. International Journal of Information Technology and Decision Making, 2006, 5(4): 597−604.

[3] Tan S, Cheng X, Ghanem M, et al. A novel refinement approach for text categorization[C]//Proceedings of the ACM 14th Conference on Information and Knowledge Management, 2005: 469−476.

[4] AGRAWAL R, GEHRKE J , GUNOPULOSD, et al . Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications [ C ] / /A shutosh Tiwary . Proceedings of ACM SIG MOD International Conference on management of data, Seattle: ACM Press, 1998: 942 105 .

[5] AGGARWAL CC, PROCOP I UC C, WOLF J L, et al . Fast Algorithms for

[6] Projected Clustering[ C ] / / Proceedings of ACM SIG MOD International Conference on Management of Data, Philadelphia: ACM Press, 1999: 61272 .

[7] AGG ARWAL CC, Y U P S . Finding Generalized Projected Clusters in High Dimensional Space [ C ] / /Proceedings of ACM SIG MOD International Conference on Management of Data, Dallas : ACM Press, 2000: 702 81 .

[8] 牛琨, 张舒博, 陈俊亮. 采用属性聚类的高维子空间聚类算法 [ J ]. 北京邮电大学学报, 2007, 30 (3) : 125-127 .

[9] 王国仁, 黄健美等. 基于最大间隙空间映射的高维数据索引技术[J]. 软件学报,2007,18(6) :1419-1428

[10] 李霞,徐树维. 子空间聚类改进算法研究综述[J]. 计算机仿真.2010,27(5):174-177

[11] 任家东, 周玮玮, 何海涛. 高维数据流的自适应子空间聚类算法[J]. 计算机科学与探索. 2010, 4(9):859-865

[12] G.J.Gan,J.H.Wu, A convergence theorem for the fuzzy subspace clustering(FSC) algorithm,PatternRecognition41(2008)1939–1947.

[13] L.P.Jing, M.K.Ng, Z.X.Huang, An entropy weighting k-means algorithm for Subspace clustering of high-dimensional sparse data, IEEETrans. Knowl. Data Eng. 19(8)(2007)1026–1041.

[14] 许倡森. 基于混合网格划分的子空间高维数据聚类算法[J]. 计算机技术与发展.2010,10(10)

[15] 许倡森. 基于混合网格划分的子空间高维数据聚类算法[J]. 计算机技术与发展.2010,20(10):150-153

[16] Chu Y, Chen Y, Yang D, et al. Reducing redundancy in subspace clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(10): 1432−1446.

[17] 武森. 高属性维稀疏聚类[D].北京科技大学,2002

主要研究方向:数据挖掘,管理优化,计算机控制。

范文六:基于子空间跟踪的MIMO―OFDM稀疏信道估计 投稿:任腽腾

摘 要

  本文提出了一种可用于MIMO-OFDM系统的稀疏信道估计算法。算法利用了MIMO信道特性改进了子空间跟踪算法中的度量函数,使得在缺乏信道稀疏度和信噪比先验信息的情况下,大大提高了信道估计性能,并逼近已知信道时延的最优LS算法。仿真结果验证了算法的有效性。【关键词】MIMO-OFDM 稀疏信道估计 压缩感知 子空间跟踪

  1 引言

  近年来为了适应新的移动通信标准中高吞吐率、高频谱效率的需求,正交频分复用(OFDM)和多天线(MIMO)技术已经逐渐成为了核心技术。使用导频进行OFDM信道估计的算法中有一类称作时域信道估计的算法在时域上对信道冲激响应进行估计,然后做FFT得到频率响应。然而,在系统采样率较高的情况下,无线信道时延扩展大,径个数较少,呈现出稀疏的特性,因此利用内在稀疏这一先验知识的稀疏信道估计算法受到关注,它能在实现复杂度较低的情况下有较好的性能表现。目前已有稀疏信道估计算法基于压缩感知(Compressive Sensing)理论,如实现较为简单的匹配跟踪(Matching Pursuit)算法、正交匹配跟踪(Orthogonal Matching Pursuit)算法,以及W. Dai等人提出的子空间跟踪算法(Subspace Pursuit),其性能和收敛速度均好于OMP算法。

  本文所关注的算法是基于子空间跟踪的稀疏信道估计算法,我们将其改进并用于MIMO-OFDM系统,改进的算法基于以下几点事实:(1)已有算法需要知道信道稀疏度K或信噪比;(2)传统的稀疏信道估计算法都是基于SISO信道;(3)SP算法的相关度量函数每次迭代都重新计算,并没有利用上一次迭代的度量信息。仿真结果表明,改进的联合子空间跟踪(Joint Subspace Pursuit)算法性能优于传统的稀疏信道估计算法,并逼近最优的已知多径时延的LS算法。

  2 算法模型

  考虑一个Nr×Nt的MIMO-OFDM系统,子载波个数为N,若导频子载波个数为P,L为最大时延采样位置,则接收端去CP并做FFT后,在任意一根接收天线上,

  y=XH+n=XWh+n (2.1)

  上式中,, ,Xi为第i个发送符号,h(l)为信道冲激响应,为DFT矩阵,。本文根据3GPP LTE协议中所规定的交错状分布导频设计算法,因此导频上的接收信号为,

  (2.2)

  其中S为P×N的选择矩阵,用于从N个子载波中选出 P个导频子载波,即从N×N单位阵中选出导频位置的 P行,式(2.2)即本文所做稀疏信道估计算法的信号模型。

  3 算法分析和设计

  3.1 最优LS估计

  通常稀疏信道估计的做法是迭代式的查找稀疏向量H中的非零元素位置,然后求解:

  (3.1)

  对于(3.1)式问题,一般使用Least Square方法估计如下,

  (3.2)

  上式中,,由集合Γ所指定的Φ中的列向量组成,yr为上一次迭代得到的残差向量。若已知当前符号块内衰落信道准确的时延位置,即有最优LS估计,

  (3.3)

  这里,集合I为信道准确时延位置。上式的估计即为 在集合I上的信道冲激响应,其余位置则为零。

  3.2 联合子空间跟踪算法

  子空间跟踪(Subspace Pursuit)算法每次维护一组基向量,在每次迭代的过程中根据当前基向量的相关度量(Correlation Metric)和投影度量(Projection Metric)即时的更新这组基向量,使得每次迭代后的基向量组更能准确的重构y,然后根据当前计算的残差度量(Residual Metric)决定迭代是否继续进行。

  对于SP算法,我们做如下改进:

  (1)现有的匹配跟踪算法中,稀疏度K选取的不恰当会引起多径的漏估或者多估。因此可以设置一个较大的值作为算法初始的稀疏度K,随着迭代的进行,当残差度量值发生一个较大的突变时停止迭代。

  (2)SP算法中的相关运算是迭代过程中增加备选基向量的度量值,投影运算则是删除备选向量的度量值。如果利用MIMO各个信道时延相同的特性,对各个信道的相关度量和投影度量做加权合并,则可大大提高算法跟踪基向量的准确度。

  相关度量合并:Cl=Cl-1+

  投影度量合并:Pl=

  残差度量合并:Rl= (3.5)

  其中,,加权系数取决于每条信道上发送的导频个数,。上式的相关合并中保留了上一次迭代的度量信息,使得随着迭代的进行,径选取的可靠性会越来越高。

  改进的联合子空间跟踪算法(JSP)如下:

  初始化:时域径集合由式(3.5)计算

  迭代:

  1.由式(3.5)计算相关度量,扩大时域径集合。

  2.计算 。

  3.由式(3.5)计算投影度量 ,筛选时域径集合。

  4.由式(3.5)计算残差度量,其中 。

  5.若Rl=Rl-1>0,迭代终止,令。否则回到1,并令K=K-1,。

  输出:时域响应,满足 ,=0。

  4 仿真与性能分析

  为了比较以上讨论的几种稀疏信道算法的性能,本文做了信道估计均方误差(MSE)和误比特率性能(BER)的仿真和比较。仿真选取2发2收,10MHz带宽,调制方式为16QAM的系统配置,其子载波个数为600个。信道选取LTE标准中建议仿真使用的Extended Typical Urban模型,该信道模型共有9径,系统做1024点FFT,可见信道冲激响应是非常稀疏的。

  图4-1比较了几种时域信道估计算法的MSE性能,其中性能最好的是已知时延的LS算法,本文算法比现有的MP,OMP和SP算法性能好3dB-8dB,与已知时延的LS算法性能最大差距3dB,随着信噪比的提高差距逐渐缩小至1dB不到。相比之下,JSP算法不存在其他3种算法随着信噪比的提高其性能出现地板效应的缺点,这主要是因为随着信噪比的提高,JSP算法能收敛到准确的时延位置,因此与理想LS算法性能接近。图4-2给出了几种算法的BER性能对比,可见JSP算法与理想的LS算法性能接近,差距不到0.1dB,验证了改进的信道估计算法的有效性。   5 小结

  本文研究了MIMO-OFDM系统的稀疏信道估计算法,通过利用MIMO信道特性改进子空间跟踪算法的3个度量函数并实时改变稀疏度,使得信道估计算法性能得到较大的提升,随着信噪比的增加逐渐逼近最优LS算法性能。把改进算法用于新的移动通信标准平台上,获得了较好的误比特率性能,仿真结果验证了以上结论。

  参考文献

  [1]王文博,郑侃.宽带无线通信OFDM技术(第二版)[M].北京:人民邮电出版社,2007(8).

  [2] P. Maechler, P. Greisen, N. Felber, and A. Burg, “Matching pursuit: Evaluation and implement- tation for LTE channel estimation,” in ISCAS Proceeding, March 2010, pp 589-592.

  [3] TROPP J A,GILBERT A c, Signal recovery from random measurements via Orthogonal matching pursuit[J].IEEE Transactions on lnformation Theory,2007,53(12):4655-4666.

  [4] W. Dai and O. Milenkovic.Subspace pursuit for compressive sensing signal reconstruction. IEEE Transactions on lnformation Theory, vol. 55, no. 5, pp. 2230-2249, May 2009.

  [5] E-UTRAN:User Equipment radio transmission and reception,3GPP Std.TS 36.101,Sept.2009.

  作者简介

  黄陈横,2012年毕业于中国科学技术大学通信与系统专业,硕士学历。现就职于广东省电信规划化设计院有限公司电信咨询设计院,主要从事移动网络规划设计工作。

  作者单位

  广东省电信规划设计院有限公司电信咨询设计院 广东省广州市 510630

范文七:一种压缩采样中的稀疏度自适应子空间追踪算法_杨成 投稿:顾趾趿

󰀁

第8期2010年8月电󰀁󰀁子󰀁󰀁学󰀁󰀁报ACTAELECTRONICASINICAVol.38󰀁No.8

󰀁

Aug.󰀁2010

一种压缩采样中的稀疏度自适应子空间追踪算法

杨󰀁成,冯󰀁巍,冯󰀁辉,杨󰀁涛,胡󰀁波

(复旦大学电子工程系,上海200433)

󰀁󰀁摘󰀁要:󰀁针对压缩采样中未知稀疏度的信号,本文提出一种自适应子空间追踪算法.首先,采用了一种基于匹配测试的估计方法获取稀疏度的估计值,再通过子空间追踪重构信号.若子空间追踪不能成功重构,则通过渐近增加信号稀疏度的方法实施估计,而上述过程可描述为在弱匹配原则下新原子的选取过程.仿真结果表明,本文的算法可以准确有效重构信号,同时运算量也较低.

关键词:󰀁压缩采样;子空间追踪;稀疏分解

中图分类号:󰀁TP391󰀁41󰀁󰀁󰀁文献标识码:󰀁A󰀁󰀁󰀁文章编号:󰀁0372󰀂2112(2010)08󰀂1914󰀂04

ASparsityAdaptiveSubspacePursuitAlgorithmforCompressiveSampling

YANGCheng,FENGWei,FENGHui,YANGTao,HUBo

(ElectronicEngineeringDepartment,FudanUniversity,Shanghai200433,China)

Abstract:󰀁Anovelsparsityadaptivesubspacepursuitalgorithmisproposedforsparsesignalswithunkownsparsity.First,anewsparsityestimationmethodbasedonmatchingtestisusedtogetaninitialestimatedvalue.Ifsubspacepursuitcannotreconstructsparsesignalsuccessfully,theestimatedvalueisincreasedeachiteration.Weakmatchingisusedintheiterationtoselectnewatoms.Comparedtootheralgorithms,itiscompetitivebothinrunningspeedandrecoveringaccuracy.

Keywords:󰀁compressivesampling(CS);subspacepursuit;sparsedecomposition

1󰀁引言

󰀁󰀁压缩采样(CompressiveSampling,CS)针对具有稀疏性或在特定域上可转化为稀疏性的信号,通过实施远低于奈奎斯特采样率的的随机采样,可准确完成原始信号的重构[1~4].由于CS有效降低了信号获取、存储及传输的代价,该理论一经出现即得到广大研究人员的密切关注.设x是一个长度为N的实向量,即x󰀂RN.x中只有不超过K个非零元素,x被称作K󰀂稀疏.研究表明:对x进行随机线性投影,即y=󰀁x,其中y是M维观测向量(M N),󰀁是M N的测量矩阵,则基于y可有效完成信号x的重构.

如何在已知y和󰀁的条件下快速、有效的重建x是CS研究的一个重要方面[5].目前已有的方法可包括组合优化,非凸优化,凸优化,贪婪算法等几类.凸优化方法通过求解一个最小化凸问题逼近信号,如基追踪(BasisPursuit)[6]等.这些算法中,贪婪算法由于算法结构简单,运算量小等特点受到重视.传统贪婪算法匹配追踪(MP)[7]、正交匹配追踪(OMP)[8,9]已在压缩采样中得到了应用.改进的算法包括分段正交匹配追踪(Stage󰀂wiseOMP,StOMP)[10]、正则化正交匹配追踪(RegularizedOMP,ROMP)[11].这几种算法只有在信号具有较低的稀

收稿日期:2009󰀂07󰀂10;修回日期:2010󰀂03󰀂31

疏度时才能较好地重建信号.子空间追踪(SubspacePur󰀂

suit,SP)[12]和压缩采样匹配追踪(CompressiveSamplingMatchingPursuit,CoSaMP)[13]是两种比较相似的算法,具有较好的性能.但是SP和CoSaMP要求信号稀疏度已知,这在很多应用中难以满足.如果对稀疏度的估计不准确,很多信号不能得到精确重建.文献[14]中提出的稀疏度自适应匹配追踪(SignalAdaptiveMatchingPursuit,SAMP)算法在每次迭代中采用增加固定数目原子的方法估计信号稀疏度.当K较大时,SAMP算法由于迭代次数多而导致运算量特别大.

2󰀁自适应子空间追踪算法

󰀁󰀁在给出自适应子空间追踪算法构造之前,首先分析约束等距性质(RestrictedIsometryProperty,RIP),它是重建x的重要基础.文献[4]提出了RIP性质用于描述从y重建x的条件.指定!范数.如果对所有满足x(1):

(1-󰀂K)x

表示l0范数,!2表示l20∀K的x,矩阵󰀁都满足式

22∀

∀󰀁x

(1+󰀂K)x2

2

(1)

󰀁󰀁那么称󰀁是以参数(K,󰀂K)满足RIP性质的线性算子.目前研究发现当测量次数M足够大时,高斯随机矩阵,伯努利随机矩阵等以极大的概率满足RIP性质[1].

基金项目:国家自然科学基金(No.60972024);教育部博士点基金(No.20090071120087);专用集成电路与系统国家点实验室开放课题(No.

第󰀁8󰀁期杨󰀁成:一种压缩采样中的稀疏度自适应子空间追踪算法1915

󰀁󰀁CS的信号重建可以看成信号稀疏分解问题.如果把󰀁的列向量vi(1∀i∀N)看作原子并归一化,它们的集合构成超完备字典D.由于x中有K个非零元素,观测值y可以看作由D中K个原子线性组合表示的信号.设这K个原子的索引组成集合 ,y可以表示成y=󰀁 x .其中󰀁 表示由󰀁索引在 中的列向量所组成的子矩阵.x 表示x中索引在 中的元素组成的向量.y在字典D上具有稀疏的表示,即可寻找最少的一组原子{vi|i󰀂! },使残差信号r=y-󰀁! x! 能量最小.

本文提出的SASP算法的目标是在K未知条件下找到这样一组原子{vi|i󰀂! }.其基本思想如下(见图1):首先,SASP使用一种稀疏度估计方法得到集合 0, 0中元素数小于K.SASP通过后续迭代改善估计并重建x.设在第n次迭代中通过子空间追踪选取出原子{vi|i󰀂 n}.如 n中原子能很好地表示y说明对K的估计是准确的.否则选取新的原子将其索引加入 n,并重复上述过程.下面分别从稀疏度估计,新原子选取,子空间追踪三部分描述SASP算法

.

,综合

K1-󰀂K*

不等式(2)、(3)可以得到󰀁∀y2. y2#

1+󰀂K

2

󰀁󰀁再由RIP性质的定义可知x#

y

2

得证.

1+󰀂K

y时,K0

*

根据以上结论的逆否命题,当󰀁 0y

2<

1-󰀂K

y2则

K

依次增加K0直到不等式不成立,同时得到的是对 的初始估计 .

0󰀁* y

2<

1-󰀂2.2󰀁新原子选取

当子空间追踪无法通过迭代使残差能量满足给定阈值时,可选取更多的原子表示y.SASP算法采用弱匹配策略选取与残差信号比较接近的原子,并将其索引加入集合 n.令g=󰀁*r,则g中第i个元素gi是原子向量vi与残差信号r的内积,即.引入实数#为弱匹配参数,#󰀂(0,1].SASP选取所有满足|gi|##

1∀j∀N

max|gj|的原子,则 n的更新可表示为

n= n-1∋{i:|gi|##max|gj|}

1∀j∀N

弱匹配可以看作选取残差的投影大于一定阈值的原子,该阈值与max|gj|有关.#=1时,与OMP类似每

1∀j∀N

2.1󰀁稀疏度估计

以下给出一种稀疏度估计方法,其思路是通过匹

配测试得到一个原子集合,使其势K0略小于K.令g=󰀁*y,󰀁*表示󰀁的转置矩阵.设信号y的真实支撑集为 ,用|!|表示集合的势,则| |=K.设g中第i个元素为gi,取|gi|前K0(1∀K0∀N)个最大值的索引得到的集合为 ,| |=K0.

次迭代只选取与残差最匹配的单个原子, n中每次增加一个元素.当#比较小时,每次迭代可能选取多个原子.所以通过弱匹配可以根据信号调整增加的原子数.已有实验表明,参数#取值0󰀁7~0󰀁9之间可以兼顾算法性能和运算速度.

命题󰀁设󰀁以参数(K,󰀂K)满足RIP性质.如果

1-󰀂*K

K0#K,则󰀁 0y2#y2.

K

证明󰀁取|gi|(1∀i∀N)中前K个最大的元素的

索引得到集合∀ ,K0#K时有∀ # ,显然󰀁*∀ y2.

󰀁* y∀

2

󰀁* y

2

#

2.3󰀁子空间追踪

子空间追踪部分也通过迭代改进估计结果,每次迭代中采用了一种后退策略[12].算法的结构如图2所示.设经过n次迭代后得到原子的索引集合为 n,残差信号为rn.在第n次迭代中,将rn-1分别投影到字典D的各个原子向量上,并选出投影最大的| n-1|个原子.

n-1n-1

把它们的索引与 合并得到集合^ ,^ 中有2| |个元素.再把y投影到原子向量{vi|i󰀂^ }张成的空

间,从^ 中去除系数最小的| |个原子的索引得到∀ ,|∀ |=| n-1|.再次把y投影到原子{vi|i󰀂∀ }张成

n-1

=max

|!|=K

i󰀂!

|%vi,y&|2󰀁󰀁󰀁 󰀁 x

*

2

#󰀁 y

*

2=

(2)1-󰀂K和

的空间,如果得到的残差能量小于r的能量则更新 n并重复上述过程.文献[12]证明如果󰀁以参数(K,󰀂P性质且󰀂3K)满足RI3K<0󰀁165,则有

r

n

2

n-1

󰀁󰀁根据RIP的定义,󰀁 的奇异值在有1-󰀂(󰀁*K∀∀ 󰀁 )∀1+󰀂K,所以可以得到

*

<

(󰀁*K之间.如果用∀ 󰀁 )表示矩阵的特征值,则

1916󰀁󰀁电󰀁󰀁子󰀁󰀁学󰀁󰀁报2010年

rn-12,子空间追踪可以从y准确重建x.

算法步骤(8).子空间追踪部分第(10)、(12)步分别需要求解一次最小二乘问题.算法外层迭代次数与每次选取的原子数和信号的稀疏度相关.

2.4󰀁算法步骤

输入:M维观测向量y,M N维测量矩阵󰀁输出:重建信号x^,x^ n=argminy-󰀁 nx n

xn

22,

^中其它元素为零x

3󰀁实验结果

3.1󰀁稀疏度估计

为了验证SASP算法中稀疏度估计的结果,本节通过实验测试稀疏度估计部分.实验中,M=256,N=512,󰀁为M N高斯随机矩阵,每项元素是独立分布零均值单位方差的高斯随机变量.从x0中随机取K个

元素,每一项值为独立分布零均值单位方差高斯随机变量,x0中其它元素值为零.通过y=󰀁x0得到观测向

(1)󰀁g0=󰀁*y,K0=1

(2)󰀁 0={|g0i|前K0个最大值索引}

0(3)󰀁如果󰀁* y

2<

1-󰀂KK

2

2

y

2,则K0=K0+1,重复(2)

(4)󰀁r0=miny-󰀁 0x 0(5)󰀁n=1(6)󰀁gn=󰀁*rn-1

n-1

(7)󰀁^ = n-1∋{|gn|个最大值索引}i|前|

(8)󰀁x^ =argminy-󰀁^ x^

x^

量y,图中横坐标表示实验次数,纵坐标表示K的估计值.图3中比较了K=51条件下󰀂K取不同估计值时得到的K估计值.

(9)󰀁∀ ={|x^ |前| n-1|个最大值索引}(10)󰀁∃r=miny-󰀁∀ x∀ (11)󰀁如果∃r

2

2<

2222,

rn-1 n=∀ ,rn=∃r,n=n+1,重复(6)

(12)󰀁如果满足迭代终止条件算法退出,否则 n= n-1∋{i:|gni|

##max|gjn|},重复(6)

1∀j∀N

3.2󰀁信号重建实验

这一部分比较OMP、StOMP、ROMP、SP、SAMP、SASP算法性能和运算时间.实验测试K取不同值的结果,其它设置与上一节相同.信号准确重建的条件设为x和x0中非零元素位置一样,且误差的能量小于10-15.

StOMP中阈值ts取3,SAMP中步长s=1,SASP中#=0󰀁7,󰀂K取估计值0󰀁3.算法中最小二乘问题都采用QR分解法求得,终止条件都设为残差能量小于∃=10-5y.算法在IntelCore2DuoE8400机器上运行,软件版本为MatlabR2008a.实验中OMP和StOMP算法的实现采用的是SparseLab(http://www.sparselab.stanford.edu/)工具箱.SAMP和ROMP的实现采用作者提供的代码.对于不同的K值,所有算法都运行500次来计算重建成功率和平均运行时间.

图4中表示不同稀疏度下信号准确重建率.从图4中可以看出本文提出的算法性能超过OMP、StOMP、ROMP和SP算法,与SAMP相比性能相当.当K/N大于0󰀁25时SASP和SAMP才会有较多信号不能成功重建.图5表示了各个算法运行平均时间.相比SP算法,SASP因为迭代次数增加而导致运算时间超过SP.而与SAMP算法相比,SASP的运算时间远小于SAMP.

󰀁󰀁第(1)~(4)步为稀疏度估计部分,得到初始估计集合 0和残差r0.第(5)步初始化迭代次数.第(6)~(12)步为SASP算法迭代主体.第(6)~(11)步通过子空间追踪改进估计结果.第(12)步判断终止条件是否满足,如果满足整个算法退出.否则通过弱匹配在 n中加入新选取的原子的索引.因为rn-1与vi(i󰀂 n-1)正交, n-1中元素不会被重复选出.算法的终止条件可设为:(1)当残差能量小于一定值时终止;(2)当原子与残差的相关小于某个阈值时终止.

2.5󰀁算法分析

n

由r

n2rn-122<2可知r能量单调递减,算法至少收敛到一个局部最小点.稀疏度估计部分主要运算在于求M次投影,计算量相对较小.SASP算法的计算复杂度与外层迭代的次数密切相关,其上限为O(K2MN).整个算法的计算量中对最小二乘问题求解占很大一部分.在外层迭代中每次重复需要求解一次最小二乘问题,即

第󰀁8󰀁期杨󰀁成:一种压缩采样中的稀疏度自适应子空间追踪算法1917

3.3󰀁图像实验

实验中使用的图像是256 256像素的Lena图像,采样矩阵采用结构化随机采样矩阵[15].实验比较了各个算法重建图像的PSNR和运算时间,所有算法选取出约3000个原子后终止.为了加快SAMP运算时间,实验比较了步长分别取s=50和s=100的结果.所有算法中对于大规模最小二乘问题的求解都采用LSQR算法.

表1比较了不同算法重建图像的PSNR和运算时间.从表中可以看出SASP重建图像PSNR最高,运算时间也较短.SAMP需要取合适的步长s才能在运算时间和重建效果间取得一个较好的平衡.

表1󰀁不同算法重建时间与性能比较

Lena(M=0.3*N)Lena(M=0.4*N)Lena(M=0.5*N)

算法OMPStOMPROMPSPSAMP(s=50)SAMP(s=100)SASP

PSNR(dB)27.2421.6223.0427.1727.2727.2527.50

运行时间(s)336.310.811.7419.57217.31118.4819.25

PSNR(dB)28.8123.9726.1327.6729.1229.0629.29

运行时间(s)338.260.852.5910.47217.34122.6519.03

PSNR(dB)29.3626.4527.0229.4929.6229.5629.80

运行时间(s)339.300.912.416.40206.25109.2619.20

theoryandapplicationofcompressedsensing[J].ActaSinicaElectronica,2009,37(5):1070-1081.(inChinese)

[6]SSChen,DLDonoho,MA.Saunders.Atomicdecompositionbybasispursuit[J].SIAMRev,2001,43(1):129-159.[7]SMallat,ZZhang.Matchingpursuitswithtime󰀂frequencydic󰀂

tionaries[J].IEEETransSignalProcess,1993,41(12):3397-3415.

[8]JATropp.Greedisgood:Algorithmicresultsforsparseap󰀂

proximation[J].IEEETransInfoTheory,2004,50(10):2231-2242.

[9]JATropp,ACGilbert.Signalrecoveryfromrandommeasure󰀂

mentsviaorthogonalmatchingpursuit[J].IEEETransInfoTheory,2007,53(12):4655-4666.

[10]DLDonoho,YTsaig,IDrori,etc.Sparsesolutionofunder󰀂

determinedlinearequationsbystagewiseOrthogonalMatching

Pursuit[OL].2007,http://www󰀂stat.stanford.edu/~dono󰀂ho/Reports/2006/StOMP󰀂20060403.pdf.[11]DNeedell,RVershynin.Uniformuncertaintyprincipleandsignalrecoveryviaregularizedorthogonalmatchingpursuit

[OL].http://arxiv.org/abs/0707.4203,2007󰀂7󰀂28/2008󰀂3󰀂15.

[12]WDai,O.Milenkovic.Subspacepursuitforcompressivesens󰀂

ingsignalreconstruction[OL].http://arxiv.org/abs/0803.0811,2008󰀂3󰀂6/2009󰀂1󰀂8.

[13]DNeedell,JATropp.CoSaMP:Iterativesignalrecoveryfrom

incompleteandinaccuratesamples[J].AppliedandComputa󰀂tionalHarmonicAnalysis,2009,26:301-321.

[14]ThongTDo,LuGan,NamNguyenetc.Sparsityadaptive

matchingpursuitalgorithmforpracticalcompressedsensing

[A].ProcAsilomarConferenceonSignals,Systems,andComputers[C].PacificGrove,CA,UnitedStates:IEEESig󰀂nalProcessingSociety.2008.10:581-587.

[15]TDo,TTran,LGan,Fastcompressivesamplingwithstruc󰀂

turallyrandommatrices[A].ProcICASSP[C].Piscataway:

InstituteofElectricalandElectronicsEngineersInc.2008.5:3369-3372.作者简介:

杨󰀁成󰀁男,1982年生于江苏兴化,现为复旦大学电子工程系博士研究生,主要研究方向:信号与图像处理.

E󰀂mail:cyang@fudan.edu.cn

4󰀁结论

󰀁󰀁本文提出了一种自适应子空间追踪算法SASP,该算法可以在未知信号稀疏度的情况下准确重建信号.

算法使用一种新的稀疏度估计方法得到稀疏度的初始估计值,然后通过迭代进行估计的更新.在每次迭代中采用弱匹配原则选取新原子,再通过子空间追踪改善结果并重建信号.实验表明,SASP算法可以有效地重建稀疏信号,同时具有较低的运算量.

参考文献:

[1]DLDonoho.Compressedsensing[J].IEEETransInfoTheo󰀂

ry,2006,52(4):1289-1306.[2]EJCand󰀁s,JRomberg,TTao.Robustuncertaintyprinciples:

Exactsignalreconstructionfromhighlyincompletefrequency

information[J].IEEETransInfoTheory,2006,52(2):489-509.

[3]EJCand󰀁s,TTao.Near󰀂optimalsignalrecoveryfromrandom

projections:Universalencodingstrategies[J].IEEETransInfoTheory,2006,52(12):5406-5425.[4]EJCand󰀁s,TTao.Decodingbylinearprogramming[J].IEEE

TransInfoTheory,2005,51(12):4203-4215.[5]石光明,刘丹华,高大化,等.压缩感知理论及其研究进展

[J].电子学报,2009,37(5):1070-1081.

s冯󰀁巍󰀁男,1983年生于辽宁沈阳,现为复旦大学电子工程系博士研究生,主要研究方向:图像处理.

范文八:1一种新的子空间聚类算法 投稿:方燰燱

 第41卷第5期 2007年5月

上海交通大学学报

J

OURNALOFSHANGHAIJIAOTONGUNIVERSITY

Vol.41No.5 

May2007 

  文章编号:100622467(2007)0520813205

一种新的子空间聚类算法

何虎翼, 姚莉秀, 沈红斌, 杨 杰

(上海交通大学图像处理与模式识别研究所,上海200240)

摘 要:,网格的新的子空间聚类算法.,同时运.,所提算法在精度、时间复关键词:聚类;中图分类号:文献标识码:A

ANewSubspaceClusteringAlgorithm

HEHu2yi, YAOLi2xiu, SHENHong2bin, YANGJie

(Inst.ofImageProcessing&PatternRecognition,ShanghaiJiaotongUniv.,Shanghai200240,China)Abstract:Anewkindofsubspaceclusteringalgorithmbasedondensityandgridswasproposed.Bounda2riesbetweenclassesarelocatedbypartitioninggridsinthedataspaceandfindingsparseregions.Thenewalgorithmusesthesearchingstrategyofprojectedpursuittofindtheclassesinthesubspace.Acompetitivepruningprocedureisutilizedtoreducethecomputationalcomplexity.Theexperimentalresultsonthebenchmarkdatasetsshowthattheproposedalgorithmhasadvantagesinaccuracyandcomputationalcom2plexity.

Keywords:clustering;subspace;grids;sparseregion

  在数据挖掘、机器学习及信息处理等领域,无监督的聚类算法日益受到人们的欢迎并得到广泛的应用[1,2].基于密度的聚类方法认为:一个类就是数据空间中被低密度区域分割开的高密度对象区域.高维数据的研究者们发现,很多真实数据的类仅存在于子空间内.因此,子空间聚类算法被提出并得到了快速的发展.CLIQUE算法[3,4]通过发现数据集中的稠密单元并运用一些方法拼接这些单元生成子空间进而得到需要的类.受该算法的启发,本文从发现数据集在各维投影的稀疏单元出发来发现类的边界,通过一种投影寻踪的搜索算法来得到适于表达

收稿日期:2006206204

的子空间及其内含的类,运用基于竞争的修剪方式来控制算法的计算复杂度,提高了算法的精度,降低了计算的复杂程度.虽然与CLIQUE算法相比增加了一个输入参数,但得到了较好的对输入参数的鲁棒性.

1 平行坐标系的高维数据可视化

  传统坐标系中的轴均相互交叉.如图1所示,在平行坐标中,所有的轴均平行且间距相等.将数据集的点分别在各维投影,并将对应投影点用直线连接起来就实现了高维数据的平行坐标系可视化[5].

作者简介:何虎翼(19782),男,四川蓬安人,硕士,从事数据挖掘与机器学习方面的研究.

姚莉秀(联系人),女,副教授,电话(Tel.):021234204010;E2mail:lxyao@sjtu.edu.cn.

814

上 海 交 通 大 学 学 报

第41卷 

或空间上一或多个稠密区域上的投影点数q的比

值,即δ=p/q.2.2 单一维边界识别

  在每一维上都可以通过数据投影的稀疏区域来寻找类的边界,故首先将数据集的每一维在数域上进行等间距等ξ的网格划分.通过τ来得到稀疏单元,将相邻的稀疏单元连接起来构成全域范围的稀

↑—坐标轴,  ——单元或类的边界

→—类内数据集的投影指向,即搜索指示

图1 平行坐标系

Fig.1 Parallelcoordinates

疏区域.接下来去掉数域两端的区域得到内含边界

的稀疏区域,.单

2   ,按照基本概念和参数说明、单一维边界识别、基于竞争的修剪、适于表达的子空间及类的生成4个部分对算法做全面的陈述.2.1 基本概念和参数说明2.1.1 基本概念  定义 类的边界.类的边界存在于将稠密区域分割开的稀疏区域中.按平均误差最小的原则,将类的边界定义为稀疏区域的中点.

定理[3] 若在K维数据空间的点集S是一个聚类,则S也是该数据空间的任意一个K-1维投影中一个聚类的一部分.

推论 一维投影的稀疏区域都对应着一个类的边界.

证明 由上述定理递推可知,若在K维数据空间的点集S是一个聚类,则S也是在这个数据空间的任意一维投影中聚类的一部分.则一维投影的聚类将包括所有的K维数据空间表达的数据,一维的稀疏区域也就成为K维数据空间的稀疏区域在一维的投影,构成了类的边界.2.1.2 参数说明 算法要求用户输入3个参数:间隔数ξ、密度域值τ及通过率δ.为了识别数据点的密度,将数据空间进行划分,找出划分后每个单元中的数据点数量.划分的方法是将每个维划分成等长且ξ相同的间隔段,这就意味着每个单元都有相同的体积,故在单元中数据点的数量可用来识别单元的密度[3].τ是单元中的数据点与总的数据点的比值[3],用于选择稀疏的单元.在投影寻踪的搜索过程中利用δ可以克服噪声及区域划分的模糊性带来的影响.所谓通过率,是指在维或空间上的一个类所包含的数据点数p在其他维

图2 单一维边界识别Fig.2 Recognitionofboundary

2.2.1 边界识别的方法———贪婪增长算法[3]

(1)从任一维开始,依据τ得到稀疏单元;(2)从该维数域的一端开始搜索,找到第一个

稀疏单元;

(3)进行深度优先搜索,将相连接的稀疏单元

拼接得到一个稀疏区域;

(4)检查是否有未访问到的稀疏单元,若有,转(3);

(5)将位于数据域两端的稀疏区域删除;

(6)选取区域中点为类的边界并将全域划分成

候选类保存于Candidate-Clusters表中;

(7)将候选类的类内数据编号并保存于data-in-clusters表内;

(8)对每一维进行以上操作直至对全部维的操作完毕;

(9)结束.2.2.2 时间复杂性 设数据集的大小为m×n.算法首先需要对每个数据访问一次以确定稀疏单元并为下一步提供数据,时间复杂性为O(mn);然后需要对每个间隔(单元)访问一次得到稀疏区域,时间复杂性为O(ξn),所以边界识别的总的时间复杂性

)n).为O((m+ξ

2.3 基于竞争的修剪

  基于竞争的修剪主要达到两个目的:①把对聚

类生成无贡献的维排除;②把不能增加贡献的维排除.最终目的是要得到较好的计算复杂性并生成可完全描述类的最大子空间.显然,这种修剪技术几乎

 第5期

何虎翼,等:一种新的子空间聚类算法  

815

不会造成任何的信息损失.2.3.1 无贡献维的修剪 如图3(a)所示,通过边界识别得到位于各维的类投影,只存在一个类投影的维对聚类的生成是无贡献的,可以将它修剪掉.其理由是任何类的投影都位于一个区域或者投影的数据点分布是相对均匀的,它对类的划分没有贡献,故可以在以后的处理中不予考虑.由于现实生活中用数据去描述的事物总是具有比较多的值相近或相似的属性,不构成分类的依据,所以这种修剪将对控制计算复杂性产生很好的效果.2.3.2 等贡献维的修剪 在下面将说明的投影寻踪搜索策略的执行中

,者维的组合对聚类生成的贡献相同

.对于与单一维的等贡献维可以采取静态的修剪策略,而对于与维

的组合是等贡献的维则可以采取动态的修剪策略.这样可以得到最适合表达的子空间,为后续算法的复杂性控制提供很好的辅助.

(1)等贡献维的静态修剪.如图3(b)所示,对于类别数相等的单一维进行搜索,如果存在一一对应的δ大于输入参数的区域,则它们对聚类生成的贡献是一样的,.

(2)如图3(c)所示,在搜,,则修剪掉该维.

(a)无贡献维的修剪(b)等贡献维的静态修剪(c)等贡献维的动态修剪

图3 基于竞争的修剪

Fig.3 Competition2basedpruning

2.4 适于表达的子空间及类的生成(7)结束.

算法通过投影寻踪的搜索策略由不同贡献的维

组合生成适于表达且无冗余维的子空间,并同时生成可用析取范式(DNF)表达的聚类.

2.4.1 算法描述 经过无贡献维的修剪后得到待搜索空间(K维).任取一维xi作为起始搜索维.

(1)选取xi的一个候选类区域Rii;

(2)用Rii内的投影点集Dii在下一维xj各区域

2.4.2 时间复杂性 算法需要进行K-1次搜索

才能生成K维空间内适合描述的最大子空间,需要对每个数据访问一次才能得到参数δi并与δ结合得到类,故时间复杂性为O((K-1)m).

3 关键问题说明

3.1 类的描述区分

的投影与各区域数据点数计算通过率δi;

(3)将xj的各区域Rji按照δi的大小顺序排序,将Rii与Rji依次拼接生成高一维空间的类存于Candidate-Clusters表,把类内数据保存在data-in-clusters表,直到δi满足

mi=1

  对类进行高一维的搜索生成新的描述时存在两

种情况:

①在高一维子空间搜索时无类别数的增加,即新出现维的边界对类的原描述无限制作用;②在高一维子空间搜索时有类别数的增加,即对类的描述会出现新维的控制边界.这种区分有助于通过选择搜索点集来控制1-δ累加效应的影响.3.2 有关联合维描述类的进一步说明  搜索过程中,一个子空间内的类在进行高一维的搜索时会产生类的增长,而原属于类描述的区域并没有发生分裂.这是因为某两个或多个类在某些子空间特定区域上分属各自的数据是纠缠在一起的.如果要强行将这些区域分割为几个区域,则不可避免地导致精度的下降,这也是CLIQUE等算法精度不高的主要原因之一.因此本算法并没有在类的生成过程中对这些区域进行分裂,而是采用联合维

δ∑

i

δ  m≤max{i|Rji}≥

时停止;

(4)依次选取xi的没访问到的区域重复(2)、(3)步直到所有区域被处理;

(5)若搜索后类表信息无增加,则执行基于竞争的动态修剪,返回(1);

(6)利用得到的类表及类内数据对未搜索到的维重复(1)~(5)步直到所有的维搜索完毕,得到类表及类内数据表,将未归属数据作为孤立点或者异常数据存入outliers表输出;

816

上 海 交 通 大 学 学 报

第41卷 

来描述类,使得精度得到了很大程度上的提高.

3.3 如何避免1-δ累加效应  所谓1-δ累加效应,是指在搜索过程中如果始终不加区分地采用先前搜索的通过点集来进行下一次搜索会对算法带来的影响.为了克服区域划分的模糊性,避免噪声数据的影响可能导致的误差,引入了参数通过率δ.如果总是对第一种描述相对应的类采用通过点集来进行搜索,则将会导致误差累积效应,削弱δ对程序精度的控制力.所以对类的描述进行区分,对类的第①种描述采用原点集而不是通过点集来进行下一次搜索,而对第②种描述则采用通过点集来进行搜索.这样,δ控制力,避免误差的扩大化.

法[4,7]、FCM[4,8]、CLIQUE及本文提出的子空间聚类算法作为聚类操作的实现工具.实验参数的选取:传统的谱系聚类法及FCM指定类别数为3,FCM的模糊因子为2;CLIQUE算法采用2~6的间隔数及0.05~0.15以0.01为步长的密度域值共

50组参数;本文算法采用0.05~0.10以0.01为步长的密度域值、0.70~0.80以0.01为步长的通过率及10个间隔共50组参数.表1给出了上述几种算法得到的精度比较,图4是的平行坐标表示、实.

1 resultsbyclusteringonIrisdataset算法谱系聚类法

FCMCLIQUE

对Iris的错分数

13~1716

错误率/%

8.7~11.310.6

4 实验与分析

4.1 实验结果

实验在

Matlab环境下实现,用来自于现实世界的

Iris数据集作为实验对象,用传统的谱系聚类

[6]

≥16(50组参数平均)

6(50组参数平均)

≥10.6

4

本文算法

(a)Iris的平行坐标表示

(b)边界识别及修剪

(c)聚类结果

图4 本文算法用于Iris数据集

Fig.4 TheproposedalgorithmusedtoIrisdataset

  传统的谱系聚类法及FCM对只在子空间内存

在类的高维数据进行聚类操作得到的结果是无意义的.为了验证本文算法的可伸缩性,利用Iris横向和纵向自我复制的扩展方式得到人工合成的大数据集,再利用两个子空间聚类算法进行聚类操作,结果如图5所示,其中tup表示一个数据.由图5可见,

本文算法具有一定的优越性.4.2 实验分析与评价

  实验表明,采用联合维描述边界投影不明显的类,起控制作用的边界只在投影区分相对清晰的维产生,所以能一定程度地避免类内数据的投影在特定维纠缠于一起时对聚类结果所产生的影响,从而提高了聚类结果的精度.算法采用基于竞争的修剪方式,不会造成信息的损失,所以不存在类丢失的情况.聚类结果采用了与CLIQUE算法一样的DNF范式表达.传统的谱系聚类法及FCM都需要指定类别数,因此对输入参数的敏感度很高,需要用户具有很好的领域知识;它们在全空间内进行计算,对于只在子空间内存在类的高维数据而言这类算法是不适用的;本文算法与CLIQUE算法都是基于密度与网格的算法,类别数在搜索过程中在存在类的子空

图5 可伸缩性

Fig.5 Scalability

间内产生,具有较好的高维数据的处理能力,但CLIQUE对输入参数敏感且精度不高,本文算法在

 第5期

何虎翼,等:一种新的子空间聚类算法  

817

宽泛的输入参数范围内都获得了比较高的正确率,有较好的对输入参数的鲁棒性.与数据呈线性的计算复杂性,使算法具有比较好的可伸缩性,有一定的处理大数据集的能力.综合一些文献记录的现存的子空间聚类算法(见表2)可以发现,本文算法在精度、时间复杂性及处理高维数据的能力方面都取得了一定的成绩.

表2 一些聚类算法的性能

Tab.2 Performanceofsomeclusteringalgorithms

能否处

算法谱系聚类法

FCM

[2] 沈红斌,王士同,吴小俊.离群模糊核聚类算法[J].

软件学报,2004,15(7):1021-1029.

SHENHong2bin,WANGShi2tong,WUXiao2jun.Fuzzykernelclusteringwithoutliers[J].JournalofSoftware,2004,15(7):1021-1029.

[3] AgrawalR,GehrkeJ,GunopulosD,etal.Auto2

maticsubspaceclusteringofhighdimensionaldat[J].DataMiningandKnowledgeDiscovery,2005,11:5-33.

[4] HanJiawei,KamberM.:概念与技术[M].

时间复杂性

O(n2)

理高维数据否对输入参数的敏感性())高(类的数目及子空间大小需要指定)

范 明,.,2001:223

-]B.Parallelcoordinates:A

forvisualizingmulti2dimensionalgeometry[C]//ProcVisualization90.Atlanta:IEEEComputerSoci2etyPress,1990:361-370.

[6] BlakeCL,MerzCJ.

UCIrepositoryofmachine

learningdatabases[EB/OL].(1998206207).ht2tp://www.ics.uci.edu/~mlearn/MLRepository.html.

[7] FisherD.Iterativeoptimizationandsimplificationof

hierarchicalclusterings[J].JournalofArtificialIntel2ligenceResearch,1996,27(4):147-180.

[8] HathawayR,BezdekJ.Fuzzyc2meansclusteringof

incompletedata[J].IEEETransSyst,2001,31(5):735-744.

[9] AggarwalCC,YuPS.Findinggeneralizedprojected

clustersinhighdimensionalspaces[C]//Procofthe2000ACMSIGMODInternationalConferenceonMan2agementofData.NewYork:ACMPress,2000:70-81.

[10] AggarwalCC,WolfJL,YuPS,etal.Fastalgo2

rithmsforprojectedclustering[C]//Procofthe1999ACMSIGMODInternationalConferenceonManage2mentofData.NewYork:ACMPress,1999:61-72.

[11] GoilS,NageshH,ChoudharyA.Mafia:Efficient

andscalablesubspaceclusteringforverylargedatasets[R].EvanstonIL:NorthwesternUniversity,1999.

[12] ChangJW,JinDS.Anewcell2basedclustering

methodforlarge,high2dimensionaldataindatamin2ingapplications[C]//Procofthe2002ACMsymposi2umonAppliedcomputing.NewYork:ACMPress,

2002:503-507.

接近O(n)

3

ORCLUS[9]O(K30+K0d)

PROCLUS[10]MAFIA[11]

与数据呈线性与数据呈线性,随维数增长呈指数级增长

是是

很高一般

CBF[12]CLIQUE

与数据呈线性与数据呈线性,维数的平方

是是

高较高

本文算法)n)+O((m+ξO((K-1)m)

是较低

(与数据呈线性)

5 结 语

  聚类算法是一种无监督的算法,在先验知识不充分的情况下能发挥巨大的作用.算法的精度对很多应用都是至关重要的,本文提出的子空间聚类算法处理高维数据时在不牺牲算法其他性能的同时提高了聚类的精度,降低了对输入参数的敏感性.但算法在处理任意形状及边界不清晰的数据方面仍需要改进.参考文献:

[1] 沈红斌,杨 杰,王士同.基于信息理论的合作模糊

聚类算法研究[J].计算机学报,2005,28(8):1287

-1294.

SHENHong2bin,YANGJie,WANGShi2tong.Studyonnewinformationtheorybasedcooperativeclusteringalgorithm[J].ChineseJournalofComput2ers,2005,28(8):1287-1294.

范文九:空间聚类分析 投稿:田輛輜

1 空间聚类的内涵理解

1.1 定义

空间聚类作为聚类分析的一个研究方向,是指将空间数据集中的对象分成由相似对象组成的类。同类中的对象间具有较高的相似度,而不同类中的对象间差异较大[3]。作为一种无监督的学习方法,空间聚类不需要任何先验知识。这是聚类的基本思想,因此空间聚类也是要满足这个基本思想。

1.2 对空间数据聚类的要求[2][5][6]

① 可伸缩性;

许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好;但是,一个大规模数据库可能包含几百万个对象,在这样的大数据集合样本上进行聚类可能会导致有偏的结果。我们需要具有高度可伸缩性的聚类算法。

② 发现任意形状的聚类;

许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是,一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。(虽然聚类分析属于非监督学习方法,但在某些情况下一些基本的客观规律也会或多或少指示聚类分析的结果)

③ 用于决定输入参数的领域知识最小化;

许多聚类算法在聚类分析中要求用户输入一定的参数,例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定,特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担,也使得聚类的质量难以控制。

④ 对噪声数据不敏感;

绝大多数现实中的数据库都包含了孤立点,缺失,或者错误的数据。一些聚类算法对于这样的数据敏感,可能导致低质量的聚类结果。

⑤ 对于输入记录的顺序不敏感;

一些聚类算法对于输入数据的顺序是敏感的。例如,同一个数据集合,当以不同的顺序交给同一个算法时,可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。

⑥ 处理高维数据;

一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理低维的数据,可能只涉及两到三维。人类的眼睛在最多三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的,特别是考虑到这样的数据可能分布非常稀疏,而且高度偏斜。

2 空间聚类的主要算法

空间聚类的主要方法有五大类:划分聚类算法、层次聚类算法、基于密度的方法、基于网格的方法和基于模型的聚类方法。[2][3]

图2-1空间聚类算法分类

2.1 划分聚类算法

主要包括:K-means、K-medoids、PAM、CLARA、K-模、K-原型、EM和CLARANS等。基本思想:给定一个包含n个对象或数据的集合,将数据集划分为k个子集,其中每个子集均代表一个聚类(k≤n),划分方法首先创建一个初始划分,然后利用循环再定位技术,即通过移动不同划分中的对象来改变划分内容。

典型的算法说明:K-means算法是首先从n个数据对象随机地选择k个对象,每个对象初始地代表了一个簇中心,对剩余的每个对象,根据其与各个簇中心的距离,将它赋给最近的簇,然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛(说明:一般都采用均方差作为标准测度函数)。特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开,这个特点正是聚类的最根本的实质要求[4]。但是K-means也有其缺点:产生类的大小相差不会很大,对于脏数据很敏感。而在这一点上,K-medoids做出了相应的改进,K-medoids不采用聚类中对象的平均值作为参照点,而选用聚类中位置最中心的对象,即中心点,仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。

2.2 层次聚类算法

层次聚类方法是通过将数据组织为若干组并形成一个相应的树来进行聚类的,层次聚类方法又可分为自顶向下的分裂算法和自底向上的凝聚算法两种。

分裂聚类算法,首先将所有对象置于一个簇中,然后逐渐细分为越来越小的簇,直到每个对象自成一簇,或者达了某个终结条件,这里的终结条件可以是簇的数目,或者是进行合并的阈值。而凝聚聚类算法正好相反,首先将每个对象作为一个簇,然后将相互邻近的合并为一个大簇,直到所有的对象都在一个簇中,或者某个终结条件被满足。

CURE(clustering using representatives)算法采取随机取样和划分相结合的方法:一个随机样本首先被划分,每个划分被局部聚类,最后把每个划分中产生的聚类结果用层次聚类的方法进行聚类。较好的解决了偏好球形和相似大小的问题,在处理孤立点时也更加健壮。

CHAMELEON(hierarchical clustering using dynamic modeling)算法的主要思想是首先使用图划分算法将数据对象聚类为大量相对较小的子类,其次使用凝聚的层次聚类算法反复地合并子类来找到真正的结果类。CHAMELEON 算法是在CURE 等算法的基础上改进而来,能够有效的解决CURE等算法的问题。

2.3 基于密度的方法

绝大多数划分方法基于对象之间的距离进行聚类,这样的方法只能发现球状的类。因此,出现了基于密度的聚类方法,其主要思想是:只要邻近区域的密度(对象或数据点的数目) 超过某个阈值,就继续聚类,这样的方法可以过滤“噪声”数据,发现任意形状的类。从而克服基于距离的方法只能发现类圆形聚类的缺点。代表性算法有:DBSCAN 算法、OPTICS 算法、DENCLUE算法等。

DBSCAN(density based spatial clustering of applications with noise)算法可以有效地发现具有任意形状的类,并正确地处理噪声数据。除此之外,该算法还具有实现简单、聚类效果较好等优点。该算法对于一个类中的每个对象,在其给定半径的领域中包含的对象不能少于某一给定的最小数目,即DBSCAN算法将聚类定义为基于密度可达性最大的密度相连对象的集合。另外不进行任何的预处理而直接对整个数据集进行聚类操作。

OPTICS 算法是一种基于类排序方法。该算法并不明确产生一个聚类,而是为自动交互的聚类分析计算出一个增强聚类顺序。这个顺序代表了数据的基于密度的聚类结构。

DENCLUE 算法是一个基于一组密度分布函数的聚类算法。该算法主要基于下面的想法: (1) 每个数据点的影响可以用一个数学函数来形式化地模拟,它描述了一个数据点在领域内的影响,被称为影响函数; (2) 数据空间的整体密度可以被模型化为所有数据点的影响函数的总和; (3) 聚类可以通过确定密度吸引点来得到,这里的密度吸引点是全局密度函数的局部最大。

2.4 基于网格法

主要思想是将空间区域划分若干个具有层次结构的矩形单元,不同层次的单元对应于不同的分辨率网格,把数据集中的所有数据都映射到不同的单元网格中,算法所有的处理都是以单个单元网格为对象,其处理速度要远比以元组为处理对象的效率要高的多。代表性算法有:STING算法、CLIQUE 算法、WAVE-CLUSTER 算法等。

STING(statistical information grid) 算法首先将空间区域划分为若干矩形单

元,这些单元形成一个层次结构,每个高层单元被划分为多个低一层的单元。单元中预先计算并存储属性的统计信息,高层单元的统计信息可以通过底层单元计算获得。这种算法的优点是效率很高,而且层次结构有利于并行处理和增量更新;其缺点是聚类的边界全部是垂直或是水平的,与实际情况可能有比较大的差别,影响聚类的质量。

CLIQUE(clustering in quest)算法综合了基于密度和基于网格的聚类方法。其主要思想是将多维数据空间划分为多个矩形单元,通过计算每一个单元中数据点中全部数据点的比例的方法确定聚类。其优点是能够有效处理高维度的数据集,缺点是聚类的精度有可能会降低。

WaveCluster(clustering using wavelet transformation)算法是一种采用小波变换的聚类方法。其首先使用多维数据网格结构汇总区域空间数据,用多维向量空间表示多维空间中的数据对象,然后使用小波变换方法对特征空间进行处理,发现特征空间中的稠密区域。最终通过多次小波变换,获得多分辨率的聚类。

2.5 基于模型法

给每一个聚类假定一个模型,然后去寻找能够很好地满足这个模型的数据集。常用的模型主要有两种:一种是统计学的方法,代表性算法是COBWEB算法;另一种是神经网络的方法,代表性的算法是竞争学习算法。COBWEB 算法是一种增量概念聚类算法。这种算法不同于传统的聚类方法,它的聚类过程分为两步:首先进行聚类,然后给出特征描述。因此,分类质量不再是单个对象的函数,而且也加入了对聚类结果的特征性描述。竞争学习算法属于神经网络聚类。它采用若干个单元的层次结构,以一种“胜者全取”的方式对系统当前所处理的对象进行竞争。

3 空间聚类分析的实现

空间聚类分析可以分为基于点和基于面两种方法。基于点的方法需要时间准确的地理位置,基于面的的方法是运用其区域内的平均值[1]。到底用哪种方法,关键取决于数据,“基于点的方法并不总是优于基于面的方法。”(Oden etal.,

1996)

当前ArcGIS软件中的空间统计分析功能还很有限,只能实现基于面的空间的空间聚类分析,其他软件如CrimeStat(Levine,2002)也有类似的功能。在这里将讲解SaTScan实现基于点的空间聚类分析和ArcGIS实现基于面的空间聚类分析,而本文的应用实例将采用SaTScan分析中国南部地区台语地名的聚集性。

图3-1 空间聚类分析分类

3.1 SaTScan中空间聚类的实现

3.1.1 基于点的全局聚类检验

全局聚类检验用于分析研究对象在整个区域内是否具有空间集聚性。将所有观察个体去分为事件和非事件两类。以Whittemore et al.提出的全局聚类检验指标为例,先计算事件之间的平均距离,再计算所有个体之间的平均距离。如果前置比后者低,则表明时间在空间上存在集聚。当研究区的中心地区具有丰富的调查样本资料时,这个方法比较有效,但如果病例分散在外围地区,则此方法效果不佳[1]。

3.1.2 基于点的局部聚类检验

对于大多数研究而言,确定空间集聚的具体位置或局部集聚也是十分重要的。研究区即使在全局聚类检验中没有统计想助兴,也有可能存在着局部集聚的现象。

这里主要说明SaTScan软件使用的空间扫描统计法使用圆作为扫描窗口,搜索这个研究区,扫描窗口半径大小的选取,以圆内样本数占总样本数的比例来确定,从0%到50%逐步上升。针对每个圈,比较窗口内和窗口外的出现的几率,存照窗口内统计上明显高的圈定义为空间集聚。空间扫描统计法使用泊松分布或伯努利分布来判断统计显著性。如果是二项分布数据(即事件与非事件数据)选用伯努利模型,它要求所有样本的地理坐标,事件记为1,非事件记为0。

例如,在伯努利模型中窗口z的似然函数计算如下:

其中,N为研究区中的样本总数,n为窗口中的事件数, M为研究区中的非事件数,m为窗口中的非事件数,p=n/m为事件在窗口中的概率,q=(N-n)(M-m)为事件在窗口外的概率。

对每个窗口,求似然函数的最大值,最可能的集聚圈就是窗口内最不可能为随机分布的圈。这种方法找到了最可能的集聚圈后,还可能找到与之不重叠的次一级集聚圈。

3.2 ArcGIS中空间聚类的实现

3.2.1 空间权重的定义

首先说明定义空间权重的不同方法,这对基于面的空间聚集分析确定各个观察对象之间的空间关系十分重要。

基于距离来定义空间权重,方法有:

1)以距离倒数为权重(1/d)。

2)以距离平方的倒数为权重(1/d2)。

3) 以距离阈值定义权重(如在阈值方位内定义为1,在阈值范围外定义为0)。

4)定义权重为距离的一个连续函数:

ωij=exp(-dij2/h2)

其中,dij是地区i和地区j之间的距离,h是距离阈值范围(Fotheringham et al.,2000:111),阈值范围的选取决定于距离影响程度,一个高度h值表示地区之间

的相互影响距离远,影响范围大。

上述基于距离的空间权重,在ArcGIS软件中都有相应的定义工具,具体是在“Cpnceptualization of Spatial Relationships”(定义空间关系)的时候选定的[7]。ArcGIS中可选的前三项为“Inverse Distance”、“Inverse Distance Squared”、“Fixed Distance Band”分别对应着上述的“距离倒数”、“距离平方倒数”和“距离阈值”这三种空间权重定义方法。第四项为“Zone of Indifference”,指给定一个距离阈值,在阈值范围内由距离倒数定义空间权重,在范围之外定义为0。

3.2.2 基于面的全局聚类检验

Moran`s I指数是最早应用于全局聚类检验的方法。它检验整个研究区中临近地区间是相似、相异(空间正相关、负相关),还是相互独立的。Moran`s I指数计算公式:

这里,N是研究区内地区总数,ωij是空间权重, xi 和 xj分别是区域i和j的属性,是属性的平均值。

Moran`s I指数数值处于-1到1之间,值接近1是表明具有相似的属性集聚在一起;值接近-1时表明具有相异的属性集聚在一起。如果Moran`s I指数接近

于0则表示属性是随机分布的,或者不存在空间自相关性。

与Moran`s I指数相似,吉瑞C指数(Geary`s C)也是全局聚类检验的一个指数,其公式为:

吉瑞C指数值通常在0到2之间。虽然2不是一个严格的上界。其值为1时,表示属性的观察值在空间上是相互独立的,值在0到1之间表示空间正相关,值在1到2之间时表示空间负相关。因此,吉瑞C指数与Moran`s I指数刚好相反。

在ArcGIS的空间统计工具包中,提供了Moran`s I指数和吉瑞C指数的计算功能:ArcToolbox>Spatial Statistics Tools>Analyzing Patterns>选Spatial Autocorrelation(Moran`s I)计算Moran`s I,选High-Low Clustering(Getis-Ord General G)计算吉瑞C。

3.2.3 基于面的局部聚类检验

Anselin提出了一个局部莫兰指数(Local Moran Index)用来检验局部地区是否存在相似或者相异的观察值聚集在一起。区域i的局部莫兰指数用来度量区域i和它领域之间的关联程度,定义为:

正的Ii表示一个高值被高值所包围(高-高)或者是一个低值被低值所包围(低-低);负的Ii表示一个低值被高值所包围或与之相反的情况。

类似地,Gi指数(Getis and Ord,1992)用来检验局部地区是否存在显著地高值或低值。Gi定义如下:

公式中的符号与Moran`s I指数相同,式中对j的累加不包括区域i本身,即

j不等于i;高的Gi代表高值的样本集中在一起,而低的Gi值表示低值的样本集中在一起。

在ArcGIS的空间统计工具包中,计算局部莫兰指数和Gi指数:ArcToolbox>Spatial Statistics Tools>Mapping Clusters>选Cluster and Outlier Analysis(Anselin Local Moran Index)计算局部莫兰指数,选Hot Spot Analysis(Getis-Ord Gi*)计算Gi指数。计算结果分别用“Cluster and Outlier Analysis with Rendering ”和“Hot Spot Analysis with Rendering”的工具来绘图显示。

4 应用实例

本案例是对于中国南部地区台语地名的空间分布进行区别是随机分布还是存在集聚性,实现过程是利用SaTScan软件(版本9.1)来完成[1]。

1、用ArcGIS准备SaTScan软件的数据

在SaTScan软件平台下,用伯努利模型执行基于点的空间聚类分析需要定义三个数据文件,即事件文件(包含区位ID和每个区位的事件数),非事件文件(包含区位ID和每个区位的非事件数)以及坐标文件(包含区位ID和对应的笛卡尔坐标或经纬度坐标)。这一步就是在ArcGIS中定义好相关属性,如必须给图层文件加入变量的坐标(Add XY Coordinates),并将属性表输出为dBase文件格式。如下图。

图4-1 图层文件属性表

图中的TAI是事件属性,POINT_X、POINT_Y是加入的坐标属性,NONTAI是根据TAI计算出的非事件属性,这些属性是不可缺少的。

2、用SaTScan软件执行空间聚类分析

运行SaTScan软件,选择Creat New Session,系统弹出一个新的对话框,如图。

图4-2 SaTScan软件创建新任务

图4-3 空间聚类分析文件设置对话框

在第一个标签Input下使用Import Wiard来定义事件文件(Case File):选择上面输出的dBase文件作为输入文件,弹出对话框,如图所示。

图4-4 Import Wiard对话框设置Case File

按照上述的步骤定义好Case File、Control File以及Coordinates File。

在第二个标签Analysis下进行选择操作,按照下图所示设置。

图4-5 Analysis设置

在第三个标签Output下,输入cluster作为结果输出文件,在dBase下点击所有的选项按钮。 最后运行。

3、分析结果的制图

在ArcGIS下,基于关联码Location ID和cluster.gis.dbf中的LOC_ID将dBase文件cluster.gis.dbf连到图层文件上。结果如下图。

图4-6 分析结果

5 参考文献

[1] 王法辉著.基于GIS的数量方法与应用[M].姜世国,滕骏华译.北京:商

务印书馆,2009.

[2] 马程.空间聚类研究[J]. 计算机技术与发展.2009,19(4).

[3] 席景科,谭海樵.空间聚类分析及评价方法[J].计算机工程与设计.2009,30

(7).

[4] 戴晓燕,过仲阳,李勤奋,吴健平.空间聚类的研究现状及其应用[J]. 上

海地质.2003,4.

[5] 聚类算法_百度百科. http://baike.baidu.com/view/69222.htm

[6] 柳彦平,王文杰,谈恒贵.数据挖掘空间聚类. 计算机工程与应用.2005,35

[7] Desktop Help 10.http://help.arcgis.com/zh-cn/arcgisdesktop/10.0/help/inde

x.html#/na/005p00000012000000/

范文十:空间聚类分析 投稿:侯眅眆

1 空间聚类的内涵理解

1.1 定义

空间聚类作为聚类分析的一个研究方向,是指将空间数据集中的对象分成由相似对象组成的类。同类中的对象间具有较高的相似度,而不同类中的对象间差异较大[3]。作为一种无监督的学习方法,空间聚类不需要任何先验知识。这是聚类的基本思想,因此空间聚类也是要满足这个基本思想。

1.2 对空间数据聚类的要求[2][5][6]

① 可伸缩性;

许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好;但是,一个大规模数据库可能包含几百万个对象,在这样的大数据集合样本上进行聚类可能会导致有偏的结果。我们需要具有高度可伸缩性的聚类算法。

② 发现任意形状的聚类;

许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是,一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。(虽然聚类分析属于非监督学习方法,但在某些情况下一些基本的客观规律也会或多或少指示聚类分析的结果)

③ 用于决定输入参数的领域知识最小化;

许多聚类算法在聚类分析中要求用户输入一定的参数,例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定,特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担,也使得聚类的质量难以控制。

④ 对噪声数据不敏感;

绝大多数现实中的数据库都包含了孤立点,缺失,或者错误的数据。一些聚类算法对于这样的数据敏感,可能导致低质量的聚类结果。

⑤ 对于输入记录的顺序不敏感;

一些聚类算法对于输入数据的顺序是敏感的。例如,同一个数据集合,当以不同的顺序交给同一个算法时,可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。

⑥ 处理高维数据;

一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理低维的数据,可能只涉及两到三维。人类的眼睛在最多三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的,特别是考虑到这样的数据可能分布非常稀疏,而且高度偏斜。

2 空间聚类的主要算法

空间聚类的主要方法有五大类:划分聚类算法、层次聚类算法、基于密度的方法、基于网格的方法和基于模型的聚类方法。[2][3]

图2-1空间聚类算法分类

2.1 划分聚类算法

主要包括:K-means、K-medoids、PAM、CLARA、K-模、K-原型、EM和CLARANS等。基本思想:给定一个包含n个对象或数据的集合,将数据集划分为k个子集,其中每个子集均代表一个聚类(k≤n),划分方法首先创建一个初始划分,然后利用循环再定位技术,即通过移动不同划分中的对象来改变划分内容。

典型的算法说明:K-means算法是首先从n个数据对象随机地选择k个对象,每个对象初始地代表了一个簇中心,对剩余的每个对象,根据其与各个簇中心的距离,将它赋给最近的簇,然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛(说明:一般都采用均方差作为标准测度函数)。特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开,这个特点正是聚类的最根本的实质要求[4]。但是K-means也有其缺点:产生类的大小相差不会很大,对于脏数据很敏感。而在这一点上,K-medoids做出了相应的改进,K-medoids不采用聚类中对象的平均值作为参照点,而选用聚类中位置最中心的对象,即中心点,仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。

2.2 层次聚类算法

层次聚类方法是通过将数据组织为若干组并形成一个相应的树来进行聚类的,层次聚类方法又可分为自顶向下的分裂算法和自底向上的凝聚算法两种。

分裂聚类算法,首先将所有对象置于一个簇中,然后逐渐细分为越来越小的簇,直到每个对象自成一簇,或者达了某个终结条件,这里的终结条件可以是簇的数目,或者是进行合并的阈值。而凝聚聚类算法正好相反,首先将每个对象作为一个簇,然后将相互邻近的合并为一个大簇,直到所有的对象都在一个簇中,或者某个终结条件被满足。

CURE(clustering using representatives)算法采取随机取样和划分相结合的方法:一个随机样本首先被划分,每个划分被局部聚类,最后把每个划分中产生的聚类结果用层次聚类的方法进行聚类。较好的解决了偏好球形和相似大小的问题,在处理孤立点时也更加健壮。

CHAMELEON(hierarchical clustering using dynamic modeling)算法的主要思想是首先使用图划分算法将数据对象聚类为大量相对较小的子类,其次使用凝聚的层次聚类算法反复地合并子类来找到真正的结果类。CHAMELEON 算法是在CURE 等算法的基础上改进而来,能够有效的解决CURE等算法的问题。

2.3 基于密度的方法

绝大多数划分方法基于对象之间的距离进行聚类,这样的方法只能发现球状的类。因此,出现了基于密度的聚类方法,其主要思想是:只要邻近区域的密度(对象或数据点的数目) 超过某个阈值,就继续聚类,这样的方法可以过滤“噪声”数据,发现任意形状的类。从而克服基于距离的方法只能发现类圆形聚类的缺点。代表性算法有:DBSCAN 算法、OPTICS 算法、DENCLUE算法等。

DBSCAN(density based spatial clustering of applications with noise)算法可以有效地发现具有任意形状的类,并正确地处理噪声数据。除此之外,该算法还具有实现简单、聚类效果较好等优点。该算法对于一个类中的每个对象,在其给定半径的领域中包含的对象不能少于某一给定的最小数目,即DBSCAN算法将聚类定义为基于密度可达性最大的密度相连对象的集合。另外不进行任何的预处理而直接对整个数据集进行聚类操作。

OPTICS 算法是一种基于类排序方法。该算法并不明确产生一个聚类,而是为自动交互的聚类分析计算出一个增强聚类顺序。这个顺序代表了数据的基于密度的聚类结构。

DENCLUE 算法是一个基于一组密度分布函数的聚类算法。该算法主要基于下面的想法: (1) 每个数据点的影响可以用一个数学函数来形式化地模拟,它描述了一个数据点在领域内的影响,被称为影响函数; (2) 数据空间的整体密度可以被模型化为所有数据点的影响函数的总和; (3) 聚类可以通过确定密度吸引点来得到,这里的密度吸引点是全局密度函数的局部最大。

2.4 基于网格法

主要思想是将空间区域划分若干个具有层次结构的矩形单元,不同层次的单元对应于不同的分辨率网格,把数据集中的所有数据都映射到不同的单元网格中,算法所有的处理都是以单个单元网格为对象,其处理速度要远比以元组为处理对象的效率要高的多。代表性算法有:STING算法、CLIQUE 算法、WAVE-CLUSTER 算法等。

STING(statistical information grid) 算法首先将空间区域划分为若干矩形单

元,这些单元形成一个层次结构,每个高层单元被划分为多个低一层的单元。单元中预先计算并存储属性的统计信息,高层单元的统计信息可以通过底层单元计算获得。这种算法的优点是效率很高,而且层次结构有利于并行处理和增量更新;其缺点是聚类的边界全部是垂直或是水平的,与实际情况可能有比较大的差别,影响聚类的质量。

CLIQUE(clustering in quest)算法综合了基于密度和基于网格的聚类方法。其主要思想是将多维数据空间划分为多个矩形单元,通过计算每一个单元中数据点中全部数据点的比例的方法确定聚类。其优点是能够有效处理高维度的数据集,缺点是聚类的精度有可能会降低。

WaveCluster(clustering using wavelet transformation)算法是一种采用小波变换的聚类方法。其首先使用多维数据网格结构汇总区域空间数据,用多维向量空间表示多维空间中的数据对象,然后使用小波变换方法对特征空间进行处理,发现特征空间中的稠密区域。最终通过多次小波变换,获得多分辨率的聚类。

2.5 基于模型法

给每一个聚类假定一个模型,然后去寻找能够很好地满足这个模型的数据集。常用的模型主要有两种:一种是统计学的方法,代表性算法是COBWEB算法;另一种是神经网络的方法,代表性的算法是竞争学习算法。COBWEB 算法是一种增量概念聚类算法。这种算法不同于传统的聚类方法,它的聚类过程分为两步:首先进行聚类,然后给出特征描述。因此,分类质量不再是单个对象的函数,而且也加入了对聚类结果的特征性描述。竞争学习算法属于神经网络聚类。它采用若干个单元的层次结构,以一种“胜者全取”的方式对系统当前所处理的对象进行竞争。

3 空间聚类分析的实现

空间聚类分析可以分为基于点和基于面两种方法。基于点的方法需要时间准确的地理位置,基于面的的方法是运用其区域内的平均值[1]。到底用哪种方法,关键取决于数据,“基于点的方法并不总是优于基于面的方法。”(Oden etal.,1996)

当前ArcGIS软件中的空间统计分析功能还很有限,只能实现基于面的空间的空间聚类分析,其他软件如CrimeStat(Levine,2002)也有类似的功能。在这里将讲解SaTScan实现基于点的空间聚类分析和ArcGIS实现基于面的空间聚类分析,而本文的应用实例将采用SaTScan分析中国南部地区台语地名的聚集性。

图3-1 空间聚类分析分类

3.1 SaTScan中空间聚类的实现

3.1.1 基于点的全局聚类检验

全局聚类检验用于分析研究对象在整个区域内是否具有空间集聚性。将所有观察个体去分为事件和非事件两类。以Whittemore et al.提出的全局聚类检验指标为例,先计算事件之间的平均距离,再计算所有个体之间的平均距离。如果前置比后者低,则表明时间在空间上存在集聚。当研究区的中心地区具有丰富的调查样本资料时,这个方法比较有效,但如果病例分散在外围地区,则此方法效果不佳[1]。

3.1.2 基于点的局部聚类检验

对于大多数研究而言,确定空间集聚的具体位置或局部集聚也是十分重要的。研究区即使在全局聚类检验中没有统计想助兴,也有可能存在着局部集聚的现象。

这里主要说明SaTScan软件使用的空间扫描统计法使用圆作为扫描窗口,搜索这个研究区,扫描窗口半径大小的选取,以圆内样本数占总样本数的比例来确

定,从0%到50%逐步上升。针对每个圈,比较窗口内和窗口外的出现的几率,存照窗口内统计上明显高的圈定义为空间集聚。空间扫描统计法使用泊松分布或伯努利分布来判断统计显著性。如果是二项分布数据(即事件与非事件数据)选用伯努利模型,它要求所有样本的地理坐标,事件记为1,非事件记为0。

例如,在伯努利模型中窗口z的似然函数计算如下:

其中,N为研究区中的样本总数,n为窗口中的事件数, M为研究区中的非事件数,m为窗口中的非事件数,p=n/m为事件在窗口中的概率,q=(N-n)(M-m)为事件在窗口外的概率。

对每个窗口,求似然函数的最大值,最可能的集聚圈就是窗口内最不可能为随机分布的圈。这种方法找到了最可能的集聚圈后,还可能找到与之不重叠的次一级集聚圈。

3.2 ArcGIS中空间聚类的实现

3.2.1 空间权重的定义

首先说明定义空间权重的不同方法,这对基于面的空间聚集分析确定各个观察对象之间的空间关系十分重要。

基于距离来定义空间权重,方法有:

1)以距离倒数为权重(1/d)。

2)以距离平方的倒数为权重(1/d2)。

3) 以距离阈值定义权重(如在阈值方位内定义为1,在阈值范围外定义为0)。

4)定义权重为距离的一个连续函数:

ωij=exp(-dij2/h2)

其中,dij是地区i和地区j之间的距离,h是距离阈值范围(Fotheringham et al.,2000:111),阈值范围的选取决定于距离影响程度,一个高度h值表示地区之间的相互影响距离远,影响范围大。

上述基于距离的空间权重,在ArcGIS

软件中都有相应的定义工具,具体是

在“Cpnceptualization of Spatial Relationships”(定义空间关系)的时候选定的[7]。ArcGIS中可选的前三项为“Inverse Distance”、“Inverse Distance Squared”、“Fixed Distance Band”分别对应着上述的“距离倒数”、“距离平方倒数”和“距离阈值”这三种空间权重定义方法。第四项为“Zone of Indifference”,指给定一个距离阈值,在阈值范围内由距离倒数定义空间权重,在范围之外定义为0。

3.2.2 基于面的全局聚类检验

Moran`s I指数是最早应用于全局聚类检验的方法。它检验整个研究区中临近地区间是相似、相异(空间正相关、负相关),还是相互独立的。Moran`s I指数计算公式:

这里,N是研究区内地区总数,ωij是空间权重, xi 和 xj分别是区域i和j的属性,是属性的平均值。

Moran`s I指数数值处于-1到1之间,值接近1是表明具有相似的属性集聚在一起;值接近-1时表明具有相异的属性集聚在一起。如果Moran`s I指数接近于0则表示属性是随机分布的,或者不存在空间自相关性。

与Moran`s I指数相似,吉瑞C指数(Geary`s C

)也是全局聚类检验的一个

指数,其公式为:

吉瑞C指数值通常在0到2之间。虽然2不是一个严格的上界。其值为1时,表示属性的观察值在空间上是相互独立的,值在0到1之间表示空间正相关,值在1到2之间时表示空间负相关。因此,吉瑞C指数与Moran`s I指数刚好相反。

在ArcGIS的空间统计工具包中,提供了Moran`s I指数和吉瑞C指数的计算功能:ArcToolbox>Spatial Statistics Tools>Analyzing Patterns>选Spatial Autocorrelation(Moran`s I)计算Moran`s I,选High-Low Clustering(Getis-Ord General G)计算吉瑞C。

3.2.3 基于面的局部聚类检验

Anselin提出了一个局部莫兰指数(Local Moran Index)用来检验局部地区是否存在相似或者相异的观察值聚集在一起。区域i的局部莫兰指数用来度量区域i和它领域之间的关联程度,定义为:

正的Ii表示一个高值被高值所包围(高-高)或者是一个低值被低值所包围(低-低);负的Ii表示一个低值被高值所包围或与之相反的情况。

类似地,Gi指数(Getis and Ord,1992)用来检验局部地区是否存在显著地高值或低值。Gi定义如下:

公式中的符号与Moran`s I指数相同,式中对j的累加不包括区域i本身,即j不等于i;高的Gi代表高值的样本集中在一起,而低的Gi值表示低值的样本集中在一起。

在ArcGIS的空间统计工具包中,计算局部莫兰指数和Gi指数:ArcToolbox>Spatial Statistics Tools>Mapping Clusters>选Cluster and Outlier Analysis(Anselin Local Moran Index)计算局部莫兰指数,选Hot Spot Analysis(Getis-Ord Gi*)计算Gi指数。计算结果分别用“Cluster and Outlier Analysis with Rendering ”和“Hot Spot Analysis with Rendering”的工具来绘图显示。

4 应用实例

本案例是对于中国南部地区台语地名的空间分布进行区别是随机分布还是存在集聚性,实现过程是利用SaTScan软件(版本9.1)来完成[1]。

1、用ArcGIS准备SaTScan软件的数据

在SaTScan软件平台下,用伯努利模型执行基于点的空间聚类分析需要定义三个数据文件,即事件文件(包含区位ID和每个区位的事件数),非事件文件(包含区位ID和每个区位的非事件数)以及坐标文件(包含区位ID和对应的笛卡尔坐标或经纬度坐标)。这一步就是在ArcGIS中定义好相关属性,如必须给图层文件加入变量的坐标(Add XY Coordinates),并将属性表输出为dBase文件格式。如下图。

图4-1 图层文件属性表

图中的TAI是事件属性,POINT_X、POINT_Y是加入的坐标属性,NONTAI是根据TAI计算出的非事件属性,这些属性是不可缺少的。

2、用SaTScan软件执行空间聚类分析

运行SaTScan软件,选择Creat New Session,系统弹出一个新的对话框,如图。

图4-2 SaTScan软件创建新任务

图4-3 空间聚类分析文件设置对话框

在第一个标签Input下使用Import Wiard来定义事件文件(Case File):选择上面输出的dBase文件作为输入文件,弹出对话框,如图所示。

图4-4 Import Wiard对话框设置Case File

按照上述的步骤定义好Case File、Control File以及Coordinates File。

在第二个标签Analysis下进行选择操作,按照下图所示设置。

图4-5 Analysis设置

在第三个标签Output下,输入cluster作为结果输出文件,在dBase下点击所有的选项按钮。

最后运行。

3、分析结果的制图

在ArcGIS下,基于关联码Location ID和cluster.gis.dbf中的LOC_ID将dBase文件cluster.gis.dbf连到图层文件上。结果如下图。

图4-6 分析结果

5 参考文献

[1] 王法辉著.基于GIS的数量方法与应用[M].姜世国,滕骏华译.北京:商

务印书馆,2009.

[2] 马程.空间聚类研究[J]. 计算机技术与发展.2009,19(4).

[3] 席景科,谭海樵.空间聚类分析及评价方法[J].计算机工程与设计.2009,30

(7).

[4] 戴晓燕,过仲阳,李勤奋,吴健平.空间聚类的研究现状及其应用[J]. 上

海地质.2003,4.

[5] 聚类算法_百度百科. http://baike.baidu.com/view/69222.htm

[6] 柳彦平,王文杰,谈恒贵.数据挖掘空间聚类. 计算机工程与应用.2005,35

[7] Desktop Help 10.http://help.arcgis.com/zh-cn/arcgisdesktop/10.0/help/inde

x.html#/na/005p00000012000000/

字典词典党费收缴自查报告党费收缴自查报告【范文精选】党费收缴自查报告【专家解析】逻辑思考题逻辑思考题【范文精选】逻辑思考题【专家解析】钣金展开放样软件钣金展开放样软件【范文精选】钣金展开放样软件【专家解析】