西瓜书+实战+吴恩达机器学习(十四)无监督学习之聚类(k-means, LVQ, 高斯混合聚类, DBSCAN, AGNES)

如果这篇文章对你有一点小小的帮助,请给个关注,点个赞喔,我会非常开心的~

0. 前言

无监督学习意味着样本的标记信息是未知的,目标是揭示数据的内在规律

聚类试图将数据集划分为不同的子集,称为“簇”

1. 性能度量

聚类应达到簇内相似度高,簇间相似度低

1.1. 外部指标

外部指标意味着将聚类结果与某个参考模型比较

给出数据集DD,聚类结果簇划分CC,参考模型簇划分CC^*,以及对应簇标记λ, λ\lambda,\ \lambda^*,定义:
a=SS,  SS={(xi,xj)λi=λj,λi=λj,i<j}b=SD,  SD={(xi,xj)λi=λj,λiλj,i<j}c=DS,  DS={(xi,xj)λiλj,λi=λj,i<j}d=DD,  DD={(xi,xj)λiλj,λiλj,i<j} a=|SS|,\ \ SS=\{(x_i,x_j)\mid \lambda_i=\lambda_j,\lambda_i^*=\lambda_j^*,i<j\}\\ b=|SD|,\ \ SD=\{(x_i,x_j)\mid \lambda_i=\lambda_j,\lambda_i^*\neq\lambda_j^*,i<j\}\\ c=|DS|,\ \ DS=\{(x_i,x_j)\mid \lambda_i\neq\lambda_j,\lambda_i^*=\lambda_j^*,i<j\}\\ d=|DD|,\ \ DD=\{(x_i,x_j)\mid \lambda_i\neq\lambda_j,\lambda_i^*\neq\lambda_j^*,i<j\}

名称 公式 指标
Jaccard系数 JC=aa+b+cJC=\frac{a}{a+b+c} 越大越好
FM指数 FMI=aa+baa+cFMI=\sqrt{\frac{a}{a+b}\cdot\frac{a}{a+c}} 越大越好
Rand指数 RI=2(a+d)m(m1)RI=\frac{2(a+d)}{m(m-1)} 越大越好

1.2. 内部指标

内部指标意味着直接考察聚类结果

考虑聚类结果CC,定义:
avg(C)=2C(C1)1i<jCdist(xi,xj)diam(C)=max1i<jCdist(xi,xj)dmin(Ci,Cj)=minxiCi,xjCjdist(xi,xj)dcen(Ci,Cj)=dist(μi,μj) avg(C)=\frac{2}{|C|(|C|-1)}\sum_{1\leqslant i <j\leqslant |C|}dist(x_i,x_j)\\ diam(C)=\max_{1\leqslant i <j\leqslant |C|}dist(x_i,x_j)\\ d_{min}(C_i,C_j)=\min_{x_i\in C_i,x_j\in C_j}dist(x_i,x_j)\\ d_{cen}(C_i,C_j)=dist(\mu_i,\mu_j)

名称 公式 指标
DB指数 DBI=1ki=1kmaxji(avg(Ci)+avg(Cj)dcen(Ci,Cj))DBI=\frac{1}{k}\sum_{i=1}^k\max_{j\neq i}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(C_i,C_j)}) 越小越好
Dunn指数 DI=miniik{minji(dmin(Ci,Cj)max1lkdiam(Cl))}DI=\min_{i\leqslant i \leqslant k}\{\min_{j\neq i}(\frac{d_{min}(C_i,C_j)}{\max_{1\leqslant l \leqslant k}diam(C_l)})\} 越大越好

2. 距离计算

距离计算是指dist(xi,xj)dist(x_i,x_j)

对于有序的属性:

名称 公式 备注
闵可夫斯基距离 dist(xi,xj)=(u=1nxiuxjup)1pdist(x_i,x_j)=(\sum_{u=1}^n\mid x_{iu}-x_{ju}\mid^p)^{\frac{1}{p}}
欧氏距离 dist(xi,xj)=u=1nxiuxju2dist(x_i,x_j)=\sqrt{\sum_{u=1}^n\mid x_{iu}-x_{ju}\mid^2} p=2
曼哈顿距离 dist(xi,xj)=u=1nxiuxjudist(x_i,x_j)=\sum_{u=1}^n\mid x_{iu}-x_{ju}\mid p=1

