內(nèi)容講義教案

1、K均值算法（十大經(jīng)典算法之一）K中心點(diǎn)算法Adaboost算法（十大經(jīng)典算法之一）7.4劃分方法K均值算法K中心點(diǎn)算法劃分方法給定n個(gè)對象的數(shù)據(jù)集D,以及要生成的簇的數(shù)目k,劃分算法將對象組織為k個(gè)劃分（kn）,每個(gè)劃分代表一個(gè)簇。這些簇的形成旨在優(yōu)化一個(gè)目標(biāo)劃分準(zhǔn)則，如基于距離的相異度函數(shù)，使得根據(jù)數(shù)據(jù)集的屬性，在同一個(gè)簇中的對象是“相似的”，而不同的簇中的對象是“相異的”。第一種劃分方法k均值（k-means）K均值算法以K（一般是用戶指定的）為輸入?yún)?shù)，把n個(gè)對象的集合分為K個(gè)簇，使得結(jié)果簇內(nèi)對象的相似度高，簇間對象的相似度低。算法聚類流程：首先，隨機(jī)地選擇k個(gè)對象，每個(gè)對象代表一個(gè)初始

2、簇中心。對剩余的每個(gè)對象，根據(jù)其與各個(gè)簇中心的距離，將它指派到距離最近的簇。然后計(jì)算每個(gè)簇的新均值。這個(gè)過程不斷重復(fù)，直到簇中心點(diǎn)不再發(fā)生變化。第一次聚類結(jié)果K=2將剩余對象指派到離它最近的簇任選兩個(gè)初始簇中心初始數(shù)據(jù)集更新聚類中心第二次聚類結(jié)果將剩余對象指派到最近的簇更新聚類中心第三次聚類結(jié)果更新簇中心，直到所有的簇中心不發(fā)生變化重新指派對象到距離最近的簇K均值過程概述輸入：k:簇的數(shù)目，D:包含n個(gè)對象的數(shù)目集。輸出：k個(gè)簇的集合。方法：(1) 從D中任意選擇k個(gè)對象作為初始簇中心；(2) Repeat(3)根據(jù)簇中對象的均值，將每個(gè)對象指派到最相似的簇;(4) 更新簇均值，即計(jì)算每個(gè)簇中

3、對象的均值;(5) Until每個(gè)簇的中心不再發(fā)生變化舉例：將數(shù)據(jù)對象集合s分為兩個(gè)簇，即 k=2YS：O5(5，2)O1(0，2)XO2(0，0)O (5,0)O3(1.5,0)4xyO102O200O31.50O450O552(1) 隨機(jī)選擇兩個(gè)初始簇中心。M1=O1=(0,2) M2=O2=(0,0)，對應(yīng)的簇為C1，C2(2)對剩余的每個(gè)對象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。對O3：d(M1,O3：d(M1,O4：d(M1,O5d(M2,O3 )=1.5 ， 將O3 加入簇C2。)=2.5對O4d(M2,O4 )=5 ， 將O4 加入簇C2。)= 5.38對O5d(M2,O

4、5 )=5.38 ， 將O5 加入簇C1。)= 5更新，得到兩個(gè)簇C1=O1，O5和C2=O2，O3，O4(3) 計(jì)算新的簇的中心。（簇中心不一定是集合中的點(diǎn)）M1=(2.5,2)重復(fù)(2) 和(3)M2=(2.17,0)對O1：d(M1,O1：d(M1,O2：d(M1,O3：d(M1,O4：d(M1,O5d(M2,O1 )=4.72 ， 將O1 加入簇C1。)= 2.5對O2d(M2,O2 )=2.17 ， 將O2 加入簇C2。)= 3.2對O3d(M2,O3 )=0.67 ， 將O3 加入簇C2。)=2.24對O4d(M2,O4 )=2.83 ， 將O4 加入簇C2。)= 3.2對O5d(

5、M2,O5 )=3.47 ， 將O5 加入簇C1。)= 2.5由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。聚類結(jié)果：C1=O1，O5和 C2=O2，O3，O4提醒：當(dāng)選擇O2和O5為初始簇中心點(diǎn)時(shí)聚類結(jié)果是C1=O1，O2，O3和C2=O4，O5優(yōu)點(diǎn)：（1）簡單易行；（2）時(shí)間復(fù)雜度接近線性；（3）對大數(shù)據(jù)集，是可伸縮和高效率的。缺點(diǎn)：最終的結(jié)果會(huì)隨初始中心的變化而變化；算法依賴于用戶指定的k值，不合適的 k 可能返回較差的結(jié)果；（3）對離群點(diǎn)是敏感的。第二種劃分方法k中心點(diǎn)K均值算法對于離群點(diǎn)是敏感的，因?yàn)橐粋€(gè)具有很大的值的對象可能顯著地?cái)?shù)據(jù)的分布。平方誤差的使用更是嚴(yán)重了這一

