聚类算法简述

• K-MEANS
  • 算法
  • K-MEANS
  • 评估聚类结果与选择K
  • MapReduce
• GMM
  • 算法
  • 初始化
  • 过拟合
  • K-MEANS比较
• LDA
  • LDA和clustering的区别
  • 数学基础
    • 四种分布
    • 共轭分布
    • 与LDA的关系
  • LDA的结构
  • Inference
    • EM算法
    • Gibbs Sampling
    • Collapsed Gibbs Sampling

本文简要介绍K-MEANS、高斯混合模型GMM、主题模型LDA三种聚类方法。

K-MEANS

算法

K-MEANS是一种coordinate descent algorithm或者叫alternating optimizing算法，每次固定其他变量，只优化部分变量。

1. 样本点划分到最近聚类中心的那一类

1. 根据重新划分的样本点，计算每个类的新聚类中心

K-MEANS++

改进了初始样本中心的选择方法。

1. 从数据中随机选择样本点作为第一个聚类中心
2. 对每个样本点，计算到最近的聚类中心的距离
3. 根据第二步计算的样本点到最近的聚类中心的距离，成概率地选择新的聚类中心
4. 重复2-3直到获得K个聚类中心

这样做的优点有：

• 提高了局部最优点的质量
• 收敛更快

这样做的缺点有：

• 相比随机选择中心点计算较大

评估聚类结果与选择K

找到上述误差式随着K增大而减小的拐点即可

MapReduce

• map：每个node存储中心点，计算到node中的点距离最近的中心点，划分类别
• reduce：根据每个类别，重新计算新的中心点，然后在分发到各个node上

GMM

算法

1. E步骤：根据模型参数估计样本i到类别k的概率rik

1. M步骤：根据样本i到类别k的概率rik最大似然模型参数

初始化

初始化对于收敛速率以及局部最优点的质量很关键，参数初始化的方法如下：

• 随机选择K个点，计算每个点到K个中心点的距离，采用硬划分计算每个聚类的模型参数。
• 类似K-MEANS++，一步步选择K个点，以期好的收敛性。
• 通过K-MEANS的结果初始化参数。

过拟合

M步骤的最大似然可能会导致训练数据的过拟合。

例如：K=2。类1只有一个点，其他的点都在类2。这样的话协方差为0的话似然函数最大为正无穷。这样的话类1的中心就是那一个点，样本点只要跟这个点不相同，那么样本点落在类1的似然就是0。

解决办法：不要让协方差变成0，在协方差的对角阵上加上一个小的常数量。

K-MEANS比较

K-MEANS是种特殊的GMM，特殊如下：

• 协方差矩阵对角化，并且对角线上的元素都相等；其聚类区域是圆形。
• E步骤中计算rik，协方差对角线上的元素很小，使得类别的决定与样本点到类别中心的距离有关。
• M步骤最大似然得到模型参数，是硬区分的。

GMM相比K-MEANS优点如下：

• 软间隔划分，样本点可以属于多个类别，可以计算属于各个类别的概率
• K-MEANS只记录了聚类中心，GMM记录了聚类的形状
• K-MEANS的聚类区域是超球形的不可以重叠，GMM的聚类区域可以是椭圆形的，而且可以斜着摆，可以重叠。
• GMM可以学习到聚类划分时各维度的权重，比如对文本聚类，可以知道哪个词划分更好。

LDA

LDA，通过文档中词语的类别归属训练，学习到了文档的类别归属，不同主题的词汇概率分布。

LDA，认为文章作者首先对文章设定了一系列主题，然后根据主题遣词造句。LDA就是从已获得的语料库反推文章主题。

LDA和clustering的区别

• clustering发现的是语料级别上不同类别的先验概率分布；LDA发现的是文档级别上不同类别的先验概率分布。
• K-MEANS认为一个样本属于一个类；GMM认为一个样本以某个概率属于某类，认为可能属于A类或者B类，但是其本质上还是认为样本只属于一个类别。LDA可以认为样本属于多个类别。例如，一个讲运动科学的文章，K-MEANS认为它就属于运动类；GMM认为它有可能属于运动类，也有可能属于科学类；LDA认为它既属于运动类又属于科学类。本质上，LDA（mixed membership modeling）想要发现样本的多个类别，而K-MEANS和GMM则想要发现文本的单个类别。
• 传统判断两个文档相似性的方法是通过查看两个文档共同词出现的多少，这样没有考虑语义。主题模型中，主题表现一个概念，更具体地表现一系列词的条件概率分布。相同主题分布的文档往往很相似。

