基于Spark的K-means改進(jìn)算法的并行化實(shí)現(xiàn)①

宋董飛, 徐 華

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院,無(wú)錫 214122)

引言

隨著移動(dòng)互聯(lián)網(wǎng)和物聯(lián)網(wǎng)技術(shù)的不斷發(fā)展,極大地豐富和便捷了人們的生活,但隨之也伴隨著巨量數(shù)據(jù)的產(chǎn)生. K-means作為典型的聚類算法,已很難適應(yīng)大數(shù)據(jù)環(huán)境下的數(shù)據(jù)處理要求,其缺點(diǎn)主要表現(xiàn)為[1]：(1)隨機(jī)選擇初始中心點(diǎn)易使算法陷入局部最優(yōu);(2)迭代過(guò)程中需要進(jìn)行大量冗余距離計(jì)算,增加算法復(fù)雜度; (3)面對(duì)海量數(shù)據(jù)集,傳統(tǒng)的串行K-means算法運(yùn)行效率低.

針對(duì)傳統(tǒng)K-means算法的缺點(diǎn),已有很多學(xué)者在K-means的基礎(chǔ)上提出了改進(jìn)措施. 文獻(xiàn)[2,3]引入通過(guò)引入canopy算法,對(duì)K-means算法進(jìn)行了優(yōu)化,利用canopy算法生成重疊子集,在生成的重疊子集中進(jìn)行聚類,同時(shí)文獻(xiàn)[2]提出了基于“最大最小原則”的canopy中心點(diǎn)選擇方法,解決了canopy選擇的盲目性與隨意性,提高了算法的分類準(zhǔn)確率,但在實(shí)際應(yīng)用中非常耗時(shí). 文獻(xiàn)[4]基于“距離最遠(yuǎn)的樣本點(diǎn)不可能分到同一個(gè)簇中”這一事實(shí),提出了最大距離法選取初始簇中心的K-means聚類算法,能夠選取質(zhì)量較好的初始中心點(diǎn),克服了傳統(tǒng)K-means算法聚類結(jié)果不穩(wěn)定和局部最優(yōu)等問(wèn)題. 文獻(xiàn)[5,6]分別利用Mapreduce框架和Spark框架,實(shí)現(xiàn)了改進(jìn)K-means算法的并行化,通過(guò)并行計(jì)算提高聚類速度,使其適用于海量數(shù)據(jù)聚類中.

基于以上研究,為了進(jìn)一步減少數(shù)據(jù)聚類迭代過(guò)程中的冗余計(jì)算,加快聚類速度,提高聚類準(zhǔn)確率,本文提出了SKDk-means (Spark based kd-tree K-means)并行聚類算法. 文獻(xiàn)[7]提出kd-tree數(shù)據(jù)結(jié)構(gòu),將其應(yīng)用在K-means迭代過(guò)程中,加快聚類速度. 受文獻(xiàn)[7]啟發(fā),本文在初始點(diǎn)選取階段引入kd-tree數(shù)據(jù)結(jié)構(gòu),改善初始中心點(diǎn)預(yù)選取算法,并在迭代過(guò)程中利用kdtree解決了聚類過(guò)程中距離冗余計(jì)算的問(wèn)題,同時(shí)將改進(jìn)后的算法部署在Spark平臺(tái)上,通過(guò)并行計(jì)算提高數(shù)據(jù)處理的速度. 本文實(shí)驗(yàn)分別以UCI標(biāo)準(zhǔn)數(shù)據(jù)集和人工產(chǎn)生的不同規(guī)模的數(shù)據(jù)集驗(yàn)證算法具有較好的聚類質(zhì)量和并行計(jì)算性能,更適合應(yīng)用于海量數(shù)據(jù)的聚類分析中.

1 基于kd-tree改進(jìn)的K-means聚類算法

1.1 kd-tree

kd-tree(k-dimensional tree)是由Bentley于1975年提出[8],k是空間數(shù)據(jù)對(duì)象的維度數(shù),在多維的空間數(shù)據(jù)結(jié)構(gòu)中,kd-tree常用來(lái)數(shù)據(jù)索引和數(shù)據(jù)查詢.