6、影響?！叭绾涡薷倪@個(gè)算法來降低這種敏感性？”可以不采用簇中對象的均值作為參考點(diǎn)，而是在每個(gè)簇中選出一個(gè)實(shí)際的對象來代表該簇。其余的每個(gè)對象聚類到與其最相似的代表性對象所在的簇中。這樣，劃分依然基于最小化所有對象與其對應(yīng)的參考點(diǎn)之間的相異度之和的原則來執(zhí)行。算法聚類流程：首先隨意選擇初始代表對象。只要能提高結(jié)果聚類質(zhì)量，迭代過程就繼續(xù)用非代表對象替換代表對象。聚類結(jié)果的質(zhì)量用代價(jià)函數(shù)來評估，該函數(shù)度量對象與其簇的代表對象之間的平均相異度。為了確定非代表對象Orandom是否是當(dāng)前代表對象Oj的好的替代，對于每一個(gè)非代表對象p，考慮如下4種情況。第一種情況：p當(dāng)前隸屬于代表對象Oj。如果Oj被Or

7、andom所代替作為代表對象，且p離其他代表對象Oi(ij)最近，則p重新分配給Oi。第二種情況：p當(dāng)前隸屬于代表對象Oj。如果Oj被Orandom代替作為代表對象，且p離Orandom最近，則p被重新分配給Orandom。第三種情況：p當(dāng)前隸屬于中心點(diǎn)Oi，ij。如果Oj被Orandom代替作為代表對象，而p依然離Oi最近，則對象的隸屬不發(fā)生變化。第四種情況：p當(dāng)前隸屬于中心點(diǎn)Oi，ij。如果Oj被Orandom代替作為代表對象，且p離Orandom最近，那么p被重新分配給Orandom。第四種情況mp 被重新分配給Orandom代價(jià) = d (Orandom, p)-d (Oi, p)Oi

8、OjpOrando第三種情況mp 的隸屬不發(fā)生變化代價(jià) = 0OiOjpOrando第二種情況mp 被重新分配給Orandom代價(jià) = d (Orandom , p)-d (Oj , p)OiOjpOrando第一種情況mp 被重新分配給Oi代價(jià) = d (Oi, p)-d (Oj, p)OiOjpOrandoK中心點(diǎn)算法隨機(jī)選擇 k個(gè)對象作為初始中心點(diǎn)將剩余對象指定到離中心點(diǎn)最近的簇中K=2隨機(jī)選擇一個(gè)非中心對象Oramdom如果聚類質(zhì)量提高，用 Oramdom替換O計(jì)算總的替換代價(jià)17循環(huán)直到代價(jià)不再減小為止1098765432100123456789 101098765432100123

9、456789 10109876543210012345678910109876543210012345678910109876543210012345678910每當(dāng)重新分配發(fā)生時(shí)，絕對誤差 E 的差對代價(jià)函數(shù)有影響。因此，如果當(dāng)前的代表對象被非代表對象所取代，代價(jià)函數(shù)就計(jì)算絕對誤差值的差。交換的總代價(jià)是所有非代表對象所產(chǎn)生的代價(jià)之和。如果總代價(jià)是負(fù)的，實(shí)際絕對誤差將會(huì)減小，Oj可以被Orandom替代。如果總代價(jià)是正的，則當(dāng)前的代表對象Oj是可接受的，在本次迭代中沒有變化發(fā)生。算法5-2 PAM（k-中心點(diǎn)算法）輸入：簇的數(shù)目k和包含n個(gè)對象的數(shù)據(jù)庫。輸出：k個(gè)簇，使得所有對象與其最近中心點(diǎn)

