聚类学习是一种重要的数据分析技术.为了从纷繁复杂的数据中发现有用的信息,可以先对数据进行聚类,根据数据对象的相关特征,将相似的对象归到同一类里,而差别较大的对象划分到不同类中,找到数据之间的内在联系,为决策提供支持^[1].谱聚类是聚类分析中十分热门的研究领域,与传统的聚类算法(如k-means, FCM)相比,其优势在于:谱聚类算法可以很好地处理非凸形结构的数据集,得到比较满意的聚类结果^[2].谱聚类的背后有着坚实的理论基础,它用图划分的思想处理数据聚类问题,为了得到最优的子图划分,引入拉普拉斯矩阵并对其特征分解,利用特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.

但是传统的谱聚类算法只适用于规模较小的数据集,因为在其聚类过程中,存储相似度矩阵需要的空间复杂度是O(n²);而对拉普拉斯矩阵特征分解,需要的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的^[3].所以,如何降低谱聚类算法的计算复杂度,将其应用于大数据的聚类上,一直是个非常有挑战性的难题.近年来,该问题的研究受到了越来越多的关注.Song等人^[4]设计了一种并行的谱聚类算法,将矩阵稀疏化处理,同时利用机器集群的优势对大规模的数据集进行聚类.Yan等人^[5]从另外的思路,提出了一种快速逼近的谱聚类算法,首先,通过k-means或RP-tree算法对数据集进行失真最小化局部变换,得到代表点的集合;然后,利用谱聚类算法将这些代表点划分成若干类;最后,根据所有点与代表点的一致性,恢复所有点的类属关系.经典的谱聚类算法一般选择前k个特征向量构成低维嵌入空间,但是Lin等人^[6]发现特征向量具有收敛性,利用幂方法对其多次迭代,得到的第1个特征向量具备多路聚类所需要的信息,从而降低了算法复杂度.

当前,在谱聚类研究领域,Nyström扩展技术是一种有效的用于大规模数据聚类的方法.Nyström最初的设计是为了求解积分方程^[7],其原理是:利用少量的抽样点对连续或离散空间中的卷积算子进行逼近,求解近似的特征向量.Williams和Seeger^[8]将Nyström方法引入到核机器学习中,以加速Gram矩阵的特征分解,而准确率并没有明显下降.Fowlkes等人^[9]扩展了Nyström方法,使其可以处理规范割(normalized cut)问题,并用改进的谱聚类算法进行图像分割,取得了很好的效果.

一般情况下,Nyström扩展方法的性能与样本点的选取有很大关系.通常认为,抽样的数目越多,Nyström逼近的效果越好,得到的计算结果与真实值的差别越小^[10].但是大量抽样也有明显的弊端:一方面没有抽样停止的标准,算法无休止地抽样是不可能的;另一方面,随着抽样点的增多,算法的复杂度必然大幅度增加.最初用于谱聚类的Nyström扩展技术是通过随机抽样获得样本点,然而随机抽样具有不稳定性,在处理大数据集时,样本点容易集中在某一局部区域,产生不准确的计算结果.因此,采用何种策略来抽样,使样本点更好地反映原数据集的分布情况,从而降低逼近误差,是Nyström方法的一个十分关键的问题.Zhang等人^{[11, 12]}详细分析了Nyström扩展的低秩逼近误差,指出量化误差的目标函数可由k-means算法求解,然后将k-means初步聚类的中心点作为抽样点,用于Nyström扩展方法.Wang等人^[13]提出一种基于最远最近策略的抽样方法,首先根据每个点被抽样的概率,形成h组数据.再从这些组中采样,获得最终的样本点集合.本文设计了一种自适应的Nyström采样方法,通过多次遍历并更新抽样概率,选取更有意义的样本点,而且从理论上证明了抽样误差会随着遍历次数的增加呈指数下降.基于此,提出一种适用于大数据的基于自适应Nyström采样的谱聚类算法,该算法可以用较小的抽样集获得令人满意的聚类效果.

本文第1节从图论的角度介绍谱聚类算法,重点分析规范割的基本原理.第2节阐述Nyström方法的相关理论,以及如何将其扩展并应用于谱聚类算法.第3节给出自适应的Nyström采样方法,并且从理论层面证明该方法的有效性.第4节提出基于自适应Nyström采样的谱聚类算法.第5节设计实验,将所提出的算法与其他算法进行对比.最后总结本文所做的工作,并给出下一步的研究方向.

