新型頻繁項集快速挖掘模式樹的方法

摘 要：在FP_growth算法中，FP_tree及條件FP_tree的構造和遍歷占了算法絕大部分的時間，為了能減少這方面的時間，提出了一種新型快速的方法——改進的層次頻繁模式樹（inproved hierarchy FP_tree，IHFP_tree）。該方法采用首先對數據庫掃描一遍，產生每個項的等價類；然后去掉不頻繁項，對等價類進行重新改寫；最后再創建FP_tree。引入層次頻繁模式的概念，在挖掘過程中大大提高了算法的時空效率。與其他頻繁模式挖掘的常用算法進行了時間復雜度和空間復雜度的比較，實驗表明，IHFP_tree的挖掘速度比FP_tree方法要快得多。

關鍵詞：FP_tree； ＩHFP_tree； 頻繁模式； 等價類

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1001-3695(2008)08-2325-03

Research on new mining algorithm of frequent itemset

WANG Jing-hong1， LIU Li-na2， GENG Zong-ke1

(1. Collgeg of Information Technology， Hebei Normal University， Shijiazhuang 050091， China; 2.Hebei Agricultural University， Qinhuangdao Hebei 066004， China)

Abstract:In FP-growth algorithm， it costs most of the time in constructing and traversing the FP-tree and conditional FP-tree.In order to constructing the FP_tree efficiently， this paper proposed a new fast algorithm called inproved hierarchy FP_tree (abbreviate IHFP_tree). The algorithm firstly scaned the database only once for generating equivalence classes of each item. Then deleted the non-frequent items and rewrote the equivalence classes of the frequent items， and then constructed the IH FP_tree.

Key words：FP_tree; IHFP_tree; frequent pattern; equivalence class

頻繁模式挖掘是關聯規則、時序模式挖掘應用中的關鍵技術和步驟。以往大多數研究采用Apriori算法^[1]來挖掘頻繁模式。Apriori算法利用generate-and-test方法產生和檢測候選項集，在挖掘過程中產生了大量的候選項集，并且需要反復掃描數據庫，從而嚴重影響了的效率。后來的一些基于Apriori的算法^[2]雖然作了一些改進，如GSP^[3]、 PSP^[4]，但仍然沒有解決產生大量候選項集的問題。為此，Han jia-wei等人提出了一種不產生候選項集的FP-growth^[5]算法，用一個壓縮的樹FP_tree來存儲頻繁一項集，并且只需要掃描數據庫兩次，大大提高了關聯規則挖掘速度。實驗分析表明，FP-growth算法比Apriori等算法快一個數量級，如FreeSpan^[6]、PrefixSpan^[7]、FP_growth。但當數據庫數量太大和支持度閾值很小時，找出所有的頻繁模式是很浪費時間的，所以為了解決頻繁模式中的冗余問題，提出了有關挖掘最大頻繁模式^[8]和閉頻繁模式^[9]的算法。這些算法都是基于FP_tree的，創建FP_tree需要掃描兩遍數據庫，這樣大大浪費了時間。

1 頻繁模式的定義

設I={i1，i2，…，im}為數據項集合，即項集；Ｄ為與任務相關的數據集合，即交易數據庫。其中的每項交易Ｔ是一個數據項子集，TI，每個交易均包含一個識別編號TID。A為一個數據項集合，Ｋ-項集是包含k個數據項的項集，如集合｛computer，finanicial_management_software｝為一個２-項集。一個項集的出現頻率就是整個交易數據集Ｄ中包含該項集的交易記錄數，稱為該項集的支持度（support count）。對于一個項集A的出現頻率大于最小支持度閾值乘以交易記錄集Ｄ中的記錄數，則稱該項集滿足最小支持度閾值；如果項集A的支持度大于等于用戶給定的閾值min_sup，即滿足最小支持閾值的項集為頻繁k-項集(frequent itemset，ＦＩ)，或稱為頻繁模式。

2 FP_tree和基于FP_tree的算法

