[發明專利]一種基于MapReduce的大規模數據分布式聚類處理方法

有效

• 申請號: 201710412014.8
• 申請日: 2017-06-02
• 公開（公告）號: CN107291847B
• 公開（公告）日: 2019-06-25
• 發明（設計）人: 高天寒;孔雪
• 申請（專利權）人: 東北大學
• 主分類號: G06F16/26
• 分類號: G06F16/26
• 代理公司: 沈陽東大知識產權代理有限公司 21109
• 代理人: 胡曉男

本發明提供一種基于MapReduce的大規模數據分布式聚類處理方法，包括對大規模數據以等規模不重復的原則進行抽樣；向MapReduce分布式并行框架輸入抽樣數據并計算抽樣數據的局部密度和平均密度；找出局部密度大于平均密度的所有抽樣數據作為每個簇的初始聚類中心點的候選點集合并反饋給主節點，選取每兩個相鄰候選點之間距離大于2倍設定范圍的所有候選點作為初始聚類中心點；利用MapReduce分布式并行框架進行并行聚類任務，針對每個簇計算數據間距離的平均值來更新聚類中心點；子節點應用誤差平方和準則函數判斷是否繼續迭代；各子節點根據聚類中心點對大規模數據進行聚類。本發明實現并行聚類，減少聚類迭代次數，提高聚類準確率和并行聚類效率。

技術領域

本發明屬于并行聚類技術領域，特別是一種基于MapReduce的大規模數據分布式聚類處理方法。

背景技術

伴隨信息技術的快速發展，數據規模不斷增大，利用并行機制對大規模數據集進行有效地挖掘分析，可以推動互聯網技術的發展和進步。聚類分析是一種重要的數據處理技術，是機器學習和人工智能領域的重要課題之一，被廣泛用于數據挖掘、信息檢索等研究中。主要工作是將數據集劃分成多個子集，使得子集內的數據對象間的相似度較高，不同子集間的數據對象間的差異度較大。由于數據規模的增大，傳統的單機聚類方法已經無法在有效地時間內處理大規模數據且效率低下，聚類效果不理想，而隨之而來的大數據技術愈加成熟，越來越多的人開始關注學習Hadoop MapReduce相關技術。因此，建立一個并行集群模式利用MapReduce并行框架是解決這些問題的一個重要研究方向。

MapReduce是一個應用于大規模數據集的并行編程模型，特點是簡單，容易實現和易于擴展。核心思想就是“分而治之”，把大規模數據集分成一個個小的數據集，交由主節點管理下的各分節點共同處理，然后把各分節點的中間結果進行整合，得到最終結果。近年來，學者們針對大規模數據聚類展開了一系列的研究，其中K-Means方法是基于劃分的經典聚類分析方法之一，優點是具有操作簡單，收斂速度較快，缺點是對于初始聚類中心的選取采用隨機方式，易導致聚類局部最優，影響最后的聚類效果。因此保證初始聚類中心的準確性是面向大規模數據并行聚類的重要環節。

目前的研究熱點是并行聚類方法的初始聚類中心點選擇方法，主要分為K-Means結合Canopy方法確定聚類中心和基于數據密度計算確定初始聚類中心兩種方法。K-Means方法結合Canopy方法Canopy-Kmeans，利用Canopy的特點計算對象的相似性，將數據做預處理，優勢在于可以給定初始聚類中心點，避免陷入局部最優，但是缺點是計算對象間的相似性的時間耗費較大。基于數據密度計算的方法是計算出所有數據的密度，然后選擇密度最大的數據作為聚類中心點從而避免了隨機選取的問題，且較為準確，但是傳統的計算開銷也較大，且易導致節點負載較大，降低并行聚類總體效率。

發明內容

針對現有技術中存在的問題，本發明提供一種基于MapReduce的大規模數據分布式聚類處理方法。

本發明的技術方案如下：

一種基于MapReduce的大規模數據分布式聚類處理方法，包括：

步驟1、對大規模數據以等規模不重復的原則進行抽樣，記錄抽樣數據；

步驟2、啟動Hadoop分布式集群環境，向MapReduce分布式并行框架輸入抽樣數據并計算抽樣數據的局部密度和平均密度；

步驟3、主節點以抽樣數據的平均密度Avg為基準下發任務到子節點，各個子節點根據局部密度進行排序，找出局部密度大于平均密度Avg的所有抽樣數據作為每個簇的初始聚類中心點的候選點集合并反饋給主節點，主節點選取候選點集合中每兩個相鄰候選點之間距離大于2倍設定范圍的所有候選點作為初始聚類中心點；