趙 雪，陳龍飛

(1燕山大學(xué)信息科學(xué)與工程學(xué)院，河北秦皇島，066004;2河北經(jīng)貿(mào)大學(xué)信息技術(shù)學(xué)院)

“大數(shù)據(jù)”時(shí)代的到來改變了人們?cè)S多處理問題的思路和想法，因?yàn)閿?shù)據(jù)的龐大，迫使人們不再單一追求處理數(shù)據(jù)的高精確率，而是要求快速;不再去對(duì)海量數(shù)據(jù)進(jìn)行類似數(shù)學(xué)統(tǒng)計(jì)似的抽樣處理，而是進(jìn)行全面處理;不再專注于找出數(shù)據(jù)之間的因果關(guān)系，而是注重?cái)?shù)據(jù)之間的相關(guān)性［1］，這對(duì)于聚類算法［2］來說是一個(gè)挑戰(zhàn)。

傳統(tǒng)的聚類算法通常是分析數(shù)據(jù)集中各個(gè)數(shù)據(jù)點(diǎn)的特征，從而將未知?dú)w屬的各個(gè)數(shù)據(jù)點(diǎn)進(jìn)行聚類。然而隨著“大數(shù)據(jù)”時(shí)代［3］的到來，分析數(shù)據(jù)點(diǎn)特征的工作變得非常困難，因?yàn)閿?shù)據(jù)點(diǎn)作為一個(gè)處理對(duì)象必然包含各種屬性，原來的數(shù)據(jù)對(duì)象可能只包含幾個(gè)屬性或幾層屬性，而現(xiàn)如今的處理對(duì)象動(dòng)輒包含幾百上千的屬性，其屬性的層次或結(jié)構(gòu)也變得多種多樣，或者說數(shù)據(jù)對(duì)象內(nèi)部本身是毫無結(jié)構(gòu)的［4］，這對(duì)于傳統(tǒng)聚類算法將是難以容忍的。它的主要障礙在于單個(gè)計(jì)算機(jī)的運(yùn)算速度和內(nèi)存容量不能處理這種數(shù)據(jù)大規(guī)模聚集的情況［5］，不管從處理速度還是效率都達(dá)不到大數(shù)據(jù)的處理要求。ROCK算法［6］是一個(gè)面向分類屬性的聚類算法，它以公共鄰居數(shù)作為評(píng)定數(shù)據(jù)點(diǎn)間相關(guān)性度量的標(biāo)準(zhǔn)，能夠較好地處理多屬性數(shù)據(jù)和無結(jié)構(gòu)數(shù)據(jù)，如果在此基礎(chǔ)上應(yīng)用典型的“大數(shù)據(jù)”計(jì)算模型MapReduce［7］對(duì)其進(jìn)行改良，將會(huì)在很大程度上提升對(duì)大數(shù)據(jù)進(jìn)行聚類的能力。

1 ROCK聚類算法在MapReduce上的實(shí)現(xiàn)

1.1 ROCK 算法介紹

ROCK(Robust Clustering Using Links)算法是一種凝聚的層次聚類算法，是由Guha等在1999年提出的，適用于類別屬性。

對(duì)于具有分類屬性的數(shù)據(jù)，傳統(tǒng)的聚類算法一般采用距離函數(shù)來度量數(shù)據(jù)對(duì)象間的相異度。然而，實(shí)驗(yàn)表明這種距離度量方法對(duì)具有分類屬性的數(shù)據(jù)不能得到好的聚類結(jié)果。而且絕大多數(shù)聚類算法只考慮點(diǎn)與點(diǎn)之間的相似性，因此在聚類的每一步，具有最大相似度的點(diǎn)被合并到同一個(gè)簇中很容易導(dǎo)致錯(cuò)誤的合并。例如，有幾個(gè)點(diǎn)來自2個(gè)顯著不同的簇，而這幾個(gè)點(diǎn)非常接近，那么根據(jù)上述的點(diǎn)與點(diǎn)之間的相似度，這2個(gè)顯著不同的簇將被錯(cuò)誤地合并在一起。為了避免這種情況，ROCK采取了更加周全的方法，也即引入了鄰居的概念［8］。如果2個(gè)點(diǎn)不僅它們本身相似，而且它們的鄰居也相似，則這2個(gè)點(diǎn)可能屬于同一個(gè)簇，因此被合并。