kd-tree的構(gòu)建思想[9]是：選擇數(shù)據(jù)對(duì)象方差值最大的維度作為分割維度,為了保證左右子樹平衡,在分割維度上選取數(shù)據(jù)的中值. 根據(jù)選取的維度和中值將k維數(shù)據(jù)空間劃分為兩個(gè)部分,小于等于中值的點(diǎn)劃分到左子樹,大于中值的點(diǎn)劃分到右子樹. 我們可以繼續(xù)分別對(duì)這兩個(gè)子k維空間進(jìn)行如上劃分,又會(huì)得到新的子空間,重復(fù)以上過(guò)程直到每個(gè)子空間都不能再劃分.

kd-tree上的最近鄰查找算法即在kd-tree中檢索與某一查詢點(diǎn)歐式距離最近的數(shù)據(jù)點(diǎn)[10]. kd-tree數(shù)最近鄰查找算法思想如下：從根節(jié)點(diǎn)遞歸地向下搜索,進(jìn)行二叉搜索; 搜索到葉子結(jié)點(diǎn),記為當(dāng)前最近鄰nearest; 進(jìn)行回溯搜索,如果超球面與父節(jié)點(diǎn)超平面相交,進(jìn)入相反的空間搜索,更新nearest,否則繼續(xù)向上回溯,回溯到根節(jié)點(diǎn),結(jié)束并返回最近鄰.

1.2 基于kd-tree的初始中心點(diǎn)選取算法

給出一組n個(gè)對(duì)象其中在N維空間中選擇數(shù)據(jù)對(duì)象方差最大的維度作為分割維度,分割值為該維度上坐標(biāo)的中值,這樣將數(shù)據(jù)集分割為左右兩個(gè)大致相等的超矩形. 然后在每個(gè)超矩形上遞歸的執(zhí)行分割,直到任何超矩形不再劃分為止.

該方法以方差最大維度上的坐標(biāo)中值進(jìn)行分割,所以每個(gè)框中的對(duì)象個(gè)數(shù)大致相同. 該屬性顯示,如果超矩形中的物體的密度比其他超矩形中的物體密度更高,則該超矩形的體積更小.

假設(shè)超矩形i中所有對(duì)象的平均值為mi,計(jì)算公式如下：

其中n表示超矩形中數(shù)據(jù)對(duì)象的個(gè)數(shù),xi表示超矩形中的數(shù)據(jù)對(duì)象.

超矩形的密度,顧名思義就是表示超矩形單元中數(shù)據(jù)對(duì)象的密集程度,我們用ρi表示,其定義如下：

其中,Ni表示超矩形單元內(nèi)數(shù)據(jù)對(duì)象數(shù)量;Vi表示超矩形的體積;dmax、dmin分別表示超矩形內(nèi)數(shù)據(jù)的最大值和最小值.

q個(gè)超矩形的密度表示為其對(duì)應(yīng)的超矩形中心表示為選擇初始中心方法如下：首先選擇密度最高的超矩形中心mi作為第一個(gè)選取的初始中心點(diǎn).

我們通過(guò)公式計(jì)算gi[11]來(lái)選擇第2個(gè)初始中心點(diǎn).選擇最大gi的超矩形中心mi作為第2個(gè)初始中心點(diǎn)

當(dāng)?shù)趖個(gè)初始中心點(diǎn)已經(jīng)被選擇,那通過(guò)下面的公式計(jì)算gi來(lái)選取第t+1個(gè)初始中心點(diǎn). 選擇滿足gi最大超矩形的mi作為第t+1個(gè)初始中心點(diǎn)：

算法描述如下：

算法1. 基于kd-tree的初始中心點(diǎn)選取算法.

2) forj=1,…,q計(jì)算超矩形的中心mi和密度ρi.

4) fort=2,…,k：

forj=1,…,q計(jì)算

第t個(gè)初始中心其中

1.3 基于kd-tree的K-means算法

在kd-tree中采用最近鄰查找思想,檢索kd-tree中與查詢點(diǎn)距離最近的數(shù)據(jù)點(diǎn),可以很快速的找到最佳點(diǎn),而不需要進(jìn)行過(guò)多的距離計(jì)算. 在K-means算法中,我們引入kd-tree這一數(shù)據(jù)結(jié)構(gòu),建立聚類中心點(diǎn)的kd-tree,然后采用最近鄰查找思想,將各數(shù)據(jù)點(diǎn)分配給距離最近的中心點(diǎn),很好地解決了K-means算法聚類迭代過(guò)程中距離冗余計(jì)算的問(wèn)題.

