蒙特卡洛的Faith

K-Means 及其衍生算法

生成模型与判别模型

在机器学习中，通常有两种模型，生成模型 (generative model) 和判别模型 (discriminative model)。对于无监督学习，聚类问题中，同样是也是以 K-Means 和高斯混合模型 (Gaussian Mixture Model) 为经典的代表。

还记得今年年初刚开始系统性学习机器学习的时候，这两个概念不是很清楚，现在弄懂了，以后有时间可以专门讲下。

对于判别模型，通常就是计算边界 (boudary)，如果以数学公式来表达通常就是直接从 training data 计算 $P (predict | data)$ 。相反的，生成模型则会假设我们的先验概率 (prior) 和近似概率 (likelihood) 的模型，从 training data求出他们的参数，最后通过经典的贝叶斯公式求出：

P (predict | data) = \frac{P (data | predict) \times P (p r e d i c t)}{P (d a t a)}

K-Means 及衍生算法

K-Means

K-Means 是 EM 算法的特殊例子，因为它用的是欧几里德 (Euclidean Distance) 距离，它的目标functon如下：

J = \sum_{i = 1}^{m} \sum_{k = 1}^{K} w_{i k} {‖ x^{i} - μ_{k} ‖}^{2}

m 代表data instances，K代表目前cluster的数量。当 $w_{i k} = 1$ 表示这个数据点属于cluster k，若 $w_{i k} = 0$ 则表示这个点不属于这个cluster。

那么算法本身可以分为 E-Step 和 M-Step。E-Step 主要计算欧几里德距离，M-Step则是算objective function J对于 $μ$ 的梯度。

\begin{aligned} E-Step： \\ \frac{\partial J}{\partial w_{i k}} = \sum_{i = 1}^{m} \sum_{k = 1}^{K} & {‖ x^{i} - μ_{k} ‖}^{2} \\ \Rightarrow w_{i k} & = {\begin{cases} 1 & if k = {argmin}_{j} {‖ x^{i} - μ_{j} ‖}^{2} \\ 0 & otherwise. \end{cases} \\ M-Step： \\ \frac{\partial J}{\partial μ_{k}} = 2 \sum_{i = 1}^{m} w_{i k} (x^{i} - μ_{k}) = & 0 \\ \Rightarrow μ_{k} & = \frac{\sum_{i = 1}^{m} w_{i k} x^{i}}{\sum_{t - 1}^{m} w_{i k}} \end{aligned}

需要注意以下几点：

如果数据集的variance过大，最好对数据做归一化 (Standardize)，使得他们的mean等于0，标准差等于1，以避免某些feature对于其他feature的影响。
K-Means 依赖于初始化状态，很有可能陷入局部最优，所以建议多初始化几次，然后取最小的J

Fuzzy C-Means (FCM)

由于K-Means是硬分类，Fuzzy C-Means就是相当于Soft K-Means。这里的Soft是指给数据点对于每个cluster不再是硬分配，而且给每个cluster分配响应的概率。

同理类似于SVM也有硬间隔和软间隔。

这里我们同样可以写出它的objective function J：

\begin{array}{l} \underset{C}{\arg min} \sum_{i = 1}^{m} \sum_{k = 1}^{K} w_{i k}^{m} {‖ x_{i} - μ_{k} ‖}^{2} \\ where: \\ w_{i j} = \frac{1}{\sum_{k = 1}^{K} {(\frac{‖ x_{i} - μ_{j} ‖}{‖ x_{i} - μ_{k} ‖})}^{\frac{2}{m - 1}}} \end{array}

FCM也是稍微将K-Means 变形，将w改为一个相对值，相对于其他所有点对应clusters的距离。分母其实就是Normalization constant，为了保证w处于0和1之间。

Hierarchical clustering

如果你留意上述的算法，他们都是要实现知道或者推断clusters的数量，我们可以通过下述方法推断：

model selection criteria (MML/LEC/AIC/BIC等等)
Elbow method (which uses the within cluster sums of squares)
Average silhouette method
Gap statistic method

但是与K-Means Clustering不同的是，Hierarchical Clustering 可以帮我们找到最优的clusters数量。

其算法很简单过程如下：

首先假设每一个点都是一个cluster，因此N个数据点就有N个clusters
通过计算cluster与cluster的距离并存在distance matrix里，将数据集中距离最近的两个点合并成一个cluster，此时有N-1个clusters
重新计算距离distanc matrix
不断重复知道只剩下一个cluster

注意有五种方式计算距离：

Single linkage: computes the minimum distance between clusters before merging them.
Complete linkage: computes the maximum distance between clusters before merging them.
Average linkage: computes the average distance between clusters before merging them.
Centroid linkage: calculates centroids for both clusters, then computes the distance between the two before merging them.
Ward’s (minimum variance) criterion: minimizes the total within-cluster variance and find the pair of clusters that leads to minimum increase in total within-cluster variance after merging.

举例：

二维图

点的笛卡尔坐标

根据第一种距离公式：

\sqrt{{(x_{a} - x_{b})}^{2} + {(y_{a} - y_{b})}^{2}}

我们可以算出distance matrix：

distance matrix

可以看出0.328是最小的，所以我们将2和4合并，此时合并高度为0.328：

distance matrix

然后再将2&4和3合并，合并高度为0.483：

合并1和5，合并高度为0.942：

distance matrix

然后根据我们每次合并的数据绘制成树状图，最后的高度为1.530：

树状图

此时最优的cluster 数目应该就是最大的合并高度下的竖线条数也就是2.

树状图解释

注意：其实这里蕴涵了两种策略，Top-Down （从一个cluster开始，不断分解到N个clusters）或者 Bottom-Up （从N个clusers开始合并为一个cluser）

Hierarchical K-Means (HKMeans)

其实是Top-Down approach，就是递归调用K-Means不断将其划为clusters中。这种方式相对较快，时间复杂度为 $O (K \log_{k} n)$ 。但是这种划分方法是greedy的也是hard的，相邻的两个点如果划为两个不同的cluster，他们再也不会划为同一个clusters.

HKmeans

总结

本次我们细讲了无监督学习聚类的判别模型，对于判别模型最大的问题是无法解决数据集overlapping的问题，更无法做一些推断和预测。这时生成模型的好处就体现出来，他可以预测出数据集中没有的数据的。后面我会讲一下生成模型和判别模型在深度学习中的应用，欢迎继续关注。

请输入密码

生成模型与判别模型

K-Means 及衍生算法

K-Means

Fuzzy C-Means (FCM)

Hierarchical clustering

Hierarchical K-Means (HKMeans)

总结