[發明專利]一種基于密度與網格結合的聚類方法及其裝置

在審

• 申請號: 201910592877.7
• 申請日: 2019-07-03
• 公開（公告）號: CN110472654A
• 公開（公告）日: 2019-11-19
• 發明（設計）人: 劉海波;李千目;龍華秋;容振邦
• 申請（專利權）人: 五邑大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 44205 廣州嘉權專利商標事務所有限公司
• 代理人: 陳均欽<國際申請>=<國際公布>=<進入

本發明公開了一種基于密度與網格結合的聚類方法及其裝置，對多維數據點集合劃分網格并沿軸創建初始箱，根據初始箱密度優化網格空間，通過結合密度和網格的方式進行聚類，在自適應網格結構的基礎上根據初始箱密度進行優化，使相鄰的網格空間具有大差異性的密度，根據此才建立鄰居鏈和生成聚類，減少了區域的細化，從而進一步減少聚類的處理時間。

技術領域

本發明涉及數據處理領域，特別是一種基于密度與網格結合的聚類方法及其裝置。

背景技術

聚類是將物理或抽象對象的集合分成由類似的對象組成的多個類的過程。由聚類所生成的簇是一組數據對象的集合，這些數據對象與同一個簇中的數據對象彼此相似，與其他簇中的數據對象相異。聚類是一項存在于許多數據挖掘相關的大型任務中的基礎級別任務。傳統的聚類方法主要有以下四種：劃分方法、層次方法、基于密度的方法和基于網格的方法。但對于大數據處理方面，數據量越來越龐大，傳統方法已經越來越難以適應。如何減少聚類的處理時間成為一個迫在眉睫的問題。

發明內容

本發明的目的在于至少解決現有技術中存在的技術問題之一，提供一種基于密度與網格結合的聚類方法及其裝置，能有效減少聚類的處理時間。

本發明解決其問題所采用的技術方案是：

本發明的第一方面，提供了一種基于密度與網格結合的聚類方法，包括以下步驟：

將多維數據點集合劃分為多個網格空間；

對每個網格空間沿軸創建多個均勻的初始箱；

計算每個初始箱的密度；

比較當前初始箱的密度和當前初始箱對應的下一個初始箱的密度直至遍歷所有初始箱以生成自適應網格，其中若當前初始箱的密度和其對應的下一個初始箱的密度兩者之差小于設定閾值，則合并兩個初始箱；

確認每個網格空間的最密集相鄰網格建立鄰居鏈；

根據鄰居鏈生成聚類。

上述基于密度與網格結合的聚類方法至少具有以下的有益效果:通過結合密度和網格的方式進行聚類，在自適應網格結構的基礎上根據初始箱密度進行優化，使相鄰的網格空間具有大差異性的密度，使網格空間具有不規則的網格間距且基于數據的實際分布，減少了區域的細化，從而進一步減少鄰居鏈建立時間和聚類生成時間。

根據本發明的第一方面，所述對每個網格空間沿軸創建多個均勻的初始箱具體為：將網格空間的軸的范圍均分為N份得到初始箱范圍，初始箱范圍內的所有多維數據點組成初始箱，其中N為創建的初始箱的數量。

根據本發明的第一方面，所述計算每個初始箱的密度具體為：統計每個初始箱內所包含的多維數據點的個數得到每個初始箱的密度。

根據本發明的第一方面，所述確認每個網格空間的最密集相鄰網格建立鄰居鏈包括以下步驟：

統計每個網格空間內所包含的多維數據點的個數得到每個網格空間的密度；

比較當前網格空間的密度和與當前網格空間相鄰的所有網格空間的密度得到當前網格空間的最密集鄰居直至遍歷所有網格空間，并據此建立鄰居鏈，其中最密集鄰居為當前網格空間和與當前網格空間相鄰的所有網格空間中密度最大的網格空間。

根據本發明的第一方面，所述根據鄰居鏈生成聚類具體為：遍歷網格空間并按照以下方式將網格空間添加到簇中：對于不屬于簇且最密集鄰居屬于簇的網格空間，將該網格空間添加到最密集鄰居的簇中；對于不屬于簇且最密集鄰居也不屬于簇的網格空間，創建一個新簇并在新簇中添加兩個空白網格空間；對于屬于簇且具有最密集鄰居的網格空間，將其最密集鄰居添加到該網格空間的簇中；對于屬于簇且最密集鄰居屬于不同簇的網格空間，合并這兩個簇。

本發明的第二方面，提供了一種基于密度與網格結合的聚類裝置，其特征在于，包括: