亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于MapReduce的可擴(kuò)展協(xié)同聚類(lèi)算法

        2013-10-15 07:38:22萬(wàn)劍怡王明文
        計(jì)算機(jī)與現(xiàn)代化 2013年11期
        關(guān)鍵詞:鍵值結(jié)點(diǎn)文檔

        馬 俏,萬(wàn)劍怡,王明文

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

        0 引言

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

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

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

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

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

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

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

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

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

        表1 常用符號(hào)表示

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

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

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

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

        2 MapReduce分布式編程模式

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

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

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

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

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

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

        圖4 MapReduce執(zhí)行流程

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

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

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

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

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

        圖5 UMapReduce算法

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

        圖6 ColumnMapReduce算法

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

        圖7 RowMapReduce算法

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

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

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

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

        Hadoop是MapReduce框架的開(kāi)源實(shí)現(xiàn),協(xié)同聚類(lèi)算法的實(shí)驗(yàn)就是基于此框架實(shí)現(xiàn)的。

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

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

        4.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

        表4顯示的是并行算法和串行算法在一次迭代過(guò)程中的運(yùn)行時(shí)間,包括表3中的并行過(guò)程所耗費(fèi)的時(shí)間以及一些額外開(kāi)銷(xiāo)所耗費(fèi)的時(shí)間。

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

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

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

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

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

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

        由實(shí)驗(yàn)結(jié)果可知,通過(guò)對(duì)文檔和特征同時(shí)聚類(lèi)的協(xié)同聚類(lèi)算法可以有效地改善聚類(lèi)的結(jié)果,而本文提出的并行協(xié)同聚類(lèi)算法在提高算法效果的同時(shí),還提高了算法的效率,達(dá)到了可擴(kuò)展的并行要求。

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

        本文的研究表明,對(duì)協(xié)同聚類(lèi)的算法進(jìn)行并行化后可以顯著縮短算法的執(zhí)行時(shí)間,提高聚類(lèi)效率,同時(shí),通過(guò)它的加速比可以看出該算法具有很好的可擴(kuò)展性。本文提出的基于MapReduce的協(xié)同聚類(lèi)算法對(duì)高維數(shù)據(jù)和大規(guī)模數(shù)據(jù)的處理具有一定意義。然而本研究還有很多值得進(jìn)一步研究的地方,例如,如何初始化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]王明文,付劍波,羅遠(yuǎn)勝,等.基于協(xié)同聚類(lèi)的兩階段文本聚類(lèi)方法[J].模式識(shí)別與人工智能,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]王明文,陶紅亮,熊小勇.雙向聚類(lèi)迭代的協(xié)同過(guò)濾推薦算法[J].中文信息學(xué)報(bào),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.

        猜你喜歡
        鍵值結(jié)點(diǎn)文檔
        有人一聲不吭向你扔了個(gè)文檔
        非請(qǐng)勿進(jìn) 為注冊(cè)表的重要鍵值上把“鎖”
        Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點(diǎn)個(gè)數(shù)估計(jì)
        一鍵直達(dá) Windows 10注冊(cè)表編輯高招
        基于RI碼計(jì)算的Word復(fù)制文檔鑒別
        Persistence of the reproductive toxicity of chlorpiryphos-ethyl in male Wistar rat
        基于Raspberry PI為結(jié)點(diǎn)的天氣云測(cè)量網(wǎng)絡(luò)實(shí)現(xiàn)
        不讓他人隨意下載Google文檔
        電腦迷(2012年4期)2012-04-29 06:12:13
        基于DHT全分布式P2P-SIP網(wǎng)絡(luò)電話穩(wěn)定性研究與設(shè)計(jì)
        注冊(cè)表值被刪除導(dǎo)致文件夾選項(xiàng)成空白
        国产免费人成视频网站在线18| 日韩爱爱视频| 国产优质女主播在线观看| 国产精品又湿又黄九九九久久嫩草 | 人妻无码久久一区二区三区免费| 一区二区免费电影| 亚洲av色精品国产一区二区三区| 成人欧美一区二区三区黑人| 亚洲人成电影在线观看天堂色| 91精品国产91久久久无码95| 在线精品亚洲一区二区三区| 看日本全黄色免费a级| 男女车车的车车网站w98免费| 婷婷亚洲国产成人精品性色| 国产亚洲精品一区二区在线播放| 日韩午夜理论免费tv影院| 饥渴的熟妇张开腿呻吟视频| 精品久久久久久蜜臂a∨| 99亚洲女人私处高清视频| 国产色视频一区二区三区qq号| 欧美日韩视频无码一区二区三| 亚洲精品www久久久久久 | 国产人妻熟女高跟丝袜图片| 国产欧美日韩视频一区二区三区 | 精品无码一区二区三区亚洲桃色 | 24小时免费在线观看av| 超清精品丝袜国产自在线拍| 人妻少妇不满足中文字幕| 成人性生交大片免费看i| 99国产精品99久久久久久| 女人做爰高潮呻吟17分钟| 69搡老女人老妇女老熟妇| 国产毛片av一区二区| 国产亚洲精品aaaa片小说| 久久精品国产亚洲av大全相关| 久久99人妖视频国产| 国产永久免费高清在线| 欧美日本国产三级在线| 亚洲精品在线一区二区三区| 欧洲熟妇色xxxx欧美老妇软件| 精品一区二区三区无码视频|