一種高效的陰陽k-Means聚類算法

李長明, 張紅臣, 王 超, 李曉光, 陸 洋, 錢超越

(1. 長春光華學院 工程技術研發中心, 長春 130033; 2. 長春光華學院 電氣信息學院, 長春 130033; 3. 長春理工大學 計算機科學技術學院, 長春 130022)

聚類分析是機器學習領域重要的無監督分類方法.k-means聚類算法具有思想簡單、收斂性好、易實現等優點, 在矢量量化、圖像壓縮和空間數據挖掘等領域應用廣泛.k-means算法通過不斷運行數據分配與中心更新兩個步驟優化目標函數值. 在分配步驟中,k-means算法將每個數據點分配給距離其最近的中心, 這需要計算所有數據與所有中心之間的距離, 計算復雜度較高. 針對該問題, 目前已提出了許多加速算法, 其中加速方式分為近似加速和精確加速兩種. 在k-means近似加速領域, Wang等[1]使用多個隨機投影樹建立聚類封閉, 提高了k-means算法在分配步驟中的效率和準確性; Sculley[2]引入了一種小批量采樣方法, 該方法可得到更好的收斂效果, 且在處理高維數據集時不會增加計算成本; Hu等[3]提出了一種從粗到細的搜索方法進行多級過濾, 測試數據中比標準k-means算法快約600倍； Fahim等[4]提出了一種距離排除準則, 在連續兩次迭代中, 點到中心的距離小于上一次迭代的距離, 則可排除剩余的距離計算, 該準則適用于大型數據集提速; Tsai等[5]利用連續指定次數迭代中不變的劃分數據進行加速; Ortegal等[6]通過計算中心的移動概率確定閥值, 排除了距離計算； Ortegal等[7]改進了該算法, 使用等距閾值改善其在大型數據集上的計算效率. 在k-means精確加速領域, Arthur等[8]通過選擇具有特定概率的隨機起始中心提高算法效率; Zhao等[9]在Hadoop平臺上運行k-means算法, 提升了高維數據的聚類效率; Lai等[10]基于距離不等式與相鄰迭代之間的移動距離提出了FKMCUCD算法; Pelleg等[11]提出了一種結構優化的方法, 使用k-d樹簡化最近鄰查詢步驟, 但當維數大于20時, 該算法的聚類效果不理想； Shu等[12]提出了一種Ballk-means算法, 通過引入球聚類和最近鄰聚類的思想創建了一種高效且自適應的k-means算法； 文獻[13-14]相繼提出了基于三角不等式的算法, 通過減少點到中心距離計算加速k-means算法.

Ding等[15]在文獻[13]算法和文獻[14]算法之間進行折中, 提出了陰陽k-means算法. 陰陽k-means 算法屬于精確k-means加速算法, 具有與k-means算法一致的迭代結果. 其通過中心分組及引入全局過濾器、組過濾器和局部過濾器排除數據與中心之間的距離計算. 與文獻[13]算法和文獻[14]算法相比, 陰陽k-means算法能繼續加速的前提是能在中心分組下整體進行距離排除判定, 與逐個中心判定相比可節約大量判斷操作. 但陰陽k-means并未利用數據的結構關系進行加速. 如果直接采用與陰陽k-means中類似的中心分組方法進行數據分組, 由于分組數據的分布半徑大于單個數據的分布半徑, 整體判定條件相比于單個數據更難滿足. 當整體判定失敗時, 數據分組將不再具有優勢, 因為陰陽k-means算法無法繼續進行更細粒度上的整體判定操作. 針對該問題, 本文在陰陽k-means算法的基礎上進行改進, 建立滿m叉樹將數據分組, 以分組后的葉子節點數據建立加權數據進行加權k-means迭代. 由于加權后數據半徑與單個數據半徑相同, 該方法進行距離排除判定時具有比陰陽k-means整體判定更高的成功概率, 可以進一步提升陰陽k-means算法的計算效率.

1 陰陽k-means算法

陰陽k-means算法通過三角不等式原理計算距離的上下界過濾數據與中心之間的距離計算, 并通過移動距離進行上下界的更新與估計. 設x為數據點,C表示聚類中心的集合,gi?C(i=1,2,…,k)為中心集合C的一個分組,b(x)為x的最佳分配聚類中心,d(x,b(x))表示x到最佳中心的距離,d(x,c)表示x到c的距離,b(x,gi)表示gi中x的最佳聚類中心標簽,δ(gi)表示每個組的最大移動幅度,lb(x,gi)表示除b(x)外所有中心之間的最短距離. 陰陽k-means算法利用

