K-means數(shù)學(xué)建模

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

2、較法不適合處理離散型屬性，但是對(duì)于連續(xù)型具有較好的聚類(lèi)效果好的聚類(lèi)效果。 劃分聚類(lèi)方法對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)時(shí)包括如下劃分聚類(lèi)方法對(duì)數(shù)據(jù)集進(jìn)行聚類(lèi)時(shí)包括如下 三個(gè)要點(diǎn)：三個(gè)要點(diǎn)：v （1 1）選定某種距離作為數(shù)據(jù)樣本間的相似性度）選定某種距離作為數(shù)據(jù)樣本間的相似性度量量 上面講到，上面講到，k-meansk-means聚類(lèi)算法不適合處理離散型聚類(lèi)算法不適合處理離散型 屬性，對(duì)連續(xù)型屬性比較適合。因此在計(jì)算數(shù)據(jù)樣屬性，對(duì)連續(xù)型屬性比較適合。因此在計(jì)算數(shù)據(jù)樣本之間的距離時(shí)，可以根據(jù)實(shí)際需要選擇歐式距離、本之間的距離時(shí)，可以根據(jù)實(shí)際需要選擇歐式距離、曼哈頓距離或者明考斯距離中的一種來(lái)作為算法的曼哈頓距離或

3、者明考斯距離中的一種來(lái)作為算法的相似性度量，其中最常用的是歐式距離。下面我給相似性度量，其中最常用的是歐式距離。下面我給大家具體介紹一下歐式距離。大家具體介紹一下歐式距離。 假設(shè)給定的數(shù)據(jù)集假設(shè)給定的數(shù)據(jù)集 ，X X中中的樣本用的樣本用d d個(gè)描述屬性個(gè)描述屬性A A1 1,A,A2 2AAd d來(lái)表示，并且來(lái)表示，并且d d個(gè)描個(gè)描述屬性都是連續(xù)型屬性。數(shù)據(jù)樣本述屬性都是連續(xù)型屬性。數(shù)據(jù)樣本x xi i=(x=(xi1i1,x,xi2i2,x,xidid), x), xj j=(x=(xj1j1,x,xj2j2,x,xjdjd) )其中，其中， x xi1i1,x,xi2i2,x,xidid

4、和和x xj1j1,x,xj2j2,x,xjdjd分別是樣本分別是樣本x xi i和和x xj j對(duì)應(yīng)對(duì)應(yīng)d d個(gè)描述屬性個(gè)描述屬性A A1 1,A,A2 2,A,Ad d的具體取值。樣本的具體取值。樣本xixi和和xjxj之之間的相似度通常用它們之間的距離間的相似度通常用它們之間的距離d(xd(xi i,x,xj j) )來(lái)表示，來(lái)表示，距離越小，樣本距離越小，樣本x xi i和和x xj j越相似，差異度越小；距離越相似，差異度越??；距離越大，樣本越大，樣本x xi i和和x xj j越不相似，差異度越大。越不相似，差異度越大。 歐式距離公式如下：歐式距離公式如下：dkjkikjixxxx

5、d12,totalmxXm,.,2 , 1|v（2 2）選擇評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù)）選擇評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù) k-meansk-means聚類(lèi)算法使用誤差平方和準(zhǔn)則函數(shù)來(lái)聚類(lèi)算法使用誤差平方和準(zhǔn)則函數(shù)來(lái) 評(píng)價(jià)聚類(lèi)性能。給定數(shù)據(jù)集評(píng)價(jià)聚類(lèi)性能。給定數(shù)據(jù)集X X，其中只包含描述屬，其中只包含描述屬性，不包含類(lèi)別屬性。假設(shè)性，不包含類(lèi)別屬性。假設(shè)X X包含包含k k個(gè)聚類(lèi)子集個(gè)聚類(lèi)子集X X1 1,X,X2 2,X,XK K；各個(gè)聚類(lèi)子集中的樣本數(shù)量分別為；各個(gè)聚類(lèi)子集中的樣本數(shù)量分別為n n1 1，n n2 2,n,nk k; ;各個(gè)聚類(lèi)子集的均值代表點(diǎn)（也稱(chēng)聚類(lèi)中各個(gè)聚類(lèi)子集的均值代表點(diǎn)（也稱(chēng)

