轉載於IT莊園博客：
http://blog.21ic.com/user1/5396/archives/2009/58831.html
http://blog.21ic.com/user1/5396/archives/2009/58832.html
聚類就是將數據對象分組成多個類或者簇，劃分的原則是在同一個粗中的對象之間具有較高的相似度，而不同簇中的對像差別較大。屬於一種無指導的學習方法。
好的聚類算法應該滿足以下幾個方面：
（1） 可伸縮型：無論對小數據量還是大數據量應該都是有效的。
（2） 具有處理不同類型屬性的能力。
（3） 能夠發現任意形狀的聚類。
（4） 輸入參數對領域知識的弱依賴性
（5） 對於輸入記錄順序不敏感
（6） 能夠處理很多維度的數據，而不止是對3維左右的數據有效
（7） 處理噪聲數據的能力
（8） 基於約束的距離：既能找到滿足特定的約束，又具有良好聚類特性的數據分組
（9） 挖掘出來的信息是可理解的和可用的。
聚類分析主要在以下幾個方面應用：
（1） 可以作為其他算法的預處理步驟
（2） 可以作為一個獨立的工具來獲得數據的分佈情況
（3） 可以完成孤立點挖掘，用來預示欺詐行為的存在。
基本概念
聚類分析的輸入可以用一組有序對（X,s）或(X,d)表示，這裡X表示一組樣本，s和d分別是度量樣本間相似度或相異度(距離)的標準。聚類系統的輸出是一個分區C={C1,C2,…,Ck}，其中Ci是X的子集，成為類。類的特徵可以用如下幾種方式表示：
2 通過類的中心或類的邊界點表示一個類。
2 使用聚類樹中的結點圖形化地表示一個類。
2 使用樣本屬性的邏輯表達式表示類。
聚類分析的方法：
聚類分析有很多大量的、經典的算法，比如k-平均、k-中心點、PAM、CLARANS, BIRTH,CURE,OPTICS,DBSCAN,STING,CLIQUE,WAVECLUSTER等。
度量標準：
一個聚類分析過程的質量取決於對度量標準的選擇，因此必須仔細選擇度量標準。 （1）距離函數
2 明可夫斯基距離：
x, y 是相應的特徵，n是特徵的維數。則明可夫斯基距離d(x,y)表示如下
，r=2為歐式距離。
2 二次型距離：
2 餘弦距離
2 二元特徵樣本的距離
假定x和y分別是n維特徵，xi和yi分別表示每維特徵，且xi和yi的取值為二元類型數值{0，1}。則x和y的距離定義的常規方法是先求如下幾個參數，然後採用SMC、Jaccard係數或Rao係數。
a是樣本x和y中滿足 xi=yi=1的二元類型屬性的數量
b是樣本x和y中滿足xi=1,yi=0的二元類型屬性的數量
c是樣本x和y中滿足xi=0,yi=1的二元類型屬性的數量
d是樣本x和y中滿足xi=yi=0的二元類型屬性的數量
則簡單匹配係數（Simple Match Coefficient, SMC）的公式如下：
Jaccard係數：
Rao係數：
（2）類間距離
設有兩個類Ca和Cb，分別有m和n個元素，他們的中心分別為ra和rb。設元素x屬於Ca，y屬於Cb，這兩個元素之間的距離記為d(x,y),類間距記為D(Ca,Cb)。
2 最短距離法：類中最靠近的兩個元素的距離為類間距離：
2 最長距離法：類中最遠的兩個元素的距離為類間距離
2 重心法：類中兩個中心點間的距離為類間距離。因此就需要定義類中心，類中心的定義：
2 類平均法：兩個類中任意兩個元素之間的距離相加後取平均值。
2 離差平方和：用到了類直徑，類直徑反應了類中各元素的差異，可以定義為各元素到類中心的歐式距離之和，這樣就得到了Ca,Cb,Ca+b的直徑分別為ra,rb,ra+b,那麼類間距為ra+b – ra - rb。
劃分聚類方法
層劃分聚類算法的基本思想
給定一個有n個對象的數據集，劃分聚類技術將構造數據k個劃分，每一個劃分就代表一個簇，k<=n。這k個劃分滿足下列條件：
2 每個簇至少包含一個對象
2 每個對象屬於且僅屬於一個簇
對於給定的k，算法首先給出一個初始的劃分方法，以後通過迭代來改變劃分，是得每一次改進之後的劃分方案都較前一次更好。所謂更好的標準時是：同一個簇中的對象越接近越好，不同簇之間的對象越遠越好。目標是最小化所有對象與其參考點之間的相異度之和。這裡的遠近或者相異度/相似度實際上是聚類的評價函數。
評價函數：
評價函數應該考慮裡兩個方面：每個簇應該是緊湊的，每個簇間的距離應該盡可能地遠。這就需要觀察兩個值：類內差異和類間差異。類內差異可以採用多種距離函數來定義，最簡單的就是計算類內的每一個點到類中心的距離的平方和，一般用w(C)表示。類間差異定義為類中心之間的距離，一般用b(C)表示。
K-means算法
首先隨機地選擇k個對象，每個對象處劃地代表了一個簇的平均值或中心。對剩餘的每個對像根據其與各個簇中心的距離，將它賦給最近的簇。然後重新計算每個簇的平均值。這個過程不斷重複，直到準則函數收斂。準則如下：
準則函數其實就是所有對象的平法誤差的總和，這個準則試圖試生成的結果簇盡可能地緊湊和獨立。
算法描述：
輸入：簇的數目k和包含n個對象的數據庫
輸出：k個簇，是平方誤差準則最小
（1） 任意選擇k個對像作為初始的簇中心
（2） Repeat
（3） 根據簇中對象的平均值，將每個對象賦給最類似的簇
（4） 更新簇的平均值，即計算每個對象簇中對象的平均值
（5） 計算準則函數
（6） Until E不再明顯地發生變化
算法性能：
優點：
（1） 簡單、快速
（2） 對大數據集，是可伸縮和高效率的。
（3） 算法嘗試找出使平方誤差函數值最小的k個劃分。當結果簇是密集的，而簇與簇之間區別明顯的時候，效果較好。
缺點：
（1） 不適合分類屬性的數據
（2） 必須給定k，對初始值k比較敏感
（3） 不適合發現非凸面形狀的簇，對噪聲和孤立點數據是敏感的。
改進措施：
（1）k-模算法，可以對離散屬性計算
（2）不採用簇中的平均值作為參考點，而選用簇中位置最靠近中心的對象。這樣可以避免孤立點的影響。
PAM算法（也稱k-中心點算法）
PAM算法需用簇中位置最靠近中心的對像作為代表對象，然後反复地用非代表對象來代替代表對象，試圖找出更好的中心點，在反复迭代的過程中，所有可能的“對像對”被分析，每個對中的一個對像是中心點，另一個是非代表對象。一個對象代表可以被最大平方-誤差值減少的對象代替。
一個非代表對象Oh是否是當前一個代表對象Oi的一個好的替代，對於每個非中心點對象Oj，有以下四種情況需要考慮：
（1） Oj當前隸屬於Oi，如果Oi被Oh替換，且Oj離另一個Om最近，i！ =m，那麼Oj被分配給Om，則替換代價為Cjih=d(j,m)-d(j,i)。
（2） Oj當前隸屬於Oi，如果Oi被Oh替換，且Oj離Oh最近，那麼Oj被分配給Oh，則替換代價為Cjih=d(j,h)-d(j,i)。
（3） Oj當前隸屬於Om，m！ =i，如果Oi被Oh替換，且Oj仍然離Om最近，那麼Oj被分配給Om，則替換代價為Cjih=0。
（4） Oj當前隸屬於Om，m！ =i，如果Oi被Oh替換，且Oj離Oh最近，那麼Oj被分配給Oh，則替換代價為Cjih=d(j,h)-d(j,m)。
然後計算
如果 為負，則可以替換。
算法描述：
輸入：簇的數目k和包含n個對象的數據庫
輸出：k個簇，使得所有對象與其最近中心點的相異度總和最小
（1） 任意選擇k個對像作為初始的簇中心點
（2） Repeat
（3） 指派每個剩餘對像給離他最近的中心點所表示的簇
（4） Repeat
（5） 選擇一個未被選擇的中心點Oi
（6） Repeat
（7） 選擇一個未被選擇過的非中心點對象Oh
（8） 計算用Oh代替Oi的總代價並記錄在S中
（9） Until 所有非中心點都被選擇過
（10） Until 所有的中心點都被選擇過
（11） If 在S中的所有非中心點代替所有中心點後的計算出總代價有小於0的存在，then找出S中的用非中心點替代中心點後代價最小的一個，並用該非中心點替代對應的中心點，形成一個新的k個中心點的集合；
（12） Until 沒有再發生簇的重新分配，即所有的S都大於0.
算法性能：
(1) 消除了k-平均算法對於孤立點的敏感性。
(2) K-中心點方法比k-平均算法的代價要高
(3) 必須指定k
(4) PAM對小的數據集非常有效，對大數據集效率不高。特別是n和k都很大的時候。
轉載本文請聯繫原作者獲取授權，同時請註明本文來自高小龍科學網博客。
鏈接地址：http://blog.sciencenet.cn/blog-849773-692323.html
留言列表
