0 引言

聚类集成具有传统聚类算法无可比拟的优势, 其关键问题在于如何将聚类成员组合为更加优越的聚类结果^[1].解决聚类集成问题最常见的方法是引入超图的邻接矩阵H表示对象之间的两两关系, 避免簇标签对应问题.根据处理的矩阵可以分为对H进行处理的方法^[1-3]和对相似度矩阵S进行处理的方法^{[1, 4-10]}.对H进行处理的方法虽然利用了簇标签提供的属性信息, 但忽略了对象之间的关系; 对H进行处理的方法揭示了对象之间的关系, 但未能有效利用簇标签提供的属性信息.

本文引入二部图模型^[11]解决聚类集成问题, 使用二部图同时建模对象集和超边集, 充分挖掘潜藏在对象之间的相似度信息和超边/簇提供的属性信息.通过正则化谱聚类算法解决二部图划分问题, 得到对象的低维嵌入, 在低维空间使用K-means++ (KM++)^[12]算法划分对象集, 从而获得最终的聚类结果.在多组基准数据集上的实验结果验证了所提出算法的有效性.

1 聚类集成相关研究

聚类集成主要研究以下两个问题: 1)聚类成员生成问题, 即如何生成具有差异性的聚类成员; 2)共识函数设计问题/聚类集成问题, 即如何将聚类成员集成/组合为更加优越的聚类结果.

由于采用随机初始化的K均值算法(K-means, KM)每次运行会得到不同的聚类结果, 可多次运行KM获得聚类成员.该方法因为简单高效而成为产生聚类成员最常见的方法^{[1, 10]}.

组对法是解决共识函数设计问题的主要方法, 其关键思想在于引入超图的邻接矩阵H表示对象之间的两两关系, 有效避免簇标签对应问题.由处理的矩阵可分为: 1)对H进行处理, 包括HGPA(Hypergraph partitioning algorithm)^[1]、MCLA(Meta-clustering algorithm)^[1]、基于矩阵低秩近似的算法^[2]、基于KM的算法^[3]等; 2)对相似度矩阵S进行处理, 包括CSPA (Cluster-based similarity partitioning algorithm)^[1]、基于证据积累(Evidence accumulation, EA)的层次聚类方法^[4-5]、谱聚类方法^[6]、链接法^[7]、基于近邻传播的方法^[8]、基于密度峰值的方法^[9]、加权共现矩阵方法^[10]等.

2 本文方法 2.1 基于二部图模型的聚类集成方法

设数据集D={d₁, d₂, …, d_n}, 由r个聚类成员构成的集合P={P⁽¹⁾, …, P^(r)}, 超图的邻接矩阵H=H^{(1, 2, …, r)}=(H⁽¹⁾, …, H^(r)).假设每个聚类成员均包含k个簇, 则超图包含n个顶点, t=rk条超边(每条超边对应于一个簇), 即H的大小为n× t.

文献[11]引入二部图模型同时聚类文本和词, 其关键思想在于词和文本聚类的双重性(duality), 即词簇能导出文本簇, 文本簇能导出词簇.本文引入该思想, 同时聚类对象和超边, 原因在于对象和超边聚类也满足双重性, 即对象簇能够导出超边簇, 超边簇也能够导出对象簇.下面举例说明本文方法的关键思想, 最终结果也验证了对象和超边聚类满足双重性.

例1  假设对象集D={d₁, d₂, d₃, d₄, d₅}, 3个聚类成员(cluster member, CM)提供的聚类标签构成集合P={P⁽¹⁾, P⁽²⁾, P⁽³⁾}.其中: CM₁提供的标签为P⁽¹⁾={1, 1, 1, 2, 2}^T, 包含2个簇C₁={d₁, d₂, d₃}和C₂{d₄, d₅}, 对应的超边分别为h₁=(1, 1, 1, 0, 0)^T和h₂=(0, 0, 0, 1, 1)^T; CM₂提供的标签为P⁽²⁾={2, 2, 2, 1, 1}^T, 包含2个簇C₃={d₁, d₂, d₃}和C₄={d₄, d₅}, 对应的超边分别为h₃=(1, 1, 1, 0, 0)^T和h₄=(0, 0, 0, 1, 1)^T; CM₃提供的标签为P⁽³⁾={1, 1, 2, 2, 2}^T, 包含2个簇C₅={d₁, d₂}和C₆={d₃, d₄, d₅}, 对应的超边分别为h₅=(1, 1, 0, 0, 0)^T和h₆=(0, 0, 1, 1, 1)^T. 3个聚类成员对应的超图的邻接矩阵分别为

