摘要：

隨著電力通信技術(shù)的發(fā)展，產(chǎn)生了大量分布式電力通信子系統(tǒng)以及海量電力通信數(shù)據(jù)，在海量數(shù)據(jù)中挖掘重要信息變得十分重要。聚類分析作為數(shù)據(jù)并行化處理和信息挖掘的一個有效手段，在電力通信中得到了廣泛的應(yīng)用。然而，傳統(tǒng)聚類算法在處理海量電力數(shù)據(jù)時已不能滿足時間性能的要求。針對這一問題，提出了一種基于MapReduce模型的并行化k-medoids聚類算法，首先采用基于密度的聚類思想對k-medoids算法初始點的選取策略進(jìn)行優(yōu)化，并利用Hadoop平臺下的MapReduce編程框架實現(xiàn)了算法的并行化處理。實驗結(jié)果表明，改進(jìn)的并行化聚類算法與其他算法相比，減少了聚類時間，提高了聚類精度，有利于對電力數(shù)據(jù)的有效分析和利用

0 引言

隨著電力通信網(wǎng)絡(luò)以功能為中心持續(xù)性發(fā)展，產(chǎn)生了大量分專業(yè)、分功能和分管理域的運維管理系統(tǒng)，進(jìn)而導(dǎo)致大量電力數(shù)據(jù)孤島的產(chǎn)生。如何利用分布式系統(tǒng)更好地處理這些數(shù)據(jù)量巨大且類型復(fù)雜的電力通信運維數(shù)據(jù)已成為研究的熱點問題。聚類分析作為數(shù)據(jù)處理的一個有效手段，支持對大量無序分散數(shù)據(jù)進(jìn)行整合分類從而進(jìn)行更深層次的關(guān)聯(lián)性分析或者數(shù)據(jù)挖掘，在電力通信網(wǎng)絡(luò)中得到越來越廣泛的應(yīng)用。同時，分布式系統(tǒng)中并行化處理機(jī)制因其優(yōu)秀的靈活性和高效性逐漸成為數(shù)據(jù)挖掘的一個重要研究方向。

國內(nèi)外學(xué)者也越來越對這方面加大關(guān)注，文獻(xiàn)[1]提出了一種基于DBSACN算法的并行優(yōu)化的聚類算法。文獻(xiàn)[2]中通過計算距離選擇最中心的k個數(shù)據(jù)點作為初始聚類中心，然后用k-medoids算法進(jìn)行迭代聚類，提高了聚類效果，但不適合處理大規(guī)模數(shù)據(jù)；文獻(xiàn)[3]提出了一種蟻群 k-medoids 融合聚類算法，該算法不需要人為確定類簇數(shù)目和初始聚類中心，提高了聚類效果，但也僅只適用于小型數(shù)據(jù)集；文獻(xiàn)[4]采用基于粒計算的聚類算法，該算法在初始聚類中心的選取過程中的計算量較大，且在處理大規(guī)模數(shù)據(jù)時存在時延問題；文獻(xiàn)[5]提出了將局部搜索過程嵌入到迭代局部搜索過程中的方法，顯著減少了計算時間。文獻(xiàn)[6]在Hadoop平臺上實現(xiàn)了傳統(tǒng)k-medoids聚類算法的并行化處理，減少了聚類時間，但在初始聚類中心的選取機(jī)制上沒有進(jìn)行改進(jìn)，沒有提高聚類效果；文獻(xiàn)[7]采用基于核的自適應(yīng)聚類算法，克服了k-medoids 的初值敏感問題，但是沒有降低算法的時間復(fù)雜度。

綜上所述，k-medoids聚類算法存在初始值敏感、運行速度慢、時間復(fù)雜度較高等問題，需要對k-medoids算法中初始點選取以及并行化方式進(jìn)行算法優(yōu)化設(shè)計。

1 k-medoids聚類初始點選取改進(jìn)機(jī)制

