基于改進層次方法的無參K-means算法

史國斌，張忠林

(蘭州交通大學電子與信息工程學院，甘肅 蘭州 730070)

1 引言

對數據進行聚類在現代數據價值提取過程中有非常重要的意義[1]。比如在現代營銷系統中，利用大量客戶資料，對客戶進行聚類可以進行精準營銷[2]；在文字識別領域，對手寫字體進行歸一化、標準化后進行聚類可以識別文字[3]；通過對滴滴、Uber等大量關于交通、運輸時間、高峰乘車地點等數據聚類有助于對城市的交通模式進行深入的了解，可以幫助做城市未來規劃等[4]。

K-means和層次方法(Hierarchical Clustering)是聚類算法中的經典算法。K-means的時間復雜度為O(ktmn)，但其對入參：聚類數k敏感。層次聚類可以無需入參，但時間復雜度至少是O(n2)[5]。

本文通過改進凝聚層次算法，使其自動為K均值算法提供初始化參數，進而利用K均值的高效性對大型數據集進行聚類。

本文算法在大型數據集(超過200萬)上的測試表明，本方法具備生產實踐應用可行性。

2 相關工作

K均值算法作為數據挖掘十大算法之一，在生產實踐中尤其是現代數據科學面對體量巨大的數據集時，仍然具有很強的商業應用價值并得到廣泛應用[6]。因此國內外學者持續對其進行研究與改進，這些改進大多都是針對如何找到合適的K值或避免初值敏感等問題的。

如K-means++算法[7]，利用聚類中心點的選取應盡可能相互離散的思想，來優化初值敏感問題。該算法一定程度上避免了初值選取隨機性帶來的問題，優化了迭代次數，但仍然存在初值、初始聚類中心的隨機選擇問題。實驗部分本文對比了該算法。

ISODATA[8]算法在運行過程中能夠根據各個類別的實際情況進行兩種操作來調整聚類中心數K：①分裂操作，對應著增加聚類中心數；②合并操作，對應著減少聚類中心數。該算法改進了原算法硬劃分的不合理性，但仍然需要設置初始參數啟動算法。

Fuzzyc-means由Dunn(1973)[9]提出，后來由Bezdek(1981)[10]進行了改進，該算法的核心是每個數據點以隸屬度值歸為多個聚類(軟分配)。Eschrich等[11]在2003對該聚類思想再優化，通過用質心代替類內所有數據點來減少數據量，以加快K-means和模糊C-means的使用效率。該算法啟動時通常采用隨機初始化。即權值隨機地選取。簇數需要人為選定。

Pelleg和Moore[12]在1999年提出利用KD樹(kd-tree)來高效地識別所有數據點最接近的聚類中心，可以省略一些明顯不屬于既定聚類中心的距離計算。一年后他們提出X均值(X-means)[13]，在之前工作的基礎上，通過給定K值得范圍，利用諸如赤池信息量準則(AIC)或貝葉斯信息準則(BIC)自動找到K。X-means需要提供初始的聚類數上下限和這需要一定的經驗。

K-medoid[14]算法是由Kaufman和Rousseeuw，2005年提出的優化K均值算法，不同的是該算法初始隨機點限定在樣本點中且使用數據的中位數而不是平均值來表示類。該算法同樣需要人工輸入K值，且其時間復雜度為O(ktn2)，t為迭代次數，復雜度不適用于大型數據集。

谷歌公司的D.Sculley在2010年提出的Mini-BatchKMeans[15]聚類算法，該算法使用了一種叫做MiniBatch(分批處理)的方法對數據點之間的距離進行計算。MiniBatch的好處是計算過程中不必使用所有的數據樣本，而是從不同類別的樣本中抽取一部分樣本來代表各自類型進行計算，這種思路不僅應用于K-Means聚類，還廣泛應用于梯度下降、深度網絡等機器學習和深度學習算法。但由于計算樣本量少，所以會相應的減少運行時間，但另一方面抽樣也必然會帶來準確度的下降。實驗部分本文對比了該算法。

所有這些擴展算法思路都是由一個或多個算法優化K均值算法，且都引入了一些必須由用戶指定的初始算法參數。本文吸收了上述算法的部分思想，同時避免了參數的輸入。

3 算法過程

基于對聚類相關算法思想的研究，本文考慮從三方面對聚類算法性能進行優化。①算法是否可以不帶隨機或者經驗性輸入參數？②一般情況下如果1成立，則算法復雜度會大幅上升(參考無參的層次聚類)，如何能兼顧1的情況下保障算法復雜度較低。③聚類作為無監督學習對于初步探究數據固有模型有實用價值，如何讓聚類算法在超大型數據集中快速有效的發揮作用。

