摘要 谱嵌入聚类（SEC算法要求样本满足流形假设，样本标签总是可以嵌入到一个线性空间中去，这为线性可分数据的谱嵌入聚类问题提供了新的思路，但该算法使用的线性映射函数不适用于处理高维非线性数据。针对这一问题，通过核化线性映射函数，建立了基于核函数的谱嵌入聚类（KSEC模型，该模型既能解决线性映射函数不能处理非线性数据的问题，又实现了对高维数据的核降维。在真实数据集上的实验分析结果表明，使用所提算法后聚类正确率平均提高了13.11%，最高可提高31.62%，特别在高维数据上平均提高了16.53%，而且在算法关于参数的敏感度实验中发现算法的稳定性更好。所以改进后的算法对高维非线性数据具有很好的聚类效果，获得了比传统谱嵌入聚类算法更高的聚类准确率和更好的聚类性能。所提方法可以用于诸如遥感影像这类复杂图像的处理领域。
　　关键词 谱聚类；谱嵌入；核函数；高维数据
　　中图分类号 TP181
　　文献标志码 A
　　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

---

期刊库（http://www.zgqkk.com），是一个专门从事期刊推广、投稿辅导的网站。
　　本站提供如何投稿辅导，寻求投稿辅导合作，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。

---

　　【免责声明】本文仅代表作者本人观点，与投稿辅导_期刊发表_中国期刊库专业期刊网站无关。投稿辅导_期刊发表_中国期刊库专业期刊网站站对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考，并请自行承担全部责任。