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

在審

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

本發明提出了一種基于MapReduce的并行密度聚類挖掘方法，其特征在于，包括以下步驟：S1，根據數據點空間分布狀況，自適應劃分網格單元；S2，對每個數據分區，構建加權網格間的關聯性；S3，計算網格密度；S4，利用MapReduce計算模型，得到并行計算局部簇；S5，利用并查集的局部簇合并算法，以及MapReduce計算模型，得到聚類全局簇。本發明提出的方法在運行效率上以及聚類精確度上都有顯著的提高。

技術領域

本發明涉及一種大數據挖掘技術領域，特別是涉及一種基于MapReduce的并行密度聚類挖掘方法。

背景技術

數據挖掘又被稱為知識發現KDD(knowledge discover in database)，其目的在于發現大量數據集中有用的信息。常見的數據挖掘任務有聚類、分類、關聯規則挖掘等。其中，聚類算法是一種無監督的學習算法，能夠根據數據對象的相關特征，將相似的對象歸為一類，而差別較大的數據對象則劃分到不同類中，因此聚類算法可以從樣本數據中發現潛在的分布模式，被廣泛應用于文本分析，生物學，醫學，衛星圖像分析等各種領域。在聚類算法中，基于密度的聚類算法，如DBSCAN和OPTICS 算法，可以發現任意形狀的簇且對噪聲不敏感，受到人們的廣泛關注。

隨著互聯網信息技術的不斷發展以及大數據時代的到來，使得大數據相較于傳統數據，具有了4V特性——Volume(數量大)、Variety(速度快)、Value(價值密度低)。但是傳統的密度聚類算法所需的時間復雜度較高，只適用于較小規模的數據集，而在處理大數據時無疑會產生更龐大的計算復雜度。所以，如何降低密度聚類算法的計算復雜度，將其應用到大數據上，是個具有挑戰性的難題。

隨著Google開發的MapReduce架構的廣泛應用，以Hadoop、Spark為代表的分布式計算架構受到了越來越多的關注。為了能進一步降低密度聚類算法的計算復雜度，通過改進傳統的密度聚類算法，并與分布式計算架構相結合成為目前密度聚類算法研究的主要方向。Li等人首先提出了基于MapReduce下的并行DBSCAN算法，其使用MapReduce計算架構，將數據分片后并行執行DBSCAN算法形成局部簇，再通過增量的方式合并得到全局簇，實現了DBSCAN算法的并行化，然而該算法沒有提出有效的方法來劃分數據，合并局部簇的計算復雜度較高；Silva等人提出了 MapReduce下的分布式DBSCAN算法，根據特定場景劃分數據，聚類簇的合并采用增量的方式，算法的時間復雜度較高，算法總體并行化效率較低。Noticewala等人和瞿原等人分別提出了基于Hadoop和基于Spark下的并行密度聚類算法，有效降低密度聚類算法的計算復雜度，同時分別給出了基于Hadoop和Spark下的數據劃分方案，但算法對數據進行分區處理時未具體考慮數據特性，也沒有給出有效的局部簇合并生成全局簇的方法。