1 谱聚类算法原理

给定一个包含N个点的数据集,根据数据点的成对相似性可以构造一个NxN的相似性矩阵,谱方法就是基于相似矩阵的特征向量和特征值来聚类的.利用这些特征向量,可以构造数据点的一个低维嵌入子空间,在这个嵌入空间中,可以使用简单的中心聚类方法(例如k-means)对数据点进行聚类.规范割(normalized cut)^[14]是一个典型的谱聚类算法,下面简要介绍该方法的基本原理.

谱方法是基于图论的,首先将数据点想象成无向加权图G(V,E),节点V代表数据点;边E的权重表示数据点的成对相似性,这些相似性的值就形成了对称矩阵WΡ^NxN.设A和B分别表示V的二部划分,即: AÈB=V,AÇB=Æ.令cut(A,B)表示A和B之间的权重之和,即:第i个节点的度定义为,集合的容量(volume)为该集合内所有节点度的总和:集合A和B之间的规范割由下式给出:

.

我们希望找到A和B,使NCut(A,B)最小化.借助谱图理论,Shi和Malik^[14]指出:通过求解归一化拉普拉斯矩阵L的第二小特征值l₂,并对相应的特征向量阈值处理,可以获得该问题的一个近似解.归一化的拉普拉斯矩阵定义为

L=D^-1/2(D-W)D^-1/2=I-D^-1/2WD^-1/2,

其中,D是对角矩阵,其元素D_ii=d_i.不管W如何,矩阵L是半正定的.它的特征值在区间^{[0, 2]}内,所以D^-1/2WD^-1/2的特征值被限制在[-1,1]中.

扩展到多分类问题,可以通过递归二划分或使用多个特征向量来处理^[15].本文采用多个特征向量把每个元素嵌入到一个N_E-维欧氏空间(N_E<<N),以便保留归一化相似性中的显著差异,抑制其中的噪音.然后,使用k-means算法对嵌入空间中的点进行划分.

要找到这样的嵌入空间,需要对D^-1/2WD^-1/2特征分解,计算其特征向量和特征值:

(D^-1/2WD^-1/2)V=VL,

其中,V由特征向量组成,是一个NxN_E的矩阵;L由特征值组成,是N_ExN_E的对角矩阵.第j个点的第i个嵌入坐标为

其中,特征向量已经按特征值的升序排列.

但是,解决这个问题所需的计算量是非常大的.在聚类的过程中,W以元素数二次幂的规模增长,很快就会占满内存空间,更不用说计算其特征向量了.一种解决方法是使用稀疏、近似的W,其中每个元素仅与其附近的少数邻居相连,而其他连接都假定为0^[16].这样就可以采用高效的、用于稀疏矩阵的特征值求解方法(例如Lanczos法),不过该方法的有效性还有待进一步研究.Fowlkes等人^[9]提出的基于Nyström矩阵低秩逼近的解决方案,允许保留所有的相似性值,虽然也会损失一部分精度,但是极大地降低了计算复杂度,在实践中取得了较好效果.

2 Nyström扩展技术

Nyström方法是寻找数值近似的技术,适用于如下特征函数问题:

我们可以在区间[a,b]上选取一组均匀分布的点x₁,x₂,…,x_n,然后用简单的求积公式来逼近该积分方程:

(1)

其中,是真实f(x)的一个近似.

由于公式(1)对任意x都成立,为了求解,可以用抽样点代替x,即:令x=x_i,得到下式:

不失一般性,将[a,b]替换成^{[0, 1]},上述问题等价于矩阵特征值问题:

,

其中,A_ij=W(x_i,x_j);F=[f₁,f₂,…,f_n]是A的n个特征向量,相应的特征值为l₁,l₂,…,l_n.代入到公式(1)中,可以得到每个的Nyström扩展:

(2)

公式(2)可以将一组样本点的特征向量扩展到任意使用W(×,x_j)作为插值权重的点x,尽管x可以是任意真值,我们所关心的是如何处理那些没有被抽到的点.为了便于理解,下面从矩阵补全的角度来分析Nyström扩展的性质.

