馬 俏，萬劍怡，王明文

(江西師范大學(xué)計算機信息工程學(xué)院，江西 南昌 330022)

0 引言

聚類分析是根據(jù)數(shù)據(jù)集中數(shù)據(jù)的不同特征，將數(shù)據(jù)集劃分為不同的簇，使得簇內(nèi)相似度盡可能高，簇間相似度盡可能低的過程。文本聚類是在傳統(tǒng)聚類分析的基礎(chǔ)上發(fā)展的，它基于“聚類假設(shè)”:相關(guān)文檔之間的相似性比無關(guān)文檔之間的相似性更大。該聚類是一種無監(jiān)督的文本分類，通常采用向量空間模型來處理，它的主要思想是，每一個詞都作為特征空間坐標系的一維，將文檔集看作是一組正交特征向量組成的特征空間，每個文檔表示為其中的一個規(guī)范化特征向量。這種描述方法簡單直接，但也使得文本向量空間變得高維而且稀疏，一個文檔集可能會包含數(shù)十萬個不同的特征，高維的特征空間不僅增加聚類算法的處理時間，而且對算法的精度也產(chǎn)生影響。雖然目前有很多對文檔特征降維的技術(shù)可以減少文本聚類的復(fù)雜度，但是在降低維度的同時容易刪除對聚類有用的信息。為了最大限度保留這些信息，本文從另一個角度來考慮文本聚類方法——協(xié)同聚類(co-clustering)。

協(xié)同聚類又稱雙聚類、二模聚類，是一種允許對一個矩陣的行和列同時聚類的數(shù)據(jù)挖掘技術(shù)。眾所周知，文本文檔是由一系列特征構(gòu)建的，而這些特征存在著潛在的相關(guān)關(guān)系，基于文檔的聚類算法無法考慮到這些潛在關(guān)系，為此有人提出協(xié)同聚類的思想。這種從多維度進行聚類分析的方法對聚類效果的提高具有重要的指導(dǎo)意義。目前協(xié)同聚類分析方法廣泛應(yīng)用于文本挖掘、生物信息學(xué)、推薦系統(tǒng)和圖挖掘等領(lǐng)域。文獻［4］從理論上證明了協(xié)同聚類算法是收斂的。文獻［3］將協(xié)同聚類算法應(yīng)用到基因表達式數(shù)據(jù)，表現(xiàn)出良好的聚類效果。文獻［2］和文獻［6］分別將協(xié)同聚類算法應(yīng)用到文本聚類分析和過濾推薦算法中，也取得了很好的效果。然而這些研究都是基于串行算法的，隨著數(shù)據(jù)量的不斷增長，勢必會存在內(nèi)存不足以及運行時間太長等問題。為此本文考慮運用MapReduce的并行框架對協(xié)同聚類算法進行改進，使得協(xié)同聚類算法能在保證效果的同時提高運行的效率。

MapReduce分布式編程模式是對大規(guī)模數(shù)據(jù)集進行并行計算的主要模式之一，也是目前最流行的并行計算框架。它使用簡單，易于實現(xiàn)且擴展性強。目前，MapReduce已被廣泛地應(yīng)用于日志分析、海量數(shù)據(jù)的排序、在海量數(shù)據(jù)中查找特定模式等場景中。文獻［4］提出了一種基于MapReduce的協(xié)同聚類算法框架，它綜合了各種協(xié)同聚類算法的公共特點，以框架的形式搭建了MapReduce并行算法，這種算法簡單且易于理解，但是算法的實現(xiàn)復(fù)雜，不利于開發(fā)人員研究具體的算法。

本文針對最小化殘差平方和協(xié)同聚類算法提出更簡單且更容易理解的并行協(xié)同聚類算法(MR_coclustering)，該算法采用分布式存儲方式存儲數(shù)據(jù)，讀寫速度快，存儲容量大，實現(xiàn)了算法的可擴展性，提高算法運行速度。實驗結(jié)果表明，該算法在Hadoop上的運行時間隨著集群中機器結(jié)點個數(shù)的增加急劇下降，說明了算法具有很好的可擴展性。

1 協(xié)同聚類算法(co-clustering算法)

