這是我參與8月更文挑戰的第11天，活動詳情查看：8月更文挑戰

本文為吳恩達機器學習課程的筆記系列第五篇，主要介紹幾個聚類算法，包括經典的K-Means算法，以及其拓展 二分K-Means算法和另一個常用的DBSCAN算法

聚類(Clustering)

聚類(Clustering)是將數據集劃分為若幹相似對象組成的多個組(group)或簇(cluster)的過程， 使得同一組中對象間的相似度最大化， 不同組中對象間的相似度最小化 。屬於無監督問題。

K-Means算法

$K$ 就是簇的數量。這個數字是人為選擇的。K-Means算法是基於質心劃分的。

算法流程：

• 首先隨機選擇 $K$ 個點作為初始聚類中心。
• 對數據集的每個數據，評估其到 $K$ 個中心點的距離，將其與距離最近的中心點關聯起來。
• 重新計算每個簇中的平均值，更新簇中心的比特置

距離的判斷：歐幾裏得距離或餘弦相似度

算法描述：

• $\mu^{(i)}$ 錶示第 $i$個聚類中心， $x^{(i)}$ 錶示第 $i$個樣本， $m$ 錶示樣本數

算法優化

K-Means同樣也要最小化聚類代價，而最小化的就是所有的數據點與其所關聯的聚類中心點之間的距離之和，引入K-Means的代價函數：

$J(c^{(1)},...,c^{(m)},\mu^{(1)},...,\mu^{(K)})=\dfrac{1}{m}\sum\limits_{i=1}^{m}||x^{(i)}-\mu^{c^{(i)}}||^2$ $J$ 也稱畸變函數（Distortion Function）

實際上，在第一個for循環裏，也就是給樣本分配簇中心時，就是在减小 $c^{(i)}$ 引起的代價；在第二個for循環裏，則是在减小 $\mu^{(k)}$ 引起的代價。

確定k值

因為不同的初始化很有可能會引起不同的聚類結果，所以應用聚類算法時往往進行多次隨機初始化，計算相應代價函數，應用 肘部法則（Elbow Method），選擇較為明顯的“肘關節”部分對應的 k 值作為聚類數。如下圖：

下面補充幾個其它常見的聚類算法：

二分K-Means算法

二分 K-Means（bisecting kmeans）算法，相較於常規的 K-Means，二分 K-Means 不急於一來就隨機 K個聚類中心，而是首先把所有點歸為一個簇，然後將該簇一分為二。計算各個所得簇的代價函數（即誤差），選擇誤差最大的簇再進行劃分（即最大程度地减少誤差），重複該過程直至達到期望的簇數目。

誤差采用 SSE（Sum of Squared Error）即誤差平方和。SSE越小，簇中的對象越集中 。

該算法為貪心算法，計算量不小。

DBSCAN算法

DBSCAN算法是基於密度的算法，該算法將具有足够高密度的區域劃分為簇，並在具有噪聲的空間數據庫中發現任意形狀的簇，它將簇定義為密度相連的點的最大的集合。

基本概念：

• $Eps$ 鄰域：給定對象半徑 $Eps$ 內的鄰域稱為該對象的 $Eps$ 鄰域。
• $MinPts$：給定鄰域包含的點的最小數目，用以决定點 $p$是簇的核心部分還是邊界點或噪聲。
• 核心對象：如果對象的 $Eps$ 鄰域包含至少 $MinPts$ 個的對象，則稱該對象為核心對象。
• 邊界點：邊界點不是核心點，但落在某個核心點的鄰域內。稠密區域邊緣上的點。
• 噪音點：既不是核心點，也不是邊界點的任何點。 稀疏區域中的點。
• 直接密度可達： 如果 $p$ 在 $q$ 的 $Eps$鄰域內， 而 $q$ 是一個核心對象， 則稱對象 $p$ 從對象 $q$ 出發時是直接密度可達的 (directly densityreachable)。
• 密度可達： 如果存在一個對象鏈 $p_1,p_2,...,p_n,p_1=q,p_n=p$， 對於 $p_i\in D(1\le i\le n)$， $p_{i+1}$ 是 $p_i$ 從關於 $Eps$ 和 $MinPts$ 直接密度可達的，則 對 象 $p$ 是 從對象 $q$ 關於 $Eps$ 和 $MinPts$ 密 度 可 達 的 (densityreachable)。
• 密度相連： 如果存在對象 $O\in D$， 使對象 $p$ 和 $q$ 都是從 $O$ 關於 $Eps$ 和 $MinPts$ 密度可達的， 那麼對象 $p$ 到 $q$ 是關於 $Eps$ 和 $MinPts$ 密度相連的(density-connected)。
• 基於密度的簇：是基於密度可達性的最大的密度相連的對象的集合 。
• 噪聲：不包含在任何簇中的對象。

DBSCAN算法， 就是檢查數據集中每個點的 $Eps$ 鄰域來搜索簇。

算法流程

算法優劣

優勢：

• 不需要指定簇個數
• 擅長找到離群點（檢測任務）
• 可以發現任意形狀的簇
• 只需兩個參數

劣勢：

• 參數難以選擇（參數對結果的影響非常大）
• 高維數據有些困難（可以做降維）