10、的相異度總和最小。任意選擇k個(gè)對象作為初始的簇中心點(diǎn)；REPEAT指派每個(gè)剩余的對象給離它最近的中心點(diǎn)所代表的簇；（4）（5）（6）（7）（8）（9）（10）REPEAT選擇一個(gè)未被選擇的代表Oi；REPEAT選擇一個(gè)未被選擇過的代表對象Orandom；計(jì)算用Orandom代替Oi的總代價(jià)并UNTIL 所有的非代表都被選擇過；在S中；UNTIL 所有的代表對象都被選擇過；IF 在S中的所有非代表對象代替所有代表對象后計(jì)算出的總代（11）價(jià)有小于0的存在 THEN 找出S中的用非代表對象替代代表對象后代價(jià)最小的一個(gè)，并用該非代表對象替代對應(yīng)的代表對象，形成一個(gè)新的k對象的集合；（12）UNTIL

11、 沒有再發(fā)生簇的重新分配，即所有的S都大于0.假如空間中的五個(gè)點(diǎn)A、如圖1所示，各點(diǎn)之間的距離關(guān)系如表1所示，根據(jù)所給的數(shù)據(jù)對其運(yùn)行PAM算法實(shí)現(xiàn)劃分聚類（設(shè)k=2）。 樣本點(diǎn)間距離如下表所示:起始中心點(diǎn)為CC2AA樣本點(diǎn)D2DBB3EE第一步 建立階段：假如從5個(gè)對象中隨機(jī)抽取的2個(gè)中心點(diǎn)為A，B,則樣本被劃分為A、C、D和B、E，如圖5-3所示。第二步交換階段：假定中心點(diǎn)A、B分別被非中心點(diǎn)C、D、E替換，根據(jù)PAM算法需要計(jì)算下列代價(jià)TCAC、 TCAD、 TCAE、TCBC、TCBD、 TCBE。以TCAC為例說明計(jì)算過程：a)當(dāng)A被C替換以后，A不再是一個(gè)中心點(diǎn)，因?yàn)锳離B比A離C近

12、，A被分配到B中心點(diǎn)代表的簇，CAAC=d(A,B)-d(A,A)=1。B是一個(gè)中心點(diǎn)，當(dāng)A被C替換以后，B不受影響，CBAC=0。C原先屬于A中心點(diǎn)所在的簇，當(dāng)A被C替換以后，C是新中心點(diǎn)，符合PAM算法代價(jià)函數(shù)的第二種情況CCAC=d(C,C)-d(C,A)=0-2=-2。D原先屬于A中心點(diǎn)所在的簇，當(dāng)A被C替換以后，離D最近的中心點(diǎn)是C，根據(jù)PAM算法代價(jià)函數(shù)的第二種情況CDAC=d(D,C)-d(D,A)=1-2=-1。E原先屬于B中心點(diǎn)所在的簇，當(dāng)A被C替換以后，離E最近的中心仍然是 B，根據(jù)PAM算法代價(jià)函數(shù)的第三種情況CEAC=0。b)c)d)e)因此，TCAC=CAAC+ CB

13、AC+ CBAC+ CDAC+ CEAC=1+0-2-1+0=-2。A,B樣本點(diǎn)ABCDEA01223B10243C22015D24103E33530在上述代價(jià)計(jì)算完畢后，要選取一個(gè)最小的代價(jià)，顯然有多種替換可以選擇，選 擇第一個(gè)最小代價(jià)的替換（也就是C替換A），根據(jù)圖5-4（a）所示，樣本點(diǎn)被劃分為 B、A、E和C、D兩個(gè)簇。圖5-4（b）和圖5-4（c）分別表示了D替換A，E替換A的情況和相應(yīng)的代價(jià)CCCAAA112111DDDBBB333EE(a)C替換A,TCAC=-2(b) D替換A, TCAD=-2(c) E替換A,TCAE=-1圖5-4替換中心點(diǎn)A圖5-5（a）、（b）、（c）分