FP_tree這種壓縮的數據結構大大提高了挖掘速度，主要原因在于不用產生大量的候選項集。FP_tree的建立需要掃描兩遍數據庫，與Apriori算法相比，性能大大提高。

1)FP_tree 的構建過程

input: 數據庫DB和最小支持度 min_sup

output: FP_tree

methord:

a)掃描數據庫DB，記錄項集F和它們的支持度，并按照支持度降低的順序排序放到集合L中。

b)創建FP_tree的根節點T， 且T=1。對于DB中的每個事務做以下操作，根據L集合中項的順序排列頻繁項，然后調用函數insert_tree([p|P]，T)。

c)insert_tree([p|P]，T)

{if T有節點N，且N.item_name=p. item_name；

則N的支持度count=count+1；

else{

建一個新的節點N；

N的支持度count=1；

N的父節點和節點T連接；

與節點N具有相同名稱的項連接起來；

}；

if p為非空，

調用insert_tree(p，N)；

}

2)基于FP_tree的算法

因為FP_tree的高效性，許多頻繁模式的挖掘算法都是基于FP_tree的，如closet+算法、TFP算法等。具體步驟請參看參考文獻。

3 IHFP_tree的創建方法

通過上面分析，創建FP_tree是基于FP_tree算法的關鍵。FP_tree的創建包含兩步：a)掃描數據庫產生頻繁一項集;b)再次掃描數據庫創建FP_tree。本文提出了一種只需掃描一遍數據庫就能建立FP_tree的方法——層次挖掘算法IHFP_tree。

IHFP_tree算法包括四部分，具體分析如下：

a)掃描數據庫，建立每個項的等價類。

定義1 每個項的等價類Ei={(Tid，j)|Tid}是序列標志，i為序列中的項，j為按照字母順序排序的緊隨i后面的一項}。假定每個序列最前面的項為root。

例1 表1給出了一個數據庫，則

Eroot={(1，a)(2，c)(3，a)(4，a)(5，d)}

Ea={(1，b)(3，b)(4，d)(5，d)}

Eb={(1，e)(3，e)}

Ec={(2，e)}

Ed={(4，f)(5，f)}

Ee={(1，f)(2，f)(3，f)}

Ef={(1，1)(2，1)(3，1)(4，1)(5，1)}

表1 事務數據庫numitemsnumitemsX1a，b， f，eX4f，a，dX2e，c， fX5f，a，dX3e，a， f，bX6a，e，fb)計算每個項的支持度，去掉非頻繁項。

定義2 |Ei|為i的支持度。

例2 由定義2可知，a的支持度為Ea=4；b的支持度為|Eb|=2;c的支持度為|Ec|=1;d的支持度為|Ed|=2；e的支持度為|Ee|=3; f的支持度為|Ef|=5。假設最小支持度為3，則b、c、d三項不滿足支持度，去掉，然后把剩下的項按照支持度大小排序，即f ∶5，a ∶4.e ∶3。

c)調整去掉非頻繁項后的等價類，再按照支持度從大到小的順序重新調整。去掉不頻繁項后需要調整等價類中頻繁項后面的項。

例3 當去掉b時，Ea中包含b，所以b被替換成b后面的項e。

Ea={(1，e)(3，e)(4，d)(5，d)}

去掉c后，

Eroot={(1，a)(2，e)(3，a)(4，a)(5，d)}

去掉d后，

Ea={(1，e)(3，e)(4，f)(5，f)}

然后再按照支持度從大到小順序調整。首先調整root，所有等價類中序列標志為1后面的項有a、mull、f、e。其中f支持度最大，所以root在第一個序列中的后面的項為f。同理，最后結果為

Eroot={(1，a)(2，e)(3，a)(4，a)(5，d)}

Ea={(1，e)(3，e)(4，f)(5，f)}

Ee={(1，f)(2，f)(3，f)}

Ef={(1，1)(2，1)(3，1)(4，1)(5，1)}

d)用調整后的等價類創建FP_tree。

定義3 |Eij|表示i項中j的支持度。

