第7章聚類分析K均值(K-Means)聚類方法算法原理屬于劃分聚類分割方法基本思想：給定一個具有n個數(shù)據(jù)元素的數(shù)據(jù)集，通過分割的方法對其進(jìn)行劃分，構(gòu)造k個分組(k<n)，每一個分組即為一個聚類。滿足下列條件：①每一個分組至少包含一個數(shù)據(jù)元素；②每一個數(shù)據(jù)元素屬于且僅屬于一個分組。也稱為簇2算法原理基本思想：給定一個具有n個數(shù)據(jù)元素的數(shù)據(jù)集，通過分割的方法對其進(jìn)行劃分，構(gòu)造k個分組(k<n)，每一個分組即為一個聚類。3算法認(rèn)為，聚類后得到的簇，應(yīng)由較為相似的對象組成，因此算法將得到緊湊且獨立的簇作為算法的過程和目標(biāo)。算法原理4k=3

，?

任意劃分3個簇緊湊更靠近簇質(zhì)心計算質(zhì)心指派對象計算質(zhì)心指派對象反復(fù)迭代隨機(jī)指派質(zhì)心K-means選擇初始質(zhì)心將數(shù)據(jù)點指派到初始質(zhì)心（SSE=305）第1次迭代：重新計算質(zhì)心，并將數(shù)據(jù)點指派到質(zhì)心（SSE=268）第2次迭代：重新計算質(zhì)心并指派到質(zhì)心(SSE=264)第3次，重新計算質(zhì)心并指派.最終結(jié)果(SSE=262)第4次，質(zhì)心不再變化，得到最終結(jié)果(SSE=262)迭代終止條件：質(zhì)心不再變化；或2)SSE不再變優(yōu)。SSE–目標(biāo)函數(shù)聚類就是使目標(biāo)函數(shù)最優(yōu)的過程。5[例]基本過程例中，二維數(shù)據(jù)距離：歐幾里得距離計算質(zhì)心點坐標(biāo)：指定到同一個簇的數(shù)據(jù)點(x、y

)坐標(biāo)平均值6算法過程對于給定的k，指定初始質(zhì)心，完成初始聚類，并通過反復(fù)迭代的方法對聚類結(jié)果進(jìn)行調(diào)整，使得每次調(diào)整后的聚類結(jié)果均比前一次好。“好”，是指簇的內(nèi)聚性大，簇間的耦合性小。通常會用設(shè)置一個指標(biāo)來進(jìn)行衡量。將數(shù)據(jù)元素指派給相距“距離”最小的簇，簇的代表為質(zhì)心。7基本算法過程8選擇適當(dāng)?shù)某跏假|(zhì)心是基本K-Means算法的關(guān)鍵步驟。選擇不同的質(zhì)心，聚類的結(jié)果也有所不同。

如何選擇初始質(zhì)心？【算法】K-means聚類算法1：選擇k個點作為初始的質(zhì)心2：repeat3：將每個點指派到最近的質(zhì)心，形成k個簇4：重新計算每個簇的質(zhì)心5：until質(zhì)心不發(fā)生變化基本算法過程1.隨機(jī)選擇質(zhì)心【算法】K-means聚類算法1：選擇k個點作為初始的質(zhì)心2：repeat3：將每個點指派到最近的質(zhì)心，形成k個簇4：重新計算每個簇的質(zhì)心5：until質(zhì)心不發(fā)生變化9基本算法過程10基本算法過程SSE較大11基本算法過程1.隨機(jī)選擇質(zhì)心隨機(jī)地指定k個點作為初始質(zhì)心點，但是簇的質(zhì)量常常不高。【算法】K-means聚類算法1：選擇k個點作為初始的質(zhì)心2：repeat3：將每個點指派到最近的質(zhì)心，形成k個簇4：重新計算每個簇的質(zhì)心5：until質(zhì)心不發(fā)生變化12基本算法過程對于非監(jiān)督的聚類，初始質(zhì)心點的個數(shù)k也是決定聚類結(jié)果的關(guān)鍵因素簇的數(shù)量越多，SSE會達(dá)到更小13(a)選擇初始質(zhì)心(SSE=3555)……(b)第2次迭代(SSE=2154)(c)最終結(jié)果(SSE=1828)k