将所有N个数据点分成两部分,一部分为随机抽样得到的n个样本点,另一部分为剩余的N-n个数据点,则相似矩阵W可以写成:

(3)

其中,AΡ^nxn为抽样点间的相似度矩阵,且A=ULU^T;BΡ^(N-n)xn为抽样点与剩余点的相似度矩阵;CΡ^(N-n)x(N-n)为剩余点间的相似度矩阵.令表示W的近似特征向量,由Nyström扩展可以得到:

相应地,令表示近似的W,则有:

.

可见,Nyström扩展技术使用B^TA^-1B来逼近C.由于n<<N,所以抽样后剩余点的数目通常是很大的,经过Nyström逼近,避免了使用剩余点的相似度,从而极大地降低了问题求解的空间和时间复杂度.但近似特征向量并不能直接使用,因为不一定满足特征向量正交的性质.定理1给出了正交特征向量的表达式.

定理1. 若A是正定的,令A^1/2表示A的对称正定平方根,定义Q=A+A^-1/2BB^TA^-1/2,将其对角化,则的正交特征向量为

(4)

证明:

(1) 首先证明V是的特征向量:

(2) 然后证明V^T和V是正交的:

.

上式右边的两部分分别乘以和,即可得到Q:

要将Nyström逼近用于谱聚类,还必须对相似矩阵(拉普拉斯矩阵)归一化处理,即其中,是对角矩阵,其对角线元素等于第i行元素之和.Fowlkes等人^[9]给出了节点度的一种简便的计算方法:

(5)

其中,m=N-n,a_r,b_rΡ^m分别表示A和B的行和,b_cΡⁿ表示B的列和,1表示元素均为1的列向量.利用就可以将矩阵A和B归一化:

(6)

(7)

3 自适应的Nyström采样方法

Nyström扩展技术不但易于理解和实现,而且已经应用到很多有挑战性的场景中,取得了令人满意的效果. Nyström方法的关键步骤是,从原数据集中选择一定数量的样本点.最常想到的方式是采用随机抽样,但是随机抽样具有不稳定性,而且对于大规模的数据集,很难做到均匀采样,所抽的数据点可能集中在某一局部区域,从而导致较差的聚类结果.

谱聚类的基本思想是:求解相似矩阵的前k个特征向量,将原始数据点映射到由特征向量构成的一个低维子空间中;在这样的近似空间中,数据的结构得到了优化,同一类中的点会更加紧凑,而不同类中的点会更加分离,聚类的结果也会更好.Frieze等人^[17]指出:任何矩阵A都有k/e行,其生成空间可以形成A的一个秩-k近似,附

加的误差在范围内.而所选取行的子集可以作为独立的样本,从A各行范数决定的分布中获得.

定理2. 给定一个mxn的矩阵A,从中选择s行构造矩阵S,每次采样都独立地遵循下面的分布,第i行被选取的概率为

其中,A⁽ⁱ⁾表示A的第i行.如果s≥k/e,矩阵(秩最大为k)的行就包含在span(S)中,且满足:

.

定理2可以转化为高效的采样算法^[18],该算法首先遍历一次A得到样本的概率分布,然后根据每一行的概率进行采样和近似计算,其复杂度是O(min{m,n}k²/e⁴).由此考虑,逼近误差是否可以通过多次遍历数据而显著减少?举例来说,假设数据中除了一个点之外,其余的点都沿着¡ⁿ的一个1维子空间,最好的秩-2子空间应该是零误差的.然而,一轮采样很有可能遗漏远离线的这一点.所以想到用两轮采样的方法:在第1轮,首先从平方范的分布中得到一组样本;然后,重新计算剩余点的抽样概率,每个点被选取的概率正比于其与已有样本生成空间的平方距离,根据概率的大小选择另一组样本,这个过程称为自适应采样.如果孤立点错过了第1次采样,它在第2次采样中被选择的概率就会很高.现在全部样本的生成空间就能形成一个良好的秩-2近似.可以证明:当进行自适应地采样时,附加误差随着遍历次数的增加呈指数下降.因此,多次遍历数据对低秩近似问题是非常有益的.自适应采样的数学描述由定理3给出.

定理3. 令S=S₁È…ÈS_t是对mxn矩阵A的行的随机抽样,其中对于j=1,…,t,每个集合S_j都是A的s行的一个采样,从以下分布中独立地选择:行i被选中的概率为

