基于Hadoop的分布式聚類(lèi)算法研究

吳德超，劉曉紅，曲志堅(jiān)

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博 255049)

聚類(lèi)作為數(shù)據(jù)挖掘中重要的組成部分，是一種對(duì)原始數(shù)據(jù)進(jìn)行合理歸類(lèi)的有效方法，然而大批量的數(shù)據(jù)也給聚類(lèi)算法的實(shí)際應(yīng)用帶來(lái)了一些麻煩，比如如何讓聚類(lèi)算法執(zhí)行的更快速、更有效是當(dāng)前聚類(lèi)算法面臨的緊迫問(wèn)題之一.

1 相關(guān)研究

1.1 K-means聚類(lèi)算法的研究

國(guó)外對(duì)于大數(shù)據(jù)聚類(lèi)算法的研究開(kāi)展較早，研究工作主要集中在為大型數(shù)據(jù)庫(kù)的有效和實(shí)際聚類(lèi)分析尋找適當(dāng)?shù)姆椒╗1].具體研究課題主要集中在聚類(lèi)方法的可伸縮性、方法對(duì)聚類(lèi)復(fù)雜形狀和類(lèi)型的數(shù)據(jù)的有效性、高維聚類(lèi)分析技術(shù)以及針對(duì)大型數(shù)據(jù)庫(kù)中混合數(shù)值和分類(lèi)數(shù)據(jù)的聚類(lèi)方法.國(guó)內(nèi)在聚類(lèi)方面的研究較晚，但是研究的進(jìn)展比較快.楊敏煜提出了一種改進(jìn)的K-means算法[2]，算法引入權(quán)重的思想，考慮到整個(gè)數(shù)據(jù)集，權(quán)重能夠加速聚類(lèi)的過(guò)程，得到較好的聚類(lèi)效果.

隨著大數(shù)據(jù)時(shí)代的到來(lái)，如何提高聚類(lèi)算法的執(zhí)行效率對(duì)于后續(xù)的數(shù)據(jù)挖掘?qū)⑵鸬疥P(guān)鍵性作用.隨著近幾年分布式計(jì)算模式的興起，對(duì)于聚類(lèi)算法的執(zhí)行效率問(wèn)題給出了一個(gè)比較好的解決方案，即利用多臺(tái)機(jī)器并行處理來(lái)提高聚類(lèi)算法處理海量數(shù)據(jù)的性能.

1.2 Hadoop 計(jì)算平臺(tái)

Hadoop是一個(gè)用于并行處理大數(shù)據(jù)的計(jì)算平臺(tái)，擴(kuò)容能力強(qiáng)、可靠性好、使用方便.在Hadoop平臺(tái)上，采用HDFS存儲(chǔ)數(shù)據(jù)、MapReduce編程模式來(lái)實(shí)現(xiàn)對(duì)海量數(shù)據(jù)的并行化處理[3-4].用戶(hù)可在不了解底層關(guān)系的情況下進(jìn)行分布式程序開(kāi)發(fā)，快速實(shí)現(xiàn)聚類(lèi)算法的并行化.

1.3 分布式計(jì)算的需求

隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，以往的聚類(lèi)方式在處理如此大批量的數(shù)據(jù)時(shí)已無(wú)法滿(mǎn)足人們的需要，近些年分布式技術(shù)的發(fā)展已經(jīng)為聚類(lèi)算法指明了新的方向[5].Hadoop是Apache下開(kāi)源的一個(gè)項(xiàng)目，是一個(gè)用于構(gòu)建云平臺(tái)的分布式的計(jì)算框架. 基于Hadoop計(jì)算平臺(tái)進(jìn)行聚類(lèi)任務(wù)能夠很大程度上降低聚類(lèi)過(guò)程的運(yùn)行時(shí)間，提高計(jì)算效率，對(duì)解決未來(lái)更大規(guī)模的數(shù)據(jù)計(jì)算具有重大的意義.

2 算法描述

2.1 K-means 算法優(yōu)缺點(diǎn)

