#0.论文信息

• 标题：Fast adaptively balanced min-cut clustering
• 期刊：Pattern Recognition
• 作者: Feiping Nie , Fangyuan Xie , Jingyu Wang ,Xuelong Li
• 机构: China Telecom, Northwestern Polytechnic al University.
• 代码链接：

#1.摘要

最小切割聚类是一种典型的图聚类方法，已厂泛应用于模式识别、数据分析和图像处理。然而，最小切割有平凡解，这导致了倾斜的聚类性能。谱聚类（SC）通过将指标矩阵放松为连续嵌入，然后离散嵌入来缓解这一问题。然而，SC存在两个主要的挑战，即高计算复杂度和两阶段过程。为了解决这些问题，本文提出了一种快速自适应平衡最小割聚类模型（FBMC），该模型直接求解离散指标矩阵，不需要任何后处理。我们利用二部图来加速亲和图的构造和优化过程。此外，在模型中加入了平衡因子，可以缓解聚类结果的偏差。提出了两种具体的方法，一种在所有集群中添加一个平衡因子，另一种将平衡因子分别分配给每个集群，称为FBMC1和FBMC2。此外，对FBMC1和FBMC2提出了一步优化问题，其复杂度为线性的。

#2.实验结果

Table3 ACC±Standard deviation(%)ofcompared methods on benchmark datasets.

Table 4 NMI± Standard deviation(%)of compared methods on benchmark datasets

Fig.3.ACCvaries with No.of anchor points and neighbors for F BMC 2.（a)CAL16.(b)CAL28.（c) COIL100.（d) Connect4.（e)ISO5.(f)PAL25.(g)Protein.(h)YaleB.

Fig.1.The change of objective function valuewith the number of iteration.（a)COIL20.(b)COIL20_0.01.©MSRA25.（d)MSRA25_0.01.

Table1 Comparison for S BMC,EBM Can dour proposed method

#3.主要贡献

-我们提出了一种快速自适应平衡的最小切割聚类，旨在最大限度地提高簇内相似性，可以作为最小切割聚类的替代方法。该方法采用了锚定图，从而降低了计算的复杂度。

-通过引入平衡因子，所提出的模型考虑了聚类的平衡，从而避免了最小切割聚类中的平凡解问题。平衡因子的计算是自适应的，模型是无参数的。

-提出了一种单步优化方法来解决优化问题。此外，在我们提出的模型中，离散指标矩阵直接通过坐标下降法求解，不需要任何后处理操作，其复杂度为线性时间。

#4.方法

3.Proposed methodology The proposed unified framework is illustrated as follows ${\min }_{F\in \mathrm{Ind},A\in Diag}{\Vert B^{T}B-FA{F}^T\Vert }_F^2$
where A = d i a g { λ 1 , λ 2 , … , λ c } , λ j > 0 , j = 1 , 2 , … , c . A {\cal{A}}\,=\,d i a g\{\lambda_{1},\lambda_{2},\ldots,\lambda_{c}\},\lambda_{j}\,>\,0,j\,=\,1,2,\ldots,c.\ {\cal{A}} A=diag{λ1​,λ2​,…,λc​},λj​>0,j=1,2,…,c. A is a diagonal matrix composed of balanced factors.When $\Lambda =\lambda I_c$ ,theproblem degradesto

$$\underset{F\in \mathrm{Ind},\lambda >0}{\min }{\Vert B^{T}B-\lambda F{F}^T\Vert }_F^2.$$

When $\exists i\ne j,{\lambda }_i\ne {\lambda }_j,$ the optimization problem is

$$\underset{F\in \mathrm{Ind},A\in Diag,\exists i\ne j,{\lambda }_i\ne {\lambda }_j}{\min }{\Vert B^{T}B-FA{F}^T\Vert }_F^2.$$

Through the adaptive balanced factors in problem(9)and（10),the final clustering results would achieve high within-cluster similarity and avoid unbalanced clustering outcomes.Infact, $A$ could be extended to any symmetric matrix,resulting in the following problem

$$\underset{F\in \mathrm{Ind},A=A^T}{\min }{\Vert B^{T}B-FA{F}^T\Vert }_F^2.$$

Problem（9)could be formulated as the following form and we denote the objective function as $J_1$

$$\max J_1(F,\lambda )=\underset{F\in \mathrm{Ind},\lambda >0}{\max }2\lambda \mathrm{Tr}\left(F^T{B}^{T}BF\right)-{\lambda }^2\Vert F{\Vert }_e.$$

