基于網(wǎng)格密度的K—均值算法簇中心點(diǎn)識(shí)別的研究

劉利康

摘 要：傳統(tǒng)的K-均值聚類算法只能通過人工參數(shù)設(shè)定K值和初始簇中心點(diǎn)，而人工方式選擇的K值和初始簇中心點(diǎn)往往有較大偏差，直接導(dǎo)致錯(cuò)誤的分簇結(jié)果.基于上述問題，本文提出了一種基于網(wǎng)格和密度的K值與最佳初始簇類中心自動(dòng)識(shí)別的方法。經(jīng)理論和實(shí)驗(yàn)證明，該方法在很大程度提高了聚類結(jié)果的質(zhì)量和算法的效率。

關(guān)鍵詞：K-均值 網(wǎng)格聚類 簇中心點(diǎn) 密度峰值

一、引言

K-均值算法是目前聚類分析算法中應(yīng)用歷史較久、范圍較廣泛的一種。傳統(tǒng)的K-均值以平方誤差準(zhǔn)則較好的實(shí)現(xiàn)了空間聚類，對(duì)處理大規(guī)模數(shù)據(jù)集有較大優(yōu)勢(shì)。但K-均值太依賴于K值、初始簇中心點(diǎn)的設(shè)定。由于大多數(shù)情況下，聚類數(shù)K和簇的大致中心位置無法事先確定，因此需要通過優(yōu)化算法對(duì)聚類數(shù)K和最佳初始簇中心點(diǎn)進(jìn)行估計(jì)。但對(duì)于如何確定K和各個(gè)簇中心的位置范圍，目前尚無明確的理論指導(dǎo)，本文則針對(duì)此問題展開討論。

本文結(jié)合K-均值算法和網(wǎng)格、密度算法的優(yōu)點(diǎn)，提出一種新的K-均值算法中K值和最優(yōu)初始簇中心點(diǎn)自動(dòng)識(shí)別的方法。經(jīng)過理論和實(shí)驗(yàn)分析驗(yàn)證了該方法可以通過計(jì)算分析自動(dòng)給出K值和較佳的初始簇中心點(diǎn)，很大程度改善了K-均值需要人工設(shè)置參數(shù)的問題，有效提高了聚類精度和效率。

二、典型基于劃分方法—K-均值算法

k-均值算法由J.B.MacQueen于1967年提出[4]，是經(jīng)典聚類算法之一。近幾十年來被廣泛應(yīng)用于生物統(tǒng)計(jì)、圖像處理、信息檢索、客戶分類等各領(lǐng)域。針對(duì)該算法的完善、改進(jìn)和擴(kuò)展，人們做了大量的長時(shí)間研究工作。

設(shè)待分析數(shù)據(jù)集合D的屬性數(shù)為d，數(shù)據(jù)對(duì)象數(shù)量為N，以歐式距離作為數(shù)據(jù)對(duì)象的差異程度的度量，則D可看作d維歐式空間Rd中的數(shù)據(jù)點(diǎn)集。設(shè)每個(gè)數(shù)據(jù)點(diǎn)為Xi，則D= {Xi，i=1，2，...，N}。

k-均值算法以k為參數(shù)，其核心思想是將N個(gè)數(shù)據(jù)點(diǎn)分為k個(gè)簇，使得每個(gè)簇中的數(shù)據(jù)點(diǎn)到該簇中心點(diǎn)的平方和最小，算法的流程如下：

1.從N個(gè)數(shù)據(jù)點(diǎn)中任意選取k個(gè)作為初始的簇類中心點(diǎn)；

2.分別計(jì)算每個(gè)數(shù)據(jù)點(diǎn)到各簇中心點(diǎn)的距離，以最近鄰原則，將該數(shù)據(jù)點(diǎn)分配到距離最近的簇中；

3.所有數(shù)據(jù)點(diǎn)分配完畢后，重新計(jì)算k個(gè)聚類的中心位置；

4.與前一次計(jì)算所得的k個(gè)聚類中心點(diǎn)的位置比較，若中心點(diǎn)位置變化的程度小于某閥值（即準(zhǔn)則函數(shù)收斂），那么算法結(jié)束；否則轉(zhuǎn)步驟2繼續(xù)執(zhí)行。

k-均值算法的優(yōu)點(diǎn)包括：執(zhí)行效率高、伸縮性強(qiáng)、設(shè)計(jì)思路簡單明了等。但同樣k-均值算法也存在著一定缺點(diǎn)，主要有：

1.算法擅長處理球狀簇的數(shù)據(jù)集，對(duì)于任意形狀的數(shù)據(jù)往往效果較差；

2.算法的k值需要人工指定，而這個(gè)k值是很難估計(jì)的。很多情況下，我們事先并不知道數(shù)據(jù)集應(yīng)該分為幾類；

3.算法的初始簇中心點(diǎn)是隨機(jī)選取的，選取點(diǎn)不同，結(jié)果也可能不同，這種依賴性導(dǎo)致聚類結(jié)果的不穩(wěn)定。且k-均值算法常采用誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)，導(dǎo)致結(jié)果容易陷入局部最優(yōu)，難以獲取全局最優(yōu)解；

4.算法需要不斷計(jì)算調(diào)整后的新的簇中心位置，然后不斷對(duì)數(shù)據(jù)點(diǎn)的分簇進(jìn)行調(diào)整，因此在數(shù)據(jù)量大時(shí)，時(shí)間開銷非常大；