K-means算法其顯著優(yōu)點(diǎn)是原理簡(jiǎn)單，容易實(shí)現(xiàn)，收斂速度快，因?yàn)榇薑-means算法更適合用于處理大數(shù)據(jù).

它也存在一些缺點(diǎn)[6].

(1)K-means算法要求首先要確定K值，現(xiàn)實(shí)中很多數(shù)據(jù)事先不知道包含幾類(lèi)，K值通常是通過(guò)經(jīng)驗(yàn)來(lái)確定.

(2)分類(lèi)結(jié)果依賴(lài)于分類(lèi)中心的初始化.

(3)對(duì)于離群點(diǎn)數(shù)據(jù)敏感，離群點(diǎn)對(duì)其最終結(jié)果影響較大.

2.2 Canopy算法優(yōu)缺點(diǎn)

Canopy 算法是2000年提出來(lái)的[7]，它不會(huì)單獨(dú)用來(lái)進(jìn)行聚類(lèi)，一般是輔助于其他算法，比如K-means算法，它可以用來(lái)確定K值和K個(gè)中心點(diǎn)，這樣能有效地降低K-means算法中計(jì)算點(diǎn)之間距離的復(fù)雜度.

Canopy的優(yōu)點(diǎn)：

(1)Canopy算法用于去除相對(duì)較少數(shù)據(jù)的類(lèi)簇，這有利于抗干擾.

(2)Canopy選擇出來(lái)的中心點(diǎn)作為K-means的初始中心點(diǎn)比較合理.

(3)對(duì)Canopy算法計(jì)算出來(lái)的每個(gè)類(lèi)簇進(jìn)行K-means聚類(lèi)，能夠大幅度減少相似度的計(jì)算次數(shù).

Canopy算法缺點(diǎn)：

(1)算法中初始距離T1、T2的確定問(wèn)題.

(2)Canopy算法執(zhí)行結(jié)束后不能給出較為準(zhǔn)確的聚類(lèi)結(jié)果.

Canopy算法不需要事先指定K值，因此可以使用Canopy聚類(lèi)先對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)處理確定K個(gè)類(lèi)簇，然后再使用K-means進(jìn)行詳細(xì)聚類(lèi)得到最終結(jié)果.將Canopy算法與K-means算法結(jié)合起來(lái)不僅能提高精確度，還能很大程度削減計(jì)算量.

3 基于Hadoop的K-means+ Canopy 聚類(lèi)算法

3.1 改進(jìn)的Canopy算法介紹

Canopy算法的執(zhí)行結(jié)果會(huì)受初始閾值T1、T2的影響，當(dāng)T1較大時(shí)，會(huì)使同一個(gè)點(diǎn)屬于多個(gè)類(lèi)簇，增加計(jì)算量；當(dāng)T2過(guò)大時(shí)，會(huì)降低類(lèi)簇的個(gè)數(shù)，為了解決T1、T2對(duì)于聚類(lèi)的影響，本文采用“最大最小化原則”來(lái)確定T1、T2的值，最大程度提高聚類(lèi)的準(zhǔn)確率.

基于“最大最小化原則”的中心點(diǎn)選擇方法的核心思想是：當(dāng)確定前n個(gè)Canopy中心點(diǎn)后，第n+1個(gè)Canopy中心點(diǎn)應(yīng)該選擇為所有候選數(shù)據(jù)點(diǎn)中與前n個(gè)中心點(diǎn)之間最小距離的最大者，如公式(1)所示：

(1)

式中DistList代表第n+1個(gè)中心點(diǎn)與前n個(gè)中心點(diǎn)的最小距離，DistMin(n+1)則表示第n+1個(gè)中心點(diǎn)應(yīng)該為所有最短距離中的最大者.