|d(x,b)-d(b,c)|≤d(x,c)≤d(x,b)+d(b,c)

(1)

進行距離過濾, 其中b,c表示兩個不同的聚類中心. 陰陽k-means算法設置三層過濾器進行距離排除操作. 首先, 進行全局過濾, 對于每個點x, 該算法通過保持上限ub(x)≥d(x,b(x))和全局下限lb(x)≤d(x,c)(?c∈C-b)完成全局過濾. 其次, 以到最近聚類中心的距離作為上界, 到第二近聚類中心的距離作為下界進行組過濾. 該步驟將k個簇分成t個組G={g1,g2,…,gt}, 其中每個gi∈G是一組集群, 將t設為不大于k/10的值. 最后, 將全局過濾條件應用于每個組. 設置局部過濾器, 找到新的b(x), 并利用到第二近中心的距離更新組下限lb(x,gi). 對于被組過濾器阻止的組, 用lb(x,gi)-δ(gi)更新下限lb(x,gi), 用d(x,b(x))更新上限ub(x). 在更新步驟利用中心更新公式更新陰陽k-means算法的中心.

陰陽k-means算法通過中心分組完成gi內所有中心的批量過濾操作, 如果過濾成功會使其比傳統的逐個中心判定比對操作計算量更小. 但其并未利用數據結構進行加速. 針對該問題, 本文提出一種加權數據的陰陽k-means聚類算法. 通過數據加權, 既完成了多個數據的統一判定與過濾操作, 同時, 加權數據本身由一個數據點代表多個數據點并未增大數據的半徑, 判定條件易滿足, 可以完成多個數據的同時判定操作.

2 改進陰陽k-means算法

2.1 基于滿m叉樹的數據加權聚類

2.1.1 數據加權

圖1 數據的分組過程Fig.1 Process of data grouping

本文用一種加權數據的方法提高陰陽k-means算法的速度. 該方法將原始數據集F={f1,f2,…,fM}進行k-means迭代, 建立滿m叉樹的數據結構. 設樹的節點度為m, 深度為h, 則共運行(h-1)層標準k-means算法, 第h層葉子節點的個數為m(h-1)個, 樹的葉子節點個數即為加權數據個數, 如圖1所示. 本文將最終加權數據個數r設為不大于|F|/10的最大整數.

2.1.2 數據加權聚類

本文設定對樹的每個節點進行3次k-means迭代, 得到加權后數據X={x1,x2,…,xr}與加權向量W=(w1,w2,…,wr), 再在更新步驟通過加權中心更新公式

(2)

對加權數據進行陰陽k-means迭代. 其中ci表示加權中心,Ai表示距離中心ci距離最近的所有加權數據點集合.

2.2 中心初始化

本文采用文獻[16]的中心初始化方法.

定義1如果對于中心cr, dis(p,cr)

圖2 c1和c2是p的有效中心, c3不是p的有效中心Fig.2 c1 and c2 are effetive centers for p, c3 is not an effective center for p

定義2如果中心c不是p的無效最近中心, 則中心c稱為數據點p的有效最近中心.

如圖2所示,c1和c2是p的有效中心. 雖然c3比c1更靠近p, 但是c2導致c3不滿足定義2, 所以c3不是p的有效中心. 有效中心可表示為

(3)

其中dis(p,c)表示下一次迭代中數據點p到中心的距離, UNCp表示點p的最近有效中心集合, average(dis(p,c))表示平均距離, max(dis(p,c))表示最大距離.

根據定義1和定義2為每個數據點建立鏈表, 在每次迭代期間, 根據式(3)選擇一個代入值最大的數據點作為下一個中心, 每次迭代后, 將更新每個數據點的“最近有效中心”鏈表, 通過此方法降低算法對初始中心的依賴.

2.3 算法流程

1) 利用式(3)初始化聚類中心.

3) 將t設為不大于k/10的值, 并滿足內存空間限制. 對初始聚類中心進行5次k-means迭代, 將其分為t個組G={g1,g2,…,gt}.

4) 對所有加權數據運行1次加權k-means算法, 對每個數據x, 設上限為ub(x)=d(x,b(x)), 下限lb(x,gi)為x和Gi中除b(x)外所有中心之間的最短距離(上限和下限分別為距離中心點第一和第二近的距離).

5) 利用式(2)更新中心, 計算每個中心的移動幅度δ(c), 并記錄每組的最大移動幅度δ(gi).

