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

王利軍

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

關(guān)鍵詞：FP-growth；二維表；存儲數(shù)據(jù)

中圖分類號：TP393 文獻標(biāo)識碼：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

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

1算法改進：采用二維表[4]存儲數(shù)據(jù)

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

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

參考文獻：

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

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

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

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

【通聯(lián)編輯：光文玲】