基于FP-growth的前后部項約束關聯規則改進算法?

李 贊 王朝霞 孟月昊 隋 昊

（陸軍勤務學院軍事物流系 重慶 401331）

1 引言

關聯規則挖掘技術可從海量的數據中發現項之間隱含的、有價值的信息。最典型的算法是Agrawal等提出的 Apriori［1～2］、FP-tree［1～2］算法，但由于在挖掘中沒有用戶的參與和控制，這些算法會產生大量冗余的頻繁項集和無價值的關聯規則，使挖掘對于用戶的實際需求缺乏針對性，降低了關聯規則的使用效率。在實際應用中，用戶也希望只挖掘出包含某些項的關聯規則，而不是在生成的大量冗余規則中自己去篩選需要的關聯規則。比如在工程建設中，監理人員可能只希望了解哪些因素與超投資、超面積有關，而不是泛泛地發現工程建設中所有因素之間的關聯規則。這就需要分析者根據用戶的具體需求，對事務中的某些項或屬性設定約束條件，再進行關聯規則挖掘，通過減少冗余規則的產生，來提高用戶需找有價值關聯規則的效率。對此，許多專家學者展開了基于項約束的關聯規則算法研究，并提出了許多有效的項約束關聯規則算法。

文獻［3～5］提出的經典項約束算法Multiple?Joins、Recorder和Direct通過約束條件在挖掘頻繁項集過程中進行篩選，減少冗余規則的產生。文獻［6～7］提出了將項約束與概念格結合的DFCLA、DFTFH算法，通過格計算較少冗余規則。文獻［8～11］提出的這類算法則采用垂直數據形式表示數據集和深度優先的挖掘策略得出項約束關聯規則。文獻［12］提出了MCAL算法，利用約束條件的單調性及非單調性對項進行篩選挖掘。此外，還有基于項的時序性來進行約束的關聯規則算法［13～14］等。

上述基于項約束的關聯規則算法大多是從整體的角度出發進行約束，但考慮到用戶感興趣的項應該出現在關聯規則的前部還是后部的算法卻很少。而用戶的需求往往不僅限定了需要挖掘的項，同時也限定了項出現在規則中的位置。這些項約束關聯規則算法雖然減少了關聯規則的冗余量，但隨著事務集的增大，產生的無用關聯規則數量仍然較多，仍然存在規則使用效率不高的問題。文獻［15］提出的AR_F&R算法雖然提出了前后部項約束關聯規則的概念，并給出了相關形式化的定義，但算法基于Apriori，需要多次掃描事務集，計算開銷較大。

因此，針對項約束關聯規則約束項在規則中的位置不夠具體的現狀，本文在AR_F&R算法定義的相關概念的基礎上，提出了一種基于FP-growth的前后部項約束關聯規則算法FRFP（Fore-part and Rear-part FP-Growth）。通過對分別屬于前后部的項進行標記，然后篩選壓縮事務集，通過簡化的FP-tree挖掘出符合約束條件的有效頻繁項集和關聯規則。實驗結果表明，FRFP算法與其他項約束算法相比，生成的關聯規則更少，運算性能方面也得到了優化。

2 基本定義

定義 1 設 I=｛I1，…，Ij，…，Ik｝是所有項的集合，其中，Ij為數據項，簡稱為項（item）。在關聯分析中，包含0個或多個項的集合被稱為項集（item?set）。事務集D是由一系列具有唯一標識的TID的事務T組成，每個事務T包含的項集都是I的子集，即T?I。

定義2 形如X→Y的蘊涵式稱為一個關聯規則，關聯規則的支持度Support是事務集D中包含X∪Y的百分比，即 support(X→Y)=P(X∪Y)。Sup_count是指項集X∪Y在事務集D中出現的次數，即支持度計數。若項集的支持度大于等于用戶給定的最小支持度minsup（即支持度計數大于等于最小支持度計數min Sup_count），則該項集稱為頻繁項集。

定義3 關聯規則X→Y的置信度Confidence是指事務集D中包含X的事務同時包含Y的百分比，即confidence(X→Y)=P(X|Y)。置信度中的最小值稱為最小置信度minconf，一般由用戶自己設定。

定義4 規則前部集合F=｛F1，F2，…，Fn｝，該集合描述待挖掘關聯規則中用戶感興趣的所有規則前部項的集合，滿足 F?I且 F≠Φ 。FS=｛FS1，…，FSi，…，FSg｝為F所有非空子集的集合，其中FSj（j=1，2，3…，g）為F的非空子集，稱為前部項集。CFj稱為前部頻繁項集候選項集，大于等于minsup的CFj稱為前部頻繁項集，記為LFj，LF為前部頻繁項集集合。

