K-MEANS算法(K均值算法).doc

《K-MEANS算法(K均值算法).doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、k-means算法一．算法簡介k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使用的聚類算法。它是將各個聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點，算法的主要思想是通過迭代過程把數(shù)據(jù)集劃分為不同的類別，使得評價聚類性能的準則函數(shù)達到最優(yōu)，從而使生成的每個聚類內(nèi)緊湊，類間獨立。這一算法不適合處理離散型屬性，但是對于連續(xù)型具有較好的聚類效果。二．劃分聚類方法對數(shù)據(jù)集進行聚類時包括如下三個要點：（1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量k-means聚類算法不適合處理離散型屬性，對連續(xù)型屬性比較適合。因此在計算數(shù)據(jù)樣本之間的距離時，可以根據(jù)實際需要選擇歐式距離、曼哈頓距

2、離或者明考斯距離中的一種來作為算法的相似性度量，其中最常用的是歐式距離。下面我給大家具體介紹一下歐式距離。假設(shè)給定的數(shù)據(jù)集，X中的樣本用d個描述屬性A1,A2…Ad來表示，并且d個描述屬性都是連續(xù)型屬性。數(shù)據(jù)樣本xi=(xi1,xi2,…xid),xj=(xj1,xj2,…xjd)其中，xi1,xi2,…xid和xj1,xj2,…xjd分別是樣本xi和xj對應(yīng)d個描述屬性A1,A2,…Ad的具體取值。樣本xi和xj之間的相似度通常用它們之間的距離d(xi,xj)來表示，距離越小，樣本xi和xj越相似，差異度越??；距離越大，樣本xi和xj越不相似，差異度越大。歐式距離公式如下：（2）選擇評

3、價聚類性能的準則函數(shù)k-means聚類算法使用誤差平方和準則函數(shù)來評價聚類性能。給定數(shù)據(jù)集X，其中只包含描述屬性，不包含類別屬性。假設(shè)X包含k個聚類子集X1,X2,…XK；各個聚類子集中的樣本數(shù)量分別為n1，n2,…,nk;各個聚類子集的均值代表點（也稱聚類中心）分別為m1，m2,…,mk。則誤差平方和準則函數(shù)公式為：（3）相似度的計算根據(jù)一個簇中對象的平均值來進行。1)將所有對象隨機分配到k個非空的簇中。2)計算每個簇的平均值，并用該平均值代表相應(yīng)的簇。3)根據(jù)每個對象與各個簇中心的距離，分配給最近的簇。4)然后轉(zhuǎn)2），重新計算每個簇的平均值。這個過程不斷重復直到滿足某個準則函數(shù)才停止

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

5、220031.50450552五．算法舉例數(shù)據(jù)對象集合S見表1，作為一個聚類分析的二維樣本，要求的簇的數(shù)量k=2。(1)選擇，為初始的簇中心，即，(2)對剩余的每個對象，根據(jù)其與各個簇中心的距離，將它賦給最近的簇。對：顯然，故將分配給對于：因為，所以將分配給對于：因為，所以將分配給更新，得到新簇和計算平方誤差準則，單個方差為總體平均方差是：（3）計算新的簇的中心。重復（2）和（3），得到O1分配給C1；O2分配給C2，O3分配給C2，O4分配給C2，O5分配給C1。更新，得到新簇和。中心為，。單個方差分別為總體平均誤差是：由上可以看出，第一次迭代后，總體平均誤差值52.25~25.65，

6、顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。六．k-means算法的性能分析6.1k-means算法的優(yōu)缺點主要優(yōu)點：1.是解決聚類問題的一種經(jīng)典算法，簡單、快速。2.對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。因為它的復雜度是0(nkt),其中,n是所有對象的數(shù)目,k是簇的數(shù)目,t是迭代的次數(shù)。通常k<

7、躁聲”和孤立點數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。針對K-Means算法對于不同的初始值，可能會導致不同結(jié)果。解決方法：1.多設(shè)置一些不同的初值，對比最后的運算結(jié)果）一直到結(jié)果趨于穩(wěn)定結(jié)束，比較耗時和浪費資源2.很多時候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個類別才最合適。這也是K-means算法的一個不足。有的算法是通過類的自動合并和分裂，得到較為合理的類型數(shù)目K，例如ISODATA算法。3.所謂的gapsta