[發明專利]一種MapReduce框架下的空間網絡對象聚類方法

在審

• 申請號: 201710178623.1
• 申請日: 2017-03-23
• 公開（公告）號: CN107545272A
• 公開（公告）日: 2018-01-05
• 發明（設計）人: 郭黎敏;高需;丁治明;陳軍成;蘇醒
• 申請（專利權）人: 北京工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京思海天達知識產權代理有限公司11203
• 代理人: 張慧

1.一種MapReduce框架下的空間網絡對象聚類方法，其特征在于，包括以下步驟：

步驟1、實現基于圖生成的層次聚類框架GGHC和基于邊的概略化聚類方法；

步驟2、實現基于代價的空間網絡對象劃分方法；

步驟3、實現MapReduce并行框架下的GGHC-MR方法。

2.如權利要求1所述的，MapReduce框架下的空間網絡對象聚類方法，其特征在于，所述步驟1空間網絡對象聚類算法GGHC的實現方法包括如下：

步驟1-1、尋找任一非空邊上聚類，以聚類頂點表示，并為連接性聚類頂點生成相應的匯聚-連接錨點；

步驟1-2、根據匯聚-連接錨點合并聚類，若可合并，則連接性聚類頂點間存在生成圖的一條邊；

步驟1-3、尋找所有生成圖的連通子圖，標記在同一個連通子圖中的對象屬于相同聚類。

3.如權利要求2所述的MapReduce框架下的空間網絡對象聚類方法，其特征在于，步驟1-1所述的空間網絡中邊上的對象進行聚類的方法包括如下：

步驟1-1-1、按照ε/2將邊劃分為多個概略化桶：將對象p存放在概略化桶中，此時對象間分組有序。在聚類過程中，以桶而非對象作為檢索目標，減少了查詢次數，僅在少數情況下依據概略化桶的性質比較桶間對象的相似性。

步驟1-1-2、依據概略化桶的性質，合并桶中對象到一個聚類頂點中；若兩桶中對象屬于不同聚類，則為桶中對象構造新的聚類頂點。

步驟1-1-3、判斷是否有對象與邊的第一個聚類頂點或最后一個聚類頂點的距離不超過ε，如果條件成立，則生成匯聚-連接錨點。

步驟1-1-4、為了提高聚類生成圖子圖遍歷效率，分別用集合V’o和V’表示邊中確定化聚類頂點和連接性聚類頂點，僅為連接性聚類頂點及生成的邊構造索引，縮小索引樹。

4.如權利要求3所述的MapReduce框架下的空間網絡對象聚類方法，其特征在于，步驟1-1-1與步驟1-1-2所述概略化桶的性質如下：

(1)性質1.p,q∈bkt_i，則p，q屬于同一聚類。

(2)性質2.p∈bkt_i,q∈bkt_i+1，則p，q屬于同一聚類。

(3)性質3.p∈bkt_i,q∈bkt_i+2且則當D_d(B_r(bkt_i),B_l(bkt_i+2))≤ε時，p，q屬于同一聚類。

(4)性質4.p∈bkt_i,q∈bkt_i+2且則當D_d(B_r(bkt_i),B_l(bkt_i+2))＞ε時，p，q屬于不同聚類。

(5)性質5.p∈bkt_i,q∈bkt_i+k且其中0＜m＜k,k≥3，則p，q屬于不同聚類。

5.如權利要求2所述的MapReduce框架下的空間網絡對象聚類方法，其特征在于，步驟1-2所述構造生成圖的邊的方法包括如下：

步驟1-2-1、將屬于同一個匯聚頂點v_i的匯聚-連接錨點按照距離聚類頂點v_i的遠近非遞減排序；

步驟1-2-2、判斷距離最小的錨點與其余錨點所含連接性聚類頂點是否存在邊，若存在，則構造生成圖的邊；

步驟1-2-3、若匯聚頂點v_i的鄰接邊長度不大于ε，且其上不存在對象，則生成v_i鄰接頂點v_j的匯聚-連接錨點。