文章目录
- 0. 前言
- 1. 性能度量
-
- 1.1. 外部指标
- 1.2. 内部指标
- 2. 距离计算
- 3. k-means算法
- 4. 学习向量量化
- 5. 高斯混合聚类
- 6. 密度聚类 DBSCAN
- 7. 层次聚类 AGNES
如果这篇文章对你有一点小小的帮助，请给个关注，点个赞喔，我会非常开心的~
0. 前言
无监督学习意味着样本的标记信息是未知的，目标是揭示数据的内在规律。
聚类试图将数据集划分为不同的子集，称为“簇”。
1. 性能度量
聚类应达到簇内相似度高，簇间相似度低。
1.1. 外部指标
外部指标意味着将聚类结果与某个参考模型比较。
给出数据集 D D D，聚类结果簇划分 C C C，参考模型簇划分 C ∗ C^* C∗，以及对应簇标记 λ , λ ∗ \lambda,\ \lambda^* λ, λ∗，定义：
a = ∣ S S ∣ , S S = { ( x i , x j ) ∣ λ i = λ j , λ i ∗ = λ j ∗ , i < j } b = ∣ S D ∣ , S D = { ( x i , x j ) ∣ λ i = λ j , λ i ∗ ≠ λ j ∗ , i < j } c = ∣ D S ∣ , D S = { ( x i , x j ) ∣ λ i ≠ λ j , λ i ∗ = λ j ∗ , i < j } d = ∣ D D ∣ , D D = { ( x i , x j ) ∣ λ 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\} 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}
| 名称 | 公式 | 指标 |
|---|---|---|
| Jaccard系数 | J C = a a + b + c JC=\frac{a}{a+b+c} JC=a+b+ca | 越大越好 |
| FM指数 | F M I = a a + b ⋅ a a + c FMI=\sqrt{\frac{a}{a+b}\cdot\frac{a}{a+c}} FMI=a+ba⋅a+ca | 越大越好 |
| Rand指数 | R I = 2 ( a + d ) m ( m − 1 ) RI=\frac{2(a+d)}{m(m-1)} RI=m(m−1)2(a+d) | 越大越好 |
1.2. 内部指标
内部指标意味着直接考察聚类结果。
考虑聚类结果 C C C，定义：
a v g ( C ) = 2 ∣ C ∣ ( ∣ C ∣ − 1 ) ∑ 1 ⩽ i < j ⩽ ∣ C ∣ d i s t ( x i , x j ) d i a m ( C ) = max 1 ⩽ i < j ⩽ ∣ C ∣ d i s t ( x i , x j ) d m i n ( C i , C j ) = min x i ∈ C i , x j ∈ C j d i s t ( x i , x j ) d c e n ( C i , C j ) = d i s t ( μ 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) avg(C)=∣C∣(∣C∣−1)21⩽i<j⩽∣C∣∑dist(xi,xj)diam(C)=1⩽i<j⩽∣C∣maxdist(xi,xj)dmin(Ci,Cj)=xi∈Ci,xj∈Cjmindist(xi,xj)dcen(Ci,Cj)=dist(μi,μj)
| 名称 | 公式 | 指标 |
|---|---|---|
| DB指数 | D B I = 1 k ∑ i = 1 k max j ≠ i ( a v g ( C i ) + a v g ( C j ) d c e n ( C i , C j ) ) 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)}) DBI=k1i=1∑kj̸=imax(dcen(Ci,Cj)avg(Ci)+avg(Cj)) | 越小越好 |
| Dunn指数 | D I = min i ⩽ i ⩽ k { min j ≠ i ( d m i n ( C i , C j ) max 1 ⩽ l ⩽ k d i a m ( C l ) ) } 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)})\} DI=i⩽i⩽kmin{j̸=imin(max1⩽l⩽kdiam(Cl)dmin(Ci,Cj))} | 越大越好 |
2. 距离计算
距离计算是指 d i s t ( x i , x j ) dist(x_i,x_j) dist(xi,xj)。
对于有序的属性：
| 名称 | 公式 | 备注 |
|---|---|---|
| 闵可夫斯基距离 | d i s t ( x i , x j ) = ( ∑ u = 1 n ∣ x i u − x j u ∣ p ) 1 p dist(x_i,x_j)=(\sum_{u=1}^n\mid x_{iu}-x_{ju}\mid^p)^{\frac{1}{p}} dist(xi,xj)=(u=1∑n∣xiu−xju∣p)p1 | |
| 欧氏距离 | d i s t ( x i , x j ) = ∑ u = 1 n ∣ x i u − x j u ∣ 2 dist(x_i,x_j)=\sqrt{\sum_{u=1}^n\mid x_{iu}-x_{ju}\mid^2} dist(xi,xj)=u=1∑n∣xiu−xju∣2 | p=2 |
| 曼哈顿距离 | d i s t ( x i , x j ) = ∑ u = 1 n ∣ x i u − x j u ∣ dist(x_i,x_j)=\sum_{u=1}^n\mid x_{iu}-x_{ju}\mid dist(xi,xj)=u=1∑n∣xiu−xju∣ | p=1 |
对于无序的属性，令 m u , a m_{u,a} mu,a表示属性 u u u上取值为 a a a的样本数， m u , a , i m_{u,a,i} mu,a,i表示第 i i i个样本簇属性 u u u上取值为 a a a的样本数，则对于属性 u u u上的两个离散属性，有：
V D M p ( a , b ) = ∑ i = 1 k ∣ m u , a , i m u , a − m u , b , i m u , b ∣ p 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 VDMp(a,b)=i=1∑k∣mu,amu,a,i−mu,bmu,b,i∣p
3. k-means算法
k-means通过迭代循环两个过程：根据簇中心将每个样本划分入最近的簇，重新计算簇中心。
算法如下图所示（图源：机器学习）：
二分k-means：先指定一个簇中心，在这个簇中使用k-means， k = 2 k=2 k=2，将簇一分为二，再选定一个簇，在这个簇中使用k-means，如此循环。
4. 学习向量量化
学习向量量化（Learning Vector Quantization）假设数据样本带有类别标记，利用这些监督信息来辅助聚类。
算法如下图所示（图源：机器学习）：
5. 高斯混合聚类
高斯混合聚类采用概率模型来表达聚类，定义高斯混合分布：
p M ( x ) = ∑ i = 1 k α i ⋅ p ( x ∣ μ i , Σ i ) p_M(x)=\sum_{i=1}^k\alpha_i\cdot p(x\mid \mu_i,\Sigma_i) pM(x)=i=1∑kαi⋅p(x∣μi,Σi)
其中，该分布有 k k k个混合成分， α i \alpha_i αi是混合系数，表示选择这个成分的概率。
采用EM算法推导高斯混合模型，首先根据样本计算对应的高斯混合成分的后验概率：
γ j i = p M ( z j = i ∣ x j ) = α i ⋅ p ( x j ∣ μ i , Σ i ) ∑ l = 1 k α l ⋅ p ( x j ∣ μ 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)} γji=pM(zj=i∣xj)=∑l=1kαl⋅p(xj∣μl,Σl)αi⋅p(xj∣μi,Σi)
则对应的簇标记为：
λ j = arg max i ∈ { 1 , 2 , . . . , k } γ j i \lambda_j=\arg\max_{i\in\{1,2,...,k\}}\gamma_{ji} λj=argi∈{1,2,...,k}maxγji
再根据后验概率更新 α , μ , Σ \alpha,\ \mu,\ \Sigma α, μ, Σ。
算法如下图所示（图源：机器学习）：
6. 密度聚类 DBSCAN
密度聚类假设聚类结构能通过样本分布的紧密程度确定。
DBSCAN作如下定义：
- ε \varepsilon ε-邻域：对于一个样本 x x x，其 ε \varepsilon ε-邻域是与 x x x距离不大于 ε \varepsilon ε的样本子集
- 核心对象：对于一个样本 x x x，其 ε \varepsilon ε-邻域的样本数目大于某个值，那么 x x x是核心对象
- 密度直达： x i x_i xi是核心对象， x j x_j xj在其邻域内，则它们密度直达
- 密度可达： x i x_i xi与 x j x_j xj密度直达， x j x_j xj与 x k x_k xk密度直达，则 x i x_i xi与 x k x_k xk密度可达
- 密度相连：对于 x i x_i xi和 x j x_j xj，存在 x k x_k xk使得 x i x_i xi与 x j x_j xj均由 x k x_k xk密度可达，则 x i x_i xi与 x j x_j xj密度相连
DBSCAN将簇定义为由密度可达关系导出的最大密度相连样本集合。
算法如下图所示（图源：机器学习）：
7. 层次聚类 AGNES
层次聚类试图在不同层次对数据集进行划分，从而形成树形的聚类结构。
AGNES是一种自底向上的聚类策略，先将数据集中每一个样本看成一个簇，然后找到距离最近的簇，将其合并，该过程不断重复，直到达到指定簇数目。
衡量簇的距离，可以采用最小距离（由两个簇最近的样本决定）、最大距离（由两个簇最远的样本决定）、平均距离，对应的AGNES算法称为单链接、全链接、均链接。
算法如下图所示（图源：机器学习）：
如果这篇文章对你有一点小小的帮助，请给个关注，点个赞喔，我会非常开心的~