聚类（1）：k均值算法

聚类简介

图 1: 几种聚类方法的比较 [PNG]

聚类是一种非监督学习方法。上图是scikit-learn中几种聚类方法的比较[1]。

k均值聚类

本节的主要内容来自Andrew NG的机器学习课程[2]。

k均值算法主要包含两步：为样本分配类标签以及修改类中心。

####k均值算法

随机初始化$K$个类中心$\boldsymbol\mu_1,\boldsymbol\mu_2,\ldots,\boldsymbol\mu_K\in\mathbb R^n$。
重复 {

1. for $i=1$ to $m$：将$\mathbf x^{(i)}$的类别标签$c^{(i)}$设为最靠近的类中心标签，$c^{(i)}=\arg\min_{k=1}^K\left\lVert\mathbf x^{(i)}-\boldsymbol\mu_k\right\rVert^2$；
2. for $k=1$ to $K$：重新计算类中心$\boldsymbol\mu_k$。

}

k均值聚类的代价函数为

\begin{equation} J\left(c^{(1)},\dots,c^{(m)},\boldsymbol\mu_1,\ldots,\boldsymbol\mu_K\right)=\frac{1}{m}\sum_{i=1}^m\left\lVert\mathbf x^{(i)}-\boldsymbol\mu_{c^{(i)}}\right\rVert^2， \label{eq:cf-k-means} \end{equation}

该代价函数通常也称为distortion function。

从代价函数可以看出，k均值算法的第1步是通过修改类标签$c^{(i)}$最小化代价函数，第2步是通过修改类中心$\boldsymbol\mu_k$最小化代价函数。

从k均值算法可知，初始化类中心$\boldsymbol\mu_k$和确定类别数$k$影响着算法的性能。

初始化类中心$\boldsymbol\mu_k$

图 2: 不恰当的类中心初始化导致局部极值 [PNG]

随机初始化类中心的方法通常是，随机从样本中选取$K$个点作为类中心。为了避免陷入局部极致，通常会进行多轮初始化，选择代价函数值最小的作为聚类结果。

####随机初始化选择k均值的类中心

For i = 1 to 100 {

1. 随机初始化类中心$\boldsymbol\mu_k$；
2. k均值算法得到$c^{(1)},\dots,c^{(m)},\boldsymbol\mu_1,\ldots,\boldsymbol\mu_K$；
3. 计算代价函数\eqref{eq:cf-k-means}。

}
选择代价函数值最小的聚类结果输出。

当$K=2,\ldots,10$时，这种方法的代价函数变化明显，当$K$很大（$K>100$）时，代价函数可能没有明显的变化。

确定类别数$K$

通过不停增大类别数$K$，选择代价函数曲线拐点对应的类别数，如下图左所示。

图 3: 确定类别数的elbow method [PNG]

有时，代价函数曲线不存在拐点，如上图右所示。还可以根据k均值应用的具体场景，选择聚类数目，比如要制作XS、S、M、L、XL几种规格的服装，当然用类别数$K=5$来划分人的身高体重。

参考文献

1. [1]F. Pedregosa et al., “Scikit-learn: Machine Learning in Python,” Journal of Machine Learning Research, vol. 12, pp. 2825–2830, 2011.
2. [2]A. Ng, “Clustering.” Coursera, 2014. [Online]

脚注