对于无序的属性,令mu,am_{u,a}表示属性uu上取值为aa的样本数,mu,a,im_{u,a,i}表示第ii个样本簇属性uu上取值为aa的样本数,则对于属性uu上的两个离散属性,有:
VDMp(a,b)=i=1kmu,a,imu,amu,b,imu,bp VDM_p(a,b)=\sum_{i=1}^k|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}|^p

3. k-means算法

k-means通过迭代循环两个过程:根据簇中心将每个样本划分入最近的簇,重新计算簇中心

算法如下图所示(图源:机器学习):
西瓜书+实战+吴恩达机器学习(十四)无监督学习之聚类(k-means, LVQ, 高斯混合聚类, DBSCAN, AGNES)
二分k-means:先指定一个簇中心,在这个簇中使用k-means,k=2k=2,将簇一分为二,再选定一个簇,在这个簇中使用k-means,如此循环。

4. 学习向量量化

学习向量量化(Learning Vector Quantization)假设数据样本带有类别标记,利用这些监督信息来辅助聚类。

算法如下图所示(图源:机器学习):
西瓜书+实战+吴恩达机器学习(十四)无监督学习之聚类(k-means, LVQ, 高斯混合聚类, DBSCAN, AGNES)

5. 高斯混合聚类

高斯混合聚类采用概率模型来表达聚类,定义高斯混合分布:
pM(x)=i=1kαip(xμi,Σi) p_M(x)=\sum_{i=1}^k\alpha_i\cdot p(x\mid \mu_i,\Sigma_i)
其中,该分布有kk个混合成分,αi\alpha_i是混合系数,表示选择这个成分的概率。

采用EM算法推导高斯混合模型,首先根据样本计算对应的高斯混合成分的后验概率:
γji=pM(zj=ixj)=αip(xjμi,Σi)l=1kαlp(xjμl,Σl) \gamma_{ji}=p_M(z_j=i\mid x_j)=\frac{\alpha_i\cdot p(x_j\mid \mu_i,\Sigma_i)}{\sum_{l=1}^k\alpha_l\cdot p(x_j\mid \mu_l,\Sigma_l)}
则对应的簇标记为:
λj=argmaxi{1,2,...,k}γji \lambda_j=\arg\max_{i\in\{1,2,...,k\}}\gamma_{ji}
再根据后验概率更新α, μ, Σ\alpha,\ \mu,\ \Sigma

算法如下图所示(图源:机器学习):
西瓜书+实战+吴恩达机器学习(十四)无监督学习之聚类(k-means, LVQ, 高斯混合聚类, DBSCAN, AGNES)

6. 密度聚类 DBSCAN

密度聚类假设聚类结构能通过样本分布的紧密程度确定

DBSCAN作如下定义:

  • ε\varepsilon-邻域:对于一个样本xx,其ε\varepsilon-邻域是与xx距离不大于ε\varepsilon的样本子集
  • 核心对象:对于一个样本xx,其ε\varepsilon-邻域的样本数目大于某个值,那么xx是核心对象
  • 密度直达:xix_i是核心对象,xjx_j在其邻域内,则它们密度直达
  • 密度可达:xix_ixjx_j密度直达,xjx_jxkx_k密度直达,则xix_ixkx_k密度可达
  • 密度相连:对于xix_ixjx_j,存在xkx_k使得xix_ixjx_j均由xkx_k密度可达,则xix_ixjx_j密度相连

DBSCAN将簇定义为由密度可达关系导出的最大密度相连样本集合。

算法如下图所示(图源:机器学习):
西瓜书+实战+吴恩达机器学习(十四)无监督学习之聚类(k-means, LVQ, 高斯混合聚类, DBSCAN, AGNES)

7. 层次聚类 AGNES

层次聚类试图在不同层次对数据集进行划分,从而形成树形的聚类结构。

AGNES是一种自底向上的聚类策略,先将数据集中每一个样本看成一个簇,然后找到距离最近的簇,将其合并,该过程不断重复,直到达到指定簇数目

衡量簇的距离,可以采用最小距离(由两个簇最近的样本决定)最大距离(由两个簇最远的样本决定)平均距离,对应的AGNES算法称为单链接全链接均链接

算法如下图所示(图源:机器学习):
西瓜书+实战+吴恩达机器学习(十四)无监督学习之聚类(k-means, LVQ, 高斯混合聚类, DBSCAN, AGNES)


如果这篇文章对你有一点小小的帮助,请给个关注,点个赞喔,我会非常开心的~