[發明專利]基于MapReduce的并行密度聚類挖掘方法

在審

• 申請號: 202010414231.2
• 申請日: 2020-05-15
• 公開（公告）號: CN111597230A
• 公開（公告）日: 2020-08-28
• 發明（設計）人: 毛伊敏;徐鍇濱
• 申請（專利權）人: 江西理工大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/28
• 代理公司: 重慶天成卓越專利代理事務所(普通合伙) 50240
• 代理人: 王宏松

1.一種基于MapReduce的并行密度聚類挖掘方法，其特征在于，包括以下步驟：

S1，根據數據點空間分布狀況，自適應劃分網格單元；

S2，對每個數據分區，構建加權網格間的關聯性；

S3，計算網格密度；

S4，利用MapReduce計算模型，得到并行計算局部簇；

S5，利用并查集的局部簇合并算法，以及MapReduce計算模型，得到聚類全局簇。

2.根據權利要求1所述的基于MapReduce的并行密度聚類挖掘方法，其特征在于，在步驟S1中包括：

將d維數據空間等分為2^d個初始網格單元，再根據數據點之間的最小平均距離計算網格邊長的劃分閾值當所有網格滿足非空且當前邊長大于密度閾值時，則停止網格劃分；其網格邊長劃分閾值的計算方法：

其中，n表示數據點的個數；

min()表示取最小值；

p_i和p_j分別為d維空間中的任意兩個數據點。

3.根據權利要求1所述的基于MapReduce的并行密度聚類挖掘方法，其特征在于，在步驟S2中包括：對加權網格的作用范圍進行設置：

其中，表示加權網格作用范圍內的網格集合，表示一個網格單元，s_i表示在某一維度下的第i個網格單元；

s_i'表示區別于s_i的其余網格單元；

表示對于任意的i其1≤i≤d；

對加權網格的權值進行設置：

對于中的一個數據點p，如果并且則設置為1；否則，設置為0；

其中，表示網格單元的加權網格中的任意網格單元，表示網格單元相對于網格單元的權重值。

4.根據權利要求1所述的基于MapReduce的并行密度聚類挖掘方法，其特征在于，在步驟S3中包括：

lbP(t)表示對P(t)作以2為底的對數運算；

H'(X)表示網格單元的密度；

其中，t表示數據網格化后的某一非空網格單元的密度，即以該網格單元為中心構成的加權網格中的所有數據點個數；x表示該密度取值下的網格單元數量；P(t)是網格單元密度為t所出現的概率；count(t)表示網格單元中網格密度為t的網格單元個數；count(n)表示劃分后的非空網格單元總數。

5.根據權利要求1所述的基于MapReduce的并行密度聚類挖掘方法，其特征在于，在步驟S4中包括：

在并行計算網格密度階段：

輸入網格對象g以及網格中的點p_i；接著，執行map函數計算出以網格對象g為中心的加權網格中點的數量C_i[g]，并輸出key-value值＜g,C_i[g]＞；之后，執行reduce函數合并map函數的結果，并使用WGIE策略計算出每個網格對象的網格密度h_i，最后輸出key-value值＜(g,N(g_i)),h_i＞傳入下一個階段；

在并行計算局部簇階段：

輸入數據集D中的點p_i以及上個階段計算出的key-value值＜(g,N(g_i)),h_i＞；之后，調用map函數對數據進行計算，如果輸入的數據為數據點p_i，則map函數計算每個數據點所對應的網格對象g并輸出key-value值＜g,p_i＞，如果輸入的數據為key-value值＜(g,N(g_i)),h_i＞，則map函數計算當前網格對象g是否為核心網格，如果h_i≤μ，則當前網格對象g為核心網格，輸出key-value值＜g,N(g_i)＞，如果h_i＞μ，則不輸出任何結果；最后執行Reduce函數，合并map函數的結果，輸出key-value值＜(g,N(g_i)),N(p_i)＞。