作業(yè)-2.k-means聚類算法

K-Means聚類算法

k-均值算法的改進

K-中心點聚類算法1.簡介K-means聚類算法就是基于距離的聚類算法所謂的基于距離的聚類算法是指采用距離作為相似性度量的評價指標(biāo)。2.K-means聚類算法原理K-means聚類算法的基本思想：一、指定需要劃分的簇的個數(shù)k值;二、隨機地選擇k個初始數(shù)據(jù)對象點作為初始的聚類中心;三、計算其余的各個數(shù)據(jù)對象到這k個初始聚類中心的距離，把數(shù)據(jù)對象劃歸到距離它最近的那個中心所處在的簇類中;四、調(diào)整新類并且重新計算出新類的中心。2.K-means聚類算法原理開始輸入聚類的個數(shù)

k,n初始化

K

個聚類中心分配各個數(shù)據(jù)對象到距離最近的類中重新計算各個聚類的中心（均值）是否收斂輸出聚類結(jié)果否是K-means算法的工作流程

K-means聚類算法原理K-Means算法的工作框架：給出n

個數(shù)據(jù)樣本,令I(lǐng)

1,隨機選擇K

個初始聚類中心

Z

j

(I

),j

1,2,3,,K

；求解每個數(shù)據(jù)樣本與初始聚類中心的距離

Dxi,Zj

I

,i

1,2,3,,nj

1,2,3,,K

，若滿足D

xi

,Z

j

I

minD

xi

,Z

j

I

,i

1,2,,n，那么xi

wk

；1

njjjni1（3）令

I

I

1,計算新聚類中心Z

2

ix

，

j

1,

2,,K

以及誤差平方和

2njK

j

c

c準(zhǔn)則函數(shù)

J

的值：

J

2

k

jx

Z

2

；j

1

k

1（4）判斷:如果JcI1

JcI

，那么表示算法結(jié)束,反之,I

I

1，重新返回第（2）步執(zhí)行。2.K-means聚類算法原理K-Means算法的特點就是調(diào)整一個數(shù)據(jù)樣本后就修改一次聚類中心以及聚類準(zhǔn)則函數(shù)的值，當(dāng)n個數(shù)據(jù)樣本完全被調(diào)整完后表示一次迭代完成，這樣就會得到新的簇和聚類中心的值。K-Means聚類算法其本質(zhì)是一個最優(yōu)化求解的問題。K-Means算法對聚類中心采取的是迭代更新的方法。K-means聚類算法特點及應(yīng)用K-means聚類算法特點優(yōu)點：算法簡單、快速。對處理大數(shù)據(jù)集，該算法是相對可伸縮的和高效率的。算法嘗試找出使平方誤差函數(shù)值最小的k個劃分。缺點：（1）K-means聚類算法只有在簇的平均值被定義的情況下才能使用。要求用戶必須事先給出要生成的簇的數(shù)目k。對初值敏感。不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。對于“噪聲”和孤立點數(shù)據(jù)敏感。3

K-means聚類算法特點及應(yīng)用3.2

K-means聚類算法應(yīng)用（1）K-means算法在散貨船代貨運系統(tǒng)中的應(yīng)用（2）K-Means算法在客戶細(xì)分中的應(yīng)用4小結(jié)本章詳細(xì)地介紹了K-means算法的基本概念、基本原理,并介紹了該算法的特點和存在的缺陷,最后介紹了K-means算法的應(yīng)用,從中可以看出K-means算法的應(yīng)用非常廣泛。

聚類算法將數(shù)據(jù)點分為多個簇(cluster)

k-menas算法中，簇的中心叫做簇質(zhì)心或中心點(centroid)，質(zhì)心不一定是一個真實存在的數(shù)據(jù)點

把每個簇想像成一塊有質(zhì)量的物體，質(zhì)心即這塊物體的質(zhì)量中心

k-means要求事先指定數(shù)據(jù)要

分為幾組，例如可指定分為3組，這里的3即算法名稱中k的含義，此時k=3圖:4個簇及其質(zhì)心1.隨機挑選3個點作為初始簇質(zhì)心(centroid)指定k=3(即要將數(shù)據(jù)點分成3組)遍歷所有點，各自加入距離最近的簇調(diào)整各個簇的的質(zhì)心4.回到第2步中止條件：簇不再發(fā)生變化第2步如何找到最近的簇？遍歷各簇質(zhì) 算歐氏距離，距離最小的即最近的第3步如何調(diào)整質(zhì)心？取簇中各點的算術(shù)平均值作為新質(zhì)心的坐標(biāo)即可＋＋(8,7)＋＋＋＋(1,

4)(6,

0)(3,

2)(0,

8)(6,

4)(8,

4)(1,

8)(6,

8)(7,

9)(7,8)(1.25,

5.5)(6.67,

2.67)＋(5.75,

2.5)＋(0.67,

6.67)

好的聚類結(jié)果的簇內(nèi)數(shù)據(jù)點比較緊湊，簇間相距大

即簇內(nèi)中各數(shù)據(jù)點離質(zhì)心的距離都比較小

可使用誤差平方和(SSE,SumofSquaredErrors)準(zhǔn)則函數(shù)來評價

一個簇的誤差平方和即簇內(nèi)各點到質(zhì)心歐式距離的平方和：SSE(k)

dis

tan

ce(

p,

centroid)2pX其中p表示簇中的點，X是簇內(nèi)點的集合，distance(p,centroid)即點p到簇質(zhì)心的距離

聚類結(jié)果的SSE即各個簇的SSE之和，其值越小表示聚類質(zhì)量越好

K-Means聚類算法

k-均值算法的改進

