Paper: Clustering and Projected Clustering with Adaptive Neighbors

简介

  • 提出一个新的框架使得相似度度量和聚类在一步完成

  • 对拉普拉斯矩阵中的相似度矩阵进行秩约束,维持聚类结构

  • 提出 PCAN 处理高维数据

CAN 结构

首先,更小的距离应该有更大的邻近概率:

$$ \min _{\forall i, s_{i}^{T} 1=1,0 \leq s_{i} \leq 1} \sum_{i, j=1}^{n}\left(\left\|x_{i}-x_{j}\right\|_{2}^{2} s_{i j}+\gamma s_{i j}^{2}\right) \tag{1} $$
后一项属于正则化项,在不考虑数据距离信息前提下,数据中任何一个点和$x_i$的距离都是$\frac{1}{n}$,作为先验概率分布。

定义 $ d_{i j}^{x}=\left|x_{i}-x_{j}\right|_{2}^{2} $, 则公式$(1)$可写为:

$$ \min _{\forall i, s_{i}^{T} 1=1,0 \leq s_{i} \leq 1}\left\|s_{i}+\frac{1}{2 \gamma} d_{i}^{x}\right\|_{2}^{2} \tag{2} $$
由于矩阵$S \in \mathbb{R}^{n \times n} $​ 中保留了每个节点的邻近概率,可以将其看作图的相似矩阵,每个节点$i$​​ 赋值为$ f_{i} \in \mathbb{R}^{c \times 1} $​​​,可以得到下式:

$$ \sum_{i, j=1}^{n}\left|f_{i}-f_{j}\right|_{2}^{2} s_{i j}=2 \operatorname{Tr}\left(F^{T} L_{S} F\right) \tag{3} $$

其中的$\operatorname{Tr}()$​​ 为 trace,即矩阵的迹,代表矩阵主对角线上各个元素的总和。$L_S$为拉普拉斯矩阵,计算公式为:

$$ L_S = D_S - \frac{S^T + S}{2} $$

其中$D_S$为相似矩阵的度矩阵。

如果相似矩阵非负,那么这个拉普拉斯矩阵满足一个重要的性质,这个性质也可以在聂飞平教授的其他聚类文章中可以找到:

Theorem 1. The multiplicity c of the eigenvalue 0 of the Laplacian matrix LS is equal to the number of connected components in the graph with the similarity matrix S.

因此,我们可以通过约束$rank(L_S)=n - c$得到很好的聚类结构。类比常见的$K-means$算法,

k-means算法流程

可以看出$k-means$通过不断的计算距离(性能度量)和更新簇,达到保持$k$​ 个聚类中心的一个稳定聚类结构的目的。而本文该定理直接使得本文算法拥有一个稳定聚类结构。

根据该定理并且结合$(1)$​ 式,得出:

