19.谱聚类 - 《机器学习》

聚类问题可以分为两种思路：

Compactness，这类有 K-means，GMM 等，但是这类算法只能处理凸集，为了处理非凸的样本集，必须引入核技巧。
Connectivity，这类以谱聚类为代表。

谱聚类是一种基于无向带权图的聚类方法。这个图用 $19.谱聚类 - 图1$ #card=math&code=G%3D%28V%2CE%29&height=18&width=73#crop=0&crop=0&crop=1&crop=1&id=PpAer&originHeight=26&originWidth=102&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 表示，其中 $19.谱聚类 - 图2$ ， $19.谱聚类 - 图3$ ，这里 $19.谱聚类 - 图4$ 就是边的权重，这里权重取为相似度， $19.谱聚类 - 图5$ #card=math&code=W%3D%28w_%7Bij%7D%29&height=19&width=67#crop=0&crop=0&crop=1&crop=1&id=MZlbX&originHeight=27&originWidth=94&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 是相似度矩阵，定义相似度（径向核）：

$19.谱聚类 - 图6$ %3D%5Cexp(-%5Cfrac%7B%7C%7Cxi-x_j%7C%7C_2%5E2%7D%7B2%5Csigma%5E2%7D)%2C(i%2Cj)%5Cin%20E%5C%5C%0Aw%7Bij%7D%3D0%2C(i%2Cj)%5Cnotin%20E%0A#card=math&code=w%7Bij%7D%3Dk%28x_i%2Cx_j%29%3D%5Cexp%28-%5Cfrac%7B%7C%7Cx_i-x_j%7C%7C_2%5E2%7D%7B2%5Csigma%5E2%7D%29%2C%28i%2Cj%29%5Cin%20E%5C%5C%0Aw%7Bij%7D%3D0%2C%28i%2Cj%29%5Cnotin%20E%0A&height=63&width=643#crop=0&crop=0&crop=1&crop=1&id=rG2Mo&originHeight=89&originWidth=900&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

下面定义图的分割，这种分割就相当于聚类的结果。定义 $19.谱聚类 - 图7$ #card=math&code=w%28A%2CB%29&height=18&width=51#crop=0&crop=0&crop=1&crop=1&id=SYyh7&originHeight=26&originWidth=72&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)：

19.谱聚类 - 图8

假设一共有 $19.谱聚类 - 图9$ 个类别，对这个图的分割 $19.谱聚类 - 图10$ %3DCUT(A1%2CA_2%2C%5Ccdots%2CA_K)%3D%5Csum%5Climits%7Bk%3D1%7D%5EKw(Ak%2C%5Coverline%7BA_k%7D)%3D%5Csum%5Climits%7Bk%3D1%7D%5EK%5Bw(Ak%2CV)-w(A_k%2CA_k)%5D#card=math&code=CUT%28V%29%3DCUT%28A_1%2CA_2%2C%5Ccdots%2CA_K%29%3D%5Csum%5Climits%7Bk%3D1%7D%5EKw%28Ak%2C%5Coverline%7BA_k%7D%29%3D%5Csum%5Climits%7Bk%3D1%7D%5EK%5Bw%28A_k%2CV%29-w%28A_k%2CA_k%29%5D&height=47&width=522#crop=0&crop=0&crop=1&crop=1&id=GVtwa&originHeight=66&originWidth=730&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

于是，我们的目标就是 $19.谱聚类 - 图11$ #card=math&code=%5Cmin%5Climits_%7BA_k%7DCUT%28V%29&height=28&width=83#crop=0&crop=0&crop=1&crop=1&id=WtR1Q&originHeight=41&originWidth=117&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)。

为了平衡每一类内部的权重不同，我们做归一化的操作，定义每一个集合的度，首先，对单个节点的度定义：

$19.谱聚类 - 图12$

其次，每个集合：

$19.谱聚类 - 图13$ %3D%5Csum%5Climits%7Bi%5Cin%20A_k%7Dd_i%0A#card=math&code=%5CDelta_k%3Ddegree%28A_k%29%3D%5Csum%5Climits%7Bi%5Cin%20A_k%7Dd_i%0A&height=38&width=171#crop=0&crop=0&crop=1&crop=1&id=Jfjzx&originHeight=54&originWidth=240&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

