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

在審

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

技術領域

本發明涉及數據聚類技術領域，具體涉及一種改進的KIDBSCAN數據聚類方法。特別是適用銀行業大型數據集的聚類。

技術背景

由于科技的快速發展，硬件設備儲存容量的倍增，以及網絡的發達，使得銀行數據中心查找數據變得非常容易。然而，在查找時往往獲得過多的數據量，而必須耗費很大的時間和精力去找出有用的信息。于是在銀行業信息發達、數據充斥的情況下，現代的信息技術所要解決的問題已不再是如何管理數據，而是如何從大量數據中，找出真正有用的信息，這要依賴于數據挖掘技術。

數據挖掘主要是從未經過結構化處理的龐大數據集中，通過歸納、分析等相關步驟，以期能發現數據中所隱藏的有用信息或趨勢的一種處理技術。而在數據挖掘的領域中，較為常見的研究議題有數據聚類(Data?Clustering)、數據分類(Data?Classification)、序列模式(Sequential?Pattern)及關聯規則(Association?Rules)等。其中，數據聚類是最常被使用的方法之一。

在1967年第一個聚類方法K-means(MacQueen,1967)的出現，使得往后有眾多的學者相繼投入數據聚類的研究領域，以期能研究出一個具有高效率、可擴展性、可去除無用數據且能獲得最優的聚類算法。

發明內容

本發明要克服現有技術的上述缺點，提供一種利用空間切割技術的密度式聚類方法。

本發明提出一個新的聚類方法，主要是針對KIDBSCAN(Tsai?and?Liu,2006)做進一步的改進，因KIDBSCAN分群過程從高密度數據點開始進行，所能提高的聚類效率相當有限。于是本發明提出的算法運用K-means切割式分群的特點，將數據空間切割為多個子空間，以減少后續密度式分群步驟中的擴張詢問次數，進而大幅提高分群算法的效率，并保有原先的聚類質量。

本發明將進一步改善KIDBSCAN的聚類效率，使其能適用于大型數據集，且保留原有的分群質量，本發明引入空間切割的技術作為分群前的預處理，將數據空間切割為多個子空間，接著以IDBSCAN針對這些子空間進行聚類，最后進行類間合并直到數據集所需群數為止。

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

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：合并群集；

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