定義1 鄰居:2個(gè)點(diǎn)Pi和Pj，如果滿足sim(Pi，Pj)A，則稱Pi和Pj為鄰居。其中，sim是一個(gè)相似性度量函數(shù)，A是由用戶給定的閾值。sim可以是一個(gè)距離度量甚至是由領(lǐng)域?qū)＜姨峁┑姆切问交亩攘?，只要它能夠?biāo)準(zhǔn)化為0和1之間的值，而且這種值越大，相應(yīng)兩點(diǎn)間的相似度越高。

定義2 連接:link(Pi，Pj)為2個(gè)數(shù)據(jù)點(diǎn)Pi和Pj的相同鄰居數(shù)，值愈大表明Pi和Pj同一簇的幾率愈大。

在聚類過程中，需要最大化簇內(nèi)link(Pq，Pr)數(shù)量的同時(shí)最小化簇間link(Pq，Pr)的數(shù)量，即保證簇內(nèi)盡量相似、簇間盡量不相似。此式子能夠幫助找到簇內(nèi)最多鏈接的同時(shí)盡量減少簇間鏈接數(shù)。其中，ni為簇Ci中數(shù)據(jù)點(diǎn)的總數(shù)，f(θ)是根據(jù)數(shù)據(jù)集設(shè)定的一個(gè)函數(shù)。

此優(yōu)化函數(shù)用于合并相似簇，而且能夠有效避免出現(xiàn)離群數(shù)據(jù)點(diǎn)時(shí)將所有簇都合并。其中為2簇中預(yù)期交叉鏈接個(gè)數(shù)。ni為簇Ci中數(shù)據(jù)點(diǎn)的總數(shù)，nj為簇Cj中數(shù)據(jù)點(diǎn)的總數(shù)，link［Ci，Cj］指簇 Ci和簇 Cj之間的鏈接數(shù)。

ROCK算法流程如下:

■輸入?yún)?shù):包含n個(gè)數(shù)據(jù)點(diǎn)的集合S及預(yù)期簇?cái)?shù)k;

■最初階段，每個(gè)數(shù)據(jù)點(diǎn)為1簇;

■計(jì)算各點(diǎn)的鏈接數(shù);

■為每個(gè)簇i，建立1個(gè)區(qū)域堆q［i］，包含每個(gè)與簇i的鏈接數(shù)不為0的簇j;

■q［i］中的各簇 j依 g(i，j)值由大至小排序;

■建立全局堆(global heap)Q，包含每個(gè)q［i］的優(yōu)化函數(shù)最大值的簇j;

■每一回合，合并Q中最佳簇j與q［j］中的最佳簇;

■合并的同時(shí)重新運(yùn)算各區(qū)域堆及全域堆，包括新形成的簇;

■當(dāng)簇?cái)?shù)不小于k時(shí)，持續(xù)合并，此外當(dāng)所有q［i］=0時(shí)停止合并。

1.2 MapReduce編程模型

MapReduce是由Google提出的一種處理海量數(shù)據(jù)的并行編程模式［9］，用于大規(guī)模數(shù)據(jù)集的并行計(jì)算，由Map(映射)操作和Reduce(化簡)操作2個(gè)階段組成，Map操作把任務(wù)分解成為多個(gè)任務(wù)，Reduce操作把分解后任務(wù)處理的結(jié)果匯總起來，得到最終結(jié)果。

(1)MapReduce編程思想

