向春梅 陳超

摘要：近年來數(shù)據(jù)庫信息越來越龐大，利用已有的算法來快速挖掘頻繁項集已經(jīng)變得越來越困難。為了解決這個問題，論文提出一種挖掘頻繁項集的新算法。該算法首先需要為每一個項目設(shè)定一個不重復(fù)的優(yōu)先級，然后采用最小優(yōu)先級樹堆的數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)庫中的每條事務(wù)，最后，從最小優(yōu)先級樹堆中尋找數(shù)據(jù)庫中的各種頻繁項集。通過實驗測試，在相同的支持度下，使用該算法來挖掘頻繁項集的運行效率的確比Apriori算法和FP-growth算法的運行效率要高。

關(guān)鍵詞：數(shù)據(jù)挖掘;關(guān)聯(lián)規(guī)則;頻繁項集;樹堆; Apriori ;FP-growth

中圖分類號：TP312? ? ? 文獻標識碼：A? ? ? 文章編號：1009-3044（2019）03-0026-03

Abstract： In recent years， database information has become more and more huge. It is more and more difficult to use the existing algorithms to quickly mine frequent items.In order to solve this problem， the paper proposes a new algorithm for mining frequent items.First， the algorithm needs to set a non-repetitive priority for each item. Second， the data structure of the minimum priority tree-heap is used to store each transaction in the database， and finally， the minimum priority tree-heap is looked for various frequent items in the database.Under the same support threshold，the experiments show that using the algorithm to mine the frequent item sets is more efficient than the Apriori algorithm and the FP-growth algorithm.

Key words： data mining; association rules; frequent items; tree-heap; Apriori; FP-growth

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘研究領(lǐng)域的一個重要研究方向[1]，其目的是為了從大量數(shù)據(jù)中發(fā)現(xiàn)項與項之間的關(guān)聯(lián)關(guān)系。傳統(tǒng)的關(guān)聯(lián)規(guī)則采用的是支持度—置信度框架，前者用于衡量關(guān)聯(lián)規(guī)則在整個數(shù)據(jù)集中的統(tǒng)計重要性，后者用于衡量關(guān)聯(lián)規(guī)則的可信程度。一般來說，只有支持度和置信度均較高的關(guān)聯(lián)規(guī)則才可能是用戶感興趣、有用的關(guān)聯(lián)規(guī)則[2]。關(guān)聯(lián)規(guī)則的挖掘可以分成兩個部分來實現(xiàn)[3]：挖掘數(shù)據(jù)庫中的頻繁項集以及從頻繁項集中挖掘關(guān)聯(lián)規(guī)則。在上面的兩個步驟中，算法的總體性能主要由第一個部分決定[4]。因此，論文主要研究頻繁項集的挖掘。

Apriori[5]算法是Agrawal等人首次提出的針對關(guān)聯(lián)規(guī)則挖掘問題的算法。該算法采用廣度優(yōu)先的搜索策略，自頂向上的遍歷思想，先產(chǎn)生候選集后獲得頻繁項集的思路。其缺點是多次掃描數(shù)據(jù)庫，會增大IO負載;會產(chǎn)生大量不需要的候選頻繁項集[6-8]。FP-growth[9]算法是由Jiawei Han等人提出的不產(chǎn)生候選集的挖掘頻繁項集的算法。該算法的思路也可以分為兩個部分[10]：構(gòu)造FP-tree和通過FP-tree挖掘頻繁項集。雖然該算法只需要掃描兩次數(shù)據(jù)庫，并且不產(chǎn)生候選集，但是當(dāng)數(shù)據(jù)庫很大時，構(gòu)造基于內(nèi)存的PF-tree也是不現(xiàn)實的[11]。因此論文提出一種新的挖掘頻繁項集的算法記為MiningByTreap 算法，該算法不產(chǎn)生候選項集，也不會存在無法構(gòu)建樹堆的情況。

1 MiningByTreap 算法

樹堆是一種同時具有樹和堆兩種特性的數(shù)據(jù)結(jié)構(gòu)。樹堆中的節(jié)點包含兩部分，數(shù)據(jù)值x和屬于該節(jié)點的唯一的優(yōu)先級p。樹堆的節(jié)點有兩個特性，對于數(shù)據(jù)值x而言，它遵循二叉查找樹的屬性，根節(jié)點數(shù)據(jù)值大于左子樹的所有節(jié)點且小于右子樹的所有節(jié)點;對于優(yōu)先級而言，它遵循堆的屬性，根節(jié)點的優(yōu)先級大于左右子樹中所有節(jié)點。就堆的數(shù)據(jù)結(jié)構(gòu)而言，根據(jù)每個節(jié)點與其子節(jié)點的大小關(guān)系，可以分為大頂堆和小頂堆，所以樹堆也可以根據(jù)每個節(jié)點優(yōu)先級與其子節(jié)點的優(yōu)先級的大小關(guān)系，分為最大優(yōu)先級樹堆和最小優(yōu)先級頂樹堆[12]。

