[發明專利]一種基于密度的多層分步聚類方法

在審

• 申請號: 201910378047.4
• 申請日: 2019-05-08
• 公開（公告）號: CN110210517A
• 公開（公告）日: 2019-09-06
• 發明（設計）人: 董明剛;吳宇倫;敬超
• 申請（專利權）人: 桂林理工大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于密度的多層分步聚類方法，其特征在于包括以下步驟：

步驟1，對于由n個待聚類j維數據:

X1(x11,x12…x1j),X2(x21,x22..x2j)…..Xn(xn1,xn2…xnl),將每個數據點看成一個節點，然后計算每兩個節點之間的距離(歐氏距離)，定義為相應節點之間的邊的權值，這樣一來就將整個數據集看成了一個全連通的無向加權圖G(V,E)；

步驟2，通過新的密度定義方式D(Xi,Xj)計算出整個數據集的平均密度；

步驟3，隨機選取一個數據點開始遍歷所有數據，計算當前數據點的密度；

步驟4，對比當前數據點的密度和平均密度，如果大于平均密度，則以該點為一個核心，向它周圍的K個鄰居遍歷，如果鄰居的密度也大于平均密度，則將其鄰居也看做核心點，置于核心點的列隊中，如果密度小于平均密度，則暫時將其看做噪聲或是離群點，暫時不予處理；

步驟5，遍歷步驟4中的核心點隊列，重復步驟4中的算法，遍歷到一個點的時候就將該點從隊列中去除，直到一個隊列的長度為0，至此一個簇的核心部分已經被偵測出來；

步驟6，通過密度相似度來判定簇的核心部分周圍的數據點是否屬于簇的一部分，如果相似度大于一個閾值，則將該點視為簇的邊界點，小于閾值的視為噪點；

步驟7，重復步驟3-6，直到所有大于平均密度的點以及其周圍的點都已經被分配完畢，這個時候有兩種情況，一種是所有的簇都已經被發現，剩下未被分配的點全都視為噪點，另一種是該數據集是密度不均勻的數據集，有一些簇的密度很大，而有一些簇的密度很小；

步驟8，統計已經被分配的簇，計算每個已被分配簇的平均數據量，例如當前有a個簇已經被發現，并且當前有m個數據點已經被分配，則每個簇的平均數據量為ap＝m/a；

步驟9,若當前剩余的數據量大于簇的平均數據量的二分之一，即：n–m>＝ap/2,則視為還有密度較小的簇未被發現，重復步驟3-8，直到n–m<ap/2.至此，所有數據點都已經被分配完畢。