K-means算法

基本思想:通过迭代方式寻找K个簇(clusters)的一种划分方案,使得聚类结果对应的代价函数最小.特别地,代价函数可以为各个样本距离所属簇中心点地误差平方和

$J(c,\mu)=\sum_{i=1}^n||x_i-\mu_{c_i}||^2$

其中M是样本总数.$\mu_{c_i}代表着对应地中心点$,n是样本总数

具体步骤:
(1)数据预处理，如归一化，离群点处理等
(2)随机选取K个簇中心,记为$\mu_{1},….\mu_{K}$
(3)定义代价函数,$J(c,\mu)=min_{\mu}min_{c}\sum_{i=1}^n||x_i-\mu_{c_i}||^2$
(4)令t=0,1,2,..为迭代步数,重复下面过程直到J收敛

对于每一个样本$x_i$,将其分配到距离最近的簇 $c_i^{(t)}\leftarrow argmin_k||x_i-\mu_k||^2$
对于每一个类簇k,重新计算该类簇的中心 $\mu_k^{(t+1)}\leftarrow argmin_{\mu}\sum_{i:c_i^{k}}||x_i-\mu||^2$

k-means的EM解释

EM算法解决的是在概率模型中含有无法观测的隐含变量情况下的参数估计问题.
假设使用平方误差作为目标函数:

$J(\mu_1,\mu_2,...,\mu_k)=\frac{1}{2}\sum_{j=1}^K\sum_{i=1}^N(x_i-\mu_j)^2$

E-Step:
固定参数$\mu_k$,将每个数据点分配到距离他本身最近的一个簇中:

$\gamma_{nk}= \begin{cases} 1,\ \ \ \ if\ \ k=argmin_j||x_n-\mu_j||^2\\ 0,\ \ \ \ otherwise\\ \end{cases}$

M-Step:
固定数据点的分配,更新参数(中心点)$\mu_k$:

$\mu_k=\frac{\sum_n\gamma_{nk}x_n}{\sum_n \gamma_{nk}}$

这也就是为什么k-means会收敛的原因。
E时找到一个最逼近的目标函数$\gamma$；
M时固定函数$\gamma$,更新均值$\mu$
所以一定收敛

K-means优缺点

缺点:

受随机初始化的质心影响每次的结果不稳定,结果通常不是全局最优
需要人工确定初始K值
易受到噪声点影响
样本只能划分到单一的类中
优点:
对大数据集，k-means相对是可伸缩和高效的,计算复杂度是O(NKt)接近线性。其中N是数据点数目,K是类别数目,t是迭代次数
调优
调优有以下几个角度:
(1)数据归一化和离群点处理(为了克服噪声点影响)
(2)合理选择K值:有手肘法和Gapstatistic方法
(3)选择核函数(传统的欧氏距离度量方法，使K-means本质上假设各个数据具有一样的先验概率,并呈现球形或者高纬球星分布.可以通过核函数将数据点映射到高维空间,在新的特征空间里进行聚类.)

变体:K-means++

k-means++主要是对初始值选择的改进。

K-means++的思想:
假设已经选取了n个初始聚类中心(0＜n＜K),则在选取第n+1个聚类中心时,距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心.在选取第一个聚类中心(n=1)时通过随机的方法生成.后续点应该彼此之间相互远离。

当然这里同样需要预设一个聚类中心个数n

变体：ISODATA

上面两种算法:k-means和k-means++都是需要事先给定聚类中心个数k的.若聚类个数k不确定时,则可以使用ISODATA算法.
其思想是某些类别的样本个数过少时,把该类去掉.当属于某个类别的样本数过多时、分散程度较大时,把该类别分为两个子类别.ISODATA算法在K均值算法的基础上加了两个操作,一是分裂操作,对应着增加一个聚类中心。二是合并操作,对应着减少聚类中心数.

ISODATA的缺点是参数比较多,不仅仅需要一个参考的聚类数量K，还要指定三个阈值.

预期聚类的中心数目K
每个类所要求的最少样本数目$N_{min}$
最大方差Sigma.用于控制每个类别中样本的分散程度.
两个聚类中心之间所允许的最小距离$D_{min}$

