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

◆任楚嵐 喬天宇 張 陽

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

1 背景介紹

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

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

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

2 構建方法

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

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

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

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

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

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

2.2 通過排除干擾點進行預聚類

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

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

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

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

根據預聚類結果，計算中的每個聚類的歐幾里得中心，獲得K個聚類中心集，表示為：

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

3 實驗分析

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

圖1 類簇指標的變化曲線

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

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

表1 數據A的對比實驗

表2 數據B的對比實驗

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

4 結語

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