以Hadoop為平臺(tái)的大數(shù)據(jù)處理模式，通過HDFS系統(tǒng)去進(jìn)行信息存儲(chǔ)、分享，使用MapReduce技術(shù)去進(jìn)行分析和挖掘，可以便宜、有效地將這些大量、高速、多變化的終端數(shù)據(jù)存儲(chǔ)下來，并能快速得到所需的結(jié)果。改進(jìn)后的ROCK算法命名為HD-ROCK算法。

HD-ROCK算法是在ROCK算法的基礎(chǔ)上進(jìn)行改進(jìn)的，它繼承了ROCK算法針對(duì)類別屬性進(jìn)行聚類的思想，同時(shí)將原算法中對(duì)數(shù)據(jù)進(jìn)行處理的部分進(jìn)行了分割、再整合的處理，在沒有改變?cè)惴▓?zhí)行順序的同時(shí)，提高了每一部分運(yùn)行的速度，使新算法的整體速度得到了提升。

數(shù)據(jù)去重是新算法的核心目的［10］，就是讓原始數(shù)據(jù)中出現(xiàn)次數(shù)超過1次的數(shù)據(jù)在輸出文件中只出現(xiàn)1次。

Map處理的是一個(gè)純文本文件，文件中存放的數(shù)據(jù)是每行表示1個(gè)用戶的姓名及其所購買的項(xiàng)目類別。Mapper處理的數(shù)據(jù)是由InputFormat分解過的數(shù)據(jù)集，其中InputFormat的作用是將數(shù)據(jù)集切割成小數(shù)據(jù)集InputSplit，每個(gè)InputSplit將由1個(gè)Mapper負(fù)責(zé)處理。此外，InputFormat中還提供了1個(gè)RecordReader的實(shí)現(xiàn)，并將1個(gè)InputSplit解析成＜key，value＞對(duì)提供給map函數(shù)。InputFormat的默認(rèn)值是TextInputFormat，它針對(duì)文本文件，按行將文本切割成 InputSplit，并用 LineRecordReader將 InputSplit解析成＜key，value＞對(duì)，key是行在文本中的位置，value是文件中的一行。Map的結(jié)果會(huì)通過partion分發(fā)到Reducer，Reducer做完Reduce操作后，將通過以格式OutputFormat輸出。Mapper最終處理的結(jié)果對(duì)＜key，value＞，會(huì)送到Reducer中進(jìn)行合并，合并時(shí)有相同key的鍵/值對(duì)則送到同一個(gè)Reducer上。Reducer是所有用戶定制Reducer類的基礎(chǔ)，它的輸入是key和這個(gè)key對(duì)應(yīng)的所有value的一個(gè)迭代器，同時(shí)還有Reducer的上下文。Reduce的結(jié)果由 Reducer.Context的 write方法輸出到文件中。這就是一個(gè)mapreduce的循環(huán)。

新算法對(duì)原算法的改變主要體現(xiàn)在2個(gè)方面:一是對(duì)用戶之間相似度的計(jì)算和共同鄰居數(shù)的計(jì)算上;二是在分別建立堆q(i)以及相近堆的合并上。

因?yàn)镽OCK算法中需要計(jì)算任意2個(gè)用戶之間的相似度，并根據(jù)相似度判斷鄰居數(shù)，而且數(shù)據(jù)集中任意一個(gè)數(shù)據(jù)對(duì)象之間是完全獨(dú)立、沒有關(guān)聯(lián)的，所以可以利用Hadoop思想對(duì)其進(jìn)行分布式處理，用十多臺(tái)甚至上百臺(tái)設(shè)備去處理原來1臺(tái)設(shè)備所處理的問題將大大提升處理速度，而且不會(huì)遇到同步和異步問題。

在建立堆q(i)和Q時(shí)需要消耗大量的內(nèi)存，而當(dāng)進(jìn)行堆與堆之間的合并時(shí)，同一時(shí)間內(nèi)對(duì)所有堆的大小進(jìn)行比較，這對(duì)于1臺(tái)設(shè)備而言是無法承受的，所以運(yùn)用分布式進(jìn)行處理，讓不同的設(shè)備建立代號(hào)不同的堆，需要合并時(shí)會(huì)按照鍵值對(duì)的值進(jìn)行處理，這將大大地縮減建立堆和處理堆的時(shí)間。

