聚類算法聚類算法概述聚類是研究“物以類聚”問題的分析方法一般方法：目的是分組需要明確指定分組變量需要明確指定分組標準聚類分析能夠將一批樣本數(shù)據(jù)，在沒有先驗知識的前提下，根據(jù)數(shù)據(jù)的諸多特征，按照其在性質上的親疏程度進行自動分組，且使組內(nèi)部個體的結構特征具有較大相似性，組之間個體的特征相似性較小。是一種對數(shù)據(jù)進行描述建模型的方法，探索數(shù)據(jù)中是否存在“自然的子類”聚類算法的種類從聚類結果角度劃分：覆蓋聚類算法與非覆蓋聚類算法：如果每個數(shù)據(jù)點都至少屬于一個類，則稱為覆蓋聚類，否則為非覆蓋聚類層次聚類和非層次聚類：如果存在兩個類，其中一個類是另一個類的子集，則稱為層次聚類，否則稱為非層次聚類確定聚類和模糊聚類：如果任意兩個類的交集為空，一個數(shù)據(jù)點最多只屬于一個類，則稱為確定聚類（或硬聚類）。否則，如果至少一個數(shù)據(jù)點屬于一個以上的類，則稱為模糊聚類聚類算法的種類從聚類變量類型角度劃分數(shù)值型聚類算法、分類型聚類算法和混合型聚類算法從聚類的原理角度劃分劃分聚類（Partitional

clustering）、層次聚類（Hierarchical

clustering）、基于密度的聚類（Density-based

clustering）算法、網(wǎng)格聚類（Rid

clustering）等K-means快速聚類屬于覆蓋型、數(shù)值、劃分聚類算法如何測度“親疏”關系距離法由于處理的聚類變量均為數(shù)值型，將點與點之間的距離定義為歐氏距離劃分聚類是指，首先將樣本空間隨意劃分為若干個區(qū)域（類），然后依據(jù)上述定義的距離，將所有樣本點分配到與之“親近”的區(qū)域（類）中，形成初始的聚類結果K-means快速聚類的基本步驟1.指定最后要聚成K類2.用戶指定k個樣本作為初始類中心或系統(tǒng)自動確定k個樣本作為初始類中心3.系統(tǒng)按照距k個中心距離最近的原則把每個樣本分派到各中心所在的類中去,形成一個新的k類，完成一次迭代4.重新計算k個類的類中心(計算每類各變量的均值,以均值點作為類中心)5.重復3步和4步，直到達到指定的迭代次數(shù)或達到終止迭代的條件K-means快速聚類的圖示快速聚類的說明聚類變量值不應有數(shù)量級上的差異標準化處理的必須的快速聚類的說明對分類型變量的處理啞變量方式（0/1)問題：d(x,y)，x=A，y=B(3分類)，則該分類型變量在歐氏距離中的“貢獻”為：大于1，而數(shù)值型變量的距離貢獻不可能大于1Clementine的解決策略是：將1調整為(1

-

0)2

+

(0

-1)

2

+

(0

-

0)

2

=

20.5

?

0.707快速聚類示例：我國31個省市自治區(qū)2008年各地區(qū)經(jīng)濟發(fā)展的數(shù)據(jù)為例聚類快速聚類的特點：所得到的類通常呈“球狀”分布算法本身無法較好地處理分類型變量算法需要指定聚類數(shù)目由于類中心的確定采用均值，因而聚類結果易受到離群點和噪聲數(shù)據(jù)的影響，且算法本身并沒有診斷的有效手段。兩步聚類算法兩步聚類（TwoStepClustering）算法是Chiu等人于2001年在BIRCH（Balanced

Iterative

Reducing

and

ClusteringusingHierarchies）算法基礎上提出的一種改進算法。算法尤其適合于大型數(shù)據(jù)集的聚類研究特點：通過兩步實現(xiàn)數(shù)據(jù)聚類同時處理數(shù)值型聚類變量和分類型聚類變量根據(jù)一定準則確定聚類數(shù)目診斷樣本中的離群點和噪聲數(shù)據(jù)兩步聚類算法第一步，預聚類采用“貫序”方式將樣本粗略劃分成L個子類預聚類過程聚類數(shù)目不斷增加第二步，聚類在預聚類的基礎上，再根據(jù)“親疏程度”決定哪些子類可以合并，最終形成L’類。聚類數(shù)目不斷減少的過程，隨著聚類的進行，類內(nèi)部的差異性將不斷增大。兩步聚類算法“親疏程度”的測度聚類變量均為數(shù)值型（標準化后），采用歐氏距離否則，采用對數(shù)似然（Log-likelihood）距離混合分布：總體分布是有限個子分布的加權線性組合J

