基于FP樹的最大頻繁項集挖掘

陳鳳娟

【摘要】頻繁項集的挖掘是數據挖掘中的一個基礎和核心問題，具有廣泛的應用領域。而頻繁項集挖掘可分為完全頻繁項集挖掘、頻繁閉項集挖掘和最大頻繁項集挖掘三類，其中，最大頻繁項集的數目最少。頻繁項集的挖掘是一個搜索問題，剪枝優化技術是提高頻繁項集挖掘效率的一個重要手段。對于最大頻繁項集的挖掘可以從寬度優先和深度優先兩個角度來考慮，而基于FP樹的深度優先算法比寬度優先算法掃描數據集的次數要少很多，因此，具有較好的性能。本文主要分析寬度優先的最大頻繁項集挖掘算法和基于FP樹的深度優先最大頻繁項集挖掘算法。

【關鍵詞】關聯規則;頻繁項集;最大頻繁項集;FP樹

1.引言

數據挖掘技術能從數據庫中智能地獲取有價值的知識和信息，是人工智能和數據庫等多個學科的重要研究內容。數據挖掘發展到現在，出現了許多技術分支和研究方向。應用不同的挖掘技術可以從數據庫中挖掘出不同類型的知識，根據挖掘出的知識不同的形式，可以把數據挖掘分為通用關聯規則挖掘、特征規則挖掘、分類挖掘、聚類挖掘、序列模式分析、時間序列分析、趨勢分析和偏差分析等類別。其中關聯規則挖掘及頻繁項集的挖掘是數據挖掘研究的核心內容之一，頻繁項集的挖掘效果對數據挖掘算法的性能和效率有重要的作用。

關聯規則是數據中一種簡單規則，這些規則能反映出實際的需求，是大量數據中項集之間相關聯系。關聯規則的挖掘算法是無監督學習的方法，其中，頻繁項集挖掘是關聯規則挖掘的第一步，也是關聯規則挖掘的關鍵步驟，是影響數據挖掘效率的關鍵問題。

本文主要分析頻繁項集與最大頻繁項集的概念，然后分析關聯規則中的最大頻繁項集挖掘的常用算法，并探討算法的優劣。

2.頻繁項集和最大頻繁項集

關聯規則挖掘的主要目的是確定數據集中不同屬性之間的聯系，從這種聯系中找出有價值的多個屬性之間的依賴關系，通過這種依賴關系給出決策支持。關聯規則的挖掘可以分成兩步來完成。第一步是按照用戶給定的最低閾值，識別出數據集中的所有頻繁項目集，第二步是從頻繁項目集中構造規則，要求構造的規則的可信度大于等于用戶設定的最低值。

設U={U1，U2，…，Un}為n個不同字符的集合，其中的字符稱為項或商品。任意一個集合XU稱為一個項集，若|X|=k，則稱X為k項集。事務（或交易）T是項的集合，且任意的TU，對應每一個事務有唯一的標識，記作TID。設A={T1，T2，…，Tn}，稱A為U上的交易集或者數據集，簡稱交易集或者數據集。如果XT，稱事務T包含X。對于一個項集X和一個交易集A，X在A中的支持度定義為X在A中的支持計數與A中總的交易個數之比，記作sup（X）。如果X的支持度大于某個給定的最小閾值，則稱X是頻繁的。

支持度是對關聯規則代表的重要性進行度量的指標，它體現了關聯規則的頻度。如果某個項集的支持度的值太小，則表明相應的規則很可能只是偶然發生的。

給定數據集A、項集X和min_sup，且min_sup∈（0，l），sup＼（XY）= 為項集X在數據集A上的支持度，簡記為sup（X）。當sup（X）≥min_sup時，項集X稱為A上的完全頻繁項集，簡稱為頻繁項集。頻繁項集挖掘就是要在事務數據庫里找出所有大于給定的最小支持度的頻繁項集。

數據集A上的頻繁閉項集定義為：若項集X滿足條件sup（X）≥min_sup且（YA∧XY→sup（Y）

項集X滿足條件sup（X）≥min_sup且（YA∧XY→sup（Y）

最大頻繁項集是指那些在所有的頻繁項集中不存在超集的頻繁項集。如果一個頻繁項集不是其它任何頻繁項集的真子項集，那么稱此頻繁項集為最大頻繁項集。由于最大頻繁項集的個數遠遠小于頻繁閉項集，更遠遠小于完全頻繁項集，所以挖掘最大頻繁項集可以有效縮小問題解的規模，給稠密集中的長頻繁模式挖掘提供了新的解決方案。

3.最大頻繁項集挖掘

如果X是一個頻繁項集，且X的任何一個超集都是非頻繁的，則X是最大頻繁項集。把所有的最大頻繁項集放入一個集合中，稱為最大頻繁項集的集合，即MFS（Maximum Frequent Sets）。如果X是最大頻繁項集，那么X的任何真子集都不是最大頻繁項集。從這個特性可知，在挖掘最大頻繁項集的過程中，最大頻繁項集所有的子集都可以不去挖掘，只需要挖掘最大頻繁項集就可以了，這樣能有效地縮短算法的運行時間，提高算法的運行效率。按遍歷搜索空間的策略，可以把最大頻繁項集挖掘算法分為寬度優先搜索和深度優先搜索兩類算法。

