K-means算法聚類中心選取

張 朝, 郭秀娟, 張坤鵬

(1. 吉林大學 地球探測科學與技術(shù)學院, 長春 130026； 2. 吉林建筑大學 電氣與計算機學院, 長春 130118)

0 引 言

K-means聚類算法是一種基于靜態(tài)數(shù)據(jù)對象間相似度的動態(tài)硬聚類算法, 迄今人們已提出了眾多可實行的改進算法[1-3], 并被廣泛應(yīng)用于不同領(lǐng)域。相比其他聚類算法,K-means聚類算法以其實現(xiàn)簡單、 線性時間復(fù)雜度低的優(yōu)勢在數(shù)據(jù)科學和工業(yè)應(yīng)用等領(lǐng)域被廣泛采用。同時,K-means聚類算法也存在一些不足, 其包括： 無法自定聚類簇個數(shù)； 聚類結(jié)果隨機性較大； 對初始聚類中心點存在很大的依賴性, 聚類結(jié)果受初始聚類中心影響較大, 導致聚類算法陷入局部最優(yōu)解, 而非全局最優(yōu)解[4-5]。為改善K-means算法存在的不足, 研究者試圖從不同的角度對K-means算法進行改進, 如隨機抽樣、 距離優(yōu)化和密度估計等方法[6]。

筆者在研究分析K-means初始聚類中心點選取的基礎(chǔ)上, 提出了一種基于原始隨機聚類中心點選取的并行選擇機制, 以降低傳統(tǒng)K-means聚類算法聚類結(jié)果對初始聚類中心點的依賴性, 避免傳統(tǒng)算法下因隨機初始化聚類中心點導致的聚類結(jié)果精確度不高問題, 提高聚類結(jié)果的準確性和穩(wěn)定性。

1 K-means算法

1)K-means聚類算法的核心思想。K-means聚類算法的核心思想是：前期通過確定簇的個數(shù)K, 隨機生成K個聚類中心點(centroids [1,2,…,k]), 將數(shù)據(jù)對象進行分類, 將n個數(shù)據(jù)對象分成k個簇, 簇間相似度極高, 簇與簇之間相似度較低。依據(jù)簇間數(shù)據(jù)對象到簇內(nèi)聚類中心點的距離計算其相似度, 根據(jù)到各簇中心點的距離的不同將數(shù)據(jù)對象劃分給不同簇。在處理龐大的數(shù)據(jù)集合時,K-means聚類算法相對其他算法效率更高。其時間復(fù)雜度為O(nkdt), 空間復(fù)雜度為O((n+k)d), 其中n為數(shù)據(jù)對象的數(shù)量,k為聚類簇數(shù)目,d為數(shù)據(jù)維度,t為迭代次數(shù)。通常情況下k?n, 且t?n。算法得到局部最優(yōu)解。

2)K-means聚類算法分析。K-means聚類算法的聚類運算流程如下。首先, 隨機選擇K個聚類中心, 每個初始的聚類中心近似代表簇的平均歐幾里德平均距離(Euclidean distance)或質(zhì)心, 對于剩余的數(shù)據(jù)集, 進行歐氏距離運算, 生成距離矩陣, 并將其賦予對應(yīng)矩陣中最接近的簇。然后, 重新計算每個簇的平均值, 在重復(fù)計算過程中, 準則函數(shù)實時變化, 直至準則函數(shù)收斂。

(1)

算法： 基于簇中數(shù)據(jù)集到簇中聚類中心點的距離(歐幾里得距離)。

輸入： 含有n個數(shù)據(jù)對象的數(shù)據(jù)集合D, 聚類生成的簇的個數(shù)k,D1∩D2∩…∩Dk=D。

輸出：k個原始聚類中心。

2 聚類中心點的算法

K-means聚類算法對初始聚類中心點的選取采用隨機選擇的方法, 在對比不同距離算法過程中, 不同的距離算法選取的初始聚類中心存在較大差異, 合適的距離算法的選取和隨機條件對后期的聚類實現(xiàn)會有較大的影響。

2.1 K-means聚類中心算法

初始聚類中心的選取采用隨機選取機制, 在整個初始聚類中心點的選取過程中,K-means聚類算法提供了兩種聚類點選擇方式, 分別是中位數(shù)選擇算法和算數(shù)平均值算法。初始聚類中心確定的算法不同, 對聚類效果存在不同程度的影響。聚類輪廓系數(shù)與初始聚類中心點的選擇算法存在一定聯(lián)系。

2.1.1 中位數(shù)算法

中位數(shù)(又稱中值、 中點數(shù)或中數(shù)), 屬于統(tǒng)計學中的專有名詞。在數(shù)據(jù)集合中, 中數(shù)代表一個樣本、 種群或概率分布的一個數(shù)值。根據(jù)這個數(shù)值將數(shù)據(jù)集合劃分為上下等量的數(shù)據(jù)子集合。在有限的數(shù)據(jù)集合中, 可對數(shù)據(jù)對象進行排序觀察, 按照升序或降序找出中位數(shù)。對數(shù)據(jù)集合按升序或降序排列后得到X1,X2,…,XN時, 當N為奇數(shù)時, 中位數(shù)為m0.5=X(N+1)/2； 當N為偶數(shù)時, 中位數(shù)為m0.5=(XN/2+XN/2+1)/2。

