K-MEANS(K均值聚類算法-C均值算法)

算法(suànfǎ)簡(jiǎn)介

k-means算法，也被稱為k-平均或k-均值，是一種得到最廣泛使用的聚類算法。它是將各個(gè)聚類子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類的代表點(diǎn)，算法的主要思想是通過迭代過程把數(shù)據(jù)集劃分為不同的類別，使得(shǐde)評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而使生成的每個(gè)聚類內(nèi)緊湊，類間獨(dú)立。這一算法不適合處理離散型屬性，但是對(duì)于連續(xù)型具有較好的聚類效果。共二十一頁(yè)算法描述為中心向量c1,c2,…,ck初始化k個(gè)種子分組:將樣本分配給距離其最近的中心向量由這些樣本構(gòu)造不相交（non-overlapping

）的聚類確定中心:用各個(gè)聚類的中心向量作為(zuòwéi)新的中心重復(fù)分組和確定中心的步驟，直至算法收斂共二十一頁(yè)算法(suànfǎ)

k-means算法輸入：簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出：k個(gè)簇，使平方誤差準(zhǔn)則最小。算法步驟：1.為每個(gè)聚類確定一個(gè)初始聚類中心，這樣就有K個(gè)初始聚類中心。2.將樣本集中的樣本按照最小距離原則分配到最鄰近聚類

3.使用每個(gè)聚類中的樣本均值作為新的聚類中心。4.重復(fù)步驟2.3直到聚類中心不再變化。5.結(jié)束，得到K個(gè)聚類

共二十一頁(yè)2024/11/14將樣本分配給距離(jùlí)它們最近的中心向量，并使目標(biāo)函數(shù)值減小更新(gēngxīn)簇平均值計(jì)算準(zhǔn)則函數(shù)E共二十一頁(yè)K-means聚類算法(suànfǎ)共二十一頁(yè)

劃分聚類方法對(duì)數(shù)據(jù)集進(jìn)行聚類時(shí)包括如下三個(gè)要點(diǎn)：（1）選定某種距離作為數(shù)據(jù)樣本間的相似性度量(dùliàng)

上面講到，k-means聚類算法不適合處理離散型屬性，對(duì)連續(xù)型屬性比較適合。因此在計(jì)算數(shù)據(jù)樣本之間的距離時(shí)，可以根據(jù)實(shí)際需要選擇歐式距離、曼哈頓距離或者明考斯距離中的一種來(lái)作為算法的相似性度量，其中最常用的是歐式距離。下面我給大家具體介紹一下歐式距離。共二十一頁(yè)

假設(shè)(jiǎshè)給定的數(shù)據(jù)集，X中的樣本用d個(gè)描述屬性A1,A2…Ad來(lái)表示，并且d個(gè)描述屬性都是連續(xù)型屬性。數(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越相似，差異度越?。痪嚯x越大，樣本xi和xj越不相似，差異度越大。歐式距離公式如下：共二十一頁(yè)（2）選擇評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù)

k-means聚類算法(suànfǎ)使用誤差平方和準(zhǔn)則函數(shù)來(lái)評(píng)價(jià)聚類性能。給定數(shù)據(jù)集X，其中只包含描述屬性，不包含類別屬性。假設(shè)X包含k個(gè)聚類子集X1,X2,…XK；各個(gè)聚類子集中的樣本數(shù)量分別為n1，n2,…,nk;各個(gè)聚類子集的均值代表點(diǎn)（也稱聚類中心）分別為m1，m2,…,mk。則誤差平方和準(zhǔn)則函數(shù)公式為：共二十一頁(yè)

（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è)過程不斷重復(fù)直到滿足某個(gè)(mǒuɡè)準(zhǔn)則函數(shù)才停止。共二十一頁(yè)Oxy10220031.50450552數(shù)據(jù)對(duì)象集合S見表1，作為一個(gè)聚類分析的二維樣本，要求的簇的數(shù)量k=2。(1)選擇，為初始的簇中心，即，。(2)對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)(gègè)簇中心的距離，將它賦給最近的簇。對(duì)：

