1. 章節(jié)主要內(nèi)容

“聚類”（clustering）算法是“無監(jiān)督學習”算法中研究最多嗜逻、應用最廣的算法栈顷，它試圖將數(shù)據(jù)集中的樣本劃分為若干個通常是不相交的子集嵌巷，每個子集稱為一個“簇”（cluster）

不同的簇分布代表著聚類算法對這組數(shù)據(jù)集觀測的不同角度，比如在不同屬性上進行分類會導致聚類算法將西瓜劃分為：“有籽瓜簇” “無籽瓜簇”靡努，”淺色瓜簇” “深色瓜簇”晓折，甚至“本地瓜簇” “外地瓜簇”等類別。

在此基礎上我們稍微擴展一下漾月，假設存在一個能對機器學習各種算法進行分類的聚類學習器胃珍，那么在訓練樣本是否有標記這個屬性上觅彰，它會將機器學習算法分為“監(jiān)督學習簇”、“非監(jiān)督學習簇”和“半監(jiān)督學習簇”烛芬；在預測結(jié)果是否是連續(xù)值這個屬性上飒责，它會將機器學習算法分為“回歸算法簇”和“分類算法簇”；在算法基本步驟這個屬性上擅憔，它會將機器學習算法分為“貝葉斯算法簇”、“決策樹算法簇”、“神經(jīng)網(wǎng)絡算法簇”等類別

需說明的是个榕，這些劃分的概念對聚類算法來說事先是未知的，聚類過程僅能自動生成簇結(jié)構(gòu)西采，簇所對應的概念語義需由使用者來把握和命名

因為聚類是在未標注樣本上的分類算法械馆，所以不像之前我們介紹的其它算法一樣，我們可以直觀的知道訓練出來的模型的好壞霹崎，即我們不能通過比對測試樣本的預測結(jié)果和真實預測結(jié)果誤差值來近似泛化誤差尾菇。

所以在介紹聚類的具體算法之前，我們得要先討論聚類算法涉及的最基本的問題：如何判斷一個聚類算法結(jié)果的好壞

1）聚類結(jié)果好壞的評估指標：性能度量

聚類性能度量亦稱聚類“有效性指標”（validity index）劳淆，與監(jiān)督學習一樣默赂，它的目的是為了用來評估聚類結(jié)果的好壞，當我們能通過性能度量來評估聚類的好壞時谒臼，我們就可以通過將這個性能度量作為優(yōu)化目標來生成更好的聚類結(jié)果耀里。

那么冯挎，對于聚類算法來說咙鞍，什么樣的結(jié)果是好的呢？

直觀上來看翰守，我們希望“物以類聚”疲酌，即同一簇的樣本盡可能彼此相似，不同簇的樣本盡可能不同湿颅。換言之，聚類結(jié)果的“簇內(nèi)相似度”（intra-cluster similarity）高且“簇間相似度”（inter-cluster similarity）低

按照這樣的定義崭庸，我們將聚類的性能度量大致劃分為了以下兩類：

［1］外部指標

這一類的性能度量是將聚類結(jié)果與某個“參考模型”（reference model）進行比較怕享，比如與領域?qū)＜业膭澐纸Y(jié)果進行比較（其實這已經(jīng)算是某種程度上對數(shù)據(jù)進行標注了）镰踏，稱為“外部指標”（external index）

基于對參考模型權(quán)威的信任，我們可以認為參考模型對樣本的劃分是滿足簇內(nèi)相似度高且簇間相似度低的驻呐。所以對于“外部指標”芳来，我們的度量目的就是要使得我們的聚類結(jié)果與參考模型盡可能相近即舌，通常通過將聚類結(jié)果與參考模型結(jié)果對應的簇標記向量進行兩兩比對，來生成具體的性能度量肥惭，其度量的中心思想是：聚類結(jié)果中被劃分到同一簇中的樣本在參考模型中也被劃分到同一簇的概率越高代表聚類結(jié)果越好紊搪。常用的性能指標有：Jaccard系數(shù)、FM指數(shù)牵囤、Rand指數(shù)