14、別表示了用C、D、E替換B的情況和相應(yīng)的代價(jià)。CCCA2AA11111D2DBBB33EEC替換B, TCBC=-2(b) D替換B, TCBD=-2圖5-5 替換中心點(diǎn)B(c) E替換B, TCBE=-2通過上述計(jì)算，已經(jīng)完成了PAM算法的第一次迭代。在下一迭代中，將用其他的非中心點(diǎn)A、D、E替換中心點(diǎn)B、C，找出具有最小代價(jià)的替換。一直重復(fù)上述過程，直到代價(jià)不再減小為止。DEEK中心點(diǎn)算法的特點(diǎn)：（1）當(dāng)存在噪聲和離群點(diǎn)時(shí)，K中心點(diǎn)方法比K均值更健壯，因?yàn)橹行狞c(diǎn)不像均值那樣容易受離群點(diǎn)或其他值的影響。（2）K中心點(diǎn)方法的執(zhí)行代價(jià)比K均值算法高。（3）兩種方法都要指定簇的個(gè)數(shù)K.AdaBoo

15、st算法AdaBoostAdaboost是adaptive boost的縮寫，它是一種迭代算法。其是針對同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器（弱分類器），然后把這些弱分類器集合起來，一個(gè)更強(qiáng)的最終分類器 (強(qiáng)分類器)。其算法本身是通過改變數(shù)據(jù)分布來實(shí)現(xiàn)的，它根據(jù)每次訓(xùn)練集之中每個(gè)樣本的分類是否正確，以及上次的總體分類的準(zhǔn)確率，來確定每個(gè)樣本的權(quán)值。 將修改過權(quán)值的新數(shù)據(jù)集送給下層分類器進(jìn)行訓(xùn)練，最后 將每次訓(xùn)練得到的分類器融合起來，作為最后的決策分類 器。使用Adaboost分類器可以排除一些不必要的訓(xùn)練數(shù)據(jù)特征，并將重點(diǎn)放在關(guān)鍵的訓(xùn)練數(shù)據(jù)上。該算法其實(shí)是一個(gè)弱分類算法的過程，這個(gè)過程通過不斷的訓(xùn)練，

16、可以提高對數(shù)據(jù)的分類能力。簡單的例子來看看adaboost的實(shí)現(xiàn)過程：圖中，“+”和“-”分別表示兩種類別，在這個(gè)過程中，使用水平或者垂直的直線作為分類器，來進(jìn)行分類。第一步：e1=0.3 1=0.37樣本權(quán)重的更新過程：分錯(cuò)的3個(gè)樣本權(quán)重不變 ：都為 0.1分對的7個(gè)樣本的權(quán)重更新為：0.1*（e1/(1-e1）=0.1*0.3/0.7=0.3/7最后規(guī)范化權(quán)重：3個(gè)分錯(cuò)的樣本權(quán)重變?yōu)?1/67個(gè)分對的樣本權(quán)重變?yōu)?1/14根據(jù)分類的正確率，得到一個(gè)新的樣本分布D2，一個(gè)子分類器h1其中劃圈的樣本表示被分錯(cuò)的。在右邊的圖中，比較大的“+”表示對該樣本做了。第二步：e2=0.21 2=0.58

17、根據(jù)分類的正確率，得到一個(gè)新的樣本分布D3，一個(gè)子分類器h2第三步：e3=0.14 3=0.79得到一個(gè)子分類器h3整合所有子分類器：0.370.580.79因此可以得到整合的結(jié)果，從結(jié)果中看，即使簡單的分類器，組合起來也能獲得很好的分類效果。D舉例：D是10個(gè)元組的訓(xùn)練集將每個(gè)元組的權(quán)重初始化為0.1根據(jù)元組的權(quán)重有放回的抽樣10次，得到D1.使用訓(xùn)練集導(dǎo)出模型M1.計(jì)算M1誤差率e(M1)=0.1*1+0.1*1+0+.=0.2分類器M1的表決權(quán)重D1(特殊情況，每個(gè)元組抽到一次)log 1 e(M1 ) log 0.8 0.6e(M1 )0.2(6) 更新正確分類元組的權(quán)重原元組的權(quán)重* e(M1) / (1-e(M1)8個(gè)正確分類的元組的權(quán)重更新為0.1*0.2/0.