基于特征向量自动选取的谱聚类算法

何家玉+许峰

摘 要：根据谱聚类矩阵特征向量组的分段常值性，提出一种基于特征向量组自动选取的谱聚类算法。其基本思想是：首先根据数据集计算出非对称规范Laplace矩阵，然后选择其前个特征向量，最后利用本征间隙法从上述特征向量中自动选取包含聚类信息的特征向量。实验表明，该算法在一定程度上解决了特征向量自动选取问题，可以获得质量较高的聚类结果。

关键词关键词：谱聚类；特征向量；谱聚类矩阵；本征间隙

DOIDOI：10.11907/rjdk.161953

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2016）008-0023-03

0 引言

聚类分析是数据挖掘的一个重要研究领域，在统计学、生物学、模式识别、机器学习和社会科学中有着极为广泛的应用。所谓聚类，就是将数据对象分成多个类或簇，使得同一簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。k-均值聚类是聚类分析中最经典的算法，算法简单，可用于多种类型数据的聚类。但当数据集为非凸时，k-均值聚类往往陷于局部最优，聚類的效果欠佳。此外，对于大小或密度不均匀的簇，k-均值聚类通常无法处理。

谱聚类是一种新型的聚类分析方法，可以克服k-均值聚类等经典方法的某些缺陷。谱聚类方法以图论中的谱图理论为基础，将聚类问题转化为图最优划分问题。在众多图的最优划分准则中，归一化割集准则的划分效果相对较好，是谱聚类中常用的划分准则。对于给定的划分准则和聚类数目k，谱聚类通常采用多路谱聚类算法将数据集划分为k个簇。

最早的谱聚类算法是Ng、Bach和Jordan提出的多路谱聚类方法。代表性的谱聚类算法还有Meila提出的多路归一化割谱聚类方法；Vidal 提出的子空间谱聚类方法；Wang等提出的多流形谱聚类方法；Cheng等提出的低秩谱聚类方法；Elhamifar等提出的稀疏子空间谱聚类方法。

在众多谱聚类算法中，多路谱聚类方法和多路归一化割谱聚类方法因其划分效果较好，算法复杂度也较低，被广大学者普遍接受。但这两种算法尚有一些问题有待研究，例如：如何选取包含聚类信息的特征向量？如何确定较合理的聚类数？

本文在多路谱聚类算法的基础上，对特征向量组的选取问题进行研究，提出一种特征向量自动选取的谱聚类算法，并根据数值实验对该算法进行性能测试。

1 谱聚类算法的基本概念与原理

谱聚类的基本思想是将聚类问题转化为图的最优划分问题，利用图的最优划分准则，使划分出的子图之间的边权之和较小，而子图内的边权之和较大。本文算法设计过程中涉及到的基本概念、性质及原理如下：

1.1 谱聚类矩阵

设数据集为{p1，p2，…，pn}，将pi视为图G（V，E）的一个顶点vi，i=1，2，…，n，对边赋权Wij，Wij通常是根据顶点vi，vj间的距离经过某种适当的变换而得，这样就得到一个基于样本点相似度的无向加权图G（V，E，W），从而将数据集{p1，p2，…，pn}的聚类问题转化为在图G（V，E，W）上的最优划分问题。

图划分准则的合理性决定着聚类结果的优劣。由于图划分问题是一个NP难问题，所以首先要将图划分问题转化为连续松弛形式，进而再将其转化为某些谱聚类矩阵的谱分解问题[2]。

常用的谱聚类矩阵如下：

1.3 高斯核参数

在谱聚类算法中，通常先要计算顶点间的距离矩阵，然后再用高斯核函数法将距离矩阵转换为相似矩阵，进而得到各种谱聚类矩阵。根据所选高斯核参数的不同，高斯核函数可分为局部尺度高斯核函数和全局尺度高斯核函数两类。通常采用全局尺度高斯核函数将距离矩阵转化为相似矩阵，具体方法为：

在将距离矩阵转换为相似矩阵的过程中，高斯核参数σ起着极为重要的作用。不同的高斯核参数可能导致不同的划分结果。本文算法中采用Zhang等[11]提出的高斯核函数法。

2 基于特征向量自动选取的谱聚类算法

2.1 算法理论基础

下面给出几个理论结果，它们是本文算法的理论基础。

引理1：非对称规范Laplace矩阵Lrw的性质[2]。

（1）λ，x分别是Lrw的特征值和特征向量的充要条件是λ，x是广义特征值问题Lx=λDx的解。

（2）Lrw具有n个非负、实的特征值：0=λ1≤λ2≤…≤λn。

引理2：连通子图的数目与Lrw的谱之间的关系[2]。

Lrw的特征值0的重数等于图GV，E，W的连通子图V1∪V2∪…∪Vk的数目；特征值0的特征空间由这些子图的指示向量组成。

