基于改進(jìn)K-means聚類算法聚類點(diǎn)選取辦法的研究

◆任楚嵐 喬天宇 張 陽

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

1 背景介紹

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

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

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

2 構(gòu)建方法

2.1 由多個(gè)K-means聚類器生成的集合

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

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

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

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

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

2.2 通過排除干擾點(diǎn)進(jìn)行預(yù)聚類

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

本節(jié)檢驗(yàn)了改進(jìn)算法的有效性，對原始算法和改進(jìn)算法進(jìn)行對比實(shí)驗(yàn)。

圖1 類簇指標(biāo)的變化曲線

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

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

表1 數(shù)據(jù)A的對比實(shí)驗(yàn)

表2 數(shù)據(jù)B的對比實(shí)驗(yàn)

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

4 結(jié)語

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