基于信心論對傳統(tǒng)K-means算法改進

李宗辰

(長春金融高等專科學(xué)?，F(xiàn)代教育中心，吉林 長春 130028 )

聚類分析已經(jīng)廣泛應(yīng)用于多個領(lǐng)域中，包括各類型顧客的消費規(guī)律、基因表達識別、圖像處理、文本檢索分類、空間數(shù)據(jù)分析等，利用聚類技術(shù)針對海量數(shù)據(jù)集進行有效處理之后，可以發(fā)現(xiàn)數(shù)據(jù)之間潛藏的、有價值的信息，將其提供給決策者，讓決策者掌握更多的知識。傳統(tǒng)的K-means算法在實現(xiàn)的過程中存在著三個重要參數(shù)：（1）數(shù)據(jù)點之間相似度的計算方法；（2）初始聚類中心的選?。唬?）數(shù)據(jù)簇的數(shù)值K。經(jīng)過深入研究，洞悉了傳統(tǒng)的K-means聚類算法的優(yōu)缺點，如何對傳統(tǒng)K-means聚類算法的缺陷進行優(yōu)化是本文的研究主體。本文著手于初始聚類中心的選取以及基于信息論對傳統(tǒng)K-means算法加以改進，得到了MI-K-means算法，通過大量實驗進行驗證，不僅能夠大大提升聚類結(jié)果的準確率，同時，還能夠縮短算法的運行時間，提高算法的工作效率。

1 K-means算法基本原理與應(yīng)用

1.1 K-means算法的基本概念

聚類分析是數(shù)據(jù)挖掘領(lǐng)域內(nèi)的一個重要的分支，通過實現(xiàn)聚類算法不單單能夠在規(guī)模龐大的數(shù)據(jù)信息內(nèi)發(fā)掘出隱藏其中的有實際應(yīng)用價值的信息與關(guān)聯(lián)規(guī)則，并且還能夠用于數(shù)據(jù)預(yù)處理以輔助其他的數(shù)據(jù)挖掘算法的開發(fā)與實現(xiàn)。通過聚類算法對數(shù)據(jù)信息進行預(yù)處理后，在將聚類結(jié)果進行進一步的分類整理，能夠大大地提高挖掘結(jié)果的準確率與精確度?；谏显V幾點因素，聚類分析技術(shù)成為各領(lǐng)域最常用的數(shù)據(jù)挖掘技術(shù)之一，并且也是數(shù)據(jù)挖掘領(lǐng)域的學(xué)者們研究的熱點課題。經(jīng)過研究者多年的研究與應(yīng)用，已經(jīng)能夠在各式各樣的研究領(lǐng)域內(nèi)或者認可與應(yīng)用，例如，模式識別領(lǐng)域、文本數(shù)據(jù)挖掘領(lǐng)域、個性推薦領(lǐng)域等。

1.2 K-means算法實現(xiàn)流程

K-means算法的實現(xiàn)過程是從一個初始聚類中心開始進行聚類處理的，然后，通過不斷的循環(huán)迭代處理直至將數(shù)據(jù)集內(nèi)所有的數(shù)據(jù)點分配到K個初始聚類中心的數(shù)據(jù)簇中，從而停止迭代，得到最終的聚類結(jié)果。K-means算法實現(xiàn)的過程是不斷重復(fù)的迭代運算過程，其最終所求的結(jié)果就是使數(shù)據(jù)集內(nèi)的數(shù)據(jù)點距離K個初始聚類中心的距離平方和達到最?。籏-means算法的實現(xiàn)過程共分為4個過程，具體K-means聚類算法實現(xiàn)步驟如下：

輸入數(shù)據(jù)：數(shù)據(jù)集DS；初始聚類中心個數(shù)K；

輸出結(jié)果：K個數(shù)據(jù)簇

（1）在數(shù)據(jù)集中隨機抽取K個數(shù)據(jù)點作為K個數(shù)據(jù)簇的初始聚類中心；

（2）利用歐式距離計算出數(shù)據(jù)集內(nèi)各個數(shù)據(jù)點與K個初始聚類中心的距離，然后，將各個數(shù)據(jù)點劃分至與其距離最近的聚類中心形成數(shù)據(jù)簇；

（3）重新計算K個數(shù)據(jù)簇，從而得到新的聚類中心；

（4）重復(fù)運行步驟(2)與步驟(3)，直至滿足算法迭代條件，終止迭代，最終輸出最終的聚類結(jié)果。

