一种基于抽样改进加权核K-means的大数据谱聚类算法

金 海，张劲松，吴 睿,3

(1. 深圳职业技术学院，广东 深圳 518055； 2. 浙江工业大学， 浙江 杭州 310014; 3. 西安交通大学，陕西 西安 710061)

科技与互联网的快速发展产生了海量信息数据，如何从TB、PB级的数据中提取有价值的知识，聚类成为主要工具。聚类能够根据数据特征和内在关系，将特征相似数据归类，从而高效组织数据[1]。现有聚类算法大多基于欧氏距离，对于非凸样本空间易陷入局部最优，且无法完全反映复杂数据集的空间分布特点[2-3]。而基于非线性核距离计算相似矩阵的谱聚类，可实现包含非凸形结构等任意形状样本集的全局最优解聚类，成为极具竞争力的聚类方法[4]。

经典算法在较小规模的数据集上聚类性能优越，而随着海量规模数据集应用的出现，其相似矩阵的计算、存储及特征分解的时间、空间复杂度限制了其优越性能的发挥[5]。为此，钱鹏江等[6]约束谱聚类的指示向量并融合约束最小球理论，将大规模数据集自适应图松弛谱聚类算法的复杂度降低到渐近线性时间，数据抽样和并行处理能够避免数据规模的限制。Li等[7]抽取代表点构建了邻接矩阵，并计算了其特征向量和特征解。张顺龙等[8]借助稀疏编码抽取了大规模集的代表点来逼近相似矩阵，但其抽样点集需尽可能大。杨艺等[4]在选取的核心点集上进行分组和谱聚类，并根据数据一致性进行了大规模数据的谱聚类。Fowlkes等[9]研究了Nyström近似来改善经典谱聚类的相似性矩阵计算。Kumar等[10]根据Nyström误差界分析，采用集成抽样方法以牺牲准确性换取更快的算法收敛速度，提高了算法的效率。

稀疏化和Nyström近似对内存占用效果较好，但仍需计算经典谱聚类的全部相似矩阵，为此，Dhillon等[11]在推导出加权核K-means算法与谱聚类目标函数在数学上等价基础上，通过加权核K-means来优化谱聚类的目标函数，避免全部相似矩阵的计算，取得了更好的聚类结果，但其核矩阵仍需较多的存储和计算资源。因此，在分析核矩阵复杂性原因的基础上，本文提出基于随机抽样改进加权核K-means算法的大规模数据集谱聚类方法。算法通过Leaderths算子快速获得初始聚类数，以指导数据抽样，然后在子样本集中约束样本子空间逼近聚类中心，从而仅需计算样本核矩阵，极大减少核矩阵的复杂度。

1 基于加权核K-means的谱聚类算法

1.1 经典谱聚类

经典谱聚类基于谱图理论，将数据聚类转为最佳子图划分问题[3]。数据集表示为无向加权图G=(V,E,A)，其中V为待聚类数据集，E表示数据间连接的集合，而衡量连接值大小即衡量两数据同类可能性的权重，组成非负对称矩阵A。

(1)

式中，link_ratio(Vi,Vi)描述子类Vi内元素的归一化连接权值。由于对于一次聚类，类内总权值与类间总权值之和为整个无向图节点总权值，因此，最大化式(1)所示目标函数可以使类内连接权值最大且类间连接权值最小。

(2)

1.2 加权核K-means算法

核K-means算法采用非线性核距离度量，与经典K-means算法相比，更适于存在非线性分布的数据集的聚类，目标函数为使划分后的类中数据点到类中心的距离误差总和最小[12]，即

(3)

式中,κ():Rd×Rd→R为非线性核距离函数；Hk为其再生核希尔伯特空间；ci()为每个子类的聚类中心。

对数据集中元素分配权值w，则加权核K-means目标函数为

(4)

其聚类中心为

(5)

由此可以得到加权类别矩阵Y∈Rk×n为

Y=(y1,…,yk)T=UW

(6)

式中，W=diag(w1,…,wn)。对式(4)的平方项展开并推导为矩阵秩的形式可得[11]

(7)

(8)

但加权核K-means的核矩阵计算和存储，在大规模数据应用时仍受限。为此，本文通过随机抽样近似核矩阵，设计了改进加权核K-means算法，以减少大数据集应用中算法的时间和空间复杂度。

2 抽样改进加权核K-means算法

数据抽样思想改进加权核K-means算法可以避免数据规模的限制[13]，但样本集的数据规模及其初始类设置对原始大数据集所含类别的完整覆盖，对算法的聚类性能起决定作用。为此，首先通过Leaders快速聚类方法对大规模数据集进行初始聚类，获得初始聚类中心，然后根据初始中心多次随机抽样形成多子样本集，对每个子样本集进行加权核K-means聚类，最后对各子样本集聚类结果进行整合，从而在合理控制抽样数据规模的同时增强初始聚类设置对原始类别的覆盖，使其近似核矩阵的计算更合理。

