-
摘要: 现有的图聚类方法主要存在两方面的问题, 一是对各个类规模一致的假设, 在许多实际应用中并不成立; 二是在处理多类聚类问题时, 其所常借助的递归技术或启发式算法会影响聚类的性能. 为此, 本文提出一种基于灵活平衡约束的多类图聚类方法. 其能够覆盖从绝对平衡约束到无平衡约束的范围, 可同时处理类别规模一致和不一致的问题. 为有效求解新方法中的参数, 进一步提出一个紧松弛方法来使所提出的图聚类方法不仅易于求解, 且在处理多类聚类问题时不必依赖递归技术, 而能直接得到聚类结果. 另外, 本文还给出一种实现松弛图聚类的有效求解算法. 在合成数据和真实数据上的实验结果表明, 所提出的方法具有良好的性能.Abstract: The existing graph clustering methods suffer from two main problems: first, they assume that the size of each class is the same, which is not applicable in many practical applications; second, when dealing with multi-class clustering problems, the recursive technique or heuristic algorithm that is commonly used can affect the clustering performance. To address these issues, this paper proposes a multi-class graph clustering method based on flexible balance constraints. It can cover a range from absolute balance constraints to no balance constraints and can handle both uniform and non-uniform class size problems simultaneously. To effectively solve the parameters in the new method, a tight relaxation method is further proposed to make the proposed graph clustering method not only easy to solve but also able to obtain clustering results directly without relying on recursive techniques when dealing with multi-class clustering problems. In addition, this paper also presents an effective algorithm for implementing the relaxed graph clustering. Experimental results on both synthetic and real data demonstrate that the proposed method has good performance.
-
Key words:
- Graph clustering /
- graph cut /
- balanced constraint /
- tight relaxation
-
聚类是数据挖掘领域中应用最广泛的技术之一. 多年来, 研究人员提出了许多不同的聚类算法, 例如K均值聚类[1]、谱聚类[2-3]、非负矩阵分解[4]和子空间聚类[5-6]. 其中, 谱聚类是一种颇为流行的聚类方法. 它求解简单、聚类性能好, 更重要的是, 可以看作是对图聚类(图划分、图切割)的一种松弛[2], 因而具有很强的理论支撑.
在图聚类方法中, 通常将一个两类(多类)聚类问题转换为一个两路(多路)图分割问题. 图分割问题主要研究如何根据一定的条件, 将图中的顶点划分成两个或多个点集群. 其处理的数据类型是图数据, 图中的每一个顶点表示一个需要进行聚类的样本点, 每一条边则表示顶点与顶点间的依赖关系. 而对于非图数据, 可先根据点与点间的相似性来构造一个邻域图, 然后再运用图聚类方法进行处理. 构造邻域图的方法有很多, 比如
$ \gamma \text{-}$ 邻域图和$ K $ 近邻图[2].现有的图分割方法大都遵循最小切割(Minimun cut, mincut)准则[7], 即要求不同集群之间的边权值之和最小. 此外, 为了避免产生非常不平衡的集群分布, 例如将单独一个顶点划分成一个集群, 这些方法还都使用平衡函数对mincut准则进行正则化. 目前, 比例割(Ratio cut, RCut)模型[8]和归一化割(Normalized cut, NCut)模型[9]是两种既简单又直接的图分割方法. 它们的不同之处在于使用了不同的平衡函数, RCut的平衡函数约束各集群的规模, 而NCut的平衡函数约束各集群内部的紧密程度.
在图聚类方法中, 平衡函数的选择是任务依赖的. 在一些实际应用中, 任务要求各集群的规模必须是平衡或近似平衡的. 如在科学计算中, 每个顶点代表一部分需要被计算的信息, 每条边表示这些信息间的依赖关系. 对信息进行平衡的划分, 可使计算网络中的每台机器都进行同等规模的计算, 从而确保并行计算的高效性. 然而, RCut和NCut方法并不能很好地处理这类需要进行平衡聚类的任务. 为此, 文献[10]提出了Cheeger比例割(Ratio Cheeger cut, RCC)方法和Cheeger归一化割(Normalized Cheeger cut, NCC)方法, 来对不平衡的图分割施加更强的惩罚, 从而得到更平衡的集群[11-12]. 此外, 还可以使用一些平衡函数, 如截断函数和硬平衡函数, 来达到施加不同级别平衡约束的目的[13]. 而在其他一些应用中, 例如图像分割, 其存在着分布不均衡的集群, 采用RCut和NCut方法反而会导致施加的平衡约束太强. 为此, 文献[14]提出了一组平衡函数, 它们由一个参数
$ p $ ($ p>1 $ )取不同的值来得到. 通过选择$ p>2 $ 的一些平衡函数, 可以对不同集群实施强度弱于RCut/NCut$( p = 2 )$ 的平衡约束. 文献[15]提出了一组平衡约束更弱的函数, 它们由参数$ \tau $ ($ 0< \tau<2 $ )取不同的值来得到, 可以覆盖从无平衡约束的mincut准则到RCut/NCut准则的平衡约束.平衡函数约束的图切割方法通常会导致非确定性多项式(Nondeterministic polynomially, NP)难题. 在实际应用中, 需要先对这样的优化问题进行松弛, 即在连续空间中对原始离散优化问题进行重新表述, 以得到一个方便求解且与原问题相近的新问题. 它们的近似程度也反映了所使用的松弛方法的松紧程度. 文献[2]证明了对RCut模型的松弛可以得到基于未归一化图拉普拉斯算子的谱聚类方法, 对NCut模型的松弛会得到基于归一化图拉普拉斯算子的谱聚类方法. 尽管如此, 文献[14]指出, 通过谱聚类方法求得的解并不能保证也是原始图切割问题的最优解. 一般来说, 使用太松的松弛方法得到的近似解和原始问题的解会存在很大的差异. 如何减小近似解与最优解间的差距, 一直是松弛方法研究中的主要问题. 文献[14]研究了Cheeger cut模型与图
$ p $ -Laplacian之间的关系. 通过选择参数$ p = 1 $ , 可以实现对Cheeger cut模型的紧松弛[16]. 之后, 文献[13]将这一结果推广到不同平衡约束的图切割问题中, 得到了各自的紧松弛模型. 此外, 文献[17]提出了利用$ \ell_1 $ 范数作为距离度量的方法, 分别实现了对RCut和NCut模型的紧松弛. 然而, 这些工作的初衷都只是解决两路图分割问题, 要处理多路图分割问题, 只能依赖于贪婪递归技术. 需要注意的是, 通过递归技术的多路扩展往往不能得到理想的多类聚类, 且会带来较大的计算复杂度. 为此, 文献[11]和文献[12]都将两路问题中的Cheeger cut模型扩展到了多路问题中, 两者的区别在于文献[11]使用的平衡函数是非对称的, 而文献[12]中是对称的, 这使得它们对各集群的大小所施加的约束不同. 文献[18]提出了一个一般化的求解多路图分割问题的方法, 可以用来求解包括RCut、RCC和非对称RCC (Asymmetric RCC, ARCC)问题, 以及它们各自对应的规范化图分割问题. 文献[19]提出将$ \ell_{2,1} $ -范数用于距离测量和归一化项, 把文献[17]中的一维谱嵌入扩展到多维谱嵌入, 从而实现了多类聚类.受文献[14-15]的启发, 本文提出了一种新的灵活平衡多路图分割(Flexible multi-way graph cut, FMC)模型. 首先, 针对两路图分割问题, 设计了一系列的平衡函数, 并且证明了传统的图分割方法是 FMC的特例. 接着进一步将两路图切割模型推广到了多分类的场景. 在文献[11]的基础上, 提出一种非对称的平衡约束模型. 与文献[15]相同, 其可通过选择合适的模型参数, 来使得所施加的平衡约束弱于 RCut和NCut方法. 与文献[15]不同的是, 所提出的模型还可以选择特定的模型参数, 来使得所施加的平衡约束强于RCC和NCC. 因此, 本文的模型具有更广泛的应用范围. 最后, 针对模型实现时的NP难题, 提出了一个紧的松弛方法, 并开发相应的算法来解决由此产生的最小化问题. 通过求解该松弛模型, 可以直接得到多分类结果, 而不需要利用递归技术对两路模型进行扩展. 尽管本文的算法基于文献[18]中的工作, 但与[18]不同, 后者只能解决平衡函数为凹函数的松弛问题, 而本文的算法既可以解决凹函数的松弛问题, 也可以解决非凹函数的松弛问题. 为了验证FMC的有效性, 在合成数据集和真实数据集上进行了大量的实验. 结果表明, 所提出的优化算法在求解多路图切割问题方面优于其他对比方法. 而且在聚类性能方面, 与几种基于图分割的聚类方法和其他类型的聚类方法相比, 本文的方法也具有竞争力.
1. 图分割模型概述
给定一个无向加权图
$ G = (V,E) $ , 其中,$V = \{v_1,\cdots,v_n\}$ 表示图$ G $ 中所有顶点的集合,$ E $ 表示边的集合. 多路图分割是指将图$ G $ 的顶点集合划分成多个非空子集$\{A_1,\cdots,A_c\}$ $ (c\geq2) $ 的过程, 且这些子集须满足$ A_i\cap{A_j} = \emptyset $ 和$ A_1\cup\cdots\cup{A_c} = V $ . 采用最小切割准则构造的多路图分割模型为$$ cut(A_1,\cdots,A_c) = \sum\limits_{k = 1}^{c}\sum\limits_{i\in{A}_k,j\in{\overline{A}_k}}s_{ij} $$ (1) 其中,
$ \overline{A}_k = V\setminus{A_k} $ 表示集合$ A_k $ 的补集, 矩阵${\boldsymbol{S}} = [s_{ij}]\in{{\bf{R}}}^{|V|\times{|V|}}$ 表示图$ G $ 的加权邻接矩阵.考虑到模型(1)往往会将单独的一个顶点划分成一个子集, 于是文献[8]在最小切割准则的基础上, 提出了一种基于平衡约束的多路图分割模型. 其利用平衡约束来惩罚子集不均衡的图分割方案, 实现方法是最小化如下目标函数
$$ RCut(A_1,\cdots,A_c) = \sum\limits_{k = 1}^{c}\frac{cut(A_k,\overline{A}_k)}{|A_k|} $$ (2) 类似地, 文献[9]定义了另一个平衡约束, 最小化的目标函数为
$$ NCut(A_1,\cdots,A_c) = \sum\limits_{k = 1}^{c}\frac{cut(A_k,\overline{A}_k)}{vol(A_k)} $$ (3) 其中,
$vol(A_k) = \sum\nolimits_{i\in{A_k}}d_{ii}$ 表示集合$ A_k $ 中包含边的总权重, 且$d_{ii} = \sum\nolimits_j{s_{ij}}$ . 与函数$ |A| $ 相似,$ vol(A) $ 也可以用来刻画集合$ A $ 的“大小”. 但$ vol(A) $ 还度量了集合$ A $ 内部各顶点之间连接的紧密性.此外, 文献[10-12]还提出了其他基于平衡约束的图分割模型, 其目标函数可以统一写成如下形式:
$$ RCC(A_1,\cdots,A_c) = \sum\limits_{k = 1}^{c}\frac{cut(A_k,\overline{A}_k)}{\min\{\lambda{|A_k|},|\overline{A}_k|\}} $$ (4) $$ NCC(A_1,\cdots,A_c) = \sum\limits_{k = 1}^{c}\frac{cut(A_k,\overline{A}_k)}{\min\{\lambda{vol(A_k)},vol(\overline{A}_k)\}} $$ (5) 其中, 文献[12]中参数
$ \lambda = 1 $ ; 文献[11]中参数$ \lambda = c- 1 $ . 很显然, 对两类聚类任务($ c = 2 $ ), 它们是等价的. 对多类聚类任务($ c>2 $ ), 当$ \lambda = 1 $ 时, 其聚类结果中, 每个类别的规模约占总规模的一半. 而当$ \lambda = c-1 $ 时, 每个类别的规模大致相等. 此外, 与$ RCut $ 和$ NCut $ 相比,$ RCC $ 和$ NCC $ 所施加的平衡约束更严格[14].为了表述方便, 本文在后续描述中, 将刻画集合规模的函数
$ |A| $ 和$ vol(A) $ 统一写成$ \rho(A) $ , 它们分别对应着Ratio (R)形式和Normalized (N)形式的平衡图分割模型.2. 基于灵活平衡约束的图分割模型
2.1 两路图分割模型
对现有两路图分割模型的研究发现, 它们都可以归纳为如下的最小化问题:
$$ \min\limits_{\{A,\overline{A}\}}\frac{cut(A,\overline{A})}{\widehat{W}(A)} $$ (6) 其中,
$ \widehat{W}(A) $ 表示不同的平衡函数. 当函数$\widehat{W}(A) = \rho(A)\rho(\overline{A})$ 时, 就得到了图分割模型$ RCut/ NCut $ . 当$ \widehat{W}(A) = \min\{\rho(A),\rho(\overline{A})\} $ , 就得到了图分割模型$ RCC/ NCC $ .文献[14]在现有平衡约束模型的基础上, 提出了一个包含无穷多个平衡函数的图切割模型, 其中用到的平衡函数族可以写为
$$ \Phi_p(v) = \dfrac{2^p}{\left(\left(\dfrac{1}{v}\right)^{\tfrac{1}{p-1}}+\left(\dfrac{1}{1-v}\right)^{\tfrac{1}{p-1}}\right)^{p-1}} $$ (7) 其中,
$ v = \rho(A)/\rho(V) $ . 通过选择不同的参数$ p $ $ (p>1) $ , 可以得到不同的平衡函数. 当$ p = 2 $ 时, 可以得到模型$ RCut /NCut $ 的平衡函数; 当$ p\rightarrow{1}^+ $ 时, 就得到了模型$ RCC/NCC $ 的平衡函数. 另外, 当$ p\rightarrow\infty $ 时, 平衡函数的极限$ \lim_{p\rightarrow\infty}\Phi_p(v) = \sqrt{\Phi_2(v)} $ . 平衡函数族(7)的示意图如图1所示.
从图1可以看到, 函数族
$ \Phi_p(v) $ 所覆盖的范围是深灰色和浅灰色区域. 在优化其对应的图分割模型时, 会找到$ \Phi_p(v) $ 取值最大的位置. 当$ p\rightarrow{1^+} $ 时, 模型更倾向于选择$ v = 0.5 $ , 即$ A $ 和$ \overline{A} $ 的规模各占整个图的一半, 这样就能得到完全平衡的分割结果. 当$ p>1 $ 时, 函数相比$ p\rightarrow{1^+} $ 时得到了一定的松弛, 模型在优化过程中会在$ v = 0.5 $ 左右一定范围内进行选择, 因此会得到不同平衡程度的分割结果. 此外,$ p $ 取值越大, 模型越有可能得到不平衡的分割结果. 然而, 函数族$ \Phi_p(v) $ 还有很大的改进空间来实现更宽松或更严格的平衡约束. 因此, 本文提出了一个新的函数族$ \Psi_r(v) $ , 其表达式为$$ \Psi_r(v) = \dfrac{-\left|\dfrac{1}{2}-v\right|^r+\left(\dfrac{1}{2}\right)^r}{\left(\dfrac{1}{2}\right)^r} $$ (8) 其中, 参数
$ r>0 $ .$ \Psi_r(v) $ 的示意图如图2所示.
图 2 函数$\Psi_r(v)$ 在不同参数$r$ 时的示意图Fig. 2 Illustration of functions$\Psi_r(v)$ with different parameter$r$ 本文提出的两路图分割模型记作FBC (Flexible bi-way graph cut). 可以很容易地验证,
$\Psi_2(\rho(A)/ \rho(V))$ 与$ RCut/ NCut $ 的平衡函数是等价的. 当$ r = 1 $ 时, 若$ \rho(A)\leq\rho(\overline{A}) $ , 则$ \Psi_1(\rho(A)/\rho(V)) = \rho(A) $ ; 反之$\Psi_1(\rho(A)/\rho(V)) \;=\; \rho(\overline{A}) $ . 因此,$\Psi_1(\rho(A)/\rho(V))\; = \min\{\rho(A),\rho(\overline{A})\}$ . 这说明$\Psi_1 (\rho(A)/ \rho(V))$ 与$RCC / NCC$ 的平衡函数等价. 从图2可以看到, 与$ \Phi_p(v) $ 相比, 新的平衡函数族$ \Psi_r(v) $ 覆盖的范围更广. 当$ r< 1 $ 时,$ \Psi_r(v) $ 可以覆盖图1中内部的三角形区域, 从而实现比函数$ \Phi_{p\rightarrow{1^+}}(v) $ 更严格的平衡约束. 特别是当$ r\rightarrow{0} $ 时,$ \Psi_r(v) $ 的极限$\lim_{r\rightarrow{0}}\Psi_r(v) = \delta(v-{1}/{2})$ , 其中$ \delta(\cdot) $ 表示狄拉克函数. 这时, 该函数会对任何不平衡的分割方案实施强力的惩罚. 当$ r>2 $ 时,$ \Psi_r(v) $ 不仅能覆盖图1中的浅灰色区域, 还能覆盖外部的空白区域, 从而实现比函数$ \Phi_{p\rightarrow{\infty}}(v) $ 更宽松的平衡约束. 特别是当$ r\rightarrow\infty $ 时,$ \Psi_r(v) $ 的极限$ \lim_{r\rightarrow\infty}\Psi_r(v) = 1 $ , 这说明此时的平衡函数未施加任何约束.2.2 多路图分割模型
在两路图分割模型(6)中, 平衡约束使得模型倾向于得到两个规模相等的子集. 同时, 通过调整参数
$ r $ , 可以实现不同程度的平衡约束. 类似地, 本文还提出一种灵活多路图分割模型, 其处理多类聚类任务时, 约束每个类的规模均等, 且可以通过参数来调节约束的程度. 此外, 文献[11]和文献[19]分别讨论了避免使用递归技术能显著改善多类聚类的性能. 为此, 所提出的多路图分割模型也采用非递归的方式来直接得到多分类的结果.一般的多路图分割模型可以表示为
$$ \min\limits_{\{A_1,\cdots,A_c\}}\sum\limits_{k = 1}^{c}\frac{cut(A_k,\overline{A}_k)}{\widehat{W}(A_k)} $$ (9) 其中,
$ \widehat{W}(A_k) $ 表示不同的平衡函数, 例如式(2) ~ (5). 在该模型框架下, 本文提出的平衡函数为$$ \Psi_r^\tau(v) = \dfrac{-\left|\dfrac{1}{\tau}-v\right|^r+\left(\dfrac{\tau-1}{\tau}\right)^r}{\left(\dfrac{\tau-1}{\tau}\right)^r} $$ (10) 其中, 参数
$ \tau = c $ . 实际上, 在两路图分割模型$(c = 2 )$ 中,$ \Psi_r(A) = \Psi_r^2(A) $ .所提出的多路图分割模型记作FMC. 因为函数
$ \Psi_r^\tau(v) $ 在$ v = 1/\tau $ 处取最大值, 所以FMC倾向于产生各个类别规模一致的聚类结果. 此外, FMC还包含了多个已有的多路图分割模型. 容易验证, 当参数$ r = 1 $ 时, FMC与文献[11]的模型等价. 如果参数$ \tau = 2 $ 且$ r = 1 $ , 则可得到文献[12]的模型.3. 模型的实现
3.1 连续松弛方法
由于FMC的实现是一个NP难问题, 因此需要先对模型进行连续松弛. 现有的一些松弛方法[14, 20]或者太松, 或者不适用于此模型. 参照文献[13, 18], 我们为新模型设计了一个紧松弛方法.
由于Lovász扩展[21]可以将集合函数由
$ 2^V $ 空间推广到整个$ {{\bf{R}}}^V $ 空间, 因此可以借助其思想将原始的离散优化问题松弛为连续优化问题. 集合函数$ \widehat{W}(A) $ 的Lovász扩展如下:$$ W({\boldsymbol{f}}) = f_{j_1}\widehat{W}(A_1)+\sum\limits_{i = 2}^n{f_{j_i}\big(\widehat{W}(A_i)-\widehat{W}(A_{i-1})\big)} $$ (11) 其中,
$A_i = \{{j_1},\cdots,{j_i}\}$ , 且$\widehat{W}(A_i) = \Psi_r^\tau(\rho(A_i)/ \rho(V))$ . 向量$ {\boldsymbol{f}}\in{{\bf{R}}}^n $ 中的各元素满足$ f_{j_1}\geq\cdots\geq{f_{j_n}} $ . 此外, 由Lovász扩展的性质可知$ W_r^\tau({\bf{1}}_A) = \widehat{W}_r^\tau(A) $ .同样地, 集合函数
$ cut(A,\widehat{A}) $ 的Lovász扩展如下:$$ TV({\boldsymbol{f}}) = \frac{1}{2}\sum\limits_{i,j = 1}^n{s_{ij}|f_{i}-f_{j}|} $$ (12) 因此, 松弛后的图分割模型可以表述为
$$ \begin{aligned} &\min\limits_{{\boldsymbol{F}} =\; [{\boldsymbol{f}}_1,\cdots,{\boldsymbol{f}}_c]}\;\;{\sum\limits_{k = 1}^c\frac{TV({\boldsymbol{f}}_k)}{W({\boldsymbol{f}}_k)}}&{(13{\rm{a}})} \\ &\;\;\;\;\;\quad{\rm{s.t.}}\;\;\quad{\boldsymbol{F}}\geq0\;\qquad\quad&(13{\rm{b}})\\ &\quad\qquad\qquad{\boldsymbol{f}}^i{\bf{1}}_c = 1,\;i = 1,\cdots,n\quad\qquad\;&(13{\rm{c}})\\ &\quad\qquad\qquad\max({\boldsymbol{f}}^i) = 1,\;\forall{i}\in{I}\quad\qquad\;&(13{\rm{d}})\\ &\quad\qquad\qquad{W}({\boldsymbol{f}}_k)\geq{m},\;k = 1,\cdots,c\quad\qquad\;&(13{\rm{e}}) \end{aligned}$$ 其中, 向量
$ {\boldsymbol{f}}_i $ 表示矩阵$ {\boldsymbol{F}} $ 的第$ i $ 列, 向量$ {\boldsymbol{f}}^i $ 表示矩阵$ {\boldsymbol{F}} $ 的第$ i $ 行. 向量$ {\bf{1}}_c $ 是一个长度为$ c $ 的全$ 1 $ 列向量. 集合$ I\subset{V} $ 是对图中特定顶点的索引, 这些顶点对应着各类中最有可能属于当前类的样本.$ m>0 $ 是平衡函数$ \widehat{W}(A) $ 在非零集合上的最小值.约束条件(13b)和(13c)相结合可以保证指示矩阵
$ {\boldsymbol{F}} $ 满足条件$ {\boldsymbol{F}}\in[0,1]^{n\times{c}} $ . 约束条件(13d)能够避免产生退化的连续解, 即由这些连续解得到的聚类结果中存在空的类别. 对于有监督的聚类任务, 集合$ I $ 包含了已知的先验知识. 对于无监督的聚类任务, 集合$ I $ 可以在模型优化的过程中自动调整[18]. 约束条件(13e)用来避免$ {\boldsymbol{f}}_k $ 为全零向量. 这4个约束条件共同保证了连续模型(13)是原始图分割模型的紧松弛, 且当$ I = V $ 时, 该松弛模型是精确的.在求得松弛模型(13)的最优解
$ {\boldsymbol{F}}^* $ 后, 可以采用k均值聚类或者rounding的方法对连续解$ {\boldsymbol{F}}^* $ 进行离散化处理, 从而得到最终的图分割结果$P = \{A_1,\cdots, A_c\}$ . 本文采用的rounding方法如下:$$ A_i = \{j\in{V}|i = \arg\max\limits_{l = 1,\cdots,c}f_{jl}\},\;i = 1,\cdots,c $$ (14) 3.2 优化算法
在优化问题(13)的目标函数中, 函数
$ TV({\boldsymbol{f}}_k) $ 是非平滑的凸函数. 而对于函数$ W({\boldsymbol{f}}_k) $ , 其凹凸性由对应的集合函数$ \widehat{W}(A_k) $ 来决定. 由于函数$ \widehat{W}(A_k) $ 的凹凸性未知, 所以这里先讨论该函数的凹凸性.由文献[22]可知, 对于非负向量
${\boldsymbol{u}}\in{\bf{R}}_+^n$ , 以及非负凹函数$h:{\bf{R}}_+\rightarrow{\bf{R}}$ , 存在一个子模函数$G:A\rightarrow {h({\boldsymbol{u}}(A))}$ , 其中${\boldsymbol{u}}(A) = \sum\nolimits_{i\in{A}}u_i$ . 此外, 函数$ G $ 的Lovász扩展是凸的. 因此, 如果$ {\boldsymbol{u}} = {\bf{1}}_n $ , 则有$ {\boldsymbol{u}}(A) = |A| $ . 另外, 当$ r\geq{1} $ 时, 函数$ h(|A|) = \Psi(|A|/|V|) $ 是凹函数. 因此, 当$ r\geq{1} $ 时, 平衡函数$ \widehat{W}(A) = \Psi(|A|/ |V|) $ 是子模函数, 那么其对应的Lovász扩展$ W({\boldsymbol{f}}) $ 是凸的. 类似地, 若$ {\boldsymbol{u}} $ 的第$ i $ 个元素$ u_i = d_{ii} $ , 则$ {\boldsymbol{u}}(A) = vol(A) $ . 当$ r\geq{1} $ 时, 平衡函数$ \widehat{W}(A) = \Psi(vol(A)/ vol(V)) $ 对应的Lovász扩展$ W({\boldsymbol{f}}) $ 也是凸的. 然而, 当$ 0<r<1 $ 时, 由于平衡函数$ \widehat{W}(A) $ 是非凹的, 因此不能确定其对应的Lovász扩展$ W({\boldsymbol{f}}) $ 的凹凸性.由文献[23]可知, 任意集合函数
$ G:2^V\rightarrow{\bf{R}} $ 都可以写成两个子模函数的差, 且该集合函数对应的Lovász 扩展$ g:{\bf{R}}^{n}\rightarrow{\bf{R}} $ 可以写成两个凸函数的差. 因此, 当$ 0<r<1 $ 时, 可以将平衡函数写成$\widehat{W}(A) = \widehat{G}(A)-\gamma\widehat{H}(A)$ . 其中, 函数$ \widehat{G}(A) = \widehat{W}(A)+\gamma\widehat{H}(A) $ , 函数$ \widehat{H}(A) $ 是一个严格的子模函数,$\gamma = {|\theta_1|}/{\theta_2}$ . 这里,$ \theta_1 $ 和$ \theta_2 $ 的具体计算为$$ \theta_1 = \min\limits_{X\subset{Y}\subset{V\setminus{j}}}{\widehat{W}(j|X)-\widehat{W}(j|Y)} $$ (15) $$ \theta_2 = \min\limits_{X\subset{Y}\subset{V\setminus{j}}}{\widehat{H}(j|X)-\widehat{H}(j|Y)} $$ (16) 其中,
$ X $ 和$ Y $ 是两个集合,$ j\in{V} $ , 且$\widehat{W}(j|X) = \widehat{W}(X\cup {j})-\widehat{W}(X)$ ,$ \widehat{H}(j|X) = \widehat{H}(X\cup{j})-\widehat{H}(X) $ .通过计算可得,
$\theta_1 = (2^r-2)/\big((\frac{\tau-1}{\tau})^r\rho(V)^r\big)$ . 此外, 本文选择函数$ \widehat{H}(A) = \Psi_2^\tau(v) $ , 则对应的$\theta_2 = 2/\big((\frac{\tau-1}{\tau})^2\rho(V)^2\big)$ . 图3显示了$ r = 0.1 $ 和$ r = 0.5 $ 时函数$ \widehat{W} $ 和$ \widehat{G} $ 的曲线对比. 可以看出, 在函数$ \widehat{W} $ 的基础上构造的函数$ \widehat{G} $ 是凹函数, 从而将非凹函数$ \widehat{W} $ 变换成两个凹函数的差.
图 3 函数$\widehat{W}$ 和$\widehat{G}$ 的对比图Fig. 3 The comparisons of$\widehat{W}$ and$\widehat{G}$ 因此, 优化问题(13)可重新写为
$$ \begin{aligned} &\min\limits_{{\boldsymbol{F}} = [{\boldsymbol{f}}_1,\cdots,{\boldsymbol{f}}_c]}\;{\sum\limits_{k = 1}^c\frac{TV({\boldsymbol{f}}_k)}{G({\boldsymbol{f}}_k)-\gamma{H({\boldsymbol{f}}_k)}}} \quad\qquad\;&(17{\rm{a}})\\ &\;\;\;\;\;\quad{\rm{s.t.}}\;\;\quad{\boldsymbol{F}}\geq{0}\quad\qquad\;&(17{\rm{b}})\\ &\quad\qquad\qquad{\boldsymbol{f}}^i{\bf{1}}_c = 1,\;i = 1,\cdots,n\quad\qquad\;&(17{\rm{c}})\\ &\quad\qquad\qquad\max({\boldsymbol{f}}^i) = 1,\;\forall{i}\in{I}\quad\qquad\;&(17{\rm{d}})\\ &\quad\qquad\qquad{G({\boldsymbol{f}}_k)}\geq{m'},\;k = 1,\cdots,c\quad\qquad\;&(17{\rm{e}}) \end{aligned}$$ 其中,
$ G({\boldsymbol{f}}_k) = {W}({\boldsymbol{f}}_k)+\gamma{H({\boldsymbol{f}}_k)} $ 是$ \widehat{G}(A) $ 的Lovász 扩展,$ H({\boldsymbol{f}}_k) $ 是$ \widehat{H}(A_k) $ 的Lovász 扩展. 当$ 0<r<1 $ 时,$\gamma = {|\theta_1|}/{\theta_2}$ , 否则$ \gamma = 0 $ .$ m'>0 $ 是集合函数$ \widehat{G}(A) $ 在非零集合上的最小值.在优化问题(17)的约束条件中, (17d)和(17e)是两个非凸约束. 依照凸近似方法, 约束条件(17d)可以变换成如下形式:
$$ {f_{ij_i} = 1,\;\forall{(i,j_i)}\in{K}} $$ (18) 其中, 索引
$j_i = \arg\max_j{f_{ij}}$ ,$ \forall{i}\in{I} $ . 集合$K = \{(i, j_i)| i\in{I}\}$ .根据次梯度的定义可知, 函数
$G({\boldsymbol{f}})\geq G({\boldsymbol{f}}^{(t)})+ \langle{{\boldsymbol{g}}^{(t)},{\boldsymbol{f}}-{\boldsymbol{f}}^{(t)}}\rangle = \langle{{\boldsymbol{g}}^{(t)},{\boldsymbol{f}}}\rangle$ , 其中$ {\boldsymbol{g}}^{(t)} $ 是函数$ G({\boldsymbol{f}}) $ 在$ {\boldsymbol{f}}^{(t)} $ 处的次梯度. 因此, 约束条件(17e)可以变换为如下形式:$$ \langle{{\boldsymbol{g}}_k^{(t)},{\boldsymbol{f}}_k}\rangle\geq{m'},\;k = 1,\cdots,c $$ (19) 于是, 本文提出的求解算法如算法1所示.
算法1. 灵活平衡约束的图聚类算法
输入. 相似图矩阵
$ {\boldsymbol{S}} = [s_{ij}] $ , 平衡函数参数$ r $ , 参数$ \tau $ , 类 别数$ c $ .输出.
$ c $ 个聚类簇.步骤 1. 初始化
$ {\boldsymbol{F}}^{(0)} $ , 满足约束条件(17b) ~ (17e), 并计 算此时目标函数的值$ \beta^{(0)} $ .步骤 2. 计算函数
$ G({\boldsymbol{f}}) $ 在$ {\boldsymbol{f}}_k^{(0)} $ 处的次梯度$ {\boldsymbol{g}}_k^{(0)} $ ,$k = 1,$ $\cdots,c $ .步骤 3. 采用主对偶混合梯度(Primal dual hybird gradient, PDHG)算法[24]求解最小化问题
${\boldsymbol{F}}^{(1)} = $ $\arg\min_{{\boldsymbol{F}}\in{C}}\sum\nolimits_{k = 1}^c\big(TV({\boldsymbol{f}}_k) + \beta^{(0)}(\gamma{H({\boldsymbol{f}}_k)} - \langle{\boldsymbol{g}}_k^{(0)},$ $ {\boldsymbol{f}}_k\rangle)\big). $ 其中, C是约束条件(17b) ~ (17e)的集合.步骤 4. 计算目标函数在
$ {\boldsymbol{F}}^{(1)} $ 时的值$ \beta^{(1)} $ .步骤 5. 利用rounding方法对
$ {\boldsymbol{F}}^{(1)} $ 进行离散化, 如果得 到的解是原始图分割模型(9)的可行解, 则更新 约束条件(17d)中的集合$ I $ ; 否则, 集合$ I $ 的规模 加倍.步骤 6. 重复执行步骤2 ~ 5, 直至算法收敛.
4. 实验结果和分析
为了验证FMC的性能, 首先在合成数据集上验证不同平衡函数对模型的影响, 然后在真实数据集上验证模型的聚类性能和解的准确性.
4.1 合成数据上的结果
合成数据包含868个数据点, 每个数据点
$ {\boldsymbol{x}}_i $ 由20维向量表示. 如图4(a)展示了前两维表示的数据集合, 剩余维度都是高斯噪声. 采用热核加权的方法构建该数据的全连接邻接图, 各连接边的权值计算方式为$$ s_{ij} = {\rm{e}}^{-\tfrac{\Arrowvert{{\boldsymbol{x}}_i-{\boldsymbol{x}}_j}\Arrowvert_2^2}{\sigma}} $$ (20) 其中, 参数
$ \sigma $ 设置成所有顶点对的平方欧氏距离的中位数. 邻接图如图4(b)所示.为了验证所提出的平衡函数族
$ \Psi_r(v) $ 比文献[14]的$ \Phi_p(v) $ 覆盖范围更广, 实验采用Ratio形式的平衡函数, 并与传统的图聚类模型RCut、RCC和ARCC进行对比. 其中,$ r\in(0,2] $ ,$ p\in(1,2] $ , 且RCC与$ \Phi_{p\rightarrow{1}^+}(v) $ 等价. 在合成数据上的聚类结果如图5所示. 由图5可以看出, RCut、RCC和ARCC都将一个孤立的点单独划分为一类, 说明传统方法即使采用最强的平衡约束也无法实现规模相近的聚类. FMC通过选择参数$ r<1 $ , 可以得到近似平衡的聚类, 这说明所提出的平衡函数族$ \Psi_r(v) $ 比$ \Phi_p(v) $ 的覆盖范围更广. 此外, 根据每个方法的结果计算的Cut值分别为$ 5.78 $ ,$ 5.74 $ ,$ 5.74 $ ,$ 79.72 $ 和$ 95.42 $ , 结合各方法的聚类结果的平衡性可以看出, RCut、RCC和ARCC虽然得到的是不平衡的聚类, 但是它们的Cut值更小. 而FMC虽然得到了平衡的聚类, 但是得到的Cut值更大.为了进一步验证不同平衡函数对模型的影响, 实验还对比了Normalized形式的FMC和传统的图聚类模型NCut、NCC和ANCC. 聚类结果如图6所示. 可以看出, NCut取得了非常不平衡的聚类, 而ANCC取得了完全平衡的聚类. NCC和FMC的聚类结果都介于NCut和ANCC之间, 不同在于, NCC有两个规模很大的类别和一个规模很小的类别, 这主要是因为NCC本质上约束了各类别的规模接近总规模的一半. 而FMC通过选择参数
$ 1<r<2 $ , 可以得到更平滑的聚类结果. 同样地, 计算的Cut值分别为$ 12.81 $ ,$ 97.58 $ ,$ 126.81 $ ,$ 79.72 $ 和$ 39.50 $ . 结合前面计算的Cut值可以看出, 平衡约束越强, 则对应得到的Cut值越大; 平衡约束越弱, 则对应得到的Cut值越小, 从而验证了平衡约束对图聚类模型的影响.4.2 真实数据上的结果
20个真实数据集的详细信息如表1所示. 其中, HIGHSCHOOL[25]是高中学生的朋友关系网络数据集, 本文从5个大类中采集了一个子集作为实验数据; POLBOOKS[26]是一个关于美国政治的书籍网络数据集; FOOTBALL[25]记录了22支足球队之间的比赛数据; DUKE[27]是用于预测乳腺癌的临床状态的基因表达谱数据, 包含7129维特征; CANCER[28]是一个包含16063个基因表达的数据集; KHAN[28]是一个包含2318个基因表达的数据集; ROSETTA[29]是一个包含12634维特征的微阵列数据集; ORL[30]和UMIST[31]都是人脸数据集, 每幅图像的尺寸为
$ 92\times{112} $ 像素; ALPHADIGS[32]是一个二进制数字数据集, 其每个样本是一个字母或数字的二值图像, 尺寸为$ 20\times{16} $ 像素; COIL20[33]数据集包含不同角度的玩具图像, 每幅图像的尺寸是$ 128\times{128} $ 像素; SAVEE[34]、CASIA[35]和IEMOCAP[36]是3个语音情感数据集, 其中, SAVEE和IEMOCAP是英文数据, CASIA是中文数据; MED[37]是一个文本摘要集合, 包含5831个单词; WEBKB4[38]和REUTERS[39]都是文本文档集合, 其分别保留了10000个和18933个最大信息增益的单词; YEAST[39]是用于预测蛋白质的细胞定位点数据, 含8维特征; FAULTS[39]包含7种类型的钢板断裂数据, 由27维特征进行描述; ECOLI[39]是蛋白质定位点数据, 包含8维特征. 为每个数据集构建一个对称$ K $ 近邻图, 其中$ K = 5 $ . 在构建该图之前, 分别提取图像、语音和文本数据的散度(Scattering)特征[40]、超音段(Supra-segmental)特征[41]和词频−逆向文件频率(Term frequency-inverse document frequency, Tf-Idf)特征.表 1 真实数据集Table 1 The statistics of real databases数据集 样本数 类别数 数据类型 HIGHSCHOOL 60 5 社交 POLBOOKS 105 3 社交 FOOTBALL 115 12 社交 DUKE 44 2 医疗 CANCER 198 14 医疗 KHAN 83 4 基因 ROSETTA 300 5 基因 ORL 400 40 图像 UMIST 575 20 图像 ALPHADIGS 1404 36 图像 COIL20 1440 20 图像 SAVEE 480 7 语音 CASIA 1200 6 语音 IEMOCAP 9994 8 语音 MED 1033 31 文本 WEBKB4 4196 4 文本 REUTERS 8293 65 文本 YEAST 1484 10 生物 FAULTS 1941 7 工业 ECOLI 327 5 蛋白质 将FMC与多个不同类型的聚类方法进行比较, 包括PLSI[42]、CLR[43]和基于NMF的方法PNMF[44]、NSC[45]、LSD[46]、NMFR[47], 以及图聚类方法1Spec[16]、MTV[11]、BKCut[18]、CCB[15]和 L21MC[19], 所有方法都采用各自文献中使用的实验方案进行配置. 在图聚类方法中, 由于MTV和L21MC采用的是Ratio形式的平衡函数, 为了进行公平的对比, 其他图聚类方法也都采用了相同形式的平衡函数, 且1Spec采用了对称的Cheeger函数, BKCut采用了与MTV相同的非对称Cheeger函数. 另外, 实现多类聚类任务的方式有两种: 1)直接执行多路图聚类模型(MTV、BKCut、CCB和FMC); 2)递归地执行两路图聚类模型(1Spec和FBC), 本文对这两种方式的聚类结果也进行了对比. 最后, 为了更好地体现出灵活模型的优势, 也统计了FBC和FMC模型在
$r = \{0.1,0.2,\cdots,2.0\}$ 上的最优结果. 聚类性能由聚类纯度(Purity)来评估, 其定义为$\frac{1}{n}{ \sum\nolimits_{k = 1}^{c}\max_{1\leq{l}\leq{c}}{n_k^l}}$ , 其中,$ n_k^l $ 表示第$ k $ 个聚类中属于第$ l $ 类的样本数. 聚类纯度越大, 说明聚类性能越好. 不同方法的聚类结果如表2和表3所示.表 2 各图聚类方法的聚类精度(%)对比Table 2 Comparison of clustering accuracies (%) between graph clustering methods数据集 1Spec[16] MTV[11] L21MC[19] BKCut[18] CCB[15] FBC (r) FMC (r) HIGHSCHOOL 81.67 80.00 70.00 81.67 86.67 71.67 (0.9) 89.67 (1.2) POLBOOKS 82.86 79.05 77.14 81.90 83.81 81.50 (1.4) 83.81 (1.3) FOOTBALL 86.96 92.17 24.35 93.04 86.09 92.11 (1.3) 93.04 (1.8) DUKE 52.27 70.45 63.64 52.27 52.27 70.45 (0.5) 70.45 (0.5) CANCER 34.34 54.04 52.02 54.55 48.48 53.54 (1.5) 54.55 (1.7) KHAN 57.83 49.40 54.22 51.81 57.83 50.28 (1.6) 57.83 (1.6) ROSETTA 76.67 76.67 76.67 76.67 76.67 76.67 (1.0) 77.33 (1.9) ORL 36.00 52.50 79.25 82.00 74.25 74.75 (1.5) 81.75 (1.0) UMIST 58.96 76.87 70.78 70.09 65.22 72.70 (1.3) 74.96 (1.3) ALPHADIGS 36.11 51.71 46.08 47.72 45.87 36.84 (2.0) 49.00 (2.0) COIL20 45.00 81.46 50.97 78.89 77.29 81.81 (1.0) 82.92 (1.2) SAVEE 25.21 32.50 31.46 31.46 29.17 31.02 (1.1) 33.24 (1.3) CASIA 22.42 32.92 28.50 28.08 28.58 26.00 (0.1) 35.54 (0.4) IEMOCAP 54.03 54.00 54.00 54.03 54.03 54.03 (1.9) 55.21 (1.5) MED 44.72 53.92 52.76 54.99 53.53 50.09 (1.4) 55.00 (1.4) WEBKB4 39.39 56.22 39.30 51.60 39.56 46.14 (0.5) 59.60 (0.7) REUTERS 52.83 73.34 65.69 61.02 69.38 67.58 (2.0) 73.53 (1.5) YEAST 51.35 53.97 49.26 53.71 51.95 44.41 (1.6) 54.85 (1.6) FAULTS 36.89 40.08 37.92 41.11 39.52 31.72 (1.8) 42.76 (1.7) ECOLI 79.82 77.67 77.67 82.87 77.98 71.43 (1.8) 82.87 (1.8) 表 3 本文方法与其他非图聚类方法的聚类精度(%)对比Table 3 Comparison of clustering accuracies (%) between ours and other non-graph clustering methods数据集 PNMF[44] NSC[45] PLSI[42] LSD[46] NMFR[47] CLR[43] FMC (r) HIGHSCHOOL 81.67 83.33 83.33 81.67 95.00 80.00 89.67 (1.2) POLBOOKS 78.10 80.95 78.10 78.10 79.05 80.95 83.81 (1.3) FOOTBALL 93.04 93.04 93.04 93.04 93.04 93.04 93.04 (1.8) DUKE 52.27 52.27 70.45 70.45 70.45 52.27 70.45 (0.5) CANCER 53.53 53.03 53.53 53.03 51.52 54.04 54.55 (1.7) KHAN 60.24 55.42 55.42 51.81 50.60 51.81 57.83 (1.6) ROSETTA 76.67 76.67 76.67 76.67 76.67 77.00 77.33 (1.9) ORL 81.50 82.25 82.50 81.25 82.50 80.00 81.75 (1.0) UMIST 64.00 68.00 68.52 68.35 71.83 70.26 74.96 (1.3) ALPHADIGS 44.94 49.43 48.65 49.36 50.78 36.47 49.00 (2.0) COIL20 75.21 81.25 80.69 75.00 82.85 85.21 82.92 (1.2) SAVEE 31.88 31.46 31.67 34.17 31.88 28.13 33.24 (1.3) CASIA 35.17 29.08 32.00 32.17 34.08 27.92 35.54 (0.4) IEMOCAP 54.00 54.06 54.00 54.00 54.00 54.02 55.21 (1.5) MED 53.92 53.73 54.50 54.60 55.86 49.18 55.00 (1.4) WEBKB4 39.06 39.77 48.90 50.81 63.32 39.56 59.60 (0.7) REUTERS 73.86 76.47 75.92 74.99 76.52 51.80 73.53 (1.5) YEAST 52.76 54.31 52.69 52.09 54.85 46.90 54.85 (1.6) FAULTS 39.26 40.08 40.03 40.18 38.17 41.37 42.76 (1.7) ECOLI 77.68 78.90 79.82 67.89 79.20 78.29 82.87 (1.8) 表2显示了不同的图聚类方法在全部20个数据集上的聚类结果, 括号中列出的是最优的参数
$ r $ , 加粗的字体表示每行的最大值. 从结果可以看出, FMC在17个数据集上取得了优于其他方法的聚类精度, 这说明一个合适的平衡正则能够显著地改善图聚类模型的性能. 此外, FMC在全部数据集上都优于L21MC方法. 实际上, L21MC方法将传统的比−和形式的图切割准则转变成了和−比形式, 这导致其在切割过程中忽视了图中边的分布. 对比结果表明, 考虑边的分布对于图聚类模型很重要. FMC的聚类性能优于CCB, 主要是因为CCB方法施加的平衡约束比RCut的更宽容, 而从FMC的最优参数可以看出, 最佳的聚类性能大部分都由比RCut更严格的平衡约束获得. 在多类聚类任务中, 多路图模型(FMC、MTV、L21MC和BKCut)的性能往往优于两路图模型(1Spec和FBC). 对比所提出的FMC和 FBC可以发现, 在DUKE、KHAN、ALPHADIGS、MED、YEAST和ECOLI数据集上, 两种方法在相同的平衡函数上取得了最佳的性能. 但是, FMC的性能除了在DUKE数据集上与FBC的相同之外, 在其他数据集上的性能远远优于FBC. 这表明, 递归的二分方式会严重影响模型在多类聚类任务上的性能. 值得注意的是, FMC模型在类别数较多的数据集上的性能优势并不明显, 甚至在ORL、UMIST和ALPHADIGS三个数据集上的聚类性能弱于MTV和BCut方法. 这说明在实验设定的平衡函数空间中, FMC模型未能准确刻画出这3个数据的类别分布. 可能的原因在于, 当类别数越多时, 类别分布越难被刻画, 所以需要更精细地选择模型参数$ r $ . 尽管如此, 与其他图聚类方法相比, FMC模型依然具有竞争力.表3显示了FMC与其他现有的聚类方法的对比结果. 可以看出, FMC在小规模数据集上的性能优于其他方法, 而这些对比方法需要更多的数据来提供额外的信息以帮助聚类. NMFR和FMC在图像数据集上都表现得很好, 而FMC在语音数据集上的表现优于NMFR. 但是, NMFR在文本数据等非流形数据集上的性能更优, 这主要是因为NMFR使用了流形平滑技术, 而FMC没有. FMC在一些数据集上的性能即使不是最优的, 也与最优性能非常接近. 因此, 本文方法可以作为处理聚类任务的可选方案.
本文还对全部的聚类结果进行了统计分析, 根据不同方法的聚类结果所绘制的箱线图如图7所示. 可以看出, FMC的全部聚类结果的中位数和上、下四分位数均大于其他图聚类方法, 说明所提出方法的总体表现明显优于其他图聚类方法. 类似地, FMC的整体表现优于PNMF、NSC、PLSI、LSD和CLR, 而在中位数上略小于NMFR. 尽管如此, FMC在上、下四分位数和最大值、最小值上都大于NMFR.
为了验证本文算法得到的解的质量, 设计了一组对比实验, 将一些方法得到的聚类结果代入同一个图分割目标函数中, 计算的函数值如表4所示. 这些方法包括全部的图聚类方法和部分非图聚类方法. 虽然非图聚类方法并不是直接优化的图分割模型, 但其结果也可以作为评价解优越性的参考. 表4统计了6个不同的图分割函数, 分别是Ratio形式的FMC (FRCut)和Normalized形式的FMC (FNCut), 参数
$ r $ 分别取值$ \{0.5, 1.0, 2.0\} $ . 每个方法的函数值都是其在全部真实数据集上的图分割函数的平均值和方差, 方差列在括号中. 可以看出, 本文算法在全部6个目标函数上都取得最小值, 这说明本文的紧松弛方法和优化算法对于所提出的平衡图分割问题有效. 值得注意的是, 虽然1Spec方法在解的优越性方面表现较好, 但在聚类性能上表现最差, 这也从一定程度上说明了灵活模型的必要性.表 4 不同聚类方法得到的图分割函数值Table 4 The values of different graph cut functions obtained by different clustering methods图分割函数 1Spec[16] MTV[11] L21MC[19] BKCut[18] CCB[15] PLSI[42] LSD[46] NMFR[47] CLR[43] 本文方法 FRCut0.5 12.64 (13.01) 13.99 (12.66) 15.57 (10.64) 12.03 (11.09) 18.63 (14.63) 14.43 (12.16) 14.70 (12.41) 14.27 (12.04) 13.69 (12.14) 9.71 (10.52) FRCut1.0 9.21 (9.64) 12.27 (11.22) 12.09 (8.27) 9.67 (9.31) 13.93 (11.28) 12.36 (10.35) 12.95 (10.83) 12.77 (10.90) 9.78 (9.08) 8.05 (8.18) FRCut2.0 7.79 (7.96) 11.89 (10.99) 10.90 (7.77) 8.37 (8.42) 12.18 (10.64) 11.88 (9.99) 12.62 (10.57) 12.50 (10.78) 8.18 (8.36) 6.72 (7.18) FNCut0.5 1.83 (1.48) 1.78 (1.42) 2.05 (1.25) 1.57 (1.25) 1.87 (1.46) 1.84 (1.35) 1.90 (1.38) 1.83 (1.37) 1.79 (1.48) 1.39 (1.21) FNCut1.0 1.35 (1.14) 1.53 (1.23) 1.56 (0.93) 1.29 (1.09) 1.41 (1.13) 1.54 (1.14) 1.63 (1.18) 1.60 (1.20) 1.26 (1.06) 1.14 (1.03) FNCut2.0 1.19 (1.00) 1.47 (1.20) 1.39 (0.87) 1.18 (1.03) 1.24 (1.07) 1.47 (1.10) 1.57 (1.14) 1.55 (1.17) 1.04 (0.95) 0.92 (0.83) 5. 结束语
本文针对多类聚类问题, 提出了一种基于灵活平衡约束的图聚类方法FMC, 能够实现从无平衡约束到严格平衡约束的图聚类. 在聚类方法的实现方面, 提出了一种紧的连续松弛方法, 将原问题中的离散集合函数替换成与之等价的Lovasz扩展. 通过选择一组合适的约束条件, 避免了病态的连续解, 从而保证能从连续解中恢复离散问题的解. 此外, 还提出了一种新的优化算法来解决非凸、非光滑的连续优化问题. 在合成数据集上对FMC在不同平衡约束下的性能进行了验证, 结果表明, FMC通过选择不同的参数
$ r $ 能实现不同的平衡约束, 从而影响聚类结果. 在20个真实数据集上对FMC的聚类性能和算法求解的准确性进行了验证, 结果表明FMC在大部分数据上的聚类性能比传统方法的更好, 且得到的解也最优. 虽然FMC的聚类性能优于其他模型, 但这些结果都是在不同参数$ r $ 上的最优性能, 如何进行模型选择还需要进一步探讨和研究. -
图 2 函数
$\Psi_r(v)$ 在不同参数$r$ 时的示意图Fig. 2 Illustration of functions
$\Psi_r(v)$ with different parameter$r$
图 3 函数
$\widehat{W}$ 和$\widehat{G}$ 的对比图Fig. 3 The comparisons of
$\widehat{W}$ and$\widehat{G}$ 表 1 真实数据集
Table 1 The statistics of real databases
数据集 样本数 类别数 数据类型 HIGHSCHOOL 60 5 社交 POLBOOKS 105 3 社交 FOOTBALL 115 12 社交 DUKE 44 2 医疗 CANCER 198 14 医疗 KHAN 83 4 基因 ROSETTA 300 5 基因 ORL 400 40 图像 UMIST 575 20 图像 ALPHADIGS 1404 36 图像 COIL20 1440 20 图像 SAVEE 480 7 语音 CASIA 1200 6 语音 IEMOCAP 9994 8 语音 MED 1033 31 文本 WEBKB4 4196 4 文本 REUTERS 8293 65 文本 YEAST 1484 10 生物 FAULTS 1941 7 工业 ECOLI 327 5 蛋白质 
下载: 导出CSV
表 2 各图聚类方法的聚类精度(%)对比
Table 2 Comparison of clustering accuracies (%) between graph clustering methods
数据集 1Spec[16] MTV[11] L21MC[19] BKCut[18] CCB[15] FBC (r) FMC (r) HIGHSCHOOL 81.67 80.00 70.00 81.67 86.67 71.67 (0.9) 89.67 (1.2) POLBOOKS 82.86 79.05 77.14 81.90 83.81 81.50 (1.4) 83.81 (1.3) FOOTBALL 86.96 92.17 24.35 93.04 86.09 92.11 (1.3) 93.04 (1.8) DUKE 52.27 70.45 63.64 52.27 52.27 70.45 (0.5) 70.45 (0.5) CANCER 34.34 54.04 52.02 54.55 48.48 53.54 (1.5) 54.55 (1.7) KHAN 57.83 49.40 54.22 51.81 57.83 50.28 (1.6) 57.83 (1.6) ROSETTA 76.67 76.67 76.67 76.67 76.67 76.67 (1.0) 77.33 (1.9) ORL 36.00 52.50 79.25 82.00 74.25 74.75 (1.5) 81.75 (1.0) UMIST 58.96 76.87 70.78 70.09 65.22 72.70 (1.3) 74.96 (1.3) ALPHADIGS 36.11 51.71 46.08 47.72 45.87 36.84 (2.0) 49.00 (2.0) COIL20 45.00 81.46 50.97 78.89 77.29 81.81 (1.0) 82.92 (1.2) SAVEE 25.21 32.50 31.46 31.46 29.17 31.02 (1.1) 33.24 (1.3) CASIA 22.42 32.92 28.50 28.08 28.58 26.00 (0.1) 35.54 (0.4) IEMOCAP 54.03 54.00 54.00 54.03 54.03 54.03 (1.9) 55.21 (1.5) MED 44.72 53.92 52.76 54.99 53.53 50.09 (1.4) 55.00 (1.4) WEBKB4 39.39 56.22 39.30 51.60 39.56 46.14 (0.5) 59.60 (0.7) REUTERS 52.83 73.34 65.69 61.02 69.38 67.58 (2.0) 73.53 (1.5) YEAST 51.35 53.97 49.26 53.71 51.95 44.41 (1.6) 54.85 (1.6) FAULTS 36.89 40.08 37.92 41.11 39.52 31.72 (1.8) 42.76 (1.7) ECOLI 79.82 77.67 77.67 82.87 77.98 71.43 (1.8) 82.87 (1.8)
下载: 导出CSV
表 3 本文方法与其他非图聚类方法的聚类精度(%)对比
Table 3 Comparison of clustering accuracies (%) between ours and other non-graph clustering methods
数据集 PNMF[44] NSC[45] PLSI[42] LSD[46] NMFR[47] CLR[43] FMC (r) HIGHSCHOOL 81.67 83.33 83.33 81.67 95.00 80.00 89.67 (1.2) POLBOOKS 78.10 80.95 78.10 78.10 79.05 80.95 83.81 (1.3) FOOTBALL 93.04 93.04 93.04 93.04 93.04 93.04 93.04 (1.8) DUKE 52.27 52.27 70.45 70.45 70.45 52.27 70.45 (0.5) CANCER 53.53 53.03 53.53 53.03 51.52 54.04 54.55 (1.7) KHAN 60.24 55.42 55.42 51.81 50.60 51.81 57.83 (1.6) ROSETTA 76.67 76.67 76.67 76.67 76.67 77.00 77.33 (1.9) ORL 81.50 82.25 82.50 81.25 82.50 80.00 81.75 (1.0) UMIST 64.00 68.00 68.52 68.35 71.83 70.26 74.96 (1.3) ALPHADIGS 44.94 49.43 48.65 49.36 50.78 36.47 49.00 (2.0) COIL20 75.21 81.25 80.69 75.00 82.85 85.21 82.92 (1.2) SAVEE 31.88 31.46 31.67 34.17 31.88 28.13 33.24 (1.3) CASIA 35.17 29.08 32.00 32.17 34.08 27.92 35.54 (0.4) IEMOCAP 54.00 54.06 54.00 54.00 54.00 54.02 55.21 (1.5) MED 53.92 53.73 54.50 54.60 55.86 49.18 55.00 (1.4) WEBKB4 39.06 39.77 48.90 50.81 63.32 39.56 59.60 (0.7) REUTERS 73.86 76.47 75.92 74.99 76.52 51.80 73.53 (1.5) YEAST 52.76 54.31 52.69 52.09 54.85 46.90 54.85 (1.6) FAULTS 39.26 40.08 40.03 40.18 38.17 41.37 42.76 (1.7) ECOLI 77.68 78.90 79.82 67.89 79.20 78.29 82.87 (1.8)
下载: 导出CSV
表 4 不同聚类方法得到的图分割函数值
Table 4 The values of different graph cut functions obtained by different clustering methods
图分割函数 1Spec[16] MTV[11] L21MC[19] BKCut[18] CCB[15] PLSI[42] LSD[46] NMFR[47] CLR[43] 本文方法 FRCut0.5 12.64 (13.01) 13.99 (12.66) 15.57 (10.64) 12.03 (11.09) 18.63 (14.63) 14.43 (12.16) 14.70 (12.41) 14.27 (12.04) 13.69 (12.14) 9.71 (10.52) FRCut1.0 9.21 (9.64) 12.27 (11.22) 12.09 (8.27) 9.67 (9.31) 13.93 (11.28) 12.36 (10.35) 12.95 (10.83) 12.77 (10.90) 9.78 (9.08) 8.05 (8.18) FRCut2.0 7.79 (7.96) 11.89 (10.99) 10.90 (7.77) 8.37 (8.42) 12.18 (10.64) 11.88 (9.99) 12.62 (10.57) 12.50 (10.78) 8.18 (8.36) 6.72 (7.18) FNCut0.5 1.83 (1.48) 1.78 (1.42) 2.05 (1.25) 1.57 (1.25) 1.87 (1.46) 1.84 (1.35) 1.90 (1.38) 1.83 (1.37) 1.79 (1.48) 1.39 (1.21) FNCut1.0 1.35 (1.14) 1.53 (1.23) 1.56 (0.93) 1.29 (1.09) 1.41 (1.13) 1.54 (1.14) 1.63 (1.18) 1.60 (1.20) 1.26 (1.06) 1.14 (1.03) FNCut2.0 1.19 (1.00) 1.47 (1.20) 1.39 (0.87) 1.18 (1.03) 1.24 (1.07) 1.47 (1.10) 1.57 (1.14) 1.55 (1.17) 1.04 (0.95) 0.92 (0.83)
下载: 导出CSV
-
[1] MacQueen J. Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, USA: University of California Press, 1967. 281−297 [2] Von Luxburg U. A tutorial on spectral clustering. Statistics and Computing, 2007, 17(4): 395-416 doi: 10.1007/s11222-007-9033-z [3] Ding S F, Cong L, Hu Q K, Jia H J, Shi Z Z. A multiway p-spectral clustering algorithm. Knowledge-Based Systems, 2019, 164: 371-377 doi: 10.1016/j.knosys.2018.11.007 [4] Liang N Y, Yang Z Y, Li Z N, Xie S L, Su C Y. Semi-supervised multi-view clustering with graph-regularized partially shared non-negative matrix factorization. Knowledge-Based Systems, 2020, 190: Article No. 105185 doi: 10.1016/j.knosys.2019.105185 [5] 庞宁, 张继福, 秦啸. 一种基于多属性权重的分类数据子空间聚类算法. 自动化学报, 2018, 44(3): 517-532Pang Ning, Zhang Ji-Fu, Qin Xiao. A subspace clustering algorithm of categorical data using multiple attribute weights. Acta Automatica Sinica, 2018, 44(3): 517-532 [6] 尹明, 吴浩杨, 谢胜利, 杨其宇. 基于自注意力对抗的深度子空间聚类. 自动化学报, 2022, 48(1): 271-281 doi: 10.16383/j.aas.c200302Yin Ming, Wu Hao-Yang, Xie Sheng-Li, Yang Qi-Yu. Self-attention adversarial based deep subspace clustering. Acta Automatica Sinica, 2022, 48(1): 271-281 doi: 10.16383/j.aas.c200302 [7] Stoer M, Wagner F. A simple min-cut algorithm. Journal of the ACM, 1997, 44(4): 585-591 doi: 10.1145/263867.263872 [8] Hagen L, Kahng A B. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992, 11(9): 1074-1085 doi: 10.1109/43.159993 [9] Shi J B, Malik J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905 doi: 10.1109/34.868688 [10] Chung F R K. Spectral Graph Theory. Providence: American Mathematical Society, 1997. 36−45 [11] Bresson X, Laurent T, Uminsky D, Von Brecht J H. Multiclass total variation clustering. In: Proceedings of the 26th International Conference on Neural Information Processing Systems. Lake Tahoe, USA: Curran Associates Inc., 2013. 1421−1429 [12] Bresson X, Tai X C, Chan T F, Szlam A. Multi-class transductive learning based on ℓ1 relaxations of cheeger cut and Mumford-shah-Potts model. Journal of Mathematical Imaging and Vision, 2014, 49(1): 191-201 doi: 10.1007/s10851-013-0452-5 [13] Hein M, Setzer S. Beyond spectral clustering-tight relaxations of balanced graph cuts. In: Proceedings of the 24th International Conference on Neural Information Processing Systems. Granada, Spain: Curran Associates Inc., 2011. 2366−2374 [14] Bühler T, Hein M. Spectral clustering based on the graph p-laplacian. In: Proceedings of the 26th Annual International Conference on Machine Learning. Montreal, Canada: ACM, 2009. 81−88 [15] Cahill N D, Hayes T L, Meinhold R T, Hamilton J F. Compassionately conservative balanced cuts for image segmentation. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. Salt Lake City, USA: IEEE, 2018. 1683−1691 [16] Hein M, Bühler T. An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA. In: Proceedings of the 23rd International Conference on Neural Information Processing Systems. Vancouver, Canada: Curran Associates Inc., 2010. 847−855 [17] Nie F P, Wang H, Deng C, Gao X B, Li X L, Huang H. New ℓ1-norm relaxations and optimizations for graph clustering. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence. Phoenix, USA: AAAI Press, 2016. 1962−1968 [18] Rangapuram S S, Mudrakarta P K, Hein M. Tight continuous relaxation of the balanced k-cut problem. In: Proceedings of the 27th International Conference on Neural Information Processing Systems. Montreal, Canada: MIT Press, 2014. 3131−3139 [19] Yang X, Deng C, Liu X L, Nie F P. New ℓ2,1-norm relaxation of multi-way graph cut for clustering. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence and the 30th Innovative Applications of Artificial Intelligence Conference and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence. New Orleans, USA: AAAI Press, 2018. 4374−4381 [20] Ling S Y, Strohmer T. Certifying global optimality of graph cuts via semidefinite relaxation: A performance guarantee for spectral clustering. Foundations of Computational Mathematics, 2020, 20(3): 367-421 doi: 10.1007/s10208-019-09421-3 [21] Lovász L. Submodular functions and convexity. Mathematical Programming the State of the Art. Berlin, Heidelberg: Springer, 1983. 235−257 [22] Bach F. Submodular functions: From discrete to continuous domains. Mathematical Programming, 2019, 175(1-2): 419-459 doi: 10.1007/s10107-018-1248-6 [23] Ji S, Xu D C, Li M, Wang Y S, Zhang D M. Stochastic greedy algorithm is still good: Maximizing submodular + supermodular functions. In: Proceedings of the 6th World Congress on Global Optimization. Metz, France: Springer, 2019. 488−497 [24] Chambolle A, Pock T. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 2011, 40(1): 120-145 doi: 10.1007/s10851-010-0251-1 [25] Batagelj V, Mrvar A. Pajek datasets [Online], available: http://vlado.fmf.uni-lj.si/pub/networks/data/, February 24, 2007 [26] Krebs V. Books about US politics [Online], available: https://www.cise.ufl.edu/research/sparse/matrices/Newman/polbooks.html, March 12, 2014 [27] Chang C C, Lin C J. LIBSVM — A library for support vector machines [Online], available: http://www.csie.ntu.edu.tw/~cjlin/libsvm, September 11, 2019 [28] Hastie T, Tibshirani R, Friedman J. The Elements of Statistical Learning. New York: Springer, 2009. 649−698 [29] Kim P M, Tidor B. Subsystem identification through dimensionality reduction of large-scale gene expression data. Genome Research, 2003, 13(7): 1706-1718 doi: 10.1101/gr.903503 [30] Samaria F S, Harter A C. Parameterisation of a stochastic model for human face identification. In: Proceedings of the IEEE Workshop on Applications of Computer Vision. Sarasota, USA: IEEE, 1994. 138−142. [31] Graham D B, Allinson N M. Characterising virtual eigensignatures for general purpose face recognition. Face Recognition: From Theory to Applications. Berlin: Springer, 1998. 446−456 [32] Roweis S. Binary alphadigits [Online], available: https://cs.nyu.edu/~roweis/data.html, January 12, 2010 [33] Nene S A, Nayar S K, Murase H. Columbia object image library (COIL-20) [Online], available: http://www.cs.columbia.edu/CAVE/software/softlib/coil-20.php, June 29, 2016 [34] Haq S, Jackson P J B, Edge J. Audio-visual feature selection and reduction for emotion classification. In: Proceedings of the International Conference on Auditory-Visual Speech Processing. Moreton Island, Australia: AVSP, 2008. 185−190 [35] 中文语言资源联盟. CASIA 汉语情感语料库 [Online], available: http://www.chineseldc.org/, 2010-10-09Chinese LDC. CASIA-Chinese emotional speech corpus [Online], available: http://www.chineseldc.org/, October 9, 2010 [36] Busso C, Bulut M, Lee C C, Kazemzadeh A, Mower E, Kim S, et al. IEMOCAP: Interactive emotional dyadic motion capture database. Language Resources and Evaluation, 2008, 42(4): 335-359 doi: 10.1007/s10579-008-9076-6 [37] Berry W M, Dumais S. LSI: Latent semantic indexing [Online], available: http://web.eecs.utk.edu/research/lsi/, November 21, 2008 [38] Srivastava S K, Singh S K, Suri J S. Effect of incremental feature enrichment on healthcare text classification system: A machine learning paradigm. Computer Methods and Programs in Biomedicine, 2019, 172: 35-51 doi: 10.1016/j.cmpb.2019.01.011 [39] Dua D, Graff C. UCI machine learning repository [Online], available: http://archive.ics.uci.edu/ml, September 24, 2018 [40] Oyallon E, Zagoruyko S, Huang G, Komodakis N, Julien S L, Blaschko M, et al. Scattering networks for hybrid representation learning. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019, 41(9): 2208-2221 doi: 10.1109/TPAMI.2018.2855738 [41] Schuller B W, Batliner A, Bergler C, Messner E M, Hamilton A, Amiriparian S, et al. The INTERSPEECH 2020 computational paralinguistics challenge: Elderly emotion, breathing & masks. In: Proceedings of the 21st Annual Conference of the International Speech Communication Association. Shanghai, China: ISCA, 2020. 2042−2046 [42] Zhou D X, Yang D, Zhang X H, Huang S, Feng S. Discriminative probabilistic latent semantic analysis with application to single sample face recognition. Neural Processing Letters, 2019, 49(3): 1273-1298 doi: 10.1007/s11063-018-9852-2 [43] Nie F P, Wang X Q, Jordan M I, Huang H. The constrained Laplacian rank algorithm for graph-based clustering. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence. Phoenix, USA: AAAI Press, 2016. 1969−1976 [44] Yang Z R, Oja E. Linear and nonlinear projective nonnegative matrix factorization. IEEE Transactions on Neural Networks, 2010, 21(5): 734-749 doi: 10.1109/TNN.2010.2041361 [45] Ding C, Li T, Jordan M I. Nonnegative matrix factorization for combinatorial optimization: Spectral clustering, graph matching, and clique finding. In: Proceedings of the 8th IEEE International Conference on Data Mining. Pisa, Italy: IEEE, 2008. 183−192 [46] Arora R, Gupta M R, Kapila A, Fazel M. Clustering by left-stochastic matrix factorization. In: Proceedings of the 28th International Conference on International Conference on Machine Learning. Bellevue, USA: Omnipress, 2011. 761−768 [47] Yang Z R, Hao T L, Dikmen O, Chen X, Oja E. Clustering by nonnegative matrix factorization using graph random walk. In: Proceedings of the 25th International Conference on Neural Information Processing Systems. Lake Tahoe, USA: Curran Associates Inc., 2012. 1079−1087 期刊类型引用(1)
1. 陈曼笙，任骊安，王昌栋，黄栋，赖剑煌. 基于混合阶相似性的多视图聚类:一个广义的视角. 计算机学报. 2024(07): 1453-1468 . 
百度学术其他类型引用(1)
-
下载:
计量
- 文章访问数: 1174
- HTML全文浏览量: 340
- PDF下载量: 171
- 被引次数: 2
