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

史國斌，張忠林

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

1 引言

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

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

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

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

2 相關工作

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

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

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

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

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

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

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

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

3 算法過程

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

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

圖1 迭代后期動態(tài)監(jiān)控各類別內聚耦合程度

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

圖2 算法流程圖

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

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

3.1 數(shù)據抽樣

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

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

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

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

3.2 算法優(yōu)化目標及偽代碼

本文算法的優(yōu)化目標函數(shù)分析如下：

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

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

L=‖cs-ct‖

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

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

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

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

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

Wk為類別內部數(shù)據的協(xié)方差矩陣

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

最終每輪迭代得到一個s(k)值，保存該值和其對應的標簽信息(labels information)?？梢悦黠@的看到，類別內部數(shù)據的協(xié)方差越小、類別之間的協(xié)方差越大CH指標s(k)越高，聚類效果越好。

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

START：

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

Step1： 計算類間的距離L(xi，xj)，第一輪時樣本(類)集為D1，后續(xù)樣本集為更新后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作為入參執(zhí)行步驟1至4，開始進行聚類結果評價，并記錄結果：E=E∪Estimator(C)

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

break；

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

return E，C，cent(ck)．

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

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

END

3.3 算法復雜度分析

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

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

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

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

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)

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

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

②f=O(f)

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

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

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

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

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

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

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

面對大型數(shù)據集時，n<

4 對比實驗

4.1 實驗綜述

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

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

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

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

①時間效率對比：算法執(zhí)行時間對比；

②基于外部熵的聚類評估方法[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) 無參照數(shù)據集

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

3) 實驗數(shù)據來源

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

表1 實驗所涉及數(shù)據集及其描述

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

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

表2 實驗涉及的算法說明

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總結

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

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

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