本文提出的基于kd-tree優(yōu)化的K-means聚類算法的基本思想是：首先應(yīng)用基于kd-tree改進(jìn)的初始中心點(diǎn)選取算法即算法1,選取出k個(gè)有效的初始聚類中心點(diǎn)然后建立聚類中心點(diǎn)集C的kd-tree,數(shù)據(jù)點(diǎn)依次遍歷kd-tree,采用最近鄰查找的思想,將數(shù)據(jù)點(diǎn)分配給距離最近的中心點(diǎn). 各數(shù)據(jù)點(diǎn)都分配給最近的聚類中心后,進(jìn)行全局的聚類中心點(diǎn)更新,將更新后的聚類中心點(diǎn)與原中心點(diǎn)比較,判斷是否收斂. 若不收斂則進(jìn)行迭代; 若收斂則退出迭代,輸出聚類結(jié)果.

算法描述如下：

算法2. 基于kd-tree優(yōu)化的K-means聚類算法.

輸出：k個(gè)最優(yōu)聚類結(jié)果簇.

1) 應(yīng)用算法1,選出k個(gè)有效的初始聚類中心點(diǎn)

2) 建立中心點(diǎn)的kd-tree.

3) 將數(shù)據(jù)集中每個(gè)點(diǎn)依次遍歷kd-tree：

① 從kd-tree根節(jié)點(diǎn)出發(fā),遞歸地向下搜索,如果xi的當(dāng)前維度上坐標(biāo)值小于分裂點(diǎn)的值,則進(jìn)入其左子樹進(jìn)行搜索,否則進(jìn)入到右子樹進(jìn)行搜索,直到葉節(jié)點(diǎn)為止,記錄下搜索路徑,將葉節(jié)點(diǎn)標(biāo)記為Nearest,計(jì)算葉節(jié)點(diǎn)與xi的距離Distance;

② 根據(jù)①中記錄的搜索路徑遞歸地向上回溯,計(jì)算搜索路徑上的每一個(gè)節(jié)點(diǎn)與目標(biāo)點(diǎn)的距離,如果其與目標(biāo)點(diǎn)xi的距離小于Distance,則更新此節(jié)點(diǎn)為最近點(diǎn)Nearest,同時(shí)更新Distance,比較Distance與xi到分裂軸的距離如果Distance比xi到分裂軸的距離大,則需要向此節(jié)點(diǎn)父節(jié)點(diǎn)的另一個(gè)分支進(jìn)行搜索; 否則繼續(xù)回溯,直到退回到根節(jié)點(diǎn),搜索結(jié)束,此時(shí)的Nearest即為xi的最近聚類中心.

4) 更新聚類中心點(diǎn),并計(jì)算數(shù)據(jù)對(duì)象的誤差平方和判斷是否收斂,若收斂則停止迭代; 否則進(jìn)入2) 重復(fù)以上步驟,直至算法收斂.

5) 輸出k個(gè)最優(yōu)聚類中心點(diǎn),完成聚類.

2 基于Spark的K-means算法并行化實(shí)現(xiàn)

2.1 Spark框架

Spark[12]由加州大學(xué)伯克利分校的AMP實(shí)驗(yàn)室開發(fā),在處理大規(guī)模數(shù)據(jù)時(shí),Spark表現(xiàn)出其特有的優(yōu)勢(shì).Spark通過(guò)引入內(nèi)存計(jì)算,在各計(jì)算節(jié)點(diǎn)內(nèi)存內(nèi)分布式緩存數(shù)據(jù)集,從而大大減少了磁盤I/O操作時(shí)間,這一特性使Spark特別適合運(yùn)用于需要多次迭代的機(jī)器學(xué)習(xí)算法中.

Spark運(yùn)行架構(gòu)如圖1所示. Spark可以高效的部署在一個(gè)計(jì)算節(jié)點(diǎn)到數(shù)千個(gè)計(jì)算節(jié)點(diǎn)之間,為了實(shí)現(xiàn)Spark集群在各個(gè)計(jì)算節(jié)點(diǎn)之間的通信與資源分配,Spark支持多種集群資源管理器(standalone、Mesos或Yarn). Spark context對(duì)象在主程序中負(fù)責(zé)總體調(diào)度,并可與集群管理器相連接,本文選擇的是Yarn模式.

圖1 Spark運(yùn)行架構(gòu)圖

2.2 初始點(diǎn)選取階段