例4 根據上述定義可知，|Erootf|=5，|Efa|=4，|Eje|=1，|Eae|=2

由|Erootf|=5可知，root后面的項即root的孩子節點為f，支持度是5，則創建FP_tree，如圖1（a）所示。同理，最后得到IHFP_tree，并創建頭表，建立連接，如圖1（b）所示。

IHFP_tree算法的創建過程如下：

input: 數據庫DB 和最小支持度 min_sup

output: IH FP_tree

methord：

a)掃描數據庫DB，創建每個項的等價類；

b)計算每個項的支持度；

c)去掉非頻繁項，重新調整等價類；

d)按照支持度降低的順序重新調整等價類；

e)函數insert_tree(Eij){

創建節點i和I的子節點j；

i的支持度為|Eij|；

調用函數 insert_tree (Eij)；

最后創建頭表和相同節點之間的連接；

}

4 時間復雜度和空間復雜度的比較

挖掘頻繁模式主要采用Apriori算法及其改進形式，這類算法的挖掘效率較低。例如對于給定的候選集合Ci，可以通過對數據庫的一次掃描計算出它們的頻率，只需保存每個候選項的計數；當遇到包含這個候選項的記錄時便增加其計數，則所需的時間是O(Ci|np)。令數據容量為np，則尋找頻繁項集所需的總時間是O(∑i|Ci|np)，也就是與所有層次候選集合數的乘積成正比。每生成一個候選項集就要掃描數據庫以確定其支持度。對于數據庫中如此大量的候選項集，需要不斷地訪問數據庫，通過模式匹配來計算項集的支持度，需要大量的I/O開銷。

FP_growth算法是一種基于模式增長的頻繁模式挖掘算法，避免了大量候選項集的產生，只需要掃描兩次數據庫，效率比Apriori算法快一個數量級。然而，FP_growth算法的主要問題是在挖掘頻繁模式時它需要遞歸地生成條件FP樹并且每產生一個頻繁模式就要生成一個條件FP_tree。創建附加數據結構，并且每當模式增長時就要創建一次，動態地創建如此大量的附加數據結構，特別是在支持度閾值較小時，即使對于很小的數據庫，也將產生數以十萬計的頻繁模式。動態地生成和釋放數以十萬計的條件FP_tree，將耗費大量時間和空間。

從算法的時間復雜性來看，IHFP_tree算法只需掃描一遍數據庫，并且不需要重復地檢索頭表，所以運行時間不會隨著支持度的降低而越來越長；而且減少了空間的使用率，節省了大量的I/O開銷。與FP_tree相比較，IHFP_tree的規模很小，且每次迭代時只是在原有IHFP_tree的基礎上添加若干個分支，因此花費的時間很少。另外，數據庫中數據量越大、事務越長，產生的候選項集就越多，FP_tree所需的運行時間越長，IHFP_tree算法只需檢索數據庫的頭表，因此，IHFP_tree算法占據的最大內存空間較小，運行時間只是前者的一半。從算法的空間復雜性來看，IHFP_tree算法在同類算法中是較低的。

5 實驗結果分析

本文提出的方法是由C++語言來實驗的。該程序在Windows XP系統上運行，CPU為2.8 GHz，內存為2 GB。數據參數如表2所示，數據集由assoc.gen^[10]產生。圖2~4分別給出了該改進算法在不同參數下的運行時間。

表2 多個數據參數參數描述T事務記錄的平均長度D數據庫中事務的數量N數據庫中項的個數I頻繁項集的平均長度圖2中的執行時間包括掃描數據庫和建立樹結構的時間。IHFP_tree算法隨著支持度的遞減，算法的性能要比FP_tree更有效。支持度越小，效率越高，當最小支持度為2%時，IHFP_tree算法的執行效率大概是FP_tree算法的4倍；當最小支持度為8%時，差距大約縮小到2倍。本文提出的算法的運行時間不會隨著支持度的降低而越來越長，因為它只需掃描一遍數據庫，并且不需要重復檢索頭表。