針對上述問題，本文算法考慮利用無參數的層次聚類在抽樣數據中找到合適的初始聚類中心；再利用其結果為K均值提供入參聚類完整數據。圖1為算法核心步驟動態查找最佳聚類值過程圖(圖片數據來自本文HandPosture實驗)。

圖1 迭代后期動態監控各類別內聚耦合程度

監控算法本身是有時間復雜度的，圖1的數據集“Hand Postures”有78095個樣本點，如果按照一般的凝聚層次方法監控的話，會造成時間復雜度增加。本文算法ABK為了控制時間復雜度與K-means相當，設計了如下所示的方法，虛線框說明了監控算法啟動觸發條件。需要注意的是，必須監測離群點/異常點(outlier)，否則算法觸發點會推遲，嚴重影響精確度。

圖2 算法流程圖

圖2中評價函數CH是利用本文2.3節介紹的評價模型calinski＿harabaz＿score(CH分數)來計算分數的。

因為ABK算法主要針對的是大型數據集，下面分步介紹ABK算法在大型數據集上工作的步驟。

3.1 數據抽樣

首先通過對數據集D={y1，y2，y3，…ym}按比例抽樣得到一個子數據集D1={x1，x2，x3，…xn}(D1∈D)。抽樣比例按照數據集大小確定，目標是找到一個平衡點，子集即保留了原始數據集統計學特征，也不至于過大導致初值確定過程耗費過大的算力和時間[16]。抽樣數一般取樣本總體的10%，且100

圖3是利用python隨機抽樣數據示意圖，展示了抽樣后數據在一定程度上仍保持原有分布模式。

圖3 數據正確抽樣后仍保持部分原有特征

圖3表明，在抽樣數據上進行數據原型刻畫(比如分類類數和類中心等)，可以一定程度上反映原始數據的特征，為K-means等需要此類參數的算法提供可靠入參。

3.2 算法優化目標及偽代碼

本文算法的優化目標函數分析如下：

首先，全部樣本點為xi(i∈1，2，…，n)；

確定類間距離L度量方法為“中心距離法”Centroid linkage：

L=‖cs-ct‖

其中S，T為兩個類，cs和ct分別是兩類中心，若初期單個實例為一類，則中心既實例坐標

初始置全部樣本點自為一類，開始迭代(iter)，本來這種迭代只能通過本次迭代的目標函數

?S，TLST=min{‖cs-ct‖}

找到最小的s、t進行合并操作，無法求全局最優解，本方法將CH(calinski＿harabaz＿score)[17]模型與原算法恰當結合，對每輪迭代后的結果進行類內聚合度和類間離散度的評估。CH算法推導如下，下面是CH主要函數

該函數中m為訓練集樣本數，k為類別數。Bk為類別之間的協方差矩陣

Wk為類別內部數據的協方差矩陣

其中cq是q類的中心點，cE是全部樣本中心點，nq是q類總樣本數，tr為矩陣的跡。

最終每輪迭代得到一個s(k)值，保存該值和其對應的標簽信息(labels information)。可以明顯的看到，類別內部數據的協方差越小、類別之間的協方差越大CH指標s(k)越高，聚類效果越好。

最后，從保存的s(k)值中取最大值對應的結果，就是最終需要自動傳遞給K均值的參數。算法偽代碼如下：

START：

輸入抽樣D1={x1，x2，x3，…xn}D1={x1，x2，x3…xn}，選定距離度量函數dist(xi，xj)，置聚類C={?}，選評估函數Estimator，聚類評價記錄E={?}；

Step1： 計算類間的距離L(xi，xj)，第一輪時樣本(類)集為D1，后續樣本集為更新后D*；

Step2： 找到最小的距離樣本對下標：

λi，j=arg mini，j∈DL(xi，xj).將{xi|i∈λi，j}合并為一個類cλi，j；

Step3： 形成新的集合D*=D1λi，j。此時：

C=C∪cλi，j。計算類中心，并入D*，此時：cent(ck)=∑xck/count(ck)，D*=D*∪cent(ck)；

Step4：return新集合D*，聚類結果C，聚類中心cent(ck)。

Step5： while count (C)>=2 do：

將步驟4返回的D*、C作為入參執行步驟1至4，開始進行聚類結果評價，并記錄結果：E=E∪Estimator(C)

Step6： 若聚類數為1：E=E∪Estimator(C)

break；

Step7： 返回聚類評價、聚類結果、聚類中心．

return E，C，cent(ck)．

Step8： 取max(E)對應聚類數k=count(CmaxE)，聚類中心作為入參傳入K-means，得到完整數據集的聚類結果。