［2］內(nèi)部指標

這一類的性能度量是直接考察聚類結(jié)果而不利用任何參考模型滞伟，稱為“內(nèi)部指標”

“內(nèi)部指標”通過計算簇內(nèi)的樣本距離梆奈，以及簇間的樣本距離來對聚類結(jié)果進行評估。其度量的中心思想是：簇內(nèi)的樣本距離近似于簇內(nèi)相似度乓梨，簇間樣本距離近似于簇間相似度，通過計算并組合這些樣本/簇距離的值來構(gòu)建一個符合需要的性能度量指標脆霎。常用的性能指標有：DB指數(shù)狈惫、Dunn指數(shù)

以DB指數(shù)為例，其代表的是：任意兩個簇 Ci 和 Cj忆肾，它們的簇內(nèi)平均距離的和（ avg(Ci) + avg(Cj) ）與它們簇間距離 dist( center(Ci), center(Cj) ) 的比值的最大值菱肖。這個指數(shù)越小稳强，代表聚類結(jié)果的簇間距離越大，而簇內(nèi)距離越小渠缕。

在理解了距離度量是聚類算法中對相似度的近似之后褒繁，我們下一節(jié)好好介紹以下距離計算的概念、性質(zhì)以及具體形式

2）簇內(nèi)/簇間相似度度量：距離計算

對于距離函數(shù) dist(. , .)燕差，若它是一個“距離度量”（distance measure）坝冕，則需滿足以下一些基本性質(zhì)：

非負性：兩點之間距離不為負;

同一性：兩個點只有在樣本空間上重合才可能距離為零徽诲；

對稱性：a到b的距離等于b到a的距離;

直遞性：a到c的距離加上c到b的距離大于等于a直接到b的距離;

［1］連續(xù)屬性上的距離計算

在連續(xù)屬性上，給定樣本 xi 和 xj，它們之間的距離一般通過“閔科夫斯基距離”來計算钱贯，它計算樣本 xi 和 xj 在每一個屬性上的數(shù)值差值的 p 次方的和的開 p 次方侦另。當 p = 2時尉共，“閔科夫斯基距離”即歐式距離袄友。

［2］離散屬性上的距離計算

在離散屬性上霹菊，因為其在定義域上只有有限個取值，當這些取值是有序的時鸠按，如 {1, 2, 3}饶碘，我們可以同樣用“閔科夫斯基距離”來計算扎运，但當取值為無序時，如 {蘋果, 香蕉, 桃子}测蹲，我們使用 VDM（Value Difference Metric）來計算鬼吵。

VDMp(a, b)代表的是在屬性 u 上齿椅，取值為 a 和 b 的樣本在不同簇上分布比例的差值的 p 次方。它是通過分布比例的不同來對屬性上的相似度來進行近似的示辈。

［3］注意項

需注意的是遣蚀，通常我們是基于某種形式的距離來定義相似度度量的，距離越大险耀，則相似度越小玖喘。然而累奈， 用于相似度度量的距離未必一定要滿足距離度量的所有性質(zhì)急但，尤其是直遞性搞乏。比如下邊的例子：

我們要讓人和人馬相似请敦、人馬和馬相似冬三，但是我們不能認為人和馬是相似的，在此情況下敌蚜，要滿足直遞性就得要人和馬的相似度不大于4窝爪，而直觀上來看人和馬十分的不相近（距離應該遠大于4）蒲每，所以在這里直遞性就不適合了。這種距離稱為“非度量距離”邀杏，在不少現(xiàn)實任務中望蜡，我們需要基于數(shù)據(jù)樣本來確定合適的距離計算式。

