·96 智能系统学报 第4卷 谱聚类初始化敏感的实质原因，通过引入模糊K~ 知识易知，矩阵A1经过若干次初等行或者列变换 Hamonic means(FKM)算法来解决对初值敏感的 则可以得到矩阵A2,故矩阵A,和A2相似.同理，当 问题，从而得到更稳定的聚类性能.在人工数据和真 以任意顺序输入得到的相似矩阵A,均与A,相似. 实数据上进行实验模拟，结果表明，FKHM-SC算法 由于矩阵D,为对角矩阵，其主对角元素为相似矩 相对于原有谱聚类算法(SC)和传统的Kmeans 阵A的相应各行元素之和，故矩阵D,和D2相似 (KM)算法和fuzzy Cmeans(FQM)算法在聚类性能 因为L1=Di12A,D12,L2=D21PA2D;1n,且 和稳定性上有了显著的提高 D,、D,为对角矩阵，由上面的相似关系可知矩阵L1 1谱聚类算法的初始化敏感分析 和L,相似，其对应的特征向量x经过若干次初等 变换可以得到特征向量，则生成矩阵Y和Y2亦 谱聚类算法将数据聚类看成是一个无向图的多 相似.故结论成立 路划分问题，由于图划分问题的组合本质，求图划分 判据的最优解是一个NP难题[6).一个有效的求解 2 改进的谱聚类算法 方法是考虑问题的连续放松形式，将原有问题转换 通过定理1可知，不同输入顺序得到的相似矩 为求解矩阵的特征值和特征向量问题，利用这些特 阵A和最终的生成矩阵Y是相似的，故谱聚类算法 征向量构造一个简化了的数据空间，在该空间中的 对初始值敏感的实质在于NW算法从特征向量获 数据的分布结构更加明显，代表性算法有Ng等人 得最终的聚类方法是否对初始化敏感.传统的K- 提出的NW算法I四 means和FOM算法对初始中心敏感I1,对于不同的 NW算法本质上是利用相似矩阵的特征向量 初始值，可能得到不同的聚类结果.在此基础上，通 进行聚类，选取构造矩阵的前K个最大特征值所对 过引入对初值不敏感的模糊K-hamonic means算法 应的特征向量，从而在K维空间中构成与原数据一 来克服这一缺点 一对应的表述，进而在K维空间中利用Kmeansi或 21模糊K-hamonic means算法 其他简单算法进行聚类， 模糊K-hamonic means(FKHM)算法I1是一种 现有的各种谱聚类算法的差异之处在于：1)构 基于中心的聚类算法，将模糊概念应用到M算 造的相似矩阵不同；2)使用的特征向量不同；3)从 法中，应用数据点对不同聚类的隶属度对目标函 特征向量获得最终的聚类方法不同；4)从连续变量 数中的距离测度进行模糊加权.设X=x,|i=1, 放松到离散变量的方法不同.NW算法是基于上述 :n}为n个数据点的集合，C=C|广=1，…k好 的第3种多类实现方法给出的一种简单有效方法， 为k个聚类中心的集合，d,=‖X,-C‖表示为数 由于传统的Kmeans?算法对初始值敏感，故NW算 据对象到聚类中心的距离表示，采用欧式距离表示 法对初值敏感是否归结于最终的聚类方法.下面给 其目标函数为 出谱聚类算法对初值敏感的证明 定理1设数据集S={,},以2种不 (1 同顺序输入得到的相似矩阵为A、A2,对角矩阵为 六wd, D1、D2,构造矩阵为L1、L2,生成矩阵为Y、Y,则A 式中：w,∈[0,1]表示数据对象X,对聚类中心C 和A2相似，D1和D2相似，L,和L2相似，Y和Y2 k 相似 的隶属度，且 ∑"g=l,a≥0为模糊算子.隶属度 证 明设以，，顺序输入得到的相 函数和聚类中心更新公式为 0A12…A1 (1/d) (2) 似矩阵A1 A21 0 A3 ,以，虽，…马逆 … … .ve Anl An2 0 X 序输入得到的相似矩阵 54 0 An(n-1) Anl C,= 3) W可 A(n.Un 0 2 由矩阵 wrdsi)2 A2n 算法描述为：初始化聚类中心，通过式(2)和式 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net谱聚类初始化敏感的实质原因 ,通过引入模糊 K2 Harmonic means(FKHM)算法来解决对初值敏感的 问题 ,从而得到更稳定的聚类性能. 在人工数据和真 实数据上进行实验模拟 ,结果表明 , FKHM2SC算法 相对于原有谱聚类算法 ( SC) 和传统的 K2means (KM)算法和 fuzzy C2means(FCM )算法在聚类性能 和稳定性上有了显著的提高. 1 谱聚类算法的初始化敏感分析 谱聚类算法将数据聚类看成是一个无向图的多 路划分问题 ,由于图划分问题的组合本质 ,求图划分 判据的最优解是一个 NP难题 [ 6 ] . 一个有效的求解 方法是考虑问题的连续放松形式 ,将原有问题转换 为求解矩阵的特征值和特征向量问题 ,利用这些特 征向量构造一个简化了的数据空间 ,在该空间中的 数据的分布结构更加明显 ,代表性算法有 Ng等人 提出的 NJW 算法 [ 7 ] . NJW 算法本质上是利用相似矩阵的特征向量 进行聚类 ,选取构造矩阵的前 K个最大特征值所对 应的特征向量 ,从而在 K维空间中构成与原数据一 一对应的表述 ,进而在 K维空间中利用 K2means或 其他简单算法进行聚类. 现有的各种谱聚类算法的差异之处在于 : 1)构 造的相似矩阵不同 ; 2)使用的特征向量不同 ; 3)从 特征向量获得最终的聚类方法不同 ; 4)从连续变量 放松到离散变量的方法不同. NJW 算法是基于上述 的第 3种多类实现方法给出的一种简单有效方法 , 由于传统的 K2means算法对初始值敏感 ,故 NJW 算 法对初值敏感是否归结于最终的聚类方法. 下面给 出谱聚类算法对初值敏感的证明. 定理 1 设数据集 S = { s1 , …, sn } ,以 2种不 同顺序输入得到的相似矩阵为 A1、A2 ,对角矩阵为 D1、D2 ,构造矩阵为 L1、L2 ,生成矩阵为 Y1、Y2 ,则 A1 和 A2 相似 , D1 和 D2 相似 , L1 和 L2 相似 , Y1 和 Y2 相似. 证 明 设以 s1 , s2 , …, sn 顺序输入得到的相 似矩阵 A1 = 0 A12 … A1n A21 0 … A2n … … … … An1 An2 … 0 ,以 s1 , s2 , …, sn逆 序输入得到的相似矩阵 A2 = 0 An ( n - 1) … An1 A ( n - 1) n 0 … A ( n - 1) 1 … … … … A1n A2n … 0 , 由矩阵 知识易知 ,矩阵 A1 经过若干次初等行或者列变换 则可以得到矩阵 A2 ,故矩阵 A1 和 A2 相似. 同理 ,当 以任意顺序输入得到的相似矩阵 A2 均与 A1 相似. 由于矩阵 D1 为对角矩阵 ,其主对角元素为相似矩 阵 A1 的相应各行元素之和 ,故矩阵 D1 和 D2 相似. 因为 L1 =D - 1 /2 1 /A1D - 1 /2 1 , L2 =D - 1 /2 2 A2D - 1 /2 2 ,且 D1、D2 为对角矩阵 ,由上面的相似关系可知矩阵 L1 和 L2 相似 ,其对应的特征向量 x1 经过若干次初等 变换可以得到特征向量 x2 ,则生成矩阵 Y1 和 Y2 亦 相似. 故结论成立. 2 改进的谱聚类算法 通过定理 1可知 ,不同输入顺序得到的相似矩 阵 A和最终的生成矩阵 Y是相似的 ,故谱聚类算法 对初始值敏感的实质在于 NJW 算法从特征向量获 得最终的聚类方法是否对初始化敏感. 传统的 K2 means和 FCM算法对初始中心敏感 [ 5 ] ,对于不同的 初始值 ,可能得到不同的聚类结果. 在此基础上 ,通 过引入对初值不敏感的模糊 K2harmonic means算法 来克服这一缺点. 2. 1 模糊 K2harmonic means算法 模糊 K2harmonic means(FKHM )算法 [ 8 ]是一种 基于中心的聚类算法 ,将模糊概念应用到 KHM 算 法 [ 9 ]中 ,应用数据点对不同聚类的隶属度对目标函 数中的距离测度进行模糊加权. 设 X = { xi | i = 1, …, n} 为 n个数据点的集合 , C = { Cj | j = 1, …, k} 为 k个聚类中心的集合 , di, j = ‖Xi - Cj‖表示为数 据对象到聚类中心的距离表示 ,采用欧式距离表示. 其目标函数为 EFHKM = ∑ n i =1 k ∑ k j=1 1 w α ij d 2 i, j . (1) 式中 : wij ∈ [ 0, 1 ]表示数据对象 Xi 对聚类中心 Cj 的隶属度 ,且 ∑ k j=1 wij = 1,α≥0为 模糊算子. 隶属度 函数和聚类中心更新公式为 wij = (1 / d 2 i, j ) 1 / (α+1) ∑ k z =1 (1 / d 2 i, z ) 1 / (α+1) , (2) Cj = ∑ n i =1 w α ij ∑ k z =1 ( w α ij d 2 i, j w α iz d 2 i, z ) 2 Xi ∑ n i =1 w α ij ∑ k z =1 ( w α ij d 2 i, j w α iz d 2 i, z ) 2 . (3) 算法描述为 :初始化聚类中心 ,通过式 (2)和式 ·96· 智 能 系 统 学 报 第 4卷