基于樹堆的頻繁項集挖掘算法

向春梅 陳超

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

關鍵詞：數據挖掘;關聯規則;頻繁項集;樹堆; 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

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

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

1 MiningByTreap 算法

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

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

1.1 計算優先級

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

算法1：

輸入：數據庫D，包含n個不同項目和m條事務。

輸出：具有n個項目及其優先級的Map集合。

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

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

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

經過算法1后，可以得到每個項目的頻率f和優先級數p，如表2所示。

1.2 構建最小優先級樹堆

論文使用的是最小優先級樹堆的數據結構。它滿足每個節點的優先級都比它的子節點的優先級小的特點，在此條件下再保證，滿足每個節點數據值大于它左子節點且小于右子節點，這種特性相當于將樹堆中的左右節點也做了排序[9]。

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

算法2：

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

輸出：最小優先級樹堆的List集合

步驟1：遍歷每條事務中每個項目節點，如果滿足最小支持度閾值則調用insert函數，添加該節點，創建一個完全二叉樹;

步驟2：對每個完全二叉樹的每個節點按照該節點的優先級進行調整;

步驟3：遞歸調整該節點的子節點;

步驟4：依次調整，直至調整到根節點;

步驟5：返回最小優先級樹堆T。

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

1.3 挖掘頻繁項集

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

算法3：

輸入：最小優先級樹堆T

輸出：頻繁項集F

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

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

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

步驟4：直到節點已經是根節點時，結束程序，返回頻繁項集F。

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

2 算法測試

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

3 結束語

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

參考文獻：

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

[2] 張全紅.面向大數據的關聯規則算法研究[D]. 西安：西安科技大學，2017.

[3] 張健.關聯規則中頻繁與高效用項集挖掘算法研究[D].廈門：華僑大學，2017.

[4] 孫金鑫.數據挖掘中的關聯規則的研究[J].智能計算機與應用，2018，8（3）：132-135.

[5] 潘燕.關聯規則下的數據挖掘算法分析[J].信息記錄材料，2018，19（7）：212-213.

[6] 王國胤，劉群.大數據挖掘及應用[M].北京：清華大學出版社，2017.

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

[8] 王建明，袁偉.基于節點表的FP-Growth算法改進[J].計算機工程與設計，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增長的數據關聯改進算法[J].電子測量技術，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.數據結構與算法分析：Java語言描述 [M].馮舜璽，譯.北京：機械工業出版社 ，2016.

【通聯編輯：謝媛媛】