基于FP—growth的頻繁模式挖掘算法的改進

王利軍

摘要：經典的FP-growth數據挖掘需要兩次遍歷數據庫，為了提高挖掘效率和減少遍歷數據庫的次數，本人提出一種采用二維表存儲數據的方案，處理后的二維表中存儲著刪除了非頻繁項和排完序的事務，可以為后續建FP-tree結構提供數據。

關鍵詞：FP-growth；二維表；存儲數據

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2019）04-0012-02

Abstract：The classical FP-growth data mining needs to traverse the database twice. In order to improve the efficiency of mining and reduce the number of times traversing the database， I propose a scheme of using atwo-dimensional table to store data. This table stores deleted infrequent items and arranged transactions， which can provide data for buildingFP-treestructure.

Key words： FP-growth； two-dimensional table； storage data

經典的FP-growth[1]數據挖掘主要包括如下步驟：首先遍歷事務數據庫D，并將數據庫中事務數據信息讀取出來并存儲到內存中，對事務數據信息包含的數據項進行頻度統計和排序，對每一個事務中事務項按照從高到低的順序排序形成有序事務，根據最小支持度進行刪除相應的事務項，符合要求的事務項按照從高到低的順序從而生成項頭表L；第二次對數據庫D進行掃描來構建FP-tree[2]結構；最后根據FP-tree結構進行頻繁模式[3]挖掘，獲取關聯規則。本文將對經典的FP-growth數據挖掘算法進行改進，減少對事務數據庫的遍歷次數，從而提高FP-growth數據挖掘的效率。

1算法改進：采用二維表[4]存儲數據

本文以實例的方式進行闡述，設置最小支持度計數為2，為了減少對數據庫的遍歷次數可以在第一次對事務數據庫D如表1所示進行掃描時，發現存在14個事務項，分別為A，B，C，D，E，F，G，I，J，O，P，L，M，N，為了使用二維表保存所有事務的信息，二維表中的行代表事務項，二維表中的列代表事務，事務項在事務中出現，則將對應的單元格的值修改為1，如表2所示，對所生成的二維表統計每行1的個數就是該事務項的支持度計數，根據各事務項的支持度計數按照從高到低進行排序，刪除低于最小支持度計數的事務項，本案例中刪除事務項O，P，I，J，L，M，N行，刪除這些行時即對每一個事務中小于最小支持度計數的項進行了刪除，后期編程第一次遍歷事務數據庫存儲數據時采用動態數組，當進行了事務項刪除后即可釋放這些空間，以達到空間最優化，排序后的二維表如表3所示，保留下來的事務項和各自行1的個數即可確定項頭表L中事務項名和支持度計數如表4所示，每一個事務已進行了刪減和排序，縱向查看事務信息即可得到刪除和排序后事務信息，如T001的事務信息為1110101，代表{A，C，E，B，F}，后期創建FP-tree結構直接根據排序后的二維表數據即可，無須再次遍歷事務數據庫，減少對數據庫的遍歷次數可以節省時間。

總之，采用二維表存儲數據的方案在整個挖掘過程只需要遍歷一次事務數據庫D，從而達到減少掃描事務數據庫D的次數，利用該二維表可以快速排序每個事務并刪除了非頻繁項，快速生成FP-tree的項頭表，從而提高后續的建樹效率。

參考文獻：

[1] 唐穎峰，陳世平.一種基于后綴項表的并行閉頻繁項集挖掘算法[J].計算機應用研究，2014.

[2] 尹治華，等.一種改進的基于FP-Tree的高效挖掘最大頻繁項目集算法[J].濟南大學學報（自然科學版） ，2017.

[3] 邢長征.垂直數據格式挖掘頻繁項集算法的改進[J].計算機工程與科學，2017.

[4] 葉福蘭.基于FP-tree的最大頻繁模式挖掘算法的改進[J].成都大學學報（自然科學版），2014.

【通聯編輯：光文玲】