在解答了聚類的性能度量之后谢肾，我們終于可以開始對具體的聚類算法進行講解了小泉，基于不同的學習策略微姊，我們可以將聚類分為不同類型。下一節(jié)弊决，我們將對不同策略下的聚類算法進行介紹魁淳。

3）原型聚類

原型聚類假設聚類結(jié)構(gòu)能通過一組原型刻畫界逛，在現(xiàn)實聚類任務中及其常見。通常情況下溉潭，算法先對原型進行初始化少欺，然后對原型進行迭代更新求解赞别。采用不同的原型表示、求解方式惠毁，將產(chǎn)生不同的算法

［1］k均值（k-means）算法

“k均值”算法的選定參數(shù) k 將數(shù)據(jù)集劃分為 k 個簇崎页，并通過迭代更新使得簇劃分最小化平方誤差飒焦。

算法步驟如下：

-> 首先，初始化 k 個簇翁巍，隨機選擇 k 個樣本作為 k 個簇的初始均值向量

-> 然后志电，不斷迭代以下幾步步驟

>> 對每個樣本 x 挑辆，計算其與每個簇均值向量的距離 d，

>> 選擇最近的簇 i 作為 x 的簇標記洒嗤，并將 x 放入該簇集合 Ci 中

>> 對所有的簇集合魁亦，根據(jù)本次迭代得到的簇集合計算新的均值向量

>> 當均值向量均未更新時，退出迭代步驟

-> 最終间唉，我們獲得了聚類計算的結(jié)果簇劃分

需注意呈野，k是靠人工選擇的結(jié)果，大家可以通過對不同的 k 值進行試驗军掂，或通過對數(shù)據(jù)集的理解來找到最合適的 k 的取值昨悼。

［2］學習向量量化（Learning Vector Quantization，簡稱LVQ）

與k均值算法類似率触，LVQ也是試圖找到一組原型向量（k均值算法中的簇均值向量集合就是一組原型向量）來刻畫聚類結(jié)構(gòu)闲延，但與一般聚類算法不同的是，LVQ假設數(shù)據(jù)樣本帶有類別標記陆馁，學習過程利用樣本的這些監(jiān)督信息來輔助聚類

學習向量量化的算法步驟如下：

-> 首先叮贩，初始化 p 個原型向量（數(shù)據(jù)集中有幾個類別佛析，p就為幾）寸莫，隨機從每個類別中選擇一個數(shù)據(jù)樣本作為該類別的初始原型向量

-> 然后，不斷迭代以下幾個步驟

>> 從樣本集中隨機選取樣本 x桃纯，并計算它與每個原型向量的距離披坏，

并找出最近距離 d 所對應的原型向量 pi

>> 如果 pi 的類標記等于 x 的類標記棒拂，則原型向量 pi 向 x 方向按

學習率移動

>> 如果?pi 的類標記不等于 x 的類標記，則原型向量 pi 向 x 反方

向按學習率移動

>> 當原型向量滿足條件時（如達到迭代次數(shù)谜诫、原型向量更新很胁滦濉）

退出迭代

-> 最終敬特，我們獲得了聚類計算的結(jié)果原型向量

［3］高斯混合聚類

與k均值伟阔、LVQ用原型向量來刻畫聚類結(jié)構(gòu)不同，高斯混合聚類采用概率模型來表達聚類原型怀估。相對于k均值聚類算法使用 k 個原型向量來表達聚類結(jié)構(gòu)合搅，高斯混合聚類使用 k 個高斯概率密度函數(shù)混合來表達聚類結(jié)構(gòu)

于是迭代更新 k 個簇原型向量的工作轉(zhuǎn)換為了迭代更新 k 個高斯概率密度函數(shù)的任務灾部。每個高斯概率密度函數(shù)代表一個簇，當一個新的樣本進來時从藤，我們可以通過這 k 的函數(shù)的值來為新樣本分類

高斯混合聚類的算法步驟如下：

-> 首先夷野，初始化高斯混合分布的模型參數(shù)