6、聚類(lèi)中心）分別為心）分別為m m1 1，m m2 2,m,mk k。則誤差平方和準(zhǔn)則函數(shù)。則誤差平方和準(zhǔn)則函數(shù)公式為：公式為：21 kiXpiimpEv （3）相似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值相似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值 來(lái)進(jìn)行。來(lái)進(jìn)行。v（1 1）將所有對(duì)象隨機(jī)分配到）將所有對(duì)象隨機(jī)分配到k k個(gè)非空的簇中。個(gè)非空的簇中。v（2 2）計(jì)算每個(gè)簇的平均值，并用該平均值代表相）計(jì)算每個(gè)簇的平均值，并用該平均值代表相應(yīng)的簇。應(yīng)的簇。v（3 3）根據(jù)每個(gè)對(duì)象與各個(gè)簇中心的距離，分配給）根據(jù)每個(gè)對(duì)象與各個(gè)簇中心的距離，分配給最近的簇。最近的簇。v（4 4）然后轉(zhuǎn)（）然后轉(zhuǎn)（2 2），重新計(jì)

7、算每個(gè)簇的平均值。），重新計(jì)算每個(gè)簇的平均值。這個(gè)過(guò)程不斷重復(fù)直到滿(mǎn)足某個(gè)準(zhǔn)則函數(shù)才停止。這個(gè)過(guò)程不斷重復(fù)直到滿(mǎn)足某個(gè)準(zhǔn)則函數(shù)才停止。K-均值聚類(lèi)示例均值聚類(lèi)示例輸入輸入: 簇的數(shù)目簇的數(shù)目k 和包含和包含n 個(gè)對(duì)象的數(shù)據(jù)庫(kù)。個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出輸出: k 個(gè)簇個(gè)簇, 使平方誤差準(zhǔn)則最小。使平方誤差準(zhǔn)則最小。方法：基于簇中對(duì)象的平均值。方法：基于簇中對(duì)象的平均值。( l) 任意選擇任意選擇k 個(gè)對(duì)象作為初始的簇中心個(gè)對(duì)象作為初始的簇中心;(2 ) r e p e a t ,(3 ) 根據(jù)簇中對(duì)象的平均值根據(jù)簇中對(duì)象的平均值, 將每個(gè)對(duì)象將每個(gè)對(duì)象(重新重新) 賦給最賦給最類(lèi)似的簇類(lèi)似的簇:(4

8、 ) 更新簇的平均值更新簇的平均值, 即計(jì)算每個(gè)簇中對(duì)象的平均值即計(jì)算每個(gè)簇中對(duì)象的平均值;(5) u n t i l 不再發(fā)生變化。不再發(fā)生變化。K-means算法算法2個(gè)核心問(wèn)題：個(gè)核心問(wèn)題：1.度量記錄之間的相關(guān)性的計(jì)算公式，此處采用歐式距離。度量記錄之間的相關(guān)性的計(jì)算公式，此處采用歐式距離。2.更新簇內(nèi)質(zhì)心的方法，此處采用平均值法，即更新簇內(nèi)質(zhì)心的方法，此處采用平均值法，即means。算法算法 k-means算法算法輸入：簇的數(shù)目輸入：簇的數(shù)目k和包含和包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)。個(gè)對(duì)象的數(shù)據(jù)庫(kù)。輸出：輸出：k個(gè)簇，使平方誤差準(zhǔn)則最小。個(gè)簇，使平方誤差準(zhǔn)則最小。（1)assign initi