于是：

$19.谱聚类 - 图14$ %3D%5Csum%5Climits%7Bk%3D1%7D%5EK%5Cfrac%7Bw(A_k%2C%5Coverline%7BA_k%7D)%7D%7B%5Csum%5Climits%7Bi%5Cin%20Ak%7Dd_i%7D%0A#card=math&code=N%28CUT%29%3D%5Csum%5Climits%7Bk%3D1%7D%5EK%5Cfrac%7Bw%28Ak%2C%5Coverline%7BA_k%7D%29%7D%7B%5Csum%5Climits%7Bi%5Cin%20A_k%7Dd_i%7D%0A&height=60&width=173#crop=0&crop=0&crop=1&crop=1&id=IEcls&originHeight=84&originWidth=243&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

所以目标函数就是最小化这个式子。

谱聚类的模型就是：

$19.谱聚类 - 图15$ %0A#card=math&code=%5C%7B%5Chat%7BA%7Dk%5C%7D%7Bk%3D1%7D%5EK%3D%5Cmathop%7Bargmin%7D_%7BA_k%7DN%28CUT%29%0A&height=34&width=183#crop=0&crop=0&crop=1&crop=1&id=zD5ny&originHeight=48&originWidth=257&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

引入指示向量：

$19.谱聚类 - 图16$

其中， $19.谱聚类 - 图17$ 表示第 $19.谱聚类 - 图18$ 个样本属于 $19.谱聚类 - 图19$ 个类别，记： $19.谱聚类 - 图20$ %5ET#card=math&code=Y%3D%28y_1%2Cy_2%2C%5Ccdots%2Cy_N%29%5ET&height=20&width=138#crop=0&crop=0&crop=1&crop=1&id=Wn1Sk&originHeight=29&originWidth=194&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)。所以：

$19.谱聚类 - 图21$ %0A#card=math&code=%5Chat%7BY%7D%3D%5Cmathop%7Bargmin%7D_YN%28CUT%29%0A&height=32&width=141#crop=0&crop=0&crop=1&crop=1&id=SNLGI&originHeight=45&originWidth=198&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

将 $19.谱聚类 - 图22$ #card=math&code=N%28CUT%29&height=18&width=57#crop=0&crop=0&crop=1&crop=1&id=jnK7G&originHeight=26&originWidth=82&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 写成对角矩阵的形式，于是：

$19.谱聚类 - 图23$ %26%3DTrace%5Bdiag(%5Cfrac%7Bw(A1%2C%5Coverline%7BA_1%7D)%7D%7B%5Csum%5Climits%7Bi%5Cin%20A1%7Dd_i%7D%2C%5Cfrac%7Bw(A_2%2C%5Coverline%7BA_2%7D)%7D%7B%5Csum%5Climits%7Bi%5Cin%20A2%7Dd_i%7D%2C%5Ccdots%2C%5Cfrac%7Bw(A_K%2C%5Coverline%7BA_K%7D)%7D%7B%5Csum%5Climits%7Bi%5Cin%20AK%7Dd_i%7D)%5D%5Cnonumber%5C%5C%0A%26%3DTrace%5Bdiag(w(A_1%2C%5Coverline%7BA_1%7D)%2Cw(A_2%2C%5Coverline%7BA_2%7D)%2C%5Ccdots%2Cw(A_K%2C%5Coverline%7BA_K%7D))%5Ccdot%20diag(%5Csum%5Climits%7Bi%5Cin%20A1%7Dd_i%2C%5Ccdots%2C%5Csum%5Climits%7Bi%5Cin%20AK%7Dd_i)%5E%7B-1%7D%5D%5Cnonumber%5C%5C%0A%26%3DTrace%5BO%5Ccdot%20P%5E%7B-1%7D%5D%0A%5Cend%7Balign%7D%0A#card=math&code=%5Cbegin%7Balign%7DN%28CUT%29%26%3DTrace%5Bdiag%28%5Cfrac%7Bw%28A_1%2C%5Coverline%7BA_1%7D%29%7D%7B%5Csum%5Climits%7Bi%5Cin%20A1%7Dd_i%7D%2C%5Cfrac%7Bw%28A_2%2C%5Coverline%7BA_2%7D%29%7D%7B%5Csum%5Climits%7Bi%5Cin%20A2%7Dd_i%7D%2C%5Ccdots%2C%5Cfrac%7Bw%28A_K%2C%5Coverline%7BA_K%7D%29%7D%7B%5Csum%5Climits%7Bi%5Cin%20AK%7Dd_i%7D%29%5D%5Cnonumber%5C%5C%0A%26%3DTrace%5Bdiag%28w%28A_1%2C%5Coverline%7BA_1%7D%29%2Cw%28A_2%2C%5Coverline%7BA_2%7D%29%2C%5Ccdots%2Cw%28A_K%2C%5Coverline%7BA_K%7D%29%29%5Ccdot%20diag%28%5Csum%5Climits%7Bi%5Cin%20A1%7Dd_i%2C%5Ccdots%2C%5Csum%5Climits%7Bi%5Cin%20A_K%7Dd_i%29%5E%7B-1%7D%5D%5Cnonumber%5C%5C%0A%26%3DTrace%5BO%5Ccdot%20P%5E%7B-1%7D%5D%0A%5Cend%7Balign%7D%0A&height=121&width=596#crop=0&crop=0&crop=1&crop=1&id=uI1DP&originHeight=170&originWidth=834&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

