文章脈絡(luò)
1.什么是聚類
2.聚類的效果評估——性能度量
? ?2.1外部指標(biāo)
? ?2.2內(nèi)部指標(biāo)3.聚類的類型
? ?3.1原型聚類
? ?3.2密度聚類
? ?3.3層次聚類4.總結(jié)
1. 什么是聚類
“聚類”（clustering）算法是“無監(jiān)督學(xué)習(xí)”算法中研究最多、應(yīng)用最廣的算法，它試圖將數(shù)據(jù)集中的樣本劃分為若干個通常是不相交的子集，每個子集稱為一個“簇”（cluster），每個簇可能對應(yīng)于一些潛在的概念（也就是類別），如“淺色瓜” “深色瓜”，“有籽瓜” “無籽瓜”，甚至“本地瓜” “外地瓜”等；需說明的是，這些概念對聚類算法而言事先是未知的，聚類過程僅能自動形成簇結(jié)構(gòu)，簇對應(yīng)的概念語義由使用者來把握和命名。
通俗來說，聚類可以將一個數(shù)據(jù)集中所有樣本根據(jù)相似度的大小分成若干組，使用者可以根據(jù)自己的目的來給每一組數(shù)據(jù)下定義。聚類的應(yīng)用有很多，比如金融機構(gòu)可以將客戶群體分為高風(fēng)險客戶、中風(fēng)險客戶、低風(fēng)險客戶等，用聚類對某一區(qū)域企業(yè)進行評級管理等。
2. 聚類的效果評估——性能度量
通過聚類所得到的結(jié)果是好是壞，需要通過性能度量來評估。聚類性能度量又稱聚類“有效性指標(biāo)”，它是聚類過程中優(yōu)化的目標(biāo)，可以分為外部指標(biāo)和內(nèi)部指標(biāo)，其中心思想都是使得簇內(nèi)相似度盡可能高，簇間相似度盡可能低。
2.1 外部指標(biāo)
外部指標(biāo)：指將聚類結(jié)果與某個“參考模型”進行比較。
常用指標(biāo)：
變量解釋：
對于數(shù)據(jù)集D = {x1,x2,……xm}，假定通過聚類給出的簇劃分為C = {C1,C2,……Ck}，參考模型給出的劃分為C* = {C1*,C2*……Cs*}，將樣本兩兩配對，定義出四個集合：
a：在C中同簇，C*中也同簇
b：在C中同簇，C*中不同簇
c：在C中不同簇，C*中同簇
d：在C中不同簇，C*也不同簇
2.2 內(nèi)部指標(biāo)
內(nèi)部指標(biāo)：直接參考聚類的結(jié)果而不利用任何的參考模型。
常用指標(biāo)：
變量解釋：
avg(C)：簇C內(nèi)樣本間的平均距離
diam(C)：簇C內(nèi)樣本間的最遠(yuǎn)距離
dmin(Ci, Cj)：兩個簇最近的樣本間的距離
dcen(Ci,Cj)：兩個簇中心點間的距離
1）距離計算
對于函數(shù)dist(·,·)，若它是一個“距離度量”，則需滿足四個性質(zhì)
1.非負(fù)性：距離不為負(fù)
2.同一性：只有兩點重合時距離才為0
3.對稱性：A到B的距離等于B到A的距離
4.直遞性：A到B再到C的距離之和要大于或等于從A直接到C的距離
有序?qū)傩缘木嚯x計算：
無序?qū)傩缘木嚯x計算：VDM
混合屬性的距離計算：閔可夫斯基距離與VDM結(jié)合
【注意】：用于度量相似度的距離未必一定要滿足“距離度量”的所有基本性質(zhì)，尤其是直遞性，這樣的距離稱為“非度量距離”。在不少現(xiàn)實任務(wù)中，有必要基于數(shù)據(jù)樣本來確定合適的距離計算式，可以通過“距離度量學(xué)習(xí)”來實現(xiàn)。
3. 聚類的類型
3.1 原型聚類
1）k均值（k-means）算法
給定樣本集D = {x1,x2,……xm}，k均值算法針對聚類所得的簇劃分C = {C1,C2,……Ck}最小化平方誤差
直觀上看，該式刻畫了簇內(nèi)樣本圍繞簇均值向量的緊密程度，E值越小則簇內(nèi)樣本相似度越高。最小化上式并不容易，需要考察樣本集D所有可能的簇劃分，這是一個NP難問題，因此k均值算法采用了貪心策略，通過迭代優(yōu)化來近似求解上面的公式，算法流程如下：
優(yōu)點：簡單易實現(xiàn)，收斂快（一般5~10次）
缺點：
1.簇數(shù)k選擇不同對結(jié)果影響很大
2.初始點的選擇會影響聚類的結(jié)果，很可能使聚類只能收斂到局部最優(yōu)，所以需要嘗試不同的初始點
3.聚類過程中用到了均值，因此噪點對算法影響較大
4.由于公式刻畫的是樣本圍繞均值的緊密程度，因此k-means算法只適用于程球狀分布的簇，如下圖（我們想要的聚類效果是左圖，但通過k-means算法聚類的效果是右圖）
2）學(xué)習(xí)向量量化（LVQ）
LVQ假設(shè)數(shù)據(jù)樣本帶有類別標(biāo)記Y = {y1,y2,……ym}，學(xué)習(xí)過程利用樣本的這些監(jiān)督信息來輔助聚類，其流程是
第1行，初始化 p 個原型向量（數(shù)據(jù)集中有幾個類別，p就為幾），隨機從每個類別中選擇一個數(shù)據(jù)樣本作為該類別的初始原型向量。第6-9行表示如果 pi*的類別標(biāo)記與 xj 的類別標(biāo)記相同，則原型向量 pi* 向 xj 方向靠攏；如果 pi*的類別標(biāo)記與 xj 的類別標(biāo)記不同，則原型向量 pi* 向 xj 方向遠(yuǎn)離，該過程迭代到滿足條件停止。
LVQ算法優(yōu)點：1.收斂較快； 2.相對于k-means算法對噪點較不敏感
LVQ算法缺點：1.原型向量的初始值和學(xué)習(xí)率對聚類的結(jié)果影響較大
3）高斯混合聚類
高斯混合聚類采用概率模型來表達聚類原型
其中p(x丨ui,Σi）表示樣本集中每個混合成分（高斯分布）的概率密度函數(shù)，ui為均值向量，Σi為協(xié)方差矩陣，αi為各成分的混合系數(shù)（概率）。
假設(shè)樣本的生成過程由高斯混合分布給出，然后根據(jù)被選擇的混合成分的概率密度函數(shù)進行采樣得到相應(yīng)樣本。令zj ∈{1，2，……k}，表示生成xj的高斯混合成分，其取值未知，p(zj = i)=αi，根據(jù)貝葉斯定理，zj的后驗分布對應(yīng)于
記 γji（i=1，2，……k）= pm（zj = i 丨xj）
從原型聚類的角度來看，高斯混合分布采用高斯分布概率模型對原型進行刻畫，簇劃分則由原型對應(yīng)后驗概率確定，簇標(biāo)記λi
在高斯混合聚類中，我們需要學(xué)習(xí)的參數(shù)是，αi，ui，Σi，其流程為：
第2-12行是基于EM算法對模型的參數(shù)進行迭代更新，具體內(nèi)容可參考貝葉斯分類章節(jié)，或者參考B站視頻便于理解：高斯混合聚類
第12行的停止條件可以是：達到最大迭代數(shù)，公式（9.29）的似然函數(shù)LL(D)趨于不再增長
高斯混合聚類優(yōu)點：1.收斂速度快； 2.能擴展以用于大規(guī)模的數(shù)據(jù)集
高斯混合聚類缺點：1.中心選擇和噪點對聚類結(jié)果影響大
3.2 密度聚類
對于樣本分布不規(guī)則的聚類，密度聚類是一種很好的方法，如下圖的分布
在密度聚類中，DBSCAN是一種著名的密度聚類算法，它基于一組“鄰域”參數(shù)（e，MinPts）來刻畫樣本分布的緊密程度。算法涉及到的概念：
“e - 鄰域”：在xj樣本以e為半徑范圍內(nèi)的所有樣本的集合
核心對象：當(dāng)樣本 xj的 “e - 鄰域”內(nèi)含有至少 MinPts 個樣本時，該樣本 xj 是一個核心對象
密度直達：若 xj 位于 xi 的?“e - 鄰域”中，且 xi 是核心對象，則稱 xj 與 xi 密度直達
密度可達：若 xi 與 xj 能通過一系列密度直達的點關(guān)聯(lián)起來，則 xi 與 xj 密度可達
密度相連：若 xi 與 xj 都能通過 xk 密度可達，則稱 xi 與 xj 密度相連
基于以上概念，NBSCAN算法的目的是：從數(shù)據(jù)集D中，找出滿足某些性質(zhì)的聚類簇。這些性質(zhì)是
NBSCAN算法的流程是：
第10-24行表示隨機從核心對象集合中抽取出一個核心對象，根據(jù)這個核心對象找出其密度相連的所有樣本集合，將這些樣本集合設(shè)定為一個簇，將該簇集合中出現(xiàn)的核心對象從核心對象集合中移除，依次不斷迭代，最后獲得聚類計算的結(jié)果簇劃分。
【注意】通過DBSCAN算法完成聚類后，會有一些樣本不屬于任何一個簇，它們被認(rèn)為是噪點，或者是異常樣本。在個別應(yīng)用場景下，這部分樣本將具有較高的價值，比如在反欺詐場景下，這部分不合群的樣本數(shù)據(jù)是欺詐行為數(shù)據(jù)的概率較高。
DBSCAN算法優(yōu)點：1.不需事先確定簇數(shù)k；2.適用于任意形狀分布的樣本數(shù)據(jù)； 3.能夠識別出噪點；
DBSCAN算法缺點：1.當(dāng)數(shù)據(jù)維度較高，樣本分布比較松散時，密度可能很難定義；2.參數(shù)e和MinPts的取值對結(jié)果影響很大
3.3 層次聚類
層次聚類試圖在不同層次對數(shù)據(jù)集進行劃分，從而形成樹形的聚類結(jié)構(gòu)。數(shù)據(jù)集的劃分可采用“自底向上”的聚合策略，也可采用“自頂向下”的分拆策略。AGNES是一種采用自底向上聚合策略的聚類算法，它先將每個樣本都作為一個簇，然后在算法運行的每一步找出距離最近的兩個聚類簇進行合并，該過程不斷重復(fù)，直到達到預(yù)設(shè)的聚類簇個數(shù)。流程如下：
輸入中，距離度量函數(shù)可以選擇dmin，dmax，davg來進行，相應(yīng)的AGNES被稱為“單鏈接”算法，“全鏈接”算法，“均鏈接”算法。
以西瓜數(shù)據(jù)集4.0為例，令A(yù)GNES算法一直執(zhí)行到所有樣本出現(xiàn)在同一個簇中（即k=1），得到的樹狀圖如下，我們可以根據(jù)簇數(shù)的要求進行“切割”，比如我們需要分出7個簇，只需令k=7即可。
AGNES算法優(yōu)點：1.距離和相似度的規(guī)則容易定義，限制少； 2.可以發(fā)現(xiàn)簇的層次關(guān)系； 3.可以聚類成其它形狀
AGNES算法缺點：1.計算復(fù)雜度高； 2.奇異值能產(chǎn)生很大影響； 3.算法很可能聚類成鏈狀
4. 總結(jié)
1）基于不同的學(xué)習(xí)策略，聚類可分為原型聚類、密度聚類、層次聚類等
2）聚類的性能度量思想是：簇內(nèi)相似度高，且簇間相似度低
3）相似度的衡量依賴于距離的計算
4）聚類生成的簇需要使用者來把握和命名
5）不同條件適用不同的聚類方法：
? ? ? a.樣本程球狀分布時：k-means算法
? ? ? b.樣本分布不規(guī)則時：密度聚類、層次聚類
? ? ? c.需要事先決定簇數(shù)時：原型聚類、層次聚類
? ? ? d.需要發(fā)現(xiàn)噪點時：密度聚類
? ? ? e.樣本帶有標(biāo)記時：LVQ算法
? ? ? f.樣本量很大時：高斯混合聚類
? ? ? ……
