內(nèi)容講義教案_第1頁
內(nèi)容講義教案_第2頁
內(nèi)容講義教案_第3頁
內(nèi)容講義教案_第4頁
內(nèi)容講義教案_第5頁
已閱讀5頁,還剩27頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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.

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論