1.3 K-means算法的優(yōu)點與缺陷

K-means算法具備以下幾點優(yōu)勢：首先，是因為K-means算法的邏輯思想設(shè)計簡潔，并且收斂速度快；其次，是相較于其他聚類算法，K-means算法能夠處理的數(shù)據(jù)集規(guī)模更加龐大，聚類分析速度更加迅速，聚類結(jié)果更加準確率；最后，就是K-means算法的魯棒性很高，它能夠高效地處理數(shù)據(jù)類型為數(shù)值型的數(shù)據(jù)集。

K-means算法的實現(xiàn)過程是通過自身不斷迭代從而得到最終的處理結(jié)果，因為數(shù)據(jù)集中大概率會存在孤立點，所以，這種實現(xiàn)過程只能夠得到局限最優(yōu)解，而無法得到全局最優(yōu)解。另外，K-means算法實現(xiàn)過程中所選取的K個初始聚類中心是通過隨機抽取的方法所得到的，這樣就導(dǎo)致了選取的K個初始聚類中心的質(zhì)量決定著最終處理結(jié)果的準確率大小。

2 K-means算法的改進

2.1 優(yōu)化初始聚類中心選取方式

通常狀態(tài)下，如果能夠獲取數(shù)據(jù)集內(nèi)各數(shù)據(jù)對象的分布形態(tài)與聯(lián)系，就能夠更好地分析出數(shù)據(jù)集內(nèi)數(shù)據(jù)對象的分布狀態(tài)，從而能夠在選取初始聚類中心時選取出更加適合的初始聚類中心，進而能夠使得聚類算法最終輸出的聚類結(jié)果更加準確，并且大大地縮小算法的運行時間，提高聚類效率。經(jīng)研究發(fā)現(xiàn)，若在選取初始聚類中心時，引入密度的思想，就能有效地減小孤立點對初始聚類中心選取的影響。具體操作如下：

輸入?yún)?shù)：參數(shù)K，數(shù)據(jù)集S，常數(shù)M。

輸出結(jié)果：將數(shù)據(jù)集S劃分為K個數(shù)據(jù)簇。

（1）通過輸入的常數(shù)M能夠計算出數(shù)據(jù)集S內(nèi)數(shù)據(jù)點的密度參數(shù)，從而能夠獲取高密度集D。

（2）在數(shù)據(jù)集D外，選取參數(shù)密度最小的一個數(shù)據(jù)點作為第一個初始聚類中心z1。

（3）計算初始聚類中心z1與數(shù)據(jù)集D內(nèi)所有數(shù)據(jù)點的距離，通過比較后，選取與z1距離最遠的一個數(shù)據(jù)點作為第二個初始聚類中心z2。

（4）重復(fù)進行步驟（3）的操作，直到獲取到K個初始聚類中心，停止計算，進行聚類分析。

2.2 基于信息論的K-means算法改進

互信息（Mutual information）是對任意兩個數(shù)據(jù)對象的概率描述，它是通過計算數(shù)據(jù)對象之間的相互包含程度的概率，而在對文本數(shù)據(jù)進行文本聚類時，相同或者相似的文檔內(nèi)會包含大量的相同或者相近的關(guān)鍵詞，這些關(guān)鍵詞所表達的文檔的主題也是高度相似的；所以，我們能夠通過計算各文檔內(nèi)關(guān)鍵詞共現(xiàn)的概率來計算出數(shù)據(jù)對象之間的互信息，從而將數(shù)據(jù)集內(nèi)的數(shù)據(jù)對象進行聚類劃分。因此，本文將選用互信息計算方式取代傳統(tǒng)的歐式距離計算法式，并結(jié)合3.1提出的初始聚類中心優(yōu)化方法，從而達到對傳統(tǒng)的K-means算法進行優(yōu)化得到MI-K-means聚類算法。MI-K-means算法的運行過程與步驟，具體如下：

輸入信息：數(shù)據(jù)集D，N個數(shù)據(jù)對象，數(shù)據(jù)簇的個數(shù)K；

輸出信息：將數(shù)據(jù)集D內(nèi)的N個數(shù)據(jù)對象劃歸到K個數(shù)據(jù)簇內(nèi)。

算法具體運行步驟：

（1）采用3.1闡述的方式來選取K個初始聚類中心；

（2）計算數(shù)據(jù)集內(nèi)所有的數(shù)據(jù)對象與K個聚類中心的互信息；

