李堯坤

(四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

面向數(shù)據(jù)規(guī)?？蓴U(kuò)展的并行優(yōu)化K-means算法

李堯坤

(四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

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

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

0 引言

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

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

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

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

使得下式取得最小值，

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

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

重新計(jì)算聚類樣本集S的每個(gè)樣本同Centers的距離，分配到距離最小類

更新Centers為每個(gè)類的均值向量，并記錄類中心移動(dòng)的偏移量絕對(duì)值之和offset

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

2 本文改進(jìn)的K-means算法

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

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

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

圖1

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

2.2 改進(jìn)的算法流程

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

3 實(shí)驗(yàn)設(shè)置及結(jié)果

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

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

表1 傳統(tǒng)K-means同本文算法運(yùn)行時(shí)間對(duì)比（s）

4 結(jié)語(yǔ)

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

[1] 王千，王成，馮振元，葉金鳳.K-means聚類算法研究綜述[J].電子設(shè)計(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] 周麗娟，王慧，王文伯，張寧.面向海量數(shù)據(jù)的并行K-means算法[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），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-），男，湖南郴州人，研究生，研究方向?yàn)槎嗝襟w計(jì)算

2014-11-18

2014-12-16