論文選擇最小優(yōu)先級樹堆作為研究的數(shù)據(jù)結(jié)構(gòu)，提出的算法由三個主要的程序構(gòu)成，首先通過計算優(yōu)先級的子程序計算出數(shù)據(jù)庫中每個變量的優(yōu)先級。計算好優(yōu)先級之后，通過創(chuàng)建樹堆的子程序為每條事務(wù)創(chuàng)建一個樹堆。最后，通過挖掘頻繁項集的子程序，采用前序遍歷的方法遍歷樹堆，從而找出頻繁項集。論文以表1展示的數(shù)據(jù)作為研究對象，逐步闡述論文提出的算法過程。

1.1 計算優(yōu)先級

在數(shù)據(jù)庫中，即使項目集不是頻繁的，但在規(guī)則生成中它可能也具有一定的重要性。在所有關(guān)聯(lián)算法中，這種不頻繁的項目往往被省略并沒有給出很多地分析。在計算優(yōu)先級的算法中，首先找到所有項目的頻率以確定該項目的優(yōu)先級。如果只著眼于需要的高頻繁項集，在后續(xù)挖掘規(guī)則時，可以根據(jù)最小支持度閾值，得到滿足要求的頻繁項集。當(dāng)然也可以選擇挖掘出所有的項集最優(yōu)的組合。算法1是計算優(yōu)先級的過程。

算法1：

輸入：數(shù)據(jù)庫D，包含n個不同項目和m條事務(wù)。

輸出：具有n個項目及其優(yōu)先級的Map集合。

步驟1：掃描數(shù)據(jù)庫D并找出每個項目的頻率f;

步驟2：將每個項目按照頻率f依次增的順序排列，并存入數(shù)組L[n];

步驟3：將每個項目及其所在數(shù)組L[n]中的下標位置加1后，存入Map集合。

經(jīng)過算法1后，可以得到每個項目的頻率f和優(yōu)先級數(shù)p，如表2所示。

1.2 構(gòu)建最小優(yōu)先級樹堆

論文使用的是最小優(yōu)先級樹堆的數(shù)據(jù)結(jié)構(gòu)。它滿足每個節(jié)點的優(yōu)先級都比它的子節(jié)點的優(yōu)先級小的特點，在此條件下再保證，滿足每個節(jié)點數(shù)據(jù)值大于它左子節(jié)點且小于右子節(jié)點，這種特性相當(dāng)于將樹堆中的左右節(jié)點也做了排序[9]。

構(gòu)建這種最小優(yōu)先級樹堆的程序必須是在每個項目的優(yōu)先級已經(jīng)確定的情況下才能執(zhí)行。算法需要給定最小支持度閾值，將滿足要求的節(jié)點按照其優(yōu)先級大小構(gòu)建最小優(yōu)先級樹堆。如果是挖掘所有項目集，可以將最小支持度閾值設(shè)為1，為了滿足所構(gòu)建的最小優(yōu)先級樹堆具有更低的深度，算法每次添加一個新節(jié)點是以完全二叉排序樹進行存儲，然后對該節(jié)點按照節(jié)點的優(yōu)先級滿足小頂堆的屬性進行調(diào)整，最終得到的最小優(yōu)先級樹堆。算法2是構(gòu)建樹堆的過程。

算法2：

輸入：具有n個項目及其優(yōu)先級的Map集合，最小支持度閾值

輸出：最小優(yōu)先級樹堆的List集合

步驟1：遍歷每條事務(wù)中每個項目節(jié)點，如果滿足最小支持度閾值則調(diào)用insert函數(shù)，添加該節(jié)點，創(chuàng)建一個完全二叉樹;

步驟2：對每個完全二叉樹的每個節(jié)點按照該節(jié)點的優(yōu)先級進行調(diào)整;

步驟3：遞歸調(diào)整該節(jié)點的子節(jié)點;

步驟4：依次調(diào)整，直至調(diào)整到根節(jié)點;

步驟5：返回最小優(yōu)先級樹堆T。

設(shè)定minSupport=10%，算法2為每條事務(wù)創(chuàng)建一個最小優(yōu)先級樹堆，如圖1所示。其中T300中的A頻率為1，項目總數(shù)為17，經(jīng)過計算可得，只有項目頻率超過1才滿足最小支持度閾值，所以節(jié)點A不會被加入最小優(yōu)先級樹堆中。

1.3 挖掘頻繁項集