-> 然后荣倾，不斷迭代以下幾個步驟

>> 對數(shù)據(jù)集中的每一個樣本 x舌仍，計算其在每一個混合成份上的后驗概率

>> 根據(jù)算好的后驗概率，更新高斯混合分布每一個混合成份上的參數(shù)

>> 當滿足停止條件苏揣，如達到迭代次數(shù)平匈、似然函數(shù)更新很小時退出迭代

-> 接著，根據(jù)最后的混合成份忍燥，我們將數(shù)據(jù)集劃分到不同的簇中

-> 最終隙姿，我們獲得簇劃分以及高斯混合分布函數(shù)模型

4）密度聚類

密度聚類假設聚類結(jié)構(gòu)能通過樣本分布的緊密程度確定输玷。通常情況下，密度聚類算法從樣本密度的角度來考察樣本之間的可連接性机久，并基于可連接樣本不斷擴展聚類簇以獲得最終的聚類結(jié)果膘盖。

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一種著名的密度聚類算法尤误，它基于一組“鄰域”參數(shù)來刻畫樣本分布的緊密程度损晤。DBSCAN算法的中心思想是將滿足一定可達關(guān)系能導出的最大密度相連樣本定義為一個簇，其通過兩個基本參數(shù) e 和 MinPts 來定義這個可達關(guān)系码党。要理解 DBSCAN 算法斥黑，我們先了解下邊這些概念：

［1］“e - 鄰域”：e為鄰域半徑揖盘，任意一個樣本 xj 的 “e - 鄰域” 包含樣本集 D 中與樣本 xj 的距離不大于 e 的樣本集合；

［2］核心對象：當一個樣本 x 的 “e - 鄰域”內(nèi)含有至少 MinPts 個樣本時锌奴，該樣本 x 是一個核心對象兽狭；

［3］密度直達：若 xj 位于 xi 的?“e - 鄰域”中，且 xi 是核心對象鹿蜀，則稱 xj 與 xi 密度直達

［4］密度可達：若 xi 與 xj 能通過一系列密度直達的點關(guān)聯(lián)起來箕慧，則 xi 與 xj 密度可達

［5］密度相連：若 xi 與 xj 都能通過 xk 密度可達，則稱 xi 與 xj 密度相連

DBSCAN算法的步驟如下：

-> 首先茴恰，初始化核心對象集合為空

-> 然后颠焦，對每個樣本計算其鄰域空間集合往枣，并根據(jù)鄰域所含結(jié)點判斷是否為

核心對象伐庭，如果是則加入核心對象集合

-> 接著粉渠，當核心對象集合不為空時，不斷重復迭代以下幾個步驟

>> 隨機從核心對象集合中抽取出一個核心對象

>> 根據(jù)這個核心對象找出其密度相連的所有樣本集合

>> 將這些樣本集合設定為一個簇

>> 將該簇集合中出現(xiàn)的核心對象從核心對象集合中移除

-> 最終圾另，我們獲得聚類計算的結(jié)果簇劃分

需注意的是霸株，在完成計算之后，可能會存在一些數(shù)據(jù)是不屬于任何簇的集乔，這些樣本被認為是噪聲或異常樣本去件。在個別應用場景下，這部分樣本將具有較高的價值扰路，比如在反欺詐場景下尤溜，這部分不合群的樣本數(shù)據(jù)是欺詐行為數(shù)據(jù)的概率較高。

5）層次聚類（Hierarchical clustering）

層次聚類試圖在不同層次對數(shù)據(jù)集進行劃分幼衰，從而形成樹形的聚類結(jié)構(gòu)靴跛。數(shù)據(jù)集的劃分可采用“自底向上”的聚合策略，也可采用“自頂向下”的分拆策略渡嚣。