在本文中，數(shù)據(jù)集表示為文檔結(jié)點的集合和特征結(jié)點的集合，其中每個文檔結(jié)點與每個特征結(jié)點之間有一條邊，邊的權(quán)值是文檔在特征上的tf-idf值。如果權(quán)值為0，則忽略該邊。協(xié)同聚類試圖將該圖劃分成不相交的簇，其中每個簇由一個文檔結(jié)點集和一個特征結(jié)點集組成。該聚類的目標是最大化簇中文檔結(jié)點和特征結(jié)點之間的邊的權(quán)值，最小化不同簇的文檔結(jié)點和特征結(jié)點之間邊的權(quán)值。圖1描述的是文檔和特征之間的關(guān)聯(lián)關(guān)系。左邊{d1，...，dn}表示文檔集合，右邊{t1，…，tm}表示特征集合，文檔與特征之間的連線rij表示文檔和特征之間的關(guān)聯(lián)程度。

圖1 文檔和特征之間的關(guān)聯(lián)圖

協(xié)同聚類算法的基本思想是:先初始化行列矩陣索引，迭代地對矩陣的行和列分別聚類，先對矩陣的行進行聚類，計算聚類簇中各個元素與類中心的關(guān)聯(lián)關(guān)系，將其加入到與它相似度最大的一個聚類簇中。列聚類的過程與行聚類類似。每次聚類可將文檔劃分到與它更相似的行聚類簇中。當各個聚類簇相對穩(wěn)定時停止迭代過程。調(diào)整后的聚類簇的內(nèi)聚性更強，類間的區(qū)分度更大，有效地提高聚類的效果。

為了方便閱讀，在介紹算法具體流程之前，首先定義一些常用到的符號，如表1所示。

表1 常用符號表示

本文采用的協(xié)同聚類算法是基于最小化殘差平方和的思想。殘差平方和的定義為:數(shù)據(jù)集的每個輸入與協(xié)同聚類的平均值的差的平方的總和。即:

協(xié)同聚類的串行算法流程如圖2所示。

從該算法中可以看出，計算最復(fù)雜的部分在第三步的迭代中，每次迭代對列聚類的時間復(fù)雜度為O(n)，更新U的時間復(fù)雜度為O(m×n)，對行聚類的時間復(fù)雜度為 O(m)。由于O(m×n)＞O(m)、O(n)，所以一次迭代的時間復(fù)雜度為O(m×n)，而由于迭代的次數(shù)不會超過設(shè)置的閾值T，所以協(xié)同聚類算法的時間復(fù)雜度為O(T×m×n)。

圖2 協(xié)同聚類的串行算法

2 MapReduce分布式編程模式

MapReduce分布式編程模式是由Google實驗室首先提出的，主要用于大規(guī)模數(shù)據(jù)集的并行計算。它是鑒于函數(shù)式的編程模式，把海量數(shù)據(jù)集的操作抽象為Map和Reduce兩個集合操作，并且對底層分布式過程進行了封裝，大大簡化了程序并行化的實現(xiàn)。Map(映射)過程和Reduce(規(guī)約)過程是MapReduce的2個關(guān)鍵過程。在MapReduce計算模式中需要用戶提供Map函數(shù)和Reduce函數(shù)以實現(xiàn)映射和規(guī)約過程，這2個函數(shù)對一組輸入的鍵值對(key/value)進行計算，得出另一組鍵值對:

Map函數(shù)接收一組輸入鍵值對(k1，v1)經(jīng)過處理產(chǎn)生一組中間鍵值對(k2，v2)，然后MapReduce函數(shù)庫將所有相同的k2鍵值對應(yīng)的v2產(chǎn)生值的集合list(v2)，發(fā)送給Reduce函數(shù)，進一步處理、歸并中間鍵的集合，最后形成鍵值對集合list(k3，v3)。圖3是數(shù)據(jù)流在MapReduce計算過程中的傳輸過程示意圖，首先將任務(wù)分割后進入Map階段，然后將Map階段的中間輸出傳遞給Reduce函數(shù)，Reduce函數(shù)經(jīng)過聚合輸出相應(yīng)的鍵值對。

化學(xué)是一門中心的、實用的和創(chuàng)造性的學(xué)科，是護理專業(yè)基礎(chǔ)課程的基礎(chǔ)，是醫(yī)務(wù)工作者必須掌握的一門學(xué)科。21世紀是生命科學(xué)時代，醫(yī)學(xué)教育進入多學(xué)科融合和創(chuàng)新的時期，護理人員應(yīng)具備相應(yīng)的理論知識和技能，以及較強的實踐操作能力。為培養(yǎng)出合格的實用型護理人才，在化學(xué)課程中實施STS教育，培養(yǎng)學(xué)生科學(xué)精神，掌握科學(xué)方法，理解科學(xué)與社會、文化等的關(guān)系。更重要的是使教學(xué)與科學(xué)、技術(shù)、社會實際問題有機結(jié)合起來，突出化學(xué)和醫(yī)學(xué)的社會價值，培養(yǎng)學(xué)生用整體、綜合觀點解決實際問題能力和創(chuàng)新能力。

