[發明專利]聚類實現方法及系統

有效

• 申請號: 200910091866.7
• 申請日: 2009-08-31
• 公開（公告）號: CN101996198A
• 公開（公告）日: 2011-03-30
• 發明（設計）人: 徐萌;高丹;鄧超;羅治國;周文輝;孫少陵;何清;趙衛中;馬慧芳
• 申請（專利權）人: 中國移動通信集團公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 郭潤湘

技術領域

本發明涉及數據挖掘領域，尤其涉及一種海量樣本數據的聚類實現方法及相應系統。

背景技術

在當前數據挖掘領域，已有的聚類算法可以分為幾類，包括基于劃分的方法，基于層次的方法，基于密度的方法，基于網格的方法以及基于模型的方法等。

進行數據挖掘時，需要將對全部數據進行逐條計算及分析，算法時間復雜度高。海量數據是對各種聚類算法的一個挑戰。已有的聚類算法大都還只是停留在實驗室階段，對于海量數據，有些算法或者不能進行有效處理，或者處理效率很低。

DBSCAN算法是一個基于空間密度的聚類算法。該算法將具有足夠高密度的區域劃分為聚類，并可以在帶有“噪聲”(指具有一些非核心樣本點)的樣本空間中發現任意形狀的聚類。

DBSCAN算法的基本原理為：

設定數據挖掘時樣本的ε鄰域(對于給定對象的半徑ε內的區域稱為該對象的ε鄰域)和最小密度(最小密度為指定ε鄰域內樣本數量的最少個數)，并當一個未被標記的樣本的ε鄰域內的未被標記所屬聚類的樣本數量滿足大于設定的最小密度時，確定該樣本為核心樣本。標記核心樣本屬于當前聚類，以及將該核心樣本的ε鄰域內各樣本置入候選隊列并標記為屬于當前聚類。進一步確定候選隊列中各候選樣本是否為核心樣本，若是，重復執行將確定出的核心樣本的ε鄰域內各樣本置入候選隊，直到遍歷整個樣本數據庫的中每個樣本，標記出每個樣本所屬聚類。

上述DBSCAN聚類算法，對于少量樣本，可以方便地在單機上實現。但對于海量樣本而言，一方面由于單機內存容量有限，不可能讀入海量的樣本數據；另一方面，由于聚類過程中需要進行候先隊列的動態更新，對樣本數據庫中的每一個樣本進行所屬聚類標記，處理時間很長，在實際的數據業務應用中，效率很低。

因此，對于實際應用中海量數據的處理，如何有效地提升處理效率是數據挖掘中需要加以解決的一個主要問題。

發明內容

本發明實施例提供聚類實現方法及聚類實現系統，通過采用多個節點并行處理，解決現有技術對海量數據無法實現聚類處理及處理效率低的問題。

本發明實施例提供的一種聚類實現方法包括：

步驟1、主控節點根據樣本數據庫中的當前未標記所屬聚類的樣本確定出一個核心樣本，并將該核心樣本的ε鄰域內各樣本標記為屬于當前聚類，將該核心樣本的ε鄰域內各樣本存入候選隊列中；

步驟2、所述主控節點對所述候選隊列中的候選樣本進行分片，將分片樣本分配并下發給至少兩個計算節點；

步驟3、每個所述計算節點根據樣本數據庫中的當前未標記樣本、設定的ε鄰域和最小密度分別確定出分配的分片樣本中的每一個樣本是否為核心樣本；將確定出的核心樣本的ε鄰域內各樣本存入所述候選隊列中；且當分配的分片樣本全部處理完畢后，通知所述主控節點；

步驟4、所述主控節點接收到每個所述計算節點發送的通知后，判斷所述候選隊列中是否存在候選樣本，當存在候選項樣本時，將每個候選樣本標記為屬于當前聚類，轉至上述步驟2；當不存在候選樣本時，轉至上述步驟1，直到所述樣本數據庫中的每一個樣本都已標記所屬聚類。

本發明實施例提供的另一種聚類實現方法，包括：

步驟1、主控節點對原始數據庫中當前未標記樣本進行分塊，將分塊樣本分配并下發給至少兩個計算節點；以及根據原始數據庫中的當前未標記樣本確定出一個核心樣本，并將該核心樣本的ε鄰域內各樣本標記為屬于當前聚類，將該核心樣本的ε鄰域內各樣本存入候選隊列中；

步驟2、所述主控節點將所述候選隊列中的候選樣本下發給每個所述計算節點；

步驟3、每個所述計算節點根據分配的分塊樣本和設定的ε鄰域，分別統計每一個候選樣本的本地ε鄰域內的樣本數量，并發送給合并節點；

步驟4、所述合并節點對每一個候選樣本，累計所述計算節點發送的對應樣本數量，并根據累計和值和設置的最小密度確定每一個候選樣本是否為核心樣本；當確定出存在核心樣本時，將確定出的核心樣本通知給各計算節點；以及當確定出不存在核心樣本時，通知所述主控節點；

步驟5、各計算節點接收到所述合并節點發送的核心樣本通知后，將對應核心樣本的本地ε鄰域內的各樣本存入所述候選隊列中，當存入完成后，通知所述主控節點；

步驟6、所述主控節點接收到所述合并節點發送的通知后，轉至上述步驟1；以及接收到每個所述計算節點發送的通知后，將所述候選隊列的每個候選樣本標記為屬于當前聚類，轉至上述步驟2；直到原始數據庫中的每一個樣本都已標記所屬聚類。

本發明實施例提供的一種聚類實現系統，包括：主控節點、至少兩個計算節點；