其中,表示A在S的生成空间上的投影.对于s≥k/e,矩阵(秩最大为k)的行就包含在span(S)中,且满足:

.

从定理3可知,虽然抽样分布改变了t次,矩阵本身没有改变.这样,当A为稀疏矩阵时就显得特别重要.由于保持了矩阵的稀疏性,可以充分利用稀疏性减少计算量,提高程序的运行效率.定理3的证明将在第3.2节给出,在证明前,先回顾矩阵的相关知识.

3.1 预备知识

任意mxn的实矩阵A都可以进行奇异值分解,即矩阵A可以写成下面的形式:

其中,r是A的秩,s₁≥s₂≥…≥s_r≥0称为奇异值;{u⁽¹⁾,…,u^(r)}Ρ^m,{v⁽¹⁾,…,v^(r)}Ρⁿ是正交向量的集合,它们分别称为左奇异向量和右奇异向量,遵循A^Tu⁽ⁱ⁾=s_iv⁽ⁱ⁾和A^Tv⁽ⁱ⁾=s_iu⁽ⁱ⁾,其中,1≤i≤r.

矩阵AΡ^mxn的元素为a_ij,A的Frobenius范数记作||A||_F,由下式给出:

.

对于子空间VÍ¡ⁿ,令p_V,k(A)表示A的最佳的秩-k近似(在Frobenius范数下),V中元素为A的行索引.令:

为A的最佳的秩-k近似.并且p_V(A)=p_V,n(A)是A在V上的正交投影.我们说“A的一组行的集合(或样本)”,意思是一组行的索引,而不是实际的行.对于A的一组行的集合S,令span(S)Í¡ⁿ表示这些行产生的子空间;为描述方便,p_span(S)(A)简记为p_S(A),p_span(S),k(A)简记为p_S,k(A).

对于子空间V,WÍ¡ⁿ,它们的和记作V+W,由下式给出:

V+W={x+yΡⁿ:xÎV,yÎW}.

同时,还会用到操作符p_V的以下基本性质:

(1) p_V是线性的,即p_V(lA+B)=lp_V(A)+p_V(B),对任意lΡ,矩阵A,BΡ^mxn成立;

(2) 如果V,WΡⁿ是正交线性子空间,则p_V+W(A)=p_V(A)+p_W(A),对任意矩阵AΡ^mxn成立.

对于一个随机向量v,其期望记作E(v).E(v)也是一个向量,其中的每个元素都是v中元素的预期值.

3.2 自适应采样的证明

为了便于证明,定义一个中间引理如下.

引理1. 令AΡ^mxn,VÍ¡ⁿ是一个向量子空间.令E=A-p_V(A),S为包含s行的随机抽样,每一行都从A中选取,

选取的概率符合分布D:

(8)

然后,对于任何非负整数k,都有:

.

证明:定义向量w⁽¹⁾,…,w^(k)ÎV+span(S),令W=span{w⁽¹⁾,…,w^(k)},则W可以认为是span{v⁽¹⁾,…,v^(k)}的一个很好的近似,即:

(9)

其中,,span{v⁽¹⁾,…,v^(k)}表示投影的最佳子空间.证明了公式(9)就证明了引理1,因为WÍV+span(S).

为此,定义为一个随机变量,其概率为P_i,使得对于i=1,…,m和l=1,…,s,有:

.

注意到是A中某一行的线性函数,该行从分布D中采样得到.令,则

E_S(X^(j))=E^Tu^(j).

对于1≤j≤k,定义:

w^(j))=p_V(A)^Tu^(j)+X^(j) (10)

然后可以得到E_S(w^(j))=s_jv^(j).下一步要寻找约束w^(j)的二阶中心矩,即E_S(||w^(j)-s_jv^(j)||²).因为

w^(j)-s_jv^(j)=X^(j)-E^Tu^(j),

所以,

(11)

单独分析公式(11)的第1项:

(12)

在公式(12)中,和是相互独立的.由公式(11)和公式(12)可以得到:

(13)

由P_i的定义可知:

(14)

利用公式(13)和公式(14),就获得了w^(j)的二阶中心矩上的一个约束:

(15)