nf

(x)

=

log(

f

(

X

k

;qj

))j

=1

k

=1Jf

(x)

=

p

j

f

j

(

X

;qj

)j

=1Jl

=

l

jj

=1如果數(shù)據(jù)矩陣的各行是獨立的，則：兩步聚類算法“親疏程度”的測度K個聚類變量x1，x2，…xk，其中包括KA個數(shù)值型聚類變量和KB個分類型聚類變量，對數(shù)似然距離定義為：反應了類內(nèi)部變量取值的總體差異性（定距變量以方差測度，分類型變量以熵測度）Jl

=

l

jj

=1d

(

j,

s)

=

l?

-

l?

=

l?

+

l?

-

l?new

j

s

<

j

,s>=

xj

+x

s-x<

j

,s>合并之前的對數(shù)似然估計合并之后的對數(shù)似然估計?log(12K

Bvk

2vkk

=1K

Ak

=12kv

v)

+

E

)+s?s?x

=

-N

()log(

vkl

NvN

vkl

NvNE?vkLk=

-l

=1兩步聚類算法---預聚類預聚類算法是Zhang、Ramakrishnon和Livny在1996年所提出的BIRCH算法的改進算法BIRCH算法提出了CF樹CF樹（Clustering

Feature

Tree）CF樹是一種描述樹結構的數(shù)據(jù)存儲方式通過指針反映樹中結點的上下層次關系。樹中的葉結點為子類，具有同一父結點的若干子類合并為一個大類形成樹的中間結點。若干大類可繼續(xù)合并成更大的類形成更高層的中間結點，直到根結點表示所有數(shù)據(jù)形成一類CF樹是一種數(shù)據(jù)的壓縮存儲方式(充分統(tǒng)計量)BjCF

={N

,

S

,

S

2

,

N

}j

j

Aj

Aj預聚類過程視所有數(shù)據(jù)為一個大類，其匯總統(tǒng)計量存儲在根結點中讀入一條數(shù)據(jù)，從CF樹的根結點開始，利用結點的匯總統(tǒng)計量，計算數(shù)據(jù)與中間結點（子類）的對數(shù)似然距離，并沿著對數(shù)似然距離最小的中間結點依次向下選擇路徑直到葉結點計算與子樹中所有葉結點（子類）的對數(shù)似然距離，找到距離最近的葉結點兩步聚類算法---預聚類預聚類過程如果最近距離小于一定閾值，則該數(shù)據(jù)被相應的葉結點“吸收”；否則，該數(shù)據(jù)將“開辟”一個新的葉結點。重新計算葉結點和相應所有父結點的匯總統(tǒng)計量葉結點足夠大時應再分裂成兩個葉結點葉結點個數(shù)達到允許的最大聚類數(shù)目時，應適當增加閾值重新建樹，以得到一棵較小的CF樹重復上述過程，直到所有數(shù)據(jù)均被分配到某個葉結點（子類）為止兩步聚類算法---預聚類離群點的甄別離群點，即那些合并到任何一個類中都不恰當?shù)臄?shù)據(jù)點兩步聚類的處理策略：找到包含樣本量較少的“小”葉結點，如果其中的樣本量僅是“最大”葉結點所含樣本量的很小比例，則視這些葉結點中的數(shù)據(jù)點為離群點

(Clementine默認為25%)兩步聚類算法---預聚類聚類過程：分析對象是預聚類所形成的稠密區(qū)域（DenseRegion）采用的方法：層次聚類法聚類過程所形成某個中間類一定會是另一個類的子類聚類過程是逐步將較多的小類合并為較少的大類，再將較少的大類合并成更少的更大類，最終將更大類的合并成一個大類，是一個類不斷“凝聚”的過程問題：第一，內(nèi)存容量問題第二，怎樣的聚類數(shù)目是合適的問題兩步聚類算法---聚類第一階段以BIC，粗略的聚類數(shù)依據(jù)類內(nèi)部差異性并兼顧模型復雜度所有類合并成一個大類，BIC的第一項最大，第二項最小。當聚類數(shù)目增加時，第一項逐漸減少，第二項逐漸增大，但BIC總體上減少；當聚類數(shù)目增加到J時，第二項的增大幅度開始大于第一項的減少幅度，BIC總體上開始增大，此刻的J即為所求JBIC(J

)

=

-2xj

