[發明專利]數據流中帶權值頻繁項挖掘方法和系統

有效

• 申請號: 200910092805.2
• 申請日: 2009-09-08
• 公開（公告）號: CN101650730A
• 公開（公告）日: 2010-02-17
• 發明（設計）人: 張玉;張永錚
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京泛華偉業知識產權代理有限公司
• 代理人: 王 勇

1.一種數據流中帶權值頻繁項挖掘方法，數據流中的帶權值頻繁項動 態存儲在部分排序的流概要數據結構中；所述部分排序的流概要數據結構 包括多個按開始值順序排列的桶，所述桶還包括有由條目通過雙向循環鏈 表所構成的組；所述桶中的條目包括數據項名稱、計數器值以及計數器的 最大可能誤差，所述條目的計數器值大于所在桶的開始值而小于或等于所 在桶的開始值與桶范圍系數之和；該方法包括：

步驟1)、從所接收到的數據流中依次取出數據項，所述數據項包括數 據項名稱和數據項權值；

步驟2)、根據所取出的數據項的數據項名稱和數據項權值在所述的部 分排序的流概要數據結構中找出合適的桶以及合適的條目，并為所述條目 中的數據項名稱、計數器值以及計數器的最大可能誤差賦值；所述數據項 與條目間映射關系存放在哈希表中，空閑條目池用于維護空閑條目；該步 驟包括：

步驟2-1)、判斷所取出數據項的數據項名稱是否在所述哈希表中，若 不存在，執行下一步，否則，執行步驟2-4)；

步驟2-2)、從所述空閑條目池中取出一空閑條目，然后判斷該空閑條 目是否已經存在于所述哈希表中，若存在，則從哈希表中刪除該空閑條目 后，對該空閑條目賦值，否則，直接對該空閑條目賦值；其中，

對條目賦值包括：

令ID＝i，count_i＝ε_i+c；

所述的ID表示空閑條目的數據項名稱，所述的i表示所取出數據項的 數據項名稱，所述的ε_i代表所取出數據項i的條目的計數器的最大可能誤 差，j代表當前窗口的標識的變量，s代表窗口大小系數，r表示所述的桶 范圍系數，表示向下取整，count_i代表所取出數據項i的條目的計數 器值，c代表所取出數據項的數據項權值；

步驟2-3)、將賦值后的空閑條目的信息插入到所述哈希表，將賦值后 的空閑條目插入到所述的部分排序的流概要數據結構，然后執行步驟3)； 其中，將賦值后的條目插入到所述的部分排序的流概要數據結構包括：

步驟2-3-1)、判斷所述的部分排序的流概要數據結構是否為空，若為 空，創建一個新桶作為該部分排序的流概要數據結構的第一個桶，并將所 述賦值后的空閑條目插入到新創建桶的組內；若不為空，執行下一步；

所述新桶的開始值為其中，svalue代表桶的開始 值，r表示所述的桶范圍系數，表示向下取整，count_i代表所取出數 據項i的條目的計數器值；

步驟2-3-2)、從部分排序的流概要數據結構的第一個桶開始向后遍歷， 如果能夠找到一個滿足條件svalue＜count_i≤svalue+r的桶，則將賦值后的空閑 條目插入到該桶的組內，如果不能找到滿足前述條件的桶，則創建一個新 桶，然后將新桶插入到桶列表的正確位置，并將該條目插入新桶的組內； 所述新桶的開始值為

步驟2-4)、若所取出數據項所對應的條目在空閑節點池中，將該條目 從空閑節點池中刪除，然后為數據項所對應的條目賦值，將賦值后的條目 插入到所述的部分排序的流概要數據結構；

步驟2-5)、若所取出數據項所對應的條目不在空閑節點池中，從部分 排序的流概要數據結構中找出所取出數據項所對應的條目，修改所述條目 中的計數器值，并在修改后的計數器值超出所在桶的數值范圍的前提下， 將該條目轉移到新的桶中，然后執行步驟3)；其中，將條目轉移到新的桶 包括：

步驟2-5-1)、從所要移動條目當前所在的桶開始向后遍歷，判斷是否 能找到一個桶滿足svalue＜count_i≤svalue+r，若能，則執行下一步，否則，執 行步驟2-5-4)；其中，svalue代表桶的開始值，r表示所述的桶范圍系數， count_i代表所取出數據項i的條目的計數器值；

步驟2-5-2)、將所要轉移條目移動到滿足前述條件的桶中，并將該條 目從原先的桶中刪除；

步驟2-5-3)、若所要轉移條目原先所在的桶在刪除該條目后變為空， 則將該桶從桶列表中刪除，結束條目轉移操作；

步驟2-5-4)、創建一個新桶，然后將所創建的新桶插入到桶列表的正 確位置；所述新桶的開始值為

步驟2-5-5)、將所要轉移的條目移到到新創建桶的組內并將該條目 從原先的桶中刪除；

步驟2-5-6)、若所要轉移條目原先所在的桶在刪除該條目后變為空， 則將該桶從桶列表中刪除，結束條目轉移操作；

步驟3)、根據用戶的命令按序遍歷所述的部分排序的流概要數據結 構，所得到的計數器值大于一閾值的條目為所要挖掘的帶權值頻繁項；其 中，所述閾值為用戶支持度門限φ與所有數據項的權值總和N的乘積。