聚類算法

K-means 算法

算法原理

K-means 是一種基于類內距離最小化的劃分式聚類算法，其核心思想是通過迭代優化將數據劃分為 K 個簇。目標函數為最小化平方誤差（SSE）：
$$SSE=\sum _{i=1}^K\sum _{x\in C_i}||x?{\mu }_i|{|}^2$$
其中 ${\mu }_i$ 是第 $i$ 個簇的質心。

算法步驟

1. 初始化：

   • 隨機選擇 K 個初始質心（或使用 k-means++ 優化初始化）

2. 迭代優化：

   • 分配階段：將每個樣本分配到距離最近的質心所屬簇
     C i = { x : ∣ ∣ x ? μ i ∣ ∣ 2 ≤ ∣ ∣ x ? μ j ∣ ∣ 2 , ? j } C_i = \{ x : ||x - \mu_i||^2 \leq ||x - \mu_j||^2, \forall j \} Ci?={x:∣∣x?μi?∣∣2≤∣∣x?μj?∣∣2,?j}
   • 更新階段：重新計算每個簇的質心
     $${\mu }_i=\frac{1}{|C_i|}\sum _{x\in C_i}x$$

3. 終止條件：

   • 質心位置不再變化（收斂）
   • 達到最大迭代次數
   • SSE 變化量小于閾值

特點

• 時間復雜度：$O(n?K?I?d)$，n 為樣本數，I 為迭代次數
• 需預先指定 K 值
• 對初始質心敏感，可能收斂到局部最優

---

DBSCAN 算法

算法原理

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一種基于密度可達性的聚類算法，由Ester等人在1996年提出，其核心思想是通過數據點的局部密度分布識別聚類結構，并有效處理噪聲。算法中的關鍵概念包括：

1. 核心點：以某點為中心、半徑ε鄰域內的點數≥MinPts的點，是簇形成的基礎。
2. 邊界點：位于核心點的ε鄰域內，但自身鄰域內點數＜MinPts的點。
3. 噪聲點：既非核心點也非邊界點的孤立點。
4. 密度可達性：若點A通過一系列核心點間接可達點B，則稱A與B密度可達。
5. 密度連通性：若存在核心點O，使得點A和B均密度可達于O，則A與B密度連通。

算法步驟

1. 初始化參數：設置鄰域半徑ε和最小密度閾值MinPts。
2. 遍歷未訪問點：隨機選擇一個未訪問點，計算其ε鄰域內的點數：
   • 若點數＜MinPts：標記為噪聲點（可能后續被重新歸類為邊界點）。
   • 若點數≥MinPts：標記為核心點，創建新簇，遞歸合并所有密度可達點。
3. 擴展聚類：通過核心點的鄰域不斷吸收邊界點和可達核心點，直至無法擴展。
4. 重復處理：遍歷所有未訪問點，直至數據集處理完畢。

特性

• 時間復雜度：O(n log n)（使用空間索引時）
• 可發現任意形狀的簇
• 自動識別噪聲點
• 對參數敏感

---

聚類評估指標

1. 輪廓系數 (Silhouette Coefficient)

綜合衡量樣本的簇內緊密度和簇間分離度：
s ( i ) = b ( i ) ? a ( i ) max ? { a ( i ) , b ( i ) } s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}} s(i)=max{a(i),b(i)}b(i)?a(i)?

• $a(i)$：樣本 i 到同簇其他點的平均距離
• $b(i)$：樣本 i 到最近其他簇的平均距離
• 取值范圍：[-1, 1]，值越大聚類質量越高

2. Calinski-Harabasz 指數

通過方差比評估聚類質量：
$$CH=\frac{tr(B_k)/(K?1)}{tr(W_k)/(n?K)}$$

• $B_k$：簇間協方差矩陣
• $W_k$：簇內協方差矩陣
• 值越大表示簇間差異越大，簇內越緊密

---

K-means 的 K 值選擇方法詳解

肘部法則 (Elbow Method)

計算不同 K 值對應的 SSE：

sse = []
for k in range(1, 11):kmeans = KMeans(n_clusters=k)kmeans.fit(data)sse.append(kmeans.inertia_)