Pincer-search算法是典型的采用寬度優先搜索策略的算法，它使用傳統的橫向數據集的表示方法，通過多次遍歷數據集來計算各個項集的支持度計數。該算法把自頂向下的搜索策略與由底向上的搜索策略結合起來，使用兩種策略同時對數據空間進行搜索。其中，由底向上的搜索方法與Apriori算法的方法相似，先掃描數據集k次生成的k階頻繁項集，用k階頻繁項集來生成k+l階侯選項集，再掃描數據集，計算候選項集的支持度計數，并將候選項集分為k+1項頻繁項集和k+1項非頻繁項集。Pincer-search算法利用兩個不同方向搜索生成的非頻繁項集和最大頻繁項集相互剪枝，不斷重復剪枝動作，直到兩個不同方向的搜索過程發現的頻繁項集一致時為止。通過互相剪枝，可以迅速降低搜索空間，提高挖掘效率，但算法需要多次遍歷數據集，并計算項集的支持度，還會產生過多的無用的候選項集，對海量數據算法效率會急劇下降。

Max-Miner算法也是采用寬度優先搜索策略，它利用子集剪枝策略對候選項集進行剪枝，又利用超集剪枝策略對非最大頻繁項集進行剪枝。Max-Miner提出的利用尾項集按項支持度從低到高的排序方法，不但提高了超集剪枝策略的效率，還被廣泛地應用在其他的最大頻繁項集挖掘算法中。Max-Miner算法根據提出的搜索空間樹概念，盡可能早地對項目集進行剪枝，有效地縮小了搜索空間。但是，由于Max-Miner算法也是橫向的寬度優先策略，所以它也需要多次掃描數據集，降低了算法的效率。

4.基于FP樹的最大頻繁項集挖掘

FP-Max算法是一種基于FP-Tree的最大頻繁項集挖掘算法，它是一種使用深度優先搜索策略的有效算法。FP-Max算法在深度優先遍歷搜索空間樹時，對于數據集，建立其FP樹，對于每個結點，還保存該結點到根結點搜索路徑上的每一個結點對應的FP子樹。這些FP子樹表示與相關結點挖掘有關的頻繁信息。在當前結點上，通過在相應項集之中添加對應的FP子樹頭表中的某個項，來生成搜索空間中的子結點。

在構建子結點的FP子樹之前做，先對其進行超集是否存在的判斷，如果在已有最大頻繁項集的集合中，存在首尾項集并集的超集，則進行前瞻剪枝;否則，創建子結點FP子樹，遞歸調用算法在該子結點上進行挖掘，直至某個子孫結點的FP子樹是單路徑樹。當某個節點的子FP樹為單一路徑樹時表明，該節點對應項集與子FP樹的頭表項集的并集，為最大頻繁項集，將其加入最大頻繁項集樹中。最大頻繁項集樹是FP-Max算法用來壓縮保存已經產生的最大頻繁項集的存儲結構。它的結構與FP樹的結構一樣，都包含頭表和樹結構，從某個葉節點到根節點的路徑代表一個最大頻繁項集。

FP-Max算法只需要在構建FP樹時，對事務數據庫進行兩次掃描，在挖掘過程中，該算法不會產生候選項集，但會產生一些候選最大頻繁項集。因此FP-Max算法在一定程度上減少了 I/O開銷，提高了算法的挖掘效率。但是FP-Max算法也有一些不足之處，首先，為了有效的進行前瞻剪枝，該算法需要在最大頻繁項集樹中查詢超集，就需要將給定項集集合中每一個項集與被檢測項集做項匹配，使得超集存在判斷的開銷較大。其次，該算法會構建大量的條件模式樹，在某些存在大量的長模式以及強模式的數據集中，構建FP樹的工作量非常大，而節點鏈的復雜度將增加數據結構的復雜性。最后，FP-Max算法是基于雙向FP樹結構的，就導致存儲FP樹需要其他單向FP樹的兩倍的存儲空間，因此，FP樹的存儲也會占用大量的內存空間。

5.結束語

在關聯規則挖掘、序列模式挖掘、多層模式挖掘等數據挖掘問題中，挖掘頻繁項集既是基本步驟，也是關鍵步驟。最大頻繁項集比頻繁項集的數量少，在某些挖掘中，挖掘最大頻繁項集可以有更好的算法效率。最大頻繁項集挖掘算法按對搜索空間樹的遍歷策略可以分為兩種，分別是寬度優先算法和深度優先算法。Pincer-search算法和Max-Miner算法是寬度優先算法，而FP-Max算法是基于FP樹的深度優先算法，對這幾個算法的分析和研究對以后的最大頻繁項集挖掘算法的改進有很大的幫助。

參考文獻

[1]李慶華，王卉等.挖掘最大頻繁項集的并行算法[J].計算機科學，2004，31（12）：132-134.

[2]吳振光.一個改進的關聯規則的頻繁項目集數據挖掘算法[J].科學，2007，34（9）：145-147.

[3]陳晨，鞠時光.基于改進FP-tree的最大頻繁項集挖掘算法[J].計算機工程與設計，2008，29（24）：6236-6239.

[4]王丹陽，田衛東.一種有效的并行頻繁項集挖掘算法[J].計算機應用研究，2008，25（11）：3332-3334.

[5]花紅娟，張健，陳少華.基于頻繁模式樹的約束最大頻繁項集挖掘算法[J].計算機工程，2011，37（9）：78-80.

[6]廖福榮，王成良.基于有序FP-tree的最大長度頻繁項集挖掘算法[J].計算機工程與應用，2012，48（30）：147-150.

[7]劉芝怡，常睿.頻繁項集高效挖掘算法研究[J].微計算機信息，2012，28（10）：491-493.