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

有效

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

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

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

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

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

步驟4、主節點接收初始聚類中心點分布任務給子節點，子節點根據初始聚類中心點利用MapReduce分布式并行框架進行并行聚類任務，針對每個簇計算數據間距離的平均值來更新聚類中心點；

步驟5：子節點應用誤差平方和準則函數作為聚類準則函數，判斷是否繼續迭代：若根據更新后的聚類中心點計算的誤差平方和準則函數是收斂的，則當前的各聚類中心點為最終的聚類中心點并反饋給主節點，執行步驟6；否則返回步驟4繼續迭代更新聚類中心點；

步驟6：主節點重新輸入聚類中心點并分布任務，各子節點根據聚類中心點對大規模數據進行聚類。

2.根據權利要求1所述的方法，其特征在于，所述以等規模不重復的原則進行抽樣，采用的公式如下：

f_i≈f_j且Nf_i＜＜D

e＝f*n*δ

其中，D表示大規模數據集，D_i和D_j表示兩個沒有交集的數據集，n表示抽樣數據有n個屬性，i和j的范圍在1到N之間，數據集D_i和D_j的數據規模分別記為f_i和f_j，N表示抽樣次數，e表示抽樣的數據大小，f為抽樣的數據在大規模數據集中所占的比例，取值為0≤f≤0.1，δ為抽樣概率，取值為0.5≤δ≤1。

3.根據權利要求1所述的方法，其特征在于，所述步驟2，包括：

步驟2.1、將抽樣數據上傳到Hadoop分布式集群環境；

步驟2.2、Hadoop分布式集群環境中的主節點對傳入的抽樣數據進行分割成多個數據塊，并下發到各個子節點進行分布式處理計算抽樣數據的局部密度；

步驟2.3、各個子節點接收任務，利用MapReduce分布式并行框架對各個任務對應的抽樣數據進行局部密度計算，即計算抽樣數據周圍設定范圍內的鄰居數據的個數；

步驟2.4、各個子節點將計算出的局部密度反饋給主節點，主節點進行整合并根據各局部密度來計算出抽樣數據的平均密度，輸出抽樣數據的平均密度和局部密度。

4.根據權利要求1或3所述的方法，其特征在于，所述局部密度的計算公式如下：

其中，i和j分別表示第i個數據和第j個數據，n表示抽樣數據有n個屬性，i_n表示數據i的第n個屬性數據，j_n表示數據j的第n個屬性數據，D_ij表示第i個數據和第j個數據的距離，ρ_i表示第i個數據的局部密度，m表示數據的個數，D_e表示為第i個數據周圍截取半徑即設定范圍，λ為系數，若鄰居數據屬于截取半徑范圍即設定范圍內，則λ取值為1，否則值為0。

5.根據權利要求1或3所述的方法，其特征在于，所述平均密度計算公式：

其中，Avg表示m個抽樣數據的平均密度，ρ_i表示第i個抽樣數據的局部密度。