面向大數據挖掘的Hadoop框架K均值聚類算法

李 爽，陳瑞瑞，林 楠

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

0 引 言

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

1 本文算法

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

1.1 MapReduce模型和Hadoop框架

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

1.2 K均值聚類算法

(1)

其中

(2)

其中，Si表示集合Si中樣本的數量。

一般地，K均值聚類算法通常采用迭代策略求解目標函數的局部最優解。具體實現算法見表1。

表1 K均值聚類算法

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

1.3 HKM聚類算法

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

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

(1)初始聚類中心提取

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

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

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

(3)

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

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

(2)數據塊聚類

(4)

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

表2 權重K均值聚類算法

(3)融合聚類

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

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

2 實驗與分析

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

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

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

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

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

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

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

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

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

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

3 結束語

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