$$ \begin{aligned} &J_{o p t}=\min _{S} \sum_{i, j=1}^{n}\left(\left\|x_{i}-x_{j}\right\|_{2}^{2} s_{i j}+\gamma s_{i j}^{2}\right) \\ &\text { s.t. } \quad \forall i, s_{i}^{T} 1=1,0 \leq s_{i} \leq 1, \operatorname{rank}\left(L_{S}\right)=n-c \end{aligned} \tag{4} $$
设 $\sigma_{i}\left(L_{S}\right)$ 是 $L_{S}$ 最小的第 $i$ 个特征值, 且因为 $L_{S}$ 为半正定的, $\sigma_{i}\left(L_{S}\right) \geq 0$ 。 则可引入一个足够大的 $\lambda$, 将 $(4)$ 式转化为: $$ \begin{aligned} &\min _{S} \sum_{i, j=1}^{n}\left(\left\|x_{i}-x_{j}\right\|_{2}^{2} s_{i j}+\gamma s_{i j}^{2}\right)+2 \lambda \sum_{i=1}^{c} \sigma_{i}\left(L_{S}\right) \\ &\text { s.t. } \quad \forall i, s_{i}^{T} \mathbf{1}=1,0 \leq s_{i} \leq 1 \end{aligned}\tag{5} $$ 根据Ky Fan​定理,可以得到: $$ \sum_{i=1}^{c} \sigma_{i}\left(L_{S}\right)=\min _{F \in \mathbb{R}^{n} \times c, F^{T} F=I} \operatorname{Tr}\left(F^{T} L_{S} F\right) \tag{6} $$ 则$(5)$式可以写为: $$ \begin{aligned} &\min _{S, F} \sum_{i, j=1}^{n}\left(\left\|x_{i}-x_{j}\right\|_{2}^{2} s_{i j}+\gamma s_{i j}^{2}\right)+2 \lambda \operatorname{Tr}\left(F^{T} L_{S} F\right) \\ &\text { s.t. } \quad \forall i, s_{i}^{T} \mathbf{1}=1,0 \leq s_{i} \leq 1, F \in R^{n \times c}, F^{T} F=I \end{aligned} \tag{7} $$ 先固定$S$,则只需要解决: $$ \min _{F \in \mathbb{R}^{n \times \subset}, F^{T} F=I} \operatorname{Tr}\left(F^{T} L_{S} F\right) \tag{8} $$ 其中的$F$​为$L_S$​的最小的前$c$​个特征向量,于是可以固定$F$​​,得到下式: $$ \begin{aligned} &\min _{S} \sum_{i, j=1}^{n}\left(\left\|x_{i}-x_{j}\right\|_{2}^{2} s_{i j}+\gamma s_{i j}^{2}\right)+2 \lambda \operatorname{Tr}\left(F^{T} L_{S} F\right) \\ &\text { s.t. } \quad \forall i, s_{i}^{T} \mathbf{1}=1,0 \leq s_{i} \leq 1 \end{aligned} \tag{9} $$

根据$(3)$式,可得:

$$ \begin{aligned} &\min _{S} \sum_{i, j=1}^{n}\left(\left\|x_{i}-x_{j}\right\|_{2}^{2} s_{i j}+\gamma s_{i j}^{2}+\lambda\left\|f_{i}-f_{j}\right\|_{2}^{2} s_{i j}\right) \\ &\text { s.t. } \quad \forall i, s_{i}^{T} 1=1,0 \leq s_{i} \leq 1 \end{aligned} \tag{10} $$
注意 $d_{i j}=d_{i j}^{x}+\lambda d_{i j}^{f}$, 其中 $d_{i j}^{x}=\left\|x_{i}-x_{j}\right\|_{2}^{2}, d_{i j}^{f}=\left\|f_{i}-f_{j}\right\|_{2}^{2}$ 。根据 $(2)$ 式, 有: $$ \min _{\forall i, s_{i}^{T} 1=1,0 \leq s_{i} \leq 1}\left\|s_{i}+\frac{1}{2 \gamma} d_{i}\right\|_{2}^{2} \tag{11} $$ 其中 $s_{i}$ 和 $d_{i}$ 分别为 $S$ 和 $d_{i j}$ 的第 $i$​ 列向量。

算法具体流程为:

image-20210816205020788

超参数确定

超参数$\gamma$值域为$[0,\infty]$,很难确定其具体值。

$(2)$式的拉格朗日函数为:

$$ \mathcal{L}\left(s_{i}, \eta, \beta_{i}\right)=\frac{1}{2}\left|s_{i}+\frac{d_{i}^{x}}{2 \gamma_{i}}\right|_{2}^{2}-\eta\left(s_{i}^{T} \mathbf{1}-1\right)-\beta_{i}^{T} s_{i} $$

根据 KKT 算法,可知:

$$ s_{i j}=\frac{-d_{i j}^{x}}{2 \gamma_{i}}+\eta+\beta_{i j} $$

在学习过程中,只有$x_i$节点附近的$k$个节点能连接到$x_i$,假设$d_{i 1}^{x}, d_{i 2}^{x}, \ldots, d_{i n}^{x}$​ 是从小到大排列的,因此根据上式,可以得到$s_{ik} > 0, s_{i,k+1}=0$​,即

