基于大數(shù)據(jù)的分布式K-means聚類算法的研究

摘 要：如何能夠使用數(shù)據(jù)挖掘方法快速對高維大規(guī)模數(shù)據(jù)進行分析和信息提取成為現(xiàn)今一個熱門課題。基于此，本文針對當(dāng)前密度峰值聚類算法的高復(fù)雜度和高計算量等問題，使用云計算框架MapReduce，研究了一種基于z值的分布式密度峰值聚類算法（DP-z）。該算法利用空間z填充曲線將高維數(shù)據(jù)集映射到一維空間上，根據(jù)數(shù)據(jù)點的z值信息對數(shù)據(jù)集進行分組。為了能夠得到正確的聚類結(jié)果，再對分組間數(shù)據(jù)進行交互，然后進行并行計算。

關(guān)鍵詞：聚類分；分布式計算；大數(shù)據(jù)

通過理論分析可知，DP-z算法與原始密度峰值聚類算法相比，在得到聚類結(jié)果相同的情況下能夠有效的提高算法執(zhí)行效率。本文在Hadoop開源云計算平臺上，設(shè)計并實現(xiàn)了DP-z算法，并通過對比實驗，驗證了本文研究方法的有效性。

一、聚類分析基本理論

聚類是一個把數(shù)據(jù)對象分成多個簇的過程，使得簇內(nèi)之間對象的相識性大于其他簇中的對象。聚類分析方法作為數(shù)據(jù)挖掘的一種常用方法，已經(jīng)被廣泛應(yīng)用于許多領(lǐng)域，例如生物，醫(yī)學(xué)，智能商務(wù)和web搜素等等。在某些應(yīng)用中，聚類分析又稱為數(shù)據(jù)分割，它根據(jù)數(shù)據(jù)之間的相似性將大型數(shù)據(jù)集劃分為簇。聚類還可以進行離散點的檢測，也就是離群點（遠離任意簇的點）。

基于劃分的聚類算法是比較常用的聚類算法。此思想是將數(shù)據(jù)對象劃分為分離的簇。典型的基于劃分的聚類算法有K-Means算法，K-Mediods算法，PAM算法等。

（1）K-Means算法

K-Means算法是一種基于形心技術(shù)對數(shù)據(jù)進行劃分的算法。從理論上講，簇形心就是它的中心點。K-Means算法思想：事先確定類的個數(shù)K，隨機選取初始點為質(zhì)心，計算每個樣本與質(zhì)心之間的距離，將點歸到離它最近的質(zhì)心。隨后，重新計算每個類的質(zhì)心，重復(fù)操作，知道質(zhì)心不在發(fā)生變化。K-Means算法實現(xiàn)簡單且廣泛，但也存在著相應(yīng)的弊端，需要事先指點K值，但很多情況下，K值的估計相對困難一些。其次K-Means算法對初始值的選取相對敏感，不同的初始值的選取會產(chǎn)生不同的聚類效果。

（2）K-Mediods算法

K-Mediods算法是對K-Means算法的一種改進。算法主要思想為：首先選取一組聚類樣本作為中心點，每個中心對應(yīng)一個簇，計算各個樣本到各個中心點的聚類，將樣本點放入距離中心點最近的簇中。計算各個簇中，距離簇內(nèi)各樣本點距離的絕對誤差最小的點，作為新的中心點，如果新的中心點原來的中心點相同，算法結(jié)束，不相同執(zhí)行計算每個中心點。

二、密度峰值聚類算法

在密度峰值聚類算法的算法思想中每個點有兩個屬性：（1）密度值ρ；（2）斥群值δ（與密度值比自己大的點的距離的最小值）。密度值ρ越大說明該點越有可能是聚類的密度中心，斥群值δ越大說明該點越有可能代表一個新的聚類，因為當(dāng)某點到比該點密度大的點距離非常遠時，該點到密度比它大的點之間的空間范圍內(nèi)點的稠密程度都比該點附近范圍內(nèi)的點稠密程度低。在空間數(shù)據(jù)分布中，簇與簇之間往往有低密度區(qū)進行區(qū)分，因此斥群值δ越大說明該點越有可能代表一個新的聚類。由此可得只有當(dāng)密度值ρ和斥群值δ都較大的時候，該點才可能是某一個聚類的密度中心點。

（一）分布式密度峰值聚類算法