HD-ROCK算法的流程如下(圖1):

●設(shè)定數(shù)據(jù)集S包含n個(gè)數(shù)據(jù)點(diǎn)，預(yù)期簇?cái)?shù)為k;

●將每個(gè)數(shù)據(jù)點(diǎn)設(shè)定為1個(gè)簇;

●將數(shù)據(jù)集S分為m組，在每份中，分別計(jì)算分組中每個(gè)點(diǎn)與整個(gè)數(shù)據(jù)集S中的每個(gè)點(diǎn)之間的相似度，得到數(shù)據(jù)集S的鄰居矩陣(是鄰居的為1，不是鄰居的為0)，其中D是S數(shù)據(jù)集中的數(shù)據(jù)，n是S集中數(shù)據(jù)的個(gè)數(shù);

●計(jì)算分組中每個(gè)數(shù)據(jù)點(diǎn)與整個(gè)數(shù)據(jù)集S中每個(gè)數(shù)據(jù)點(diǎn)之間的共同鄰居數(shù)，得到鍵值對(duì)L＜(Pi，Pj)，link(Pi，Pj)＞，其中Pi和Pj為數(shù)據(jù)集S中的任意點(diǎn)，并得到鄰居數(shù)矩陣;

●為各組中每個(gè)數(shù)據(jù)點(diǎn)建立堆q(i)＜Pi，link(Pi，Pj)＞;

●建立全局簇Q，降序存放所有堆q(i);

●在Q中找到最大元素的編號(hào)u;

●在u中找到最大元素的編號(hào)v;

●用優(yōu)化函數(shù)進(jìn)行合并，去除合并前的簇;

●更新Q;

●直到簇?cái)?shù)小于k時(shí)結(jié)束;

(2)MapReduce函數(shù)的設(shè)計(jì)

Map1函數(shù)，是Map函數(shù)的主要構(gòu)成之一，它的作用主要在于對(duì)數(shù)據(jù)集進(jìn)行分塊處理，是分布式處理的開端，而本函數(shù)的任務(wù)則是對(duì)數(shù)據(jù)集進(jìn)行并行化處理，計(jì)算數(shù)據(jù)集S中各個(gè)數(shù)據(jù)點(diǎn)之間的相似性，并形成中間鍵值對(duì)＜key，value＞，即＜Pj，鄰居矩陣Nj＞。其偽碼描述如下:

Combine2的任務(wù)是合并Q中最相似簇并判斷Q中簇的個(gè)數(shù)，如果大于k，則返回map3繼續(xù)執(zhí)行。

1.3 時(shí)間復(fù)雜度和空間復(fù)雜度分析

假設(shè)數(shù)據(jù)集中樣本點(diǎn)的總數(shù)為n，設(shè)備數(shù)目為m，其中Mm和Ma分別為1個(gè)點(diǎn)的平均近鄰數(shù)和最大近鄰數(shù)。

(1)原算法首先計(jì)算各個(gè)數(shù)據(jù)點(diǎn)之間的相似度，這一階段的時(shí)間復(fù)雜度為O(n);而新算法也同樣需要計(jì)算各個(gè)數(shù)據(jù)點(diǎn)之間的相似度，但是由于新算法采用了分布式處理，所以其時(shí)間復(fù)雜度為O(n/m);

(2)在計(jì)算完數(shù)據(jù)點(diǎn)之間的相似度后需要計(jì)算鄰接矩陣，原算法在這一階段的時(shí)間復(fù)雜度為O(n*Mm*Ma);而新算法在此階段的時(shí)間復(fù)雜度同樣為O(n*Mm*Ma/m);

(3)計(jì)算共同鄰居數(shù)，原算法在這一階段的時(shí)間復(fù)雜度為O(n2);而新算法在此階段的時(shí)間復(fù)雜度同樣為O(n2/m);