這種選擇中心點(diǎn)的方法在應(yīng)用中會(huì)呈現(xiàn)如下規(guī)律：當(dāng)中心點(diǎn)的個(gè)數(shù)低于或者大于真實(shí)中心點(diǎn)的個(gè)數(shù)時(shí)DistMin(n+1)變化程度較小，當(dāng)中心點(diǎn)的個(gè)數(shù)接近真實(shí)中心點(diǎn)個(gè)數(shù)時(shí)DistMin(n+1)變化程度較大.為了確定類(lèi)簇的最優(yōu)個(gè)數(shù)以及T1的值，引入深度指標(biāo)Depth(i)表示變化幅度，其定義如公式(2)：

Depth(k) = |DistMin(k)-DistMin(k-1)| +

|Dist(k+1)-DistMin(k)|

(2)

當(dāng)k接近真實(shí)類(lèi)簇?cái)?shù)時(shí)，Depth(k)取得最大值，這時(shí)設(shè)置T1=DistMin(k)使得結(jié)果最優(yōu).

3.2 基于Hadoop平臺(tái)的K-means聯(lián)合Canopy實(shí)現(xiàn)過(guò)程

在Hadoop程序開(kāi)發(fā)中最重要的就是MapReduce程序設(shè)計(jì)與實(shí)現(xiàn)，在MapReduce框架下實(shí)現(xiàn)K-means + Canopy聚類(lèi)功能分為Canopy算法代碼開(kāi)發(fā)和K-means算法代碼開(kāi)發(fā)[8]，其中Canopy算法生成K個(gè)類(lèi)簇，這K個(gè)類(lèi)簇中心可以作為K-means算法的初始聚類(lèi)中心，K-means算法得到最終的聚類(lèi)結(jié)果，在Hadoop計(jì)算框架下每一部分都是分解為多個(gè)子任務(wù)完成，具體流程如圖1所示.

圖1 Canopy + K-means算法實(shí)現(xiàn)流程Fig.1 Implementation process of Canopy + K-means algorithm

Hadoop平臺(tái)Canopy算法聯(lián)合K-means聚類(lèi)算法的實(shí)現(xiàn)步驟如下.

(1)讀取數(shù)據(jù)特征.

(2)執(zhí)行Canopy算法獲取初始聚類(lèi)中心的步驟：

①將數(shù)據(jù)的特征矩陣存到一個(gè)list中同時(shí)基于“最大最小化原則”確定距離闞值T1.

②從list中隨機(jī)取一個(gè)向量P，計(jì)算P與所有Canopy之間的距離，如果當(dāng)前還沒(méi)有Canopy，則把P作為第一個(gè)Canopy，如果P與某個(gè)Canopy距離在T1以?xún)?nèi)，則將點(diǎn)P加入到這個(gè)Canopy[9].

③如果向量P與某個(gè)Canopy的距離在T2以?xún)?nèi)，則把P從list中刪掉.

④重復(fù)步驟2、3，直到list為空結(jié)束.

(3)執(zhí)行K-means算法計(jì)算數(shù)據(jù)對(duì)象與聚類(lèi)中心間的距離，步驟如下：

①選取Canopy算法執(zhí)行結(jié)束后得到的K個(gè)簇的中心作為初始聚類(lèi)中心.

②遍歷剩下的所有向量計(jì)算其到K個(gè)中心的距離，將其歸到距離最近的中心點(diǎn)所位于的類(lèi)簇中.

③對(duì)計(jì)算得到的K個(gè)類(lèi)簇重新計(jì)算每個(gè)類(lèi)簇的中心點(diǎn).

④再次計(jì)算每個(gè)點(diǎn)到K個(gè)中心點(diǎn)的距離，將其歸類(lèi)到距離最近的那個(gè)點(diǎn)所位于的類(lèi)簇中[10].

⑤重復(fù)2到4步，直到中心點(diǎn)位置不再變化或者達(dá)到預(yù)定的迭代次數(shù)為止.

(4)將聚類(lèi)結(jié)果保存.

4 手寫(xiě)數(shù)字字形校正