高斯混合模型

高斯混合模型(GMM)也是一种常见的聚类算法,与K均值算法类似,同样使用了EM算法进行迭代计算.高斯混合模型假设每个簇的数据都符合高斯分布(又叫正态分布)的,当前数据呈现的分布就是各个簇的高斯分布叠加的结果.(每个数据的概率都和每个簇相关,只不过前面的权值影响的大小不同)

高斯混合模型的核心思想

当数据事实上有多个类,或者我们希望将数划分为一些簇时,可以假设不同簇中的样本各自服从不同的高斯分布,由此得到的聚类算法称为高斯混合模型.

核心思想:假设数据可以看作从多个高斯分布中生成出来的.在该假设下,每个单独的分模型都是标准高斯模型,其均值$\mu_i$和方差$\Sigma_i$是待估计的参数.此时,每个分模型都还有一个参数$\pi_i$,可以理解为权重或者生成数据的概率.

高斯混合模型的的公式:

$p(x)=\sum_{i=1}^K\pi_i N(x|\mu_i,\Sigma_i)$

高斯混合模型是一个生成模型.可以这样理解数据的生成过程.
假设一个简单情况,即只有两个一维标准高斯分布的分模型N(0,1)和N(5,1),其权重分别为0.7和0.3.那么,在生成第一个数据点时,先按权重的比例,随机选择一个分布,比如选择第一个高斯分布,接着从N(0,1)中生成一个点.这就是第一个数据.在生成第二个数据点时,随机选择到第二个高斯分布N(5,1),然后按照N(5,1)的分布生成第二个数据点.由此生成所有数据点

然而,我们并不能直接得到高斯混合模型的参数,而是观察到一系列数据点,给出一个类别的数量K后,希望求得最佳的K个高斯分模型.因此高斯混合模型就变成了寻找最佳的均值$\mu$,方差$\Sigma$,权重$\pi$的寻找,这类问题通常通过最大似然估计来求解.遗憾的是,此问题中直接使用最大似然估计,得到的是一个复杂的非凸函数,目标函数是和的对数,难以展开和对其求导.

求解高斯混合模型

GMM的待求参数为$(\mu,\Sigma,\pi)$
极大似然估计与EM的关系:

以上分别是高斯混合模型和EM适用的问题

如果我们已经清楚了某个变量服从的高斯分布，而且通过采样得到了这个变量的样本数据，想求高斯分布的参数，这时候极大似然估计可以胜任这个任务；而如果我们要求解的是一个混合模型，只知道混合模型中各个类的分布模型（譬如都是高斯分布）和对应的采样数据，而不知道这些采样数据分别来源于哪一类（隐变量），那这时候就可以借鉴EM算法。EM算法可以用于解决数据缺失的参数估计问题（隐变量的存在实际上就是数据缺失问题，缺失了各个样本来源于哪一类的记录）。
　　下面将介绍EM算法的两个步骤：E-step(expectation-step，期望步)和M-step(Maximization-step,最大化步);

用EM算法求解

E步骤:根据当前参数,计算每个点由某个分模型生成的概率
M步骤:使用E步骤估计出的概率,来改进每个分模型的均值、方差和权重

高斯混合模型与K-means的相同点是,都是可用于聚类的算法;都需要指定K值;都是使用EM算法来求解;都往往只能收敛于局部最优.而它相比于K-means的优点是可以给出样本属于某类的概率是多少;不仅仅可以用于聚类,还可以用于概率密度估计;并且可以用于生成新的样本点;

聚类算法的评估

优于聚类问题,没有外部标签数据,那么如何平哥两个聚类算法优劣?

为了评估不同聚类算法性能优劣,我们需要了解常见的数据簇的特点

中心定义的数据簇:这类数据集合倾向于球形分布,通常中心被定义为质心,即此数据簇中所有点的平均值.集合中的数据到中心的距离相比到其他簇中心的距离更近
密度定义的簇:这类数据集合呈现和周围数据簇明显不同的密度,或稠密或稀疏,当数据簇不规则或互相盘绕,并且有噪声和离群点时,常常适用基于密度的簇定义
以连通定义的数据簇:这类数据集合中的数据点和数据点之间有连接关系,整个数据簇表现为图结构.该定义对不规则形状或者缠绕数据簇有效.
以概念定义的数据簇:这类数据集合中的所有数据点具有某种共同性质

