9.聚類(lèi)

有必要回顧下前文所涉及的機(jī)器學(xué)習(xí)主流分類(lèi)，有監(jiān)督學(xué)習(xí)中根據(jù)預(yù)測(cè)結(jié)果離散和連續(xù)屬性分為分類(lèi)和回歸兩大類(lèi)，常見(jiàn)的算法有：線性模型、決策樹(shù)、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、貝葉斯分類(lèi)器以及集成學(xué)習(xí)。

本文開(kāi)始說(shuō)無(wú)監(jiān)督學(xué)習(xí)（unsupervised learning），訓(xùn)練樣本的標(biāo)記信息是未知的，目標(biāo)是通過(guò)對(duì)無(wú)標(biāo)記訓(xùn)練樣本的學(xué)習(xí)來(lái)揭示數(shù)據(jù)的內(nèi)在性質(zhì)及規(guī)律，為進(jìn)一步的數(shù)據(jù)分析提供基礎(chǔ)。聚類(lèi)(clustering)是無(wú)監(jiān)督學(xué)習(xí)任務(wù)中研究最多、應(yīng)用最廣泛的算法。

9.1聚類(lèi)任務(wù)

聚類(lèi)將數(shù)據(jù)集中的樣本劃分為若干個(gè)通常是不相交的子集，每個(gè)子集稱(chēng)為一個(gè)簇（cluster），每個(gè)簇對(duì)應(yīng)一個(gè)潛在概念或類(lèi)別。當(dāng)然這些類(lèi)別在執(zhí)行聚類(lèi)算法之前是未知的，聚類(lèi)過(guò)程是自動(dòng)形成簇結(jié)構(gòu)，簇所對(duì)應(yīng)的概念語(yǔ)義由使用者命名。

形式化地說(shuō)，假定樣本集D={x₁,x₂,…,x_m}包含m個(gè)無(wú)標(biāo)記樣本，每個(gè)樣本x_i={x_i1; x_i2;…;x_in}是一個(gè)n維特征向量（屬性），則聚類(lèi)算法將樣本集D劃分為k個(gè)不相交的簇{C_l|l=1,2,…,k}，其中C_l∩_l≠l’C_l’=?且D=U_l=1…kC_l。相應(yīng)地，用R_j∈{1,2,…,k}表示樣本x_j的簇標(biāo)記(cluster label)，即x_j∈C_Rj。聚類(lèi)的結(jié)果可用包含m個(gè)元素的簇標(biāo)記向量R=(R₁;R₂;…;R_m)表示。

聚類(lèi)既能作為一個(gè)單獨(dú)過(guò)程，用于尋找數(shù)據(jù)內(nèi)在的分布結(jié)構(gòu)，也可作為分類(lèi)等其他學(xué)習(xí)任務(wù)的前驅(qū)過(guò)程。如在一些商業(yè)應(yīng)用中需對(duì)新用戶(hù)的類(lèi)型進(jìn)行判別，但定義用戶(hù)類(lèi)型對(duì)商家來(lái)說(shuō)可能不太容易，此時(shí)可先對(duì)用戶(hù)進(jìn)行聚類(lèi)，根據(jù)聚類(lèi)結(jié)果將每個(gè)簇定義為一個(gè)類(lèi)，然后再基于這些類(lèi)訓(xùn)練分類(lèi)模型，用于判別新用戶(hù)的類(lèi)型。

基于不同的學(xué)習(xí)策略，可設(shè)計(jì)出多種類(lèi)型的聚類(lèi)算法。眾多算法的評(píng)估，就先要談兩個(gè)基本問(wèn)題，性能度量和距離計(jì)算。

9.2性能度量

聚類(lèi)性能度量也稱(chēng)聚類(lèi)有效性指標(biāo)（validity index）。與監(jiān)督學(xué)習(xí)中的性能度量作用相似。對(duì)聚類(lèi)結(jié)果，要通過(guò)某種性能度量來(lái)評(píng)估其好壞。如明確最終要使用的性能度量，可直接將其作為聚類(lèi)過(guò)程的優(yōu)化目標(biāo)，從而更好地得到符合要求的聚類(lèi)結(jié)果，即事后度量也可作為事中追求的目標(biāo)。

