聚类问题可以分为两种思路：
- Compactness，这类有 K-means，GMM 等，但是这类算法只能处理凸集，为了处理非凸的样本集，必须引入核技巧。
- Connectivity，这类以谱聚类为代表。
如图1所示，上图为Compactness，下图为Connectivity
图1
谱聚类是一种基于带权重无向图的聚类方法。这个图用 表示，其中
，
，这里
就是边的权重，这里权重取为相似度，
是相似度矩阵，定义相似度（径向核）：
下面定义图的分割，这种分割就相当于聚类的结果。定义:
带权重的无向图--谱聚类
假设一共有个类别，对这个图进行分割：
于是，我们的目标就是 。
为了平衡每一类内部的权重不同，做归一化的操作，定义每一个集合的度，首先，对单个节点的度定义：
其次，每个集合：
于是：
谱聚类的模型就是：
引入指示向量：
其中，表示第
个样本属于第
个类别，记：
。
将N(CUT)写成对角矩阵的形式， 得到：
已知，求
，由于
，对于
，只在对角线上的
处为1，所以：
其中，表示有
个样本属于第
类，即
。
引入对角矩阵，根据 的定义
得到
对另一项
另外：
于是这个矩阵的第 项可以写为：
这个矩阵的对角线上的项和 相同，所以取迹后的取值不会变化。
所以：
其中， 叫做拉普拉斯矩阵。
网友评论