9、al value for means; /*任意分配到任意分配到k個(gè)對(duì)象作為簇的平均值個(gè)對(duì)象作為簇的平均值*/ (2) REPEAT (3) FOR j=1 to n DO assign each xj to the closest clusters; (4) FOR i=1 to k DO / *更新簇平均值更新簇平均值*/ (5) Compute /*計(jì)算準(zhǔn)則函數(shù)計(jì)算準(zhǔn)則函數(shù)E*/ (6) UNTIL E不再明顯地發(fā)生變化。不再明顯地發(fā)生變化。21 kiCxiixxEiCxiixCx1Oxy10220031.50450552數(shù)據(jù)對(duì)象集合數(shù)據(jù)對(duì)象集合S見(jiàn)表見(jiàn)表1，作為一個(gè)聚類(lèi)分析的二維，作為

10、一個(gè)聚類(lèi)分析的二維樣本，要求的簇的數(shù)量樣本，要求的簇的數(shù)量k=2。(1)選擇選擇 ， 為初始的簇中心，為初始的簇中心，即即 ， 。(2)對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。離，將它賦給最近的簇。 對(duì)對(duì) ： 顯然顯然 ，故將，故將 分配給分配給 ；同理，將；同理，將 分配分配給給 ， 分配給分配給 。更新，得到新簇更新，得到新簇 和和計(jì)算平方誤差準(zhǔn)則，單個(gè)方差為計(jì)算平方誤差準(zhǔn)則，單個(gè)方差為2 , 01O0 , 02O2 , 011OM0 , 022OM5 . 2025 . 10,2231OMd5 . 1005 . 10,2232O

11、Md3132,OMdOMd3O3O2C4O2C4O1C511,OOC 511,OOC 252250220022221E25.272E例子例子，?？傮w平均方差是：總體平均方差是：（3）計(jì)算新的簇的中心。）計(jì)算新的簇的中心。 25.5225.272521EEE 2 , 5 . 2222, 2501M0 ,17. 23000, 355 . 102M重復(fù)（重復(fù)（2）和（）和（3），得到），得到O1分配給分配給C1；O2分配給分配給C2，O3分配分配給給C2 ，O4分配給分配給C2，O5分配給分配給C1。更新，得到新簇。更新，得到新簇和和 。 中心為中心為 ， 。顯影的單個(gè)方差分別為顯影的單個(gè)方差分別為

12、511,OOC 4322,OOOC 2 , 5 . 21M0 ,17. 22M5 .122255 . 2225 . 2022221E15.132E總體平均誤差是：總體平均誤差是： 65.2515.135 .1221EEE由上可以看出，第一次迭代后，總體平均誤差值由上可以看出，第一次迭代后，總體平均誤差值52.2525.65，顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過(guò)程顯著減小。由于在兩次迭代中，簇中心不變，所以停止迭代過(guò)程，算法停止算法停止。 k k-means-means算法的性能分析算法的性能分析n主要優(yōu)點(diǎn)：主要優(yōu)點(diǎn)：u是解決聚類(lèi)問(wèn)題的一種經(jīng)典算法，簡(jiǎn)單、快速。是解決聚類(lèi)問(wèn)題的

13、一種經(jīng)典算法，簡(jiǎn)單、快速。u對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。對(duì)處理大數(shù)據(jù)集，該算法是相對(duì)可伸縮和高效率的。因?yàn)樗膹?fù)雜度因?yàn)樗膹?fù)雜度是是0 (n k t ) , 其中其中, n 是所有對(duì)象的數(shù)目是所有對(duì)象的數(shù)目, k 是簇的數(shù)目是簇的數(shù)目, t 是迭代的次數(shù)。是迭代的次數(shù)。通常通常k n 且且t n 。u當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí)當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí), , 它的效果較好。它的效果較好。n主要缺點(diǎn)主要缺點(diǎn)u在簇的平均值被定義的情況下才能使用，在簇的平均值被定義的情況下才能使用，這對(duì)于處理符號(hào)屬性的數(shù)據(jù)這對(duì)于處理符號(hào)屬性的數(shù)據(jù)不適用。不適用。u必須

