|
聚類分析就僅根據(jù)在數(shù)據(jù)中發(fā)現(xiàn)的描述對象及其關系的信息，將數(shù)據(jù)對象分組(簇)。其目標是，組內(nèi)的對象相互之間是相似的，而不同組中的對象是不同的。組內(nèi)相似性越大，組間差別越大，聚類就越好。
先介紹下聚類的不同類型，通常有以下幾種：
(1)層次的與劃分的：如果允許簇具有子簇，則我們得到一個層次聚類。層次聚類是嵌套簇的集族，組織成一棵樹。劃分聚類簡單地將數(shù)據(jù)對象劃分成不重疊的子集(簇)，使得每個數(shù)據(jù)對象恰在一個子集中。
(2)互斥的、重疊的與模糊的：互斥的指每個對象都指派到單個簇。重疊的或是模糊聚類用來反映一個對象同時屬于多個組的事實。在模糊聚類中，每個數(shù)據(jù)對象以一個0和1之間的隸屬權值屬于每個簇。每個對象與各個簇的隸屬權值之和往往是1。
(3)完全的與部分的：完全聚類將每個對象指派到一個簇中。部分聚類中，某些對象可能不屬于任何組，比如一些噪音對象。
聚類分析后發(fā)現(xiàn)的簇往往也具有不同的類型：
(1)明顯分離的：簇是對象的集合，不同組中的任意兩點之間的距離都大于組內(nèi)任意兩點之間的距離。(1)
(2)基于原型的：簇是對象的集合，其中每個對象到定義該簇的原型的距離比到其他簇的原型的距離更近（或更加相似）。對于具有連續(xù)屬性的數(shù)據(jù)，簇的原型通常是質心，即簇中所有點的平均值。這種簇傾向于呈球狀。
(3)基于圖的：如果數(shù)據(jù)用圖表示，其中節(jié)點是對象，而邊代表對象之間的聯(lián)系，則簇可以定義為連通分支，即互相連通但不與組外對象連通的對象組?；趫D的簇一個重要例子就是基于臨近的簇，其中兩個對象是相連的，僅當他們的距離在指定的范圍之內(nèi)。也就是說，每個對象到該簇某個對象的距離比不同簇中的任意點的距離更近。
(4)基于密度的：簇是對象的稠密區(qū)域，被低密度的區(qū)域環(huán)繞。當簇不規(guī)則或互相盤繞，并且有噪聲和離群點時，常常使用基于密度的簇定義。
下面介紹三種常用的聚類算法：
(1)基本K均值：基于原型的，劃分的聚類技術，試圖從全部數(shù)據(jù)對象中發(fā)現(xiàn)用戶指定個數(shù)的簇。
(2)凝聚層次聚類：開始每個點各成一簇，然后重復的合并兩個最近的簇，直到指定的簇個數(shù)。
(3)DBSCAN：一種劃分的，基于密度的聚類算法。
下面我們以對二維空間的數(shù)據(jù)點對象的聚類為例，依次介紹三面三種聚類算法。我們使用的表示二維空間的數(shù)據(jù)點的源文件中，每行為一個數(shù)據(jù)點，格式是x坐標值# y坐標值。
基本K均值：選擇K個初始質心，其中K是用戶指定的參數(shù)，即所期望的簇的個數(shù)。每次循環(huán)中，每個點被指派到最近的質心，指派到同一個質心的點集構成一個簇。然后，根據(jù)指派到簇的點，更新每個簇的質心。重復指派和更新操作，直到質心不發(fā)生明顯的變化。
為了定義二維空間的數(shù)據(jù)點之間的“最近”概念，我們使用歐幾里得距離的平方，即點A(x1,y1)與點B(x2,y3)的距離為dist(A,B)=(x1-x2)2+(y1-y2)2。另外我們使用誤差的平方和SSE作為全局的目標函數(shù)，即最小化每個點到最近質心的歐幾里得距離的平方和。在設定該SSE的情況下，可以使用數(shù)學證明，簇的質心就是該簇內(nèi)所有數(shù)據(jù)點的平均值。
根據(jù)該算法，實現(xiàn)如下代碼：
https://github.com/intergret/snippet/blob/master/Kmeans.py
或是 http://www.oschina.net/code/snippet_176897_14731
聚類的效果如下圖，圖中的折線是歷次循環(huán)時3個簇的質心的更新軌跡，黑點是初始質心：
我們查看基本K均值算法實現(xiàn)步驟及上面的聚類效果可以發(fā)現(xiàn)，該聚類算法將所有數(shù)據(jù)點都進行了指派，不識別噪音點。另外選擇適當?shù)某踉囐|心是基本K均值過程的關鍵。其實，只要兩個初試質心落在一個簇對的任何位置，就能得到最優(yōu)聚類，因為質心將自己重新分布，每個簇一個，是SSE最小。如果初試時一個簇只有一個質心，那么基本K均值算法不能將該質心在簇對之間重新分布，只能有局部最優(yōu)解。另外，它不能處理非球形簇，不同尺寸和不同密度的簇。
關于基本K均值算法的其他還可以查閱陳皓的博客：http:///articles/7779.html
凝聚層次聚類：所謂凝聚的，指的是該算法初始時，將每個點作為一個簇，每一步合并兩個最接近的簇。另外即使到最后，對于噪音點或是離群點也往往還是各占一簇的，除非過度合并。對于這里的“最接近”，有下面三種定義。我在實現(xiàn)是使用了MIN，該方法在合并時，只要依次取當前最近的點對，如果這個點對當前不在一個簇中，將所在的兩個簇合并就行：
(1)單鏈(MIN):定義簇的鄰近度為不同兩個簇的兩個最近的點之間的距離。
(2)全鏈(MAX):定義簇的鄰近度為不同兩個簇的兩個最遠的點之間的距離。
(3)組平均：定義簇的鄰近度為取自兩個不同簇的所有點對鄰近度的平均值。
根據(jù)該算法，實現(xiàn)如下代碼。開始時計算每個點對的距離，并按距離降序依次合并。另外為了防止過度合并，定義的退出條件是90%的簇被合并，即當前簇數(shù)是初始簇數(shù)的10%：
https://github.com/intergret/snippet/blob/master/HAC.py
或是 http://www.oschina.net/code/snippet_176897_14732
聚類的效果如下圖，黑色是噪音點： 另外我們可以看出凝聚的層次聚類并沒有類似基本K均值的全局目標函數(shù)，沒有局部極小問題或是很難選擇初始點的問題。合并的操作往往是最終的，一旦合并兩個簇之后就不會撤銷。當然其計算存儲的代價是昂貴的。
DBSCAN：是一種簡單的，基于密度的聚類算法。本次實現(xiàn)中，DBSCAN使用了基于中心的方法。在基于中心的方法中，每個數(shù)據(jù)點的密度通過對以該點為中心以邊長為2*EPs的網(wǎng)格(鄰域)內(nèi)的其他數(shù)據(jù)點的個數(shù)來度量。根據(jù)數(shù)據(jù)點的密度分為三類點：
(1)核心點：該點在鄰域內(nèi)的密度超過給定的閥值MinPs。
(2)邊界點：該點不是核心點，但是其鄰域內(nèi)包含至少一個核心點。
(3)噪音點：不是核心點，也不是邊界點。
有了以上對數(shù)據(jù)點的劃分，聚合可以這樣進行：各個核心點與其鄰域內(nèi)的所有核心點放在同一個簇中，把邊界點跟其鄰域內(nèi)的某個核心點放在同一個簇中。
根據(jù)該算法，實現(xiàn)如下代碼：
https://github.com/intergret/snippet/blob/master/Dbscan.py
或是 http://www.oschina.net/code/snippet_176897_14734
聚類的效果如下圖，黑色是噪音點： 因為DBSCAN使用簇的基于密度的定義，因此它是相對抗噪音的，并且能處理任意形狀和大小的簇。但是如果簇的密度變化很大，例如ABCD四個簇，AB的密度大大大于CD，而且AB附近噪音的密度與簇CD的密度相當，這是當MinPs較大時，無法識別簇CD，簇CD和AB附近的噪音都被認為是噪音；當MinPs較小時，能識別簇CD，但AB跟其周圍的噪音被識別為一個簇。這個問題可以基于共享最近鄰(SNN)的聚類結局。
|