定義 5 規則后部集合 R=｛R1，R2，…，Rm｝，該集合描述待挖掘關聯規則中用戶感興趣的所有規則后部項的集合，滿足R?I且R≠Φ。RS為R所有非空子集的集合。RS=｛RS1，…，RSt，…，RSn｝，RSt（t=1，2，3…，n）為R的非空子集，稱為后部項集。

定義4和定義5隱含以下條件：

條件1 F∩R=Φ。即用戶感興趣的所有規則前部項的集合F與用戶感興趣的所有規則后部項的集合R無交集。

定義6 給定關聯規則X→Y，若X?F，且Y?R，則關聯規則X→Y為前后部項約束關聯規則。

由條件1得出以下結論：若X→Y為前后部項約束關聯規則，則X∩Y=Φ。

證明：F∩R=Φ ，且X?F，Y?R故 X∩Y=Φ成立。

根據上述相關定義及條件1，進一步提出包含前后部項集的概念。

定義7 給定前后部項集集合IFR=｛IFR1，…，IFRt，…，IFRd｝，則其中的任一項集IFRt（t=1，2，3，…d）是同時包含規則前部項和規則后部項的項集即IFRt?(FUR)，且 IFRt∩F≠Φ ，IFRt∩R≠Φ ，IFRt簡稱為前后部項集。

前后部頻繁項集候選項集記為CFRt，若某個項集IFRt大于等于minsup，則稱為前后部頻繁項集，記為LFRt。包含前后部頻繁項集的集合記為LFR。

挖掘用戶感興趣規則前部項和規則后部項的關聯規則時，由于原始事務集D的事務中可能有大量冗余項，或者某些事務不包含用戶感興趣的前部項集合或后部項集合，則需要對原始事務集合進行篩選壓縮。其依據為

由性質1可得到如下結論：

結論1 給定事務T，?i：Ii?T，若Ii?F且Ii?R，則從事務T中刪除此項。

該結論是刪除事務冗余項的依據。

結論2 給定事務T，若T∩F=Φ，則刪除此條事務T。

該結論是刪除冗余事務的依據。

由 置 信 度 定 義 Confidence(X→Y)=可知，若要求取前后部項約束關聯規則X→Y，則必需知道(XUY)和（X）這兩種頻繁項集的支持度，而X為規則前部，Y為規則后部，則(XUY)表示同時具有規則前部和后部項的頻繁項集，故定義前后部項集IFRt及對應的前后部頻繁項集LFRt。而（X）表示只具有前部項的頻繁項集，故定義前部項集FSj及對應的前部頻繁項集LFj。從置信度定義公式可以看出，每個LFRt有且只有一個LFj與之對應，故只能生成一條關聯規則，是能夠減少冗余規則產生的原因所在。

因此，FRFP算法的思想在于：通過挖掘出所有的前后部頻繁項集LFRt和前部頻繁項集LFj，來達到求取符合項約束條件的關聯規則以及減少關聯規則冗余量的目的。整個算法流程均是圍繞如何挖掘出所有的LFRt和LFj來進行求解。

3 算法思想及流程

3.1 算法流程

本文提出的FRFP算法流程分為4個步驟，如圖1所示。

為更直觀形象地理解本算法，以只包含9個事務的事務集D作為案例，如表1左邊部分所示，假定用戶感興趣的規則前部集合F=｛I2，I5｝，規則后部集合R=｛I1，I3｝，minsup=0.25。

步驟1 計算頻繁1-項集。計算頻繁1-項集方法與FP-growth算法相同。頻繁1-項集的結果采用表FR-list來描述。表FR-list包括四個域：項名，支持度計數，標記和指針。首先，項按照支持度計數值從大到小排序；標記域用來描述某個項是否屬于前部項集合F或后部項集合R，如果該項屬于前部項集合，則標記為f，如果該項屬于后部項集合，則標記為r；加入指針域則是使得FR-list具有項頭表的功能，用于鏈接后續構建的FP-tree上的節點。

圖1 FRFP算法流程圖

表1 事務集D及FR-list

對案例事務集D完成步驟1后，生成的FR-list如表1右邊部分所示。FR-list的第一列的項按照支持度計數由大到小排序，第二列為項的支持度計數值，第三列存放前部和后部的標記信息，第四列的值暫時為空指針。

步驟2 篩選事務集并建立FP-tree。首先根據結論1和結論2對事務集進行篩選，壓縮事務集空間，然后按照FP-growth算法一樣建立FP-tree。具體方法見3.2.1節