基于kd-tree改進(jìn)的K-means算法改善了初始點(diǎn)選擇問(wèn)題,并減少了迭代過(guò)程中的距離計(jì)算,但kdtree的建立以及kd-tree的搜索都需要花費(fèi)很多的時(shí)間代價(jià),并不適用于海量數(shù)據(jù)的聚類. 本文利用Spark并行計(jì)算框架實(shí)現(xiàn)了基于kd-tree改進(jìn)的K-means算法,使其能應(yīng)用于海量數(shù)據(jù)聚類中. 基于Spark的kdtree優(yōu)化K-means算法主要分為兩個(gè)階段：初始點(diǎn)選取階段和基于kd-tree的K-means并行階段.

初始點(diǎn)選取階段,我們通過(guò)并行建樹和并行計(jì)算各超矩形屬性值,在確保初始聚類中心點(diǎn)選擇效果的同時(shí),減少初始點(diǎn)選擇的時(shí)間. 啟動(dòng)算法,集群從HDFS讀取數(shù)據(jù)集形成初始RDD0; RDD0啟動(dòng)map算子執(zhí)行Vectors.dense(),將原始文本數(shù)據(jù)轉(zhuǎn)化為可處理的向量數(shù)據(jù)鍵值對(duì),形成RDD1; RDD1啟動(dòng)map算子通過(guò)statistics.clostats計(jì)算數(shù)據(jù)方差最大的維度值,并形成(維度值,維度值上的數(shù)據(jù)值)形式的鍵值對(duì),保存為RDD2; RDD2啟動(dòng)reduceByKey、countByKey算子計(jì)算該維度上數(shù)據(jù)分割點(diǎn)split、該維度上數(shù)據(jù)個(gè)數(shù)count; RDD1啟動(dòng)map算子判斷各條數(shù)據(jù)劃分維度上的數(shù)據(jù)值與split的大小,并據(jù)此進(jìn)行左右子樹劃分,左子樹的鍵在原key后面添加0作為新的鍵,右子樹的鍵在原key后面添加1作為新鍵. 然后再依次對(duì)RDD1執(zhí)行上述算子,將左右子樹進(jìn)行劃分,每次循環(huán)的最后對(duì)相應(yīng)RDD執(zhí)行count函數(shù),計(jì)算出葉子節(jié)點(diǎn)個(gè)數(shù),當(dāng)葉子節(jié)點(diǎn)個(gè)數(shù)大于聚類個(gè)數(shù)k時(shí),停止劃分.這樣完成了kd-tree并行建樹過(guò)程.

RDD1啟動(dòng)countByKey計(jì)算各超矩形中包含數(shù)據(jù)的個(gè)數(shù),記為countKey. 對(duì)RDD1啟動(dòng)reduceBy Key算子,通過(guò)公式(1),可計(jì)算出各個(gè)葉超矩形的中心點(diǎn)形成RDDm. 對(duì)RDD1啟動(dòng)reduceByKey算子,通過(guò)公式(2)來(lái)計(jì)算出各超矩形的密度,形成RDDd. 對(duì)RDDd啟動(dòng)reduceByKey計(jì)算出密度最大的超矩形,并將其中心加入初始中心點(diǎn)集C中. 對(duì)于C中已有點(diǎn),RDDm啟動(dòng)mapValues算子,根據(jù)公式(4)計(jì)算出各超矩形的gi,選出最大的gi的超矩形中心加入C中,更新C繼續(xù)迭代計(jì)算. 當(dāng)C中點(diǎn)的個(gè)數(shù)為k時(shí),保存初始中心點(diǎn)數(shù)據(jù),程序結(jié)束. 初始中心點(diǎn)選取階段流程如圖2.

圖2 初始中心點(diǎn)選取流程圖

2.3 基于kd-tree的K-means并行計(jì)算階段

K-means算法利用kd-tree的最近鄰搜索,可以有效地減少迭代過(guò)程中不必要的距離計(jì)算,將各個(gè)數(shù)據(jù)點(diǎn)快速劃入所屬簇中,從而大大地加快了聚類速度. 各從節(jié)點(diǎn)間的并行計(jì)算,總體上是采用“map”和“reduce”的思想,并行計(jì)算流程圖如圖3所示.

圖3 SKDk-means并行聚類算法流程