圖3中設定最小支持度為7%，它給出了不同事務大小時兩種算法的執行時間比較。由圖3可知，IHFP_tree的運行時間小于FP_tree。這是因為：a)數據庫中數據量越大，FP_tree所需的運行時間越長，因為事務越長，掃描該事務數據的時間就越長，事務越長，產生的候選項集就越多；b)IHFP_tree算法只需花費比FP_tree更少的時間來檢索頭表維持項之間的聯系。

圖4中設定最小支持度仍然是7%，它給出了事務數量不同時的執行時間。隨著事務數量的增加，執行時間也增長，而且事務數據量越大，兩種算法的執行時間的差距也就越大。主要原因是IHFP_tree 算法只需掃描一遍數據庫，FP_tree算法需要掃描兩遍數據庫，所以事務數據量越大，掃描所花費的時間就越長，I/O 代價就越大。另外，FP_tree的建立需要通過檢查事務記錄來過濾非頻繁項并記錄每個事務中的頻繁項；相反，IHFP_tree不需要做這些工作。

6 結束語

本文提出了一個新穎的建立FP_tree的方法IHFP_tree。從實驗結果來看，該方法優于FP_tree。原因是該算法只需掃描一遍數據庫；不需要篩選和重組事務記錄；當在IHFP_tree中加入一個新節點時，不需要重復地檢查頭表和連接。

參考文獻：

[1]AGRAWAL R， SRIKANT R. Fast algorithms for mining association rules[C]// BOCCA B， JARKE M， ZANIOLO C. Proc of the 20th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers， 1994:487-499.

[2]AGRAWAL R， SRIKANT R . Mining sequential patterns[C]// YU P， CHEN A. Proc of the 11th International Conference on Data Engineering. Taipei:IEEE Computer Society Press， 1995:3-14.

[3]SRIKANT R， AGRAWAL R. Mining sequential patterns: generalizations and performance improvements[C]//APERS P， BOUZEGHOUB M， GARDARIN G. Proc of the 5th International Conference on Extending Database Technology. London: Springer-Verlag， 1996:3-17.

[4]MASSEGLIA F， CATHALA F， PONCELET P. The PSP approach for mining sequential patterns[C]//ZYTKOW J， QUAFAFOU M. Proc of the 2nd European Symposium on Principles of Data Mining and Knowledge Discovery. London: Springer-Verlag， 1998:176-184.

[5]HAN Jia-wei， PEI Jian， MORTAZAVI-ASL B， et al. FreeSpan: frequent pattern-projected sequential pattern mining[C]//RAMAKRISHNAN R， STOLFO S， BAYARDO R， et al. Proc of the 6th ACM SIGKDD International Corference on Knowledge Discovery and Data Mining. New York: ACM Press， 2000:355-359.

[6]PEI Jian， HAN Jia-wei， MORTAZAVI-ASL B. PrefixSpan: mining sequential patterns efficiently by prefix-projected pattern growth[C]// BUCHMANN A， GEORGAKOPOULOS D. Proc of the 17th International Conterence on Data Engineering. Washington DC: IEEE Computer Society， 2001:215-224.

[7]HAN Jia-wei， PEN Jian， YIN Yi-wen. Mining frequent patterns without candidate generation[C]// Proc of ACM SIMOD International Conference on Management of Data. New York: ACM Press， 2000:135-143.

[8]GRAHNE G， ZHU Jian-fei. High performance mining of maximal frequent itemsets[C]// Proc of the 6th SIAM International Workshop on High Performance Data Mining. 2003:885-887.

[9]PASQUIER N， BASTIDE Y， TAOUIL R， et al. Discovering frequent closed itemsets for association rules[C]// Proc of the 7th Internatio-nal Conference on Database Theory. London: Springer-Verlag， 1999:398-416.

[10]IBM Almaden Research Center. Quest synthetic data generation [EB/OL].(2005).http://www.almaden.ibm.com/software/quest/resources/datasets/syndata.htnl.

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