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

鞅牛 2019-02-28

展開全文

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

KMeans

KMeans算法在給定一個數(shù)k之后，能夠?qū)?shù)據(jù)集分成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}

的均值向量，或者說是質(zhì)心。其中

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

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

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范數(shù)）
當p==1的時候，閔可夫斯基距離即為曼哈頓距離（1范數(shù) 或者叫 cityblock distance）

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

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

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

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

密度聚類（DBSCAN）

密度聚類的思想是不同于KMeans的，但是更符合我們?nèi)祟惖乃季S，基本的思想是通過是否緊密相連來判斷樣本點是否屬于一個簇。代表性的算法就是DBSCAN，它基于一組鄰域參數(shù) $(ϵ, M i n P t s)$ 來表征某處樣本是否是緊密的。在介紹算法之前先介紹一些概念。
$ϵ$ -鄰域：即對于樣本點 $x_{i}$ ，和它的距離在 $ϵ$ 之內(nè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}$ 是一個核心對象。其實也就是在核心對象周圍的點相對鄰域參數(shù)來說是致密的。

密度直達與可達：直達的意思是點 $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的一個結(jié)果示意圖
這里寫圖片描述
如圖算法自動將數(shù)據(jù)集分成了3簇，用三種顏色代表。每一簇內(nèi)較大的點代表核心對象，較小的點代表邊界點（與簇內(nèi)其他點密度相連，但是自身不是核心對象）。黑色的點代表離群點或者叫噪聲點。
另外從最上面的圖也能夠看出DBSCAN的表現(xiàn)還是很不錯的。

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

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

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

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

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

層次聚類（hierarchical clustering）

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

算法的原理很簡單，最開始的時候?qū)⑺袛?shù)據(jù)點本身作為簇，然后找出距離最近的兩個簇將它們合為一個，不斷重復以上步驟直到達到預設的簇的個數(shù)。

可以看到，一個很關鍵的地方就是判斷簇之間的距離。判斷的準則叫做鏈接準則。對于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也是適用于較大的數(shù)據(jù)集的，尤其是在有connectivity constraint的時候，什么是connectivity constraint？下面有一個圖
這里寫圖片描述

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

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

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

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