图解机器学习/第十四章 聚类

聚类是无监督机器学习方法的一种。

K均值聚类

K均值聚类的算法流程：

1. 给各个簇中心$\mu_1,\dots,\mu_c$以适当的初值

2. 更新样本$x_1,\dots,x_n$对应的簇标签$y_1,\dots,y_n$

   $$y_i \leftarrow \mathop{argmin}_{y\in \lbrace 1,\dots,c \rbrace}||x_i - \mu_y||^2,i=1,\dots,n$$

3. 更新各个簇中心$\mu_1,\dots,\mu_c$

   $$\mu_y \leftarrow \frac{1}{n_y}\sum_{i:y_i=y}x_i,y=1,\dots,c$$

   上式中，$n_y$为属于簇$y$的样本总数

4. 直到簇标签达到收敛精度为止，重复上述2、3步的计算。

核K均值聚类

由于K均值聚类是依据欧氏距离的大小来决定样本所属的簇，因此只能处理线性可分的聚类问题。利用核映射的方法就可以得到处理非线性可分的聚类问题的核K均值聚类算法。

具体而言，首先把欧氏距离的平方$||x-\mu_y||^2$用样本间的内积$\langle x,x’ \rangle$来表示

$$||x-\mu_y||^2=||x - \frac{1}{n_y}\sum_{i:y_i=y}x_i||^2=\langle x,x \rangle - \frac{1}{n_y}\sum_{i:y_i=y}\langle x,x_i \rangle \frac{1}{n_y^2} \sum_{i,i':y_i=y_{i'}=y} \langle x,x_{i'} \rangle$$

将上式內积置换为核函数$K(x,x’)$，就变成了核K均值聚类算法

$$y \leftarrow \mathop{argmin}_{y \in \lbrace1,\dots,c \rbrace}[- \frac{2}{n_y}\sum_{i:y_i=y} K(x,x_i) + \frac{1}{n_y^2}\sum_{i,i':y_i=y_i'=y} K(x_i,x_{i'})]$$

在这里，与$\langle x,x \rangle$相对应的$K(x,x)$是与最小化无关的常数，因此在实际计算中可以忽略。

然而，采用核函数的非线性核K均值聚类算法，最终的聚类结果强烈依赖于初始值的选择。

谱聚类

对于核K均值聚类算法的不足，可以通过降维来解决，这种方法称为谱聚类。

谱聚类，首先在核特征空间中应用局部保持投影法，然后直接应用通常的K均值聚类方法。

谱聚类的具体算法流程：

1. 对样本$\lbrace x_i \rbrace_{i=1}^n$应用拉普拉斯特征映射，得到$c-1$次维的$\lbrace z_i \rbrace_{i=1}^n$
2. 对于得到的样本$\lbrace z_i \rbrace_{i=1}^n$，应用通常的K均值聚类方法求其簇标签$\lbrace y_i \rbrace_{i=1}^n$

调整参数的自动选取

核K均值聚类法与谱聚类的结果依赖于高斯核函数的带宽等核参数的选择。

互信息是信息论里的一个基本的概念，由概率变量$x$和$y$的联合概率$p(x,y)$到各个边缘概率$p(x)p(y)$的KL距离来定义

$$\int \sum_{y=1}^c p(x,y)log\frac{p(x,y)}{p(x)p(y)}dx$$

互信息一般为非负的数值，只有当概率变量$x$和$y$在统计上是相互独立的时候，即当$p(x,y)=p(x)p(y)$的时候，其值为零。

互信息越大，簇标签$\lbrace y_i \rbrace_{i=1}^n$则包含的样本$\lbrace x_i \rbrace_{i=1}^n$的信息越多