聚類(lèi)將樣本集D劃分為若干互不相交的子集，即樣本簇。怎么樣的聚類(lèi)結(jié)果比較好呢？物以類(lèi)聚，即同一簇的樣本盡可能彼此相似，不同簇的樣本盡可能不同。簡(jiǎn)單來(lái)說(shuō)，就是簇內(nèi)相似度（intra-cluster similarity）高且簇間相似度（inter-clustersimilarity）低。

聚類(lèi)性能度量大致有兩類(lèi)，一類(lèi)是將聚類(lèi)結(jié)果與某個(gè)參考模型（reference model）進(jìn)行比較，稱(chēng)為外部指標(biāo)（externel index）；另一類(lèi)是直接考察聚類(lèi)結(jié)果而不利用任何參考模型，稱(chēng)為內(nèi)部指標(biāo)（internal index）。

對(duì)數(shù)據(jù)集D={x₁,x₂,…,x_m}，假定通過(guò)聚類(lèi)給出的簇劃分C={C₁,C₂,…,C_k}，參考模型給出的簇劃分為CR={CR₁,CR₂,…,CR_k}。相應(yīng)地，令F和FR表示與C和CR對(duì)應(yīng)的簇標(biāo)記向量。將樣本兩兩配對(duì)考慮，定義：

a=|SS|,SS={(x_i,x_j)|F_i=F_j,FR_i=FR_j,i<j}

b=|SD|,SD={(x_i,x_j)|F_i=F_j,FR_i≠FR_j,i<j}

c=|DS|,SD={(x_i,x_j)|F_i≠F_j,FR_i=FR_j,i<j}

d=|DD|,SD={(x_i,x_j)|F_i≠F_j,FR_i≠FR_j,i<j}

其中集合SS包含了在C中隸屬于相同簇且在CR中也隸屬于相同簇的樣本對(duì)，集合SD 包含了在C隸屬于相同簇但在CR中隸屬于不同簇的樣本對(duì)，……由于每個(gè)樣本對(duì)( x_i,x_j)（i<j）僅能出現(xiàn)在一個(gè)集合中，因此有a+b+c+d=m(m-1)/2成立?；谏鲜鲂问交?#xff0c;可定義如下常用的聚類(lèi)性能度量外部指標(biāo)：

?

9.3距離計(jì)算

上文定義的性能度量指標(biāo)，有non 個(gè)很重要的數(shù)學(xué)關(guān)系，就是樣本間的距離dist，實(shí)際上抽象出來(lái)，任何物體的相似度都是通過(guò)距離來(lái)判斷，至于怎么定義距離就不同而論。函數(shù)dist()是一個(gè)距離度量（distance measure），滿足如下基本性質(zhì)：

1）非負(fù)性：dist(x_i,x_j)≥0；

2）同一性：dist(x_i,x_j)=0當(dāng)且僅當(dāng)x_i=x_j；

3）對(duì)稱(chēng)性：dist(x_i,x_j)=dist(x_j,x_i)；

4）直遞性：dist(x_i,x_j)≤dist(x_i,x_k)+ dist(x_k,x_j)；

給定樣本x _i={x _i1;x _i2;…; x _in}與x _j={x _j1;x _j2;…; x _jn}，最常用的是閔可夫斯基距離（Minkowskidistance）：

屬性通常劃分為連續(xù)屬性（continuous attribute）和離散屬性（categoricalattribute），連續(xù)屬性在定義域上有無(wú)窮多個(gè)可能的取值；后者在定義域上是有限個(gè)取值。連續(xù)屬性亦稱(chēng)數(shù)值屬性（numerical attribute）；離散屬性也稱(chēng)為列名屬性（nominalattribute）。在討論距離計(jì)算時(shí)，屬性上是否定義了序的關(guān)系很重要。如定義域?yàn)閧1,2,3}的離散屬性與連續(xù)屬性的性質(zhì)更接近，能直接在屬性值上計(jì)算距離，這樣的屬性稱(chēng)為有序?qū)傩?#xff08;ordinal attribute）；而定義域?yàn)閧飛機(jī)，火車(chē)，輪船}這樣的離散屬性則不能直接在屬性上計(jì)算距離，稱(chēng)為無(wú)序?qū)傩?#xff08;non-ordinalattribute）。顯然閔可夫斯基距離用于有序?qū)傩?#xff0c;那么無(wú)序?qū)傩栽趺从?jì)算距離呢？實(shí)際上，有序?qū)傩院蜔o(wú)序?qū)傩栽跀?shù)據(jù)挖掘上更多屬性。離散屬性的有序化很重要，對(duì)于機(jī)器學(xué)習(xí)來(lái)說(shuō)，刻畫(huà)和訓(xùn)練都基于向量，無(wú)序無(wú)數(shù)自然不行。