算法開始,程序讀取初始中心點(diǎn)選取階段選取的中心點(diǎn)數(shù)據(jù),建立初始中心點(diǎn)的kd-tree,保存為center_tree,并將center_tree作為廣播變量發(fā)送給所有工作節(jié)點(diǎn). 程序讀取原始數(shù)據(jù)集保存為RDD_data,RDD_data啟動(dòng)map算子,map中的函數(shù)為kd-tree的最近鄰查找函數(shù)：首先比較數(shù)據(jù)點(diǎn)當(dāng)前坐標(biāo)是否小于分裂點(diǎn)的坐標(biāo),如果小于進(jìn)入左子樹搜索,否則進(jìn)入右子樹搜索,直到葉節(jié)點(diǎn)為止,標(biāo)記為Nearest,計(jì)算葉節(jié)點(diǎn)與數(shù)據(jù)點(diǎn)距離記為Nearest; 進(jìn)行回溯搜索,如果回溯點(diǎn)的超球面與父節(jié)點(diǎn)抄平面相交,進(jìn)入相反空間搜索,更新Nearest,否則繼續(xù)向上回溯,回溯到根節(jié)點(diǎn),返回Nearest. 數(shù)據(jù)集遍歷kd-tree,形成(Nearest,數(shù)據(jù)點(diǎn))形式的鍵值對(duì),記為RDD_kv. RDD_kv啟動(dòng)reduceByKey算子,計(jì)算出新的聚類中心,并計(jì)算誤差平方和判斷是否收斂,若不收斂則建立新聚類中心的kd-tree,進(jìn)行迭代; 若收斂則輸出聚類結(jié)果.

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境、實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)采用阿里云平臺(tái)的服務(wù)器,創(chuàng)建了一個(gè)Master節(jié)點(diǎn),6個(gè)Slave節(jié)點(diǎn). Master配置為8 G內(nèi)存,80 G硬盤; Slave配置為8 G內(nèi)存,160 G硬盤.Hadoop版本為2.7.2,Spark版本為2.0.2.

實(shí)驗(yàn)測(cè)試數(shù)據(jù)利用UCI[13]數(shù)據(jù)集下的Iris、Wine、Ecoli來(lái)驗(yàn)證算法的有效性,數(shù)據(jù)集詳細(xì)情況如表所示.為了驗(yàn)證算法的并行效果,采用了人工數(shù)據(jù)集Data1～4,數(shù)據(jù)集詳細(xì)信息如表1和表2所示.

表1 實(shí)驗(yàn)測(cè)試數(shù)據(jù)集

表2 人工數(shù)據(jù)集Data1～4

為了測(cè)試SKDk-means算法的整體性能,采用以下評(píng)價(jià)指標(biāo)：準(zhǔn)確率、加速比(Sizeup)、擴(kuò)展比(Scaleup).

3.2 實(shí)驗(yàn)結(jié)果

1) 算法準(zhǔn)確度

為了驗(yàn)證算法的有效性,利用Iris、wine、Ecoli數(shù)據(jù)集進(jìn)行20次實(shí)驗(yàn),取20次實(shí)驗(yàn)的平均值為最終值. 在傳統(tǒng)k-means算法中,由于每次聚類初始中心為隨機(jī)選擇,聚類效果不穩(wěn)定,迭代次數(shù)較多,而本文算法優(yōu)化了初始中心點(diǎn)的選擇,擁有十分穩(wěn)定的聚類結(jié)果. 由表3可知,文本算法正確率高于傳統(tǒng)k-means算法.

表3 數(shù)據(jù)集測(cè)試結(jié)果

2) 算法擴(kuò)展性

為了分析算法在Spark框架下并行執(zhí)行的性能,需要計(jì)算算法執(zhí)行的加速比. 加速比是用來(lái)衡量程序執(zhí)行并行化的重要指標(biāo). 算法的加速比曲線如圖4所示. 在數(shù)據(jù)量較小時(shí),隨著節(jié)點(diǎn)數(shù)的增加,加速比開始時(shí)線性增加,后漸漸趨于平緩或逐漸下降,這是因?yàn)楫?dāng)數(shù)據(jù)規(guī)模較小時(shí),數(shù)據(jù)量遠(yuǎn)小于集群能夠處理的數(shù)據(jù)量,這時(shí)再將數(shù)據(jù)分成很多小塊發(fā)送給各子節(jié)點(diǎn),隨著子節(jié)點(diǎn)數(shù)目增加,集群運(yùn)行時(shí)間、任務(wù)調(diào)度時(shí)間、數(shù)據(jù)通信時(shí)間增加,降低了計(jì)算速度,此時(shí)并行效果不佳;數(shù)據(jù)量較大時(shí),加速比隨著節(jié)點(diǎn)數(shù)增加線性上升,雖然距離“理想加速比”這個(gè)理想狀態(tài)還很遠(yuǎn),但此時(shí)的并行效果已很明顯. 這說(shuō)明,數(shù)據(jù)規(guī)模越大,SKDkmeans算法的處理效率越高,聚類效果越明顯.

