數(shù)據(jù)挖掘-三個算法課件

7.4

劃分方法K均值算法K中心點算法劃分方法給定n個對象的數(shù)據(jù)集D,以及要生成的簇的數(shù)目k,劃分算法將對象組織為k個劃分（k≤n）,每個劃分代表一個簇。這些簇的形成旨在優(yōu)化一個目標劃分準則，如基于距離的相異度函數(shù)，使得根據(jù)數(shù)據(jù)集的屬性，在同一個簇中的對象是“相似的”，而不同的簇中的對象是“相異的”。第一種劃分方法—k均值（k-means）K均值算法以K（一般是用戶指定的）為輸入?yún)?shù)，把n個對象的集合分為K個簇，使得結果簇內(nèi)對象的相似度高，簇間對象的相似度低。算法聚類流程：首先，隨機地選擇k個對象，每個對象代表一個初始簇中心。對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它指派到距離最近的簇。然后計算每個簇的新均值。這個過程不斷重復，直到簇中心點不再發(fā)生變化。初始數(shù)據(jù)集K=2將剩余對象指派到離它最近的簇任選兩個初始簇中心更新聚類中心將剩余對象指派到最近的簇更新聚類中心更新簇中心，直到所有的簇中心不發(fā)生變化重新指派對象到距離最近的簇第一次聚類結果第二次聚類結果第三次聚類結果輸入：k:簇的數(shù)目，D:包含n個對象的數(shù)目集。輸出：k個簇的集合。方法：從D中任意選擇k個對象作為初始簇中心；Repeat根據(jù)簇中對象的均值，將每個對象指派到最相似的簇;更新簇均值，即計算每個簇中對象的均值;Until每個簇的中心不再發(fā)生變化K均值過程概述O1(0，2)O2(0，0)O5(5，2)O3(1.5,0)4O

(5,0)XxyO102O200O31.50O450O552舉例：將數(shù)據(jù)對象集合s分為兩個簇，即

k=2YS：(1)隨機選擇兩個初始簇中心。M1=O1=(0,2)

M2=O2=(0,0)，對應的簇為C1，C2(2)對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它賦給最近的簇。d(M2,O3

)=1.5

，將O3

加入簇C2。對O3

：d(M1,O3

)=2.5對O4

：d(M1,O4

)=5.38 d(M2,O4

)=5

，將O4

加入簇C2。對O5

：d(M1,O5

)=5 d(M2,O5

)=5.38

，將O5

加入簇C1。更新，得到兩個簇C1={O1，O5}和C2={O2，O3，O4}(3)計算新的簇的中心。（簇中心不一定是集合中的點）M2=(2.17,0)M1=(2.5,2)重復(2)和(3)對O1

：d(M1,O1

)=2.5 d(M2,O1

)=4.72

，將O1

加入簇C1。對O2

：d(M1,O2

)=3.2 d(M2,O2

)=2.17

，將O2

加入簇C2。對O3

：d(M1,O3

)=2.24 d(M2,O3

)=0.67

，將O3

加入簇C2。對O4

：d(M1,O4

)=3.2 d(M2,O4

)=2.83

，將O4

加入簇C2。對O5

：d(M1,O5

)=2.5 d(M2,O5

)=3.47

，將O5

加入簇C1。由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。聚類結果：C1={O1，O5}

和

C2={O2，O3，O4}提醒：當選擇O2和O5為初始簇中心點時聚類結果是C1={O1，O2，O3}和C2={O4，O5}優(yōu)點：思想簡單易行；時間復雜度接近線性；對大數(shù)據(jù)集，是可伸縮和高效率的。缺點：最終的結果會隨初始中心的變化而變化；算法依賴于用戶指定的k值，不合適的k