k-medoids算法是一種基于劃分的聚類算法，具有簡單、收斂速度快以及對噪聲點不敏感等優(yōu)點，因此在模式識別、數(shù)據(jù)挖掘等領(lǐng)域都得到了廣泛的應(yīng)用。k-medoids算法初始中心點的選取十分重要，如果初始中心點選擇的是離群點時，就會導(dǎo)致由離群點算出的質(zhì)心會偏離整個簇，造成數(shù)據(jù)分析不正確；如果選擇的初始中心點離得太近，就會顯著增加計算的時間消耗。因此本文算法首先對初始中心點的選取進(jìn)行優(yōu)化。基于密度的聚類可以很好地分離簇和環(huán)境噪聲，所以本文采用基于密度的聚類思想，盡量減少噪聲數(shù)據(jù)對選取初始點的影響。

定義1：點密度是對于數(shù)據(jù)集U中的數(shù)據(jù)集的樣本點x，以x為球心，某一正數(shù)r為半徑的球形域中所包含樣本點的個數(shù)，記作Dens(x)。其中：

本文算法中，首先對每個數(shù)據(jù)點并行計算點密度，并將點密度作為該數(shù)據(jù)點的一個屬性。選取初始聚類中心的具體步驟如下：

(1)計算數(shù)據(jù)集中m個數(shù)據(jù)點之間的距離。

(2)計算每個樣本點的點密度Dens(xi)以及均值點密度AvgDens，將點密度大于AvgDens的點即核心點存入集合T中，并記錄其簇中所包含的數(shù)據(jù)點。

(3)合并所有具有公共核心點的簇。

(4)計算各個簇的類簇密度CDens(ci)，選擇其中k個較大密度的簇，計算其中心點，即為初始聚類中心。

類簇中心點的計算方法如下：假設(shè)有一個類簇ci包含m個數(shù)據(jù)點{x1，x2，…，xm}，則其中心點ni按如式(5)計算：

經(jīng)過上述步驟，可以優(yōu)化初始聚類中心點的選取，使之后的聚類迭代運算更加有效，降低搜索范圍，大大減少搜索指派的時間。

2 k-medoids聚類算法并行化設(shè)計策略

本文針對k-medoids算法具有初始點選取復(fù)雜、聚類迭代時間久、中心點選取消耗資源過多等缺點，使用Hadoop平臺下的MapReduce編程框架對算法進(jìn)行初始點的點密度計算選取并行化、非中心點分配并行化和中心點更新并行化等方面的改進(jìn)。MapReduce分為Map(映射)和Reduce(化簡)兩部分操作，使用MapReduce實現(xiàn)算法并行化關(guān)鍵在于Map函數(shù)和Reduce函數(shù)的設(shè)計。其中Map函數(shù)將可并行執(zhí)行的多個任務(wù)映射到多個計算節(jié)點，多個計算節(jié)點對各自被分派的任務(wù)并行進(jìn)行處理，Reduce函數(shù)則是在各計算節(jié)點處理結(jié)束后，將計算結(jié)果返回給主進(jìn)程進(jìn)行匯總。

2.1 點密度計算并行化策略

在點密度的計算中，由于一個數(shù)據(jù)點的點密度對其他數(shù)據(jù)點的點密度沒有影響，所以該計算過程是可以并行化的。使用MultithreadedMapper在一個JVM進(jìn)程里以多線程的方式同時運行多個Mapper，每個線程實例化一個Mapper對象，各個線程并發(fā)執(zhí)行。主進(jìn)程把數(shù)據(jù)點分派給若干個不同的計算節(jié)點進(jìn)行處理，計算節(jié)點將數(shù)據(jù)平均分成k份，且有k個線程，每個線程中的數(shù)據(jù)點都與數(shù)據(jù)集中所有點進(jìn)行距離計算，進(jìn)而計算出點密度，最后通過Reduce函數(shù)將計算結(jié)果匯總并輸出。并行處理使得點密度計算所用時間大大減少，提高了算法的執(zhí)行效率。

2.2 非中心點分配及中心點更新并行化策略

非中心點分配階段的主要工作是計算各數(shù)據(jù)點到每個中心點的距離，由于每個數(shù)據(jù)點跟各個中心點距離的計算互不影響，所以該計算過程也是可并行化的。此階段的MapReduce化過程中，Map函數(shù)主要負(fù)責(zé)將數(shù)據(jù)集里除中心點外的每一個樣本點分配給與其距離最近的聚類中心，Reduce函數(shù)則負(fù)責(zé)通過計算更新每一個簇的中心點，按照這個原則迭代下去一直到達(dá)到設(shè)定閾值。主進(jìn)程利用Map函數(shù)把非中心點分配的任務(wù)分派給若干個計算節(jié)點，每個計算節(jié)點采用基于Round-Robin的并行化分配策略。首先把每一個數(shù)據(jù)點看作一個請求，輪詢地分配給不同的線程，對非中心點和每一個中心點的距離進(jìn)行計算，找出最小的距離，然后把該非中心點指派給最小距離所對應(yīng)的中心點。

