引言
文章根據(jù)udacity 的機器學習視頻進行整理，提供給初學者進行參考。主要圍繞幾種聚類算法：K-Means、層次聚類、DBSCAN、高斯混合模型聚類(GMM) 幾種聚類算法進行敘述。簡單講述算法原理、算法在sklearn中實現(xiàn)、相關(guān)應用案例的論文、算法優(yōu)缺點等。最后介紹評價聚類算法的兩種指標：調(diào)整蘭德系數(shù)和輪廓系數(shù)。
相關(guān)參考學習視頻：
udacity--機器學習（PS：國外導師視頻課程，中文字幕。課程簡潔易懂、生動形象。具有項目實戰(zhàn)、導師項目審核特色。比較推薦入門。點擊此處可獲得課程優(yōu)惠券）
coursera--吳恩達機器學習(PS:? 吳恩達的機器學習一直備受入門的歡迎。內(nèi)容詳細、由淺入深。)
書籍：吳恩達機器學習筆記
1. K均值聚類(K-Means)
1.1 算法概述
K-均值是最普及的聚類算法，算法接受一個未標記的數(shù)據(jù)集，然后將數(shù)據(jù)聚類成不同的組。
K-均值是一個迭代算法，假設我們想要將數(shù)據(jù)聚類成 n 個組，其方法為:
????1. 首先選擇 k 個隨機的點，稱為聚類中心(cluster centroids), 也叫質(zhì)心;
????2. 對于數(shù)據(jù)集中的每一個數(shù)據(jù)，按照距離 K 個中心點的距離，將其與距離最近的中心點關(guān)聯(lián)起來，與同一個中心點關(guān)聯(lián)的所有點聚成一類。
????3. 計算每一個組的平均值，將該組所關(guān)聯(lián)的中心點移動到平均值的位置。
可視化均值聚類過程?？稍?a href="http://www.itdecent.cn/%E2%97%8B%20https://www.naftaliharris.com/blog/visualizing-k-means-clustering/" target="_blank">此點擊進行詳細了解。該網(wǎng)站將均值聚類的方法通過動態(tài)畫方式進行展示，可以幫助理解均值聚類的過程。
1.2 K-Means 性質(zhì)
K-Means 在指定質(zhì)心之后，需要進行多次迭代。在“多次迭代”和“更新質(zhì)心”的中，會算法最終達到收斂。但不幸的是算法最終會收斂，但是收斂最終集群卻不唯一，這取決于初始化的質(zhì)心的位置。如何初始化質(zhì)心的位置？（可見1.3 K-Means 初始化策略）
K-Means 需要先指定 k 值，即聚類的數(shù)量。通常情況下，并不知道聚類的數(shù)量為多少？選擇聚類數(shù)量可通過肘部法 (見1.4 選擇聚類的數(shù)量)。
1.3 K-Means 初始化策略
如何初始化K-Means質(zhì)心的位置？ 有三種方法：
1. 隨機初始化所有的聚類中心點。隨機選擇 K 個訓練實例，然后令K個聚類中心分別于K個訓練實例相等，但有可能會停留在一個局部最小值處，這取決于初始化情況。解決這個問題，通常需要多次運行 K-均值算法，每一次都重新進行隨機初始 化，最后再比較多次運行 K-均值的結(jié)果，選擇代價函數(shù)最小的結(jié)果。這種方法如果K比較大，那么效果不會有明顯改善。
2. 以“最遠的”啟發(fā)式方法實現(xiàn)。隨機初始化第一個質(zhì)心，然后將第二個質(zhì)心初始化為距離它最遠的數(shù)據(jù)點。
3.?k-means ++?；?K-Means 的改進。它的工作方式與“最遠的”啟發(fā)式相似，不同的是，它選擇了一個點，其概率與其到最近的質(zhì)心的距離的平方成正比，而不是選擇第j個質(zhì)心為距前一個質(zhì)心最遠的點。
1.4 選擇聚類的數(shù)量
通常情況下，選擇聚類的數(shù)量是需要根據(jù)不同的問題，人工進行選擇的。選擇的時候思考運用 K-均值算法聚類的動機是什么，然后選擇能最好服務于該目的標聚類數(shù)。
當選擇聚類數(shù)目時，通常會用到一個 “肘部法則” 的方法：
關(guān)于“肘部法則”，所需要做的是改變 k 值，也就是聚類類別數(shù)目的總數(shù)。這里利用K-均值的代價函數(shù)（又叫畸變函數(shù)）如圖：
選擇的K值不同，代價函數(shù)表現(xiàn)表現(xiàn)也不一樣。通常情況下是 K 值越多，代價函數(shù)越小。但在實際中 K 值(代表聚類數(shù)量) 不是要越多越好。K 值和代價函數(shù)之間通常可表現(xiàn)如下圖：
上圖中，可以看到這樣的曲線，像一個人的肘部。K 的選擇從 1 到 2 ，2 到 3 時代價函數(shù) J 下降最大。在 3 之后代價函數(shù) J 下降變緩。看起來當選擇 K = 3 時是相對比較好的。
選擇聚類數(shù)目也可以參考 輪廓系數(shù)。見“6.3 內(nèi)部評價指標-輪廓系數(shù)”
1.5 K-Means 的表現(xiàn)
K-Means在具有大致相等大小和大致規(guī)則形狀的聚類的數(shù)據(jù)集中效果最好。但在一些 “月牙數(shù)據(jù)” 中，K 值表現(xiàn)就不盡人意。如下圖K-means在一些數(shù)據(jù)集中的表現(xiàn)結(jié)果。
盡管有利有弊，但k-means算法還是聚類分析中的主要工具：它可在許多實際數(shù)據(jù)集上很好地工作，并且相對較快，易于實現(xiàn)且易于理解。許多改進或推廣k均值的聚類算法，例如：k中值，k medoids，k-means ++和用于高斯混合的EM算法。
1.6 Sklearn 中的 K-Means
sklearn 中 K-Means 的相關(guān)介紹及實現(xiàn)
sklearn 中封裝 K-Means API
exmaple ：
2. 層次聚類(Hierarchical Clustering)
2.1 概述
層次聚類(Hierarchical Clustering)是聚類算法的一種，通過計算不同類別數(shù)據(jù)點間的相似度來創(chuàng)建一棵有層次的嵌套聚類樹。層次如同公司內(nèi)部的人員體系，最高層是老板、老板下面是部門經(jīng)理、部門經(jīng)理下面是每個部門的員工。
層次聚類可以直觀的了解類之間的關(guān)系。如下圖：
2.2 四種不同的層次聚類法
2.2.1 概述
層次聚類法在主要有：單鏈接聚類法、全鏈接聚類法、組平均聚類、離差平方和法。四種不同的層次聚類算法基本原理基本相同，主要區(qū)別在于衡量距離的方式不同。
2.2.2 單鏈接聚類
基本原理:?
1. 假設數(shù)據(jù)特征如下圖模式：
2. 先假設每個點是一個類，然后計算任意兩個類之間的距離。把距離最近的兩個類合并成一個類。建立第一層，
如下圖：將 1 和 2 合并為一類；4 和 5 合并為一類；6 和 8 合并為一類；3 、7 單獨為一個類。
3. 在上面的基礎上再計算兩個類之間的距離。把距離最近的兩個類合并為一個類。組建為第二層。
上圖中可見：7 類 距離 [6,8] 類比較近。 這里注意單鏈接算法中兩個類的距離，是以兩個類中兩點之間的最短距離為標準，如：7 到 6 的距離。由此，可將 3 、1、2 合并為一類；7、6、8 合并為一類。
4. 以此建立為一個完整的系統(tǒng)樹。如下圖：
單鏈接聚類法衡量距離的方法是兩類之間兩點最短的距離。將距離最短的類合并。如下圖：
2.2.3 全鏈接聚類法表現(xiàn)
全鏈接聚類中衡量距離的方法是兩類中最遠的兩點之間的距離，這樣的衡量方法使得產(chǎn)生的類比較緊湊。
但是這些點可能是其他類中的一部分，全鏈接聚類法就忽視了它們，只考慮最遠的兩點。因此需要考慮其他方法，可參考下面的組平均和離差平方法。
如下圖兩個類中兩點之間的最遠距離：
2.2.4 組平均聚類法
組平均聚類法計算的是任意兩點之間的距離，然后取平均值。
如下圖：
2.2.4 離差平方和法
離差平方和法是sklearn中預設的一種層次聚類法。這種方法的目的就是把合并類時的變量最小化。
離差平方和法計算兩類間距離的方法：
1. 找一個中心點，取所有點之間的平均位置，所得即為中心點。
2. 然后計算所有點與中心點之間的距離。分別計算其平方、再相加
3. 再減去類中的變量平方。找到類中變量的方法：找到每個類的中心點，然后計算類中點到中心點的距離。
下圖中：X 為中心點、C 為兩類中的點到中心點的距離、A 和 B 分別為類中變量的平方。
2.3 表現(xiàn)
層次聚類中各種聚類算法在數(shù)據(jù)集中的表現(xiàn)：
優(yōu)點：
層次表達、內(nèi)容鮮明、把聚類結(jié)果可視化。特別是當數(shù)據(jù)有層次結(jié)構(gòu)的時候，例如生物學。
缺點：
對噪音和離群值比較敏感。需要提前清理噪聲
計算量大。如果數(shù)據(jù)規(guī)模大、算法的執(zhí)行會比較慢。
案例：
把分泌蛋白聚類，并創(chuàng)建不同的類表示不同種類的真菌
2.4 sklearn 中的層次聚類
sklearn 中的層次聚類法：https://scikit-learn.org/stable/modules/clustering.html#hierarchical-clustering
sklearn 中的層次聚類API：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.FeatureAgglomeration.html#sklearn.cluster.FeatureAgglomeration
如果需要繪制層次樹，需要借助 SciPy ：
3. 密集聚類(DBSCAN)
3.1 概述
密集聚類指的是具有噪聲的基于密度的聚類方法。對噪聲具有很強的適用性。一般是把密集分布的點進行聚類，再將剩余的點標記為噪聲。這種算法對 “月牙” 數(shù)據(jù)非常適用
3.2 基本原理
1. 假定這是對應的數(shù)據(jù)特征：
2. DBSCAN 在開始時任意選擇一點。選擇這個點后，查看點的領域。所謂領域是由 Epsilon 界定的，在算法開始時候指定。假如指定 Epsilon = 1 如下圖：
3. 該點的領域內(nèi)沒有任何點，則它不屬于任何類，標記為噪聲。再重新選擇一個點查看領域。
4. 如果重新選擇的點中，包括其他點。需要查看包含點的數(shù)量是否滿足指定數(shù)量。這里的指定數(shù)量用MinPts 指定，也是在算法開始時指定。假如指定 MinPts = 5 。表示領域內(nèi)必須由5個或5個以上的點才滿足要求，否則標為噪聲。如下圖找到Cluster 1
5. 同時再繼續(xù)尋找，如果遇到多個數(shù)據(jù)點緊湊在一起，如下圖，則標記為 cluster 2
3.3 表現(xiàn)
DBSCAN與K-Means 算法對比，在各種數(shù)據(jù)集的表現(xiàn)：
優(yōu)點
不需要指明類的數(shù)量。DBSCAN能根據(jù)點的分布密度找到類。
不受限于某種外形的類，能靈活找到并分離各種形狀和大小的類
能處理噪聲和離群值
缺點
從兩個類可達的邊界點被分配給另一個類，因為這個類先發(fā)現(xiàn)的這個邊界點，由于各個點被隨機拜訪，這種情況不能保證回傳相同的聚類。但這種情況大多數(shù)數(shù)據(jù)集不會出現(xiàn)。
在找到不同密度的類方面有一定的困難?；谶@個可以用DBSCAN的變體HDBSCAN 即具有噪聲的基于密度的高層次空間聚類算法
應用案例
網(wǎng)絡流量的研究。論文：Traffic Classification Using Clustering Algorithms
對溫度數(shù)據(jù)值做異常檢測論文：Anomaly detection in temperature data using dbscan algorithm
3.4 sklearn 中的DBSCAN
sklearn 中的DBSCAN ：https://scikit-learn.org/stable/modules/clustering.html#hierarchical-clustering
sklearn 中 DBSCAN 的 API：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN
4. 高斯混合模型聚類(GMM)
4.1 概述
高斯混合模型聚類(Gaussian Mixture Models) 是一種相對溫和的聚類算法。意思是數(shù)據(jù)中的每個點，每個樣本都屬于現(xiàn)有的類。只是隸屬不同。
例如：有這樣的一組一維數(shù)據(jù)集。
高斯混合模型算法會檢查每個點，算法會認為該點似乎是由高斯分布產(chǎn)生的。由此產(chǎn)生不同的隸屬度。如下圖：
高斯混合模型聚類算法是一種相對超前的算法。這種算法假設每個類都遵循統(tǒng)計分布的規(guī)律，它利用大量的概率和統(tǒng)計學知識來找出這些類。生活中很多都數(shù)據(jù)分布都遵循高斯分布(也叫正太分布) 的規(guī)律。如學生成績、人的身高。
4.2 一維高斯混合模型
4.2.1 一維高斯分布
1. 簡單概述一維高斯分布。以考試成績?yōu)槔?，考試成績一般都遵循高斯分布，如下圖：
2. 上圖中，中間可能有重疊的部分，無法看清，這時候需要借助柱狀體表示。柱狀圖的高度即為學生取得的分數(shù)。其中最高的柱狀表示頻次最多。即該分數(shù)段的學生最多。如下圖：
3.?由柱狀圖可以描述高斯分布或正太分布的曲線，同時描述正太分布曲線的數(shù)字有：平均值、標準差。在統(tǒng)計學中，以平均值為中心，向左減一個標準差，向右則加一個標準差。在1個標準差的范圍內(nèi)數(shù)據(jù)概率是 68%。（詳細可見統(tǒng)計學知識）。如下圖：
4.2.2 一維高斯混合模型聚類
同樣借助考試成績?yōu)槔齺砻枋鲆痪S高斯混合模型聚類。如下圖的數(shù)據(jù)集。
1. 假設數(shù)據(jù)集是由數(shù)學成績和物理成績混合的，因為是混合而成的數(shù)據(jù)，所以它并不是高斯分布。如下圖：
2.?但是在高斯混合模型中，能夠通過高斯混合分布，找到這是兩個類。高斯混合分布本身并不是高斯模型，而是兩個高斯混合模型的混合物，但包含兩個高斯分布。借助高斯分布，判斷點屬于對應的類。
如下圖：
4.3 二維高斯混合模型聚類
4.3.1 二維高斯分布
1. 同樣以考試成績?yōu)槔?，如下圖是學生的兩門考試成績，包含了平均值和標準差。
2. 借助二維圖表，把 chemistry Score 設置為 X 軸，Geology Score 設置為 Y 軸。將對應的數(shù)據(jù)投射到圖表中。如下圖：
3. 可以看到每個變量呈現(xiàn)高斯分布，因此被稱為多維高斯狀態(tài)分布。如果用一種視覺化看待，圓心是兩條軸的平均值，第一個橢圓是每條軸的平均值或加或減標準差，包含 68 % 的數(shù)據(jù)，第二個橢圓包含95%的數(shù)據(jù)集，第三個包含 99% 數(shù)據(jù)集。
4.3.2 二維高斯混合模型聚類
1. 假設有這樣的兩組數(shù)據(jù)，均為多變量高斯分布，也叫二維高斯分布。如下圖：
2.?假設現(xiàn)在將兩組數(shù)據(jù)集混合之后，無法檢索原來的數(shù)據(jù)集。現(xiàn)在得到的數(shù)據(jù)集也不符合高斯分布。但我們知道這是由兩個符合高斯分布的數(shù)據(jù)集混合而成的。如下圖：
3.?到此實現(xiàn)利用高斯分布規(guī)律找到兩個類，需要借助期望最大化算法(EM）。
算法步驟：
step 1: 初始化K個高斯分布(在本例中 K = 2)。需要給它們均值和標準差，有很多方法可以實現(xiàn)。最樸素方法是將它們設置為數(shù)據(jù)集本身的平均值。實踐中還有一種更好的方法，是在數(shù)據(jù)集上使用K均值，然后使用K均值生成聚類初始化高斯分布。
在這個例子中，我們選取任意點，為每個高斯選擇隨機均值和隨機方差(方差不是標準差，方差是標準差的平方) 。到此完成了第一步，如下圖：
step 2: 將數(shù)據(jù)軟聚類成初始化的的兩個高斯。這一步驟稱為 E 步驟。
數(shù)據(jù)集中，每個點有兩個值，可以看著 feature1 和 feature2 。該步驟需要計算每個點的隸屬度。
計算方式如下圖：
step3: 基于軟聚類重新估計高斯。這一步驟稱為M步驟
該步驟是將 step2 中的所有點對聚類的隸屬度，用這些隸屬度為高斯模型提出新的參數(shù)，即新的均值和方差。所以該步驟以 step2 的結(jié)果作為輸入，輸出新的均值和方差
新的均值計算：
新的方差計算：
現(xiàn)在有了新方差和均值，對比之前的均值和方差，可以看到有微微移動。這樣的過程可能需要重復5、10、20、30次直到收斂。
step4: 利用評估對數(shù)似然來檢查收斂。如果收斂，則返回結(jié)果。否則返回第二步反復進行，直到收斂
通過選取的方差、均值來最大化。其結(jié)果可以表示為，值越大，說明該模型里有需要的數(shù)據(jù)集
4.3.3 期望最大化示例
在上一節(jié)中使用高斯混合模型找到聚集的數(shù)據(jù)集。
如下圖：（黃色圓圈為需要找到的數(shù)據(jù)集）
上圖中很明顯使用圓形的高斯分布，無法收斂得到最終的兩個類。這是因為沒有選擇好初始化參數(shù)。我們需要做一個更好類型的初始化來初始化K值。這里可先使用K-Means的結(jié)果初始化高斯模型。使用K-Means做高斯混合模型的默認值，協(xié)方差為 full ，初始化將是K-Means的默認值。如果我們進行這個一個過程，將可能是這樣的。如下圖：
這可能是最近兩個數(shù)據(jù)集的模型，這就是高斯混合模型實現(xiàn)的。其他聚類模型或許無法實現(xiàn)。
4.4 表現(xiàn)
優(yōu)點：
提供軟聚類，軟聚類是多個實例屬性的隸屬度。（比如說：你正在對文檔進行分類，并且希望每個文檔有多個主題和類別。高斯混合模型聚類對這類場景很有用）
聚類方面具有靈活性，一個聚類中可以包含另一個聚類
缺點：
對初始化值比較敏感，可能收斂的局部最優(yōu)，但不是全局最優(yōu)。
收斂速度慢
相關(guān)應用論文：
Nonparametric discovery of human routines from sensor data
Application of the Gaussian mixture model in pulsar astronomy
參考：
4.4 Sklearn 中的高斯混合模型
sklearn 中高斯混合模型的API：https://scikit-learn.org/stable/modules/generated/sklearn.mixture.GaussianMixture.html?highlight=mixture#sklearn.mixture.GaussianMixture
5. 聚類分析過程
使用各種聚類算法的目的主要在于將數(shù)據(jù)集 data 轉(zhuǎn)化為 知識knowledge 。這個聚類算法的分析過程如下圖，選擇聚類算法只是其中一步。
step 1 ：特征選擇和特征提取
特征選擇：從一組候選特征中選擇特征，不必對所有的數(shù)據(jù)集使用聚類方法，有時候數(shù)據(jù)集特征可能有成千上百。進行聚類需要消耗大量的資源，我們需要使用一些工具來選取特征。
特征提取：對數(shù)據(jù)進行轉(zhuǎn)換，以生成有用的特征。最好的例子是PCA即主成成分分析。
step 2 :? 選擇聚類算法。
根據(jù)數(shù)據(jù)的特征選擇合適的算法。通常是試驗那一種算法能有更好的結(jié)果。沒有一個算法普遍適合。
step 3 ：聚類評價。
即評估一個聚類的效果如何，因此除了在情況下對結(jié)果進行可視化之外，還需要一些評估方法，這些方法被稱為指數(shù)，每一個指數(shù)稱為聚類的有效評價指標。
step 4 ：聚類結(jié)果的解釋
可以從最終聚類結(jié)構(gòu)中得到什么樣的見解
6. 聚類驗證
6.1 概述
聚類評價是客觀和定量評估聚類結(jié)果的過程。聚類評價指數(shù)有三種：外部指標、內(nèi)部指標、相對指標
外部指標：這是處理有標簽數(shù)據(jù)集時候使用的評分。因此在有標簽數(shù)據(jù)集的情況下，可使用外部指標來進行評價。
內(nèi)部指標：在數(shù)據(jù)集沒有標簽的情況下，則需要采用內(nèi)部指標進行評價。僅使用數(shù)據(jù)來衡量數(shù)據(jù)和結(jié)構(gòu)之間的吻合度。
相對指標：這些指標表明兩個聚類結(jié)構(gòu)中，哪一種在某種意義上更好。基本上所有的外部指標都能作為相對指標。
大多數(shù)評價指標都是通過緊湊性和可分性來定義的。緊湊性是衡量一聚類中元素之間彼此的距離?？煞中允遣煌垲愔g距離
6.2 外部評價指標-調(diào)整蘭德系數(shù)
外部評價指標是當數(shù)據(jù)集有標簽時使用的評分方法。
在下圖中可以看到在sklearn中給定的評分方法和范圍。輸入原始的標簽，它會產(chǎn)生在范圍內(nèi)的一個得分。大多數(shù)在[0,1] 內(nèi)。但調(diào)整蘭德系數(shù)在[-1, 1]。
調(diào)整蘭德系數(shù)中，調(diào)整蘭德系數(shù)中 ARI 值為評價指標，ARI 越接近 1 。聚類結(jié)構(gòu)越好。
可參考論文：Details of the Adjusted Rand index
6.3 內(nèi)部評價指標-輪廓系數(shù)
內(nèi)部評價指標是當無數(shù)據(jù)標簽時使用的評價指標。
在下圖中可以看到在sklearn中給定的評分方法和范圍。其中給定的輪廓系數(shù)評分范圍在[-1, 1] 內(nèi)。它會給任何一個聚類在[-1,1] 之間的一個評分
輪廓系數(shù)評價指標
1. 假設這是一個已經(jīng)聚類完成的數(shù)據(jù)集。需要利用輪廓系數(shù)進行評價打分。
2. 輪廓系數(shù)評分公式：
參數(shù) a ： 同一個聚類中到某個點其他樣本的平均距離，如下圖，藍色直線的距離。
參數(shù) b：b 是某個點距離其他類中的點最近的距離平均值。如下圖，就是黃色直線距離。
將a 和 b 代入公式即可得到輪廓系數(shù)。
獲取每個點的輪廓系數(shù)，取平均值。就得到這個聚類的輪廓系數(shù)。
3. 參考不同數(shù)據(jù)集情況下， K 值情況下輪廓系數(shù)的?？傻弥狵=3時候聚類結(jié)構(gòu)最好。同時可以借助輪廓系數(shù)來找到最優(yōu)的 K 值，即聚類數(shù)量。
但在DBSCAN下不能使用輪廓系數(shù)。
在“圓形”數(shù)據(jù)集情況下，DBSCAN聚類效果比較好，但是評分卻比較低。如下圖舉例，所以在DBSCAN中，可參考基于密度的聚類驗證