2.2 算法原理

引理1 确保了Lrw的特征值的实值性和非负性。引理2表明，Lrw的理想情形包含不同类间完全分离的情形，即Lrw的理想情形一般优于相似矩阵和Laplace矩阵的理想情形。另外，Lrw的包含聚类信息的特征向量构成的矩阵具有分段常值性，即它反映的聚类信息比较明显。综上，本文算法中选用Lrw作为谱聚类矩阵。

在经典的谱聚类算法中，往往选定谱聚类矩阵的前k个特征向量，得到特征向量空间，再用k-均值聚类等传统聚类算法对特征向量空间的特征向量进行聚类，从而得出聚类结果。这种作法的局限性在于，当k较大时，选取的k个特征向量不一定包含聚类信息，从而导致聚类结果出现偏差。特别是当聚类数k有误差时，聚类结果会较混乱[6]。

为了解决上述问题，本文提出两个应对策略。首先，为避免遗漏包含聚类信息的特征向量，选取较多的Lrw的特征向量进行分析、判断。当n较大时，究竟选取多少特征向量进行分析比较合理目前尚无定论。综合考虑划分效果和算法的复杂度，本文选取前ln（n）个特征向量进行分析。其次，采用本征间隙法[12]判定选取的特征向量中是否包含聚类信息。

所谓本征间隙是指相邻两个特征值的差。本征间隙法的原理是，根据矩阵摄动理论，本征间隙越大，选取的k个特征向量所构成的子空间就越稳定。

虽然本征间隙法理论上并不能保证找出全部包含聚类信息的特征向量，但由于此方法简单易行，而对特征向量分段常值性的检验能在一定程度上弥补此方法的缺陷。

2.3 算法步骤

根据上述分析，本文提出一种特征向量自动选取的谱聚类方法，具体步骤如下：

3 数值实验

为了检验新算法的聚类性能，本文选取了4组典型的子空间谱聚类仿真数据进行实验，结果如图1～图4所示。

图1中的数据类数较多，但聚类难度并不大；图2和图3中的数据无法用传统方法聚类，适合用谱聚类，其中图3中的数据聚类有一定难度；图4中的数据量大，且密度相差较大，经典谱聚类算法的效果往往欠佳。上述聚类效果图显示，本文提出的特征向量自动选择谱聚类算法对各类子空间聚类问题具有极佳的聚类效果。

4 結语

本文根据非对称规范Laplace矩阵特征向量组的分段常值性，增加了待分析特征向量的数量，并利用本征间隙方法判断特征向量中是否包含聚类信息。数值实验表明，这种算法对典型的谱聚类问题可获得质量较高的聚类结果，在一定程度上解决了特征向量的自动选取问题。

需指出的是，本文提出的算法较适用于独立子空间情形，而对于不满足独立子空间的情形或者是复杂的多流形情形效果欠佳。另外，与经典的谱聚类算法相比，本文算法具有较高的复杂度。

参考文献：

[1]JAIN A，MURTY M，FLYNN P.Data clustering： a review[J].ACM Computing Surveys，1999，31（3）： 264-323.

[2]LUXBRUG U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17（4）： 395-416.

[3]VERMA D，MEILA M.A comparison of spectral clustering algorithm[R].Washington： University of Washington，2003.

[4]NG A，JORDAN M，WEISS Y.On spectral clustering： analysis and an algorithm[C].Advances in Neural Information Processing Systems.Cambridge： MIT Press，2001： 849-856.

[5]BACH F，JORDAN M.Learning spectral clustering[C].Advances in Neural Information Processing Systems.Cambridge： MIT Press，2004： 1-13.

[6]MEILA M，XU L.Multiway cuts and spectral clustering[R].Washington： University of Washington，2003.

[7]VIDAL R.Subspace clustering[J].IEEE Signal Processing Magazine，2011，28（2）：52-68.

[8]WANG Y，JIANG Y，WU Y，et al.Spectral clustering on multiple manifolds[J].IEEE Transactions on Neural Networks，2011，22（7）：1149-1161.

[9]CHENG B，LIU G，WANG J，et al.Multi-task low rank affinity pursuit for image segmentation[J].ICCV，2011（15）：36-39.

[10]ELHAMIFAR E，VIDAL R.Sparse subspace clustering：algorithm，theory，and applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（11）：2765-2781.

[11]ZHANG X，LI J，YU H.Local density adaptive similarity measurement for spectral clustering[J].Pattern Recognition Letters，2011（16）： 352-358.

[12]孔万增，孙志海，杨灿，等.基于本征间隙和正交特征向量的自动谱聚类[J].电子学报，2010，38（8）： 1880-1885.

（责任编辑：陈福时）