[發(fā)明專利]一種基于MapReduce的并行聚類方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210434240.3
• 申請(qǐng)日: 2012-11-05
• 公開（公告）號(hào): CN103793438B
• 公開（公告）日: 2017-07-14
• 發(fā)明（設(shè)計(jì)）人: 孫占全
• 申請(qǐng)（專利權(quán)）人: 山東省計(jì)算中心（國(guó)家超級(jí)計(jì)算濟(jì)南中心）
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)挖掘領(lǐng)域，特別涉及大規(guī)模數(shù)據(jù)聚類分析。

背景技術(shù)

隨著電子信息技術(shù)的飛速發(fā)展，電子數(shù)據(jù)量以指數(shù)級(jí)增長(zhǎng)，數(shù)據(jù)洪流在很多領(lǐng)域開始出現(xiàn)，如生物信息、生物醫(yī)學(xué)、化學(xué)信息、網(wǎng)頁(yè)等等。如何充分利用海量數(shù)據(jù)挖掘有用信息，從而輔助企業(yè)決策是信息領(lǐng)域?qū)＜宜媾R的巨大挑戰(zhàn)。如果能夠充分挖掘電子信息，將為企業(yè)帶來(lái)巨大效益，如果不能從海量數(shù)據(jù)中挖掘有用信息，將成為電子垃圾，成為企業(yè)負(fù)擔(dān)。數(shù)據(jù)挖掘是從大量數(shù)據(jù)集中發(fā)現(xiàn)新模式的過(guò)程，結(jié)合了人工智能、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)和數(shù)據(jù)庫(kù)，是目前分析數(shù)據(jù)的最有效手段。國(guó)內(nèi)外很多學(xué)者從事這方面的研究，很多數(shù)據(jù)挖掘方法已被應(yīng)用到實(shí)際當(dāng)中。隨著數(shù)據(jù)規(guī)模的擴(kuò)大，很多傳統(tǒng)的數(shù)據(jù)挖掘方法已不實(shí)用，針對(duì)大規(guī)模數(shù)據(jù)密集型的并行數(shù)據(jù)挖掘方法研究是近年來(lái)信息領(lǐng)域的研究重點(diǎn)。有效的并行算法和實(shí)現(xiàn)技術(shù)是實(shí)現(xiàn)大規(guī)模數(shù)據(jù)挖掘的關(guān)鍵。很多并行挖掘算法以不同技術(shù)實(shí)現(xiàn)，如多線程、MPI技術(shù)、MapReduce技術(shù)、工作流技術(shù)等，不同的實(shí)現(xiàn)技術(shù)有不同的性能和使用特性，MPI模式適用于計(jì)算密集型問(wèn)題，特別適用于仿真，但編程復(fù)雜度較高，對(duì)運(yùn)行環(huán)境的時(shí)延要求高，容錯(cuò)性較差。MapReduce是信息檢索領(lǐng)域提出的一種適于數(shù)據(jù)分析的云技術(shù)，適合于數(shù)據(jù)密集型的并行數(shù)據(jù)挖掘。目前有幾種MapReduce的結(jié)構(gòu)，傳統(tǒng)的MapReduce架構(gòu)只是單向的Map和Reduce過(guò)程，不支持迭代，不適合復(fù)雜的數(shù)據(jù)挖掘算法。最新由美國(guó)印第安那大學(xué)教授提出的Twister軟件，是一種迭代MapReduce模型，支持算法的迭代，大大提供了MapReduce算法的實(shí)用性。