由于算法2中已經(jīng)對最小支持度閾值并做出了相應(yīng)的處理，因此在挖掘頻繁項的算法中不需要輸入最小支持度閾值。算法3采用前序遍歷、自下而上地搜索頻繁項集，直到離開節(jié)點并返回優(yōu)先級值和其節(jié)點數(shù)據(jù)值。算法返回節(jié)點的父節(jié)點和兄弟節(jié)點。如果沒有兄弟節(jié)點，則返回父節(jié)點和父節(jié)點的兄弟幾點，依次類推，一直搜索到根節(jié)點，程序結(jié)束。

算法3：

輸入：最小優(yōu)先級樹堆T

輸出：頻繁項集F

步驟1： 前序遍歷直到T中葉子節(jié)點的最左節(jié)點N;

步驟2：如果N節(jié)點存在兄弟節(jié)點則返回N節(jié)點的兄弟節(jié)、N節(jié)點和N節(jié)點的父節(jié)點，并加入頻繁項集F中;

步驟3：如果N節(jié)點沒有兄弟節(jié)點，則返回N節(jié)點的父節(jié)點 的兄弟節(jié)點、N節(jié)點和N節(jié)點的父節(jié)點，并加入頻繁項集F中;

步驟4：直到節(jié)點已經(jīng)是根節(jié)點時，結(jié)束程序，返回頻繁項集F。

通過算法3，得到頻繁項集F，如表3所示：

2 算法測試

為檢驗論文提出的算法的性能，將其與Apriori算法和FP-growth算法進行比較。實驗環(huán)境：CPU為Intel Celeron 1.80GHz、內(nèi)存4GB和Windows 7 家庭普通版操作系統(tǒng)。算法采用Java語言編寫，在Eclipse開源軟件上編譯，分別實現(xiàn)了Apriori、FP-growth和Threap-mining三種算法，測試數(shù)據(jù)是從http：//fimi.ua.ac.be/data/上下載的四種數(shù)據(jù)。通過對不同數(shù)據(jù)進行實驗分析及測試，得到實驗的結(jié)果如表4所示。分析表4可得，在相同支持度下，同一數(shù)據(jù)中，使用MiningByTreap 算法挖掘頻繁項的效率更高。同時測試了在同一數(shù)據(jù)不同支持度下使用論文提出的算法進行挖掘頻繁項，實驗結(jié)果如表5所示。分析表5可得，MiningByTreap 算法在支持度較小時挖掘效率依然很高。

3 結(jié)束語

本文提出的利用最小優(yōu)先級樹堆來挖掘頻繁項集的算法，在不同大小的數(shù)據(jù)上應(yīng)用均可得到相對其他算法更高的效率，而且可以快速地挖掘支持度較小的頻繁項集。同時，該算法還可以有效地挖掘非頻繁項集。

參考文獻：

[1] 穆罕默德·扎基，小瓦格納·梅拉.數(shù)據(jù)挖掘與分析：概念與算法[M].吳誠堃，譯.北京：人民郵電出版社，2017.

[2] 張全紅.面向大數(shù)據(jù)的關(guān)聯(lián)規(guī)則算法研究[D]. 西安：西安科技大學(xué)，2017.

[3] 張健.關(guān)聯(lián)規(guī)則中頻繁與高效用項集挖掘算法研究[D].廈門：華僑大學(xué)，2017.

[4] 孫金鑫.數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則的研究[J].智能計算機與應(yīng)用，2018，8（3）：132-135.

[5] 潘燕.關(guān)聯(lián)規(guī)則下的數(shù)據(jù)挖掘算法分析[J].信息記錄材料，2018，19（7）：212-213.

[6] 王國胤，劉群.大數(shù)據(jù)挖掘及應(yīng)用[M].北京：清華大學(xué)出版社，2017.

[7] Dong Juan Gu，Lei Xia. A Novel and Improved Apriori Algorithm[J]. Applied Mechanics and Materials，2015，3748（721）.

[8] 王建明，袁偉.基于節(jié)點表的FP-Growth算法改進[J].計算機工程與設(shè)計，2018，39（1）：140-145.

[9] Chien-Hua Wang，Li Zheng，Xuelian Yu，XiDuan Zheng. Using Fuzzy FP-Growth for Mining Association Rules[P]. 2017 International Conference on Organizational Innovation （ICOI 2017），2017.

[10] 何恒松，李文明，李文峰.基于FP增長的數(shù)據(jù)關(guān)聯(lián)改進算法[J].電子測量技術(shù)，2017，40（9）：58-64.

[11] Yi Zeng，Shiqun Yin，Jiangyue Liu，et al. Gendelman. Research of Improved FP-Growth Algorithm in Association Rules Mining[J]. Scientific Programming，2015，2015.

[12] Mark Allen Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析：Java語言描述 [M].馮舜璽，譯.北京：機械工業(yè)出版社 ，2016.

【通聯(lián)編輯：謝媛媛】