有了这个约束,即可完成证明.令y^(j)=w^(j)/s_j,1≤j≤k,定义矩阵可以用F来约束误差.F的行空间包含在W=span{w⁽¹⁾,…,w^(k)}中,所以.

通过沿左奇异向量u⁽¹⁾,…,u^(r)分解A-F,可以使用不等式(15)来约束,从而证明引理1:

(16)

利用引理1,下面采用归纳法证明定理3.

定理3的证明:假设采样的总次数为t.定理2给出了t=1的基本情况.

令.借助引理1,对于s≥k/e,可以得到:

.

又因为,所以,

(17)

利用在S₁,…,S_t-1上的期望以及t-1次采样的归纳假设,就可以得到定理3的结果:

(18)

当进行t次采样时,所有样本索引的集合为S₁È…ÈS_t=S.由不等式(18)可知:A在span(S)上的二阶中心矩不超过,其中,p_k(A)是A最佳的秩-k近似,是一个定值,是附加的误差.因为0<e<1,所以当采样次数t增大时,附加误差会呈指数下降.定理3说明,采用自适应的抽样方法可以有效减少抽样误差.通过多次遍历采样,使得到的样本点具有更强的代表性,这样,利用少数抽样点就能较好地描述数据的真实结构.在Nyström扩展方法中,使用这些高质量的样本点进行近似计算,得到相似矩阵的特征向量更接近真实的值.

4 基于自适应Nyström采样的谱聚类算法

第3节从理论层面分析了基于概率分布的自适应抽样方法.传统的算法大多从一个固定分布里对数据点进行采样,而自适应采样每次选择一组样本后,都会更新所有样本的概率分布,使最终得到的样本可以产生最佳的秩-k子空间(v⁽¹⁾,…,v^(k)的生成空间)的一个近似.利用该自适应抽样方法对相似矩阵W进行采样,从所有行的初始分布开始,选择s<n行来形成子矩阵R¢;然后,根据先前选择的行更新剩余行被选择的概率,选取概率最大的s个新的行并入R¢.重复此过程,直到已经选择了n行为止.该自适应采样方案详见算法1.

算法1. 自适应Nyström采样算法.

输入:数据点的相似度矩阵WΡ^NxN,总的采样行数n,每次遍历选取的行数s;

输出:W中n个行的索引,即抽得的n个样本.

SAMPLE-ADAPTIVE(W,N,n,s)

Step 1. 初始化抽样点的索引的集合S=Æ,令迭代次数t=n/s.

Step 2. 对于iÎ[1,…,t],重复执行以下步骤:

            (a) P_i¬UPDATE-PROBABILITY(S)

            (b) S_i¬根据P_i选取的s个索引组成的集合

            (c) S¬SÈS_i

Step 3. 返回抽样集合S

UPDATE-PROBABILITY(S)

Step 1. 选出与S中的索引对应的W的行,组成集合R¢.

Step 2. 计算R¢的左奇异向量U_R¢

Step 3. 计算W与它在R¢上的正交投影的误差:

Step 4. 对于jÎ[1,…,n],重复执行以下步骤:

            (a) 如果jÎS,就令P_j=0;

            (b) 否则,令.

Step 5. 更新所有数据点的抽样概率.

Step 6. 返回概率集合P.

通过算法1得到n个样本的索引后,再使用Nyström扩展技术对相似矩阵W进行逼近,得到,最后,采用谱聚类算法将数据点划分成k类.算法流程见算法2.

算法2. 基于自适应Nyström采样的谱聚类算法(ANS-SC).

输入:数据集X={x_i|i=1,…,N},采样的数目n,聚类数目k;

输出:聚类产生的k个簇.

Step 1. 计算X中成对数据点的相似性,构造相似度矩阵WÎR^NxN,其中每个元素w_ij可以用高斯核函数来表示,即:w_ij=exp(-||x_i-x_j||²/2s²).

Step 2. 利用算法1进行采样,得到n个样本的索引集合,然后从W中选出相应的元素,组成抽样点间的相似度矩阵AΡ^nxn,以及抽样点与剩余点的相似度矩阵BΡ^(N-n)xn.

Step 3. 在矩阵A和B的基础上,根据公式(5)计算节点的度,然后根据公式(6)、公式(7)分别对矩阵A和B作归一化处理.

