K_MEANS(K均值聚類(lèi)算法,C均值算法)

《K_MEANS(K均值聚類(lèi)算法,C均值算法)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、2.13.2Thek-MeansAlgorithm(K-均值聚類(lèi)算法）主講內(nèi)容算法性能分析算法改進(jìn)算法簡(jiǎn)介算法應(yīng)用算法要點(diǎn)算法描述算法實(shí)例ISODATA算法gapstatistics算法簡(jiǎn)介k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使用的聚類(lèi)算法。它是將各個(gè)聚類(lèi)子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類(lèi)的代表點(diǎn)，算法的主要思想是通過(guò)迭代過(guò)程把數(shù)據(jù)集劃分為不同的類(lèi)別，使得評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而使生成的每個(gè)聚類(lèi)內(nèi)緊湊，類(lèi)間獨(dú)立。這一算法不適合處理離散型屬性，但是對(duì)于連續(xù)型具有較好的聚類(lèi)效果。算法描述為中心向量c1

2、,c2,…,ck初始化k個(gè)種子分組:將樣本分配給距離其最近的中心向量由這些樣本構(gòu)造不相交（non-overlapping）的聚類(lèi)確定中心:用各個(gè)聚類(lèi)的中心向量作為新的中心重復(fù)分組和確定中心的步驟，直至算法收斂算法k-means算法輸入：簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出：k個(gè)簇，使平方誤差準(zhǔn)則最小。算法步驟：1.為每個(gè)聚類(lèi)確定一個(gè)初始聚類(lèi)中心，這樣就有K個(gè)初始聚類(lèi)中心。2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類(lèi)3.使用每個(gè)聚類(lèi)中的樣本均值作為新的聚類(lèi)中心。4.重復(fù)步驟2.3直到聚類(lèi)中心不再變化。5.結(jié)束，得到K個(gè)聚類(lèi)2021

3、/7/9將樣本分配給距離它們最近的中心向量，并使目標(biāo)函數(shù)值減小更新簇平均值計(jì)算準(zhǔn)則函數(shù)EK-means聚類(lèi)算法劃分聚類(lèi)方法對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)時(shí)包括如下三個(gè)要點(diǎn)：（1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量上面講到，k-means聚類(lèi)算法不適合處理離散型屬性，對(duì)連續(xù)型屬性比較適合。因此在計(jì)算數(shù)據(jù)樣本之間的距離時(shí)，可以根據(jù)實(shí)際需要選擇歐式距離、曼哈頓距離或者明考斯距離中的一種來(lái)作為算法的相似性度量，其中最常用的是歐式距離。下面我給大家具體介紹一下歐式距離。假設(shè)給定的數(shù)據(jù)集，X中的樣本用d個(gè)描述屬性A1,A2…Ad來(lái)表示，并且d個(gè)描述屬性都是連續(xù)

4、型屬性。數(shù)據(jù)樣本xi=(xi1,xi2,…xid),xj=(xj1,xj2,…xjd)其中，xi1,xi2,…xid和xj1,xj2,…xjd分別是樣本xi和xj對(duì)應(yīng)d個(gè)描述屬性A1,A2,…Ad的具體取值。樣本xi和xj之間的相似度通常用它們之間的距離d(xi,xj)來(lái)表示，距離越小，樣本xi和xj越相似，差異度越小；距離越大，樣本xi和xj越不相似，差異度越大。歐式距離公式如下：（2）選擇評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù)k-means聚類(lèi)算法使用誤差平方和準(zhǔn)則函數(shù)來(lái)評(píng)價(jià)聚類(lèi)性能。給定數(shù)據(jù)集X，其中只包含描述屬性，不包含類(lèi)別屬性。假設(shè)X包含k個(gè)聚

5、類(lèi)子集X1,X2,…XK；各個(gè)聚類(lèi)子集中的樣本數(shù)量分別為n1，n2,…,nk;各個(gè)聚類(lèi)子集的均值代表點(diǎn)（也稱聚類(lèi)中心）分別為m1，m2,…,mk。則誤差平方和準(zhǔn)則函數(shù)公式為：（3）相似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值來(lái)進(jìn)行。（1）將所有對(duì)象隨機(jī)分配到k個(gè)非空的簇中。（2）計(jì)算每個(gè)簇的平均值，并用該平均值代表相應(yīng)的簇。（3）根據(jù)每個(gè)對(duì)象與各個(gè)簇中心的距離，分配給最近的簇。（4）然后轉(zhuǎn)（2），重新計(jì)算每個(gè)簇的平均值。這個(gè)過(guò)程不斷重復(fù)直到滿足某個(gè)準(zhǔn)則函數(shù)才停止。Oxy10220031.50450552數(shù)據(jù)對(duì)象集合S見(jiàn)表1，作為一個(gè)聚類(lèi)分析的二維

6、樣本，要求的簇的數(shù)量k=2。(1)選擇，為初始的簇中心，即，。(2)對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。對(duì)：顯然，故將分配給例子對(duì)于：因?yàn)樗詫⒎峙浣o對(duì)于：因?yàn)樗詫⒎峙浣o更新，得到新簇和計(jì)算平方誤差準(zhǔn)則，單個(gè)方差為Oxy10220031.50450552，?？傮w平均方差是：（3）計(jì)算新的簇的中心。重復(fù)（2）和（3），得到O1分配給C1；O2分配給C2，O3分配給C2，O4分配給C2，O5分配給C1。更新，得到新簇和。中心為，。單個(gè)方差分別為總體平均誤差是：由上可以看出，第一次迭代后，總體平均誤差值52.25~2

7、5.65，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過(guò)程，算法停止。Oxy10220031.50450552k-means算法的性能分析主要優(yōu)點(diǎn)：是解決聚類(lèi)問(wèn)題的一種經(jīng)典算法，簡(jiǎn)單、快速。對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。因?yàn)樗膹?fù)雜度是0(nkt),其中,n是所有對(duì)象的數(shù)目,k是簇的數(shù)目,t是迭代的次數(shù)。通常k<

8、同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。K-Means算法對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。解決方法：1.多設(shè)置一些不同的初值，對(duì)比最后的運(yùn)算結(jié)果）一直到結(jié)果趨于穩(wěn)定結(jié)束，比較耗時(shí)和浪費(fèi)資源2.很