面向數(shù)據(jù)規(guī)模可擴展的并行優(yōu)化K-means算法

李堯坤

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

面向數(shù)據(jù)規(guī)模可擴展的并行優(yōu)化K-means算法

李堯坤

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

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

K-means；大規(guī)模；更新類中心；并行

0 引言

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

1 傳統(tǒng)的K-means算法及背景

1.1 K-means的優(yōu)化目標

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

使得下式取得最小值，

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

1.2 傳統(tǒng)K-means算法流程

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

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

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

2 本文改進的K-means算法

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

2.1 數(shù)據(jù)預(yù)處理

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

圖1

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

2.2 改進的算法流程

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

3 實驗設(shè)置及結(jié)果

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

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

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

4 結(jié)語

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

[1] 王千，王成，馮振元，葉金鳳.K-means聚類算法研究綜述[J].電子設(shè)計工程，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] 周麗娟，王慧，王文伯，張寧.面向海量數(shù)據(jù)的并行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