机器学习-聚类

http://en.wikipedia.org/wiki/Multispectral_pattern_recognition

聚类基础知识
凝层次聚类
K-means 聚类
基于EM算法的聚类

聚类基础知识

聚类：将数据划分到不同的类里，使相似的数据在同一类里，不相似的数据在不同的类里（物以类聚，人以群分）。

主要应用：

文本聚类，图像聚类，商品聚类。
便于发现规律，以及解决数据稀疏问题。

拿到一些大数据，如果没有什么先验知识，我们可以先聚类，来发现规律。

聚类的类型：

层次聚类非层次聚类

硬聚类 VS 软聚类

硬聚类：每个对象只属于一类。

软聚类：每个对象都以某个概率属于每个类。

距离矩阵相似度矩阵

大家可以看到：矩阵 D 中，1 与 2 距离为2.0,2 与 4 的距离是：9.0.

由于矩阵是对称的，所以只用下三角阵就可以。

有时在优化的过程中，我们只需要相似度矩阵，而不需要知道真正原始数据。

有时我能很容易得到相似度矩阵，而不容易得到原始矩阵。比如：在社交网络中，我们计算人与人的之间关系（也就是相似度）

比如：

人1 ==》人2 (人1 与人2 是好友)，距离1

人1 ==》人2 ==人3 (人1 与人2，人2 和人3 是好友)，距离2

聚类效果评价：

内部评价（Internal Evaluation）：同类是否相似，跨类是否相异。（无监督）

内部评价：Davies–Bouldin index

:表示类 x 的质心。

：表示类 x 内的所有对象到质心的平均距离。

外部评价（External Evaluation）：跟外部标准的一致度（监督）

分类指标：准确度（accuracy）、精度（Precision）、召回(Recall)、F值（F-measure）

，其中P：是精度，R是召回。β 是参数调整 P 和 R 权重，β =1 表示：P 和 R 同等重要。F值越大越好。

凝聚层次聚类

自底向上：凝聚层次聚类（Agglomerative Hierarchical Clustering）

自顶向下：分裂层次聚类（Divisive Hierarchical Clustering）

Agglomerative Hierarchical Clustering 算法描述：

将每个对象归为一类，共得到N类，每类仅包含一个对象。
找到最近接的两个类合并成一类。
重新计算新的类与所有旧类之间的聚类
重复第 2 步和第 3 步，直到最后合并成为一个类为止（此类包含了N 个对象）

第一步第二步第三步

第四步第五步第六步

最后生成这个树。如果我们需要几个聚类，只需要在树上横切一刀，切着几根线，就是几个类。

当然，如果事先知道要聚几个类，我们不没有必要生成这个棵树，在凝聚到我们要的个数时，停止凝聚即可。

凝聚层次聚类：每次减少一个分类。所以需要聚 n-1 次（所以这种聚类方法是很慢的，如果我们有10万零1条数据，那么我们需要聚10万次）。

树在查询时，这种遍历和：前序遍历，中序遍历，后序遍历，广度优先遍历，深度优先遍历，这些传统的树遍历方法有所不一样，我们要根据 similarity 小的优先遍历，也就是我们需要模拟一条直线从上向下切割，我们通过一个有序堆栈来存别切断的类，如果堆栈中数据不够我们的要求的，我们会弹出一个 similarity 最小的node ，然后将他的左右子节点放入堆栈中（我们采用插入排序进行降序排列，保证下次弹出最小的 similarity 的 node），这样堆栈中又多了一个类。依次增加堆栈中节点个数。直到达到 K 的个数。

距离的计算法方式：

单链（single linkage）:类的距离定义为：两个类中对象间的最近距离。

全链（complete linkage）:类的距离定义为：两个类中对象间的最远距离。

组平均（average linkage）类的距离定义为：两个类中对象间的平均距离。

min(single link) max(complete link) Group average

single link:易受噪音和 outliers 影响。容易形成较大大分类（链状）需要计算9次

complete link:受噪音和 outliers 影响较小。容易形成很多大小差不多的分类。需要计算9次

group average:介于两者之间。需要计算9次