Step 4. 利用归一化的A,B,计算矩阵Q:Q=A+A^-1/2BB^TA^-1/2.

Step 5. 将矩阵Q对角化:,得到矩阵U_Q和Λ_Q.

Step 6. 将U_Q,L_Q代入公式(4),求的正交特征向量V.

Step 7. 从V中选出前k个最大特征值对应的特征向量v₁,…,v_k,形成矩阵V_k:

Step 8. 将矩阵V_k的每一行都规范化成单位向量,得到矩阵Y,其每个元素.矩阵Y形成了一个低维嵌入空间¡^Nxk,其第i行与原始数据集的点x_i对应.

Step 9. 利用k-means算法对矩阵Y的行向量进行聚类,若第i行被分到第j类中,就将原数据点x_i归到第j

类中,这样,将所有数据点划分成k个类簇.

算法1抽样得到的行的索引都保存在集合S中,每次迭代时,在已有采样点的基础上使用一组新的正交向量进行扩展,产生新的样本点S_i.所选取的每一行的残差二范数||E⁽ⁱ⁾||²以及总的,可以通过相似矩阵W减去它在span(S)上的正交投影p_S(W)计算得到.令M表示相似矩阵W中非零点的数目,N表示数据集中数据点的总数,n表示采集的样本点的总数,s表示一次采样选取的样本数目.每次迭代时,在正交向量上投影所需的时间为O(Ms).在第i次迭代中,由于¡^N空间中对s个向量进行Gram-Schmidt正交化时,一个正交基的大小最多为s(i+1),所以计算正交基需要的时间为O(Ns²i).那么,第i次迭代所需的时间为O(Ms+Ns²i);t次迭代,总的时间为O(Mst+Ns²t²).又因为t=n/s,所以算法1的时间复杂度为O(Mn+Nn²).

算法2中输入的数据集一共包含N个数据点,Step 1利用高斯核函数计算这N个数据点的相似性值,构造相似矩阵,时间复杂度为O(N²);Step 2通过算法1采样,得到n个样本的索引,组成矩阵A和矩阵B,时间复杂度为O(Mn+Nn²);Step 3根据公式(5)计算节点度所需的时间为O(n(N-n)),归一化矩阵A和B需要的时间分别为O(n²)和O(n(N-n)),因为n<<N-n,所以Step 3的时间复杂度为O(n(N-n));Step 4~Step 6利用Nyström扩展技术求解近似的正交特征向量,时间复杂度为O(n³);Step 7寻找前k个特征向量,构造矩阵V_k需要的时间为O(k);Step 8对V_k归一化的时间复杂度为O(kN);Step 9使用k-means算法聚类的时间复杂度为O(kNt),其中,t是迭代的次数.因此,算法2的时间复杂度为O(N²)+O(Mn+Nn²)+O(kNt).

5 实验分析

为了对本文提出的ANS-SC算法的有效性进行验证,从UCI机器学习数据库中选取了7个不同大小的数据集,它们的数据特征见表 1.

对于USCI(US Census Income)数据集,我们去除了包含缺失数据的实例和属性,剩下一共285 779个数据点,含有37个属性.Poker Hand数据集非常不均匀,所以我们把小的类聚到一起,而大的类保持不动.这样,最终得到3个类,其数据点的数目分别占总实例数的50.12%,42.25%和7.63%.同时,我们对Connect-4和USCI数据集做了归一化处理,使得所有属性的平均值为0,而标准差为1.为了确定谱聚类中高斯核参数s的值,本文采用了交叉验证的方法,搜索范围是^{[0, 200]},搜索步长设为0.1.

实验中,评估聚类性能的指标主要有两个:算法运行时间和聚类准确率.聚类准确率关心的是聚类算法得到的类标签是否正确,需要统计数据集中每个实例的类归属与真实的类标签相符的比例.经过聚类,类的序号往往会重新排列,为了找到聚类结果与原数据集中类划分的对应关系,令z={1,…,k}表示类标签的集合,q(×)表示真实的类标签,f(×)表示聚类算法赋予每个数据点的类标签,那么聚类准确率b可以定义为

(19)

其中,I是指示函数,P_z是z上所有排列的集合.

