一種新的頻繁項集挖掘算法

摘 要：首先對傳統集合操作進行了擴展，提出基于擴展集合操作的最大頻繁項集生成算法FIS-ES，并從理論和實驗上對算法的復雜度進行了詳細的分析。實驗表明，在最小支持度較小的情況下，FIS-ES比Apriori算法具有更快的挖掘速度、更少的空間占用等優點，與Apriori有很好的互補性。

關鍵詞：擴展集合操作； 關聯規則； FIS-ES算法

中圖法分類號：P208； TP393文獻標識碼：A

文章編號：1001—3695(2007)02—0017—03

關聯規則的挖掘分為兩步[1，7]：首先找出滿足最小支持度要求的頻繁項集；然后根據頻繁項集生成滿足最小置信度要求的關聯規則集。其中，第二步比較成熟，挖掘關聯規則的總體性能則由第一步決定。經典頻繁項集挖掘算法Apriori[1，2]的主要問題是由于多次重復掃描而帶來的I/O 代價過高， 因此， 之后的研究提出了許多減少數據庫掃描次數的方法， 比較有代表性的是分塊、采樣等[2—6]。近年來， 通過減少項目集的搜索空間來減少數據庫的掃描次數已經被廣泛研究，典型的代表有Han 提出的FP-增長算法[4]。該方法不用候選頻繁集，而是通過狀態樹記錄掃描信息，一次掃描數據庫生成頻繁項集。本文算法將利用擴展后的集合操作，通過一次掃描數據庫，逐步生成最終的最大頻繁項集。

1 基本概念

定義1（集合上的亞操作）[8] 設S₁和S₂是定義在相空間上的兩個項目集，I是定義在相空間上的一個項。定義如下操作：

2 基于擴展集合操作的頻繁項集挖掘算法（FIS-ES）

2.1 理論依據

FIS-ES算法與Apriori算法具有相同的理論依據，即Apriori性質：頻繁項集的所有非空子集也都必須是頻繁的，算法均使用了頻繁項集性質的先驗知識，只是使用的方向不同。Apriori性質屬于一種反單調的分類。如果一個集合不能通過測試，則它的所有超集也都不能通過相同的測試。基于此，Apriori算法使用逐層搜索的迭代方法，頻繁K-1項集通過與自身連接生成候選的K項集，再對候選的K項集進行剪枝，保留滿足最小支持度要求的項，以壓縮搜索空間。如此反復，直到不能找到頻繁K項集為止。

Apriori性質同時還表明，如果一個集合通過了測試，則它的所有子集也都能通過相同的測試。FIS-ES算法正是基于此性質。算法逐個讀取數據庫中的記錄，并考查當前是否有符合最小支持度要求的頻繁項，如果有，則刪除該頻繁項的真子集，重復該操作直到數據庫中的記錄全部讀完為止。該算法通過只保留最大的頻繁項集來達到壓縮搜索空間、提高效率的目的。FIS-ES算法與Apriori算法的另一個不同之處是，FIS-ES只需掃描一次數據庫，而Apriori算法的每一層搜索都需要掃描一次數據庫。當數據庫較大，不能一次放入內存時，多次重復的I/O操作會嚴重影響Apriori算法的效率。

2.2 三個基本函數

數據庫每個記錄的掃描可以看作是新的項目加入項集的過程，這一工作可以通過項集的并操作來完成。為了方便，通常使用支持數N_ms代替支持度P_ms，即以該項在數據庫中的出現次數來進行相關討論。

2.3 最大頻繁項集的挖掘算法 

基于擴展集合操作的關聯規則挖掘算法在內存中建立了兩個線性數據結構S和S^*，S存儲從數據庫掃描中得到的項，S^*存儲生成的頻繁項集，它們的元素隨著項的增加和裁減而變化。基于擴展集合操作的最大頻繁項集的生成算法FIS-ES如下。

2.4 FIS-ES算法執行示例

對于包含項｛ABCD，BCE，ABCE，BDE，ABCD｝的事務數據庫，我們跟蹤FIS-ES算法的執行。表1給出了FIS-ES對它的處理過程(假設Pms=40%，則Nmin=2)

2.5 FIS-ES算法分析

2.5.1 空間與時間復雜度的理論分析

假定NT為事務數據庫中項的個數，NI為項目空間大小，LMI為事務數據庫中最長項的長度，NDI為事務數據庫中所包括的不同項數目。

FIS-ES算法在空間上的代價主要是項集S、頻繁項集S^*及MakeFre中I的所有子集的存儲。FIS-ES算法的時間和空間效率的理論分析如下。

2.5.2 實驗結果分析 

本節通過三組試驗對以下三個因素進行測試。試驗是在Celeron 1.7GHz/256MB RAM的PC上進行的，試驗用的數據庫是隨機產生的項，其中的項均以大寫英文字母標志。FIS-ES算法的可用性取決于以下幾個因素：

（1）空間占用試驗

本試驗描述在不同事務數據庫容量下，FIS-ES算法中的空間占用情況。圖1和圖2顯示了LMI=8，NI=10，最小支持度Pms=0.05時的實驗結果。

如圖1所示，隨著數據量的增大，S^*保持平穩，即使在數據隨機的情況下，S^*也會遠小于它的理論值；而S的空間復雜度呈現O(log NT)的趨勢，不會發生膨脹的指數增長結果。另外，由于數據是隨機產生的，因此項重復的可能性較小（選擇最小支持度較小，也是這個原因），如果項的重復性大，S的空間占用會有下降的趨勢。

（2）時間占用試驗

本試驗描述在不同事務數據庫容量下，FIS-ES算法的時間占用情況。圖2給出了隨著數據庫容量增大，FIS-ES算法的時間攀升趨勢。從圖2可以看出，FIS-ES算法的執行時間呈線性增長，遠小于理論上限值。

（3）FIS-ES與Apriori算法的對比試驗

①時間/空間占用隨項數目的變化

圖3是在LMI=8，NI=10，最小支持度Pms=0.005時，兩種算法時間占用和空間占用情況的比較。結果表明，在最小支持度比較低的情況下，FIS-ES的時間和空間占用要比Apriori要少。

②時間/空間占用隨最小支持度的變化

圖4是在NT=4K，LMI=8，NI=10的條件下，兩種算法的時間和空間占用隨最小支持度變化的情況。

如圖4所示，隨著最小支持度的降低，FIS-ES算法的時間和空間占用呈下降趨勢，而Apriori算法則呈上升趨勢。因為最小支持下降，Apriori中的候選項目集會指數增加，從而導致時間和空間占用急劇加大。相反，FIS-ES算法在最小支持度降低時，最大頻繁項集中項目的長度增加、數據增多，從而S中的項目因裁減得越來越多，待考查的項目相對減少，所以占用的時間和空間會呈下降趨勢。由此可見，FIS-ES算法與Apriori有著很好的互補性。

3 結束語

FIS-ES算法只需一次事務數據庫掃描就可以獲得最大頻繁項集，其使用的線性數據結構比FP-Tree算法存儲結構簡單，而且通過及時裁減，提高了內存的利用率。實驗表明FIS-ES算法在時間和空間的占用上是遠小于它的理論上界值的，在最小支持度較小的情況下，FIS-ES比Apriori算法具有更快的挖掘速度、更少的空間占用等優點，與Apriori具有很好的互補性。FIS-ES算法有待改進之處在于：①算法的時間和空間占用隨項目長度的增加呈指數增長，這種情況在最小支持度較大時表現得尤為突出；②所有的中間數據都存放在內存中，這種方式在事務數據庫很大時是不可取的。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。