第2期 汪中，等：基于模糊K-hamonic means的谱聚类算法 97· (3)分别计算隶属度和聚类中心，然后进行迭代，直 到最大的迭代次数或者目标函数式(1)稳定为止. 3 该算法的时间复杂度为O(mXnX),其中m为数 据属性的个数. 22基于模糊K-hamonic means的谱聚类算法 (FKHM-SC) 由于传统谱聚类算法对初始值敏感，本文在 NW算法的框架下提出基于模糊K-hamonic means 的谱聚类算法，具体实现步骤如下： -3-2-101234 输入：n个数据点S={,s,聚类数目k 输出：数据点集的划分 (a)three circles-joined聚类结果(o-Q05) 步骤： 100 1)构造相似矩阵A∈R",其中A= 80 ep(-‖s-S2/2o2),i≠广Aa=0其中0是参 4r从年 数 60 868 2构造矩阵L=D1PAD12.其中D是对角矩 40 m米wx物 阵对角元素为D,=1, 20 3)采用Nystrom逼近方法I计算L的前k个特 20 40 60 80100 征值所对应的特征向量x,,,x。重复特征值取 其相互正交的特征向量)构造矩阵 (b)1 ine and balls聚类结果(o=1) X=[x为…X)∈t,规范化矩阵X的行向量， 100 得到矩阵Y=Xg/(∑X)n: 4)将矩阵Y的每行当作空间中一点，采用上 80 述对初值不敏感的FKM算法聚为k类，如果k的 60 第行数据为第类，则原数据s划分到第类 40 由于谱聚类初始化敏感的特点，考虑到传统的 Kmeans和FCM算法依赖于初始k个对象的选择； 20 而FKHM算法通过对数据点到聚类中心的调和平 均进行加权，动态加权对初值不敏感起到重要的作 20 40 60 80100 用，故改进算法在理论上能得到更稳定的聚类性能： (c)squiggles聚类结果(o=1) 利用Nystrom逼近方法求解矩阵的特征值和特征向 100 量减少了计算的复杂度 ++++ 3实验 80 60 3.1人工数据 文献[7给出一些有挑战性的人工数据聚类问题 0 图1分别给出了FKIM-SC在4组人工数据集上的聚 20 类结果图，FKM-SC可以成功地识别这4组有聚类数 据问题，同时给出了相应的核参数σ的值. 102030 4050607080 FKM-SC可以成功地识别上面4组数据，利用 多个特征向量构造了一个简化的数据空间，在该空 (d)blobs and circles聚类结果(o=2) 间中的数据的分布结构更加明显，通过每组数据的 图1FKHM-SC在4组人工数据集上的聚类结果图 特征向量图可以直观地观察数据的分布」 Fig 1 Cluster results of FKHM-SC on four artificial data sets 1994-2009 China Academie Journal Electronic Publishing House.All rights reserved.http://www.cnki.net(3)分别计算隶属度和聚类中心 ,然后进行迭代 ,直 到最大的迭代次数或者目标函数式 ( 1)稳定为止. 该算法的时间复杂度为 O (m ×n ×k) ,其中 m 为数 据属性的个数. 2. 2 基于模糊 K2harmonic means的谱聚类算法 (FKHM2SC) 由于传统谱聚类算法对初始值敏感 ,本文在 NJW 算法的框架下提出基于模糊 K2harmonic means 的谱聚类算法 ,具体实现步骤如下 : 输入 : n个数据点 S = { s1 , …, sn },聚类数目 k 输出 :数据点集的划分 步骤 : 1) 构 造 相 似 矩 阵 A ∈ R n ×n , 其 中 Aij = exp ( - ‖si - sj‖ 2 /2σ2 ) , i ≠ j, Aii = 0. 其中 σ是参 数; 2)构造矩阵 L =D - 1 /2 AD - 1 /2 . 其中 D 是对角矩 阵 ,对角元素为 Dii = ∑ n j=1 Aij ; 3)采用 Nystrom逼近方法 [ 4 ]计算 L 的前 k个特 征值所对应的特征向量 x1 , x2 , …, xn (重复特征值取 其 相 互 正 交 的 特 征 向 量 ) 构 造 矩 阵 X = [ x1 x2 … xn ] ∈R n×k ,规范化矩阵 X的行向量 , 得到矩阵 Y =Xij / ( ∑j X 2 ij ) 1 /2 ; 4)将矩阵 Y的每行当作 R k空间中一点 ,采用上 述对初值不敏感的 FKHM算法聚为 k类 ,如果 k的 第 i行数据为第 j类 ,则原数据 si 划分到第 j类. 由于谱聚类初始化敏感的特点 ,考虑到传统的 K2means和 FCM算法依赖于初始 k个对象的选择 ; 而 FKHM算法通过对数据点到聚类中心的调和平 均进行加权 ,动态加权对初值不敏感起到重要的作 用 ,故改进算法在理论上能得到更稳定的聚类性能. 利用 Nystrom逼近方法求解矩阵的特征值和特征向 量减少了计算的复杂度. 3 实 验 3. 1 人工数据 文献 [7 ]给出一些有挑战性的人工数据聚类问题. 图 1分别给出了 FKHM2SC在 4组人工数据集上的聚 类结果图 , FKHM2SC可以成功地识别这 4组有聚类数 据问题 ,同时给出了相应的核参数σ的值. FKHM2SC可以成功地识别上面 4组数据 ,利用 多个特征向量构造了一个简化的数据空间 ,在该空 间中的数据的分布结构更加明显 ,通过每组数据的 特征向量图可以直观地观察数据的分布. ( a) three circles2joined聚类结果 (σ = 0. 05 ) ( b) line and balls聚类结果 (σ = 1) ( c) squiggles聚类结果 (σ = 1) ( d) blobs and circles聚类结果 (σ = 2) 图 1 FKHM2SC在 4组人工数据集上的聚类结果图 Fig. 1 Cluster results of FKHM2SC on four artificial data sets 第 2期 汪 中 ,等 :基于模糊 K2harmonic means的谱聚类算法 ·97·