机器学习（六）K-means聚类、密度聚类、层次聚类、谱聚类

本文主要简述聚类算法族。聚类算法与前面文章的算法不同，它们属于非监督学习。

1、K-means聚类

记k个簇中心，为(mu_{1}),(mu_{2}),...,(mu_{k}),每个簇的样本数为(N_{i})
假设每个簇中的数据都满足分布(N(mu_{i},sigma))，即方差相同，均值不同的GMM。
则每一个样本点的分布函数为：$$phi_{i}=dfrac{1}{sqrt{2pisigma^{2}}exp(-dfrac{({x_{i}-mu})}2}{2sigma^2})$$
可求出其似然函数

[L_{mu}=phi_{1} imesphi_{2} imes... ]

且可求其对数似然为(以三个点为例)

[l_{mu}=dfrac{1}{2}sum^{k}_{j=1}sum^{i=1}_{N_{j}}(x_{I}-mu_{j})^2 ]

求驻点有：$$mu_{j}=dfrac{1}{N_{j}}sum^{N}{i=1}x{i}$$
因此，以均方误差为目标函数的时候肯定是收敛的。用其他函数作为目标函数不一定收敛。

注：(k)的选择采用“手肘法”，注意不是交叉验证，它连标签都没有！

2、密度聚类

代表算法：DBSCAN

K-means对噪声敏感，密度聚类对噪声不敏感。

3、层次聚类

按层次聚类，由上至下或由下至上，优点是可以任意选择聚类数

4、谱聚类

Step1:对样本点俩俩计算相似度(S_{ij}),组成相似度矩阵，又称权值矩阵$$W_{n imes n}=[S_{ij}]$$

Step2:将(W_{n imes n})的主对角线元素全部置为0，把每行元素的值相加，第(i)行的和为(d_{i})。将(d_{i})作为主对角线元素组成(D_{n imes n})

Step3:令$$L_{n imes n}=D_{n imes n}-W_{n imes n}$$，称为拉普拉斯矩
阵。这个(L)是半正定的，它最小的特征值为0。

Step4:求L矩阵的特征值和特征向量，将所有特征值从小大排列，取出前k个（聚类数为k），将其对应的特征向量如下排列：$$[u_{1},u{2},...,u_{k}]$$该矩阵的第一行即为第一个样本点转换后的特征，第二行为第二个样本点转换后的特征。将这些特征扔入K_means，其聚类结果即是谱聚类结果。