25 Feb 2017

简单聚类

k-means算法

来，今天讲下应该是最简单的一个聚类算法，K-means算法,很好上手，很好实现，

算法步骤

输入：样本S = X1, X2,…, Xm。步骤：

选择初始的K个类别中心μ1，μ2，…，μk，k < m
对每个样本Xi，找到与其最近的那个聚类中心后将其标记为距离类别中心最近的类别，即：

 PS：上式的读法是：样本xi的类别距离xi最近的聚类中心μj的那个类别。    3. 经过上面一步，有些聚类(聚类集合也称为簇)中的元素就更新了，于是就需要调整聚类中心，所以将每个类别中心更新为隶属该类别的所有样本的均值： <img src="https://yzhihao.github.io/static/img/blog/Machine Learning/base_cluster2.jpg" alt="header1" style="height:auto!important;width:auto%;max-width:1020px;"/>

重复最后两步，直到类别中心的变化小于某阈值。终止条件：迭代次数/簇中心变化率/最小平方误差MSE(MinimumSquared Error)

好了，算法步骤写完了，那我们下面继续讨论几个问题。

k-means算法是否一定收敛

*　k -means算法一定收敛吗？在特定的场景下，答案是肯定的。 *　可以证明k-means正是在J上的坐标下降过程（参考第八讲）。尤其是k-means算法的内循环实际上是在重复：保持μ不变最小化J关于c的函数，然后再保持c不变最小化J关于μ的函数。因此，J是单调递减的，它的函数值一定收敛

k-means算法的凸性质

失真函数J是一个非凸函数，所以对于J的坐标下降并不能保证其收敛于全局最小值，即kk-means会被局部最小值影响。尽管如此，kk-means算法通常都都能很好的完成聚类任务。

也就是说初始值对结果的影响较大在聚类的时候要多选几次随机初始化，然后选择最小

K如何选择

步骤知道了，那选择几个类别呢？这个还真没有好办法，只能使用先验知识选定、拍脑门选一个或者用交叉验证的方式去验证…. 当然有些地方说K=(n/2)1/2，这个知道就好。

聚类中心如何初始化

话说K-means是初值敏感的,K-means算法会产生局部最优值的。即：如果聚类中心选择的不太好的话，可能到一个不太好的地方后就停了。那如何选择聚类中心呢？有这么个方法:

随便选一个聚类中心A，然后统计所有的样本点到A的距离，并让距离A远的样本点选中的概率大一些（如：距离A越远的样本点权值越大）。
在上面的基础上选出第二个点B作为聚类中心，然后计算所有样本点到这两个聚类中心的距离（如：所有样本点到最近的那个聚类中心的距离作为其权值），距离远的选中概率大。
重复上面的步骤，选出K个聚类中心。 PS：选中聚类中心时可以给个阈值，如果距离小于阈值就PASS，如果大与阈值就作为候选聚类中心，而这个阈值的选择方法可以是：建立个最小生成树，然后对边的权值取均值/最大值/最小值作为阈值。当然，实际运用中经常不这么麻烦，假设是二维的，于是上面的图可以放到一个x,y 坐标轴上，于是就求出最左边样本点到最右边样本点的长度X，和最上边样本点与最下边样本点的长度Y，然后用X/N和Y/N作为阈值的参考值。

K-means的公式化解释

记K个簇中心为μ1，μ2，…，μk，每个簇的样本数目为N1,N2, …, Nk 使用平方误差作为目标函数： header1

注：上式中等号右边的意思是：求属于第j个簇的所有样本到第j个簇的聚类中心μj的距离的平方和，然后求所有簇的上述值的和。

我们的目的是对该目标函数取最小，哪一个聚类中心，或者说哪一个簇能使该目标函数取最小，我们就说哪个是最好的。于是对μ求偏导：

header1

这是在说：

聚类中心即在该聚类中的所有样本的和求均值。
样本距离聚类中心是服从高斯分布的。
K-means最终的结果一定是像个圆形的。

K-means聚类方法总结

优点：

是解决聚类问题的一种经典算法，简单、快速
对处理大数据集，该算法保持可伸缩性和高效率
当簇近似为高斯分布时，它的效果较好缺点：
在簇的平均值可被定义的情况下才能使用，可能不适用于某些应用
必须事先给出k(要生成的簇的数目)，而且对初值敏感，对于不同的初始值，可能会导致不同结果。
不适合于发现非凸形状的簇或者大小差别很大的簇
对躁声和孤立点数据敏感

K-means的一个小改进（K中值聚类）

比如数组1、2、3、4、100的均值为22，显然距离“大多数”数据1、2、3、4比较远。于是改成求数组的中位数3，在该实例中更为稳妥。这就是K-Mediods聚类（K中值聚类），它的目标函数一定意义上可以认为是把K-means的目标函数中的平方换成绝对值。这个算法在一定程度上可以对抗异常值。

混合高斯模型

从几何上讲，单高斯分布模型在二维空间应该近似于椭圆，在三维空间上近似于椭球。遗憾的是在很多分类问题中，属于同一类别的样本点并不满足“椭圆”分布的特性。这就引入了高斯混合模型。而且因为高斯函数具有良好的计算性能，所以GMM被广泛地应用。

GMM简单的说就是从几个GSM(高斯分布)中生成出来的。即，如果GSM（高斯分布）的概率密度函数用

header1 ，θ = (μ,σ2) 表示的话，那GMM就是：

header1

其中，ak是系数，ak >=0， header1

header1

称为第k个分模型，其中θk= (μk,σk2)。a1+a2+…+aK = 1。

GMM的EM算法的推导

假设观测数据y1, y2,…, yN由GMM生成

header1

其中，θ = (a1,a2, …, ak; θ1, θ2, …, θk)。我们的目标是用EM算法估计GMM的参数θ。

1,明确隐变量，写出完全数据的对数似然函数

可以设想观测数据yj，j = 1, 2,…, N，是这样产生的：首先依概率ak选择第k个高斯分布分模型φ(y

θk)；然后依第k个分模型的概率分布φ(y

θk)生成观测数据yj。

这时观测数据yj是已知的，观测数据yj来自的第k个分模型是未知的(k =1, 2, .., K)，于是这个就是隐变量，我们用rjk表示，其定义如下：

header1

PS：隐变量rjk是0-1随机变量。有了观测数据yj及未观测数据rjk，那么完全数据是 (yj,rj1, rj2, …, rjk), j = 1, 2, …, N 于是，可以写出完全数据的似然函数

header1

式中

header1 （a式）

tip：第一个等号：在满足θ的高斯分布中，第j样本点出现的概率是P(yj, rj1, rj2, …, rjK | θ)，于是代表“所有的样本点出现的概率”的P(y,r | θ)就推出了第一个等号。第二个等号：由9.27式可得，若第j个观测来自第k个分模型时，rjk=1，即，akφ(yj|θk)]^rjk = akφ(yj|θk)]，反之，akφ(yj|θk)]^rjk = 0。于是将K个akφ(yj|θk)]^rjk连乘，就表示了第j个样本集合属于第k个分模型，即P(yj, rj1, rj2, …, rjK | θ)的展开后面两个等号是基本的数学知识，就不再解释了。

那么，完全数据的对数似然函数就是

header1