(4)建立堆的時(shí)間。原算法中，總的建堆時(shí)間為O(n2)，執(zhí)行循環(huán)的次數(shù)為O(n2*lgn);而新算法在此階段的建堆時(shí)間為O(n2/m)，執(zhí)行循環(huán)的次數(shù)也是O(n2*lgn);

所以ROCK算法時(shí)間復(fù)雜度為O(n+2n2+n*Mm*Ma+n2*lgn);而新算法的時(shí)間復(fù)雜度為O((2n2+n*Mm*Ma+n*m)/m+n2*lgn)。

由此可知，其中m的數(shù)量決定新算法的效率。由于新算法只是對(duì)原算法中的可分離的獨(dú)立數(shù)據(jù)進(jìn)行處理，不涉及數(shù)據(jù)類型的改變，所以兩者的空間復(fù)雜度都為O(min{n2，n*Mm*Ma})。

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

實(shí)驗(yàn)的目的在于驗(yàn)證基于MapReduce的ROCK聚類算法(HD-ROCK)在處理數(shù)據(jù)尤其是高維數(shù)據(jù)上的執(zhí)行速度和正確率。為了讓實(shí)驗(yàn)更加鮮明，將通過2組測試數(shù)據(jù)來驗(yàn)證新算法的正確性和時(shí)效性。

2.1 實(shí)驗(yàn)環(huán)境

采用Eclipse+Hadoop的結(jié)合去驗(yàn)證新算法的可行性。

2.1.1 Hadoop的配置 Hadoop有3種運(yùn)行方式:單機(jī)模式、偽分布式模式和完全分布式模式。單機(jī)模式中，默認(rèn)情況下，Hadoop被配置成一個(gè)以非分布式模式運(yùn)行的獨(dú)立java進(jìn)程。偽分布式模式Hadoop可以在單節(jié)點(diǎn)上運(yùn)行，用不同的java進(jìn)程模擬分布式運(yùn)行中的各類節(jié)點(diǎn)，如NameNode，DataNode，master，slave和taskTracker。在實(shí)際使用中，使用3臺(tái)機(jī)器來搭建集群，3臺(tái)機(jī)器均使用centOS6.3操作系統(tǒng)(linux操作系統(tǒng)之一)，第1臺(tái)用于做NameNode，master和 jobTracker。另外 2 臺(tái)用于做 DataNode，slave和 taskTracker。3臺(tái)機(jī)器如表1所示。

圖1 HD-ROCK算法流程

表1 Hadoop集群信息

2.1.2 eclipse在 Hadoop 中的配置

(1)安裝MapReduce插件(Hadoop自帶)。將 hadoop-0.20.2-eclipse-plugin.jar copy 至 eclipse/plugin 目錄下即可。

(2)打開eclipse，創(chuàng)建MapReduce項(xiàng)目File＞New＞Project。在彈出的對(duì)話框中選擇 MapReduce Project，輸入 project name，如 HD-ROCK。

(3)建立 DFS Locations。Window-＞Show View-＞Other-＞MapReduce Tools-＞MapReduce Location。MapReduce Location配置如圖2所示。

最后配置eclipse中的jdk，并將本地的 text文件導(dǎo)入到其中。

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

為了驗(yàn)證基于Hadoop平臺(tái)的HD-ROCK算法在處理大數(shù)據(jù)對(duì)象的正確性和時(shí)效性，采用2組測試數(shù)據(jù)進(jìn)行驗(yàn)證。數(shù)據(jù)集DataSet1采用KDD Cup’99提供的經(jīng)典數(shù)據(jù)集，用于測試基于Hadoop的HDROCK聚類結(jié)果的正確性。DataSet2采用加利福尼亞大學(xué)的機(jī)器學(xué)習(xí)數(shù)據(jù)集，其中包含許多隨機(jī)的離群點(diǎn)分布在整個(gè)數(shù)據(jù)空間中，主要用于測試基于Hadoop平臺(tái)聚類算法的時(shí)效性，即能不能做到處理速度的大幅提升。