AGNES（AGglomerative NESting）是一種采用自底向上聚合策略的層次聚類算法，它的算法十分簡單肥印，那就是先將每個樣本看作一個初始聚類簇识椰，然后在算法運行的每一步找出距離最近的兩個聚類簇進行合并，該過程不斷重復深碱，直到達到預設的聚類簇個數(shù)腹鹉。

這個算法十分簡單，其中的關(guān)鍵是如何計算兩個聚類簇之間的距離敷硅。根據(jù)以下不同的距離定義功咒，我們將得到不同分類結(jié)果：

［1］最小距離：兩個聚類簇樣本之間的最小距離，使用該距離定義的算法被稱為“單鏈接”算法

［2］最大距離：兩個聚類簇樣本之間的最大距離绞蹦，使用該距離定義的算法被稱為“全鏈接”算法

［3］平均距離：兩個聚類簇樣本之間的距離之和的平均力奋，使用該距離定義的算法被稱為“均鏈接”算法

上圖是在西瓜數(shù)據(jù)集上的層次聚類結(jié)果，采用的是最大距離幽七，橫軸對應于樣本編號景殷，縱軸對應于聚類簇距離

2. 基礎知識

1）無監(jiān)督學習（unsupervised learning）

在無監(jiān)督學習中，訓練樣本的標記信息是未知的澡屡，目標是通過對無標記訓練樣本的學習來揭示數(shù)據(jù)的內(nèi)在性質(zhì)和規(guī)律猿挚，為進一步的數(shù)據(jù)分析提供基礎。

2）監(jiān)督學習（supervised learning）

顧名思義驶鹉，監(jiān)督學習與無監(jiān)督學習相反绩蜻，即在標記好的訓練樣本上進行訓練和學習的機器學習算法

3）高斯分布（Gaussian distribution）

高斯分布也叫“正態(tài)分布”（Normal Distribution）。若隨機變量X服從一個數(shù)學期望為μ室埋、方差為σ^2的正態(tài)分布办绝，記為N(μ踏兜，σ^2)，其概率密度函數(shù)為正態(tài)分布的期望值μ決定了其位置八秃，其標準差σ決定了分布的幅度碱妆。當μ = 0,σ = 1時的正態(tài)分布是標準正態(tài)分布。

4）協(xié)方差矩陣

在統(tǒng)計學與概率論中昔驱，協(xié)方差矩陣的每個元素是各個向量元素之間的協(xié)方差疹尾。即協(xié)方差矩陣 aij 代表的是樣本 xi 和樣本 xj 的協(xié)方差。

3. 總結(jié)

1）“聚類”（clustering）算法試圖將數(shù)據(jù)集中的樣本劃分為若干個通常是不相交的子集骤肛，每個子集稱為一個“簇”（cluster）纳本，每個簇可能對應于一些潛在的概念（類別）

2）聚類過程僅能自動生成簇結(jié)構(gòu)，簇所對應的概念語義需由使用者來把握和命名

3）聚類性能度量的目的是找出使聚類結(jié)果的“簇內(nèi)相似度”（intra-cluster similarity）高且“簇間相似度”（inter-cluster similarity）低的聚類結(jié)果

4）距離度量是聚類算法中對相似度的近似

5）基于不同的學習策略腋颠，我們可以將聚類分為：原型聚類繁成、密度聚類以及層次聚類等不同類型

6）原型聚類假設聚類結(jié)構(gòu)能通過一組原型刻畫

7）密度聚類假設聚類結(jié)構(gòu)能通過樣本分布的緊密程度確定

8）層次聚類試圖在不同層次對數(shù)據(jù)集進行劃分，從而形成樹形的聚類結(jié)構(gòu)

9）密度聚類可能會有樣本不屬于任何一個簇淑玫，這部分數(shù)據(jù)可被認為是噪聲或異常數(shù)據(jù)

10）原型聚類和層次聚類的簇數(shù)量是由使用者自己設定的巾腕，而密度聚類則是由算法自己學習得來