由于中位數(shù)不受數(shù)據(jù)集合中極端值的影響, 在一定程度上中位數(shù)對分布數(shù)據(jù)集合的代表性有所提升。但在離散型數(shù)據(jù)集合中, 如果數(shù)據(jù)集合中的偏態(tài)數(shù)據(jù)較多, 中位數(shù)則無法準確的代表該數(shù)據(jù)集合。

2.1.2 算數(shù)平均值算法

算數(shù)平均值(又稱均值), 屬于統(tǒng)計學中最基本、 最常用的一種平均指標。該均值算法主要適用于數(shù)值型數(shù)據(jù)集合, 不適用于品質(zhì)型數(shù)據(jù)集合。算數(shù)平均值是加權(quán)平均數(shù)的一種形式(特殊在各項的權(quán)重相等)。

算數(shù)平均值簡單易行、 反應(yīng)敏捷、 確定嚴密等優(yōu)點。但算數(shù)平均值極易受極端值影響, 在一定程度上極端數(shù)據(jù)會影響算數(shù)平均值的代表性[7]。極端數(shù)據(jù)對象數(shù)量過多會直接影響數(shù)據(jù)集合算數(shù)平均值的值。

(2)

2.2 K-means聚類距離算法

K-means聚類算法初始聚類中心點是隨機選取的, 但距離算法過程中有眾多的選擇, 具體距離算法有歐幾里得距離(Euclidean distance)、 城市街區(qū)距離(City Block distance)、 皮爾森相關(guān)系數(shù)(Pearson correlation)、 絕對相關(guān)系數(shù)(absolute value of the correlation)、 非中心絕對相關(guān)系數(shù)(absolute uncentered correlation)、 斯皮爾曼等級相關(guān)系數(shù)(Spearman’s rank correlation)和等級相關(guān)系數(shù)(Kendall’s tau)等。

2.2.1 歐幾里得距離算法

歐幾里得距離(又稱歐氏距離、 歐幾里得度量)算法是聚類距離算法中較為常用的一種算法, 歐幾里得度量(Euclidean metric)對數(shù)據(jù)對象進行計算, 依據(jù)數(shù)據(jù)點距離聚類中心點C1,C2,…,Ck的歐幾里得距離進行分類, 確定距離點所屬簇類。該算法的時間復(fù)雜度為O(nkdt)。計算公式如下。

二維空間計算公式

(3)

三維空間計算公式

(4)

2.2.2 城市街區(qū)距離算法

城市街區(qū)距離(又稱曼哈頓距離)源于城市區(qū)塊距離, 是將多個維度上的距離進行求和后的結(jié)果, 是由赫爾曼·閔可夫斯基在十九世紀所提出的詞匯。計算公式如下

d(i,j)=|Xi-Xj|+|Yi-Yj|

(5)

城市街區(qū)距離算法具有下列性質(zhì)。

1) 非負性。d(i,j)≥0, 距離是一個非負的數(shù)值。

2) 同一性。d(i,i)=0, 對象到自身的距離為0。

3) 對稱性。d(i,j)=d(j,i), 距離是一個對稱函數(shù)。

4) 三角不等式。d(i,j)≤d(i,k)+d(k,j), 從對象i到對象j的直接距離不會大于途經(jīng)的任何其他對象k的距離。

3 聚類中心點實驗

筆者的實驗環(huán)境為： Intel Core i5-2450m, DDR3 1333Mhz 4 GByte內(nèi)存, 128 GB固態(tài)硬盤, Ubuntu操作系統(tǒng), 利用Python3.5語言進行編程, 以驗證算法的有效性。引用中國氣象數(shù)據(jù)網(wǎng)天氣數(shù)據(jù), 截取同一天國內(nèi)2 239座城市中106個城市的氣象信息, 每條數(shù)據(jù)包含7個屬性, 分為5類。分別對數(shù)據(jù)使用歐幾里得距離算法和城市街區(qū)算法隨機進行了10次測試, 記錄其運行時間與輪廓系數(shù), 并進行了綜合比對分析。

3.1 實驗方法

在實驗過程中, 對數(shù)據(jù)集合進行了10次聚類實驗。實驗數(shù)據(jù)分析階段引入輪廓系數(shù)[8]對聚類結(jié)果進行評價分析, 相同數(shù)據(jù)集合的前提條件下, 選用方法不同聚類效果不盡相同, 輪廓系數(shù)可以直接有效的反應(yīng)聚類效果的好壞[9]。對于單一數(shù)據(jù)對象, 其輪廓系數(shù)計算公式如下

(6)

