面向大數(shù)據(jù)挖掘的Hadoop框架K均值聚類算法

李 爽，陳瑞瑞，林 楠

(1.鄭州工業(yè)應用技術學院 信息工程學院，河南 鄭州 451199；2.鄭州大學 軟件與應用科技學院，河南 鄭州 451199)

0 引 言

采用聚類等無監(jiān)督方法挖掘大數(shù)據(jù)中的隱藏模式是數(shù)據(jù)挖掘的有效手段之一，在數(shù)據(jù)建模和數(shù)據(jù)預處理等任務中應用廣泛[1]。聚類是一種無監(jiān)督的學習方法，用于將數(shù)據(jù)劃分成不同的簇，各個簇中的數(shù)據(jù)彼此相似，而不同簇中數(shù)據(jù)具有明顯差異。當數(shù)據(jù)沒有標記的情況下，采用聚類算法進行數(shù)據(jù)挖掘，可以構建獨立的數(shù)據(jù)模型或為其它數(shù)據(jù)建模和分析奠定基礎，廣泛應用于社會網(wǎng)絡、生物信息學和圖像處理等眾多研究領域[2,3]。K均值聚類算法是目前應用最為廣泛的聚類算法之一，該算法采用劃分的思想，使用均方誤差最小準則將數(shù)據(jù)劃分到不同的簇。其優(yōu)點是聚類過程不需要監(jiān)督，簡單快捷，對于服從正態(tài)分布的數(shù)據(jù)能夠達到較好的聚類效果。但在面向大數(shù)據(jù)挖掘應用時，K均值聚類算法的運算效率難以滿足要求[4-6]。盡管目前也提出了許多改進的K均值聚類算法[7-9]，如文獻[9]針對經(jīng)典K均值聚類算法隨機選擇的初始聚類中心可能不合理的問題，提出了一種改進的K均值聚類算法，結合底層數(shù)據(jù)結構的相關性改進初始聚類中心的選擇策略，提高聚類的收斂速度，進而提高聚類效率。但是在大數(shù)據(jù)挖掘應用時，聚類效率仍然很低。本文結合大數(shù)據(jù)挖掘應用中常使用的Hadoop框架，設計一種Hadoop框架K均值聚類算法，采用分布式并行處理方式加速聚類過程。針對Hadoop框架的Map階段和Reduce階段的不同分工，對K均值算法進行修改，分別提出了權重K均值聚類算法和加權融合K均值聚類算法，在保持聚類準確率的前提下大幅提升大數(shù)據(jù)聚類時K均值聚類算法的運算效率。

1 本文算法

在大數(shù)據(jù)挖掘應用中使用K均值聚類算法進行數(shù)據(jù)聚類的計算成本很高。為了降低計算成本，本文提出一種面向大數(shù)據(jù)挖掘的Hadoop框架K均值聚類算法，目標是設計一種快速、精確的大數(shù)據(jù)聚類算法。下面首先介紹Hadoop框架和MapReduce模型，然后介紹經(jīng)典的K均值聚類算法，最后詳細介紹本文提出的Hadoop框架K均值聚類算法(為了便于描述，簡記為HKM聚類算法)。

1.1 MapReduce模型和Hadoop框架

Hadoop是在大數(shù)據(jù)挖掘領域廣泛使用的分布式處理框架之一，該框架使用的是MapReduce編程模型。在這個框架下，首先對數(shù)據(jù)集進行初始化，然后采用兩個步驟來解決數(shù)據(jù)分析處理問題。首先，通過Hadoop分布式文件系統(tǒng)(hadoop distributed file system，HDFS)將大數(shù)據(jù)劃分為多個數(shù)據(jù)塊。在各個數(shù)據(jù)塊上執(zhí)行Map任務，并將結果發(fā)送到Reduce任務。Reduce任務對結果進行融合，并將融合后的最終結果寫入HDFS。在一些MapReduce算法中，可以迭代地執(zhí)行這些步驟。Hadoop框架可以應用于具有大量數(shù)據(jù)的分布式系統(tǒng)上。此外，該框架的容錯能力很強，是大數(shù)據(jù)挖掘常用的數(shù)據(jù)處理框架之一[10]。本文采用Hadoop框架改進K均值聚類算法，解決經(jīng)典K均值聚類算法在大數(shù)據(jù)挖掘應用中處理效率低的問題。

1.2 K均值聚類算法

(1)

其中

(2)

其中，Si表示集合Si中樣本的數(shù)量。

一般地，K均值聚類算法通常采用迭代策略求解目標函數(shù)的局部最優(yōu)解。具體實現(xiàn)算法見表1。

表1 K均值聚類算法

