【机器学习】（6）：聚类

2015/4/17 18:26:16

在参数方法中，我们假设样本来自于一个已知的分布，因此我们的主要工作就是估计有限的参数；而对于另外一些问题，我们不能确定样本遵从的分布假设，这时我们可以退一步，采用混合分布估计输入样本；如果这样也不行，那么我们就要使用非参数的方法。今天我们来初步了解下聚类 学习。主要的要点如下：

• 混合密度
• K-均值聚类
• 聚类后的监督学习
• 层次聚类

一、混合密度

之所以要提出混合分布，主要原因就是上面所说的分布假设无法确定的情况，另一个原因也有可能样本遵从的分布本身就不是单一的，比如语音识别的学习，同样一个单词，可能因为说话者的性别、年龄、方言等因素而有不同的发音，因此不能够用统一的分布假设来进行拟合。这里我们采取表示所有这些不同发音方法的策略，即半参数密度估计（semiparamitric density estimation），我们对样本假定有多个分组，每个分组仍然假定一个具体的模型。

混合密度（mixture density）记作：

这里的G-i称为混合分支（mixture component），也称做分组（group）或簇（cluster）；P(x|G-i)是分支密度，而P(G-i)是混合比例，这里是通过概率的量来度量分支的比例和密度。分支数K是超级参数，应当是预先指定的。

二、K-均值聚类

如何对一个样本进行聚类分析呢？这里我们有一个简单的算法，称之为K-均值聚类。为了便于理解，我们引入一个颜色量化的实例。比如我们有一副24位/像素的图像（即24个比特位来标示图像，总共可以表示2^24中颜色，1600多万种），假定我们有个8位/像素的彩色屏幕，显示这副图像无疑会存在像素损失，现在的问题是我们从原先的1600万种颜色中选取256种颜色来显示图像呢？

如果直接均匀量化是不实际的，因为图像像素的分布并不均匀，比如一副大海的图片蓝色比较多，而基本不会出现红色；我们量化后的图像像素应当尽可能地接近反映原来的像素密度，将映射表更多地放在高密度区域，丢弃没有数据的区域。

这里我们一个自然的想法，将“距离”比较近的一些像素用一个近似值来代表，从而实现像素的量化。比如对于24位的像素x，我们有24位的映射表集合M，如果对于某个映射m-i附近的像素值都用序号i来表示像素的话，那么我们只要选取256个映射表，就可以实现1600万-->256的映射。因此这里关键是度量像素样本x与映射表m之间的距离（都是24比特的二进制序列）：

现在的问题是我们应当如何计算符合这样条件的m-i呢？我们的方法是计算总重构误差（reconsturction error），定义为：

我们可以根据一个迭代算法来计算出这样的m，最终参考向量被设置为它所代表的所有实例的均值。算法的伪代码是：

选择K个点作为初始中心；

Repeat

将每个点指派到最近的中心，形成K个簇；

重新计算每个簇的中心；

Until簇的中心不再变化

初始化K-均值算法可以有不同的方法，比如简单随机选择k个实例作为初始的M，或者可计算所有数据的均值，并将一些小的随机变量加到均值上，得到k个初始的m值。

参数K的去顶依赖于我们使用的聚类方法类型，我们可以将重构误差或对数似然作为k的函数绘制图形，找出“拐点”，即足够大的K之后，算法将开始分裂分组，此时重构误差不会大幅降低，而对数似然也不会大幅提高。

其实K-均值聚类算法是期望最大化算法（Expectation-Maximization, EM）的一个特例。

三、聚类后的监督学习

聚类可以用来探查数据，理解数据的结构。维度归约方法用来发现变量间的相关性，从而对变量分组；而聚类方法用于发现实例间的相似性，从而对实例分组。

聚类的一个最直接应用就是分类问题，一旦发现实例间存在基于某种相似性的分组，那么可以对分组进行命名标记，定义属性，比如“客户关系管理”中对客户进行分组。

聚类也可以作为监督式学习的预处理步骤，我们先了解发生了什么，然后学习它意味着什么。

四、层次聚类

上面的聚类方法通过混合模型拟合数据，或找出最小化重构误差的分组模式，还有一些聚类方法只关注实例间的相似性，对数据没有其他要求。这里的目标是找出分组，使得一个分组汇总的对象比不在一个分组中的对象更相似，这种方法称为层次聚类（hierarchiacl clustering）。

层次聚类的关键是度量相似性，常用的就是欧式距离（向量对应分量差的组合）和绝对值距离（向量间距离）。在单链接聚类中，距离定义为两个分组的所有可能元素之间的最小距离，而全链接聚类中，两个分组间的距离则取所有可能元素之间的最大距离。

Refer： 《机器学习导论》，Ethen Alpaydin（土耳其），机械工业出版社