圖4 SKDk-means算法的加速比

當(dāng)集群中的計(jì)算節(jié)點(diǎn)的數(shù)目不斷增加時(shí),并行算法的加速比并不能無(wú)限地增大,此時(shí)僅用“加速比”已不能反映集群的利用率,因此引入并行算法效率(擴(kuò)展比)的概念. 如圖5所示,數(shù)據(jù)量較小時(shí)擴(kuò)展比下降很快,此時(shí)集群得不到很好的利用; 當(dāng)數(shù)據(jù)量增大時(shí),擴(kuò)展比下降速率相對(duì)趨緩,并逐漸趨于穩(wěn)定. 綜合算法的加速比和擴(kuò)展比,樣本規(guī)模越大,SKDk-means算法的處理效率越高,聚類效果越明顯.

圖5 SKDk-means算法的擴(kuò)展比

4 結(jié)束語(yǔ)

本文針對(duì)傳統(tǒng)K-means算法隨機(jī)選擇初始點(diǎn)及迭代過(guò)程中冗余距離計(jì)算問(wèn)題,通過(guò)引入kd-tree數(shù)據(jù)結(jié)構(gòu),對(duì)算法進(jìn)行了改進(jìn),并將改進(jìn)后的算法應(yīng)用于Spark大數(shù)據(jù)計(jì)算框架,實(shí)現(xiàn)了算法的并行化. 實(shí)驗(yàn)驗(yàn)證了該算法具有較高的聚類準(zhǔn)確率,并且具有優(yōu)良的加速比和擴(kuò)展比,適合應(yīng)用于海量數(shù)據(jù)聚類中.

1 孫吉貴,劉杰,趙連宇. 聚類算法研究. 軟件學(xué)報(bào),2008,19(1)：48-61.

2 毛典輝. 基于MapReduce的Canopy-Kmeans改進(jìn)算法. 計(jì)算機(jī)工程與應(yīng)用,2012,48(27)：22-26,68. [doi：10. 3778/ j.issn.1002-8331.2012.27.005]

3 衣治安,王月. 基于MapReduce的K_means并行算法及改進(jìn). 計(jì)算機(jī)系統(tǒng)應(yīng)用,2015,24(6)：188-192.

4 翟東海,魚江,高飛,等. 最大距離法選取初始簇中心的K-means文本聚類算法的研究. 計(jì)算機(jī)應(yīng)用研究,2014,31(3)：713-715,719.

5 張石磊,武裝. 一種基于Hadoop云計(jì)算平臺(tái)的聚類算法優(yōu)化的研究. 計(jì)算機(jī)科學(xué),2012,39(S2)：115-118.

6 劉鵬,滕家雨,張國(guó)鵬,等. 基于Spark的大規(guī)模文本kmeans并行聚類算法. 第二屆CCF大數(shù)據(jù)學(xué)術(shù)會(huì)議論文集. 北京,中國(guó). 2014. 1-11.

7 Tiwari S,Solanki T. An optimized approach for k-means clustering. 9th International ICST Conference on Heterogeneous Networking for Quality,Reliability,Security and Robustness. 2013. 5-7.

8 Bentley JL. Multidimensional binary search trees used for associative searching. Communications of the ACM,1975,18(9)：509-517. [doi：10.1145/361002.361007]

9 陳曉康,劉竹松. 基于改進(jìn)Kd-Tree構(gòu)建算法的k近鄰查詢. 廣東工業(yè)大學(xué)學(xué)報(bào),2014,31(3)：119-123.

10 Panigrahy R. An improved algorithm finding nearest neighbor using Kd-trees. Proceedings of the 8th Latin American Conference on Theoretical informatics. Búzios,Brazil. 2008. 387-398.

11 Redmond SJ,Heneghan C. A method for initialising the K-means clustering algorithm using Kd-trees. Pattern Recognition Letters,2007,28(8)：965-973. [doi：10. 1016/j.patrec.2007.01.001]

12 Zaharia M,Chowdhury M,Franklin MJ,et al. Spark：Cluster computing with working sets. Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing.Boston,MA,USA. 2010. 10.

13 UCI. UCI machine learning repository. http：//archive.ics.uci.edu/ml,2015-03-30.