还有一种，我们计算每个类的质心每个类需要3次计算。然后用质心间的距离作为类与类之间的距离。本例供需6次计算。

这样看来计算比较少。但是由于每次质心都是不一样的，所以我们要计算质心。其他三种情况，聚类都是数据与数据之间的，所以我们可以建一个相似度矩阵，这样在以后的计算划分过程中，我们只需要取值即可。总体上，经典中三种情况还是有可取之处的。

，如图：由于大类的表面积大，所以如果用single link，大类跟容易吸收其他数据。如果用complete link，由于大类就吃亏了，因为他最远点，也比较远。

凝聚层次聚类小结

算法简单
层次用于：概念聚类（生成概念、文档层次树）
聚类对象的两种表示法都适用。
处理大小不同的簇。
簇选取步骤在梳妆图生成之后。

K-means 聚类

算法描述

任意选择 K 个点作为初始聚类中心。（如果最初有一定目的性，我们可以手动设置质心，比如我们想用外部目标评价聚类，聚成两个类，一个是体育类，一个是财经，我们可以收集很多财经的词汇作为中心点，收集很多体育词汇作为另一个中心点）。
根据每个聚类的中心，计算每个对象与这些中心的距离，并根据最小距离重新对相应对象进行划分。
重新计算每个聚类中心。
当满足一算法终止定条件，如类别划分不再变化过时，则，否则继续步骤 2 和 3

Demonstration of the standard algorithm
1) k initial "means" (in this case k=3) are randomly generated within the data domain (shown in color).

2) k clusters are created by associating every observation with the nearest mean. The partitions here represent theVoronoi diagram generated by the means.

3) The centroid of each of the k clusters becomes the new mean.

4) Steps 2 and 3 are repeated until convergence has been reached.

损失函数：Within-Cluster Sum of Squares (WCSS)

在每次更新质心后，WCSS 是单调递减的。每次循环都输出WCSS的值，如果值没有单调递减，则表明在训练数据时，程序有错误。也可用弄一条数据，进行测试。避免数据量大不容看出计算的数值错误。

在每次求质心就是最小化 L(C)。

K-Means 是局部最优。也就是K-Means 聚类结果不稳定。

，途中红圈是 K 的初始值，我们可以看到每次 K 取的值不一样，聚类的结果相差很大。

距离的选择：

L1 范数:|x-y|
L2范数：(x-y)^2
余弦相似性：。注意：一般距离度量，距离越远，越不行相似。而余弦相似性：conβ 值越大越相似。

在对文本进行相似计算时：余弦相似性用的还是比较多的。由于数据稀疏性，如果两个向量中对应 feature 只有一个有值，那么计算距离时需要计算。如果余弦相似性那么就不需要计算，因为内积时这一维是为零。

中心点的选择：

1.随机

2.多轮随机，选择最小的WCSS

3.如果有目的的聚类，可以根据目的手工设置。

一旦 K 确定，K-Means 其实是按照中心点的中垂线对空间进行分割（图中黑点是中心点）。

所以中心点的选择，对聚类的结果影响也很大。图1

所以一旦中心点确定了，空间的划分也就确定了，这样 K-Means 对原始数据的密度，类的大小没有考虑。由于 K-Means 是对空间在中垂线无偏的划分，可以根据原始数据加个权重。在后边　ＧＭＭ　分类中就有这样的效果。

K 值的确定：根据先验知识我们知道 K 取值的大致范围，在取值范围内我们尽量取一个稍微大一点的值，因为一般我们将一个大类细分成两个子类我们可以接受，比如：将体育系统查分成篮球比赛和足球比赛两个类。但是将两个类没有分开是不可接受的。比如：体育类和财经类没有分开。

K-Means 优点：

算法简单，有效
时间复杂度低 O(nkt).n:聚类对象数，k 簇的数目，t 迭代次数。

K-means 聚类限制

处理非球（凸面）聚类。图1可以，K-Means 是直线将空间划分，所以对凸面分布的数据聚类效果不好。
密度，大小不同的聚类（受 K 的限制，难于发现自然的聚类）

