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

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

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

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

一、聚類(lèi)分析基本理論

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

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

（1）K-Means算法

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

（2）K-Mediods算法

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

二、密度峰值聚類(lèi)算法

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

（一）分布式密度峰值聚類(lèi)算法

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

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

（二）分布式密度峰值聚類(lèi)算法冗余計(jì)算問(wèn)題分析

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

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

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

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

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

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

四、總結(jié)

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

參考文獻(xiàn)：

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

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