数学基础

四种分布

• 二项分布（binomial）：n次伯努利实验。每次伯努利实验只有两个结果01。
• 多项分布（multi-nomial）：n次伯努利实验。每次伯努利实验可以有多个结果。
• beta分布：[0,1]区间随机变量x的概率密度函数
• dirichelet分布：[0,1]区间多个随机变量xi的联合概率密度函数，且

beta分布和dirichelet分布有个好处，其均值可以用参数来估计。

共轭分布

贝叶斯理论中，后验概率可以通过先验概率与似然函数得到。假如先验概率与后验概率满足相同的分布律，那么先验分布与后验分布叫做共轭分布。同时，先验分布叫做似然函数的先验共轭分布。

在LDA中，表现为两点：

• 每个文档的主题分布服从先验狄利克雷分布，根据文档中的词的类别获得的数据是多项分布的，根据先验的狄利克雷分布以及多项分布的数据，可以推导出后验分布的狄利克雷分布。
• 每个主题的单词分布服从狄利克雷分布，分局文档中词的类别获得的数据是多项分布的，根据先验分布的狄利克雷分布以及多项分布的数据，可以推导出后验分布的狄利克雷分布。

与LDA的关系

LDA模型中：一篇文档的生成方式如下：

• 从狄利克雷分布α中取样生成文档ii的主题分布θi
• 从主题ii的多项式分布θi中取样生成文档i第j个词的主题zi,j
• 从狄利克雷β分布中取样生成主题zi,j对应的词语分布ϕzi,j
• 从词语的多项式分布ϕzi,j中采样生成最终的词语wi,j

LDA的结构

LDA的输入如下：

• 语料库每个文本的单词集（sets of words）。

LDA的输出包含三部分：

• 语料库级别：词汇在不同类别的概率分布
• 文档级别：文档中每个词所属的类别（硬）
• 文档级别：文档所属类别的概率分布

这三部分各自的作用如下：

• 语料库级别：词汇在不同类别的概率分布——检验主题的一致性，主题的关键词是什么？是否形成了有意义的主题？常用于反推主题标签
• 文档级别：文档中每个词所属的类别（硬）——通常不感兴趣
• 文档级别：文档所属类别的概率分布——将文本分为多个类别；文档的相关性；研究用户的主题喜好。

Inference

通常，LDA被视作贝叶斯模型，理由如下：

• 做预测的时候考虑到了参数的不确定性，认为参数都是随机变量而不像频率学派那样认为参数就是一个确定的值。
• 与MLE相比自带正则

EM算法

LDA中设计到模型的参数，比如狄利克雷的分布参数等等，这种情况下也可以用EM算法：

• E：在模型参数确定的情况下，确定文档中的词分布。
• M：用文档中的词分布去反推模型的参数。

Gibbs Sampling

这里写图片描述

迭代地，按照条件概率对文本中词汇进行分类（硬）。

1. 根据语料库级别各个词汇在各个类别的概率、文档级别文档在各个类别的概率，计算文档级别文档中每个词的类别。
2. 根究文档级别文档中每个词的类别，计算该文档在不同类别下的概率。
3. 根究文档级别文档中每个词的类别，计算语料库级别各个词汇在各个类别下的概率。
4. 重复直到达到迭代次数

Collapsed Gibbs Sampling

根据LDA的结构，只需要对文档级别每个词属于的类别进行采样即可，不需要采样语料库级别各个词汇在各个类别下的概率，也不需要采样文档级别文档在不同类别下的概率。

这样做，因为在更小的特征空间上评判不确定性，通常可以取得更好的表现。

1. 随机对每个文档的词汇的类别进行分配。根据每个文档的词汇类别，计算文档级别该文档不同类别的count，计算语料库级别各个词汇在各个类别下的count。
2. 选择一个文档，随机选择一个词，将该词的类别归0，对应更改文档级别不同类别的count以及语料库级别不同词在不同类下的count。
3. 将文档级别不同类别的count视为该文档对不同类别的偏好；将语料库级别该词对应不同类别的count视为该词对不同类别的偏好。将上面两个偏好转化为概率相乘（加上平滑参数）即可得到该词对应不同类别的采样概率，根据采样概率重新分配该词的类别，并对应更改文档级别的类别count、语料库级别不同词汇对应不同类别的count。
4. 迭代2-3直到到达迭代次数。
5. 获得文档级别每个词的类别归属后，计算文档级别各个类的概率以及语料库级别不同词汇对应不同类别的概率。