改進(jìn)的K-means法及其應(yīng)用.pdf

1、人們對(duì)客觀事物的研究總是從無認(rèn)識(shí)到有認(rèn)識(shí)，步步深入，漸漸明朗化的。對(duì)事物進(jìn)行分類則是人類認(rèn)識(shí)世界的基本手段之一。在數(shù)據(jù)分類不明確時(shí)，對(duì)其進(jìn)行探索性的分類是極為必要的。聚類分析作為一種無監(jiān)督的分類方法，在分類方法學(xué)中起到了舉足輕重的作用。 聚類分析包括很多種，其中K-means法作為快速聚類法(又稱動(dòng)態(tài)聚類法)中最常用的一種，由于在計(jì)算速度上具有無可比擬的優(yōu)勢(shì)，常被作為大樣本聚類分析的首選方案。其基本原理為：人為地或按照某種標(biāo)準(zhǔn)選

2、擇初始凝聚點(diǎn)，依據(jù)樣品點(diǎn)到各初始凝聚點(diǎn)的歐氏距離，將樣品劃分到與其距離最近的類別中，形成初始分類。再對(duì)初始分類進(jìn)行修正，直到分類比較合理，不必再修正為止。實(shí)踐表明，由于該方法在聚類過程中采取距離就近原則，故更傾向于產(chǎn)生大小相等的球狀類。而在實(shí)際研究中常存在幾個(gè)類在“空間”所占容積大小不等的情況。例如亞健康問題，健康的人大都相似，處于亞健康狀態(tài)的人卻因?yàn)榘Y狀各不相同而存在較大的變異度。在這種情況下，K-means法常常無法得到令人滿意的結(jié)

3、果。本研究通過模擬和實(shí)例分析來探討對(duì)于各類在“空間”所占容積(對(duì)應(yīng)于方差)大小不等的類，如何聚類可以達(dá)到較好的效果。 材料與方法: 本研究旨在提出一種改進(jìn)的K-means法，在對(duì)方差不等的類進(jìn)行聚類時(shí)，可以取得較好的效果。 思想來源： 樣品來自兩個(gè)方差不等的類的可能性不但與該樣品與類中心的距離有關(guān)，還與類內(nèi)相似度有關(guān)。故在每次聚類過程中，對(duì)樣品與類之間距離的量化，應(yīng)考慮類內(nèi)方差的大小?；舅枷耄翰煌念愊?/p>

4、似度可能不同。故在計(jì)算樣品與類的距離時(shí)，依據(jù)類內(nèi)相似度的大小為其賦予不同的權(quán)重。當(dāng)類內(nèi)相似度比較大時(shí)，為其賦予較大的權(quán)重。當(dāng)類內(nèi)相似度比較小時(shí)，為其賦予較小的權(quán)重。類內(nèi)相似度可以通過類內(nèi)方差的大小來度量。方差大，說明類內(nèi)相似度比較??；方差小，則說明類內(nèi)相似度比較大。故將權(quán)重定義為方差的倒數(shù)。 算法描述： 1、初始凝聚點(diǎn)的選擇在選擇初始凝聚點(diǎn)的過程中，如果僅僅基于距離因素，往往會(huì)找到許多孤立點(diǎn)作為初始凝聚點(diǎn)。實(shí)際上，初始凝

5、聚點(diǎn)除了盡量分散，能使各類被恰當(dāng)?shù)貐^(qū)分之外，還應(yīng)該具有一定的代表性，即具有較高的密度。因此，在初始凝聚點(diǎn)的選擇中，除了考慮其散布程度外，還應(yīng)考慮密度因素。本文所提出的聚類方法，引入了每類的方差，若仍以孤立點(diǎn)為初始凝聚點(diǎn)，聚類的效率會(huì)受到很大影響。因此，本文所提出的方法，選擇密度法作為初始凝聚點(diǎn)的選擇方法。 2、距離的定義由于考慮了各類方差的影響，故定義樣品到各類的“相對(duì)距離”而非“絕對(duì)距離”作為聚類準(zhǔn)則。所謂相對(duì)距離即樣品點(diǎn)到類

