文章目錄
- 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算法稱為單連結、全連結、均連結。
算法如下圖所示（圖源：機器學習）：
如果這篇文章對你有一點小小的幫助，請給個關注，點個贊喔，我會非常開心的~