+

mJ

log(N

)j

=1KBk

=1

kAJ(L

-1))m

=

J

(2K

+兩步聚類算法---聚類數(shù)目確定兩步聚類算法---聚類數(shù)目確定第一階段以BIC，粗略的聚類數(shù)?計算類內(nèi)差異的定基增長率找到R1(J)取最小值（Clementine規(guī)定R1(J)應小于0.04）的J為聚類數(shù)目的“粗略”估計dBIC

(J

)

=

BIC

(J

)

-

BIC

(J

+1)1dBIC(1)R

(J

)

=

dBIC(J

)第二階段對第一階段“粗略”估計值J的修正依據(jù)類間對數(shù)似然距離，不考慮模型的復雜度2dmin

(CJ

)R

(J

)

=兩步聚類算法---聚類數(shù)目確定最小類間距離dmin

(CJ

+1

)計算類間最小距離的環(huán)比增長率，R2(J-1)、R2(J-2)到R2(2)的值找到其中的最大值和次大值。Clementine中，如果最大值是次大值的

1.15倍以上，則最大值所對應的J為最終聚類數(shù)；否則，最終聚類數(shù)J為最大值對應的聚類數(shù)目和次大值對應的聚類數(shù)目中的較大值兩步聚類算法示例：保留客戶的細分服務套餐選擇分布存在差異是否選擇無線服務的分布存在差異受教育水平和收入等方面的分布也存在差異Kohonen網(wǎng)絡聚類Kohonen網(wǎng)絡2001年芬蘭科學家Kohonen提出的是一種自組織特征映射網(wǎng)絡(Self-Organizing

FeatureMap:SOFM)：前饋式、兩層、全連接、認知機網(wǎng)絡廣泛應用于聚類問題中采用歐氏距離作為數(shù)據(jù)點“親疏程度”的測度，通常適合于數(shù)值型聚類變量，也能處理重新編碼的分類型變量模擬人腦神經(jīng)細胞的機理，引入競爭機制，實現(xiàn)聚類Kohonen網(wǎng)絡聚類概述人腦神經(jīng)細胞的工作原理神經(jīng)細胞的組織是很有序的，通常呈二維空間排列空間中處于不同區(qū)域的神經(jīng)細胞控制著人體不同部位的運動空間中處于鄰近區(qū)域的神經(jīng)細胞之間存在側向交互性空間中處于不同區(qū)域的神經(jīng)細胞對不同刺激信號表現(xiàn)出不同的敏感性，通常與進化和后天訓練有極大關系Kohonen網(wǎng)絡聚類概述Kohonen網(wǎng)絡的拓撲結構一個輸入層、一個輸出層(也稱競爭層)，沒有隱層每個輸入節(jié)點與輸出節(jié)點完全相連輸出節(jié)點呈二維結構分布輸出層中的節(jié)點具有側向連接，在一定的鄰域范圍內(nèi)有一定數(shù)量的鄰接節(jié)點兩類權值：輸入節(jié)點與輸出節(jié)點之間的連接權值輸出節(jié)點與鄰接節(jié)點間的側向連接權值輸入結點接收到樣本數(shù)據(jù)的“刺激信號”后，將通過網(wǎng)絡連接“傳遞”給輸出結點。輸出結點將對不同的輸入表現(xiàn)出不同的“敏感性”，并通過側向連接影響其鄰接結點，最終“獲勝”的輸出結點將給出最大的輸出值輸出層空間中哪些區(qū)域的輸出結點對哪種特征的輸入表現(xiàn)出一貫性的“敏感”，是樣本“后天”訓練的結果學習結束以后，輸出層結點所反應的結構特征即是對不同樣本群不同特征的概括Kohonen網(wǎng)絡聚類原理輸入結點的個數(shù)取決于聚類變量的個數(shù)，輸出結點的個數(shù)表示聚類數(shù)目學習的目標就是要使某個特定的輸出結點對于具有某種相同結構特征的樣本輸入給出一致的輸出學習結束后，每個輸出結點將對應一組結構特征相似的樣本，即對應樣本空間的一個區(qū)域，構成一組聚類。輸出層是二維的，而輸入是多維的，對應映射關系能夠很好地將多維空間中數(shù)據(jù)分布的特征反應到二維平面上Kohonen網(wǎng)絡聚類原理第一，數(shù)據(jù)預處理數(shù)值型變量的標準化處理分類型變量的預處理第二，確定聚類數(shù)目k和初始類中心第j個類中心位置由p個(輸出節(jié)點)0至1范圍內(nèi)的隨機數(shù)wij(i=1,2,…p)確定K個類中心對應K個輸出結點，每個輸出結點對應一個具有p個元素的行向量W第三，t時刻，隨機讀入一個樣本數(shù)據(jù)X(t)計算與K個類中心點的歐氏距離d(t)，找出距離最近的類中心：輸出結點Wc(t)。Wc(t)是“獲勝”結點，是對第t個樣本的最佳“匹配

”結點---最敏感的節(jié)點Kohonen網(wǎng)絡的聚類過程第四，調整“獲勝”結點Wc(t)和其鄰接結點所代表的各類中心位置調整算法類似人工神經(jīng)網(wǎng)絡中網(wǎng)絡權值的調整以樣本與類中心的距離為依據(jù)進行權值調整“獲勝”結點Wc(t)的權值調整為：指定一個鄰域半徑，以Wc(t)為圓心，距離在指定半徑范圍內(nèi)的輸出結點都視為鄰近結點。對鄰接結點

Wj(t)的權值調整的計算方法：Kohonen網(wǎng)絡的聚類過程Wc

(t

+1)

=

Wc

(t)

+h(t)[

X

(t)

-Wc

(t)]Wj

(t

+1)

=

Wj

(t)

+h

(t)hjc

(t)[

X

(t)

-Wj

(t)]h

jc

(t)=

max(|wij

(t)

-

wic

(t)

|) (i

=

1,2,...,

p)鄰區(qū)半徑（可看為0或1）Clementine鄰接半徑設置似乎有問題h依t遞減把輸出節(jié)點向相應輸入節(jié)點的方向拉近第五，判斷是否滿足迭代終止的條件輸出層形成一個能夠反映各類樣本結構（類）特征關聯(lián)的映射，有效將數(shù)據(jù)在高維空間中的聚類特征投影到低維空間中。這個過程被稱為自組織過程。Kohonen網(wǎng)絡的聚類過程兩個學習階段第一個階段為粗略學習階段，指定一個相對較大的鄰域半徑和初始學習率，以大致概括數(shù)據(jù)的結構特征；第二階段為調整學習階段，指定一個相對較小的鄰域半徑和初始學習率，對類中心做進一步的細小調整，以保證輸出層所體現(xiàn)的數(shù)據(jù)結構特征更貼近樣本的真實情況Kohonen網(wǎng)絡聚類的說明學習率值偏小，無法使各輸入節(jié)點與競爭節(jié)點之間的權重迅速接近某相似模式,不能使各相似模式有效地分離較大的學習率雖然可以有效的改善聚類效果，但也會帶來權重調整的震蕩問題在權重的調整過程中采取可變學習率的策略。實踐證明這種方法不僅可以有效解決震蕩問題，而且可以加速網(wǎng)絡的收斂通常h是依次遞減的?？梢跃€性遞減函數(shù)，也可以是非線性遞減函數(shù)，定義為：其中：h(0)為學習率的初始值；c為已完成的學習周期；hlow為最小值，小于h(0)Kohonen網(wǎng)絡聚類的說明手寫數(shù)字識別Kohonen網(wǎng)絡聚類的應用(0,0):0(

2,0):1(1,0):2基于聚類分析的離群點探索通過聚類，計算樣本點與數(shù)據(jù)組群之間的距離，以距離遠近的判斷，實現(xiàn)離群點診斷以及離群點成因的分析多維空間基于聚類的診斷方法離群點分析包括三個階段：第一，聚類，即根據(jù)“親疏程度”將樣本點聚成若干類；第二，計算，即在第一階段聚類的基礎上，依據(jù)距離，計算所有樣本點的異常性測度指標；第三，診斷，即在第二階段異常性測度指標的基礎上，確定最終的離群點，并分析導致樣本點異常的原因，

即分析離群點在哪個變量方向上呈現(xiàn)異常多維空間基于聚類的診斷方法第二階段：計算樣本的離群測度指標對于樣本點S，找到樣本點S所屬的類v計算樣本點S與類別v的對數(shù)似然距離，稱之為組差異指標GDI(Group

Deviation

Index)多維空間基于聚類的診斷方法vvvkv

vNNNNLkK

A

K

Bvkl

log

vklE????122kl

=1vk

2vkk

=1k

=1=

-)

+

E

)log(s

+

sx

=

-N

(=

xv

-

x<v,s>GDI

S

=

d

(v,

s)

=

xv

+

xs

-x<v,s>GDI反映了樣本點S加入類v所引起的類