聚类评估的任务是估计在数据集上进行聚类的可行性,以及聚类方法产生结果的质量.这一过程又分为三个子任务:
(1) 估计聚类趋势(检测数据是否有效)
这一步骤是检测数据分布中是否存在非随机的簇结构.如果数据是基本随机的,那么聚类的结构是毫无意义的.我们可以观察聚类误差是否随聚类类别数目的增加而单调变化,如果数据是基本随机的,即不存在非随机簇结构,那么聚类误差随聚类类别数量增加而变化的幅度应该较不明显,并且找不到一个合适的K对应数据的真实簇数.
我们可以应用霍普金斯统计量来判断数据在空间上的随机性
从所有样本中随机找到n个点,记为$p_1,p_2,…p_n$,对其中的每一个点$p_i$,都在样本空间中找到一个离它最近的点并计算它们之间的距离$x_i$,从而得到距离向量$x_1,x_2,…,x_n$;然后,从样本的可能取值范围内随机生成n个点,记为$q_1,q_2,..,q_n$,对每个随机生成的点,找到一个离它最近的样本点并计算它们之间的距离，得到$y_1,y_2,…,y_n$.霍普金斯统计量H可以表示为：

$H=\frac{\sum_{i=1}^ny_i}{\sum_{i=1}^nx_i+\sum_{i=1}^ny_i}$

如果样本接近随机分布,那么$\sum_{i=1}^nx_i$和$\sum_{i=1}^ny_i$的取值应该比较接近,即H的值接近于0.5;如果聚类趋势明显,则随机生成的样本点距离应该远大于实际样本点的距离,即$\sum_{i=1}^ny_i>>\sum_{i=1}^nx_i$,H的值接近于1.

(2)判定数据簇数(确定簇数K)
确定聚类趋势之后,我们需要找到与真实数据分布最吻合的簇数,据此判定聚类结果的质量.数据簇数的判定方法有很多,比如手肘法和Gap Statistic方法.需要说明的是,用于评估的最佳数据簇数可能与程序输出的簇数是不同的.
(3)测定聚类质量(测定质量)
如何判定哪个聚类结果的质量更高?
以下几种常用的度量指标:

轮廓系数: $s(p)=\frac{b(p)-a(p)}{max\{a(p),b(p)\}}$ 其中a(p)是点p与同一簇中的其他点p’之间的平均距离;b(p)是点p与另一个不同簇的店之间的最小平均距离(如果有n个其他簇,则只计算和点p最接近的一簇中的点与该点的平均距离).a(p)反映的是p所属簇中数据的紧凑程度,b(p)反映的是该簇与其他临近簇的分离程度.显然,b(p)越大,a(p)越小,对应的聚类质量越好,因此我们将所有点对应的轮廓s(p)求平均值来度量聚类结果的质量.
均方根标准偏差 $RMSSTD={\{\frac{\sum_i\sum_{x∈C_i}||x-c_i||^2}{P\sum_i(n_i-1)}\}^2}$ 其中$C_i$代表第i个簇,$c_i$是该簇的中心,$x∈C_i$代表属于第i个簇的一个样本点,$n_i$为第i个簇的样本数量,P为样本点对应的向量维数.可以看出,分母对点的维度P做了惩罚,维度越高,则整体的平方距离度量值越大.$\sum_i(n_i-1)=n-NC$,其中n为样本点的总数,NC为聚类簇的个数,通常NC<<n,其中n为样本点的总数,NC为聚类簇的个数,通常NC<<n,因此$\sum_i(n_i-1)$的值接近点的总数,为一个常数.
R方(R-Square) $RS=\frac{\sum_{x∈D}||x-c||^2-\sum_i\sum_{x∈C_i}||x-c_i||^2}{\sum_{x∈D}||x-c||^2}$