因為輪詢調(diào)度算法是假設(shè)所有服務(wù)器中的處理性能都是相同，并不關(guān)心每臺服務(wù)器當(dāng)前的計算速度和響應(yīng)速度。因此當(dāng)用戶發(fā)出請求時，如果服務(wù)間隔的時間變化較大的時候，那么Round-Robin調(diào)度算法是非常容易導(dǎo)致服務(wù)器之間的負(fù)載發(fā)生不平衡表現(xiàn)。而本文中所運用的每個數(shù)據(jù)點都是平等的，所以不會造成服務(wù)器分配任務(wù)不均的問題。因此基于Round-Robin的策略是可行的。

本文算法在實現(xiàn)聚類的過程中經(jīng)歷了兩次并行化劃分，分別是非中心點分配和中心點更新過程。這兩次并行化過程是周而復(fù)始的，直到滿足程序退出的條件才會終止循環(huán)。

3 仿真實驗與結(jié)果分析

仿真實驗分別使用本文算法、DBSCAN并行化算法[1]和k-medoids并行化算法[8]進(jìn)行對比試驗，證明各個算法的優(yōu)劣性。為了證明本文算法的有效性，實驗將分析不同算法的聚類時間、聚類準(zhǔn)確度以及增加線程數(shù)之后的時間消耗。實驗將在兩種類型的數(shù)據(jù)集上進(jìn)行測試：

(1)電力數(shù)據(jù)集。電力通信數(shù)據(jù)的屬性有設(shè)備狀態(tài)、設(shè)備資產(chǎn)、網(wǎng)絡(luò)拓?fù)涞龋鋽?shù)據(jù)量約為1 GB。

(2)公有數(shù)據(jù)集。分別為200數(shù)量級的Northix、1 000數(shù)量級的DSA、5 000數(shù)量級的SSC和10 000數(shù)量級的GPSS。

3.1 電力數(shù)據(jù)集實驗結(jié)果分析

實驗首先設(shè)置6個線程對數(shù)據(jù)集進(jìn)行處理，三種算法對電力數(shù)據(jù)進(jìn)行聚類的結(jié)果見表1。其中k-medoids并行化算法[8]采用標(biāo)簽共現(xiàn)原則對初始點選取進(jìn)行改進(jìn)，但沒有考慮線程的分配方式，因此其執(zhí)行效率最差；DBSCAN算法考慮到了初始點的選取，并采用動態(tài)分配策略實現(xiàn)并行化，但在計算動態(tài)分配過程中增加了一定消耗，因此聚類準(zhǔn)確度和執(zhí)行效率都略有提升；本文所提出的算法，既考慮了初始點的合理選取，同時采用簡單有效的并行化分配策略，以減少計算和過多資源占用，因此相對于k-medoids并行化算法和DBSCAN并行化算法執(zhí)行效率大幅提升，準(zhǔn)確度也有所提高。

然后增加線程處理器的數(shù)量至8個，得到下表的聚類結(jié)果，見表2。

由表2可得，使用8個線程時，本文算法比k-medoids并行化算法執(zhí)行時間快了42.64%，比DBSCAN并行化算法快了24.70%。

各類算法增加線程后所用時間相比原算法減少的百分比如圖1。

由圖1可知，k-medoids并行化算法減少了10.20%，DBSCAN并行化算法減少了1.68%，本文算法減少了16.13%，說明本文算法在線程數(shù)增加時，可以更有效地減少運算時間，提高執(zhí)行效率。

3.2 公有數(shù)據(jù)集實驗結(jié)果分析

基于Northix、DSA、SSC和GPSS數(shù)據(jù)集使用5個線程實現(xiàn)算法的聚類準(zhǔn)確度比較見表3。

本文算法的聚類準(zhǔn)