5.對(duì)噪聲點(diǎn)和孤立點(diǎn)敏感。

本文針對(duì)k-均值的k值和初始簇中心點(diǎn)的依賴性問題，提出一種通過網(wǎng)格化方法自動(dòng)確定k值和選取最佳初始簇中心點(diǎn)的新思路，在此基礎(chǔ)上給出了改進(jìn)的K-均值算法。

三、利用網(wǎng)格的貢獻(xiàn)值進(jìn)行網(wǎng)格劃分

為便于空間定位和網(wǎng)格統(tǒng)計(jì)量的計(jì)算，改進(jìn)的算法先對(duì)數(shù)據(jù)作歸一化，然后采用均勻劃分方法。設(shè)每一維上劃分長度相同的P個(gè)區(qū)間，則劃分產(chǎn)生Pd個(gè)網(wǎng)格。那么P值該取多大呢？這里引入網(wǎng)格貢獻(xiàn)值的概念來獲取最佳的網(wǎng)格劃分。

我們將網(wǎng)格看做盒子，網(wǎng)格中的數(shù)據(jù)點(diǎn)看作盒子中的小球，則最均勻的狀態(tài)是一個(gè)盒子裝一個(gè)球，這時(shí)數(shù)據(jù)集沒有簇產(chǎn)生，聚類沒有意義。但該狀態(tài)是小概率事件，現(xiàn)實(shí)中幾乎不可能出現(xiàn)。實(shí)際上數(shù)據(jù)分布往往是不均的，一個(gè)盒子可能裝好幾個(gè)球，也可能是空的。

我們?cè)诤凶雍颓虻臄?shù)量一一對(duì)應(yīng)的條件下考察二者的關(guān)系。一個(gè)盒子是空的意味著另一個(gè)盒子多一個(gè)球，空盒子越多說明另外有盒子裝得越滿，分布越不均勻，聚類越容易，因此對(duì)聚類的貢獻(xiàn)越大。另外換個(gè)角度看，盒子裝得越滿，說明空盒子變的更多，有球的盒子之間的空盒子越多，空隙越大，聚類變?nèi)菀?，?duì)聚類的貢獻(xiàn)也越大。

自然的引入單元網(wǎng)格貢獻(xiàn)值的概念，用C表示。容易想到將包含數(shù)據(jù)點(diǎn)數(shù)為1（基數(shù)為1）的單元網(wǎng)格貢獻(xiàn)值設(shè)0。因?yàn)榫鶆驙顟B(tài)的單元網(wǎng)格基數(shù)全部為1，對(duì)形成密度差沒有任何貢獻(xiàn)。直觀上看，一個(gè)盒子一個(gè)球是常態(tài)，正常情況應(yīng)該就是這樣，談不上貢獻(xiàn)。把球從一個(gè)盒子拿到另一個(gè)盒子的運(yùn)動(dòng)為改變常態(tài)做了“功”，這里稱為“貢獻(xiàn)”。使?fàn)顟B(tài)偏離常態(tài)越遠(yuǎn)，“貢獻(xiàn)”就越大。

描述貢獻(xiàn)值最簡單的方式將貢獻(xiàn)值函數(shù)設(shè)置為線性函數(shù)C=|n-1|，將空盒子的貢獻(xiàn)值設(shè)為1，基數(shù)為1的盒子設(shè)為0，基數(shù)大于1的盒子設(shè)為n-1。為更符合貢獻(xiàn)值的變化曲線，一般采用Sigmoid核函數(shù)的變化形式進(jìn)行描述：

稱基數(shù)為n的網(wǎng)格為n-網(wǎng)格，則n-網(wǎng)格的貢獻(xiàn)值為S（|n-1|）。這里將1-網(wǎng)格稱為臨界網(wǎng)格，易知當(dāng)網(wǎng)格劃分和臨界網(wǎng)格確定后，全部網(wǎng)格的貢獻(xiàn)值總和越大，簇之間的空隙越大，類別特征越明顯。

我們稱基數(shù)大于臨界網(wǎng)格的網(wǎng)格為稠密網(wǎng)格，基數(shù)小于或等于臨界網(wǎng)格則稱為稀疏網(wǎng)格。臨界網(wǎng)格也可選擇基數(shù)為2，3，…，n的網(wǎng)格擔(dān)當(dāng)，實(shí)踐證明，在數(shù)據(jù)量較大的時(shí)候，基數(shù)在1到4之間選擇常得到聚類效果佳的劃分。文中我們?cè)O(shè)臨界網(wǎng)格為1-網(wǎng)格，即網(wǎng)格數(shù)盡量與數(shù)據(jù)點(diǎn)數(shù)一致。令hd=N，則每一維劃分?jǐn)?shù)P=[h]，這里為提高聚類效率，讓P向下取整。

確定P值之后，將每維劃分成P個(gè)小區(qū)間，由于數(shù)據(jù)已歸一化，于是每維的取值范圍為[0，1]，為保證每個(gè)數(shù)據(jù)點(diǎn)落到唯一的網(wǎng)格中，設(shè)第1個(gè)劃分區(qū)間為閉區(qū)間，其他情況下為左開右閉區(qū)間，…，。然后遍歷數(shù)據(jù)點(diǎn)集，將數(shù)據(jù)點(diǎn)依次放入所屬的網(wǎng)格中，并統(tǒng)計(jì)網(wǎng)格基數(shù)。遍歷完成后，將稠密網(wǎng)格按基數(shù)降序排序生成稠密網(wǎng)格降序列表G。