數(shù)據(jù)對象o的密度值ρo的計算需要知道點o到數(shù)據(jù)集中其余所有點j∈S的距離doj，然后判斷其距離是否小于dc，進而決定其密度值是否加1。因此，只要在MapReduce集群中分布式計算出數(shù)據(jù)集中所有點對之間的距離，即可得到每個點的密度值ρ。

分布式計算每個點的密度值ρ總共需要兩個MapReduce作業(yè)，第一個MapReduce用來計算數(shù)據(jù)集中所有點對之間的距離，并判斷其距離關(guān)系是否小于dc，由于點對之間的距離的計算分布在不同機器上，導(dǎo)致每個點的dc范圍內(nèi)附近的點的個數(shù)也分布在不同機器上，因此需要第二個MapReduce作業(yè)來對dc范圍內(nèi)點的個數(shù)進行合并，得到最終的密度值ρ。

（二）分布式密度峰值聚類算法冗余計算問題分析

為了提高DPC算法的執(zhí)行效率，文獻研究一種對基本DPC算法的改進算法，并通過分布式結(jié)構(gòu)來實現(xiàn)，稱為高效的分布式密度峰值聚類算法（EDDPC）。但是由于這種方法在數(shù)據(jù)復(fù)制方面所存在的問題導(dǎo)致其大量的冗余復(fù)制和計算開銷。

2-1 EDDPC的dc復(fù)制方案示例

其中pi，pj是分組Pi，Pj的種子點，這樣可以將相鄰組在分界線dc范圍內(nèi)的點相互復(fù)制，從而在組內(nèi)計算時能夠得到正確的密度值ρ。但是該復(fù)制方法可能會導(dǎo)致如圖2-1所示問題，o2所在區(qū)域則為多余復(fù)制，同時也因為冗余的復(fù)制，導(dǎo)致在組內(nèi)計算每個點的密度值ρ時也造成了冗余的計算開銷。

三、基于隨機抽樣的K-Means算法優(yōu)化

基于最大最小距離的K-Means算法，雖然對尋找初始中心點的準(zhǔn)確性和穩(wěn)定性進行了優(yōu)化，但是一個初始中心點的選擇，都需要掃描整個數(shù)據(jù)集，但是在數(shù)據(jù)量非常大的場景下，會因為迭代計算次數(shù)過多而導(dǎo)致執(zhí)行時間過長，所以考慮采用抽樣技術(shù)的方法來降低掃描數(shù)據(jù)的次數(shù)，降低程序執(zhí)行時間的復(fù)雜度。在使用抽樣技術(shù)的時候，應(yīng)當(dāng)注意選擇的樣本要具有代表性和規(guī)模上的簡約性，這樣才能發(fā)揮最大最小距離算法的優(yōu)勢，雖然樣本量大，準(zhǔn)確性高，但是效率低；如果樣本量小，準(zhǔn)確性就會降低。因此需要找到合適的初始中心點，從而很好地逼近全局最小值。因此，合理選取聚類中心可以避免陷入局部最優(yōu)并且能夠減少算法的迭代次數(shù)，而采取隨機樣本抽樣的最大最小距離法能夠很好解決該問題。

通過以上分析，可見目前密度峰值聚類及其改進算法中存在大量的冗余復(fù)制和計算效率不高等問題。基于此，為了提高分布式密度峰值聚類算法的性能，減少分布式環(huán)境中數(shù)據(jù)之間的通信開銷和冗余的計算開銷，本文根據(jù)空間z填充曲線和高維數(shù)據(jù)點z值攜帶點位置信息的特點研究一種基于z值的分布式密度峰值聚類算法，并使用基于云計算開發(fā)框架Hadoop實現(xiàn)基于z值的分布式密度峰值聚類算法。

四、總結(jié)

針對密度峰值聚類算法處理高維大規(guī)模數(shù)據(jù)集所存在的運行時間長，效率低，計算開銷大等問題研究了一種基于z值的分布式密度峰值聚類算法，利用z空間曲線將高維空間中的點映射到一維坐標(biāo)系中，并通過分組間數(shù)據(jù)進行交互，在分組間數(shù)據(jù)交互時采用過濾策略，然后并行計算，減少大量無效距離計算和數(shù)據(jù)傳輸開銷，從而提高算法執(zhí)行效率。

參考文獻：

[1]石鳳貴.地方技能型高水平大學(xué)《軟件建模技術(shù)》課程知識體系建設(shè)研究[J].現(xiàn)代計算機，2021（20）：103-107.

[2]田宇，趙昶宇.軟件建模技術(shù)在嵌入式軟件中的研究與應(yīng)用[J].科技與創(chuàng)新，2021（05）：165-166+169.