图 1给出了基于二部图模型的聚类集成方法.图中圆点表示对象, 包含多个圆点的虚线表示簇/超边. 图 1(a) ~ 图 1(c)分别为3个聚类成员提供的聚类结果, 图 1(d)为对象集(对象用圆点表示)和簇集(簇用菱形表示)所构建的二部图模型.对象与对象之间没有边, 簇与簇之间没有边, 只有当某个簇包含某个对象时, 对应的簇与对象之间有边.

图 1(d)中的虚线表示对二部图的一个划分, 同时划分了对象集和簇集.要获得最终的聚类结果, 有以下两种方案: 1)直接取顶点集的划分结果{{d₁, d₂, d₃}, {d₄, d₅}}; 2)参照MCLA^[1]间接获得顶点集的划分结果.具体地, 首先获得对簇集的划分结果{{C₁, C₃, C₅}, {C₂, C₄, C₆}}, 其中{C₁, C₃, C₅}和{C₂, C₄, C₆}称为元簇(meta-cluster); 然后将每个元簇中的所有超边断裂并合并为一条元超边(meta-hyperedge), 用一个包含每个对象与该元超边关联程度的向量进行表示, 关联程度等于元簇中包含的所有超边向量的平均值, 元簇{C₁, C₃, C₅}对应的元超边{d₁, d₂, d₃}, 其关联向量为(1, 1, 2/3, 0, 0)^T, 元簇{C₂, C₄, C₆}对应的元超边{d₃, d₄, d₅}, 其关联向量为(0, 0, 1/3, 1, 1)^T; 最后每个元簇根据关联向量竞争每个对象, 每个对象被分到具有最高关联向量值的元簇中.例如, 在竞争对象d₃时, 元簇{C₁, C₃, C₅}以2/3＞1/3的优势赢了元簇{C₂, C₄, C₆}, 因此, 最终得到的两个对象簇为{d₁, d₂, d₃}和{d₄, d₅}, 该结果与采用第1种方案得到的结果一致.

2.2 二部图谱划分算法设计

根据二部图模型, 同时建模对象集D和超边集W, 得到拉普拉斯矩阵, 其中D_W和D_D为对角矩阵, 对角元素分别为

下面将正则化拉普拉斯矩阵D^-1L的特征值分解(Eigenvalue decomposition, EVD)问题转换为规模较小的矩阵EVD问题.

定理1  设

则D^-1L的前l个最小特征向量可通过求解t阶方阵H_n^TH_n的前l个最大特征值及对应的特征向量获得.

证明  考虑广义特征值分解问题Lz=λDz, 设, 则有

展开得

因为D_W、D_D为非奇异矩阵, 分别将上面两式左乘D_W^-1/2和D_D^-1/2, 得到

设u=D_W^1/2w, v=D_D^1/2d, 经过整理得

设σ =1-λ, 则H_nv=σu, H_n^Tu=σv.可见, u、v分别为H_n的左、右奇异向量, σ为相应的奇异值.因此, D^-1L的前l个最小特征向量可以通过求解H_n的前l个最大奇异值对应的左、右奇异值向量获得.

设rank(H_n)=p≤ n, 其奇异值分解(Singular value decomposition, SVD)定义为H_n = UΣV^T.其中: U、V分别为n阶和t阶酉矩阵, U^TU=I_n, V^TV = I_t; Σ ∈ R^{n× t}为对角阵, 且对角元素σ_i为H_n的奇异值, 1≤ i≤ n, 当1≤ i≤ p时, σ_i>0, 当i≥ p+1时, σ_i=0.易得H_n^T=VΣU^T, H_n^TH_n=VΣ²V^T.可见, H_n的奇异值等于H_n^TH_n的特征值的非负平方根, 对应的右奇异向量等于H_n^TH_n的非零特征值对应的特征向量.另外, 将H_n的SVD两边同时右乘VΣ^†, 其中Σ^†为Σ的广义逆, 得到U=H_nVΣ^†.设H_n^TH_n的特征值及对应的特征向量为δ_i和q_i, 有