7) 設置局部過濾器. 對于每個剩余點x, 利用目前找到的第二近的中心過濾剩余中心, 計算x到過濾中心的距離, 找到新的b(x), 并用到第二近中心距離更新組下限lb(x,gi). 對于未通過過濾器的組, 用lb(x,gi)-δ(gi)更新下限lb(x,gi), 用d(x,b(x))更新ub(x).

8) 重復步驟5)～步驟7), 直到迭代結束.

9) 再對原數據集F進行5次陰陽k-means算法的迭代, 得到最終聚類結果.

3 實 驗

3.1 實驗環境與實驗數據

本文實驗的5組對比數據均來自UCI機器學習數據庫, 數據集信息列于表1. 實驗環境為Intel I-54200H 2.8 GHz雙核處理器, Windows10 64位操作系統, 8 GB內存, VS 2010開發平臺. 所有算法均使用C++語言實現.

表1 5組UCI數據集特征

3.2 實驗結果與分析

實驗分別測試k-means算法、本文算法、傳統陰陽k-means算法(陰陽-k)[15]、FKMCUCD算法[10]和Ballk-means (Ball-k)[12]算法的運行情況, 結果列于表2. 以k-means算法的運行速度為基準, 用SKM表示k-means算法的速度,Salgm表示其他聚類算法的速度,HKM表示k-means算法的函數值,Halgm表示其他聚類算法的函數值, 則加速比E和函數值誤差百分比I分別表示為

E=SKM/Salgm,

(4)

I=1-HKM/Halgm.

(5)

表2 不同算法在測試數據集上不同聚類個數下的運行結果

圖3 4種算法在不同數據集上的平均加速比Fig.3 Average speedup of four algorithms on different data sets

由表2可見, 只有本文算法與傳統陰陽k-means算法在所有測試條件下加速比均大于1, 表明這兩種算法能在所有測試條件下加速k-means算法, 具有廣泛的適用性. 加速算法Ballk-means與FKMCUCD在k值較大時具有較好的加速效果, 對于某些小k值, 加速比略低. 圖3為當聚類個數為10,20,30,50時4種算法在UCI數據集上的平均加速比. 由圖3可見, 在5組UCI數據集上, 本文算法的平均加速比始終保持最高, 平均加速比最高達59.4, 而其他算法的平均加速比最高為8.35. 本文算法的高加速比是因為本文算法在數據加權聚類過程中, 充分利用了數據的結構信息, 用加權數據代替臨近區域內數據點集, 大幅度縮減了距離比對與計算次數. 通過數據加權, 既完成了多個數據的統一判定與過濾操作, 同時, 加權數據本身由一個數據點代表多個數據點并未增大數據的半徑, 判定條件易滿足, 可以完成多個數據的同時判定操作.

表2的最后一列為本文算法函數值誤差百分數. 從數據結果可見, 在多數情況下, 本文算法與傳統陰陽k-means聚類(k-means與陰陽k-means算法結果一致)相比, 函數收斂精度基本相同或更高. 唯一一組誤差較大的數據為Kegg數據集, 其函數值誤差百分數為27.88%～33.22%. 在兩組數據Pen-digits與Gas中函數誤差始終不超過5.59%, 在LR數據集合上多數結果誤差不到10%. 在Page數據集合上具有比傳統陰陽k-means算法明顯更高的收斂精度, 優化幅度最高達284.26%. 測試精度結果表明, 雖然利用加權數據代表多個數據點降低了聚類的迭代精度, 但利用權向量進行加權陰陽k-means算法迭代在一定程度上克服了數據約簡導致的精度損失, 而且基于加權結果采用精確聚類迭代進一步提高了收斂精度.

綜上所述, 針對陰陽k-means算法聚類加速過程未利用數據自身相似性, 計算效率較低的問題, 本文提出了一種基于數據多層分解的陰陽k-means加速算法. 該算法根據數據相似性建立滿m叉樹結構逐層分解數據, 以樹結構各葉子節點中存儲的數據信息建立加權數據, 運行加權陰陽k-means算法得到收斂中心. 在原始數據中以加權數據收斂中心為初始化條件運行陰陽k-means算法進一步優化目標函數值. 與k-means、傳統陰陽k-means以及其他加速算法對比結果表明, 本文算法在不同數據集上始終具有較高的計算效率, 平均加速比最高達59.40, 而其他算法的平均加速比最高為8.35. 此外, 在多數測試條件下函數收斂精度誤差不到10%, 與傳統陰陽k-means算法精度基本相同.