[發明專利]數據關聯規則挖掘實現方法與系統

有效

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

1.一種數據關聯規則挖掘實現方法，其特征在于，包括：

主控節點對數據記錄進行分塊，將分塊數據記錄分配并分發給至少兩個計算節點；

每個所述計算節點并行對分配的每條分塊數據記錄中包含的每個數據項，分別統計本地出現次數，并發送統計出的每個數據項的本地出現次數給第一類合并節點；

所述第一類合并節點累計每個所述計算節點發送的每個數據項的本地出現次數，得到每個數據項的總出現次數，并確定出總出現次數大于設定的支持度閾值的對應數據項為頻繁1-項集，并發送頻繁1-項集及對應的總出現次數給每個所述計算節點；

每個所述計算節點按總出現次數由大到小的順序排序各頻繁1-項集，對分配的每條分塊數據記錄中包含的數據項，按照排序后的各頻繁1-項集的順序進行排序，并刪除每條記錄中包含的非頻繁1-項集數據項，得到對應的每條處理后記錄；以及

每個所述計算節點對每條處理后記錄，分別以包含的每個頻繁1-項集為終止數據項，以該條處理后記錄包含的首個頻繁1-項集為起始數據項，得到由該條處理后記錄生成的全部子數據項串；并分別統計每個子數據項串的本地出現次數，將本地的每個子數據項串及對應的本地出現次數發送給第二類合并節點；

所述第二類合并節點累計每個所述計算節點發送的每個子數據項串的本地出現次數，得到每個子數據項串的總出現次數；并根據每個子數據項串及其總出現次數，構建對應的頻繁模式FP子樹，發送給所述主控節點或第三類合并節點；以及

由所述主控節點或所述第三類合并節點合并各FP子樹，得到全局FP樹，再根據得到的全局FP樹挖掘關聯規則。

2.如權利要求1所述的方法，其特征在于，所述第一類合并節點至少包括兩個；由所述主控節點預先分配每個第一類合并節點進行合并的對應數據項；

每個所述計算節點發送統計出的每個數據項的本地出現次數給第一類合并節點，具體包括：

每個所述計算節點根據每個第一類合并節點進行合并的對應數據項，將本地統計出的相應數據項的本地出現次數，上報給對應的第一類合并節點；或者

每個第一類合并節點根據自身進行合并的對應數據項，分別向每個所述計算節點請求上傳所述對應數據項的統計信息；每個所述計算節點向每個所述第一類合并節點返回其請求的所述對應數據項的本地出現次數。

3.如權利要求2所述的方法，其特征在于，所述第二類合并節點至少包括兩個；由所述主控節點預先分配每個第二類合并節點進行合并的對應子數據項串；

每個所述計算節點將本地的每個子數據項串及對應的本地出現次數發送給第二類合并節點，具體包括：

每個所述計算節點根據每個第二類合并節點進行合并的對應子數據項串，將本地統計出的相應子數據項串的本地出現次數，上報給對應的第二類合并節點；或者

每個第二類合并節點根據自身進行合并的對應子數據項串，分別向每個所述計算節點請求上傳所述對應子數據項串的統計信息；每個所述計算節點向每個所述第二類合并節點返回其請求的所述對應子數據項串的本地出現次數。

4.如權利要求3所述的方法，其特征在于，當由第三類合并節點進行FP子樹合并時，所述第三類合并節點由至少兩個子樹合并分節點和一個子樹合并總節點組成；由所述主控節點預先分配每個子樹合并分節點進行合并的至少兩個對應FP子樹，并通知所述第二類合并節點；

所述第二類合并節點構建繁模式FP子樹，并發送給第三類合并節點，具體包括：

每一個第二類合并節點根據每個子樹合并分節點進行合并的對應FP子樹，將本地構建的對應FP子樹發送給進行合并的對應的子樹合并分節點；每個子樹合并分節點進行子樹合并后，傳送給所述子樹合并總節點。