因此, H_n的前l个最大奇异值对应的左、右奇异向量可通过求解t阶方阵H_n^TH_n的前l个最大特征值δ_i对应的特征向量q_i得到.

设Λ_l =diag(δ₁^-1/2 … δ_l^-1/2), Q_l=[q₁, q₂, …, q_l], D^-1L的前l个最大特征向量构成的矩阵为

即D^-1L前l个最小特征向量可通过求解t阶方阵H_n^TH_n前l个最大特征值及对应的特征向量获得.

在获得对象与超边的低维表示Z后, 考虑到Z的第1 ~ n行对应于对象集, 第n+1 ~ n+t行对应于超边集, 因此可以采用KM算法对Z的第1 ~ n行聚类, 直接获得最终的聚类结果. KM采用K个均值向量表示数据集, 其目标函数为最小化误差平方和(Sum of squared errors, SSE), 有

其中: 为簇C_k的质心向量, n_k为簇C_k包含的对象个数, 为常量.

不失一般性, 假设对象按照其所在的簇进行排序, 上述最小化SSE问题的解可以表示为K个指示向量构成的矩阵

其中

此时上述最小化问题变为J=Tr(Z^TZ)-Tr(F^TZ^TZF), 其中Tr(·)表示矩阵的求迹运算.设组对相似度矩阵为P=Z^TZ, 上述问题转换为迹最大化问题

KM算法简单高效, 但聚类结果受初始聚类中心(seeds)影响较大, 易收敛到较差的局部最优解.为了提高聚类质量, 引入KM++^[12]算法, 运行KM++多次, 取最优值作为最终的聚类结果. KM++的关键之处在于选择远离的数据点作为seeds, 克服了KM算法随机选择seeds的盲目性.具体地, 首先随机选择1个数据点作为第1个seed, 然后逐步选择新的数据点作为新的seed, 选择新seed的原则是, 离已有seeds越远的点被选为新seed的概率越大, 重复上述过程, 直到选出K个seeds.

将本文的聚类集成方法称为二部图谱划分(Bipartite spectral graph partitioning, BSGP), 算法主要步骤描述如下.

Input:对象集D={d₁, d₂, …, d_n} ∈ R^{n× m}, n为对象个数, m为特征个数, 簇个数为K, 聚类成员个数为r.

Step 1:运行随机选取初始质心的KM算法r次, 每次得到K个簇, 生成r个聚类成员.

Step 2:构建超图的邻接矩阵H, 计算H_n, 求解t阶方阵H_n^TH_n的EVD, 求解Z.

Step 3:设z_i ∈R^l为对应于Z的第i行(1≤ i≤ n)的列向量, 使用KM++算法将Z={z_i|i=1, 2, …, n}划分为K个簇C₁, C₂, …, C_K.

Output:聚类结果π={D₁, D₂, …, D_K}, 其中D_k={d_i|z_i ∈ C_k}, k=1, 2, …, K.

Step 1时间复杂度为O(tmn), Step 2时间复杂度为O(t²n²+t³), 其中t阶方阵的求解可通过高效的矩阵乘法获得, Step 3时间复杂度为O(Kln).通常t≤ n, 因此, 本文方法的计算复杂度较低.在下文的实验部分进一步证实了本文算法具有较高的运行效率.

3 实验分析

实验平台为: Intel Xeon E5-1650六核处理器, 频率3.50 GHz, 内存16.00 GB, 程序在Matlab2016b下运行, 操作系统为Windows 10专业版.

3.1 实验数据集与评价指标