由表1可見，K均值聚類算法在迭代過程中反復劃分簇和更新聚類中心，直至相鄰兩次迭代結果中聚類中心變化小于設定的誤差ε或者迭代次數(shù)大于上限值tmax。

1.3 HKM聚類算法

本文設計Hadoop框架K均值聚類算法的目標是提供一種可以在Hadoop平臺上應用的快速K均值聚類算法，在保證聚類精度的前提下實現(xiàn)高效的大數(shù)據(jù)聚類?；驹O計思路是：首先，將大數(shù)據(jù)切分成許多數(shù)據(jù)塊；然后，每一個數(shù)據(jù)塊獨立進行聚類；最后，對各個數(shù)據(jù)塊的聚類結果進行融合，得到最終的聚類結果。為了提高各個數(shù)據(jù)塊的聚類收斂速度，本文在初始化階段先進行一次K均值聚類，得到初始的聚類中心，后續(xù)各個數(shù)據(jù)塊在這些初始聚類中心的基礎上進行迭代聚類，提高收斂速度。基于這一思路，本文的HKM算法主要分為3個階段：①初始聚類中心提??；②數(shù)據(jù)塊聚類；③融合聚類。

按照MapReduce編程模型，數(shù)據(jù)塊聚類對應于Map階段，融合聚類對應于Reduce階段。首先，HKM算法使用HDFS選項從主節(jié)點的數(shù)據(jù)集中隨機選擇一些數(shù)據(jù)，并采用經(jīng)典的K均值聚類算法進行聚類，提取初始聚類中心并發(fā)送到Hadoop緩存文件。在每一次迭代過程中使用這些初始的聚類中心提高算法的收斂速度。然后，在各個分布式節(jié)點，使用K均值聚類算法對節(jié)點所分配的數(shù)據(jù)塊進行聚類，得到各個數(shù)據(jù)塊的聚類中心。為了便于實現(xiàn)后續(xù)Reduce階段的聚類融合，本文提出一種權重K均值聚類算法，在每個數(shù)據(jù)塊聚類時根據(jù)聚類簇的緊湊性生成一個權重項，用于評價該聚類中心的重要程度。最后在Reduce階段提出一種加權融合K均值聚類算法，對各個數(shù)據(jù)塊的聚類中心和權重項進行融合，得到最終的聚類中心。詳細描述如下。

(1)初始聚類中心提取

為了提高數(shù)據(jù)塊聚類的收斂速度，本文先采用K均值聚類算法在隨機選擇的一個數(shù)據(jù)子集上提取初始化的聚類中心，將其存儲在Hadoop的分布式緩存文件中。分布式緩存文件是Hadoop的一個基本特征，可由各個節(jié)點獨立訪問。這樣，各個節(jié)點在對數(shù)據(jù)塊進行K均值聚類之前，可以先讀取分布式緩存文件中的初始聚類中心，替換表1所示算法中初始化階段隨機選擇的初始聚類中心。因為本文提取的初始聚類中心是由大數(shù)據(jù)的一個子集聚類而來的，而不是隨機選取的，因此更能反映大數(shù)據(jù)實際的數(shù)據(jù)分布。因此用其作為初始聚類中心，可以降低聚類迭代次數(shù)，提高收斂速度。快速收斂在大數(shù)據(jù)領域至關重要，因為分析大量數(shù)據(jù)是非常耗時的。

二十一世紀網(wǎng)絡科學技術飛速發(fā)展，移動互聯(lián)網(wǎng)更是融入到人們的日常生活當中，因此，傳統(tǒng)的媒介都已經(jīng)通過網(wǎng)絡技術向新媒體發(fā)展與融合。傳統(tǒng)媒介傳播方式單一，宣傳成本高，技術不足，再加上傳統(tǒng)媒介的本身的制約，很難取得很大的發(fā)展。

為了提取初始聚類中心，需要從大數(shù)據(jù)中選取一個數(shù)據(jù)子集。本文采用隨機選取的方式選擇大數(shù)據(jù)中的部分數(shù)據(jù)構成數(shù)據(jù)子集。該數(shù)據(jù)子集的尺寸越大，得到的初始聚類中心的精度越高，但運算效率越低。給定錯誤率α，數(shù)據(jù)子集的尺寸可以近似表示為[11]

(3)

其中，r表示大數(shù)據(jù)中各類別占比的相對差異，vα是與α相關的一個經(jīng)驗值。在本文中，取α=0.05、vα=1.27359、r=0.10。

對于所選擇的尺寸為N的數(shù)據(jù)子集，本文采用表1所示的K均值聚類算法進行聚類，得到初始的聚類中心，并將其存儲在Hadoop的分布式緩存文件中。