（3）比較數(shù)據(jù)對象的互信息，然后，選取互信息最大的數(shù)據(jù)對象將其劃歸至與其關(guān)聯(lián)的數(shù)據(jù)簇內(nèi)；

（4）重新計算各數(shù)據(jù)簇內(nèi)的聚類中心；

（5）不斷重復(fù)（2）（3）兩個步驟，直至把數(shù)據(jù)集內(nèi)的數(shù)據(jù)對象都劃歸到K個數(shù)據(jù)簇內(nèi)，停止迭代，輸出結(jié)果，算法結(jié)束。

在MI-K-means算法的執(zhí)行過程中，計算數(shù)據(jù)集T內(nèi)的兩個數(shù)據(jù)對象ti和tj的互信息d(ti,tj)的計算公式為：

其中，I(Tbefore,Y)表達數(shù)據(jù)對象聚類之前在數(shù)據(jù)集T內(nèi)所含有的互信息數(shù)量，I(Tafter,Y) 則表達數(shù)據(jù)對象在數(shù)據(jù)對象聚類后在數(shù)據(jù)集T內(nèi)所含有的互信息數(shù)量；I(Tbefore,Y)與I(Tafter,Y) 的差值就是數(shù)據(jù)對象合并的代價。

計算公式如下：

而p(?)與q(?) 之 間 的 距 離 為JS∏[p,q]， 我 們 選 用Jensen-Shannon距離進行計算，計算公式如下：

3 實驗與分析

3.1 實驗數(shù)據(jù)與實驗環(huán)境

為了檢驗本為提出MI-K-means算法的合理性，本次實驗將針對不同維度的文本數(shù)據(jù)對象進行聚類實驗并進行比較。本次實驗數(shù)據(jù)是選用復(fù)旦大學(xué)中文語料庫內(nèi)抓取的部分數(shù)據(jù)，這些數(shù)據(jù)依照主題的不同分為以下九類：教育、娛樂、體育、財經(jīng)、軍事、房產(chǎn)、汽車、時政與科學(xué)。本次實驗是將在數(shù)據(jù)集內(nèi)獲到的數(shù)據(jù)混合在一起，然后，隨機生成的7個實驗數(shù)據(jù)集，分別是3個三類數(shù)據(jù)集、3個六類數(shù)據(jù)集和1個九類數(shù)據(jù)集。選取文本數(shù)據(jù)集進行實驗，數(shù)據(jù)集規(guī)模為4500條數(shù)據(jù)，有且僅有上述9種主題的文本數(shù)據(jù)，經(jīng)過數(shù)據(jù)預(yù)處理后，每個文本數(shù)據(jù)對象含有500個屬性。

3.2 實驗結(jié)果與分析

本輪實驗比較是在三種算法在相同的實驗環(huán)境下處理等樣的數(shù)據(jù)集得出的結(jié)論（如表1），本文采用傳統(tǒng)的K-means算法、可變網(wǎng)格優(yōu)化的K-means算法以及本文提出的MI-K-means算法的實驗結(jié)果進行比較。通過上述三種算法對7組數(shù)據(jù)集進行聚類處理，通過最終得到的聚類結(jié)果可得知，本文提出的MI-K-means算法的準確率要高于傳統(tǒng)的K-means算法，也要高于可變網(wǎng)格K-means算法，尤其是當數(shù)據(jù)集規(guī)模越大，本文提出的算法所給出的聚類結(jié)果相比其他兩中聚類算法的準確率越高。

表1 三種算法聚類結(jié)果的準確率對比（%）

4 結(jié)語

本文闡述了傳統(tǒng)的K-means算法的基礎(chǔ)理論與應(yīng)用現(xiàn)狀，并且闡述了傳統(tǒng)的K-means算法的優(yōu)缺點，本文從處理聚類中心選取和聚類過程兩個方面對傳統(tǒng)的K-means算法進行改進，并提出了MI-K-means算法，通過大量的實驗對比分析，證明改進有效。在未來的研究里，是如何將改進的MI-K-means算法與云計算結(jié)合起來，以便于在對更大規(guī)模的海量數(shù)據(jù)進行聚類分析，從而能夠更好地協(xié)助技術(shù)人員做數(shù)據(jù)挖掘工作，發(fā)現(xiàn)海量數(shù)據(jù)中存在的潛在的、有用的價值創(chuàng)造社會價值。