李宗辰

(長春金融高等?？茖W校現(xiàn)代教育中心，吉林 長春 130028 )

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

1 K-means算法基本原理與應用

1.1 K-means算法的基本概念

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

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

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

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

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

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

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

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

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

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

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

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

2 K-means算法的改進

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

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

輸入參數(shù)：參數(shù)K，數(shù)據(jù)集S，常數(shù)M。

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

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

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

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

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

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

互信息（Mutual information）是對任意兩個數(shù)據(jù)對象的概率描述，它是通過計算數(shù)據(jù)對象之間的相互包含程度的概率，而在對文本數(shù)據(jù)進行文本聚類時，相同或者相似的文檔內會包含大量的相同或者相近的關鍵詞，這些關鍵詞所表達的文檔的主題也是高度相似的；所以，我們能夠通過計算各文檔內關鍵詞共現(xiàn)的概率來計算出數(shù)據(jù)對象之間的互信息，從而將數(shù)據(jù)集內的數(shù)據(jù)對象進行聚類劃分。因此，本文將選用互信息計算方式取代傳統(tǒng)的歐式距離計算法式，并結合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個數(shù)據(jù)對象劃歸到K個數(shù)據(jù)簇內。

算法具體運行步驟：

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

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

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

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

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

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

其中，I(Tbefore,Y)表達數(shù)據(jù)對象聚類之前在數(shù)據(jù)集T內所含有的互信息數(shù)量，I(Tafter,Y) 則表達數(shù)據(jù)對象在數(shù)據(jù)對象聚類后在數(shù)據(jù)集T內所含有的互信息數(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ù)是選用復旦大學中文語料庫內抓取的部分數(shù)據(jù)，這些數(shù)據(jù)依照主題的不同分為以下九類：教育、娛樂、體育、財經、軍事、房產、汽車、時政與科學。本次實驗是將在數(shù)據(jù)集內獲到的數(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ù)，經過數(shù)據(jù)預處理后，每個文本數(shù)據(jù)對象含有500個屬性。

3.2 實驗結果與分析

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

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

4 結語

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