聚類分析常用算法原理：KMeans,DBSCAN, 層次聚類

鞅牛 2019-02-28

展開全文

聚類分析是非監(jiān)督學習的很重要的領域。所謂非監(jiān)督學習，就是數據是沒有類別標記的，算法要從對原始數據的探索中提取出一定的規(guī)律。而聚類分析就是試圖將數據集中的樣本劃分為若干個不相交的子集，每個子集稱為一個“簇”。下面是sklearn中對各種聚類算法的比較。
這里寫圖片描述

KMeans

KMeans算法在給定一個數k之后，能夠將數據集分成k個“簇” $C = {C_{1}, C_{2}, \dots, C_{k}}$ ，不論這種分類是否合理，或者是否有意義。算法需要最小化平方誤差：

E = \sum_{i = 1}^{k} \sum_{x \in C_{i}} ‖ x - μ_{i} ‖^{2} (1)

其中

μ_{i} = \frac{1}{| C_{i} |} \sum_{x \in C_{i}} x

是簇

C_{i}

的均值向量，或者說是質心。其中

‖ x - μ_{i} ‖^{2}

代表每個樣本點到均值點的距離（其實也是范數）。這里就稍微提一下距離度量。
距離度量最常用的就是閔可夫斯基距離（亦即p范數），即

d i s t_{m k} (x_{i}, x_{j}) = (\sum_{u = 1}^{n} | x_{i u} - x_{j u} |^{p})^{1 / p} (2)

當p==2的時候，閔可夫斯基距離即為歐氏距離（2范數）
當p==1的時候，閔可夫斯基距離即為曼哈頓距離（1范數或者叫 cityblock distance）

以上是對于數值屬性來說的，對于一些離散屬性也有相關的距離的定義。最后在現實中的數據如果要確定合適的距離計算式，可以通過“距離度量學習”來實現。

也就是說上面的式（1）的目的就是我們要找到k個簇，使得在每個簇內，所有的樣本點都盡量靠得比較近。

下面介紹KMeans的基本算法流程
輸入：樣本數據集 $D$ ，聚類簇數k
(1) 從樣本中隨機選取k個樣本點作為初始的均值向量 ${μ_{1}, μ_{2}, \dots, μ_{k}}$
(2)循環(huán)以下幾步直到達到停止條件：
（2.1）令 $C_{i} = \emptyset (1 \leq i \leq k)$
（2.2）對所有樣本點計算他們到k個均值向量之間的距離，取其中距離最短的距離對應的均值向量的標記作為該點的簇標記，然后將該點加入相應的簇 $C_{i}$
（2.3）對每一個簇計算他們新的均值向量 $μ_{i} = \frac{1}{| C_{i} |} \sum_{x \in C_{i}} x$ ，如果相比之前的向量有變化，就更新，將其作為新的均值向量，如果沒有變化就不變

可以看出KMeans的基本算法是很容易理解的，算法本身也挺簡單，運行較快，所以KMeans可用于非常大型的數據集。但是KMeans也有一些缺點
（1）對初始值敏感。KMeans可能由于初始值選的不同，導致最終結果的不同。我的理解是我們要優(yōu)化的其實是式（1），但是它很難優(yōu)化，所以我們采用的是一種貪心算法，那么這種算法就可能掉進局部最優(yōu)的坑里面，所以我們要盡量多選幾個初始值多計算幾次。不過scikit-learn里面KMeans的算法的參數里面有個’init’參數，將其設置成’init = k-means++’可以在初始化均值向量的時候讓他們之間盡量分開。
（2）對特殊分布的數據集不能夠得出合理的結果
這里寫圖片描述
比如上圖，我們希望的結果應該是左圖，但是KMeans只能得出右圖，不能得出我們想要的結果，但是這不是KMeans單獨的缺點，很多聚類算法對這種情況或者數據分布是一種長條形等的一類特殊情況效果都不甚理想。這些情況在文章開頭的圖中都有所體現。

總體上KMeans以及它很多聚類算法對于每一簇數據分布都是凸的情況效果都很好。
除了KMeans之外，我們還有一些它的變體的算法比如 Mini Batch K-means 或者Learning Vector Quantization (LVQ)等，在這里就不再贅述。

密度聚類（DBSCAN）

密度聚類的思想是不同于KMeans的，但是更符合我們人類的思維，基本的思想是通過是否緊密相連來判斷樣本點是否屬于一個簇。代表性的算法就是DBSCAN，它基于一組鄰域參數 $(ϵ, M i n P t s)$ 來表征某處樣本是否是緊密的。在介紹算法之前先介紹一些概念。
$ϵ$ -鄰域：即對于樣本點 $x_{i}$ ，和它的距離在 $ϵ$ 之內的屬于樣本集 $D$ 中的點的集合，即 $N_{ϵ} (x_{j}) = {s_{i} \in D | d i s t (x_{i}, x_{j}) \leq ϵ}$

核心對象:若 $x_{j}$ 的 $ϵ$ -鄰域至少包含 $M i n P t s$ 個樣本，即 $| N_{ϵ} (x_{j}) | \geq M i n P t s$ ，那么 $x_{j}$ 是一個核心對象。其實也就是在核心對象周圍的點相對鄰域參數來說是致密的。