$$ \left\{\begin{array}{c} -\frac{d_{i k}^{x}}{2 \gamma_{i}}+\eta>0 \\ -\frac{d_{i, k}^{x}}{2 \gamma_{i}}+\eta \leq 0 \end{array}\right. $$
根据上式和$s_{i}^{T} \mathbf{1}=1$,可以得到: $$ \begin{aligned} &\sum_{j=1}^{k}\left(-\frac{d_{i j}^{x}}{2 \gamma_{i}}+\eta+\beta_{i j}\right)=1 \\ &\Leftrightarrow \eta+\beta_{i j}=\frac{1}{k}+\frac{1}{2 k \gamma_{i}} \sum_{j=1}^{k} d_{i j}^{x} \end{aligned} $$ 为了得到含有$k$个非零元素的最优解$s_i$​,我们可以将$\gamma_i$设为: $$ \begin{gathered} \frac{k}{2} d_{i k}^{x}-\frac{1}{2} \sum_{j=1}^{k} d_{i j}^{x}<\gamma_{i} \leq \frac{k}{2} d_{i, k+1}^{x}-\frac{1}{2} \sum_{j=1}^{k} d_{i j}^{x} \\ \gamma_{i}=\frac{k}{2} d_{i, k+1}^{x}-\frac{1}{2} \sum_{j=1}^{k} d_{i j}^{x} \end{gathered} $$ 因此总体的$\gamma$应该是$\gamma_{1}, \gamma_{2}, \ldots, \gamma_{n}$的平均数,即: $$ \gamma=\frac{1}{n} \sum_{i=1}^{n}\left(\frac{k}{2} d_{i, k+1}^{x}-\frac{1}{2} \sum_{j=1}^{k} d_{i j}^{x}\right) $$ 这样对于$\gamma$的调参就变成了对邻近数$k$的调参,效率大大提升。

代码部分解析

can.m文件为主要部分,该算法在其中体现的很好:

1
function [y, A, evs] = CAN(X, c, k, r, islocal)

在函数定义中,$X$对应数据矩阵,$c$对应聚类数目,$k$对应邻近数,$r$对应超参数,其他参数在代码中都有详细标注。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
distX = L2_distance_1(X,X);
%distX = sqrt(distX);
[distX1, idx] = sort(distX,2);
A = zeros(num);
rr = zeros(num,1);
for i = 1:num
    di = distX1(i,2:k+2);
    rr(i) = 0.5*(k*di(k+1)-sum(di(1:k)));
    id = idx(i,2:k+2);
    A(i,id) = (di(k+1)-di)/(k*di(k+1)-sum(di(1:k))+eps);
end;

if r <= 0
    r = mean(rr);
end;
lambda = mean(rr);

A0 = (A+A')/2;
D0 = diag(sum(A0));
L0 = D0 - A0;
[F, temp, evs]=eig1(L0, c, 0);]
% evs为前idx个特征值

这一部分主要是确定初始参数,值得称赞的是,变量定义和文章中的相差不多。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
for iter = 1:NITER
    distf = L2_distance_1(F',F');
    A = zeros(num);
    for i=1:num
        if islocal == 1
            idxa0 = idx(i,2:k+1);
        else
            idxa0 = 1:num;
        end;
        dfi = distf(i,idxa0);
        dxi = distX(i,idxa0);
        ad = -(dxi+lambda*dfi)/(2*r);
        A(i,idxa0) = EProjSimplex_new(ad);
    end;

    A = (A+A')/2;
    D = diag(sum(A));
    L = D-A;
    F_old = F;
    [F, temp, ev]=eig1(L, c, 0);
    evs(:,iter+1) = ev;

    fn1 = sum(ev(1:c));
    fn2 = sum(ev(1:c+1));
    if fn1 > 0.00000000001
        lambda = 2*lambda;
    elseif fn2 < 0.00000000001
        lambda = lambda/2;  F = F_old;
    else
        break;
    end;

end;

这一部分就是在确定了基本参数的基础上,不断迭代,从而得到更好地效果。

1
2
3
4
if fn1 > 0.00000000001
        lambda = 2*lambda;
    elseif fn2 < 0.00000000001
        lambda = lambda/2;  F = F_old;

尤其是其中的这一部分,在论文下注中有提到是一个为了加速而不断学习$\lambda$值的过程。如果当前的连通分量小于$c$,则增加$\lambda$​ 值,反之亦然。

三种数据的效果如下:

image-20210816212431621

image-20210816212516719

image-20210816212540156


引用

updatedupdated2021-08-162021-08-16