=4基本算法過程1.隨機(jī)選擇質(zhì)心隨機(jī)地指定k個點作為初始質(zhì)心點，但是簇的質(zhì)量常常不高。2.最小誤差平方和SSE法多次運行，每次使用一組不同的隨機(jī)初始質(zhì)心，然后選取具有最小SSE（誤差的平方和）的簇集?！舅惴ā縆-means聚類算法1：選擇k個點作為初始的質(zhì)心2：repeat3：將每個點指派到最近的質(zhì)心，形成k個簇4：重新計算每個簇的質(zhì)心5：until質(zhì)心不發(fā)生變化14基本算法過程1.隨機(jī)選擇質(zhì)心2.最小誤差平方和SSE法3.層次聚類法使用層次聚類技術(shù)對樣本進(jìn)行聚類，從聚類結(jié)果中提取k個簇，并以這些簇的質(zhì)心為初始質(zhì)心。方法通常很有效，但僅限于樣本相對較?。▽哟尉垲愰_銷較大）而且k相對于樣本大小較小的情況。【算法】K-means聚類算法1：選擇k個點作為初始的質(zhì)心2：repeat3：將每個點指派到最近的質(zhì)心，形成k個簇4：重新計算每個簇的質(zhì)心5：until質(zhì)心不發(fā)生變化15基本算法過程1.隨機(jī)選擇質(zhì)心2.最小誤差平方和SSE法3.層次聚類法4.離散質(zhì)心法①隨機(jī)地選擇或選取所有點的質(zhì)心作為第一個初始質(zhì)心。②

每個后繼初始質(zhì)心，選擇離已經(jīng)選取過的初始質(zhì)心最遠(yuǎn)的點。確保選擇的初始質(zhì)心不僅是隨機(jī)的，且是散開的?？赡苓x中離群點，且求離當(dāng)前初始質(zhì)心集最遠(yuǎn)的點開銷也非常大?！舅惴ā縆-means聚類算法1：選擇k個點作為初始的質(zhì)心2：repeat3：將每個點指派到最近的質(zhì)心，形成k個簇4：重新計算每個簇的質(zhì)心5：until質(zhì)心不發(fā)生變化16基本算法過程17準(zhǔn)則：迭代次數(shù)達(dá)到一定次數(shù)質(zhì)心的變化距離<ε【算法】K-means聚類算法1：選擇k個點作為初始的質(zhì)心2：repeat3：將每個點指派到最近的質(zhì)心，形成k個簇4：重新計算每個簇的質(zhì)心5：until質(zhì)心不發(fā)生變化基本算法過程變化：二分k均值算法是基本k均值算法的直接擴(kuò)充。步驟：將所有點的集合分裂成兩個簇從現(xiàn)有簇中選取一個繼續(xù)分裂重復(fù)步驟②此下去，

直到產(chǎn)生k

個簇18初始化簇表，包含由所有的點組成的簇repeat

從簇表中取出一個簇

for

i=1to

n(實驗次數(shù))

do

使用基本k均值，二分選定的簇

end

for

選擇n個結(jié)果中總SSE最小的二分簇將這兩個簇添加到簇表中until

簇表中包含k個簇。算法特點對

k值較為敏感k=2k=4k=3k=4不同的距離初始值對同樣的數(shù)據(jù)樣本可能得到不同的結(jié)果事先判斷簇的劃分個數(shù)非常困難并往往帶有很大的隨意性19算法特點對離群點、噪聲敏感有離群點k=2離群點導(dǎo)致：SSE高，質(zhì)心代表性變差如何識別、如何處理20算法特點對離群點、噪聲敏感無離散點的聚類迭代過程有離散點的聚類迭代過程21算法特點不能處理非球形簇原始數(shù)據(jù)k=2k=4k=322算法特點不能處理不同尺寸的簇k=2k=423算法特點不能處理不同尺寸的簇k=3k=424算法特點不能處理不同密度的簇原始數(shù)據(jù)K=225算法特點計算開銷大需要迭代進(jìn)行數(shù)據(jù)點之間的鄰近度計算，以調(diào)整質(zhì)心并指派到簇。當(dāng)數(shù)據(jù)量較大時，算法的時間開銷非常大算法簡單，易于理解二分k均值等變種算法運行良好，不受初始化問題的影響26一些問題空簇所有的點在指派時都沒有分配到某簇，就會得到空簇解決：選擇一個替補質(zhì)心找一個距當(dāng)前任何質(zhì)心最遠(yuǎn)的點從最大SSE簇中選一個替補質(zhì)心，繼續(xù)分裂簇，降低SSE27一些問題后處理降低簇SSE進(jìn)一步分裂簇（選SSE最大的簇）引進(jìn)一個新的質(zhì)心（選離所有簇質(zhì)心最遠(yuǎn)的點）拆散一個簇（刪除其質(zhì)心，重新指派其中的點）合并兩個簇增量地更新質(zhì)心在點到簇