密度直達與可達：直達的意思是點 $x_{j}$ 位于點 $x_{i}$ 的 $ϵ$ -鄰域中?？蛇_的意思是存在這么一個樣本序列 $p_{1}, p_{2}, \dots, p_{n}$ ， $x_{j}$ 到 $p_{1}$ 是直達的， $p_{1}$ 到 $p_{2}$ 是直達的，就這樣不斷地借著這些樣本作為“跳板”， $x_{j}$ 可以間接地“跳到” $x_{i}$ 。

密度相連：對于樣本點 $x_{j}$ 和 $x_{i}$ 若存在點 $x_{k}$ 使得 $x_{j}$ 和 $x_{i}$ 均可由 $x_{k}$ 密度可達，則稱 $x_{j}$ 和 $x_{i}$ 密度相連。

最后由DBSCAN所定義的簇的概念為：由密度可達關系導出的最大的密度相連樣本集合。
下圖為DBSCAN的一個結果示意圖
這里寫圖片描述
如圖算法自動將數據集分成了3簇，用三種顏色代表。每一簇內較大的點代表核心對象，較小的點代表邊界點（與簇內其他點密度相連，但是自身不是核心對象）。黑色的點代表離群點或者叫噪聲點。
另外從最上面的圖也能夠看出DBSCAN的表現還是很不錯的。

下面是DBSCAN的基本算法步驟：
這里寫圖片描述

其實周志華老師的書《機器學習》上對算法的描述更清晰，感興趣的可以去看看。

這里提一個我的想法，我在看算法的時候就覺得這個算法有點眼熟，后來想起來發(fā)現跟廣度優(yōu)先搜索有點像，再想想發(fā)現DBSCAN的思路就是和廣度優(yōu)先很想。比如密度直連的兩個點之間可以看作這兩個點相連，密度可達可以看作兩個點之間存在一條路徑，找出所有的簇就可以看作找出整個圖中的連通分量。另外在數據結構上DBSCAN和廣度優(yōu)先都使用了隊列來儲存訪問到的點。只是由 $(ϵ, M i n P t s)$ 來確定兩個點是否相連。以上提供一個視角以供參考。

DBSCAN的優(yōu)點：
（1）可以解決數據分布特殊（非凸，互相包絡，長條形等）的情況
（2）對于噪聲不敏感
（3）速度較快，可適用于較大的數據集
（4）在鄰域參數 $(ϵ, M i n P t s)$ 給定的情況下，結果是確定的，只要數據進入算法的順序不變，與初始值無關，這里就和KMeans不同
（5）不需要指定簇的個數

缺點：
（1）簇之間密度差距過大時效果不好，因為對整個數據集我們使用的是一組鄰域參數
（2）數據集較大的時候很消耗內存，目前在scikit-learn中已經可以使用ball-trees 和 kd-trees來確定鄰居點（可以看出找出點的鄰域內有幾個點是DBSCAN最基本，最多的操作）,但是在默認情況下是不使用他們的，而是使用很消耗內存的距離矩陣。
（3）對于高維數據距離的計算會比較麻煩，造成“維數災難”

層次聚類（hierarchical clustering）

層次聚類是一類算法的總稱，是通過從下往上不斷合并簇，或者從上往下不斷分離簇形成嵌套的簇。這種層次的類通過“樹狀圖”來表示。AgglomerativeClustering算法是一種層次聚類的算法。
下面大致講一下 AgglomerativeClustering算法。

算法的原理很簡單，最開始的時候將所有數據點本身作為簇，然后找出距離最近的兩個簇將它們合為一個，不斷重復以上步驟直到達到預設的簇的個數。

可以看到，一個很關鍵的地方就是判斷簇之間的距離。判斷的準則叫做鏈接準則。對于AgglomerativeClustering算法，scikit-learn有三種準則

· Ward minimizes the sum of squared differences within all clusters. It is a variance-minimizing approach and in
this sense is similar to the k-means objective function but tackled with an agglomerative hierarchical approach.
· Maximum or complete linkage minimizes the maximum distance between observations of pairs of clusters.
· Average linkage minimizes the average of the distances between all observations of pairs of clusters.

三種準則有所不同，在后面的文章中再來探討他們的區(qū)別
AgglomerativeClustering也是適用于較大的數據集的，尤其是在有connectivity constraint的時候，什么是connectivity constraint？下面有一個圖
這里寫圖片描述

左邊是沒有connectivity constraint的，可以看到有些藍色的簇橫跨了兩片（只能這么表述了），右邊有connectivity constraint的情況下，簇可以看到基本就是沿著彎曲的平面分布的，這種結果可能更合理，并且是可以加快計算速度的，尤其是在數據量很大的情況下。因為對于每個點只需要考慮和它相鄰的點，而不是考慮所有的點。但是connectivity constraint需要一個叫做connectivity matrix的東西，這個矩陣我也不清楚具體形式，寫這些只是提醒有connectivity constraint這么個東西存在。

還有，從最上方的圖中也能夠看出AgglomerativeClustering算法對于形狀比較怪異的分布也有較好的效果

綜上就是我挑出的三個主要的聚類算法進行了大致的介紹，另外還有一個算法：高斯混合模型，我準備把它和EM算法一起單獨寫篇文章。聚類算法可以作為一些監(jiān)督算法的前驅過程，又是非監(jiān)督學習的重要部分，還是很重要的。

參考：
DBSCAN聚類原理
 DBSCAN密度聚類算法