基于改進K-means聚類算法聚類點選取辦法的研究

◆任楚嵐 喬天宇 張 陽

( 1.沈陽化工大學(xué)計算機科學(xué)與技術(shù)學(xué)院 遼寧 110142; 2.遼寧中醫(yī)藥大學(xué)附屬醫(yī)院 遼寧 110032 )

1 背景介紹

現(xiàn)有的聚類算法中，K均值聚類已成為使用最廣泛的技術(shù)之一，主要是因為其簡單性和有效性。在K均值聚類中，有兩個典型的階段，即聚類初始化和迭代優(yōu)化。在集群初始化中，首先應(yīng)隨機或根據(jù)某些標準確定一組K個集群中心。聚類結(jié)果K個聚類中心將通過將每個數(shù)據(jù)對象迭代地分配給它最近的聚類中心并更新聚類中心的集合而得到優(yōu)化。K均值的迭代優(yōu)化算法對數(shù)據(jù)初始聚類中心非常敏感。一組初始化不佳的聚類中心會降低K均值性能。

為了解決K均值存在的初始化問題，利用不同的技術(shù)進行嘗試。由于在聚類中心選擇中通常會存在一些隨機（或概率）決策，因此這些方法還會遭受隨機性帶來的不穩(wěn)定性。這里的問題是我們是否可以將可能不穩(wěn)定的多個初始化合并到一個更好、更健壯的初始化中，以增強 k-means聚類的整體性能。Arthur和Vassilvitskii 提出了 k-means ++的辦法，該方法隨機選擇第一個聚類中心，然后根據(jù)一定的概率選擇第i個聚類中心。數(shù)據(jù)集中的對象與先前選擇的i-1中心之間的距離。

基于此種方法集合聚類技術(shù)的啟發(fā)也稱為無監(jiān)督集成學(xué)習，旨在將多個弱聚類組合成一個更好的聚類，在本文中，我們通過將多個K均值實例集成到一個集成框架中，提出了一種改進的K均值初始化方法。具體來說，我們首先從數(shù)據(jù)集中隨機選取一個樣本作為初始聚類中心C1。對于數(shù)據(jù)集中的每一個點Xi，計算出它和當前已有聚類中心之間的最小距離。用D（X）表示。然后選擇一個新的樣本為新的聚類中心，一般選取距離D（X）大的點，被選取作為聚類中心的概率較大。通過重復(fù)以上的步驟，選出K個聚類中心。我們在多組真實事跡的醫(yī)療數(shù)據(jù)集上進行了實驗，證明了所改進的K均值初始化方法能夠比其他幾種初始化方法產(chǎn)生更好的性能。

2 構(gòu)建方法

2.1 由多個K-means聚類器生成的集合

K均值聚類對初始聚類中心的選擇高度敏感。即使使用相同的初始化策略，在多次運行中獲得的初始群集中心的集合也可能會非常不同，許多初始化方法中固有隨機性會導(dǎo)致最終K均值聚類結(jié)果不穩(wěn)定。

本文采用多種初始化來獲得魯棒集群中心初始化結(jié)果。我們多次執(zhí)行K均值聚類（使用隨機初始化）以獲得各種基礎(chǔ)聚類的集合。每個K均值聚類器的聚類數(shù)也可以隨機選擇，以進一步改善生成的基本聚類的多樣性。

令D= {D1，D2，...，DN}表示數(shù)據(jù)集，其中DN是第N個對象，是數(shù)據(jù)集中對象數(shù)量。km表示均值聚類器聚類數(shù)，它是在[kmin，kmax]范圍內(nèi)隨機選擇的。

δ∈[0，1]是隨機變量，從隨機選擇的初始聚類中心開始，執(zhí)行K均值聚類以獲得第一個基本聚類，表示為：

表示第一個群集，并表示第一個基本群集中i-th的群集數(shù)量。通過執(zhí)行 K均值聚類時間，可以由此獲得基本聚類的整體，表示為：

2.2 通過排除干擾點進行預(yù)聚類

基本聚類集合構(gòu)成之后 K-means算法對孤立點是十分敏感的。因此在獲得基本的聚類集合之后，獲得了基本聚類的集合后，接下來借助排除干擾的孤立點構(gòu)建和聚集聚類來構(gòu)建預(yù)聚類結(jié)果。

本文基于密度思想，需人為給定半徑r和最小鄰域點數(shù)MinPts。以空間的某一點為球心，r為半徑的球體，給定半徑r的鄰域。用Nr(p)來表示該鄰域里的點p在半徑r的范圍里所有點的集合。表示為：

用D(p,q)表示兩點之間距離，V為數(shù)據(jù)集的容積，n為樣本個數(shù)，d是樣本維度，Γ為伽馬函數(shù)。MinPts為該鄰域內(nèi)核心點的最小鄰域點，MinPts的值根據(jù)數(shù)據(jù)集中的數(shù)據(jù)多少而定。

通過這一辦法，將數(shù)據(jù)樣本集分為核心點、邊界點和孤立點三類。核心點對我們有幫助，為了達到有效的聚類效果，要排除集合中的孤立點和邊界點，取集合簇中核心點的中心作為新的聚類中心。

根據(jù)預(yù)聚類結(jié)果，計算中的每個聚類的歐幾里得中心，獲得K個聚類中心集，表示為：

K個聚類中心結(jié)合了多種方法得到的，具有隨機初始化的多個K均值聚類器中，然后將這K-means聚類群集中心用作初始群集中心在最終的K均值過程中獲得強大的聚類結(jié)果。我們將評估針對預(yù)聚類結(jié)果的方法以及其他幾種初始化方法的K均值。

3 實驗分析

本節(jié)檢驗了改進算法的有效性，對原始算法和改進算法進行對比實驗。

圖1 類簇指標的變化曲線

由圖1可知，在不同的聚類數(shù)目類簇指標下，可以清楚地看到在K=3的時候，出現(xiàn)拐點。類簇指標有明顯改變，故K=3。

為了驗證結(jié)果的可靠性。分別代入兩組不同數(shù)據(jù)（數(shù)據(jù) A ，數(shù)據(jù)B）進行傳統(tǒng)K-means聚類算法和改進后的K-means聚類算法兩組實驗，并對兩組實驗的準確率進行對比。

表1 數(shù)據(jù)A的對比實驗

表2 數(shù)據(jù)B的對比實驗

通過兩組實驗，我們可以看出：傳統(tǒng)的K-means算法，相同數(shù)據(jù)集條件下，不排除孤立點和邊緣點，效果不佳，對實驗整體影響很大，準確率不如改進的算法。

4 結(jié)語

本文采用基于密度的方法，改進集群中心初始化集成學(xué)習的K均值聚類方法，先是利用隨機初始化的辦法，再利用多個K均值聚類器和隨機數(shù)的簇，M個基的整體生成聚類。在此聚類的基礎(chǔ)上，結(jié)合基于密度的方法，排除孤立點和邊緣點。最后，再通過對比實驗驗證了改進后的算法，結(jié)果強于傳統(tǒng)的K-means聚類算法。