上一章：機器學習08——集成學習
下一章：機器學習10——降維與度量學習
機器學習實戰項目：【從 0 到 1 落地】機器學習實操項目目錄：覆蓋入門到進階，大學生就業 / 競賽必備

一、聚類任務（無監督學習的核心）

聚類是無監督學習中最核心的任務之一，目標是將無標記樣本集劃分為若干不相交的“簇”（cluster），以揭示數據內在的分布結構。

（一）形式化描述

• 給定樣本集D={x1,x2,...,xm}D = \{x_1, x_2, ..., x_m\}D={x1?,x2?,...,xm?}，每個樣本$x_i$為n維特征向量；
• 聚類算法將$D$劃分為$k$個簇{C1,C2,...,Ck}\{C_1, C_2, ..., C_k\}{C1?,C2?,...,Ck?}，滿足：
  • 簇間不相交：$C_{l^{\prime }}{\cap }_{l^{\prime }\ne l}{C}_l=?$；
  • 覆蓋所有樣本：$D={\cup }_{l=1}^k{C}_l$；
• 簇標記向量λ={λ1;λ2;...;λm}\lambda = \{\lambda_1; \lambda_2; ...; \lambda_m\}λ={λ1?;λ2?;...;λm?}表示樣本所屬簇（λj∈{1,2,...,k}\lambda_j \in \{1, 2, ..., k\}λj?∈{1,2,...,k}，即$x_j\in C_{{\lambda }_j}$）。
  

二、聚類性能度量（有效性指標）

性能度量用于評價聚類結果的優劣，核心是“簇內相似度高、簇間相似度低”，分為外部指標和內部指標。

（一）外部指標（與參考模型比較）

• 定義：將聚類結果與“參考模型”（如人工標注的簇劃分）比較，通過樣本對的匹配情況計算。
• 關鍵參數：
  • $a$：同簇且參考模型中同簇的樣本對數量；
  • $b$：同簇但參考模型中不同簇的樣本對數量；
  • $c$：不同簇但參考模型中同簇的樣本對數量；
  • $d$：不同簇且參考模型中不同簇的樣本對數量。
• 常用指標：
  • Jaccard系數（JC）：$JC=\frac{a}{a+b+c}$；
  • FM指數（FMI）：$FMI=\sqrt{\frac{a}{a+b}?\frac{a}{a+c}}$；
  • Rand指數（RI）：$RI=\frac{2(a+d)}{m(m?1)}$。

（二）內部指標（直接評價聚類結果）

• 定義：基于聚類結果自身的統計特性（如距離、密度）評價，無需參考模型。
• 關鍵參數：
  • $avg(C)$：簇$C$內樣本平均距離；
  • $diam(C)$：簇$C$內樣本最大距離；
  • $d_{min}(C_i,C_j)$：簇$C_i$與$C_j$的最近樣本距離；
  • $d_{cen}(C_i,C_j)$：簇$C_i$與$C_j$的中心距離。
• 常用指標：
  • DB指數（DBI）：$DBI=\frac{1}{k}{\sum }_{i=1}^{k}ma{x}_{j\ne i}\left(\frac{avg(C_i)+avg(C_j)}{d_{cen}({\mu }_i,{\mu }_j)}\right)$（值越小越好）；
  • Dunn指數（DI）：$DI=mi{n}_{1\le i\le k}\left\{mi{n}_{j\ne i}\left(\frac{d_{min}(C_i,C_j)}{ma{x}_{1\le l\le k}diam(C_l)}\right)\right\}$（值越大越好）。

三、距離計算（聚類的基礎）

距離度量是聚類的核心，需滿足非負性、同一性、對稱性和直遞性，不同屬性類型需采用不同度量方式。

（一）常用距離

• 閔可夫斯基距離：$dist(x_i,x_j)={\left({\sum }_{u=1}^n|x_{iu}?x_{ju}{|}^p\right)}^{1/p}$，其中：
  • $p=2$為歐氏距離（最常用）；
  • $p=1$為曼哈頓距離。

（二）屬性類型與距離度量

1. 連續屬性：直接使用閔可夫斯基距離；
2. 離散屬性：
   • 有序屬性：可轉換為連續值后用閔可夫斯基距離；
   • 無序屬性：用VDM距離：
     $$VD{M}_p(a,b)=\sum _{i=1}^k{\left|\frac{m_{u,a,i}}{m_{u,a}}?\frac{m_{u,b,i}}{m_{u,b}}\right|}^p$$
     （$m_{u,a,i}$為第$i$簇中屬性$u$取$a$的樣本數，$m_{u,a}$為屬性$u$取$a$的總樣本數）；