14、事先給出必須事先給出k k（要生成的簇的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的（要生成的簇的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。初始值，可能會(huì)導(dǎo)致不同結(jié)果。u它對(duì)于它對(duì)于“躁聲躁聲”和孤立點(diǎn)數(shù)據(jù)是敏感的，和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類(lèi)數(shù)據(jù)能夠?qū)ζ骄倭康脑擃?lèi)數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。值產(chǎn)生極大的影響。uk-modes 算法：實(shí)現(xiàn)對(duì)離散數(shù)據(jù)的快速聚類(lèi)，保留了算法：實(shí)現(xiàn)對(duì)離散數(shù)據(jù)的快速聚類(lèi)，保留了k-means算法的效率同時(shí)將算法的效率同時(shí)將k-means的應(yīng)用范圍擴(kuò)大到離散數(shù)據(jù)。的應(yīng)用范圍擴(kuò)大到離散數(shù)據(jù)。uK-modes算法是按照算法是按照k-means算法的核心內(nèi)

15、容進(jìn)行修改，針?biāo)惴ǖ暮诵膬?nèi)容進(jìn)行修改，針對(duì)分類(lèi)屬性的度量和更新質(zhì)心的問(wèn)題而改進(jìn)。對(duì)分類(lèi)屬性的度量和更新質(zhì)心的問(wèn)題而改進(jìn)。具體如下具體如下:1.度量記錄之間的相關(guān)性度量記錄之間的相關(guān)性D的計(jì)算公式是比較兩記錄之間，屬的計(jì)算公式是比較兩記錄之間，屬性相同為性相同為0，不同為，不同為1.并所有相加。因此并所有相加。因此D越大，即他的不相關(guān)越大，即他的不相關(guān)程度越強(qiáng)（與歐式距離代表的意義是一樣的）；程度越強(qiáng)（與歐式距離代表的意義是一樣的）；2.更新更新modes，使用一個(gè)簇的每個(gè)屬性出現(xiàn)頻率最大的那個(gè)屬，使用一個(gè)簇的每個(gè)屬性出現(xiàn)頻率最大的那個(gè)屬性值作為代表簇的屬性值。性值作為代表簇的屬性值。k-mea

16、nsk-means算法的改進(jìn)方法算法的改進(jìn)方法k-mode k-mode 算法算法uk-Prototype算法：可以對(duì)離散與數(shù)值屬性?xún)煞N混合的數(shù)據(jù)算法：可以對(duì)離散與數(shù)值屬性?xún)煞N混合的數(shù)據(jù)進(jìn)行聚類(lèi)，在進(jìn)行聚類(lèi)，在k-prototype中定義了一個(gè)對(duì)數(shù)值與離散屬性都中定義了一個(gè)對(duì)數(shù)值與離散屬性都計(jì)算的相異性度量標(biāo)準(zhǔn)。計(jì)算的相異性度量標(biāo)準(zhǔn)。uK-Prototype算法是結(jié)合算法是結(jié)合K-Means與與K-modes算法，針對(duì)算法，針對(duì)混合屬性的，解決混合屬性的，解決2個(gè)核心問(wèn)題如下：個(gè)核心問(wèn)題如下：1.度量具有混合屬性的方法是，數(shù)值屬性采用度量具有混合屬性的方法是，數(shù)值屬性采用K-means方法方法得到得到P1，分類(lèi)屬性采用，分類(lèi)屬性采用K-modes方法方法P2，那么，那么D=P1+a*P2，a是權(quán)重，如果覺(jué)得分類(lèi)屬性重要，則增加是權(quán)重，如果覺(jué)得分類(lèi)屬性重要，則增加a，否則減少，否則減少a，a=0時(shí)即只有數(shù)值屬性時(shí)即只有數(shù)值屬性2.更新一個(gè)簇的中心的方法，方法是結(jié)合更新一個(gè)簇的中心的方法，方法是結(jié)合K-Means與與K-modes的更新方法。的更新方法。k-meansk-means算法的改進(jìn)方法算法的改進(jìn)方法k-prototypek-prototype算法算法