目前，多數高校圖書館電腦設施配置不夠高級，軟件硬件更新不快，機器嚴重老化，在借閱過程中經常出錯，甚至導致借閱系統混亂，越是借閱高峰期越容易出錯，還有報警設備也時好時壞，該響的時候不響，不該響的時候亂叫，使借閱室處于一片混亂狀態。再就是借閱室格局單調，進門就是書架，滿眼都是書，缺乏人文氣氛，使人產生一種擁堵疲憊的感覺，享受不到知識帶來的愉悅感。

END

3.3 算法復雜度分析

主要對時間復雜度進行分析。本文算法時間復雜度由改進的層次聚類算法和K-means兩部分組成。計抽樣數為n，樣本總數為N。

本算法層次聚類部分復雜度為O(n3)，迭代后期加入CH評估后，該部分增加的時間復雜度推導如下：

基于CH函數(式(1))的計算方法，得

s(k)=f(Wk，Bk，k，m)(k，m視為常數)

O(s)=O(f(Wk，Bk，k，m))=O(f(Wk，Bk))①

=O(Wk，Bk)②

O(Wk，Bk)=O(Wk)×O(Bk)==O(Wk×Bk)③

∴O(Wk，Bk)=O(C×Bk)=O(N)

推導中運用的一些算法復雜性分析基本運算規則如下：(以下假設f(N)，g(N)是定義在正數集上的正函數。)

①O(C×f)=O(f)

②f=O(f)

③O(f)×O(g)=O(f×g)

假設迭代數為C，根據規則①，推知CH算法的時間復雜度是O(n)，n為樣本容量。

在層次聚類算法中添加CH算法，其對時間復雜度的影響符合如下規則：

④O(f)+O(g)=O(max(f，g))

通過以上分析，ABK算法在數據模型刻畫階段與傳統層次聚類算法的時間復雜度一至，為O(n3)(計抽樣數為n)。

在K-means聚類階段的時間復雜度是O(ktmn)，總時間復雜度是

O(ABK)=O(n3)+O(ktmN)

面對大型數據集時，n<

4 對比實驗

4.1 實驗綜述

實驗的硬件環境為：CPU：Intel-I5處理器、8GB內存。實驗的軟件環境為：64位Windows10；Python3.6.3。

為了驗證算法效率，實驗從兩方面進行對比：一是對比不同聚類算法在同一數據集上的聚類時間和結果評價，目的是在同一數據集上驗證不同算法效率。二是對比不同數據集下各算法的聚類時間、迭代次數和結果評價，目的是查看在不同數據集類型，不同數據規模下同一算法的表現。數據集的選取情況及針對不同數據集的評估方法介紹如下。

1) 有參照(labels＿true)數據集

對于已有劃分參照的數據集實驗包括2個維度的對比：

①時間效率對比：算法執行時間對比；

②基于外部熵的聚類評估方法[18](external entropy based cluster evaluation measure)：該維度分為以下三個子評分，其中：

C={ci|i=1，2，…，n}為n個待聚類樣本；

K={kj|j=1，2，…，m}代表m個聚類；

A={aij}代表第i個樣本被分配到第j類。

a)同質性評估(homogeneity)

每個群集只包含單個類的成員，公式如下

其中

b)完整性評估(completeness)

其中

c)兩者的調和平均(V-mesure)

其中：若β比1大，則完整性權重大。否則同質性權重大。

2) 無參照數據集

對于沒有真實分類參照的數據集將從執行時長和CH分數兩個維度，結合PCA降維后的圖形化進行對比分析。

3) 實驗數據來源

對比實驗所用數據集來自于UCI[19]標準數據集和scikit-learn[20]。包括來自sklearn的digits手寫字數據集，來自UCI的Mop Cap Hand Postures手勢數據集、美國人口普查數據集US Census1990。具體數據集描述如表1所示。

表1 實驗所涉及數據集及其描述

4) 本文比對的算法及其參數

本文對比算法均來自Python-sklearn庫，如表2所示。表2中算法1、2入參中設置了n＿init為10，該參數使K-means算法以隨機中心執行10次并選取其中最好的結果輸出。計算迭代次數(iteration)時，只輸出最好的這次的迭代次數，故計算實際迭代次數時需要按輸出的迭代次數乘以10估算(n＿iter＿*10)。

表2 實驗涉及的算法說明

來自sklearn算法4、5、6、7沒有輸出沒有迭代數(n＿iter＿)，不進行迭代次數對比。

下面是不同算法在不同數據集上與ABK效率對比實驗結果介紹。

4.2 手寫字(digits)數據集對比實驗