K-Means 聚类效果与层次聚类效果对比

层次聚类的效果 K-Means 聚类的效果

K-Means 分布式应用：

在每个 Reduce 中，都有一个份质心列表。每个 Reduce 都需要计算他拥有的数据到质心的距离，并且重新分类，重新分类后，重新计算质心。这样每个Reduce 都有一个新的不同的质心。这是 Map 负责从每个Reduce那里收集质心，然后求一个平均，算出最终的质心，然后再重新分发给每个Reduce，每个Reduce就开始新的一轮计算。

基于 EM（Expectation-Maximization）算法的聚类

高斯分布（正态分布）

一元正态分布概率密度函数（PDF）：公式 1

多元正态分布概率密度函数PDF:将方差编程协方差矩阵。

如果我们知道一些数据符合高斯分布并且知道 σ 和 μ ，你给我x 我通过密度函数能够求出 x 的概率。（已知分布求概率）

如果我们知道一些数据(x1,x2,x3,x4...)和概率，但是不知道它们具体哪个具体的高斯分布，我需要求 σ 和 μ 的值，已确定分布。

μ=(x1+x2+...+xn)/n

σ^2=[(x1-μ)^2+(x2-μ)^2+...+(xn-μ)^2]

一元高斯分布

多元高斯分布（平均数的求方法跟一元高斯分布一样）

这是一个协方差矩阵。

混合模型

数据由多个分布产生：如果：高斯分布（也可以不是高斯分布，二项分布，指数分布...等）

对数据聚类：

估计分布的参数。
根据分布计算数据属于不同的分布（不同参数的高斯分布）的概率。

高斯分布可用于描述“椭圆形”的簇。

混合模型分布：是软聚类。而分层聚类和K-Means 都是硬聚类。

我们可以看到：每个环，就像一个等高线，在同一个环上的点，概率都相同。中心环的概率最高。越向外逐渐衰减，不同的分布中环与环不具有可比性，因为不同分布的衰减率不同，有的分布衰减很快，有些分布衰减比较缓慢。所有点，都在三个高斯分布中，但是概率不同。

混合高斯分布GMM

数据是由多个高斯分布的模型线性组合之后的模型产生的。

这是混合高斯分布的模型。

x:特征向量。θ:表示其他参数像：μ，σ，Σ。 m：表示有个混合模型，这 m 模型都产生点 x 一部分。P(j):第 j 个高斯分布的一个权重。

Log 似然函数：

这就是GMM的策略。

我们要最大化这个似然函数。这个似然函数表示的意思:每条数据通过模型求得概率，然后将概率连乘，这里取了对数，所以是求和。

我们要给出一个π，μ，Σ 的值，使得似然函数值最大。平常求极值，我们直接求导等于 0 ，这可以了。大家可以看到这个方程比较复杂，所以我们需要用另外一种方法：EM 算法，虽然刚开始，我们得值不是很好，但是 EM 算法逐渐优化，最后会得到一个比较不错的结果。

这个似然函数单调上升。

EM 算法期望最大（Expectation Maximization）

EM 是一种迭代优化算法。

解决数据不完整情况下的参数估计。不完整的意思是：不知道数据由那些模型产生的。

原理：E 步骤：利用当前参数值计算隐藏变量的后验概率，并基于此计算目标函数的期望。

M 步骤：最大化目标函数，求得新的参数值。

E步：.这里 j 表示一个类。分母是属于所有类加起来求和，这是归一化。P(j):表示第 j 个模型本来的概率（先验概率，这个公式和朴素贝叶斯分类器那个公式非常相似，只不多朴素贝叶斯分类器的后验概率，是通过一个独立假设后，我们对每个词概率的连乘求出来的，而这里是数据满足高斯分布，我们可以直接利用高斯分布的密度函数直接求出来。在朴素贝叶斯中我们将分母舍弃，是因为我们只算一边就确定了数据分类，并且我们是比较各类别之间的大小，这里确实要计算出后验概率的实际值，因为我们多次迭代，计算出靠谱的参数后，再去划分类型）。