通?；谟蟹N形式的距離定義相似度度量（similarity measure），距離越大，相似度越小。然而，用于相似度度量的距離未必一定要滿足距離度量的所有基本性質(zhì)，尤其是直遞性。不滿足直遞性的距離稱(chēng)為非度量距離（non-metric distance），文中以人馬為例來(lái)說(shuō)明。本文所說(shuō)的距離公式都是事先定義好的，在現(xiàn)實(shí)任務(wù)中，應(yīng)該結(jié)合數(shù)據(jù)樣本和聚類(lèi)潛在結(jié)果來(lái)確定合適的距離計(jì)算公式，可通過(guò)距離度量學(xué)習(xí)（distance metric learning）來(lái)實(shí)現(xiàn)。

有了性能度量和距離計(jì)算，下文來(lái)說(shuō)明典型的聚類(lèi)算法。

9.4原型聚類(lèi)

原型聚類(lèi)，也稱(chēng)基于原型的聚類(lèi)（prototype-based clustering），該類(lèi)算法假設(shè)聚類(lèi)結(jié)構(gòu)能夠通過(guò)一組原型刻畫(huà)，在現(xiàn)實(shí)聚類(lèi)任務(wù)中較為常用。一般情形下，算法先對(duì)原型進(jìn)行初始化，然后對(duì)原型進(jìn)行迭代更新求解。采用不同的原型表示、不同的求解方式，將產(chǎn)生不同的算法。

文中的西瓜集例子配合起來(lái)可以更好理解算法過(guò)程。算法核心是對(duì)當(dāng)前簇劃分及均值向量迭代更新。

2）學(xué)習(xí)向量量化

與k均值算法類(lèi)似，學(xué)習(xí)向量量化（learning vector quantization，簡(jiǎn)稱(chēng)LVQ）也是試圖找到一組原型向量來(lái)刻畫(huà)聚類(lèi)結(jié)構(gòu)，但與一般聚類(lèi)算法不同的是，LVG假設(shè)數(shù)據(jù)樣本帶有類(lèi)別標(biāo)記，學(xué)習(xí)過(guò)程利用樣本的這些監(jiān)督信息來(lái)輔助聚類(lèi)。

給定樣本集D={(x ₁,y ₁),(x ₂,y ₂),…,(x _m,y _m)}；每個(gè)樣本x _j是由n個(gè)屬性描述的特征向量（x _j1; x _j1;…; x _jn），y _j∈Y是樣本x _j的類(lèi)別標(biāo)記。LVQ的目標(biāo)是學(xué)得一組n維原型向量{p ₁,p ₂,…,p _q}，每個(gè)原型向量代表一個(gè)聚類(lèi)簇，簇標(biāo)記t _i∈Y。LVQ算法過(guò)程如下：

算法在對(duì)原型向量進(jìn)行迭代優(yōu)化，每一輪迭代中，算法隨機(jī)選取一個(gè)有標(biāo)記訓(xùn)練樣本，找出與其距離最近的原型向量，并根據(jù)兩者的判別標(biāo)記是否一致來(lái)對(duì)原型向量進(jìn)行相應(yīng)的更新。若算法的停止條件已滿足（如已達(dá)到最大迭代輪數(shù)，或原型向量更新很小甚至不再更新），則將當(dāng)前原型向量作為最終結(jié)果返回。

上面這兩個(gè)類(lèi)似的算法，Kmean和LVG主要還是看樣本，如果帶有標(biāo)記，LVG是可以采用的。文中的例子可以配合理解。

3）高斯混合聚類(lèi)

與K均值、LVQ用原型向量來(lái)刻畫(huà)聚類(lèi)結(jié)構(gòu)不同，高斯混合（Mixture-of-Gaussian）聚類(lèi)采用概率模型來(lái)表達(dá)聚類(lèi)原型。

高斯混合聚類(lèi)算法流程如下：

