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

有效

• 申請號: 201210434240.3
• 申請日: 2012-11-05
• 公開（公告）號: CN103793438B
• 公開（公告）日: 2017-07-14
• 發明（設計）人: 孫占全
• 申請（專利權）人: 山東省計算中心（國家超級計算濟南中心）
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于MapReduce編程模型的并行聚類方法，其特征在于，包括步驟：

原始數據劃分及參數設定；

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

以基于MapReduce的并行中心聚類方法實現最終聚類結果；

所述的原始數據劃分及參數設定，具體包括：

對原始文件進行分析，將原始數據轉換成用概率向量表示的形式，然后隨機的將原始數據均勻劃分成n份，將n份數據分布到m個map節點，設定聚類截尾精度閾值α₀、β₀和δ₀，其中α₀是聚類步驟與該組數據中所有數據數比值的閾值；β₀是信息損失量實際損失值與預測值差值的閾值；δ₀是在并行中心聚類過程中，當前的聚類中心與上次聚類中心差值的閾值；

所述的基于MapReduce的并行信息瓶頸理論聚類方法確定聚類數和初始聚類中心，具體包括：

針對每個數據劃分，利用基于信息瓶頸理論聚類方法進行聚類：a.將每個向量數組看作最初的類；b.計算任意兩組向量合并產生的信息損失量，選擇合并后產生的信息損失量最小的一組進行合并，生產新的數組；c.重復步驟b直至滿足聚類截尾精度α₀和β₀，確定聚類數，具體為：對于第i個數據劃分，當聚類步數達到第k步k＞n_iα₀時，開始利用當前聚類步前k-1步產生的信息損失量進行最小二乘回歸，根據回歸方程，當前聚類步的預測值為則預測值與實際信息損失量的差值為當e＞β₀時，聚類結束，聚類數即為當前數據集的聚類數；

合并各數據劃分的聚類中心，利用基于信息瓶頸理論聚類方法重新聚類，生成全局初始聚類中心；

所述基于MapReduce的并行中心聚類方法實現最終聚類結果，具體包括：

a利用中心聚類方法確定每步聚類中心；

b通過迭代的方式調整聚類中心，當滿足迭代閾值時，聚類結束；

所述利用中心聚類方法確定每步聚類中心，具體包括：

在獲取初始聚類中心C⁰后，將其分布到各個Map節點，設k個空數據集P¹，P²，...，P^k，計算樣本x與初始聚類中心之間的距離，用信息損失作為測度，當x與之間的信息損失最小時，將樣本x放入到數據集Pⁱ中，根據下式計算數據集Pⁱ的中心

對數據子集的所有數據計算過后，根據新生成的數據集P¹，P²，...，P^k計算新的聚類子中心C¹，C²，...，C^m，將所有的數據子集中心收集到一起，根據(2)計算新的全局聚類中心；

所述通過迭代的方式調整聚類中心，當滿足迭代閾值時，聚類結束，具體包括：

計算新聚類中心x^new與上次聚類中心x^old的差值，如果差值小于預先指定的閾值，迭代過程結束，如果大于指定的閾值，繼續迭代過程，差值計算如下

當δ＜δ₀時，迭代結束。

2.根據權利要求1所述的一種基于MapReduce編程模型的并行聚類方法，其特征在于，

根據信息瓶頸理論，兩組數組合并所產生的信息損失量為：

。

3.根據權利要求1所述的一種基于MapReduce編程模型的并行聚類方法，其特征在于，所述生成全局初始聚類中心，具體包括：

收集所有Map節點計算得到的數據子集的分聚類中心，生成新的聚類樣本，根據所述基于信息瓶頸理論的聚類方法生成全局初始聚類中心并確定聚類數。