聚类-下

常见聚类算法(续)

密度聚类

密度聚类算法基于一种想法——同属于一个子集的样本之间的密度较大、距离较近,他们是相互连接的,而不同子集的样本不可以互联。

因此密度聚类选择设定了一个距离阈值$\epsilon$,凡是大于这个阈值的两个样本,都是为不直接相连,凡是小于这个阈值的,都视为直接相连。

在此基础上,定义两个重要的概念:

  • 核心对象:即在其$\epsilon$-邻域(即距离它不大于$\epsilon$的范围)中的样本数目大于minNum的样本
  • 密度可达:即对于$x_i和x_j$,存在一系列的样本点$x_i,x_1.x_2…x_j$,其中$x_i$和$x_{i+1}$直接相连,并且中途点都是核心对象

算法思想如下:

  1. 确定$\epsilon$和minNum,找到核心对象
  2. 将任意一个核心对象作为起点,使用广度优先搜索找到所有密度可达的对象,作为一个聚类子集
  3. 重复2,直到所有节点都已经被访问过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 输入:样本集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的取值,这个过程一直持续到收敛为止。

于是,可以使用如下算法来求解高斯混合模型:

  1. 利用样本数据来计算初始化$\gamma_{ji}$,方法是用频率替代概率
  2. 根据公式(7)(8)(9)更新模型参数$\alpha,\mu,\sum$,这是M步
  3. 根据公式(3)更新$\gamma_{ji}$,这是E步
  4. 重复2、3步骤直到最大迭代轮数或者参数稳定

下面是图解:

密度聚类

值得一提的是,前面提到的k均值算法是高斯混合聚类算法在各混合成分方差相等,且每个样本仅仅归属于一个聚类类别的特例,可以看出,高斯混合聚类是更加具有普适性的聚类算法

小结

聚类算法多种多样,新的算法仍然在不断提出中,但是大多是可以理解和非黑箱的。同时,还可以结合集成学习对聚类算法进行优化,提高其鲁棒性。

异常检测和聚类算法也有一定的关系:聚类算法可以视为一种异常检测的途径。基于聚类的离群点:一个对象是基于聚类的离群点,如果该对象不强属于任何簇

查看更多

所有的文章都会在我的博客和我的知乎专栏同步进行更新,欢迎阅读


本文结束啦感谢您的阅读
生活不易,求打赏
0%