步驟3 挖掘LFR和LF。在步驟2建立的FP-tree上，挖掘前后部頻繁項集和前部頻繁項集，并分別放入集合LFR和LF中。本步驟挖掘出所有前后部頻繁項集及前部頻繁項集，具體方法見3.2.2節。

步驟4 輸出關聯規則。對于每個LFRt，若存在對應的前部頻繁項集LFj，則計算每個前后部頻繁項集的置信度Confidence若其置信度大于等于minconf，則輸出強關聯規則。若不存在對應的前部頻繁項集LFj，則不考慮。從而輸出所有符合約束條件的關聯規則。

3.2 算法具體描述

3.2.1 篩選事務集并建立FP-tree

本節重點闡述對事務集D進行壓縮并建立FP-tree的方法。

1）刪除事務中的冗余項

分為兩種情況：一是刪除所有支持度小于minsup的項。二是刪除未被標記為f或r的項。以案例事務集合D為例，如圖2（c）第三列所示，事務 T200=｛I2，I4｝和事務 T400=｛I2，I1，I4｝中，I4未被標記為f或r，故篩選出I4，并從相應事務中刪除。

2）刪除冗余事務

根據結論2，去掉只標記有r項的分組事務。而只標記有f項的分組事務，可能會產生前部頻繁項集，故保留。以案例事務集合D為例，T500，T700均為｛I1，I3｝，I1和I3均被標記為r，故刪除此兩條事務。

具體偽代碼如下所示：

1.Sort-D（D，FR-list）｛∕刪除事務中冗余項，并對事務排序

2.foreach T in D do

3. foreach item in T do

4. if（item.support＜ minsup）or（item未標記為 f或 r）

5.then從T中刪除item

6. if T≠? then按項支持度值對T中的項降序排列

7.Output Dsorted∕輸出排序后的事務集合Dsorted

｝

圖2 排序篩選事務集并建立FP-tree

根據篩選排序后的Dsorted建立FP-tree，建樹方法與FP-growth算法相同。以案例事務集為例建立FP-tree如圖2（c）所示。需要指出的是，為了便于搜索分組FP-tree，以FR-list作為項頭表，使前部項和后部項通過指針指向它在FP-tree中的位置。如圖2所示，I5為前部項（標記為f），I3為后部項（標記為r），故分別通過指針指向I5和I3在FP-tree中的位置。

3.2.2 挖掘LFR和LF

根據建立的FP-tree挖掘包含前后部頻繁項集的集合LFR和前部頻繁項集集合LF。具體挖掘方法：1）發現分枝；2）在分枝上挖掘LFR和LF。

1）發現分枝

針對標記為f或r的項，根據每項指針所指位置在FP-tree上找到對應的枝進行挖掘。同時，根據本項在FP-tree上對應的節點的支持度計數來確定分枝上其他節點的支持度計數。如圖4所示，以案例事務集合D的FP-tree為例，I5和I3分別標記為f和r。I5通過指針在FP-tree上有兩個分支：null→I2：1→I1：1→I5：1 和 null→I2：1→I1：1→I3：1→I5：1。I3在1號分組FP-tree上有兩個分支：null→I2：2→I1：2→I3：2，和null→I2：2→I3：2。

2）在分枝上挖掘LFR和LF

若挖掘的是標記為f的項的分枝。例如I5，其生成的頻繁項集只可能有兩種類型：同時有f和r標記的頻繁項集；只有標記為f的頻繁項集。而這兩類頻繁項集又分別屬于LFR和LF。故直接按照傳統的FP-growth算法，遞歸挖掘頻繁項集即可。

若挖掘的是標記為r的項的分枝。遍歷每個分枝，根據FR-list的label中前后部項標記的信息，將分枝上的節點分別放入規則前部集合F和規則后部集合R，并分別求出前部項集集合FS和后部項集集合RS。只保留RS中包含本項的后部項集RSn，然后與FS中的前部項集FSj兩兩組合連接，生成前后部項集IFRt并輸出，但不輸出前部項集FSj。如圖3所示是挖掘標記為r項的分枝。

圖3 挖掘標記為r項的分支流程圖

圖4 I5和I3生成的LFR和LF

由圖3可知，I3為被標記為r的本分組項。選取I3一條枝null→I2：3→I1：3→I3：3，由于I3出現在規則后部集合R中，故只保留RS中包含I3的后部項集RSn，然后與前部項集FSj兩兩組合連接，輸出前后部項集IFRt。挖掘過程與挖掘標記為f的分組項項基本相同，但不輸出FSj。

