聚类-下
由ypyu创建，最终由ypyu 被浏览 15 用户
在本文中，我将介绍机器学习中关于聚类的算法。
因为知乎中对于markdown的支持太差了，本文不在知乎直接排版，所以阅读体验不是很好，若想获得更好的阅读体验，请点击下文链接进行阅读。
所有的文章都会在我的博客和我的知乎专栏同步进行更新，欢迎阅读
下面是正文：
密度聚类
密度聚类算法基于一种想法——同属于一个子集的样本之间的密度较大、距离较近，他们是相互连接的，而不同子集的样本不可以互联。
因此密度聚类选择设定了一个距离阈值$\epsilon$，凡是大于这个阈值的两个样本，都是为不直接相连，凡是小于这个阈值的，都视为直接相连。
在此基础上，定义两个重要的概念：
- 核心对象：即在其$\epsilon$-邻域（即距离它不大于$\epsilon$的范围）中的样本数目大于minNum的样本
- 密度可达：即对于$x_i和x_j$,存在一系列的样本点$x_i,x_1.x_2...x_j$，其中$x_i$和$x_{i+1}$直接相连，并且中途点都是核心对象
算法思想如下：
-
确定$\epsilon$和minNum，找到核心对象
-
将任意一个核心对象作为起点，使用广度优先搜索找到所有密度可达的对象，作为一个聚类子集
-
重复2，直到所有节点都已经被访问过
输入：样本集D={x1,x2.....xm}
聚类阈值 epsilon 和 最小数目 minNUm
def DBC(D,epsilon,minNum): # 初始化邻域集合 C = 空集 # 寻找核心对象 for i in range(1,m+1): 确定xi邻域数目N(xi) if N(xi) > minNUm: C = C U xi # 初始化聚类个数 numK = 0 while C != 空集: 随机抽取C中的一个核心对象a # 下面的代码是构造队列并进行bfs（广度优先搜索） Q = 空队列 Q.push(a) while not Q.empty(): Qfront = Q.pop() if N(Qfront) > minNum: # 去除Qfront的邻域核心对象 neighbor = Q.front.neighbor if neighbor 未被标记: 标记neighbor为已经访问 Q.push(neighbor) 上一轮所有标记的样本为一个聚类子集 numK = numK + 1 return
对于密度聚类算法而言，最终聚类的个数不能确定，是由$\epsilon$和minNum决定的，所以可以尝试不同的$\epsilon$和minNum，以找到符合现实任务要求的聚类结果。
下图诠释了密度聚类算法的工作过程：
高斯混合聚类
高斯混合聚类和之前所有的聚类算法都不同，它是一种基于概率分布的聚类算法，也就是说，该算法将样本的分布看做k个高斯分布的混合，其中k为我们想要的聚类数目。
先回顾一下n维向量的高斯分布的概率密度函数：$P(x|\mu,\sum)=\frac 1 {(2\pi)^{\frac n2}|\sum|^{0.5}}e^{(-\frac12(x-\mu)^T\sum^{-1}(x-\mu))}$其中x为n维向量，$\mu$为n维向量，$\sum$为协方差矩阵，$|\sum|$为矩阵的行列式，可以看出高斯分布的概率密度函数仅仅由参数$\mu和\sum$即可确定。
故高斯混合聚类的样本分布为k个上式的混合：$P_M(x)=\sum_{i=1}^k\alpha_ip(x|\mu,\sum_i)$其中$\alpha_i$是每个对应的高斯分布的权重，也可以理解为某个样本是该高斯分布对应的聚类的概率。
如图所示：
(以下部分帮助理解，可以略过)我们该如何理解高斯混合聚类呢？如果给定了一个高斯混合分布，即：$P_M(x)=\sum_{i=1}^k\alpha_ip(x|\mu,\sum_i)$那么对于某个样本$x_j$(j是它在数据集中的排位)，它的类别为$x_j$，则样本属于类别i的概率为$P(z_j=i|xj)$，根据逆概率公式知：$\begin{align}P(z_j=i|x_j)& = \frac {P(z_j=i)P(x_j|z_j=i)} {P_M（x_j）} \\& （由\alpha_i的定义可知，P(z_j=i)=\alpha_i） \\& = \frac {\alpha_iP(x_j|\mu_i,\sum_i)} {P_M（x_j）} \\& = \frac {\alpha_iP(x_j|\mu_i,\sum_i)} {\sum_{i=1}^k\alpha_iP(x_j|\mu,\sum_i)）}\end{align}$看最终的(6)式，分子为**$x_j$在所有高斯分布上的概率的加权和**，分母为**$x_j$在特定的第i个（即我们指定的类别）高斯分布的概率**，所以，整个式子代表了该样本从所有类别中选择一个，选择到第i个聚类类别的概率。
那么，我们下面的问题就是如何求解$P_M(x)=\sum_{i=1}^k\alpha_ip(x|\mu,\sum_i)$中的参数$\mu,\sum$，可以利用极大似然法——求导取最值，略去繁琐的数学过程，可以算得：$\mu_i = \frac {\sum_{j=1}^{m} \gamma_{ji}x_j} {\sum_{j=1}^{m}\gamma_{ji}}$
$\sum_i = \frac {\sum_{j=1}^{m} \gamma_{ji}(x_j-\mu_i)(x_j-\mu_i)^T} {\sum_{j=1}^{m}\gamma_{ji}}$
其中$\gamma_{ji}$代表第j个样本被判定为第i个聚类的概率，即$\gamma_{ji}=P(z_j=i|x_j)$。
采用极大似然法求得这两个参数的结果，还有一个参数——每个高斯分布的权重$\alpha_i$，采用拉格朗日乘子法优化，可以算得：$\alpha_i=\frac 1m {\sum_{j=1}^{m}\gamma_{ji}}$得到上述结果后，便可以使用EM算法来迭代更新高斯混合模型的参数：
EM 算法是 Dempster,Laind,Rubin 于 1977 年提出的求参数极大似然估计的一种方法，它可以从非完整数据集中对参数进行估计，是一种非常简单实用的学习算法。可以有一些比较形象的比喻说法把这个算法讲清楚。比如说食堂的大师傅炒了一份菜，要等分成两份给两个人吃，显然没有必要拿来天平一点的精确的去称分量，最简单的办法是先随意的把菜分到两个碗中，然后观察是否一样多，把比较多的那一份取出一点放到另一个碗中，这个过程一直迭代地执行下去，直到大家看不出两个碗所容纳的菜有什么分量上的不同为止。EM算法就是这样，假设我们估计知道A和B两个参数，在开始状态下二者都是未知的，并且知道了A的信息就可以得到B的信息，反过来知道了B也就得到了A。可以考虑首先赋予A某种初值，以此得到B的估计值，然后从B的当前值出发，重新估计A的取值，这个过程一直持续到收敛为止。
于是，可以使用如下算法来求解高斯混合模型：
- 利用样本数据来计算初始化$\gamma_{ji}$，方法是用频率替代概率
- 根据公式（7）（8）（9）更新模型参数$\alpha,\mu,\sum$，这是M步
- 根据公式（3）更新$\gamma_{ji}$，这是E步
- 重复2、3步骤直到最大迭代轮数或者参数稳定
下面是图解：
值得一提的是，前面提到的k均值算法是高斯混合聚类算法在各混合成分方差相等，且每个样本仅仅归属于一个聚类类别的特例，可以看出，高斯混合聚类是更加具有普适性的聚类算法。
小结
聚类算法多种多样，新的算法仍然在不断提出中，但是大多是可以理解和非黑箱的。同时，还可以结合集成学习对聚类算法进行优化，提高其鲁棒性。
异常检测和聚类算法也有一定的关系：聚类算法可以视为一种异常检测的途径。基于聚类的离群点：一个对象是基于聚类的离群点，如果该对象不强属于任何簇 。
\n