Soft Kernel Spectral Clustering

聚类

---

硬聚类在数据存在重叠(overlap)的时候，性能下降明显。软聚类/模糊聚类因此在很多领域非常流行。SKSC是基于KSC框架下的，改变了划分规则，以便于实现软聚类。新方法不需要再特征空间使用KMeans，只需要计算在投影空间计算出原型的中心，并计算余弦距离。新的模型选择方法称为average membership strength (AMS) 。

SKSC

SKSC先使用KSC获得数据的初始划分，通过重新计算特征变量空间的原型，改善划分。划分是用过比较每个点和原型之间的余弦距离实现的。不仅获得了更好的聚类效果，而且给研究的问题提供了更好的分解。算法流程如下：

软划分
不存在重叠的时候，数据在特征变量空间是共线的。这个理想的情况下使用硬划分即可。

如图所示，j一定是完全属于原型，i则不是完全属于原型了。如果有一个原型向量和i共线，那么i属于这个原型。如果不贡献，那么则i是应该使用软聚类了，看i与两个原型的余弦距离。

利用训练数据的投影$e_i^{(l)}, i=1,...,N_{tr}$，可以计算新的原型$s_1, ...,s_p,...s_k, s_p \in \mathbf R^{k-1}$

$$s_{p}={1\over n_{p}}\sum\limits_{i=1}^{n_{p}}e_{i}^{(l)}$$

$n_p$是KSC中划分给簇p的数量。然后可以计算数据点i和原型$s_p$之间的余弦距离

$$d_{ip}^{\cos}=1-e_{i}^{T}s_{p}/(\Vert e_{i}\Vert _{2}\Vert s_{p}\Vert _{2})$$

其中$e_i = [e_i^{(1)},...,e_i^{(k-1)}]$。余弦距离越小，表示越接近。那么数据点i对簇q的隶属度可以表示为：

$$cm_{i}^{(q)}={\prod_{j\neq q}d_{ij}^{\cos}\over {\sum}_{p=1}^{k}\prod_{j\neq p}d_{ij}^{\cos}}$$

显然有：$\sum _{p=1} ^k cm_i^p=1$。隶属度越大，那么i属于簇q的概率就越大，这可以认为是使用概率来实现软划分。如果k=2， 那就使用欧式距离，余弦距离隶属度会失效。

AMS
计算每个节点属于其类的概率。AMS的最大值对应的参数，即可认为是最优参数。

$${\rm AMS} ={1\over k}\sum\limits_{p=1}^{k}{1\over n_{p}}\sum\limits_{i=1}^{n_{p}}cm_{i}^{(p)}$$

实验

参考文献

Langone, R.; Mall, R.; Suykens, J.A.K, "Soft kernel spectral clustering" Neural Networks (IJCNN), The 2013 International Joint Conference on, 2013