2.1 基于Leaders初始聚类设置

Leaders方法[14]通过选取大规模数据集中各子类的Leader来实现基于能量的数据聚类，其在无需先验数据类别数设置的情况下，对大数据集只需扫描一次即可完成聚类。虽然该算法对数据元素的输入顺序较为敏感，聚类结果并不精确，会存在类内相似性大于类间相似性的情况，但其聚类速度较快，聚类效率优势十分明显，可以用于对大规模数据集的预处理，算法实现过程见表1。

表1 Leaders算法的伪代码实现

文中采用Leaders算法进行初始聚类预处理，利用获得的聚类中心进行多样本子集的随机抽样和样本集的加权核K-means聚类初始值设置。

2.2 子样本集加权核K-means聚类

Leaders算法聚类结果并不精确，会存在类内相似性大于类间相似性的情况，因此对每个初始聚类中心的数据进行随机抽样，可以在维护各个抽样之间关联性的同时，将未被正确分类的数据通过随机抽样分布到不同的子样本集中，这样通过子样本集的重新聚类实现这部分数据的新分类。

(9)

(10)

(11)

(12)

将式(8)代入得抽样子集改进加权核K-means算法的目标函数为

(13)

3 试验与分析

为验证文中谱聚类算法(记为SikSC)的性能，试验将其与传统谱聚类(记为TraSC)[1]、自适应Nyström谱聚类(记为NysSC)[9]和内存高效核近似聚类(记为MekSC)[4]3种方法进行比较。试验服务器环境构建为：Intel Xeon E5-2699 v4 @ 2.20 GHz，8 GB内存，Matlab 2012b。试验采用表2所示的4个数据集，Waveform集由施加均值0、σ2=1噪声的3种类型的波形样本组成[15]；Ringnorm集[16]包含正态分布的两种样本，且两样本存在重叠，聚类难度较大；USPS集和MNIST集为图片集，各包含10种手写数字[16]。

表2 试验数据集相关参数

采用归一化互信息(NMI)作为评价指标

(14)

式中，Uc和Ut分别为试验和真实类别矩阵，H(Uc)和H(Ut)分别为其信息熵。试验中迭代次数为50，聚类结果为20次试验平均值。

3.1 聚类性能比较试验

图1所示为4种算法在不同采样点数的聚类NMI结果，由于传统谱聚类对所有数据进行处理，因此其在前3个数据集结果如图中虚线所示，其在各采样点下NMI值始终为唯一值；而在图1(d)的MINIST数据集中，由于数据集规模太大，平台内存局限，传统谱聚类无法实现聚类。

图1 算法在各数据集上的性能试验结果

从图中试验结果看出，传统算法由于使用所有数据在前3个规模相对较小的数据集中取得聚类结果最优，但在MNIST大规模数据集时因核矩阵占用资源巨大而无法聚类，而NysSC、MekSC及文中SikSC算法通过抽样实现4个数据集的较好聚类，说明抽样约束减少资源占用对大数据谱聚类是有效的。随着采样点数的增加，3种算法聚类性能(NMI指标)逐渐提高，SikSC最优，且逼近传统谱聚类NMI指标，说明文中算法通过改进抽样策略和子集中对聚类中心的约束可以取得与完整核矩阵相近的聚类结果，也说明改进方法有效。

3.2 算法运行时间比较试验

在上一试验基础上，NysSC、MekSC和SikSC这3种算法采样点数取2000，TraSC仍使用全部数据，在4个数据集上运行时间比较结果见表3。

表3 算法运行时间的试验结果 s

从运行时间可以看出，传统算法运行时间最长，其完整的Laplacian矩阵特征分解时间复杂度最高，而使用数据抽样或近似的NysSC、MekSC及SikSC算法的运行时间在所有数据集上都大幅缩减，且在MNIST集上仍取得可接受的聚类时间。进一步测试不同采样点下3种算法的聚类时间可知，随着采样点数的增加，3种算法的聚类时间也逐渐增加，但SikSC算法的变化趋势相对最为缓慢，且聚类时间较短，这是由于NysSC算法近似特征向量的计算时间开销较大，而MekSC算法的最佳秩近似核矩阵的求解效率也大幅降低。

综合试验结果可以看出，SikSC算法在保持与经典SwkSC算法聚类性能相似的情况下，极大地提高了算法的聚类效率，更适合大规模数据挖掘工作。

4 结 语

在分析经典谱聚类算法目标函数与加权核K-means函数等价基础上，设计了一种基于抽样改进加权核K-means算法的大规模数据谱聚类算法。算法通过Leaders进行初始聚类预处理，以增加随机抽样的有效性，使随机抽样及其数据规模更合理，通过子类加权核K-means迭代优化避免Laplacian矩阵特征分解资源占用，从而通过部分核矩阵的使用降低经典算法的时间、空间复杂度。试验结果表明，改进算法在保持聚类精度基础上，大幅提高了聚类效率。