圖3 MapReduce數(shù)據(jù)變化的基本模型

MapReduce通過把輸入數(shù)據(jù)自動分割成若干塊分布到多臺機器上，使輸入的塊能夠在不同的機器上被并行處理。圖4顯示了一次MapReduce執(zhí)行的具體流程。

MapReduce集群中有一個稱為master的機器用于管理其他機器和調(diào)度作業(yè)(Map作業(yè)或者Reduce作業(yè))，其他機器被稱為worker。被分配了Map作業(yè)的worker，開始讀取對應(yīng)分片的輸入數(shù)據(jù)，Map作業(yè)從輸入數(shù)據(jù)中抽取出鍵值對，每一個鍵值對都作為參數(shù)傳遞給map函數(shù)，map函數(shù)產(chǎn)生的中間鍵值對被緩存在內(nèi)存中。緩存的中間鍵值對會被定期寫入本地磁盤，而且被分為R個區(qū)，R的大小是由用戶定義的，將來每個區(qū)會對應(yīng)一個Reduce作業(yè);這些中間鍵值對的位置會被通報給master，master負責將信息轉(zhuǎn)發(fā)給Reduce worker。master通知分配了Reduce作業(yè)的worker它負責的分區(qū)在什么位置，當Reduce worker把所有它負責的中間鍵值對都讀過來后，先對它們進行排序，使得相同鍵的鍵值對聚集在一起。因為不同的鍵可能會映射到同一個分區(qū)也就是同一個Reduce作業(yè)，所以排序是必須的。Reduce worker遍歷排序后的中間鍵值對，對于每個唯一的鍵，都將鍵與關(guān)聯(lián)的值傳遞給reduce函數(shù)，reduce函數(shù)產(chǎn)生的輸出會添加到這個分區(qū)的輸出文件中。

圖4 MapReduce執(zhí)行流程

3 基于MapReduce的協(xié)同聚類算法

文獻［5］提出了一種適合協(xié)同聚類的并行框架DisCo，可用于大規(guī)模數(shù)據(jù)的聚類分析，并給出了基于MapReduce的協(xié)同聚類算法框架。本文在該框架的基礎(chǔ)上提出針對最小化殘差平方和的協(xié)同聚類算法的改進并行算法，在本文中用MR_co-clustering表示。

本文在MapReduce框架的開源項目Hadoop上完成對協(xié)同聚類算法的實現(xiàn)?？v觀整個協(xié)同聚類算法，運算時間主要集中在計算協(xié)同簇中心矩陣和對文檔、特征聚類的過程中。而之前已經(jīng)有人研究過對矩陣的并行處理以及k均值的并行實現(xiàn)，本文參考前人的經(jīng)驗，針對算法中計算耗時的部分進行并行化處理，使算法運行的時間大大縮短，提高算法的效率。

在算法中設(shè)計3個MapReduce過程。第一個MapReduce過程用于計算協(xié)同簇中心矩陣(U)，用UMapReduce表示。第二個MapReduce過程是實現(xiàn)對特征的聚類，用ColumnMapReduce表示。第三個MapReduce是實現(xiàn)對文檔的聚類，用RowMapReduce表示。下面對各個MapReduce過程進行描述。

(1)UMapReduce:計算協(xié)同簇中心矩陣U。由于矩陣U的計算只與屬于該行簇和列簇的元組相關(guān)，具有相對獨立性，可以用MapReduce實現(xiàn)。針對已知的Row和Column，把文檔-特征矩陣A按行劃分，并行地分析每個元組行和列所屬的簇，然后將屬于同一行簇和列簇的元組進行求和，計算出U，這樣就得到了協(xié)同簇中心矩陣。算法偽代碼如圖5所示。

圖5 UMapReduce算法

(2)ColumnMapReduce:對特征進行聚類，將特征分配到距離該簇中心距離最小的簇中。由于每一個特征的聚類都是相對獨立的，因此可以用MapReduce實現(xiàn)，即將特征列分發(fā)到集群的各臺機器中，同時對機器中的特征聚類，輸出特征聚類結(jié)果。偽代碼如圖6所示。

圖6 ColumnMapReduce算法

(3)RowMapReduce:與Mapreduce2類似，對文檔進行聚類，將文檔分配到距離簇中心距離最小的簇中。將文檔行分發(fā)到集群的各臺機器中，并行地進行文檔聚類，輸出文檔聚類的結(jié)果。偽代碼如圖7所示。