表2 單機(jī)和HD-ROCK的聚類準(zhǔn)確率比較

在單機(jī)模式下和基于Hadoop平臺(tái)HD-ROCK算法對(duì)數(shù)據(jù)集DataSet1的聚類結(jié)果如表2所示。測試結(jié)果表明在這2種模式下，HD-ROCK算法的聚類質(zhì)量是基本等價(jià)的。從而驗(yàn)證了在Hadoop平臺(tái)上ROCK聚類算法的聚類能力較強(qiáng)。

為驗(yàn)證基于 Hadoop平臺(tái)的 HDROCK算法的時(shí)效性，采用多次復(fù)制數(shù)據(jù)集DataSet2的方法獲得大規(guī)模數(shù)據(jù)，并把不同數(shù)據(jù)量分別在單機(jī)和Hadoop平臺(tái)上運(yùn)行。其結(jié)果如圖3所示。

圖2 mapReduce location配置

可見，基于Hadoop平臺(tái)的HD-ROCK算法的執(zhí)行速度比單機(jī)明顯提高，數(shù)據(jù)量越大，這種優(yōu)勢越明顯，因此更適合大數(shù)據(jù)的處理。

3 結(jié) 論

針對(duì)普通聚類算法難以處理的數(shù)據(jù)維數(shù)過高、數(shù)據(jù)量過大等問題提出了基于Hadoop的Rock聚類算法，該算法對(duì)Hadoop平臺(tái)下的MapReduce編程模型進(jìn)行改編，將難以用單機(jī)處理的數(shù)據(jù)分散化，提升了算法處理數(shù)據(jù)吞吐量的同時(shí)大幅提升了處理速度，并通過實(shí)驗(yàn)證明了這一點(diǎn)。

然而該算法也有許多需要改善的地方，比如在建立堆棧的過程中出現(xiàn)的不能同步處理的問題等，筆者將會(huì)在日后的學(xué)習(xí)中逐步解決該問題。

［1］ 孟小峰，慈祥.大數(shù)據(jù)管理:概念、技術(shù)與挑戰(zhàn)［J］.計(jì)算機(jī)研究與發(fā)展，2013，50(1):146-169.

［2］ 陳黎飛.高維數(shù)據(jù)的聚類方法研究與應(yīng)用［D］.廈門:廈門大學(xué)，2008.

［3］ SCHONBERGER Viktor Mayer.大數(shù)據(jù)時(shí)代:生活、工作與思維的大變革［M］.杭州:浙江人民出版社，2012.

［4］ 韓晶.大數(shù)據(jù)服務(wù)若干關(guān)鍵技術(shù)研究［D］.北京:北京郵電大學(xué)，2013.

［5］ 齊鳴.共享內(nèi)存并行系統(tǒng)上空間數(shù)據(jù)檢索及優(yōu)化研究［D］.北京:中國科學(xué)技術(shù)大學(xué)，2012.

［6］ 高虎明，王歡歡，張悅.基于ROCK聚類與相似傳遞性的圖書協(xié)同過濾算法［J］.微計(jì)算機(jī)信息，2010，26(33):210-212.

［7］ 覃雄派，王會(huì)舉，杜小勇，等.大數(shù)據(jù)分析-RDBMS與MapReduce的競爭與共存［J］.軟件學(xué)報(bào)，2012，23(1):32-45.

［8］ 王榮，李晉宏，宋威.基于關(guān)鍵字的用戶聚類算法［J］.計(jì)算機(jī)工程與設(shè)計(jì).2012，33(9):3 553-3 557.

［9］ 鄭啟龍，房明，汪勝，等.基于MapReduce模型的并行科學(xué)計(jì)算［J］.微電子學(xué)與計(jì)算機(jī)，2009，26(8):13-17.

［10］ 譚玉娟.數(shù)據(jù)備份系統(tǒng)中數(shù)據(jù)去重技術(shù)研究［D］.湖北:華中科技大學(xué)，2012.

(責(zé)任編輯:石瑞珍)