由于個(gè)人書(shū)寫(xiě)習(xí)慣可能會(huì)出現(xiàn)字體傾斜的情況，如果對(duì)字形進(jìn)行傾斜校正，會(huì)提高聚類(lèi)準(zhǔn)確率[11-12].字形傾斜可以通過(guò)計(jì)算整體傾斜度來(lái)進(jìn)行校正，目標(biāo)是使圖像的傾斜度盡可能的小，手寫(xiě)數(shù)字一般有細(xì)長(zhǎng)的特點(diǎn)，因此可以將圖像的高寬比作為圖像傾斜度的依據(jù).在調(diào)整圖像的傾斜度時(shí)引入二分搜索的思想，在傾斜-90°～90°的范圍內(nèi)進(jìn)行二分查找，尋找最小傾斜角度，使其結(jié)果近似最優(yōu)，具體步驟如下：

(1)因?yàn)樽煮w可能左右傾斜，所以設(shè)置調(diào)整角度的范圍在-90°～90°之間.

(2)從手寫(xiě)數(shù)字圖像中截取數(shù)字區(qū)域計(jì)算圖像高寬比，如果高寬比較前一次有所減小，則調(diào)整角度減半，繼續(xù)搜索；如果傾斜度趨于穩(wěn)定，則退出查找，并使用此時(shí)的調(diào)整角度對(duì)圖像進(jìn)行調(diào)整.

圖2所示是原圖像最終調(diào)整55°后的圖像對(duì)比，明顯看出調(diào)整后圖像中的數(shù)字更標(biāo)準(zhǔn).

圖 2 圖像調(diào)整Fig.2 Image adjustment

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

本次實(shí)驗(yàn)以開(kāi)源Hadoop項(xiàng)目作為開(kāi)發(fā)平臺(tái),聚類(lèi)分析對(duì)象是手寫(xiě)數(shù)字圖像.為了比較基于“最大最小化原則”的Canopy算法與傳統(tǒng)選取T1、T2值Canopy算法的優(yōu)劣,在同一數(shù)據(jù)集下分別采用了以上兩種策略進(jìn)行了對(duì)比分析.同時(shí)為了比較MapReduce框架處理大批量數(shù)據(jù)的性能優(yōu)勢(shì),將基于同一數(shù)據(jù)集與Canopy + K-means 單機(jī)算法進(jìn)行效率對(duì)比.另外進(jìn)行字形傾斜校正，分析字形傾斜對(duì)于聚類(lèi)結(jié)果的影響.

5.1 實(shí)驗(yàn)環(huán)境設(shè)置

實(shí)驗(yàn)硬件配置為3個(gè)服務(wù)器節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)均為8核、8GB內(nèi)存的PC；軟件配置：每個(gè)節(jié)點(diǎn)均為L(zhǎng)inux Ubuntu 14.04操作系統(tǒng)，Hadoop版本為2.6.0，開(kāi)發(fā)包為JDK1.7版本.程序開(kāi)發(fā)工具為 Intellij IDEA，算法由Java實(shí)現(xiàn).

手寫(xiě)數(shù)字實(shí)驗(yàn)數(shù)據(jù)來(lái)自THE MNIST DATABASE，鏈接為http://yann.lecun.com/exdb/mnist/.

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

(1)為了驗(yàn)證集群模式與單機(jī)模式處理大規(guī)模數(shù)據(jù)時(shí)的速度差異，針對(duì)同一數(shù)據(jù)集分別放在兩種模式下運(yùn)行，結(jié)果見(jiàn)表1.

表1 單機(jī)模式與Hadoop集群模式對(duì)比Tab.1 Execution comparison between standalone mode and Hadoop cluster

從表1中可以看處理Hadoop集群的計(jì)算優(yōu)勢(shì)非常明顯,程序執(zhí)行時(shí)間較單機(jī)計(jì)算時(shí)間縮短.Hadoop集群適用于更大數(shù)量級(jí)的處理，數(shù)量級(jí)在TB級(jí)別時(shí)Hadoop優(yōu)勢(shì)更為明顯.這里做一個(gè)擁有3個(gè)節(jié)點(diǎn)的Hadoop集群與單機(jī)處理不同量級(jí)速度的對(duì)比，如圖3所示.

