李媛媛,孫玉強,晁 亞,劉 陽
(1.常州大學(xué) 信息科學(xué)與工程學(xué)院,江蘇 常州 213164; 2.中國電建 上海電力環(huán)保設(shè)備制造總廠有限公司,上海 201900)
云環(huán)境下的高效K-Medoids并行算法
李媛媛1,孫玉強1,晁 亞1,劉 陽2
(1.常州大學(xué) 信息科學(xué)與工程學(xué)院,江蘇 常州 213164; 2.中國電建 上海電力環(huán)保設(shè)備制造總廠有限公司,上海 201900)
傳統(tǒng)聚類算法K-Medoids對初始點的選擇具有隨機性,容易產(chǎn)生局部最優(yōu)解;替換聚類中心時采用的全局順序替換策略降低了算法的執(zhí)行效率;同時難以適應(yīng)海量數(shù)據(jù)的運算;針對上述問題,提出了一種云環(huán)境下的改進K-Medoids算法,該改進算法結(jié)合密度法和最大最小原則得到優(yōu)化的聚類中心,并在Canopy區(qū)域內(nèi)對中心點進行替換,再采用優(yōu)化的準則函數(shù),最后利用順序組合MapReduce編程模型的思想實現(xiàn)了算法的并行化擴展;實驗結(jié)果表明,該改進算法與傳統(tǒng)算法相比對初始中心的依賴降低,提高了聚類的準確性,減少了聚類的迭代次數(shù),降低了聚類的時間。
云環(huán)境;K-Medoids聚類;Canopy算法;最大最小原則;MapReduce
隨著數(shù)據(jù)規(guī)模的爆炸性增長,傳統(tǒng)的數(shù)據(jù)挖掘工作在處理大規(guī)模數(shù)據(jù)時會出現(xiàn)用時過長、存儲量不足等缺點。云計算的提出將這些問題迎刃而解,它是一種基于互聯(lián)網(wǎng)的計算,是分布式計算、并行處理和網(wǎng)格計算的進一步發(fā)展。由Google提出的MapReduce編程框架[1]是云計算中代表性的技術(shù),主要用于海量數(shù)據(jù)的并行計算。已有多種數(shù)據(jù)挖掘算法在MapReduce計算模型的基礎(chǔ)上被實現(xiàn)了,而聚類是在數(shù)據(jù)挖掘中運用比較廣泛的一種算法。
K-Medoids算法是一種典型的基于劃分的聚類算法[2],該算法[3]簡單且易于實現(xiàn),運用于科學(xué)研究的各個領(lǐng)域。但是它對初始聚類中心的選擇非常敏感,不能有效地對大規(guī)模數(shù)據(jù)進行聚類處理。針對K-Medoids算法的特點以及不足,國內(nèi)外很多學(xué)者提出了相應(yīng)的改進K-Medoids算法。文獻[4]提出了一種基于 MapReduce 的 K-Medoids 并行算法,用并行模型高效快速地對海量數(shù)據(jù)進行聚 類處理,但并沒有解決K-Medoids算法對初始中心敏感的問題。文獻[5]提出一個基于最小支撐樹的聚類中心初始化方法,對估計密度方面的方法進行了改進,但是增加了時間復(fù)雜度;文獻[6]對初始中心點進行優(yōu)化,并在每個簇內(nèi)對中心點進行替換,提高了算法的效率,但降低了聚類的精確度;文獻[7]提出一個基于初始中心微調(diào)與增量中心候選集的改進 K-Medoids 算法,文獻[8]提出一種基于密度初始化的改進算法,這些研究通過不同的方法解決了算法對初始中心敏感的問題和對中心點替換的策略進行優(yōu)化,但無法適應(yīng)海量數(shù)據(jù)的處理需求。文獻[9]提出一種基于ACO的K-Medoids聚類算法;文獻[10]提出一種基于粒計算的 K-Medoids聚類算法,都是結(jié)合一些成熟的算法來改進K-Medoids聚類算法,雖然在少量數(shù)據(jù)環(huán)境下能夠顯著提升算法的性能,但卻因為額外的組件增加了算法的復(fù)雜性。
因此,本文提出了一種云環(huán)境下的高效K-Medoids并行算法,其結(jié)合了密度思想和最大最小原則對初始中心點優(yōu)化以提高聚類效率;通過在Canopy區(qū)域內(nèi)進行中心點替換來降低時間復(fù)雜度;并利用云計算對改進K-Medoids算法進行進一步研究以提高該改進算法的并行化執(zhí)行速度。實驗表明,該并行化的改進算法將具有重要的理論研究價值和實際應(yīng)用意義。
MapReduce是一種分布式并行編程模型,數(shù)據(jù)被存儲在分布式文件系統(tǒng)(distributed file system, DFS)中,以鍵-值對
圖1 Mapreduce的操作流程圖
傳統(tǒng)K-Medoids算法思想[4]:在包含n個數(shù)據(jù)對象的數(shù)據(jù)集D中,首先隨機選擇k個不同的數(shù)據(jù)對象作為初始聚類中心Oi;再根據(jù)其剩余數(shù)據(jù)對象到聚類中心的相似度(歐式距離),將其分配給與之相似度最大(距離最近)的中心點所在的聚類;然后全局隨機選取一個非聚類中心點的數(shù)據(jù)對象p作為替代簇心;如果替代簇心的聚類效果比當(dāng)前簇心好,則更新當(dāng)前的簇中心,繼續(xù)進行聚類迭代,直到各簇中心不再發(fā)生變化,說明當(dāng)前聚類結(jié)構(gòu)不再進行調(diào)整,迭代算法結(jié)束。判定一個非中心點對象比當(dāng)前中心點效果好的參照是誤差平方和準則函數(shù)的值減少,即用非中心點p代替中心點Oi的代價S<0。
歐式距離公式如下:
(1)
其中:i=(xi1,xi2,...,xip);j=(xj1,xj2,...,xjp)分別表示一個p-維數(shù)據(jù)對象。
誤差平方和函數(shù)可以定義為:
(2)
其中:p為類Ci中的樣本,Oj為聚類中心(p和Oj均是多維的)。
傳統(tǒng)的K-Medoids算法通過完全隨機的策略對初始聚類中心點進行選取,不能確保聚類結(jié)果的準確性??梢酝ㄟ^密度思想和最大最小原則相結(jié)合的策略求得數(shù)據(jù)集的初始聚類中心。
在高密度區(qū)域選擇初始中心點可以排除噪聲點和孤立點的干擾,而最大最小原則可以避免在高密度區(qū)域選取的中心點過于鄰近,具體表述如下。
定義1:高密度點:取數(shù)據(jù)集中的數(shù)據(jù)對象xi為中心點,計算此中心點在鄰域半徑δ內(nèi)包含的樣本個數(shù),若樣本個數(shù)不少于常數(shù)Minds,則該中心點就被稱為高密度點。其中δ的取值需結(jié)合輸入的數(shù)據(jù)對象集,將其取為n個數(shù)據(jù)樣本間距離均方根的一半,公式如下:
(3)
其中:║xi-xj║為公式(1)的歐式距離D(i,j)。
得到優(yōu)化的初始中心點流程為:
1)根據(jù)定義3計算出原始數(shù)據(jù)集的高密度點,并將其放于集合S{X1,X2,…Xn}中。從中取最高密度點作為第一個初始聚類中心點C1,并將其從S中刪除;
2)在剩余的高密度點集S中找到距離C1最遠的點,作為第二個初始聚類中心點C2,并將其從S中刪除;
3)分別計算剩余高密度點集到已有的i個聚類中心點之間的距離,取最小距離的最大者:D(i+1)=max{min{D(j,1),D(j,2),…,D(j,i)}},j=1,2,…,n,則第i+1個初始聚類中心點為Ci+1=Xj,并將其從S中刪除;
4)當(dāng)表示D(i+1)變化幅度的深度指標Depth(k)=|D(k)-D(k-1)|+ |D(k+1)-D(k)|取得最大值時,所得到的前k個記錄值就是需要的初始聚類中心點,同時下一輪Canopy的區(qū)域半徑可設(shè)為T1=D(k),避免了Canopy算法初始值設(shè)置的盲目性和隨機性。
1)K-Medoids算法時間復(fù)雜度較高,不能很好的處理大規(guī)模數(shù)據(jù)的聚類操作。而基于MapReduce的分布式并行計算模型,將一個大型數(shù)據(jù)切分成多個小數(shù)據(jù)模塊的形式,分配給多臺計算機集群進行分布式計算,與傳統(tǒng)的單機運行平臺相比,加快了總體的運行速率,減少了執(zhí)行時間。
2)傳統(tǒng)的K-Medoids算法在對聚類中心進行替換時,采用的是全局順序替換的策略,雖然在一定程度上確保了聚類的效果,但是總體上降低了算法的效率,而且全局順序替換策略不能適應(yīng)大規(guī)模數(shù)據(jù)的聚類處理。對于一個中心點,若要對其進行替換,一些較優(yōu)的候選點最有可能出現(xiàn)在該中心點附近,如同一簇內(nèi)或其附近簇中的點。因此在搜索新的中心點時可以只在這些范圍內(nèi)進行。對此,提出了一種Canopy(華蓋)區(qū)域內(nèi)中心點隨機替換策略來代替?zhèn)鹘y(tǒng)的替換方法,即在每個Canopy區(qū)域內(nèi)部對中心點進行隨機替換?;贑anopy區(qū)域的中心替換策略是Park等人[6]提出的簇內(nèi)替換策略的優(yōu)化擴展,擴大了搜索的范圍,提高聚類精度。
3)傳統(tǒng)的K-Medoids算法將剩余數(shù)據(jù)對象分配給距離最近的簇時,計算了剩余數(shù)據(jù)對象與每一個中心點的距離,使得計算規(guī)模較大。而通過Canopy的粗略劃分后,只需要計算剩余數(shù)據(jù)對象與對應(yīng)的同一Canopy區(qū)域內(nèi)的中心點之間的距離,降低了運算規(guī)模,提高運行效率。
Canopy算法[12]的思想是使用一種代價低的相似性度量方法,快速粗略地將數(shù)據(jù)劃分成若干個重疊子集,每個子集可以看成是一個簇。Canopy劃分基本流程如下:(1)設(shè)置閾值T1=D(k),Canopy中心為上一輪的k個初始聚類中心點;(2)計算剩余的數(shù)據(jù)集中每一個數(shù)據(jù)對象與所有的Canopy中心之間的距離,如果該數(shù)據(jù)對象與某個Canopy中心的距離在T1內(nèi),則將該對象加入到這個Canopy中,當(dāng)該數(shù)據(jù)對象與所有Canopy中心的距離計算完成后,將其從數(shù)據(jù)集中刪除,如果該數(shù)據(jù)對象沒有加入到任何Canopy,則構(gòu)建一個新的Canopy。
4)傳統(tǒng)算法都是將聚類內(nèi)部的數(shù)據(jù)對象的距離誤差平方和作為準則函數(shù),沒有考慮到所有聚類之間的距離對聚類總體質(zhì)量的影響。對此,為了得到最優(yōu)的空間聚類結(jié)果,提出了一種基于加權(quán)的準則函數(shù)[8]。
類間距離b定義為不同聚類中心點間的距離,可以表述為:
(4)
基于加權(quán)的準則函數(shù)采用類內(nèi)距離w(即公式(2)的誤差平方和函數(shù))和類間距離b共同決定,則準則函數(shù)可以表示為:
(5)
其中:w1、w2為加權(quán)系數(shù),且w1+w2=1;w1、w2需要根據(jù)不同的數(shù)據(jù)集設(shè)置,但w1、w2必須滿足w1+w2=1的關(guān)系,使聚類效果達到最好并能提高算法的適應(yīng)性。
4.1 改進算法基本流程
首先運用密度思想和最大最小距離法相結(jié)合的方法求得數(shù)據(jù)集的初始聚類中心;再在聚類中心的替換方法上,用Canopy區(qū)域內(nèi)隨機替換策略代替?zhèn)鹘y(tǒng)的全局順序替換策略,以改進K-Medoids算法。一方面,該算法可以通過獲得優(yōu)化的初始聚類中心來提高聚類結(jié)果的精確度;另一方面,該算法能夠提高收斂速度,降低時間復(fù)雜度。最后,將改進后的算法運用于MapReduce的并行計算模型中,其基本流程如圖2所示。
圖2 基于Mapreduce的改進K-Medoids算法的基本流程圖
4.2 改進算法并行化步驟
4.2.1 計算初始聚類中心點
計算高密度數(shù)據(jù)集
算法1:高密度點的生成
輸入:數(shù)據(jù)集S
輸出:高密度點集H
Map函數(shù):
每個Map讀取數(shù)據(jù)集S,計算每個數(shù)據(jù)點xi與其余數(shù)據(jù)點之間的距離Di,j;
Reduce函數(shù):
1)根據(jù)公式(3)計算鄰域半徑δ,并統(tǒng)計到每個數(shù)據(jù)點xi距離小于δ的數(shù)據(jù)個數(shù);
2)讀取密度閾值Minds,若個數(shù)大于Minds,則把該點定義為高密度點,得到高密度點集合H。
3)最大最小原則計算初始中心點
該階段任務(wù)確定初始中心點[13]以及區(qū)域半徑T1,避免了下一個階段Canopy算法初始值設(shè)置的盲目性和隨機性,具體算法如下:
算法2:中心點生成算法
Map 函數(shù):
輸入:高密度點集H
輸出:中心點的初始集合Q
1)設(shè)置初始中心點的集合,Q=null;
2)設(shè)置迭代次數(shù),Whilek< sqrt(N)(當(dāng)前節(jié)點數(shù)據(jù)規(guī)模N);
3)if集合Q為空,求數(shù)據(jù)集V(當(dāng)前節(jié)點數(shù)據(jù)集V)中密度最大點,并保存該點至集合Q;else求數(shù)據(jù)集V中數(shù)據(jù)點與集合Q中數(shù)據(jù)點的距離最小值中最大者,并保存該點至集合Q;
Reduce 函數(shù):
輸入:各節(jié)點中心點的初始集合Q={Q1,Q2,...,Qn};
輸出:中心點的最終集合U以及半徑T1;
1)求取集合Q的數(shù)據(jù)總量,N=Count(Q) ;
2)設(shè)置迭代次數(shù),Whilek< sqrt(N)
3)求數(shù)據(jù)集中數(shù)據(jù)點之間距離最小值中最大者,并保存該點至集合Q′;
4)求取集合Q′的數(shù)據(jù)量m= Count(Q′);
5)whilej 4.2.2 Canopy劃分 算法3:Canopy劃分算法 Map函數(shù): 輸入:數(shù)據(jù)集S 輸出:標注對應(yīng)Canopy的數(shù)據(jù)集C。 1)讀取中心點的最終集合U以及半徑T1,計算數(shù)據(jù)集中的對象與中心點之間的距離D; 2)當(dāng)D≤T1,則標注該數(shù)據(jù)點屬于對應(yīng)的Canopy,并將結(jié)果輸出。 4.2.3 K-Medoids迭代 該階段的主要任務(wù)是進行精確的聚類計算,其算法流程為: 算法4:K-Medoids算法 輸入:標注對應(yīng)Canopy的數(shù)據(jù)集C 輸出:K中心點集合U′ Map 函數(shù): 1)讀取中心點的最終集合U,將中心點的最終集合U作為初始K中心點集合,U′=U; 2)通過Map函數(shù)比較已標注的輸入數(shù)據(jù)點與對應(yīng)中心點的距離,輸出當(dāng)前數(shù)據(jù)點及對應(yīng)最近距離的中心點編號; Reduce 函數(shù): 1)通過K個Reduce函數(shù)將同一中心點下的數(shù)據(jù)點歸并,在該中心點Oi對應(yīng)的Canopy內(nèi)選擇一個未被選擇過的非中心點p,根據(jù)公式(5)計算用p代替Oi的代價并記錄在Si中,直到Canopy中所有的非中心點都被選擇過; 2)如果Si中最小值小于0,則將最小值對應(yīng)的非中心點代替當(dāng)前簇心,進行下一輪MapReduce的迭代,否則終止程序。 5.1 實驗平臺 硬件環(huán)境:6臺主機:一臺Namenode,5臺Datanode;CPU 為2.66 GHz;硬盤為250 G;內(nèi)存為2 G。 Hadoop集群軟件環(huán)境:Ubuntu12.04操作系統(tǒng);VMware Workstation v8.0;Hadoop版本為0.20.2;JDK版本為JDK1.6。 5.2 聚類質(zhì)量以及執(zhí)行效率的分析 在Hadoop集群上,采用標準數(shù)據(jù)集:Zoo、Iris、Wine及Breast Cancer數(shù)據(jù)集進行聚類研究,分別對K-Medoids算法、改進K-Medoids算法進行測試。 表1 各數(shù)據(jù)集的參數(shù)比較 預(yù)先給出K-Medoids算法需要的聚類數(shù)目。平均查準率為p,平均查全率為R,迭代次數(shù)為t,執(zhí)行時間為T,以下的結(jié)果是運行5次的平均結(jié)果。為了能體現(xiàn)改進算法與傳統(tǒng)的K-Medoids算法在并行化的條件下的優(yōu)越性,使用相同 Hadoop集群、相同數(shù)據(jù)集進行聚類,聚類結(jié)果如表2~表5所示。 表2 算法在Zoo數(shù)據(jù)集的聚類質(zhì)量以及執(zhí)行效率 表3 算法在Iris數(shù)據(jù)集的聚類質(zhì)量以及執(zhí)行效率 表4 算法在Wine數(shù)據(jù)集的聚類質(zhì)量以及執(zhí)行效率 表5 算法在Breast Cancer數(shù)據(jù)集的聚類質(zhì)量以及執(zhí)行效率 由表2、表3、表4和表5可以得出以下結(jié)論,在處理4種不同類型的數(shù)據(jù)集時,改進K-Medoids算法不僅聚類效果較K-Medoids算法好,而且具有較快的收斂速度。密度思想和最大最小原則相結(jié)合的方法能夠快速地獲取到較好的初始聚類中心,從而減少算法中的循環(huán)迭代次數(shù),加快收斂速度。針對聚類數(shù)與屬性數(shù)相對較多的Zoo數(shù)據(jù)集,其改進效果更加明顯,而對于Breast Cancer這種聚類數(shù)較少的數(shù)據(jù)集能夠維持其原來的聚類效果,驗證了改進算法在聚類效果上的穩(wěn)定性。 5.3 K-Medoids聚類加速比分析 增加Iris數(shù)據(jù)集數(shù)據(jù)對象的數(shù)量,選取樣本1、樣本2、樣本3這3個記錄數(shù)n(單位:萬)分別是1、10、100的數(shù)據(jù)進行實驗對比分析,執(zhí)行效率如表6所示。在節(jié)點數(shù)為1、2、3、4、5、6的Hadoop平臺上,使用改進K-Medoids算法進行聚類計算所對應(yīng)的加速比,如圖3所示。 表6 算法在不同規(guī)模Iris數(shù)據(jù)集的執(zhí)行效率 圖3 Hadoop下不同規(guī)模數(shù)據(jù)集的改進K-Medoids算法加速比 由表6和圖3可以看出:1)在處理樣本量較小的數(shù)據(jù)集時,改進算法的加速比容易達到瓶頸;2)加速比隨著節(jié)點數(shù)的增加而增大,但由于節(jié)點數(shù)的增加而帶來了消耗更多時間的數(shù)據(jù)通信等使得加速比的增長速度降低;3)在處理大規(guī)模的樣本集時,改進算法的加速比更趨近于線性。 在處理海量數(shù)據(jù)時,為解決K-Medoids算法在進行聚類運算時,會出現(xiàn)初始聚類中心選取的不確定性、算法時間復(fù)雜度較高、算法的執(zhí)行效率低下等問題,提出了一種高效的改進K-Medoids算法。為提高算法的執(zhí)行效率,并在MapReduce的平臺下對該改進聚類算法進行實現(xiàn)。并通過實驗對其進行對比分析,與傳統(tǒng)的聚類算法相比,該改進算法不僅能提高算法的查準率和查全率以及運行效率而且能改進聚類的效果,這對促進 K-Medoids 算法的發(fā)展與應(yīng)用具有積極的意義。 [1] Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113. [2] Han J, Kamber M.?dāng)?shù)據(jù)挖掘:概念與技術(shù)[M].范 明,孟小峰,譯.2 版.北京:機械工業(yè)出版社,2007. [3] Chen X Q,Peng H,Hu J S. K-medoids substitution clustering method and a new clustering validity index method[A].Proc of 6th World Congress on Intelligent Control and Automation[C].2006:5896-5900. [4] 張雪萍,龔康莉,趙廣才.基于MapReduce的K-Medoids并行算法[J].計算機應(yīng)用,2013, 33(4):1023-1025,1035. [5] Gao D Y,Yang B R. An improved K-medoids clustering algorithm[A].Proc of the 2nd International Conference on Computer and Automation Engineering(ICCAE)[C].2010:132-135. [6] Park H S,Jun C H. A simple and fast algorithm for K-medoids clustering[J].Expert Systems with Applications,2009, 36(2): 3336-3341. [7] 夏寧霞,蘇一丹,覃 希.一種高效的K-medoids 聚類算法[J].計算機應(yīng)用研究, 2010, 27(12): 4517-4519. [8] 姚麗娟,羅 可,孟 穎.一種新的K-medoids聚類算法[J].計算機工程與應(yīng)用,2013, 49(19): 153-157. [9] 孟 穎,羅 可,姚麗娟,等.一種基于ACO的K-medoids聚類算法[J].計算機工程與應(yīng)用,2012, 48(16): 136-139. [10] 馬 箐,謝娟英.基于粒計算的K-medoids聚類算法[J].計算機應(yīng)用,2012, 32(7): 1973-1977. [11] Isard M, Budiu M, Yu Y, et al. Dryad: Distributed data-parallel programs from sequential building blocks[A]. Proc. of the 2ndEuropean Conf. on Computer Systems (EuroSys)[C]. 2007: 59-72. [12] 孫吉貴,劉 杰,趙連宇.聚類算法研究[J].軟件學(xué)報,2008, 19(1): 48-61. [13] 毛典輝.基于MapReduce的Canopy-Kmeans改進算法[J].計算機工程與應(yīng)用,2012,48(27):22-26. Highly Efficient Parallel Algorithm of K-Medoids in Cloud Environment Li Yuanyuan1, Sun Yuqiang1, Chao Ya1, Liu Yang2 (1.School of Information Science&Engineering,Changzhou University,Changzhou 213164,China; 2.SEPEE,Power Construction of China,Shanghai 201900,China) Traditional K-Medoids clustering algorithm selects the initial points randomly, which is easy to produce local optimum; when replace the cluster centers, adopted global sequential replacement policy reduces the efficiency of the algorithm; at the same time, it is difficult to adapt to operation of massive data. In response to the above problems, an improved K-Medoids clustering algorithm in cloud environment is proposed. The algorithm combines the density method and Max-Min principle to obtain optimized cluster centers, and replaces centers in the area of Canopy, and adopts optimization criterion function, and finally uses the ideas of sequential composition of MapReduce programming model to achieve the parallel extensions of the algorithm. Result of the experiments shows that the improved method is less dependent on the initial points and reduces the number of iterations and the clustering time. cloud environment; K-Medoids clustering; Canopy algorithm; max-min principle; MapReduce 2016-07-20; 2016-08-02。 國家自然科學(xué)基金項目(11271057,51176016);江蘇省自然科學(xué)基金項目(BK2009535)。 李媛媛(1991-),女,江蘇鹽城人,碩士研究生,主要從并行計算、數(shù)據(jù)挖掘等方向的研究,CCF學(xué)生會員ID方向的研究。 孫玉強(1956-),男,河南人,教授,碩士研究生導(dǎo)師,主要從事并行計算、軟件工程等方向的研究。 1671-4598(2016)12-0139-04 10.16526/j.cnki.11-4762/tp.2016.12.040 TP311 A5 實驗結(jié)果分析
6 結(jié)束語