數(shù)據(jù)聚類是是對(duì)于靜態(tài)數(shù)據(jù)分析的一門技術(shù)，在許多領(lǐng)域受到廣泛應(yīng)用，包括機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識(shí)別、圖像分析以及生物信息等。聚類的目的是把相似的對(duì)象通過(guò)靜態(tài)分類的方法分成不同的組別或者更多的子集，這樣讓在同一個(gè)子集中的成員對(duì)象都有相似的一些屬性，是一種無(wú)監(jiān)督方法。很多聚類方法已被研究，如k均值聚類、Fisher聚類、Kohonen聚類、基于信息瓶頸理論聚類方法等，不同聚類方法具有不同的聚類性質(zhì)，適用于不同的聚類問(wèn)題。K均值聚類應(yīng)用最廣，但聚類的距離測(cè)度只能度量變量之間的線性相關(guān)性。Kohonen聚類是一種自適應(yīng)神經(jīng)網(wǎng)絡(luò)，但聚類測(cè)度通常也是歐幾里德距離，無(wú)法度量變量之間的任意相關(guān)性。基于信息瓶頸理論的聚類是基于信息熵理論的聚類方法，以信息損失量為測(cè)度度量變量之間的相關(guān)性，可以統(tǒng)計(jì)變量之間任意統(tǒng)計(jì)相關(guān)性，已被用于多個(gè)領(lǐng)域的聚類問(wèn)題，取得理想的效果。但隨著數(shù)據(jù)規(guī)模的擴(kuò)大，基于信息瓶頸理論聚類方法的計(jì)算量越來(lái)越大，已不適于大規(guī)模的數(shù)據(jù)分析問(wèn)題。基于信息瓶頸理論聚類方法的優(yōu)點(diǎn)，本專利提出了基于MapReduce編程模式的并行聚類方法，有效解決了大規(guī)模聚類分析問(wèn)題。

基于MapReduce的并行聚類方法可用于生物信息的DNA數(shù)據(jù)聚類，生物信息數(shù)據(jù)量非常龐大，每天都會(huì)產(chǎn)生大量的DNA數(shù)據(jù)，DNA序列聚類是生物信息的重要內(nèi)容之一，如何對(duì)大規(guī)模的DNA序列進(jìn)有效聚類是研究熱點(diǎn)。DNA數(shù)據(jù)通常用A、C、G、T字符串組成，為實(shí)現(xiàn)DNA數(shù)據(jù)進(jìn)行序列對(duì)比，通常需要對(duì)DNA字符對(duì)進(jìn)行統(tǒng)計(jì)，將DNA序列轉(zhuǎn)化成概率向量，通過(guò)計(jì)算兩個(gè)概率向量的距離來(lái)度量DNA序列直接的相關(guān)性，從而利用本發(fā)明專利實(shí)現(xiàn)DNA序列的有效聚類。

基于MapReduce聚類方法與其它聚類方法相比主要有以下優(yōu)點(diǎn)：

1)用信息損失量作為度量?jī)蓚€(gè)變量之間的距離測(cè)度，可以度量變量之間任意統(tǒng)計(jì)相關(guān)性；

2)本發(fā)明可用客觀的方法確定聚類數(shù)，有效避免現(xiàn)有聚類方法人為主觀指定聚類數(shù)的缺點(diǎn)；

3)本發(fā)明專利提出的基于MapReduce并行聚類方法適于大規(guī)模數(shù)據(jù)聚類，有效提高聚類效率和性能。

發(fā)明內(nèi)容

本發(fā)明的目的之一在于提出一種基于MapReduce的并行聚類方法，該方法以信息損失作為樣本之間距離的測(cè)度，以MapReduce編程模式實(shí)現(xiàn)聚類中心的并行計(jì)算，為聚類數(shù)確定提供了客觀標(biāo)準(zhǔn)，避免主觀指定聚類數(shù)的弊端。

為達(dá)到上述目的，本發(fā)明采用的技術(shù)方案為：

該基于MapReduce的并行聚類方法，包括步驟：

將原數(shù)據(jù)集進(jìn)行轉(zhuǎn)換，以概率的形式進(jìn)行描述；

對(duì)原數(shù)據(jù)進(jìn)行劃分，設(shè)定聚類參數(shù)；

以基于MapReduce的并行信息瓶頸理論聚類方法確定聚類數(shù)和初始聚類中心；

以基于MapReduce的并行中心聚類方法實(shí)現(xiàn)最終聚類結(jié)果。

附圖說(shuō)明

圖1基于迭代MapReduce編程模式的Twister軟件架構(gòu)