By taking the partial derivative of $\lambda$ the expression for the optimal valueof $\lambda$ can be obtained as follows

$$\lambda =\frac{\mathrm{Tr}\left(F^T{B}^{T}BF\right)}{\mathrm{Tr}\left(F^T{1}_n{1}_n^{T}F\right)}.$$

From the expression of $\lambda$ it can be seen that the higher the similarity within the clusters and the more balanced the clustering results,the smaller the value of $\lambda$ From problem(4),a small value of $\lambda$ indicatesa bigvalue of $\gamma$ which shows that the balancing term plays a more sig n if i cant role.By substituting the expression of $\lambda$ in $J_1$ the formulation of $J_1$ becomes

$$\mathrm{ax}{J}_1(F)=\underset{F\in \mathrm{Ind}}{\max }\frac{{\left(\mathrm{Tr}\left(F^T{B}^{T}BF\right)\right)}^2}{\mathrm{Tr}\left(F^T{1}_n{1}_n^{T}F\right)}=\underset{F\in \mathrm{Ind}}{\max }\frac{{\left({\sum }_{j=1}^c{\mathbf{f}}_j^T{B}^{T}B{\mathbf{f}}_j\right)}^2}{{\sum }_{j=1}^c{\mathbf{f}}_j^T{1}_n{1}_n^T{\mathbf{f}}_j}.$$
For $F^{(0)}$ 1， $f_{ip}^{(0)}=1$ While as for $F^{(l)}$ $f_{il}^{(l)}=1$ Thus, when $l\ne p$ , the pth and /th column are different for $F^{(0)}$ and $F^{(l)}$ When ,they are $l=p$ the same.Thus,the calculation of $J_1(F^{(l)})$ is discussed in two cases.

Case1:When $l\ne p$ thevalueof $J_1(F^{(l)})$ is

$$J_1(F^{(l)})=\frac{{\left({\sum }_{j=1}^c{\mathbf{f}}_j^{(l)T}{B}^{T}B{\mathbf{f}}_j^{(l)}\right)}^2}{{\sum }_{j=1}^c{\mathbf{f}}_j^{(l)T}{1}_n{1}_n^T{\mathbf{f}}_j^{(l)}}.$$

