[發明專利]基于自適應網格邊界劃分的多維數據聚類改進算法

在審

• 申請號: 202210229884.2
• 申請日: 2022-03-09
• 公開（公告）號: CN114943266A
• 公開（公告）日: 2022-08-26
• 發明（設計）人: 赫斌;何云斌;趙琦
• 申請（專利權）人: 哈爾濱理工大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于自適應網格邊界劃分的多維數據聚類改進算法，主要包括以下步驟：

步驟一：根據單元網格劃分參數的值將原數據表的每一維劃分成相等的區間，同時將每一維上區間的劃分保存下來；

步驟二：n＝1；這時所有的單元都為候選密集單元；

步驟三：掃描原數據表，找出n維子空間中落在每個候選密集單元的數據點數；

步驟四：根據密度閾值公式計算密度閾值；

步驟五：根據計算出的密度閾值找出n維子空間中的密集單元；

步驟六：根據自適應邊界劃分算法重新劃分密集單元邊界；

步驟七：根據子空間的聚類效果篩選子空間；

步驟八：用MDL-based算法修剪子空間；

步驟九：由n維子空間中的密集單元集求出n+1維子空間中的候選密集單元集，若n+1維子空間中的候選密集單元集不為空，則跳轉第三步；

步驟十：用深度優先算法找出n維空間中的聚類；

步驟十一：用貪婪算法求覆蓋每個聚類的最大區域集；

步驟十二：求出每個聚類的最小覆蓋；

步驟十三：將聚類信息保存到結果表中。

2.根據權利要求1所述的一種自適應網格邊界劃分的多維數據聚類改進算法，對于任意單元網格，其密度閾值公式為：

3.根據權利要求2所述的網格密度閾值，其中每一個子空間中包含的數據投影點數和為sum，每個子空間的非空單元網格數目和為count(Si)。

4.根據權利要求1所述的一種自適應網格邊界劃分的多維數據聚類改進算法，對于子空間的聚類效果，可分為兩種情況：第一種情況，當子空間的密集連通單元網格的數量等于1時，說明該子空間將所有數據聚為一類，同時也會刪除一些孤立點和少部分簇中數據點，故對數據聚類幫助不大，可將此子空間舍棄；第二種情況：當子空間的密集連通單元網格的數量大于1時，說明該子空間將所有數據聚為不止一類，能夠有效幫助聚類，可將此子空間保留下來。

5.根據權利要求1所述的一種自適應網格邊界劃分的多維數據聚類改進算法，對于自適應網格邊界劃分算法重新劃分密集單元邊界。

6.根據權利要求5所述的自適應網格劃分邊界算法，是根據Clique算法，把原多維空間數據對象的每一維屬性按照設定很好的值劃分成相等的區間，即每個區間被劃分為[s1，l1)，[s2，l2)，…，[sn，ln)。遍歷待劃分密集單元，m＝1為第一次劃分網格，密集單元[si，li)相鄰的待劃分密集單元為[si+d，li+d)，其中d為區間長度。若帶劃分密集單元的1/2m區間[si+d，li+d/2m)的密度閾值大于1/2m的密度閾值ρ/2m，則將該區間并入到密集單元中，密集單元更新為[si，li+d/2m)。否則重復(4)步驟，直到待劃分密集單元[si+d，li+d/2m)中無數據點。