一种基于灰关联分析的谱聚类方法

一种基于灰关联分析的谱聚类方法

1基于差异信息模型的灰关联分析聚类分析是机械学习领域的一个重要研究方向。作为一种有效的数据分析方法，它已广泛应用于机械工具、文本检索、语音识别等领域。传统的聚类算法（如k-mean算法、im算法等）当样品接近凸球形时，聚类效果好，但当样品呈任意形状时，很容易陷入局部最优的解。集群算法主要用于计算机视觉、vlasi设计等领域，后来扩展到机械学习。由于它能识别微凸分布，不受数据维数的影响，它可以收敛整体最优解决的优点，引起人们的注意，并迅速成为机械学习领域的研究热点。然而，现有的集群算法对参数的变化非常敏感，并且微变化的参数值会影响集群的效果。不同数据集的最佳参数值不同，这会影响算法的适用性。灰色理论作为一种处理现实中存在的部分信息明确、部分信息不明确的“小样本”、“贫信息”等不确定性问题的有力工具,已经在油气勘探、工业控制、图像处理、网络安全、经济预测、物流管理等多个学科领域得到广泛应用.本文提出利用基于差异信息理论的灰关联分析中均衡接近度的概念来测度数据点间的相似度,以改进现有谱聚类方法的性能,实验证明新方法能够得到更好的聚类结果.2灰关联分析的应用灰色系统理论是由邓聚龙教授于1982年提出的一种处理不确定性和非线性问题的系统理论,主要包括灰哲学、灰生成、灰分析、灰建模、灰预测、灰决策、灰控制、灰评估、灰数学等方面的内容.灰关联分析是灰色系统分析中的一个重要内容,与数理统计中的回归分析、方差分析和主成分分析不同,它对样本的数量和分布规律不做要求,量化结果与定性分析的结果保持一致,因此特别适用于对小样本、无明显规律的数据进行研究.2.1生成线性助推式的线性范围和灰关联度定义1设序列集X={xi|xi=(xi(1),xi(2),…,xi(n)),i∈N},N={1,2,…,m},若X满足1),xi(k)和xj(k)为同一数量级,Vk∈K,K={1,2,…,n},记为属性ρ1;2)不同序列对应的分量间可以定义距离测度,简称为数值可接近性,记为属性ρ2,则称序列集X为因子集.定义2设序列集X=x{xi|xi=(xi(1),xi(2),…,xi((n)),i∈N},N={1,2,…,m},存在映射Ti=x→x,Ti可以采用以下形式称Ti为序列的纯量化算子.T1至T6分别称为初始值化算子、均值化算子、最大值化算子、最小值化算子、区间值化算子和始点零化算子.定义3设X为灰关联因子集,X=x{xi|xi=(xi(1),xi(2),…,xi(n)),i∈N},N={0,1,2,…,m},m≥2,K={1,2,…,n},n≥3,x0∈X为参考序列,而xi∈X为比较序列,若存在一个非负实数γ(x0(k),xi(k))为X上一定环境下的比较测度,且令非负实数则当其满足规范性、偶对称性、整体性、接近性时,称γ(x0(k),xi(k))为xi对x0在k点的灰关联系数,称γ(x0,xi)为xi对x0的灰关联度.2.2灰关联熵-均衡距离度张岐山教授以灰朦胧集为背景,从差异信息的角度建立了一套信息序列的熵理论,并以此为基础研究了灰色系统中若干重要理论问题.在灰关联分析方面,通过引入灰关联熵,克服了传统灰关联分析可能造成局部点关联倾向的问题.定义4灰关联密度:设X为灰关联因子集,X={xi|i∈N},N={0,1,2,…,m},m≥2,xi=(xi(1),xi(2),…,xi(k)),k∈K={1,2,…,n},n≥3,x0为参考序列,xi为比较序列,ri=(γ(x0(k),xi(k)))为第i个比较序列的灰关联系数序列,C={ri|i∈N}为灰关联系数序列集,则称映射为灰关联系数分布映射,映射值v(x0(k),xi(k))为第i个比较序列在第k点的灰关联密度值.此比较序列的所有关联密度值的全体构成灰关联密度序列,记为vi.定义5灰关联熵:设X为灰关联因子集,X={xi|i∈N},N={0,1,2,…,m},m≥2,xi=(xi(1),xi(2),…,xi(k)),k∈K={1,2,…,n},n≥3,x0为参考序列,xi为比较序列,ri=(γ(x0(k),xi(k)))为第i个比较序列的灰关联系数序列,C={ri|i∈N}为灰关联系数序列集,V={vi|i∈N}为灰关联密度序列集,则称函数为第i个比较序列的灰关联熵.定义6熵关联度:设I(vi)为第i个比较序列的灰关联熵,Im为灰关联系数序列的最大关联熵,则称为第i个比较序列的熵关联度.定义7均衡接近度:设γ(x0,xi)和E(x0,xi)分别为第i个比较序列的灰关联度和熵关联度,则称为第i个比较序列的均衡接近度.由于均衡接近度既考虑了灰关联因子序列间点的距离接近性,又考虑了整体的无差异性接近,因此可以克服点关联强倾向问题.3多路规范割准则谱聚类算法的思想来源于谱图划分理论.如果将数据集看成一个无向完全图G=(V,E),数据点作为图的顶点,将数据点间的相似度量化作为顶点连接边的权值,则聚类问题就转化为图的划分问题.要使聚类效果达到最优也就是设计一种划分准则,使划分后的子图间的相似度最小,而子图内部的相似度最大.因此,划分准则的好坏对聚类效果有直接影响.目前常用的划分准则主要有规范割准则(Normalizedcut)、比例割准则(Ratiocut)、平均割准则(Averagecut)、多路规范割准则(Multi-waynormalizedcut)等.其中,规范割准则是求目标函数的最小值.其中是子图A中的顶点与图V中所有顶点间的连接边的权值的总和,assoc(B,V)也仿此定义.从公式(12)可以看出,规范割准则同时考虑簇内数据相似度最高和簇间数据相异度最低,因此其划分效果比较好.但是,由于它是一种2路划分法,当簇数大于2时需要进行递归划分.Meila和Shi扩展了2路划分法,提出多路规范割准则(Multi-waynormalizedcut),其目标函数为MNcut可以将图G同时划分为k个子图.可以证明,求图的最优划分是一个NP难问题.但是,通过放松问题的约束条件,对由相似矩阵S生成的Laplacian矩阵L进行谱分解,可以在多项式时间内逼近最优解.Laplacian矩阵的形式主要有三种其中,矩阵D是一个对角矩阵,其对角线元素为各顶点的度.D一般被称为度矩阵.目前典型的谱聚类算法有Perona和Freeman提出的PF算法,Shi和Malik提出的Ncut算法,Kannan等提出的KVV算法,Ng,Jordan和Weiss提出的NJW算法,Meila和Shi提出的MNcut算法,等等.不同的算法采用不同的Laplacian矩阵生成方法,如:Ncut算法使用公式(14),MNcut算法使用公式(15),NJW算法用的是公式(16).在描述数据点间的相似度方面,多数算法采用形如的高斯核函数.其中,si代表数据点,σ是算法的参数.谱算法的基本步骤可以归纳为1)构建相似矩阵S.2)从公式(14)至公式(16)中选择一种构建Laplacian矩阵L.3)求矩阵L的特征值和特征向量.4)子图划分.(a)2路划分:根据矩阵L的第二小特征值对应的特征向量将数据点划分成两个簇,在划分好的两个簇上再递归进行2路划分,直到找到指定数量的簇.(b)多路划分:根据矩阵L的前k个正交特征向量组成特征矩阵,应用K-Means算法或其它的聚类算法对其进行聚类.谱聚类算法在取得广泛成功的同时也存在一些亟待解决的问题,如:聚类的效果对参数σ的变化非常敏感,将其应用于大规模学习问题时计算量太大,如何自动确定聚类数目,等等.4基于灰关联分析的相关研究传统谱聚类算法中的相似性测度采用的是高斯核函数,需要确定参数σ.从灰关联分析的角度,可以将每个数据点表示为由其属性组成的属性序列,通过计算属性序列间的均衡接近度从整体上衡量数据点之间的相似程度.当由于相似度完全由数据点自身的属性值描述,不需要引入额外参数,消除了参数对算法的影响.基于此可以设计一个基于灰关联分析的谱聚类算法,即GSC(Greyspectralclustering)算法.4.1计算相似度矩阵及特征向量1)输入簇数参数k和数据集,构建数据矩阵Datan×m(每个行向量代表一个数据点);2)确定数据点属性序列si={si1,si2,…,sin},i=1,2,…,n;3)计算所有属性序列的均衡接近度,构建相似度矩阵Sn×n;4)根据公式(14)至公式(16)构建Laplacian矩阵,计算L的特征值和特征向量,取前k个最大特征值对应的特征向量x1,x2,…,xk,构造矩阵X=[x1,x2,…,xk]∈Rn×k;5)将矩阵X的每个行向量看作一个数据点,用K-Means算法对将其划分成k个簇;6)若矩阵X的第i行被划分到簇j,则也将对应原始数据点si划分到簇j;7)输出聚类结果.4.2算法的时间复杂度GSC算法中,构建数据矩阵需要O(n×m)的时间,计算任意两个属性序列的均衡接近度的时间复杂度为O(m),因此构建相似度矩阵T需要的时间为O(n2×m).求矩阵特征值的时间复杂度一般为O(n3),但当矩阵是稀疏对称阵时,用Lanczos方法可以将时间减少到O(C×n),其中C为求解过程中需要用到的矩阵-向量计算的次数的最大值,一般C=o(n).K-Means算法的时间复杂度为O(k×m×n),因此,整个算法在最坏情况下的时间复杂度为O(n3).算法中矩阵S和矩阵L占用的空间均为O(n2),矩阵X占用的空间为O(k×n),因此整个算法的空间复杂度为O(n2).5实验结果与分析为了验证新算法的聚类性能,在一台硬件配置为1.66GHzCPU、2GB内存,软件配置为WindowsXPSP2的PC机上进行实验,从UCI机器学习数据集仓库中选取6个有代表性的数据集与Ncut算法和NJW算法做对比,表1给出测试数据集的相关信息.实验采用精确度(Accuracy)指标和F-测度(F-measure)指标对GSC算法、Ncut算法和NJW算法的性能进行评测,精确度指标从整体上衡量一个算法的聚类效果,其定义如下:其中,N1为正确分类的实例数,N2为全部实例数.F-测度指标着重于通过衡量每个类的聚类质量来综合评价算法的聚类效果,其定义如下:其中,T(i)表示正确分到第i个类的实例数,Cluster(i)表示第i个簇的实例数,Class(i)表示第i个类的实例数.每个算法在每个数据集上重复测试100次,取其平均值为实验结果.由于GSC算法的聚类性能还受到灰关联分析中纯量化算子的影响,实验中使用的是使评测值最高的算子.精确度实验结果如表2所示.从表2可以看出,GSC算法在前5个数据集上的聚类精确度都优于对比算法,仅在最后一个Ecoli数据集上略差于NJW算法,这表明在多样化的应用环境中,基于均衡接近度的相似性测度比基于高斯核函数的相似性测度更能反映数据点间的整体相似程度,从而获得更好的聚类结果.而且,由于均衡接近度的计算完全依据数据点自身的信息,不需要引入额外的相似度参数,克服了外部参数对算法性能的影响.F-测度实验结果如表3所示.表3的实验结果表明:即使从微观的角度衡量每个类的聚类质量,也可以得出与精确度实验相似的结论GSC算