對(duì)于高斯混合聚類(lèi)，要理解概率密度和高斯分布才能更好理解基于概率模型的原型聚類(lèi)。

9.5密度聚類(lèi)

密度聚類(lèi)，也稱(chēng)為基于密度的聚類(lèi)（density-based clustering），該類(lèi)算法假設(shè)聚類(lèi)結(jié)構(gòu)能通過(guò)樣本分布的緊密程度確定。一般情形下，密度聚類(lèi)算法從樣本密度的角度來(lái)考察樣本之間的可連接性，并基于可連接樣本不斷擴(kuò)展聚類(lèi)簇以獲得最終的聚類(lèi)結(jié)果。

算法先給給定的領(lǐng)域參數(shù)（ ）找出所有核心對(duì)象，接著以任一核心對(duì)象為出發(fā)點(diǎn)，找出由其密度可達(dá)的樣本生成聚類(lèi)簇，直到所有核心對(duì)象均被訪問(wèn)過(guò)為止。文中西瓜集例子可以輔助理解，最好是能就文中的西瓜集例子子集編程實(shí)現(xiàn)，實(shí)在時(shí)間有限，這些算法只能留待實(shí)際使用中再代碼實(shí)現(xiàn)。

9.6層次聚類(lèi)

層次聚類(lèi)（hierarchicalclustering）試圖在不同層次對(duì)數(shù)據(jù)集進(jìn)行劃分，從而形成樹(shù)形的聚類(lèi)結(jié)構(gòu)。數(shù)據(jù)的劃分可采用自底向上的聚合策略，也可采用自頂向下的分拆策略。

AGNES（AGglomera-tiveNEString）是一種采用自底向上聚類(lèi)策略的層次聚類(lèi)算法。它先將數(shù)據(jù)集中的每個(gè)樣本看做一個(gè)初始聚類(lèi)簇，然后在算法運(yùn)行的每一步中找出距離最近的兩個(gè)聚類(lèi)簇進(jìn)行合并，該過(guò)程不斷重復(fù)，直至達(dá)到預(yù)設(shè)的聚類(lèi)簇個(gè)數(shù)。這里的關(guān)鍵是如何計(jì)算聚類(lèi)簇之間的距離。每個(gè)簇是一個(gè)樣本集合，因此采用關(guān)于集合的某種距離即可。給定聚類(lèi)簇C_i和C_j，可通過(guò)下面的公式來(lái)計(jì)算距離：

算法先對(duì)僅含一個(gè)樣本的初始聚類(lèi)簇和相應(yīng)的距離矩陣進(jìn)行初始化，接著不斷合并距離最近的聚類(lèi)簇，并對(duì)合并得到的聚類(lèi)簇的距離矩陣進(jìn)行更新，不斷重復(fù)，直到達(dá)到預(yù)設(shè)的聚類(lèi)簇?cái)?shù)。

現(xiàn)在我們來(lái)總結(jié)聚類(lèi)這一章節(jié)的脈絡(luò)，首先聚類(lèi)是無(wú)監(jiān)督學(xué)習(xí)算法，和前文的監(jiān)督學(xué)習(xí)算法不同在于樣本不帶標(biāo)記，聚類(lèi)有自己的性能度量評(píng)估指標(biāo)，分外部指標(biāo)和內(nèi)部指標(biāo)，核心就是距離計(jì)算，也就是后續(xù)算法關(guān)鍵；其次，就聚類(lèi)算法做了三大分類(lèi)，分別是原型聚類(lèi)、密度聚類(lèi)、層次聚類(lèi)，三類(lèi)算法的概要理解就在于原型、密度、層次；其中原型聚類(lèi)又由基于均值的KMeans、基于原型的LVG、基于概率的高斯混合聚類(lèi)。說(shuō)到聚類(lèi)，不得不說(shuō)其經(jīng)典應(yīng)用場(chǎng)景異常檢測(cè)（anormaly detection），其常借助聚類(lèi)或距離計(jì)算進(jìn)行，如將遠(yuǎn)離所有簇中心的樣本作為異常點(diǎn)，或?qū)⒚芏葮O低處的樣本作為異常點(diǎn)，最近有研究提出基于隔離性（isolation）可快速檢測(cè)出異常點(diǎn)。

總結(jié)

以上是生活随笔為你收集整理的机器学习笔记(九)聚类的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。