[發明專利]利用空間切割技術的密度式聚類方法

在審

• 申請號: 201510329447.8
• 申請日: 2015-06-15
• 公開（公告）號: CN104991902A
• 公開（公告）日: 2015-10-21
• 發明（設計）人: 劉東升;郭飛鵬;王冰;吳功興;趙毅;謝紅華;沈建華
• 申請（專利權）人: 浙江工商大學;浙江金大科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

1.利用空間切割技術的密度式聚類方法，包括以下步驟：

Step1：輸入參數和資料集；

需輸入的參數包括：

群數K：該參數是源于K-means，其用途是設定數據集將被分為多少類；半徑Eps：半徑與最少包含點兩參數是源于IDBSCAN，半徑參數的概念是指使用著認為以某點為圓心的半徑距離的數據點都可以被視為鄰居點；最少包含點Minpts：是指鄰居點數量要大于或等于此參數所設定的值，才能夠將這些數據點視為同一群；

Step2：執行K-means算法；

K-means算法針對所設定的參數K，將數據集劃分為K個子空間群集，每一數據點均擁有分群編號Cluster?ID，再依照分群編號予以歸類；

Step3：執行IDBSCAN算法；

IDBSCAN針對經由K-means所分出的K個群集分別進行分群，當進行擴張詢問時，IDBSCAN掃描的范圍僅止于一個群集之內；

Step4：找出群集邊界點；

找出群集邊界點是為了減少數據量，以提高后續合并的效率；由于合并動作是以群集之間的最近距離進行合并，只需要各群集的邊界點來做距離計算即可，故靠近群集核心的數據點是可以被忽略的；

Step5：判斷是否需要進行合并；

一開始所設定的參數K，不僅決定將空間切割為多少子空間，也是決定最后數據集應被分為幾群的依據，假如經由IDBSCAN分群過后，群集數量大于K群，則進行Step6將群集合并，否則結束分群；

Step6：合并群集；

合并方式本發明采取群集之間的最近距離，即群集間最接近的兩個數據點的距離，計算公式如下：

dmin(Ci,Cj)=minP∈Ci,P′∈Cj||P-P′||]]>

公式中C_i與C_j代表經由IDBSCAN分群后的第i個和第j個群集，P與P′各自代表兩群集內的數據點，從所有群集間找出距離最近的兩群集進行合并動作，每次僅進行一次的合并，合并完成后會將當前的群集數減1；

Step7：判斷是否達到合并結束條件；

此階段是判別當前的群集數是否達到之前所設定的群數K，如符合條件則分群結束，否則回到Step6繼續進行合并。