实验使用由TREC(http://trec.nist.gov)提供的10组基准文本数据集, 见表 1.数据集tr11、tr23、tr41和tr45中的文本类别对应于某个特殊类别的查询.数据集la1、la2和la12由洛杉矶时报上的文章构成, 包含6类文章.数据集hitech, reviews和sports取自San Jose Mercury报纸, hitech包含关于计算机、电子、健康、医疗、研究和科技方面的文章, reviews包含关于食物、电影、音乐、广播和饭店方面的文章, sports包含关于棒球、篮球、自行车、拳击、足球、高尔夫、曲棍球的文章.所有数据集中的文本类别标签唯一.

本文采用机器学习领域比较流行的规范化互信息(Normalized mutual information, NMI)^[1]衡量聚类结果和已知类别标签的匹配程度.当两个类别标签一一对应时, NMI值达到最大值1.另外, 本文采用在信息检索领域常用的评价文本聚类质量的综合指标F值(F-measure). F值越大, 聚类质量越高, 反之聚类质量越低.

3.2 实验结果与分析

将本文的BSGP与主流聚类集成方法进行对比, 对比算法为文献[1]提出的CSPA、HGPA、MCLA和文献[5]提出的基于EA思想的4个层次聚类算法(单连接(Single linkage, SL)、全连接(Complete linkage, CL)、组平均(Average linkage, AL)和Ward, 分别记为EASL、EACL、EAAL、EAWL).

本文首先对经过预处理的文本数据集进行TF-IDF(Term frequency-inverse document frequency)加权, 然后运行使用余弦相似度的KM算法100次, 每次生成K个簇(K等于真实类别个数), 生成100个聚类成员, 运行不同的聚类集成方法.需要指出的是, 对于其他领域的数据集, 需要采用不同的预处理方式和相似度函数才能获得有效的聚类成员, 并进行聚类集成. CSPA和MCLA调用了图划分算法METIS, 不平衡因子UB取默认值0.05, 得到稳定的聚类结果. HGPA调用了HMETIS算法, 不平衡因子UB取默认值0.05, 因为HMETIS得到局部最优解, 所以HGPA获得的聚类结果不够稳定, 本文运行10次取最佳值.凝聚层次聚类方法递归地合并对象, 将数据集划分为嵌套的层次结构, 获得了稳定的聚类结果. BSGP算法运行KM++算法10次取最优结果.

图 2和图 3分别为不同聚类集成算法获得的NMI值和F值, 柱状图依次为CSPA、HGPA、MCLA、EASL、EACL、EAAL、EAWL、BGSP.由图 2和图 3可见: 1) BSGP在tr23、tr41、la12、reviews和sports上获得了最高的NMI值, 在tr41、la12、reviews和sports上获得了最高的F值. 2) BSGP在10组数据集上获得的平均NMI值和F值高于其他算法, 总体来看, BSGP在多数情况下获得了最佳聚类效果, 且平均聚类质量最高. 3)实验采用了两种常用的评价指标, 结果显示获得高NMI值的算法通常也可以获得高F值, 反之亦然, 但是也有例外情况发生, 例如BSGP在tr23上获得了最高的NMI值, 而CSPA却获得了最高的F值.该现象反映了聚类结果评价的困难性, 而其根本原因在于聚类分析是不适定问题.

在面向海量数据挖掘时, 聚类集成算法运行效率是衡量算法优劣的重要指标, 考虑到HGPA、MCLA和EASL聚类质量较差, 本文仅比较CSPA、EACL、EAAL、EAWL和BGSP的运行时间.将数据集依据其大小(显示在数据集下方)递增排列, 5个聚类集成算法在聚类集成阶段的运行时间如图 4所示.由图 4可见, 不同聚类集成算法的运行时间满足BGSP < CSPA < EACL ≈ EAAL < EAWL, 即BGSP效率最高, CSPA次之, 层次聚类算法效率最低.特别地, 在规模最大的数据集sports上(大小为8 580), BGSP的运行时间不超过10 s, 而层次聚类算法的运行时间则超过130 s.显然, 当进行海量数据挖掘时, 层次聚类算法高昂的计算成本让人难以接受, 而BGSP较高的运行效率则使其易于扩展到大规模应用领域.

4 结论

本文将二部图模型引入聚类集成问题中, 使用二部图模型同时建模对象集和超边集, 并设计正则化谱聚类算法解决二部图划分问题, 提出了BGSP算法.在10组基准数据集上进行的实验结果表明, 与主流的聚类集成算法相比, BGSP不仅能获得更加优越的结果, 而且具有较高的运行效率.