最后將各分枝挖掘出的IFRt、FSj進行合并，得到候選項集CFRt和CFsj，并根據最小支持度minsup求出前后部頻繁項集LFRt和前部頻繁項集LFj，并分別放入前后部頻繁項集集合LFR和前部頻繁項集集合LF中。如圖4是標記為f的I5和標記為r的I3生成的前后部頻繁項集集合LFR和前部頻繁項集集合LF。

由FP-growth算法挖掘頻繁項集的方式：以待挖掘項為后綴挖掘FP-tree，構造條件模式樹，遞歸挖掘包含后綴的頻繁項集。因此生成的頻繁項集必定包含此項，而不包含此項的項集必定不是頻繁項集。根據這一特性，在挖掘標記為r的項的分枝時，只保留RS中包含本項的后部項集RSn，以確保挖掘出的有效項集必定是頻繁項集。

具體偽代碼如下所示：

1.gen-LFR（FP-tree，FR-list，minsup）｛∕發現分枝

2.foreach item in FR-list｛∕對 FR-list中的每項

3.if item.link≠null then

4.branchset←find branch（item.link，FP-tree）；

5. foreach branch in Branchsetdo

6.F←find-Fore-part（branch，FR-list）；

7.R←find-Rear-part（branch，FR-list）；

8.FS←non-empty-powerset（F）；

9.RS←non-empty-powerset（R）；∕挖掘標記為f的項：

10. if item.label=‘f’then∕調用FP-growth算法進行挖掘，挖掘標記為r的項：

12. if item.label=‘r’then∕若本分組項被標記為r，保留RS中包含本分組項的后部項集RSn

14. foreach（FSj∈ FS，RSn∈ RS）do

15. IFRt←FSj??RSn∕生成前后部項集IFRt

∕合并項集生成 LFR，LF

16.CFRt，CFj←aggregate IFRt，FSj∕將相同的 IFRt，FSj進行合并生成候選項集CFRt，CFj

17.foreach CFRt，CFjdo ∕合并同時判斷頻繁項集

18.if CFRt，CFj≥ min sup×D then

19. LFRt，LFj←CFRt，CFj∕生成頻繁項集 LFRt，LFj

20. LFR，LF←add LFRt，LFj∕將 LFRt，LFj添加進 LFR，

LF

21. ｝

22.｝

4 實驗結果分析

FRFP算法在MyEclipse開發環境下用Java編程實現，并從不同數據集規模運行時間和生成有效關聯規則數比較了FRFP算法與其他項約束算法的優劣，從不同最小支持度運行時間方面分析了FR?FP算法本身的性能。實驗環境為華碩筆記本，CPU 2.6GHz，4GB內存，操作系統為Windows7。采用的數據集 T40I10D100k 來源于 http：∕fimi.ua.ac.be∕data∕，抽取其中6000條數據作為實驗數據。

FRFP與其他算法比較：

1）不同數據集規模運行時間對比。將FRFP算法與 AR_F&R［15］算法、DFTFH［7］算法進行比較，設置最小支持度minsup為10%，最小置信度minconf為50%，如圖5所示。

FRFP算法比AR_F&R算法、DFTFH算法在運行相同數據集的條件下，所用時間最少，且隨著數據集的增大，運行時間基本呈線性增長，說明FRFP算法的數據規模增長性較好。

圖5 數據集規模運行時間對比

2）生成關聯規則數對比。統計實驗1中三種算法生成的關聯規則數，如下表2所示。

表2 關聯規則結果對比

由表2可知，DFTFH算法由于約束條件并未具體約束關聯規則前部和后部的項，生成的關聯規則數要比有明確前后部項約束的FRFP算法和AR_F&R算法多，而FRFP算法與AR_F&R算法生成的關聯規則數基本相同。

FRFP算法自身性能分析：

3）不同最小支持度下運行時間對比。為測試算法在不同最小支持度下運行的時間，選取了最小支持度為0.05，0.1，0.15三種情況進行了測試，測試結果如圖6所示。

圖6 不同最小支持度運行時間

由圖6可知，隨著最小支持度的增大，FRFP算法運行時間越少，這是由于最小支持度篩選掉了更多的項集，降低了挖掘的復雜程度和計算開銷，因此運行時間變少。

5 結語

本文提出的FRFP算法，立足于優化項約束關聯規則約束條件不夠明確具體的問題，通過對規則前后部具體只出現哪些項進行明確的約束，從而更進一步減少冗余關聯規則的產生，滿足用戶的需求。但FRFP在挖掘實時更新的事務集時，效果欠佳。因此，如何挖掘實時動態更新的事務集將是下一步研究的重點內容。