可能返回較差的結果；對離群點是敏感的。第二種劃分方法—k中心點K均值算法對于離群點是敏感的，因為一個具有很大的 值的對象可能顯著地 數(shù)據(jù)的分布。平方誤差的使用更是嚴重 了這一影響。“如何修改這個算法來降低這種敏感性？”可以不采用簇中對象的均值作為參考點，而是在每個簇中選出一個實際的對象來代表該簇。其余的每個對象聚類到與其最相似的代表性對象所在的簇中。這樣，劃分依然基于最小化所有對象與其對應的參考點之間的相異度之和的原則來執(zhí)行。算法聚類流程：首先隨意選擇初始代表對象。只要能提高結果聚類質(zhì)量，迭代過程就繼續(xù)用非代表對象替換代表對象。聚類結果的質(zhì)量用代價函數(shù)來評估，該函數(shù)度量對象與其簇的代表對象之間的平均相異度。為了確定非代表對象Orandom是否是當前代表對象Oj的好的替代，對于每一個非代表對象p，考慮如下4種情況。第一種情況：p當前隸屬于代表對象Oj。如果Oj被Orandom所代替作為代表對象，且p離其他代表對象Oi(i≠j)最近，則p重新分配給Oi。第二種情況：p當前隸屬于代表對象Oj。如果Oj被Orandom代替作為代表對象，且p離Orandom最近，則p被重新分配給Orandom。第三種情況：p當前隸屬于中心點Oi，i≠j。如果Oj被Orandom代替作為代表對象，而p依然離Oi最近，則對象的隸屬不發(fā)生變化。第四種情況：p當前隸屬于中心點Oi，i≠j。如果Oj被Orandom代替作為代表對象，且p離Orandom最近，那么p被重新分配給

Orandom。第四種情況p

被重新分配給Orandom代價

=d

(Orandom,p)-d

(Oi,p)OiOjOrando第一種情況mp

被重新分配給Oi代價

=d

(Oi,p)-d

(Oj,p)pOiOjOrando第二種情況mp

被重新分配給Orandom代價

=d

(Orandom

,p)-d

(Oj

,p)pOiOjOrando第三種情況mp

的隸屬不發(fā)生變化代價

=0pOiOjOrandomp17K中心點算法1098765432100123456789

1010987654321023456789

100

1K=2隨機選擇k個對象作為初始中心點1098765432100123456789

10將剩余對象指定到離中心點最近的簇中隨機選擇一個非中心對象Oramdom計算總的替換代價10987654321001

23

45

67

89

10如果聚類質(zhì)量提高，用Oramdom替換O循環(huán)直到代價不再減小為止10987654321001

23

45

67

89

10每當重新分配發(fā)生時，絕對誤差E

的差對代價函數(shù)有影響。因此，如果當前的代表對象被非代表對象所取代，代價函數(shù)就計算絕對誤差值的差。交換的總代價是所有非代表對象所產(chǎn)生的代價之和。如果總代價是負的，實際絕對誤差將會減小，Oj可以被Orandom替代。如果總代價是正的，則當前的代表對象Oj是可接受的，在本次迭代中沒有變化發(fā)生。算法5-2

PAM（k-中心點算法）輸入：簇的數(shù)目k和包含n個對象的數(shù)據(jù)庫。輸出：k個簇，使得所有對象與其最近中心點的相異度總和最小。任意選擇k個對象作為初始的簇中心點；REPEAT指派每個剩余的對象給離它最近的中心點所代表的簇；REPEAT選擇一個未被選擇的代表Oi；REPEAT選擇一個未被選擇過的代表對象Orandom；計算用Orandom代替Oi的總代價并記錄在S中；UNTIL

所有的非代表都被選擇過；UNTIL

所有的代表對象都被選擇過；（11）IF

在S中的所有非代表對象代替所有代表對象后計算出的總代價有小于0的存在

THEN

找出S中的用非代表對象替代代表對象后代價最小的一個，并用該非代表對象替代對應的代表對象，形成一個新的k對象的集合；（12）UNTIL

沒有再發(fā)生簇的重新分配，即所有的S都大于0.假如空間中的五個點｛A、Ｂ、Ｃ、Ｄ、Ｅ｝如圖1所示，各點之間的距離關系如表1所示，根據(jù)所給的數(shù)據(jù)對其運行PAM算法實現(xiàn)劃分聚類（設k=2）。樣本點間距離如下表所示:樣本點ABCDEA01223B10243C22015D24103E33530CADBE322EDCBA第一步建立階段：假如從5個對象中隨機抽取的2個中心點為{A，B},則樣本被劃分為{A、C、D}和{B、E}，如圖5-3所示。第二步