圖7 RowMapReduce算法

圖8描述了一次迭代的協(xié)同聚類算法的具體流程。首先將文檔集和初始化的Row和Column輸入UMapReducer中，計算出新的協(xié)同聚類簇中心，然后計算RU(特征的簇中心);進入第二個并行過程，對特征的聚類ColumnMapReduce，輸出對特征聚類的結(jié)果Column，由于特征的聚類結(jié)果變化導(dǎo)致協(xié)同聚類簇中心的結(jié)果也發(fā)生變化，所以對文檔-特征矩陣再進行UMapReduce過程，計算更新后的U，然后對文檔進行聚類，執(zhí)行RowMapReducer過程，輸出文檔聚類的結(jié)果，最后計算‖A-RUC‖，通過判斷與迭代前的結(jié)果是否相等判斷迭代是否還要再繼續(xù)下去。

由于串行協(xié)同聚類算法的時間復(fù)雜度為O(T×m×n)，而并行的協(xié)同聚類算法與機器數(shù)N相關(guān)，它的時間復(fù)雜度由機器數(shù)的增加而減少，所以并行協(xié)同聚類算法的時間復(fù)雜度為O(T×m×n/N)

4 實驗與結(jié)果分析

4.1 實驗環(huán)境和數(shù)據(jù)集

Hadoop是MapReduce框架的開源實現(xiàn)，協(xié)同聚類算法的實驗就是基于此框架實現(xiàn)的。

Hadoop集群中各節(jié)點采用相同的配置，即:Hadoop 版本為 Hadoop 0.20.203.0，操作系統(tǒng)為 ubuntu10.10，JDK 版本為 1.6.0;PC 機的硬件環(huán)境同為Pentium(R)Dual-core CPU E6300@2.8 GHz雙核處理器，ADAT 2G內(nèi)存，Hitachi 320 GB硬盤。

本實驗采用的數(shù)據(jù)集是復(fù)旦中文文檔集，總共有8214篇文檔。預(yù)處理階段將每篇文檔進行分詞，采用χ2算法選擇維數(shù)，抽取了500維的特征，采用tf-idf的方法進行特征抽取。實驗時采用隨機初始化的原則對Row和Column進行初始化。矩陣文檔36M，為了使實驗結(jié)果更符合預(yù)期，將Hadoop的配置文件中的分塊設(shè)置改為6M，默認情況下是64M。

4.2 實驗結(jié)果

首先通過對協(xié)同聚類算法和常用聚類算法K-means的比較來說明協(xié)同聚類算法的優(yōu)越性。表2顯示的是K-means算法，串行協(xié)同聚類算法S_co_clustering以及本文提出的并行協(xié)同聚類算法MR_co_clustering在純度、熵和互信息上的結(jié)果，結(jié)果表明協(xié)同聚類算法能夠有效提高聚類的效果，對協(xié)同聚類算法的并行化不影響聚類的效果。

表2 K-means與串行協(xié)同聚類算法和并行協(xié)同聚類算法的結(jié)果比較

為了說明本文算法的可擴展性，對算法的執(zhí)行時間與集群中的機器數(shù)的關(guān)系進行了比較。

表3顯示的是一次迭代過程中，各MapReduce過程和對應(yīng)的串行算法的耗時。圖9是對應(yīng)的折線圖。表3和圖9顯示并行算法的運行時間隨著機器數(shù)的增加而降低。

表3 一次迭代過程中3個MapReduce過程以及對應(yīng)串行算法的執(zhí)行時間(S_computU、S_Column、S_Row分別是計算U、對列聚類和對行聚類的串行方法)

圖9 各并行階段及對應(yīng)串行算法執(zhí)行時間折線圖

表4顯示的是并行算法和串行算法在一次迭代過程中的運行時間，包括表3中的并行過程所耗費的時間以及一些額外開銷所耗費的時間。

表4 MR_co-clustering與S_co-clutering的執(zhí)行時間比較(單位s)

圖10 一次迭代執(zhí)行時間折線圖