6、中心的歐氏距離平方與類內(nèi)方差之比。考慮到極端點(diǎn)對(duì)方差的影響，故此處對(duì)方差進(jìn)行修正。修正方法為選擇與類中心的歐氏距離平方最近的80﹪的樣品點(diǎn)，計(jì)算方差。 3、聚類效果的評(píng)價(jià)概括地說，對(duì)聚類效果的評(píng)價(jià)主要有三種方法。一種是基于外部的準(zhǔn)則，該準(zhǔn)則基于數(shù)據(jù)集上的一個(gè)預(yù)定義的結(jié)構(gòu)來評(píng)價(jià)聚類算法的結(jié)果。另外一種是基于內(nèi)部的準(zhǔn)則，即利用數(shù)據(jù)集本身的特征來評(píng)價(jià)聚類結(jié)果。第三種是相對(duì)準(zhǔn)則，即在同一個(gè)數(shù)據(jù)集上，用同一種聚類算法但參數(shù)取值不同的多次聚

7、類結(jié)果的比較來進(jìn)行算法的評(píng)價(jià)。 基于以上各準(zhǔn)則的評(píng)價(jià)指標(biāo)很多，且各有優(yōu)缺點(diǎn)。本研究采用的模擬數(shù)據(jù)和實(shí)際數(shù)據(jù)為已知分類的數(shù)據(jù)，故可采用外部準(zhǔn)則對(duì)其進(jìn)行評(píng)價(jià)。聚類準(zhǔn)確度定義為分類結(jié)果與預(yù)定義類別一致的個(gè)體數(shù)與參與聚類的全部個(gè)體數(shù)的比。該指標(biāo)容易理解，是對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)的一個(gè)常用外部評(píng)價(jià)指標(biāo)。但是聚類結(jié)果中所給出的類標(biāo)簽，與金標(biāo)準(zhǔn)并無明確的對(duì)應(yīng)關(guān)系，故該指標(biāo)如何計(jì)算十分模糊。本研究利用SAS軟件編寫程序，尋找聚類結(jié)果與金標(biāo)準(zhǔn)之間的對(duì)

8、應(yīng)關(guān)系，并計(jì)算聚類準(zhǔn)確率。從而使聚類結(jié)果更加直觀。模擬實(shí)驗(yàn)：利用SAS產(chǎn)生兩類服從雙變量正態(tài)分布的數(shù)據(jù)。要求兩類數(shù)據(jù)具有不同的方差比，對(duì)于所選取的每個(gè)固定的方差比，設(shè)置不同的類間距。每類樣本量為300，每種情況抽樣次數(shù)為100。 實(shí)例分析：應(yīng)用改進(jìn)的K-means法對(duì)真實(shí)數(shù)據(jù)進(jìn)行分析，并對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)。 算法實(shí)現(xiàn)：采用SAS軟件編寫改進(jìn)的K-means法的實(shí)現(xiàn)程序以及產(chǎn)生模擬數(shù)據(jù)、產(chǎn)生初始凝聚點(diǎn)以及準(zhǔn)確度度量的程序。

9、 結(jié)果與討論: 模擬試驗(yàn)的結(jié)果顯示：當(dāng)兩類方差比為9，6，4，3時(shí)，改進(jìn)的K-means法的聚類效果優(yōu)于傳統(tǒng)的K-means方法。當(dāng)兩類方差比為2時(shí)，改進(jìn)的K-means法未體現(xiàn)出優(yōu)越性。比較兩種方法的聚類準(zhǔn)則，可以看出：改進(jìn)的K-means法與傳統(tǒng)K-means法的不同之處在于，對(duì)處于中間地帶的樣品點(diǎn)的處理方式不同。改進(jìn)的K-means法由于考慮了方差的因素，認(rèn)為處于中間地帶的樣品點(diǎn)雖然與兩類“絕對(duì)距離”相當(dāng)，但“相對(duì)