圖3 Hadoop集群與單機(jī)處理耗時(shí)對(duì)比Fig.3 Comparison of time between Hadoop cluster and stand- alone processing

從圖3可以看出數(shù)據(jù)量在1 100MB以下時(shí)，Hadoop集群與單機(jī)計(jì)算速度幾乎沒(méi)有差別，甚至數(shù)據(jù)量在不到900MB時(shí)單機(jī)計(jì)算速度優(yōu)于Hadoop集群，這是由于在Hadoop集群中會(huì)有系統(tǒng)初始化、中間文件生成以及傳遞等操作，這些操作會(huì)消耗一定的時(shí)間，所以在數(shù)據(jù)量較小時(shí)Hadoop集群的速度優(yōu)勢(shì)體現(xiàn)不出來(lái)，但是當(dāng)數(shù)據(jù)量達(dá)到2GB以上時(shí)，Hadoop集群的優(yōu)勢(shì)開(kāi)始凸顯，而且這種優(yōu)勢(shì)隨著數(shù)據(jù)量的增大愈加明顯.

(2)基于“最大最小化原則”的Canopy算法確定初始化中心點(diǎn)與傳統(tǒng)確定T1、T2值的Canopy算法確定初始聚類(lèi)中心比較：

①聚類(lèi)對(duì)象為單個(gè)的手寫(xiě)數(shù)字圖像，有0～9十種數(shù)字.

②圖像特征基于灰度值提取.

③傳統(tǒng)Canopy算法設(shè)置T1為數(shù)據(jù)集中所有元素間的距離的平均值的一半,T2為三倍的T1.

通過(guò)傳統(tǒng)和“最大最小化原則”兩種Canopy算法方式選出初始聚類(lèi)中心，然后基于Hadoop進(jìn)行K-means算法聚類(lèi)，重復(fù)執(zhí)行5次，聚類(lèi)結(jié)果分析見(jiàn)表2.

表2 傳統(tǒng)與“最大最小化原則”的Canopy算法準(zhǔn)確率對(duì)比Tab.2 The accuracy comparison of traditional Canopy algorithm and the one with “maximum minimization principle”

手寫(xiě)數(shù)字特征集合大小為10GB，分別通過(guò)傳統(tǒng)Canopy算法和基于“最大最小化原則”的Canopy算法兩種方式選取初始聚類(lèi)中心點(diǎn)，聚類(lèi)結(jié)束后隨機(jī)抽取一個(gè)類(lèi)簇的20條數(shù)據(jù)，計(jì)算出正確率.從這5次的結(jié)果可以得出隨機(jī)選取初始聚類(lèi)中心的聚類(lèi)結(jié)果會(huì)因?yàn)槌跏贾行狞c(diǎn)的不同而產(chǎn)生波動(dòng)，而由于Canopy算法能夠有效避免陷入局部最優(yōu)，所以通過(guò)Canopy算法得到初始聚類(lèi)中心聚類(lèi)結(jié)果較為穩(wěn)定，準(zhǔn)確率也相對(duì)較高.

(3)分析字形傾斜對(duì)于聚類(lèi)結(jié)果的影響，字形傾斜矯正偽代碼如下：

Begin:

maxAngle = 90, minAngle = -90,midAngle

= (maxAngle+minAngle)/2

/*初始化值*/

While minAngle < maxAngle do

height,width = getInfo(img)

rate1 = height / width /*計(jì)算比率*/

rotatedImg = rotate(image, midAngle) /*旋轉(zhuǎn)數(shù)字*/

new_height, new_width =

getInfo(rotatedImg)

rate2 = new_height / new_width

if rate2 > rate1 then

minAngle=midAngle+1

elseif rate2 < rate1 then

maxAngle=midAngle-1

else exit

midAngle=

(maxAngle+minAngle) / 2

End.