數據集介紹：手寫字數據集是由1797個手寫字符組成的數據集，內容是手寫的阿拉伯數字1至9，每個字符由8×8的矩陣表示，所以該字符集有64維屬性。其聚類目標是10個阿拉伯數字(0至9)，實驗結果如表3所示。

表3 各算法在手寫字(digits)小型數據集上的聚類結果對比(抽樣數：500 是否預處理：否)

表3 中，本文算法的時間效率是8種算法中最高的，比PCA降維后的K-means表現還高22%(0.02/0.09)；而在同質性評分上僅次于自頂向下的層次聚類(-9%)、但時間效率是其7.28倍；完整性評分上僅低于近鄰傳播(-22%)但時間效率是其100.8倍；兩者調和平均V-measure評分上，時間效率是自底向上的層次聚類算法的7.42倍，但評分下降了18%。

評分整體表現上高于除了向下層次聚類算法的其它6種算法，但時間效率在小數據集無法完全體現K-means優勢的情況下仍然比向下的層次聚類高7倍。

4.3 手勢(hand postures)數據集對比實驗

數據集介紹：手勢數據集是使用帶有位置矢量標記的手套，記錄了來自12個用戶的5種手勢得到的數據集。其聚類目標是5種手勢的區分。實驗結果如表4所示。

表4 各算法在手勢(hand postures)中型數據集上的聚類結果對比

實驗表明，在樣本數達到7萬時，本文算法綜合性能優于除了算法2、3的其它6種算法。在這個數據量級上，與算法2時間效率差距較大、但有精確度上的優勢；從迭代數可以看出，算法2的迭代數是全部算法里最少的。近鄰傳播和層次聚類已不適用這種規模的數據集。

圖4 手勢數據集聚類可視化(1，2維)

本文算法在聚類結果評價上優于算法2、3，正如相關工作中提到的，MiniBatchKMeans會輕微造成精度下降。而PCA用其它屬性投影在主屬性上進行“預測”則會產生5%左右的誤差[21]。圖4是在手勢數據集上的聚類效果圖。

從圖中可以看到，藍色部分由于簇型結構較好聚類基本與原始聚類一致。其它簇的結果稍弱，但紅色(red)簇實驗效果不理想，該簇類被其它簇類瓜分了部分樣本。

4.4 人口普查(USCensus)數據集對比實驗

數據集介紹：美國人口普查數據集(USCensus1990raw)來自加州大學歐文分校機器學習庫，是從1990年的總體普查樣本中的公共用途微數據樣本(PUMS)中抽取的百分之一的樣本。其屬性為68維，包含居民衣食住行等全面的信息。該數據集專門針對聚類，聚類目標為測試本算法效率和可伸縮性。實驗結果如表5所示。

表5 各算法在(UScensus1990)人口普查大型數據集上的聚類結果對比

通過表5可以看到，在樣本數達到245萬時，本文算法時間效率和評分結果比所有參與實驗的算法均有提升。尤其是時間效率比算法2提升了12%。PCA降維K均值算法在超大數據集聚類時時間優勢喪失且在聚類結果CH分數評價上產生了嚴重下降(-67.7%)。

該數據集進行可視化時，由于數據集具有68個維度，通過PCA主成分分析后發現該數據集90%以上的方差比集中在三個維度，故進行PCA降維后可視化會較為明顯。圖5是將245萬個點進行PCA，參數n＿components=9(選擇進行9維的主成分投影)后得到的聚類效果圖，可以清晰的看到，該數據集經過PCA處理后，其簇型結構非常明顯。

圖5 人口普查數據集聚類可視化(PCA后的前2維，數據集本身經過數據發布者脫敏及標準化處理，沒有單位)

該數據集90%的特征集中在3個維度上，進行PCA后3D可視化可以更清晰的看到該數據集的簇型結構。圖6是利用python的3D建模庫對人口普查數據集進行3D可視化的結果。

圖6 人口普查數據集聚類可視化(3D)

通過3D圖像可以更清晰看到，該數據集在9維中的前三維里展現出更加明顯的層次簇型結構。

5 總結

本文提出了一種凝聚層次聚類思想刻畫K-means初始模型的算法ABK，通過分析抽樣數據自動的為K-means算法提供相對精確的初始參數。即結合了層次聚類算法無入參的特點，又發揮了K-means算法的高效性和可伸縮性。

在多個真實世界數據集上的實驗結果驗證了ABK要比多個聚類算法具有更好的聚類性能，尤其是面對大型數據集，ABK在聚類效率方面提升明顯。

在對多種數據集測試實驗過程中，也發現了一些問題，這些問題成為下一步工作的方向和思路：比如針對不同數據集如何選擇合適的預處理方法；如何提高對非團簇型數據聚類效果等。這些問題有待進一步的理論和實踐研究。