3. 混合屬性：結合閔可夫斯基距離和VDM：
   $$MinkovD{M}_p(x_i,x_j)={\left(\sum _{連續屬性}|x_{iu}?x_{ju}{|}^p+\sum _{無序屬性}VD{M}_p(x_{iu},x_{ju})\right)}^{1/p}$$

四、原型聚類（基于原型的聚類）

原型聚類假設聚類結構可通過“原型”（如中心、概率分布）刻畫，通過迭代優化原型實現聚類。

（一）k均值算法（k-means）

• 核心思想：最小化簇內平方誤差$E={\sum }_{i=1}^k{\sum }_{x\in C_i}\Vert x?{\mu }_i{\Vert }_2^2$（${\mu }_i$為簇$C_i$的均值向量）。
• 算法步驟：
  1. 隨機選擇$k$個樣本作為初始均值向量{μ1,μ2,...,μk}\{\mu_1, \mu_2, ..., \mu_k\}{μ1?,μ2?,...,μk?}；
  2. 迭代：
     • 簇劃分：將每個樣本劃入距離最近的均值向量對應的簇；
     • 更新均值：計算每個簇的新均值向量${\mu }_i=\frac{1}{|C_i|}{\sum }_{x\in C_i}x$；
  3. 終止：均值向量不再更新時停止。
• 特點：高效易實現，但對初始中心敏感，適用于凸形分布數據。
  

• 模型定義：混合分布$p_M(x)={\sum }_{i=1}^k{\alpha }_{i}p(x|{\mu }_i,{\Sigma }_i)$，其中${\alpha }_i$為混合系數（$\sum {\alpha }_i=1$），$p(x|{\mu }_i,{\Sigma }_i)$為第$i$個高斯分布（均值${\mu }_i$，協方差${\Sigma }_i$）。
• 求解方法（EM算法）：
  1. 初始化參數{αi,μi,Σi}\{\alpha_i, \mu_i, \Sigma_i\}{αi?,μi?,Σi?}；
  2. 迭代（E步→M步）：
     • E步：計算樣本$x_j$屬于第$i$個成分的后驗概率${\gamma }_{ji}=\frac{{\alpha }_{i}p(x_j|{\mu }_i,{\Sigma }_i)}{{\sum }_{l=1}^k{\alpha }_{l}p(x_j|{\mu }_l,{\Sigma }_l)}$；
     • M步：更新參數${\alpha }_i=\frac{1}{m}{\sum }_j{\gamma }_{ji}$，${\mu }_i=\frac{{\sum }_j{\gamma }_{ji}{x}_j}{{\sum }_j{\gamma }_{ji}}$，${\Sigma }_i=\frac{{\sum }_j{\gamma }_{ji}(x_j?{\mu }_i)(x_j?{\mu }_i{)}^T}{{\sum }_j{\gamma }_{ji}}$；
  3. 終止：似然函數收斂。
• 特點：靈活擬合復雜分布，可輸出樣本屬于各簇的概率，但計算復雜度高。

五、層次聚類（樹形結構聚類）

層次聚類通過逐層合并或拆分簇，形成樹形聚類結構，分為自底向上（聚合）和自頂向下（分拆）策略。

（一）AGNES算法（自底向上聚合）

• 核心思想：初始將每個樣本視為一個簇，迭代合并距離最近的兩個簇，直至達到預設簇數$k$。
• 簇距離度量：
  • 最小距離：$d_{min}(C_i,C_j)=mi{n}_{x\in C_i,z\in C_j}dist(x,z)$；
  • 最大距離：$d_{max}(C_i,C_j)=ma{x}_{x\in C_i,z\in C_j}dist(x,z)$；
  • 平均距離：$d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}{\sum }_{x\in C_i}{\sum }_{z\in C_j}dist(x,z)$。
• 特點：生成層次化簇結構，便于可視化，但計算復雜度高（$O(m^{2}logm)$），對噪聲敏感。

總結

聚類通過無監督方式揭示數據內在結構，性能可通過外部或內部指標評價。距離計算需根據屬性類型選擇（如連續屬性用歐氏距離，無序屬性用VDM）。原型聚類（k均值、高斯混合）高效且適用于大規模數據；層次聚類（AGNES）生成樹形結構，適合探索數據層次關系。實際應用中需根據數據分布和任務需求選擇算法。

上一章：機器學習08——集成學習
下一章：機器學習10——降維與度量學習
機器學習實戰項目：【從 0 到 1 落地】機器學習實操項目目錄：覆蓋入門到進階，大學生就業 / 競賽必備