(2)數(shù)據(jù)塊聚類

(4)

事實上，上式中的分母項為各簇中每一個樣本與聚類中心之間的歐氏距離的平均值。很明顯，該值越小，說明各簇中的樣本離聚類中心的距離越近，數(shù)據(jù)越緊湊。因此，對應的權重應當越大。

表2 權重K均值聚類算法

(3)融合聚類

(1)初始聚類中心不采用隨機選擇方式生成，而是從Map階段生成的聚類中心中選出權重最大的那一組作為初始聚類中心。

表3 加權融合K均值聚類算法

2 實驗與分析

本文算法的設計目標是提升大數(shù)據(jù)挖掘應用場合K均值聚類算法的運算效率，因此實驗時主要測量算法的聚類耗時指標。另外，在提升K均值聚類算法運算效率的同時還要關注聚類是否正確，因此實驗時還要測量算法的聚類準確率指標。

本文選擇經(jīng)典K均值聚類算法(簡記為KM)[6]和文獻[9]改進的K均值聚類算法(簡記為MKM)進行對比實驗。實驗所用的大數(shù)據(jù)集選擇HIGGS數(shù)據(jù)集，該數(shù)據(jù)集包含1100萬條記錄，每條記錄有28個屬性特征。

實驗平臺包括1個主節(jié)點和8個從節(jié)點，主節(jié)點的硬件配置為：Intel Core i7-2600 CPU，16GB RAM，1TB硬盤。從節(jié)點的硬件配置為：Intel Core i5-4460 CPU，16 GB RAM，1TB硬盤。操作系統(tǒng)都是CentOS 7，Hadoop版本都為2.7.1，各節(jié)點通過100 Mbps的本地網(wǎng)絡進行連接。

3種對比算法中的公共參數(shù)設置相同，具體為：簇數(shù)量k=2，迭代次數(shù)上限tmax=1000。針對不同的誤差ε，測試不同算法的聚類耗時和聚類準確率的變化情況，結果分別如圖1和圖2所示。

圖1 聚類耗時隨誤差的變化曲線(橫坐標無單位)

圖2 聚類準確率隨誤差的變化曲線(橫坐標無單位)

由圖1和圖2可見，隨著誤差ε的增加，3種算法的聚類耗時都會降低，而聚類準確率也有所下降。因為誤差ε越大，聚類算法的收斂速度越快，聚類耗時隨之下降。但是，快速收斂也可能引起迭代搜索的解并不是最優(yōu)解，因此，聚類準確率可能會下降。

對比圖1中3種算法的聚類耗時曲線，MKM算法的聚類耗時與KM算法相比有所降低，但是還是明顯高于本文算法。以誤差ε=1e-6為例，本文算法的聚類耗時為MKM算法的13.6%、為KM算法的14.4%?？梢?，本文算法對于KM算法的運算效率提升是非常明顯的。這是因為本文算法將大數(shù)據(jù)的聚類分配到多個節(jié)點上進行，從而降低了聚類的耗時，而且，本文算法的聚類耗時受誤差ε的影響也比較小，因此曲線比較平緩。

對比圖2中3種算法的聚類準確率曲線，可見3種算法的聚類準確率相差不大，且誤差ε較大時本文算法的聚類準確率略高于其它兩種算法，這是因為本文算法將大數(shù)據(jù)劃分成分塊聚類，各數(shù)據(jù)塊聚類時采用權重K均值和加權融合K均值算法提高聚類精度，弱化了誤差參數(shù)對整體聚類準確率的影響。

綜上所述，本文算法在保持聚類準確率的前提下大幅提升了大數(shù)據(jù)聚類時K均值聚類算法的運算效率。

3 結束語

本文提出了一種面向大數(shù)據(jù)挖掘應用的Hadoop框架K均值聚類算法。該算法結合Hadoop框架和MapReduce模型，設計大數(shù)據(jù)的K均值聚類算法，與經(jīng)典K均值聚類算法相比，主要是在Map階段提出了權重K均值聚類算法，用于提取各個節(jié)點上數(shù)據(jù)塊的聚類中心和權重。另外在Reduce階段提出了加權融合K均值聚類算法，用于對Map階段得到的聚類中心和權重進行融合，得到最終的聚類結果。本文算法的主要特色是將大數(shù)據(jù)聚類的耗時分攤到各個節(jié)點上，從而提高大數(shù)據(jù)聚類效率。通過在HIGGS數(shù)據(jù)集上進行聚類對比實驗與分析，驗證了本文算法的聚類準確率與經(jīng)典K均值聚類算法和改進的MKM聚類算法相當，但聚類耗時遠低于所對比的兩種聚類算法。