交換階段：假定中心點A、B分別被非中心點{C、D、E}替換，根據(jù)PAM算法需要計算下列代價TCAC、TCAD、TCAE、TCBC、TCBD、TCBE。以TCAC為例說明計算過程：當A被C替換以后，A不再是一個中心點，因為A離B比A離C近，A被分配到B中心點代表的簇，CAAC=d(A,B)-d(A,A)=1。B是一個中心點，當A被C替換以后，B不受影響，CBAC=0。C原先屬于A中心點所在的簇，當A被C替換以后，C是新中心點，符合PAM算法代價函數(shù)的第二種情況CCAC=d(C,C)-d(C,A)=0-2=-2。D原先屬于A中心點所在的簇，當A被C替換以后，離D最近的中心點是C，根據(jù)PAM算法代價函數(shù)的第二種情況CDAC=d(D,C)-d(D,A)=1-2=-1。E原先屬于B中心點所在的簇，當A被C替換以后，離E最近的中心仍然是B，根據(jù)PAM算法代價函數(shù)的第三種情況CEAC=0。因此，TCAC=CAAC+CBAC+CBAC+CDAC+CEAC=1+0-2-1+0=-2。樣本點起始中心點為A,B在上述代價計算完畢后，要選取一個最小的代價，顯然有多種替換可以選擇，選擇第一個最小代價的替換（也就是C替換A），根據(jù)圖5-4（a）所示，樣本點被劃分為{B、A、E}和{C、D}兩個簇。圖5-4（b）和圖5-4（c）分別表示了D替換A，E替換A的情況和相應的代價(a)

C替換A,

TCAC=-2 (b)

D替換A,

TCAD=-2 (c)

E替換A,

TCAE=-1圖5-4 替換中心點A圖5-5（a）、（b）、（c）分別表示了用C、D、E替換B的情況和相應的代價。C替換B,

TCBC=-2(b)

D替換B,TCBD=-2 (c)

E替換B,

TCBE=-2圖5-5替換中心點B通過上述計算，已經(jīng)完成了PAM算法的第一次迭代。在下一迭代中，將用其他的非中心點{A、D、E}替換中心點{B、C}，找出具有最小代價的替換。一直重復上述過程，直到代價不再減小為止。311EDCBA311EDCBA312EDCBA311EDCBA311EDCBA122EDCBAK中心點算法的特點：當存在噪聲和離群點時，K中心點方法比K均值更健壯，因為中心點不像均值那樣容易受離群點或其他

值的影響。K中心點方法的執(zhí)行代價比K均值算法高。兩種方法都要指定簇的個數(shù)K.AdaBoost算法AdaBoostAdaboost是adaptiveboost的縮寫，它是一種迭代算法。其思想是針對同一個訓練集訓練不同的分類器（弱分類器），然后把這些弱分類器集合起來，構成一個更強的最

終分類器(強分類器)。其算法本身是通過改變數(shù)據(jù)分布來

實現(xiàn)的，它根據(jù)每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的準確率，來確定每個樣本的權值。

將修改過權值的新數(shù)據(jù)集送給下層分類器進行訓練，最后

將每次訓練得到的分類器融合起來，作為最后的決策分類

器。使用Adaboost分類器可以排除一些不必要的訓練數(shù)據(jù)

特征，并將重點放在關鍵的訓練數(shù)據(jù)上。該算法其實是一個弱分類算法的提升過程，這個過程通過不斷的訓練，可以提高對數(shù)據(jù)的分類能力。簡單的例子來看看adaboost的實現(xiàn)過程：圖中，“+”和“-”分別表示兩種類別，在這個過程中，使用水平或者垂直的直線作為分類器，來進行分類。第一步：e1=0.3α1=0.37樣本權重的更新過程：分錯的3個樣本權重不變：都為0.1分對的7個樣本的權重更新為：0.1*（e1/(1-e1））=0.1*0.3/0.7=0.3/7最后規(guī)范化權重：3個分錯的樣本權重變?yōu)?/67個分對的樣本權重變?yōu)?/14根據(jù)分類的正確率，得到一個新的樣本分布D2，一個子分類器h1其中劃圈的樣本表示被分錯的。在右邊的圖中，比較大的“+”表示對該樣本做了

。第二步：根據(jù)分類的正確率，得到一個新的樣本分布D3，一個子分類器h2e2=0.21α2=0.58第三步：得到一個子分類器h3e3=0.14α3=0.79整合所有子分類器：因此可以得到整合