由圖9和圖10可知，串行協(xié)同聚類算法運行時間幾乎不受集群機器個數(shù)的影響，因為串行算法的效率只與運行該算法的機器有關(guān)，而與集群中其他機器無關(guān);并行協(xié)同聚類算法的運行時間則與集群中機器的個數(shù)密切相關(guān)。當只有一臺機器時，基于MapReduce的并行協(xié)同聚類算法比串行算法運行得更慢，這是由于集群需要耗費一定的通訊開銷。但是當集群中機器數(shù)量增加時，執(zhí)行時間迅速下降，當集群機器數(shù)達到6至8臺時基本趨于穩(wěn)定，這是由于在本文的數(shù)據(jù)集是分為6(36/6)塊被分布到集群上的不同機器上的，也即MapReduce需要處理的任務(wù)有6個，所以當機器數(shù)目已經(jīng)滿足MapReduce分配的6個之后，增加機器不再對執(zhí)行時間產(chǎn)生顯著影響。

圖11 一次迭代加速比曲線圖

圖11描述了MR_co-clustering算法的加速比曲線，其中各MapReduce子階段的加速比曲線與MR_co-clustering類似。由于機器數(shù)達到6臺后執(zhí)行時間受影響的因素已經(jīng)不是機器的個數(shù)，因此，加速比曲線圖里不考慮機器數(shù)大于6臺以后的現(xiàn)象。從圖11中可以看出，隨著機器數(shù)量的增長MR_co-clustering算法的加速比是趨于線性加速比的，這說明本文的算法具有很好的可擴展性。

由于在運行MapReduce過程中會產(chǎn)生大量中間數(shù)據(jù)，而這些中間數(shù)據(jù)直接影響算法的運行時間，為此，對中間數(shù)據(jù)的優(yōu)化也是一種算法的改進措施。與DisCo算法相比，本文提出的算法在并行運算中產(chǎn)生的中間數(shù)據(jù)遠遠小于DisCo算法，有效減少了中間數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸時間，提高了算法的效率。

由實驗結(jié)果可知，通過對文檔和特征同時聚類的協(xié)同聚類算法可以有效地改善聚類的結(jié)果，而本文提出的并行協(xié)同聚類算法在提高算法效果的同時，還提高了算法的效率，達到了可擴展的并行要求。

5 結(jié)束語

本文的研究表明，對協(xié)同聚類的算法進行并行化后可以顯著縮短算法的執(zhí)行時間，提高聚類效率，同時，通過它的加速比可以看出該算法具有很好的可擴展性。本文提出的基于MapReduce的協(xié)同聚類算法對高維數(shù)據(jù)和大規(guī)模數(shù)據(jù)的處理具有一定意義。然而本研究還有很多值得進一步研究的地方，例如，如何初始化Row和Column使迭代更快更穩(wěn)定地收斂到最合適的狀態(tài)，以及k和l的值的確定。

［1］Jimmy Lin，Chris Dyer.Data-Intensive Text Processing with MapReduce［M］.Morgan ＆ Claypool Publishers，2010.

［2］王明文，付劍波，羅遠勝，等.基于協(xié)同聚類的兩階段文本聚類方法［J］.模式識別與人工智能，2009，22(6):848-853.

［3］Cho H，Dhillon I，Guan Y，et al.Minimum sum-squared residue co-clustering of gene expression data［C］//Proceedings of the 4th SIAM International Conference on Data Mining.2004:509-514.

［4］Aris Anagnostopoulos，Anirban Dasgupta，Ravi Kumar.Approximation algorithms for co-clustering［C］//Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.2008:201-210.

［5］Spiros Papadimitriou，Jimeng Sun.DisCo:Distributed coclustering with Map-Reduce:A case study towards Petabyte-scale end-to-end mining［C］//Proceedings of the 8th IEEE International Conference on Data Mining(ICDM’08).2008:512-521.

［6］王明文，陶紅亮，熊小勇.雙向聚類迭代的協(xié)同過濾推薦算法［J］.中文信息學(xué)報，2008，22(4):61-65.

［7］Chuck Lam.Hadoop in Action［M］.Manning Publication，2010.

［8］George T，Merugu S.A scalable collaborative filtering framework based on co-clustering［C］//Proceedings of the 5th IEEE International Conference on Data Mining.2005:625-628.

［9］Hartigan J A.Direct clustering of a data matrix［J］.Journal of the American Statistical Association，1972，337(67):123-129.

［10］Madeira S C，Oliveira A L.Biclustering algorithms for biological data analysis:A survey［C］//IEEE/ACM Transactions on Computational Biology and Bioinformatics.2004:24-45.

［11］Banerjee A，Dhillon I，Ghosh J，et al.A generalized maximum entropy approach to Bregman co-clustering and matrix approximation［J］.Journal of Machine Learning Research，2007(8):1919-1986.

［12］Hadoop.The Apache Software Foundation［EB/OL］.http://hadoop.apache.org，2013-06-05.