[發明專利]一種基于非易失性存儲器的頻繁模式挖掘方法

有效

• 申請號: 201710027657.0
• 申請日: 2017-01-16
• 公開（公告）號: CN106874396B
• 公開（公告）日: 2020-04-14
• 發明（設計）人: 劉鐸;林怡;黃鉑鈞;朱瀟;李陽
• 申請（專利權）人: 重慶大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2458
• 代理公司: 廣州三環專利商標代理有限公司 44202
• 代理人: 麥小嬋;郝傳鑫

1.一種基于非易失性存儲器的頻繁模式挖掘方法，其特征是，包括以下步驟：

步驟1、利用多核系統對頻繁模式樹進行并行構建

先將數據庫中的多條交易記錄大致均勻地分配到每個核中，在每一個核上構建一棵本地頻繁模式樹；包括：

依次掃描數據庫中的每一條交易記錄，獲得其中所包含的全部項的支持度計數，排除支持度計數值小于閾值的項，剩余的項即為頻繁項，對頻繁項按其支持度計數降序排列得到一個列表L；

創建頻繁模式樹的根結點T，以“null”標記；再次掃描數據庫，將讀取的每條交易記錄中的頻繁項選出并按L中的次序排序，排序后以null為根結點構建一條FP樹的路徑，只對路徑上位于最末的結點的計數加1，路徑上的其他結點的計數保持不變；

依次掃描完整個數據庫中所有交易記錄后獲得頻繁模式初始樹；

用深度優先搜索算法對所述頻繁模式初始樹依次進行遍歷，遍歷結點的計數器值為該結點本身的值加上其所有孩子結點的值，依次遍歷完所述頻繁模式初始樹之后，構建出完整的所述頻繁模式樹；

步驟2、對步驟1所構建的頻繁模式樹進行合并

將本地頻繁模式樹的信息搜集起來，合并成一棵大的全局頻繁模式樹；

在所述步驟1中，構建本地頻繁模式樹時，采用左孩子右兄弟鏈表結構，在構建所述頻繁模式初始樹過程中創建新節點時，為根結點T以下的孩子結點建立哈希表；在所述步驟2中，包括以下步驟：

步驟(1)、從根結點出發，將樹1的根結點的最末孩子結點的兄弟指針指向樹2的根結點的第一個孩子結點；

步驟(2)、利用所建立的哈希表查找樹1和樹2根結點的孩子結點中是否存在相同結點，如存在，用T1和T2分別表示樹1和樹2中相同的結點，然后執行步驟(3)；如不存在，則執行步驟(5)；

步驟(3)、T1計數域的值＝T1計數域的值+T2計數域的值，并將T2結點從該鏈表中刪除；

步驟(4)、將T1和T2分別作為樹1和樹2的根結點，返回步驟(1)；

步驟(5)、結束程序。