一種基於MapReduce的並行聚類方法
2023-10-25 07:22:02 1
一種基於MapReduce的並行聚類方法
【專利摘要】本發明基於MapReduce的並行聚類方法，主要是針對大規模數據集的聚類問題，該方法以信息損失量度量樣本之間的相關性，可以體現樣本之間複雜的相關性，並且提供了一個客觀的聚類數確定準則，通過數據並行，大大提高了聚類速度。該聚類方法可以廣泛應用於醫學、藥學、智能交通、模式識別等領域的聚類問題。
【專利說明】—種基於MapReduce的並行聚類方法
【技術領域】
[0001]本發明涉及數據挖掘領域，特別涉及大規模數據聚類分析。
【背景技術】
[0002]隨著電子信息技術的飛速發展，電子數據量以指數級增長，數據洪流在很多領域開始出現，如生物信息、生物醫學、化學信息、網頁等等。如何充分利用海量數據挖掘有用信息，從而輔助企業決策是信息領域專家所面臨的巨大挑戰。如果能夠充分挖掘電子信息，將為企業帶來巨大效益，如果不能從海量數據中挖掘有用信息，將成為電子垃圾，成為企業負擔。數據挖掘是從大量數據集中發現新模式的過程，結合了人工智慧、機器學習、統計和資料庫，是目前分析數據的最有效手段。國內外很多學者從事這方面的研究，很多數據挖掘方法已被應用到實際當中。隨著數據規模的擴大，很多傳統的數據挖掘方法已不實用，針對大規模數據密集型的並行數據挖掘方法研究是近年來信息領域的研究重點。有效的並行算法和實現技術是實現大規模數據挖掘的關鍵。很多並行挖掘算法以不同技術實現，如多線程、MPI技術、MapReduce技術、工作流技術等，不同的實現技術有不同的性能和使用特性，MPI模式適用於計算密集型問題，特別適用於仿真，但編程複雜度較高，對運行環境的時延要求高，容錯性較差。MapReduce是信息檢索領域提出的一種適於數據分析的雲技術，適合於數據密集型的並行數據挖掘。目前有幾種MapReduce的結構,傳統的MapReduce架構只是單向的Map和Reduce過程，不支持迭代，不適合複雜的數據挖掘算法。最新由美國印第安那大學教授提出的Twister軟體,是一種迭代MapReduce模型,支持算法的迭代,大大提供了MapReduce算法的實用性。
[0003]數據聚類是是對於靜態數據分析的一門技術，在許多領域受到廣泛應用，包括機器學習、數據挖掘、模式識別、圖像分析以及生物信息等。聚類的目的是把相似的對象通過靜態分類的方法分成不同的組別或者更多的子集，這樣讓在同一個子集中的成員對象都有相似的一些屬性，是一種無監督方法。很多聚類方法已被研究，如k均值聚類、Fisher聚類、Kohonen聚類、基於信息瓶頸理論聚類方法等，不同聚類方法具有不同的聚類性質，適用於不同的聚類問題。K均值聚類應用最廣，但聚類的距離測度只能度量變量之間的線性相關性。Kohonen聚類是一種自適應神經網絡，但聚類測度通常也是歐幾裡德距離，無法度量變量之間的任意相關性。基於信息瓶頸理論的聚類是基於信息熵理論的聚類方法，以信息損失量為測度度量變量之間的相關性，可以統計變量之間任意統計相關性，已被用於多個領域的聚類問題，取得理想的效果。但隨著數據規模的擴大，基於信息瓶頸理論聚類方法的計算量越來越大，已不適於大規模的數據分析問題。基於信息瓶頸理論聚類方法的優點，本專利提出了基於MapReduce編程模式的並行聚類方法，有效解決了大規模聚類分析問題。
[0004]基於MapReduce的並行聚類方法可用於生物信息的DNA數據聚類，生物信息數據量非常龐大，每天都會產生大量的DNA數據，DNA序列聚類是生物信息的重要內容之一，如何對大規模的DNA序列進有效聚類是研究熱點。DNA數據通常用A、C、G、T字符串組成，為實現DNA數據進行序列對比，通常需要對DNA字符對進行統計，將DNA序列轉化成概率向量，通過計算兩個概率向量的距離來度量DNA序列直接的相關性，從而利用本發明專利實現DNA序列的有效聚類。
[0005]基於MapReduce聚類方法與其它聚類方法相比主要有以下優點:
[0006]I)用信息損失量作為度量兩個變量之間的距離測度，可以度量變量之間任意統計相關性；
[0007]2)本發明可用客觀的方法確定聚類數，有效避免現有聚類方法人為主觀指定聚類數的缺點；
[0008]3)本發明專利提出的基於MapReduce並行聚類方法適於大規模數據聚類，有效提高聚類效率和性能。
【發明內容】
[0009]本發明的目的之一在於提出一種基於MapReduce的並行聚類方法,該方法以信息損失作為樣本之間距離的測度，以MapReduce編程模式實現聚類中心的並行計算，為聚類數確定提供了客觀標準，避免主觀指定聚類數的弊端。
[0010]為達到上述目的，本發明採用的技術方案為:
[0011]該基於MapReduce的並行聚類方法,包括步驟:
[0012]將原數據集進行轉換，以概率的形式進行描述；
[0013]對原數據進行劃分，設定聚類參數；
[0014]以基於MapReduce的並行信息瓶頸理論聚類方法確定聚類數和初始聚類中心；
`[0015]以基於MapReduce的並行中心聚類方法實現最終聚類結果。
【專利附圖】
【附圖說明】
[0016]圖1基於迭代MapReduce編程模式的Twister軟體架構
[0017]圖2基於MapReduce的並行信息瓶頸理論聚類方法流程圖
[0018]圖3基於MapRedcue的並行中心聚類方法流程圖
[0019]圖4基於信息損失量變化確定聚類數
[0020]圖5由本發明實施DNA序列聚類結果
【具體實施方式】
[0021]為更好地理解本發明，下面結合附圖和【具體實施方式】對本發明作詳細說明。
[0022]聚類是通過分析變量之間的相關性將數據集合劃分若干類的過程，使得類內差異小，類間差異大。對於大規模數據的聚類分析，需要通過並行的方式實現。在數據劃分的並行聚類中，如何實現全局的聚類中心是關鍵。另外，如何確定聚類數需要一個客觀的標準。本發明提出一種基於MapReduce編程模式的並行聚類方法，該方法的具體操作如下。
[0023]數據轉換、劃分及參數設定
[0024]對原始文件進行分析，將原始數據轉換成用概率向量表示的形式。然後隨機的將原始數據均勻劃分成η份，將η份數據分布到m個map節點，設定聚類截尾精度閾值a ^
和Stl，其中Citl是聚類步驟與該組數據中所有數據數比值的閾值；Pci是信息損失量實際損失值與預測值差值的閾值；S ^是在並行中心聚類過程中，當前的聚類中心與上次聚類中心差值的閾值。
[0025]基於MapReduce的並行信息瓶頸理論聚類
[0026]1)基於迭代MapReduce的Twister軟體架構
[0027]本發明是基於迭代MapReuce編程模式，以Twister軟體為例，介紹基於迭代MapReduce編程模式軟體的架構。
[0028]迭代MapReduce軟體包括以下幾部分，主作業、Map作業、Reduce作業和Combine作業，架構附圖1如下所示。
[0029]其中，MapReduce作業通過客戶節點控制,在配置階段,客戶端分布各MapReduce方法給各個任務，準備KeyPair對和靜態數據給MapReduce任務,在每次迭代過程中，客戶端接收到Combine方法返回的結果，直到任務結束。
[0030]Map作業主要實現計算模型，在初始化階段，Map作業根據劃分文件從本地磁碟加載靜態數據，利用用戶定義的計算模型對劃分數據進行分析，結果傳遞給Reduce作業。Reduce作業主要接受從Map作業傳遞過來的結果，具體工作根據實際任務進行分析。
[0031]Combine作業是將分析的結果收集起來，傳遞給客戶端。在客戶端程序，判斷是否達到截尾準則，如果達到程序結束退出，否則重複MapReduce過程。
[0032]2)基於信息瓶頸理論聚類方法
[0033]在給定一個目標集合，基於瓶頸原理的聚類方法是尋找在所有的聚類中使目標類與特徵之間的信息損失達到最小。設在目標空間X和特徵空間Y上的聯合概率分布為P(x，y)，信息瓶頸理論是找一個聚類f在給定聚類質量的約束條件下使信息損失/(z;r)-/(f;y)達到最小。是X和f之間的互信息
[0034]
【權利要求】
1.一種基於MapReduce編程模型的並行聚類方法，其特徵在於，包括步驟: 原始數據劃分及參數設定； 以基於MapReduce的並行信息瓶頸理論聚類方法確定聚類數和初始聚類中心； 以基於MapReduce的並行中心聚類方法實現最終聚類結果。
2.根據權利I所述的原始數據劃分及參數設定，其特徵在於， 對原始文件進行分析，將原始數據轉換成用概率向量表示的形式。然後隨機的將原始數據均勻劃分成1份，將1份數據分布到m個map節點，設定聚類截尾精度閾值a ^ β ^和S C1，其中是聚類步驟與該組數據中所有數據數比值的閾值；β ^是信息損失量實際損失值與預測值差值的閾值；S ^是在並行中心聚類過程中，當前的聚類中心與上次聚類中心差值的閾值。
3.根據權利I所基於MapReduce的並行信息瓶頸理論聚類方法確定聚類數和初始聚類中心，其特徵在於， 針對每個數據劃分，利用基於信息瓶頸理論聚類方法進行聚類； 合併各數據劃分的聚類中心，利用基於信息瓶頸理論聚類方法重新聚類，生成全局初始聚類中心。
4.根據權利3所述基於信息瓶頸理論聚類方法，其特徵在於， a.將每個向量數組看作最初的類； b.計算任意兩組向量合併產生的信息損失量，選擇合併後產生的信息損失量最小的一組進行合併，生產新的數組； C.重複步驟b直至滿足聚類截尾精度CItl和β C1，確定聚類數。
5.根據權利4中b所述，其特徵在於 根據信息瓶頸理論，兩組數組合併所產生的信息損失量為:
6.根據權利4中c所述，其特徵在於 對於第i個數據劃分，當聚類步數達到第k步k > ni α時,開始利用當前聚類步前k_l步產生的信息損失量進行最小二乘回歸，根據回歸方程，當前聚類步的預測值為六，則預測值與實際信息損失量為
7.根據權利3所述生成全局初始聚類中心，其特徵在於， 收集所有Map接點計算得到的數據子集的分聚類中心，生成新的聚類樣本,根據權利3所述基於信息瓶頸理論的聚類方法生成全局初始聚類中心並確定聚類數。
8.根據權利I所述基於MapReduce的並行中心聚類方法實現最終聚類結果，其特徵在於 a利用中心聚類方法確定每步聚類中心； b通過迭代的方式調整聚類中心，當滿足迭代閾值時，聚類結束。
9.根據權利8中a所述，其特徵在於 在獲取初始聚類中心C°後，將其分布到各個Map節點，設k個空數據集P1，P2，…，Pk,計算樣本X與初始聚類中心4之間的距離，用信息損失作為測度，當X與cf之間的信息損失最小時，將樣本X放入到數據集Pi中，根據下式計算數據集Pi的中心
10.根據權利8中b所述，其特徵在於 計算新聚類中心Χη?與上次聚類中心X°k的差值，如果差值小於預先指定的閾值，迭代過程結束，如果大於指定的閾值，繼續迭代過程。差值計算如下
【文檔編號】G06F17/30GK103793438SQ201210434240
【公開日】2014年5月14日 申請日期:2012年11月5日 優先權日:2012年11月5日
【發明者】孫佔全 申請人:山東省計算中心