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

在審

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

1.一種基于密度與網格結合的聚類方法，其特征在于，包括以下步驟：

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

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

計算每個初始箱的密度；

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

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

根據鄰居鏈生成聚類。

2.根據權利要求1所述的一種基于密度與網格結合的聚類方法，其特征在于，所述對每個網格空間沿軸創建多個均勻的初始箱具體為：將網格空間的軸的范圍均分為N份得到初始箱范圍，初始箱范圍內的所有多維數據點組成初始箱，其中N為創建的初始箱的數量。

3.根據權利要求1或2任一項所述的一種基于密度與網格結合的聚類方法，其特征在于，所述計算每個初始箱的密度具體為：統計每個初始箱內所包含的多維數據點的個數得到每個初始箱的密度。

4.根據權利要求3所述的一種基于密度與網格結合的聚類方法，其特征在于，所述確認每個網格空間的最密集相鄰網格建立鄰居鏈包括以下步驟：

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

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

5.根據權利要求3所述的一種基于密度與網格結合的聚類方法，其特征在于，所述根據鄰居鏈生成聚類具體為：遍歷網格空間并按照以下方式將網格空間添加到簇中：對于不屬于簇且最密集鄰居屬于簇的網格空間，將該網格空間添加到最密集鄰居的簇中；對于不屬于簇且最密集鄰居也不屬于簇的網格空間，創建一個新簇并在新簇中添加兩個空白網格空間；對于屬于簇且具有最密集鄰居的網格空間，將其最密集鄰居添加到該網格空間的簇中；對于屬于簇且最密集鄰居屬于不同簇的網格空間，合并這兩個簇。

6.一種基于密度與網格結合的聚類裝置，其特征在于，包括:

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

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

初始箱密度計算器，用于計算每個初始箱的密度；

初始箱密度比較器，用于比較當前初始箱的密度和當前初始箱對應的下一個初始箱的密度直至遍歷所有初始箱以生成自適應網格，所述初始箱密度比較器包括：初始箱合并器，用于比較得到當前初始箱的密度和其對應的下一個初始箱的密度兩者之差小于設定閾值時合并兩個初始箱；

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

聚類生成器，用于根據鄰居鏈生成聚類。

7.根據權利要求6所述的一種基于密度與網格結合的聚類裝置，其特征在于，所述初始箱創建器將網格空間的軸的范圍均分為N份得到初始箱范圍，初始箱范圍內的所有多維數據點組成初始箱，其中N為創建的初始箱的數量。

8.根據權利要求6或7任一項所述的一種基于密度與網格結合的聚類裝置，其特征在于，所述初始箱密度計算器統計每個初始箱內所包含的多維數據點的個數得到每個初始箱的密度。

9.根據權利要求8所述的一種基于密度與網格結合的聚類裝置，其特征在于，所述鄰居鏈建立器包括：

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

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

10.根據權利要求8所述的一種基于密度與網格結合的聚類裝置，其特征在于，所述聚類生成器遍歷網格空間并按照以下方式將網格空間添加到簇中：對于不屬于簇且最密集鄰居屬于簇的網格空間，將該網格空間添加到最密集鄰居的簇中；對于不屬于簇且最密集鄰居也不屬于簇的網格空間，創建一個新簇并在新簇中添加兩個空白網格空間；對于屬于簇且具有最密集鄰居的網格空間，將其最密集鄰居添加到該網格空間的簇中；對于屬于簇且最密集鄰居屬于不同簇的網格空間，合并這兩個簇。