面向數據規模可擴展的并行優化K-means算法

李堯坤

(四川大學計算機學院，成都 610065）

面向數據規模可擴展的并行優化K-means算法

李堯坤

(四川大學計算機學院，成都 610065）

傳統的K-means算法迭代過程中需要加載全部的聚類樣本數據，并且更新類中心過程是非并行的。針對傳統K-means算法處理數據規模小和類中心更新慢的問題，提出一種改進的K-means算法，面向解決K-means單臺機器處理數據規模擴展問題，和處理器利用率低效問題。實驗驗證，該方法能夠高效地處理大規模數據聚類。

K-means；大規模；更新類中心；并行

0 引言

聚類是用于劃分空間中的數據方法，將相似的數據聚成相同簇，不相似的聚成不同簇，是數據挖掘、機器學習的基本工具。K-means算法是科研和應用中常用的聚類算法，是由Steinhaus于1955年，Lloyd于1957年Ball，Hall于1965年，McQueen于1967年各自獨立提出[1]。自K-means算法提出以來，許多研究者對它進行了改進和優化，主要包括:初始類中心選擇[2]、K-means算法并行化改造[3]、近似K-means算法。雖然K-means歷經改進，研究人員和工業界最常用的依然是Lloyd提出的經典的K-means算法框架，K-means的各種衍生版本一般用于特定的場合。商用聚類工具——CLUTO[4]，采用的也是經典K-means算法。近年來，隨著大數據的提出和研究應用需求的擴展，K-means作為大數據最為廣泛使用的基礎工具之一，得到了更為長足的發展，同時也面臨著新的挑戰——如何解決大規模數據的聚類問題。傳統的K-means算法需要加載所有聚類樣本到內存，當需要聚類的數據規模超出進程內存限制時，算法便不能運行，同時由于算法類中心更新過程是非并行的，處理器利用效率低。一些研究者提出了基于Hadoop Map-Reduce[5]的改進算法，能夠一定程度地解決大規模數據聚類問題，然而算法是基于Hadoop框架，必須先要架設Hadoop并且要求較高的硬件資源配置，否則因為Hadoop分布式框架本身的通信，調度開銷，甚至會低于單臺機器聚類效率。本文提出的算法可實現單臺機器上規模可擴展的和充分利用處理器處理效率的K-means算法。

1 傳統的K-means算法及背景

1.1 K-means的優化目標

對于給定的聚類任務樣本集合S=｛v1，v2，…，vn｝，vi∈Rd，K-means的優化目標就是找到K個劃分P=｛p1，p2，…，pk｝，對于任意vi，被分到K個劃分中的某一個pj，K個劃分的中心為：

使得下式取得最小值，

式（2）的意義是，找出K個劃分，使得每個劃分的成員向量與對應劃分均值向量差的平方和最小。已經證明最優化J（C）是一個NP-Hard問題，因而研究者從啟發式求解方法入手解決該問題。K-means是一種貪心思想的最優化J（C）的方法，初始類中心后，每次迭代重新分配樣本到歐氏距離最小的類中心所屬類，然后再更新類中心，直到類中心不再移動，收斂到固定的位置。

1.2 傳統K-means算法流程

重新計算聚類樣本集S的每個樣本同Centers的距離，分配到距離最小類

更新Centers為每個類的均值向量，并記錄類中心移動的偏移量絕對值之和offset

Until offset＜ξ//ξ為設定迭代停止的一個較小的閾值

2 本文改進的K-means算法

針對傳統K-means算法不能大規模聚類和更新類中心處理非并行問題，首先，將聚類數據預處理為二進制向量塊，按批次讀入樣本向量到內存更新類中心可以解決因數據規模大而不能運行的問題；其次，更新類中心過程，各個樣本向量同類中心間計算距離是獨立的，可以將其并行化處理，最大化利用處理器效率，更快地完成聚類。

2.1 數據預處理

預先將聚類樣本向量轉儲為二進制浮點形式,可以避免每次讀入數據從字符向量到浮點向量的解析開銷。同時分塊存儲,批量導入到內存,既可以解決數據規模擴展問題,同時保證高效地將數據加載到內存。設定二進制向量塊的最大文件長度為S_Size,讀入字符串表示的樣本向量并解析為浮點值表示向量寫入到向量塊文件，當超過S_Size時，另外開辟新的向量文件進行存儲。

圖1

每個文件塊的最大長度為S_Size，每一行存儲一個向量——浮點型的二進制值。整個文件塊存儲整數個向量直到所有向量空間超過S_Size時，另外開辟新的文件存儲。預處理后，便于后續算法快捷批次讀入向量數據到內存。

2.2 改進的算法流程

算法采用批次讀入聚類樣本到內存，并行計算更新類中心，可充分利用處理器和解決傳統K-means因聚類樣本數據量過大無法聚類問題。

3 實驗設置及結果

實驗環境為Windows7操作系統，處理器為i5-3230m（2核）4G內存筆記本電腦。算法基于.NET framework 4.0和C++實現。設定實驗參數2.1中S_Size=600M,算法中批次讀入內存向量最大占用內存為160M。實驗采用了數據規模為10^6，10^7，10^8 64維雙精度浮點向量，同傳統K-means進行實驗對比，類中心K=1000。

從表1可以看出本文處法能夠處理傳統K-means算法已經不能處理的10^8規模級別數據，驗證了本文算法對于數據規模的可擴展性；比較10^6和10^7數據，可看出本文算法大致快2倍，處理器為2核，說明充分利用了處理器效率，同時也說明本文算法改進使用硬盤存儲聚類樣本數據，批次導入內存帶來的額外開銷小，聚類數據規模較大情況下可以忽略。

表1 傳統K-means同本文算法運行時間對比（s）

4 結語

K-means算法是研究和應用常用到的基本工具，本文改進的K-means算法較傳統算法，解決了聚類數據規模可擴展問題，同時也優化了算法處理器效率利用低問題。相比在沒有Hadoop軟硬件平臺支撐的前提下，本文算法可應用到更廣泛的實際問題中。

[1] 王千，王成，馮振元，葉金鳳.K-means聚類算法研究綜述[J].電子設計工程，2012（07）

[2] Arthur,D.and Vassilvitskii,S.K-means++:the Advantages of Careful Seeding[J].Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms.Society for Industrial and Applied Mathematics Philadelphia,PA,USA.pp.1027～1035，2007

[3] W Zhao,H Ma,Q He.Cloud Computing[C].springer.2009

[4] Karypis Lab.http://glaros.dtc.umn.edu/gkhome/views/cluto

[5] 周麗娟，王慧，王文伯，張寧.面向海量數據的并行K-means算法[J].華中科技大學學報（自然科學版），2012（s1）

Parallel Optimization K-means Algorithm Facing the Data Size Scalable

LI Yao-kun
（College of Computer Science,Sichuan University,Chengdou 610065）

Traditional K-means algorithm need to load all the sample data into memory,and updating the class center is a non-parallel process.For the problem of the number of processing data is small and updating class centers with low speed in traditional K-means algorithm,proposes an improved K-means algorithm to solve the problems of processing data scale expansion and the processor utilization inefficient. Experiment shows the method can efficiently deal with large-scale data clustering.

K-means;Large-Scale;Updating Class Centers;Parallel

1007-1423（2015）02-0003-03

10.3969/j.issn.1007-1423.2015.02.001

李堯坤（1989-），男，湖南郴州人，研究生，研究方向為多媒體計算

2014-11-18

2014-12-16