当前位置：网站首页>Week 7 Latent Variable Models and Expectation Maximization

Week 7 Latent Variable Models and Expectation Maximization

2022-08-04 13:03:00 【金州饿霸】

一、Clustering

1、Clustering Algorithms（聚类算法）

基于中心（KMeans）
基于密度 (DBSCAN)（Density based）
层次聚类（Hierarchical clustering）
基于图的聚类（Graph based clustering）

2、软聚类和硬聚类

软聚类：数据点可能属于一个或多个集群，且给出属于每个集群的概率
硬聚类：数据点只属于一个集群

二、KMeans Algorithm（简单易懂版）

1、KMeans原理

K-Means算法的特点是类别的个数是人为给定的，如果让机器自己去找类别的个数，通过一次次重复这样的选择质心-计算距离后分类-再次选择新质心的流程，直到我们分组之后所有的数据都不会再变化了，也就得到了最终的聚合结果。

KMeans 对初始值敏感，这意味着具有不同初始聚类中心的 Kmeans 的不同执行可能会导致不同的解决方案
KMeans 是一种非概率算法，仅支持硬分配，一个数据点只能分配给一个且只有一个集群

2、KMeans过程

随机选取k个质心（k值取决于你想聚成几类）
计算样本到质心的距离，距离质心距离近的归为一类，分为k类
求出分类后的每类的新质心
再次计算计算样本到新质心的距离，距离质心距离近的归为一类
判断新旧聚类是否相同，如果相同就代表已经聚类成功，如果没有就循环2-4步骤直到相同

3、KMeans算法实例讲解

随机选取k个质心（k值取决于你想聚成几类）

假设我想聚3类，那我们随机选取【电影1、电影6、电影9】这3个电影作为质心（初始大佬）

计算样本到质心的距离，距离质心距离近的归为一类，分为k类

计算除质心（大佬）外的样本（小弟）的欧式距离，样本（小弟）离哪个质心（大佬）近，该样本就跟哪个质心（大佬）

从上图可以看出：

电影2、电影3（小弟）离电影1（大佬）更近，所以他们3个暂时为A类

电影4、电影5、电影10（小弟）离电影6（大佬）更近，所以他们4个暂时为B类

电影7、电影8（小弟）离电影9（大佬）更近，所以他们3个暂时为C类

求出分类后的每类的新质心

上面我们已经分为三类了，我们需要从三类中重新选出大佬（质心）。

A将电影2、电影3和电影1的平均值做A类的大佬，则A类新大佬（质心）为：

电影搞笑镜头电影搞笑镜头电影搞笑尽头=(电影1搞笑镜头+电影2搞笑镜头+电影3搞笑尽头3,

电影亲吻镜头电影亲吻镜头电影亲吻尽头，电影1亲吻镜头+电影2亲吻镜头+电影3亲吻尽头3，

电影打斗镜头电影打斗镜头电影打斗尽头电影1打斗镜头+电影2打斗镜头+电影3打斗尽头3)

=(100,20,20)

同理也可以计算出B类新大佬（质心）为（17.5，98.75，17.5），C类新大佬（20,20,100）

再次计算计算样本到新质心的距离，距离质心距离近的归为一类

同样用上面方法计算样本到质心（新大佬）的欧式距离，得

从上图可以看出：

电影1、电影2、电影3（小弟）离A类（新大佬）更近，他们归为一类

电影6、电影4、电影5、电影10（小弟）离B类（新大佬）更近，他们也归为一类

电影9、电影7、电影8（小弟）离C类（新大佬）更近，他们也归为一类

判断新旧聚类是否相同

经过这次计算我们发现聚类情况并没有变化，这就说明我们的计算收敛已经结束了，不需要继续进行分组了，最终数据成功按照相似性分成了三组。即电影1，2,3为一类电影4,5，6，10为一类，电影7,8，9为一类，完成聚类。

三、KMeans Algorithm（课件公式推导版）

1、“1-of-K”⽬标函数

引⼊⼀组D维向量 $\mu_k$ ，其中k = 1, . . . , K，且µk是与第k个聚类关联的⼀个代表。正如我们将看到的那样，我们可以认为 $\mu_k$ 表⽰了聚类的中⼼。我们的⽬标是找到数据点分别属于的聚类，以及⼀组向量{ $\mu_k$ }，使得每个数据点和与它最近的向量 $\mu_k$ 之间的距离的平⽅和最⼩。

现在，⽐较⽅便的做法是定义⼀些记号来描述数据点的聚类情况。对于每个数据点 x_n

，我们引⼊⼀组对应的⼆值指⽰变量 $r_{nk}$ ∈ { 0, 1}，其中k = 1, . . . , K表⽰数据点 x_n

属于K个聚类中的哪⼀个，从⽽如果数据点xn被分配到类别k，那么 $r_{nk}$ = 1，且对于j ≠ k，有 $r_{nk}$ = 0。这被称为“1-of-K”表⽰⽅式。之后我们可以定义⼀个⽬标函数，有时被称为失真度量（distortion measure），形式为:

$J=\sum_{n=1}^{N} \sum_{k=1}^{K} r_{n k}\left\|\boldsymbol{x}_{n}-\boldsymbol{\mu}_{k}\right\|^{2}$

它表⽰每个数据点与它被分配的向量 $\mu_k$ 之间的距离的平⽅和。我们的⽬标是找

到{ $r_{nk}$ }和{ $\mu_k$ }的值，使得J达到最⼩值。我们可以⽤⼀种迭代的⽅法完成这件事，其中每次迭

代涉及到两个连续的步骤，分别对应 $r_{nk}$ 的最优化和 $\mu_k$ 的最优化。

2、 $r_{nk}$ 的最优化和 $\mu_k$ 的最优化（包含公式推导）

（1）步骤

⾸先，我们为 $\mu_k$ 选择⼀些初始值。
然后，在第⼀阶段，我们关于 $r_{nk}$ 最⼩化J，保持 $\mu_k$ 固定。
在第⼆阶段，我们关于 $\mu_k$ 最⼩化J，保持 $r_{nk}$ 固定。
不断重复这个⼆阶段优化直到收敛。

我们会看到，更新 $r_{nk}$ 和更新 $\mu_k$ 的两个阶段分别对应于EM算法中的E（期望）步骤和M（最⼤化）步骤。为了强调这⼀点，我们会在K均值算法中使⽤E步骤和M步骤的说法。

（2）E（期望）步骤

⾸先考虑确定 $r_{nk}$ 。上述给出的J是 $r_{nk}$ 的⼀个线性函数，因此最优化过程可以很容易地进⾏，得到⼀个解析解。与不同的n相关的项是独⽴的，因此我们可以对每个n分别进⾏最优化，只要k的值使 $\left \| x_n - \mu_k \right \|^2$ 最⼩，我们就令 $r_{nk}$ 等于1。换句话说，我们可以简单地将数据点的聚类设置为最近的聚类中⼼。更形式化地，这可以表达为:

（3）M（最⼤化）步骤

现在考虑 $r_{nk}$ 固定时，关于 $\mu_k$ 的最优化。⽬标函数J是 $\mu_k$ 的⼀个⼆次函数，令它关于 $\mu_k$ 的导

数等于零，即可达到最⼩值，即：

$\begin{gathered} 2 \sum_{n=1}^{N} r_{n k}\left(\boldsymbol{x}_{n}-\boldsymbol{\mu}_{k}\right)=0 \\ \boldsymbol{\mu}_{k}=\frac{\sum_{n} r_{n k} \boldsymbol{x}_{n}}{\sum_{n} r_{n k}} \end{gathered}$