數(shù)字傾斜度調(diào)整結(jié)束后提取圖像灰度值作為特征，然后通過(guò)傳統(tǒng)與“最大最小化原則”兩種方式的Canopy算法進(jìn)行初始聚類(lèi)中心點(diǎn)選取，聚類(lèi)結(jié)束后隨機(jī)抽取一個(gè)類(lèi)簇的20條數(shù)據(jù)，計(jì)算出正確率.重復(fù)執(zhí)行5次，結(jié)果見(jiàn)表3.

表3 字形調(diào)整后傳統(tǒng)與“最大最小化原則”的Canopy算法選取初始中心點(diǎn)的準(zhǔn)確率對(duì)比Tab.3 The accuracy comparison of the initial center point by the traditional and "maximum minimization principle" Canopy algorithm

比較表3和表2可以看出，字形傾斜校正后兩種模式的Canopy算法選取初始中心點(diǎn)的準(zhǔn)確率明顯不同，由于字形調(diào)整后字體變得標(biāo)準(zhǔn)和統(tǒng)一，提取出的特征也會(huì)相對(duì)標(biāo)準(zhǔn)化，才能得出較好的聚類(lèi)結(jié)果.

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

針對(duì)傳統(tǒng)Canopy+K-means算法的一些不足，尤其是在處理大數(shù)據(jù)時(shí)面臨的效率和準(zhǔn)確度問(wèn)題，提出了基于Hadoop平臺(tái)上的K-means算法，并且基于“最大最小化原則”對(duì)Canopy算法進(jìn)行優(yōu)化.另外通過(guò)字形調(diào)整進(jìn)一步提高了特征數(shù)據(jù)的質(zhì)量.通過(guò)以上這些操作大大提高了聚類(lèi)的準(zhǔn)確率及效率.

[1]丁祥武, 郭濤, 王梅,等. 一種大規(guī)模分類(lèi)數(shù)據(jù)聚類(lèi)算法及其并行實(shí)現(xiàn)[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(5):1 063-1 071.

[2] 楊敏煜. 基于改進(jìn)聚類(lèi)算法的數(shù)據(jù)挖掘系統(tǒng)的研究與實(shí)現(xiàn)[D]. 成都：電子科技大學(xué), 2012.

[3]武霞, 董增壽, 孟曉燕. 基于大數(shù)據(jù)平臺(tái)HADOOP的聚類(lèi)算法K值優(yōu)化研究[J]. 太原科技大學(xué)學(xué)報(bào), 2015, 36(2):92-96.

[4]SINGH H, BAWA S. A mapreduce-based scalablediscovery and indexing of structured big data[J]. Future Generation Computer Systems, 2017, 73:32-43.

[5]李正兵, 羅斌, 翟素蘭,等. 基于關(guān)聯(lián)圖劃分的KMEANS算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013, 49(21):141-144.

[6]ABUBAKER M, ASHOUR W. Efficient data clustering algorithms:improvements over kmeans[J]. International Joural OF Intelligent Systems & Applications, 2013, 5(3):37-49.

[7]韓銳, 崔創(chuàng)雄. 一種基于CANOPY算法的聚類(lèi)優(yōu)化方法及系統(tǒng):中國(guó), CN201410194172.7[P]. 2015-11-25.

[8]尹超. 基于HADOOP的聚類(lèi)算法的研究與應(yīng)用[D]. 西安：西安建筑科技大學(xué), 2013.

[9]SREEDHAR C, KASIVISWANATH N, REDDY P C. Clustering large datasets using K-Means modified inter and intra clustering (KM-I2C) in hadoop[J]. Journal of Big Data, 2017, 4(1):8-11.

[10]余長(zhǎng)俊, 張燃. 云環(huán)境下基于CANOPY聚類(lèi)的FCM算法研究[J]. 計(jì)算機(jī)科學(xué), 2014, 41(S2):316-319.

[11]王崇陽(yáng), 傅迎華, 陳瑋,等. 一種改進(jìn)的稀疏表示的手寫(xiě)數(shù)字識(shí)別[J]. 信息技術(shù), 2015(2):5-8.

[12]YANG X, LIU W, TAO D, et al. Canonical correlation analysis networks for two -view image recognition [J]. Information Sciences, 2017, 385(C):338-352.