[發(fā)明專利]聚類實現(xiàn)方法及系統(tǒng)

有效

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

1.一種聚類實現(xiàn)方法，其特征在于，包括：

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

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

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

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

2.如權(quán)利要求1所述的聚類實現(xiàn)方法，其特征在于，在所述步驟1之前還包括：所述主控節(jié)點對原始數(shù)據(jù)庫進行抽樣處理，得到所述樣本數(shù)據(jù)庫；以及

在所述步驟4之后還包括：

所述主控節(jié)點對當前每一個聚類，分別計算屬于該聚類的各樣本的樣本值的均值，確定出每一個聚類的對應(yīng)聚類中心點；

所述主控節(jié)點對所述原始數(shù)據(jù)庫中除所述樣本數(shù)據(jù)庫中包含的樣本外的其余樣本進行分塊，將分塊樣本分配給至少兩個計算節(jié)點；以及將分配的分塊樣本及確定出的所述聚類中心點分別發(fā)送給每個所述計算節(jié)點；

每個所述計算節(jié)點分別計算分配的分塊樣本中每個樣本在樣本空間中的對應(yīng)樣本點與各聚類中心點的距離，將每個樣本歸屬到所述距離最小的對應(yīng)聚類中心點所屬聚類，并返回樣本標識與所屬聚類的聚類標識給所述主控節(jié)點；

所述主控節(jié)點根據(jù)每個所述計算節(jié)點返回的樣本標識與所屬聚類的聚類標識，確定出所述其余樣本中的每個樣本的所屬聚類。

3.如權(quán)利要求1或2所述的聚類實現(xiàn)方法，其特征在于，所述步驟4中，當所述候選隊列中存在候選項樣本，所述主控節(jié)點在將每個候選樣本標記為屬于當前聚類之前，還合并由不同的計算節(jié)點存入到所述候選隊列中的相同樣本。

4.一種聚類實現(xiàn)方法，其特征在于，包括：

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

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

步驟3、每個所述計算節(jié)點根據(jù)分配的分塊樣本和設(shè)定的ε鄰域，分別統(tǒng)計每一個候選樣本的本地ε鄰域內(nèi)的樣本數(shù)量，并發(fā)送給合并節(jié)點；

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

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

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

5.如權(quán)利要求4所述的聚類實現(xiàn)方法，其特征在于，所述步驟6中，所述主控節(jié)點將所述候選隊列的每個候選樣本標記為屬于當前聚類之前，還合并由不同的計算節(jié)點存入到所述候選隊列中的相同樣本。