王利軍

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ù)信息讀取出來并存儲(chǔ)到內(nèi)存中，對(duì)事務(wù)數(shù)據(jù)信息包含的數(shù)據(jù)項(xiàng)進(jìn)行頻度統(tǒng)計(jì)和排序，對(duì)每一個(gè)事務(wù)中事務(wù)項(xiàng)按照從高到低的順序排序形成有序事務(wù)，根據(jù)最小支持度進(jìn)行刪除相應(yīng)的事務(wù)項(xiàng)，符合要求的事務(wù)項(xiàng)按照從高到低的順序從而生成項(xiàng)頭表L；第二次對(duì)數(shù)據(jù)庫D進(jìn)行掃描來構(gòu)建FP-tree[2]結(jié)構(gòu)；最后根據(jù)FP-tree結(jié)構(gòu)進(jìn)行頻繁模式[3]挖掘，獲取關(guān)聯(lián)規(guī)則。本文將對(duì)經(jīng)典的FP-growth數(shù)據(jù)挖掘算法進(jìn)行改進(jìn)，減少對(duì)事務(wù)數(shù)據(jù)庫的遍歷次數(shù)，從而提高FP-growth數(shù)據(jù)挖掘的效率。

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

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

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

參考文獻(xiàn)：

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

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

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

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

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