使用表 1中的数据集,我们将ANS-SC算法与另外3种基于不同采样技术的谱聚类算法进行了对比,分别是基于随机抽样的谱聚类算法(RS-SC)^[9]、基于加权抽样的谱聚类算法(WS-SC)^[19]、基于方差增量抽样的谱聚类算法(IS-SC)^[20].实验的计算机环境为:处理器Pentium(R) Dual-Core E5300 2.60GHz,操作系统Windows 8,编程环境MATLAB 2013a.为了客观地对比算法的各项聚类指标,实验中分别将上述4种算法执行20次,计算其平均聚类准确率和聚类时间.在不同的采样比例下,4种算法在UCI数据集上的聚类准确率以及它们在置信水平为0.05下的配对t检验的比较结果见表 2.

表 2中的P-value表示在0.05的置信水平下,配对t检验计算出的P值.当P值<0.05时,说明该算法的聚类准确率与ANS-SC算法有显著差异;当P值>0.05时,说明该算法的聚类准确率与ANS-SC算法的差异不显著.从表 2中可以看出:随着采集的样本数的增多,各种算法的聚类准确率也不断提高.RS-SC算法由于采用随机抽样,其聚类性能不太稳定,波动较大,而且聚类准确率也比较低.WS-SC算法利用了未抽样点的信息,通过最小化舒尔补来降低逼近误差,其聚类表现优于RS-SC算法.但是对于大多数数据集,WS-SC算法的聚类效果不如IS-SC算法和ANS-SC算法.IS-SC算法根据特征向量的可聚性,分析舒尔补中相邻数据点之间的关系,然后利用基于方差的启发式策略进行增量抽样,得到所有样本点.在ImageSeg,Musk,penDigits,mGamma数据集上,多数情况下,IS-SC算法的P值>0.05,其聚类准确率与ANS-SC算法很接近,说明当数据集规模较小时,ANS-SC算法的聚类表现与IS-SC算法差不多.但是在处理大规模的数据集,如Connect-4,USCI,Poker Hand时,IS-SC算法的P值<0.05,其聚类准确率明显不如ANS-SC算法,说明ANS-SC算法的聚类性能更好.可见,ANS-SC算法使用自适应的采样方法,能够根据数据集自身的结构特征找到更具代表性的样本,使得Nyström逼近得到的特征向量更接近真实的特征空间,从而提高聚类的准确率.这4种算法在不同数据集上聚类所花费的时间见表 3.

由表 3可知:样本点的数目越多,算法聚类所需要的时间也越长.基于随机抽样的RS-SC算法在各个数据集上运行的时间都是最少的,因为另外3种算法使用改进的抽样策略,需要花费额外的时间寻找合适的样本点.其中,WS-SC算法耗时最长,主要由于它在每一次采样迭代时,都需要计算一个n阶矩阵的行列式,算法复杂度较高.当采样比例为5%时,ANS-SC算法的运行时间与IS-SC算法差不多.但是当采样比例增加到10%和20%时, ANS-SC算法在几个数据集上聚类的时间都长于IS-SC算法,说明自适应Nyström采样方法所需的计算量还是比较大的.如何有效降低其时间复杂度,今后需要进一步研究.

6 结束语

Nyström矩阵低秩逼近方法可以求解近似的特征向量和特征空间,是处理大数据的一个有力工具.在谱聚类中,利用Nyström扩展技术进行近似计算,可以在很大程度上降低时间和空间的开销,以较小的精度损失换取算法效率的大幅提升.使用Nyström方法时,抽样策略的选择会对聚类结果的优劣产生重要影响.为了使所选取的少数样本点更好地反映数据集的分布情况,设计了一种自适应的采样方法用于Nyström扩展技术.该方法通过多次遍历,根据不同的概率进行采样,每次采样只选择一部分样本点,并更新剩余点的采样概率.如此迭代循环,直到已经选择了足够的样本点为止.本文从理论上证明了采样次数的增加可以有效降低抽样误差.接着,提出一种基于自适应Nyström采样的谱聚类算法.在UCI机器学习数据库上的实验表明:该算法的聚类效果优于基于随机抽样的谱聚类算法,基于加权抽样的谱聚类算法以及基于方差增量抽样的谱聚类算法,能够较好地处理大规模的数据集.

致谢 在此,我们向对本文的工作给予支持和建议的同行表示感谢.