其中a(i)為該數(shù)據(jù)對象到本身所屬簇內(nèi)其他點的平均距離,b(i)為改數(shù)據(jù)對象到非本身所在簇的點的平均距離。當簇內(nèi)有且僅有一個數(shù)據(jù)對象時, 定義S(i)為0[10]。輪廓系數(shù)的取值范圍為-1～1, 輪廓系數(shù)越高表明簇內(nèi)聚度和分離度都相對較優(yōu)。

3.2 實驗結(jié)果

為了檢驗聚類的有效性, 在眾多距離算法中選取歐氏距離算法和城市街區(qū)距離算法, 其余距離算法因平均聚類輪廓系數(shù)為負, 不進行比較分析說明。確定數(shù)據(jù)集合進行聚類的K值為5。數(shù)據(jù)集合共有106條數(shù)據(jù)對象, 分為5類, 在實驗過程中根據(jù)指定的初始聚類中心選取算法隨機選取初始聚類中心和聚類距離算法進行距離度量計算, 對數(shù)據(jù)對象進行聚類分析。

在整個聚類實驗過程中, 首先采用中位數(shù)初始聚類中心選取算法, 距離度量計算依次使用歐氏距離算法和城市街區(qū)距離算法, 對輸出數(shù)據(jù)進行有效性記錄。在系統(tǒng)性的進行測試實驗過程中, 由于多次出現(xiàn)實驗結(jié)果完全相同的情況, 故在多次循環(huán)測試過程中對重復(fù)性實驗結(jié)果數(shù)據(jù)進行選擇性舍棄。在對中位數(shù)初始聚類中心選取算法實驗結(jié)束后, 改用算數(shù)平均值初始聚類中心選取算法, 距離度量計算依然延續(xù)使用首次實驗中的歐氏距離算法和城市街區(qū)距離算法。進行實驗分析, 記錄相關(guān)數(shù)據(jù)結(jié)果。具體數(shù)據(jù)如表1所示。

表1 組合算法運行時間及輪廓系數(shù)

圖1 組合算法輪廓系數(shù)對比分析圖Fig.1 Coefficient of combination algorithm outline contrast analysis diagram

在分析表1的時間參數(shù)和輪廓系數(shù)S(i)過程中, 發(fā)現(xiàn)在選擇中位數(shù)初始聚類中心選取算法的前提下, 歐氏距離算法聚類效果遠優(yōu)于城市街區(qū)距離算法； 在選擇算數(shù)平均值初始聚類中心選取算法的前提下, 歐氏距離算法聚類效果遠優(yōu)于城市街區(qū)距離算法。對表1中的4種組合算法的聚類結(jié)果的輪廓系數(shù)計算, 分別計算4種組合算的平均絕對偏差, 算法1的平均絕對偏差為0.035 947 948； 算法2的平均絕對偏差為0.032 819 146； 算法3的平均絕對偏差為0.112 560 421； 算法4的平均絕對偏差為0.028 708 484。

在分析表1的數(shù)據(jù)后, 提取4種組合算法的聚類輪廓系數(shù)進行比對分析, 如圖1所示, 4種組合算法的輪廓系數(shù)曲線。

3.3 實驗分析

通過對比4種組合算法對同一數(shù)據(jù)集合的聚類運算結(jié)果, 發(fā)現(xiàn)傳統(tǒng)K-means聚類算法在隨機選取初始聚類中心的過程中選取算法不同, 以及距離度量算法的不同對聚類效果有較大的影響。初始聚類中心算法與距離度量算法的不同組合, 對數(shù)據(jù)的聚類效果也不盡相同。組成的4種組合聚類算法在對數(shù)據(jù)進行聚類分析的過程中, 通過對其聚類輪廓系數(shù)的分析比較可以看出, 不同的算法組合其輪廓系數(shù)離散程度不同。

在考慮極端輪廓系數(shù)的前提條件下, 聚類離散程度最小的為歐氏距離算數(shù)平均值初始聚類中心選擇算法, 而對應(yīng)的離散程度最大的為城市街區(qū)距離算法中位數(shù)初始聚類中心點選擇算法。

在忽略極端聚類輪廓系數(shù)的前提條件下, 歐氏距離算法中位數(shù)初始聚類中心點選擇算法聚類效果最優(yōu), 在針對大數(shù)據(jù)聚類分析過程中在不考慮時間因素的前提下優(yōu)先選擇歐氏距離算法, 搭配的初始聚類中心選擇算法算數(shù)平均值算法和中位數(shù)算法均可達到較好的聚類效果。

4 結(jié) 語

K-means聚類算法是科學計算、 數(shù)據(jù)分析、 數(shù)據(jù)挖掘中的重要算法之一, 通常作為經(jīng)典的無監(jiān)督機器學習算法[11]。筆者通過對比分析傳統(tǒng)K-means聚類算法中的距離選擇算法和初始聚類中心點選擇算法, 在實際的數(shù)據(jù)聚類過程中, 進行相關(guān)實驗, 通過聚類結(jié)果的輪廓系數(shù), 初步確定了基于原始K-means聚類算法的優(yōu)化K-means聚類算法。通過實驗分析在可接受運行時間內(nèi), 重組后的K-means聚類算法穩(wěn)定性更好, 準確性更高。