[發明專利]一種并行高效的基于網格與密度的多維空間數據聚類算法GRIDEN

在審

• 申請號: 201711063595.5
• 申請日: 2017-11-02
• 公開（公告）號: CN107908696A
• 公開（公告）日: 2018-04-13
• 發明（設計）人: 鄧超;陳智斌;郭曉惠;農英雄;黃聰;李喆;韋屹;汪倍貝;錢方遠
• 申請（專利權）人: 廣西中煙工業有限責任公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06K9/62
• 代理公司: 北京三聚陽光知識產權代理有限公司11250
• 代理人: 李紅團

技術領域

本發明涉及數據挖掘和大數據分析領域，具體涉及一種并行高效的基于網格與密度的多維空間數據聚類算法GRIDEN。

背景技術

空間數據聚類被廣泛的應用于許多信息技術領域，例如數據挖掘、模式識別、機器學習、人工智能、可視分析、地理信息系統等。在大數據時代，它可用來探索與發現數據中潛在的模式及價值，可應用于許多學科領域，例如天文學、生物信息學、文獻計量學、社會網絡分析、經濟網絡分析、交通網絡分析、氣象分析、智慧城市發展等。傳統的空間數據聚類方法主要有四種：1)、基于劃分的聚類；2)、基于密度的聚類；3)、層次聚類；4)、基于網格的聚類。

基于密度的聚類方法可以有效的處理數據噪聲點以及識別任意形狀，其中，最經典的算法是DBSCAN(Density-Based Spatial Clustering of Applications with Noise)，計算精度高。但是，傳統的DBSCAN算法的時間復雜度為O(N²)，隨著數據樣本數量的增長，所需計算時間呈指數級增加，使得DBSCAN的應用范圍與場景受到限制。基于網格的聚類算法可以高效的進行數據聚類，其時間復雜度為O(N)，所需計算時間隨著數據樣本數量的增長呈線性增加，但是對比基于密度的聚類算法，其聚類精度存在缺陷。

因此，如何將基于密度的算法和基于網格的算法有機結合起來，使得新型的變異算法可以同時具備基于密度的算法的精度和基于網格的算法的速度是值得研究的。同時現有絕大部分空間數據聚類方法在相關文獻中并未給出并行化設計技術方案，在大數據時代下，支持并行計算意味著計算時間可以通過增加計算核心數量成倍的壓縮，因此設計一款能夠支持并行計算的空間數據聚類算法是具有現實意義的。

發明內容

本發明要解決的是現有基于密度的空間數據聚類算法效率不夠高，以及現有基于網格的空間數據聚類算法精度不夠高的問題，設計了一款能夠同時具備基于密度聚類算法的精度和基于網格聚類算法的速度的變異空間數據聚類算法，同時結合了并行計算的思想與方法，本方法具備可靠的計算精度和非常強悍的運算效率。

為了解決上述技術問題，本發明提供如下技術方案：

一種基于網格與密度的多維空間數據聚類算法GRIDEN，包括以下步驟：

步驟1，根據預設近鄰距離參數ε、網格劃分系數k及D維空間數據集P創建D維空間數據網格G，并將P中的數據點映射到G中；

步驟2，計算關于所述近鄰距離參數ε與所述網格劃分系數k的近鄰格子子集S；

步驟3，根據預設最小近鄰參數Min_N和所述近鄰格子子集S對所述D維空間數據網格G進行無監督的空間網格聚類，并根據數據點所在D維格子的聚類結果對整個所述D維空間數據集P進行分類標注。

可選地，上述并行高效的基于網格與密度的多維空間數據聚類方法中，所述k為大于0的自然數，ε為大于0的任意數值；D為正整數。所述創建一個D維空間數據網格G的具體方法為：計算每個格子的邊長并根據所述邊長L對所述D維空間數據集P的每個維度的數值范圍進行平均切分；所述空間數據網格G中的每個格子為各邊相等的超方格子。所述將P中的數據點映射到G中的具體方法為：根據所述D維空間數據集P中每個點的D維信息將數據點映射到相應的格子，并進行數據點數量累加與記錄。

可選地，上述基于網格與密度的多維空間數據聚類算法GRIDEN中，所述近鄰格子子集S的計算方法具體包括以下步驟：

1)對于所述D維空間數據網格G中的任意格子C_i，其所述近鄰格子子集S中的任意格子C_j的正中心與C_i的正中心之間的空間距離不超過ε；

2)C_i也是C_i自己的近鄰格子；

3)所述近鄰格子子集S存在且僅存在于格子子集S₁中，其中，S₁是以C_i為空間正中心的(2k+1)^D個格子的集合，且S₁中的任意格子C_j與C_i在任意維度的間距均不超過k。

可選地，上述基于網格與密度的多維空間數據聚類算法GRIDEN中，所述無監督的空間聚類的計算方法具體包括以下步驟：