K-中心點聚類算法學(xué)生喜歡吃零食喜歡看韓劇喜歡打籃球喜歡玩工資A88005000B78015100C87015080D88105030E001085010F02985090G12995020H21895040結(jié)果被“工資”主導(dǎo)了！考慮對如下學(xué)生數(shù)據(jù)進行聚類

為什么結(jié)果被“工資”主導(dǎo)了？例如x2,y2的差值很大，而x1,y1等差異很小，則計算得到的歐氏距離幾乎就約等于

(x2

y2

)2

解決方案:歸一化v

vminv'

vmax

vminv為原特征值，v'為歸一化后的值，vmin為樣本最小值，vmax為樣本最大值學(xué)生喜歡吃零食喜歡看韓劇喜歡打籃球喜歡玩工資A88005000B78015100C87015080D88105030E001085010F02985090G12995020H21895040歸一化學(xué)生喜歡吃零食喜歡看韓劇喜歡打籃球喜歡玩工資A11000B0.875100.1111111C10.87500.1111110.8D110.100.3E0010.8888880.1F00.250.90.8888880.9G0.1250.250.910.2H0.250.1250.810.4

主要優(yōu)點是解決聚類問題的經(jīng)典算法，簡單、快速結(jié)果簇比較密集，簇間區(qū)別明顯時，效果較好

主要缺點對初始值比較敏感，不同的初始值可能會導(dǎo)致不同的結(jié)果對“噪聲”和孤立點數(shù)據(jù)敏感，少量的該類數(shù)據(jù)能對平均值產(chǎn)生極大的影響在簇的平均值被定義的情況下才能使用，對分類屬性不適用必須事先給出k值如何初始值選的是這兩個點會怎么樣？k-means++基本思路:初始的聚類中心之間的相互距離要盡可能的遠(yuǎn)算法思想:隨機選擇第一個簇質(zhì)心對于數(shù)據(jù)集中每一個點x，計算它與最近質(zhì)心的距離D(x)選擇一個新數(shù)據(jù)點作為新簇質(zhì)心，選擇原則是:

D(x)較大的點，被選取作為聚類中心的概率較大重復(fù)2和3直到k個簇質(zhì)心被選出來利用這k個初始的簇質(zhì)心來運行標(biāo)準(zhǔn)的k-Means算法請課后查閱相關(guān)資料了解算法細(xì)節(jié)

K-Means聚類算法

k-均值算法的改進

K-中心點聚類算法k-中心點算法(k-me

ds)不是簡單像k-means算法采用均值計算法，每次迭代后的質(zhì)心都是從簇的樣本點中選取，而選取的標(biāo)準(zhǔn)就是當(dāng)該樣本點成為新的質(zhì)點后能提高簇的聚類質(zhì)量，使得類簇更緊湊。算法使用SSE來定義一個簇的緊湊程度。算法步驟:隨機選擇k個對象作為初始的中心點；重復(fù)指派每個剩余的樣本點給最近的中心點所代表的簇；隨意地選擇一個非中心點Orandom；計算用Orandom代替原中心點的總代價S；如果S<0(更緊湊了)，則用Orandom替換原中心點；直到不發(fā)生變化*其中

S為替換原中心點后的

SSE減去替換前的

SSE，S<0表示替換后

SSE變小了，即聚類質(zhì)量更好了請課后查閱相關(guān)資料了解算法細(xì)節(jié)1.簡介K中心點聚類算法重復(fù)迭代，直到每 對象都成為它的簇的實際中心點，或最靠中心的對象。聚類結(jié)果的質(zhì)量用代價函數(shù)來評估，該函數(shù)用來度量對象與其簇的代表對象之間的平均相異度。2.K-中心點聚類算法原理K-中心點聚類算法的基本思想為：選用簇中位置最中心的對象，試圖對n個對象給出k個劃分，代表對象也被稱為是中心點，其他對象則被稱為非代表對象。2.K-中心點聚類算法原理在K-中心點聚類算法中需要計算所有非選中對象與選中對象之間的相異度作為分組的依據(jù)．一般情況下，數(shù)據(jù)對象為數(shù)值型，選用曼哈頓距離：d

i,

j

xi1

xj1

xi2

xj

2

xin

xjn此處：i

xi1,

xi

2

,,

xin

和

j

xj1,

xj

2

,,

xjn

是兩個n維的數(shù)據(jù)對象。2.K-中心點聚類算法原理K-中心點聚類算法描述:輸入：簇的數(shù)目k和包含n個對象的數(shù)據(jù)庫輸出：k個簇，使得所有對象與其最近中心點的相異度總和最小任意選擇k個對象作為初始的簇中心點,Repeat指派每個剩余對象給離他最近的中心點所表示的簇Repeat選擇一個未被選擇的中心點Repeat2.K-中心點聚類算法原理K-中心點聚類算法描述:選擇一個未被選擇過的非中心點對象計算用代替的總代價并記錄在S中Until所有非中心點都被選擇過Until所有的中心點都被選擇過If在S中的所有非中心點代替所有中心點后的計算出總代價有小于0的存在，then找出S中的用非中心點替代中心點后代價最小的一個，并用該非中心點替代對應(yīng)的中心點，形成一個新的k個中心點的集合；Until沒有再發(fā)生簇的重新分配，即所有的S都大于0.K-中心點聚類算法特點及應(yīng)用K-中心點聚類算法特點優(yōu)勢：對噪聲點/孤立點不敏感，具有較強的數(shù)據(jù)魯棒性；聚類結(jié)果與數(shù)據(jù)對象點輸入順序無關(guān)；聚類結(jié)果具有數(shù)據(jù)對象平移和正交變換的不變性等。缺點：在于聚類過程的高耗時性。3.K-中心點聚類算法特點及應(yīng)用3.2

K-中心點聚類算法應(yīng)用（1）K-中心點算法在暫住人口分析中的應(yīng)用（2）K-