我们已经知道 $19.谱聚类 - 图24$ 这两个矩阵，我们希望求得 $19.谱聚类 - 图25$ 。

由于：

$19.谱聚类 - 图26$

对于 $19.谱聚类 - 图27$ ，只在对角线上的 $19.谱聚类 - 图28$ 处为 1，所以：

$19.谱聚类 - 图29$ %0A#card=math&code=Y%5ETY%3Ddiag%28N_1%2CN_2%2C%5Ccdots%2CN_K%29%0A&height=20&width=193#crop=0&crop=0&crop=1&crop=1&id=FuF81&originHeight=29&originWidth=270&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

其中， $19.谱聚类 - 图30$ 表示有 $19.谱聚类 - 图31$ 个样本属于 $19.谱聚类 - 图32$ ，即 $19.谱聚类 - 图33$ 。

引入对角矩阵，根据 $19.谱聚类 - 图34$ 的定义， $19.谱聚类 - 图35$ %3Ddiag(w%7BNN%7D%5Cmathbb%7BI%7D%7BN1%7D)#card=math&code=D%3Ddiag%28d1%2Cd_2%2C%5Ccdots%2Cd_N%29%3Ddiag%28w%7BNN%7D%5Cmathbb%7BI%7D_%7BN1%7D%29&height=18&width=272#crop=0&crop=0&crop=1&crop=1&id=zo2jO&originHeight=26&originWidth=381&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)，于是：

$19.谱聚类 - 图36$

对另一项

$19.谱聚类 - 图38$ )-diag(w(Ai%2CA_i))%3Ddiag(%5Csum%5Climits%7Bj%5Cin%20Ai%7Dd_j)-diag(w(A_i%2CA_i))%0A#card=math&code=O%3Ddiag%28w%28A_i%2CV%29%29-diag%28w%28A_i%2CA_i%29%29%3Ddiag%28%5Csum%5Climits%7Bj%5Cin%20A_i%7Dd_j%29-diag%28w%28A_i%2CA_i%29%29%0A&height=38&width=466#crop=0&crop=0&crop=1&crop=1&id=l6FAE&originHeight=54&originWidth=653&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)

其中，第一项已知，第二项可以写成 $19.谱聚类 - 图39$ ，这是由于：

$19.谱聚类 - 图40$

于是这个矩阵的第 $19.谱聚类 - 图41$ 项可以写为：

$19.谱聚类 - 图42$

这个矩阵的对角线上的项和 $19.谱聚类 - 图43$ #card=math&code=w%28A_i%2CA_i%29&height=18&width=61#crop=0&crop=0&crop=1&crop=1&id=WeFWo&originHeight=26&originWidth=86&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 相同，所以取迹后的取值不会变化。

所以：

其中， $19.谱聚类 - 图45$ 叫做拉普拉斯矩阵。