K-means算法聚類中心選取

張 朝, 郭秀娟, 張坤鵬

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

0 引 言

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

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

1 K-means算法

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

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

(1)

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

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

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

2 聚類中心點的算法

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

2.1 K-means聚類中心算法

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

2.1.1 中位數算法

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

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

2.1.2 算數平均值算法

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

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

(2)

2.2 K-means聚類距離算法

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

2.2.1 歐幾里得距離算法

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

二維空間計算公式

(3)

三維空間計算公式

(4)

2.2.2 城市街區距離算法

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

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

(5)

城市街區距離算法具有下列性質。

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

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

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

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

3 聚類中心點實驗

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

3.1 實驗方法

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

(6)

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

3.2 實驗結果

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

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

表1 組合算法運行時間及輪廓系數

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

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

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

3.3 實驗分析

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

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

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

4 結 語

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