顯然(xiǎnrán)，故將分配給例子共二十一頁(yè)對(duì)于：因?yàn)樗詫⒎峙?fēnpèi)給對(duì)于：因?yàn)樗詫⒎峙浣o更新，得到新簇和計(jì)算平方誤差準(zhǔn)則，單個(gè)方差為Oxy10220031.50450552共二十一頁(yè)，?？傮w平均方差是：（3）計(jì)算(jìsuàn)新的簇的中心。重復(fù)（2）和（3），得到O1分配給C1；O2分配給C2，O3分配給C2

，O4分配給C2，O5分配給C1。更新(gēngxīn)，得到新簇和。中心為，。單個(gè)方差分別為總體平均誤差是：

由上可以看出，第一次迭代后，總體平均誤差值52.25~25.65，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過程，算法停止。

Oxy10220031.50450552共二十一頁(yè)k-means算法的性能(xìngnéng)分析主要優(yōu)點(diǎn)：是解決聚類問題的一種經(jīng)典算法，簡(jiǎn)單、快速。對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。因?yàn)樗膹?fù)雜度是0(nkt),其中,n是所有對(duì)象的數(shù)目,k是簇的數(shù)目,t是迭代的次數(shù)(cìshù)。通常k<<n且t<<n。當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí),它的效果較好。主要缺點(diǎn)在簇的平均值被定義的情況下才能使用，這對(duì)于處理符號(hào)屬性的數(shù)據(jù)不適用。必須事先給出k（要生成的簇的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。共二十一頁(yè)k-Prototype算法：可以對(duì)離散與數(shù)值屬性兩種混合的數(shù)據(jù)進(jìn)行聚類，在k-prototype中定義了一個(gè)對(duì)數(shù)值與離散屬性都計(jì)算的相異性度量標(biāo)準(zhǔn)。K-Prototype算法是結(jié)合K-Means與K-modes算法，針對(duì)混合屬性的，解決2個(gè)核心問題如下：1.度量具有混合屬性的方法是，數(shù)值屬性采用K-means方法得到P1，分類屬性采用K-modes方法P2，那么D=P1+a*P2，a是權(quán)重，如果覺得分類屬性重要(zhòngyào)，則增加a，否則減少a，a=0時(shí)即只有數(shù)值屬性2.更新一個(gè)簇的中心的方法，方法是結(jié)合K-Means與K-modes的更新方法。k-means算法的改進(jìn)(gǎijìn)方法——k-prototype算法共二十一頁(yè)k-中心點(diǎn)算法：k-means算法對(duì)于孤立點(diǎn)是敏感的。為了解決這個(gè)問題，不采用簇中的平均值作為參照點(diǎn)，可以(kěyǐ)選用簇中位置最中心的對(duì)象，即中心點(diǎn)作為參照點(diǎn)。這樣劃分方法仍然是基于最小化所有對(duì)象與其參照點(diǎn)之間的相異度之和的原則來(lái)執(zhí)行的。

k-means算法(suànfǎ)的改進(jìn)方法——k-中心點(diǎn)算法共二十一頁(yè)2024/11/14K-means算法在圖像分割上的簡(jiǎn)單(jiǎndān)應(yīng)用例1：圖片：一只遙望大海的小狗；此圖為100x100像素的JPG圖片，每個(gè)像素可以表示為三維向量（分別對(duì)應(yīng)JPEG圖像中的紅色、綠色和藍(lán)色通道(tōngdào)）

；將圖片分割為合適的背景區(qū)域（三個(gè)）和前景區(qū)域（小狗）；使用K-means算法對(duì)圖像進(jìn)行分割。共二十一頁(yè)2024/11/14在圖像分割上的簡(jiǎn)單(jiǎndān)應(yīng)用分割(fēngē)后的效果注：最大迭代次數(shù)為20次，需運(yùn)行多次才有可能得到較好的效果。共二十一頁(yè)2024/11/14在圖像(túxiànɡ)分割上的簡(jiǎn)單應(yīng)用例2：注：聚類中心(zhōngxīn)個(gè)數(shù)為5，最大迭代次數(shù)為10。共二十一頁(yè)共二十一頁(yè)共二十一頁(yè)內(nèi)容(nèiróng)總結(jié)算法簡(jiǎn)介。2.將樣本集中的樣本