本文摘要：谱嵌入聚类是建立在谱图理论基础上，该算法主要应用于计算机视觉，目前此种算法正在迅速成为国际机器学习领域的研究热点，其中数据聚类有良好的应用前景，小编推荐关于在谱嵌入聚类在计算机应用的论文。 摘要：谱嵌入聚类(SEC算法要求样本满足流形假设，样本
谱嵌入聚类是建立在谱图理论基础上，该算法主要应用于计算机视觉，目前此种算法正在迅速成为国际机器学习领域的研究热点，其中数据聚类有良好的应用前景，小编推荐关于在谱嵌入聚类在计算机应用的论文。
摘要：谱嵌入聚类(SEC算法要求样本满足流形假设，样本标签总是可以嵌入到一个线性空间中去，这为线性可分数据的谱嵌入聚类问题提供了新的思路，但该算法使用的线性映射函数不适用于处理高维非线性数据。针对这一问题，通过核化线性映射函数，建立了基于核函数的谱嵌入聚类(KSEC模型，该模型既能解决线性映射函数不能处理非线性数据的问题，又实现了对高维数据的核降维。在真实数据集上的实验分析结果表明，使用所提算法后聚类正确率平均提高了13.11%，最高可提高31.62%，特别在高维数据上平均提高了16.53%，而且在算法关于参数的敏感度实验中发现算法的稳定性更好。所以改进后的算法对高维非线性数据具有很好的聚类效果，获得了比传统谱嵌入聚类算法更高的聚类准确率和更好的聚类性能。所提方法可以用于诸如遥感影像这类复杂图像的处理领域。
关键词：谱聚类;谱嵌入;核函数;高维数据
0引言
谱聚类算法(Spectral Clustering Algorithm， SCA是近几年来机器学习和数据挖掘领域研究的热点算法之一，它是聚类算法引入谱图理论之后诞生的一类新算法[1]。与传统的聚类算法相比，它能够不受凸集样本的特性限制而获得全局最优解，得到更好的聚类结果。
在谱聚类算法的研究过程中，文献[2]提出了用大于k个特征向量去构建特征空间来进行谱聚类，获得了比传统的kway方法更好的聚类结果;文献[3]则从亲和度矩阵的构造和特征分解过程出发，提出了非负稀疏谱聚类算法，在时间和空间杂度上改善了谱聚类算法的性能;文献[4]将实例约束泛化到空间约束，使用半监督方法大大提高了谱聚类性能。谱聚类算法发展至今，虽然在大多数数据集上能够得到好的聚类结果，但是在将它扩展到海量数据时仍然困难重重，尤其是在解决高维数据的问题上。Wu等[5]提出在面对高维数据时可以利用稀疏向量来构造亲和度矩阵，避免了海量数据聚类时高昂的计算代价;Nie等[6]则在2011年提出了谱嵌入聚类(Spectral Embedded Clustering， SEC算法框架，指出高维数据的类别标签矩阵总是可以嵌入到一个线性空间中去，数据样本按照类别在这个空间中跨度开来，即所有的数据在C维空间中都有自己的类标签，C代表N个数据样本的类别总数目，这便解决了高维数据因不具备低维的流形结构而造成的聚类困难，相比传统的SCA较好地解决了高维数据的谱聚类问题;2012年Jiao 等[7]将成对点约束监督信息引入到SEC框架中，增强了数据谱嵌入的能力，取得了较好的聚类效果。
由于谱嵌入聚类算法在聚类时选用线性的映射函数，所以它对线性可分数据具有较好的聚类效果，但对非线性数据并不适用。针对这一问题本文提出了一种基于核函数的谱嵌入聚类(Spectral Embedded Clustering based on Kernel function， KSEC算法，将核函数引入到SEC框架中去，很好地改善了高维非线性数据的谱聚类性能。通过在真实数据集上进行实验，与传统的一些谱聚类算法进行比较后发现改进后的算法效果更为良好。
1谱聚类算法
谱图理论是图论领域经典的知识体系，它通过矩阵论方法来研究图的邻接矩阵，挖掘其潜在的结构信息，这里的结构信息在数据上便体现为类别信息，它的基础是图的Laplacian矩阵，是由Fiedler[8]在1973年提出来的。将数据的聚类问题转化为对图的划分问题的求解，这便是建立在谱图理论基础之上的谱聚类算法的核心思想。
谱聚类算法实现的基本流程[9]描述如下：1数据预处理。将数据转化为一个无向加权图，采用高斯核函数(式(1计算两个样本点之间的相似性[10]，得到这个图的邻接矩阵。2谱映射。对Laplacian矩阵进行特征分解，在得到的特征向量中选择一个或者多个合适的向量构造特征空间。3对数据进行聚类。使用经典聚类算法，例如Kmeans算法在新的数据空间进行聚类，将聚类结果映射回原始数据空间，算法结束。图1展示了Iris数据的类别分布与它的Laplacian矩阵结构间的关系，其中Laplacian矩阵图是对称结构，每一个像素点代表两个样本之间的相似度大小，取值在0～1。
Aij=exp-d(si，sj2σ2(1
2谱嵌入聚类算法框架
给定一个数据样本集合X={x1，x2，…，xn}∈Rd×n;定义X的簇分配矩阵Y=[y1，y2，…，yn]T∈Bn×c，c代表簇的个数，定义它的扩展簇分配矩阵为F[6]1798：
F=D12Z=D12Y(YTDY12=f(Y(2
其中：Z=Y(YTDY- 12，D为度矩阵，将其进行放松连续化处理后F∈Rn×c。为方便计算，假设数据都是中心化的，即X1n=0，这时定义数据的总体散布矩阵为St，类间散布矩阵为Sb，类内散布矩阵为Sw：
St=XXT
Sb=XGGTXT
Sw=XXT-XGGTXT(3
其中：G=Y(YTY- 12。
文献[6]证明了如果rank(Sb=c-1且rank(St=rank(Sw+rank(Sb，那么簇分配矩阵便能够由一个低维的线性空间来描述，这时存在W∈Rd×c，b∈Rc×1使得Y=XTW+1nbT。
基于以上矩阵定义和理论支持，文献[6]提出了SEC算法将线性正则化方法引入到SCA算法当中，提出目标函数为式(4
minF，W，bFTF=IcJ(F+u(‖XTW+1nbT-F‖2+γgtr(WTW(4其中，u和γg是两个正则化参数，第一个参数描述簇分配矩阵与低维空间的线性关系的强弱，第二个参数描述簇分配矩阵被放松处理后的F与低维线性空间的不匹配程度;J(F=tr(FTLF指的是传统谱聚类算法的目标函数。在式(4上对W和b分别进行求导，使其结果等于0得：
W=(XXT+γgId-1XF
b=1nFT1n(5
将式(5代入式(4后进行化简，优化问题便转化为：
minFTF=IcJ(F+uP(F(6
其中
P(F=tr(FTLgF。
Lg=Hn-XT(XXT+γgId-1X(7
其中
Hn=In-1n1n1Tn。
这时，与传统的谱聚类算法同理，对簇分配矩阵的求解进行放松处理便转化为对L+uLg的特征分解问题了，取前c个最小特征值对应的特征向量构建特征空间，在新的特征空间中对数据进行划分，就成功地实现了对高维数据的准确聚类。
3基于核函数的谱嵌入聚类算法
3.1核函数
经典的核学习理论指出，低维空间中线性不可分的模式通过一种非线性映射到高维特征空间后，就能够实现线性可分。但是，如果直接采用这种非线性映射技术在高维空间进行分类或者回归，就必然面临着映射函数的形式和参数的确定问题，而且很有可能引发“维数灾难”，这时采用核函数可以有效地解决这一问题。设x，z∈X，X属于R(n空间，非线性函数Φ实现了低维空间中数据X到高维的特征空间F的映射，其中F属于R(m，(nm空间，则核函数[11]定义为：
k(x，z=〈Φ(x，Φ(z〉(8
其中
〈〉表示内积，k(x，z表示核函数。
式(8表明核函数将m维(高维空间里的内积运算转化成了n维(低维空间里的核函数计算，从而解决了数据的“高维”带来的维数灾难问题，而且核函数不需要知道非线性变换函数Φ的形式和参数，引入方便。本文选用高斯核函数来完成非线性数据到高维的映射过程，同时该函数也是在谱聚类算法开始时构造亲和度矩阵的径向基函数。
3.2KSEC算法
根据以上分析，基于核函数的谱嵌入聚类算法(KSEC引入一个非线性的核函数yi=f(xi=∑nj=1αik(xi，xj，将非线性的不可分数据映射到高维的特征空间实现可分，这里的核函数选用高斯核函数，与式(1定义相同。
KSEC算法使用核化的映射函数将高维非线性数据X映射后，将其簇分配矩阵嵌入到一个线性低维空间，设置目标函数为：
minF，W，bFTF=IcJ(F+u(‖Kα-F‖2+γgtr(ααT(9
在目标函数式(9上，把对α的求导结果置为0可得α=(K+γgIn-1F∈Rn×c。根据矩阵的2范数和矩阵迹的关系，式(9可以转化为：
minF，W，bFTF=IcJ(F+u(tr[(Kα-F(Kα-FT]+γgtr(ααT(10
将α代入式(10，目标函数的优化问题转化为式(6所列形式，其中P(F=tr(FLgFT，注意这里：
Lg=In-(K+γgIn-1(11
至此，KSEC算法的理论推导便转化为了对Lsym+uLg的特征求解问题了。算法1详细介绍了KSEC算法的实现流程。
核化的映射函数对数据的处理不再局限于线性可分数据，它对使用线性映射函数难以处理的数据，例如高维数据和稀疏数据都能够很好地进行映射以便实现可分，当然对线性可分数据它依然适用。对比式(7和式(11发现核函数的引入大大精简了待求式的中间量如In和1n，简化了Lg的计算，提高了算法效率。从算法复杂度上来分析，算法第1步构造亲和度矩阵时的时间复杂度为O(n2，第4步进行矩阵分解时的时间复杂度为O(n2+1，所以该算法的整体时间复杂度为O(n2+1+n2，即O(n2。
算法1KSEC算法。
输入：数据集X={x1，x2，…xn}∈Rd×n，参数σ，类别数c，正则化参数u、γg。
输出：数据的类标签。
小编推荐优秀电子期刊 《计算机工程与科学》
《计算机工程与科学》(月刊)创刊于1973年，由国防科技大学计算机学院主办。办刊宗旨是为计算机界同行发表有创见的学术论文，介绍有特色的科研成果，探讨有新意的学术观点提供理想园地;活跃计算机界学术气氛，扩大国内外交流，为发展中国的计算机事业尽一点微薄之力。
转载请注明来自发表学术论文网：http://www.fbxslw.com/dzlw/3814.html