Wedefine Ω = { j ∣ j = 1 , 2 , … , c } \varOmega\,=\,\{j|j\,=\,1,2,\dotsc,c\} Ω={j∣j=1,2,…,c} and Ω ( l ) = { j ∣ j = 1 , 2 , … , c , j ≠ \Omega^{(l)}\,=\,\{j|j\,=\,1,2,\dots,c,j\,\neq\, Ω(l)={j∣j=1,2,…,c,j= toexpress more clearly.Since the columns of $F^{(0)}$ and $F^{(l)}$ are $l,j\ne p\}$ the same expect/th and pth column, $J_1(F^{(l)})$ can also be written as

$$\frac{{\left({\sum }_{j\in {\Omega }^{(l)}}{\mathbf{f}}_j^{(0)T}{B}^{T}B{\mathbf{f}}_j^{(0)}+{\mathbf{f}}_l^{(l)T}{B}^{T}B{\mathbf{f}}_l^{(l)}+{\mathbf{f}}_p^{(l)T}{B}^{T}B{\mathbf{f}}_p^{(l)}\right)}^2}{{\sum }_{j\in {\Omega }^{(l)}}{\mathbf{f}}_j^{(0)T}{1}_n{1}_n^T{\mathbf{f}}_j^{(0)}+{\mathbf{f}}_l^{(l)T}{1}_n{1}_n^T{\mathbf{f}}_l^{(l)}+{\mathbf{f}}_p^{(l)T}{1}_n{1}_n^T{\mathbf{f}}_p^{(l)}}.$$

By observing ${\mathbf{f}}_l^{(l)}$ and ${\mathbf{f}}_l^{(0)}$ ，itisfound that theyonly differ in the it h element, that is ${\mathbf{f}}_{il}^{(l)}=1$ and ${\mathbf{f}}_{il}^{(0)}=0$ . Thus, ${\mathbf{f}}_l^{(l)}={\mathbf{f}}_l^{(0)}+{\mathbf{e}}_i,$ where ${\mathbf{e}}_i$ is a column vector with its $i\mathbf{th}$ elementas ${}^1$ and others a sO.Then,for ${\mathbf{f}}_l^{(l)T}{B}^{T}B{\mathbf{f}}_l^{(l)}$ and ${\mathbf{f}}_l^{(l)T}{1}_n{1}_n^T{\mathbf{f}}_l^{(l)}$ wehave

$$\begin{array}{rl}& {\mathbf{f}}_l^{(l)T}{B}^{T}B{\mathbf{f}}_l^{(l)}={\left({\mathbf{f}}_l^{(0)}+{\mathbf{e}}_i\right)}^T{B}^{T}B\left({\mathbf{f}}_l^{(0)}+{\mathbf{e}}_i\right)\\ & ={\mathbf{f}}_l^{(0)T}{B}^{T}B{\mathbf{f}}_l^{(0)}+2{\mathbf{b}}_i^{T}B{\mathbf{f}}_l^{(0)}+{\mathbf{b}}_i^T{\mathbf{b}}_i.\\ & {\mathbf{f}}_l^{(l)T}{1}_n{1}_n^T{\mathbf{f}}_l^{(l)}={\left({\mathbf{f}}_l^{(0)}+{\mathbf{e}}_i\right)}^T{1}_n{1}_n^T\left({\mathbf{f}}_l^{(0)}+{\mathbf{e}}_i\right)\\ & ={\mathbf{f}}_l^{(0)T}{1}_n{1}_n^T{\mathbf{f}}_l^{(0)}+21_n^T{\mathbf{f}}_l^{(0)}+1.\end{array}$$
$$\begin{array}{rl}& {\mathbf{f}}_p^{(I)T}{B}^{T}B{\mathbf{f}}_p^{(I)}={\left({\mathbf{f}}_p^{(0)}-{\mathbf{e}}_i\right)}^T{B}^{T}B\left({\mathbf{f}}_p^{(0)}-{\mathbf{e}}_i\right)\\ & ={\mathbf{f}}_p^{(0)T}{B}^{T}B{\mathbf{f}}_p^{(0)}-2{\mathbf{b}}_i^{T}B{\mathbf{f}}_p^{(0)}+{\mathbf{b}}_i^T{\mathbf{b}}_i,\\ & {\mathbf{f}}_p^{(I)T}{1}_n{1}_n^T{\mathbf{f}}_p^{(I)}={\left({\mathbf{f}}_p^{(0)}-{\mathbf{e}}_i\right)}^T{1}_n{1}_n^T\left({\mathbf{f}}_p^{(0)}-{\mathbf{e}}_i\right)\\ & ={\mathbf{f}}_p^{(0)T}{1}_n{1}_n^T{\mathbf{f}}_p^{(0)}-21_n^T{\mathbf{f}}_p^{(0)}+1.\end{array}$$

TakeEqs.(18)-(21) intoEq.(17), $J_1(F^{(l)})$ becomes

$$\frac{{\left({\sum }_{j\in \Omega }{\mathbf{f}}_j^{(0)T}{\mathbf{B}}^T\mathbf{B}{\mathbf{f}}_j^{(0)}+2{\mathbf{b}}_i^T\mathbf{B}{\mathbf{f}}_l^{(0)}-2{\mathbf{b}}_i^T\mathbf{B}{\mathbf{f}}_p^{(0)}+2{\mathbf{b}}_i^T{\mathbf{b}}_i\right)}^2}{{\sum }_{j\in \Omega }{\mathbf{f}}_j^{(0)T}{1}_n{1}_n^T{\mathbf{f}}_j^{(0)}+21_n^T{\mathbf{f}}_l^{(0)}-21_n^T{\mathbf{f}}_p^{(0)}+2}.$$

Case2:When $l=p$ the value of objective function is

$$J_1(F^{(l)})=\frac{{\left(\mathrm{Tr}\left(F^{(0)T}{B}^{T}B{F}^{(0)}\right)\right)}^2}{\mathrm{Tr}\left(F^{(0)T}{1}_n{1}_n^T{F}^{(0)}\right)}.$$

We denote u as the value of objective function when we update it h row and $I\mathrm{th}$ column. Considering that when $l\ne p$ ， $f_{il}^{(0)}=0$ and when $l=p$ thevalueof $f_{il}$ is ${}^1$ U can be written in a unified form:

$$\frac{{\left(\mathrm{Tr}(F^{(0)T}{B}^{T}B{F}^{(0)})+2{\mathbf{b}}_i^T(1-f_{il}^{(0)})(B{\mathbf{f}}_l^{(0)}-B{\mathbf{f}}_p^{(0)}+{\mathbf{b}}_i)\right)}^2}{\mathrm{Tr}\left(F^{(0)T}{1}_n{1}_n^T{F}^{(0)}\right)+2(1-f_{il}^{(0)})(1_n^T{\mathbf{f}}_l^{(0)}-1_n^T{\mathbf{f}}_p^{(0)}+1)}.$$
From formula(24),there are five elements needed to be stored in advance,whichare $\mathrm{Tr}(F^{(0)I}{B}^{I}B{F}^{(0)}),\mathrm{Tr}(F^{(0)I}{1}_n{1}_n^T{F}^{(0)}),B{F}^{(0)},1_n^T{F}^{(0)}$ and ${\mathbf{b}}_i^T{\mathbf{b}}_i,i=1,2,\dots ,n.$ Since ${\mathbf{b}}_i^T{\mathbf{b}}_i,i=1,2,\dots ,n$ is not changed at all there is no need to update it.After obtaining the new ${\mathbf{f}}^{\iota }$ ,otherfour elements do not need to update as well if $q=p$ However,if $q\ne p$ the optimal $F^{(q)}$ would replace $F^{(0)}$ and these four elements should be updated for the update of next row.Based on the above analysis we do not need tore calculate the values of these elements,which can be updated by pre-stored variables.The updating formulations are exhibited below

$$\begin{array}{rl}& \mathrm{Tr}(F^{(0)T}{B}^{T}B{F}^{(0)})\leftarrow \mathrm{Tr}(F^{(0)T}{B}^{T}B{F}^{(0)})+2{\mathbf{b}}_i^{T}B{\mathbf{f}}_q^{(0)}\\ & -2{\mathbf{b}}_i^{T}B{F}_p^{(0)}+2{\mathbf{b}}_i^T{\mathbf{b}}_i\\ & \mathrm{Tr}(F^{(0)T}{1}_n^T{F}^{(0)})\leftarrow \mathrm{Tr}(F^{(0)T}{1}_n^T{F}^{(0)})+21_n^T{\mathbf{f}}_q^{(0)}\\ & -21_n^T{F}_p^{(0)}+2\\ & B{F}^{(0)}(:,q)\leftarrow B{F}^{(0)}(:,q)+B(:,i)\\ & B{F}^{(0)}(:,p)+B{F}^{(0)}(:,p)-B(:,i)\\ & 1_n^T{F}^{(0)}(q)\leftarrow 1_n^T{F}^{(0)}(q)+1\\ & 1_n^T{F}^{(0)}(p)\leftarrow 1_n^T{F}^{(0)}(p)-1\end{array}$$

It is worth noting that when updating $\mathrm{Tr}({\mathcal{F}}^{(0)T}{B}^{T}B{\mathcal{F}}^{(0)})$ and $\mathrm{Tr}(F^{(0)T}{1}_n{1}_n^T{F}^{(0)})$ , several elements such as $B{\mathbf{f}}_l^{(0)}$ ， $B{\mathbf{f}}_p^{(0)}$ ， $1_n{1}_n^T$ and $1_n^T{\mathbf{f}}_p$ can betaken from the corresponding values in $B{F}^{(0)}$ and $1_n^T{F}^{(0)}$ directly.

#5.总结&限制性

在本文中，我们提出了一种快速目适应平衡最小切割（FBMC）聚类方法，旨在最大化聚类内的相似性和平衡聚类结果。由SBMC和EBMC提出了两种具体的方法，分别命名为FBMC1和FBMC2。与最小切割聚类相比，FBMC没有平凡的解，且复杂度随时间呈线性关系。此外，FBMC1和FBMC2的优化算法是一步一步的，没有额外的超参数。而离散指标矩阵则可以用CD法直接求解，而不需要进行任何后处理。综合实验结果表明了FBMC1和FBMC2的优越性。然而，当在FBMC1和FBMC2中构造二部图时，需要邻居的数量作为一个已知的参数。快速准确地确定该参数是今后研究的一个方向。此外，在这两种方法中，在构造二部图后，仍然需要构造一个全连通图，这可能是不必要的。在未来，我们将关注的重点是从二部图中直接挖掘出聚类信息。