李 贊 王朝霞 孟月昊 隋 昊

（陸軍勤務(wù)學(xué)院軍事物流系 重慶 401331）

1 引言

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

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

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

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

2 基本定義

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

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

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

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

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

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

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

定義6 給定關(guān)聯(lián)規(guī)則X→Y，若X?F，且Y?R，則關(guān)聯(lián)規(guī)則X→Y為前后部項約束關(guān)聯(lián)規(guī)則。

由條件1得出以下結(jié)論：若X→Y為前后部項約束關(guān)聯(lián)規(guī)則，則X∩Y=Φ。

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

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

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

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

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

由性質(zhì)1可得到如下結(jié)論：

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

該結(jié)論是刪除事務(wù)冗余項的依據(jù)。

結(jié)論2 給定事務(wù)T，若T∩F=Φ，則刪除此條事務(wù)T。

該結(jié)論是刪除冗余事務(wù)的依據(jù)。

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

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

3 算法思想及流程

3.1 算法流程

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

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

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

圖1 FRFP算法流程圖

表1 事務(wù)集D及FR-list

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

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

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

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

3.2 算法具體描述

3.2.1 篩選事務(wù)集并建立FP-tree

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

1）刪除事務(wù)中的冗余項

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

2）刪除冗余事務(wù)

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

具體偽代碼如下所示：

1.Sort-D（D，F(xiàn)R-list）｛∕刪除事務(wù)中冗余項，并對事務(wù)排序

2.foreach T in D do

3. foreach item in T do

4. if（item.support＜ minsup）or（item未標(biāo)記為 f或 r）

5.then從T中刪除item

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

7.Output Dsorted∕輸出排序后的事務(wù)集合Dsorted

｝

圖2 排序篩選事務(wù)集并建立FP-tree

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

3.2.2 挖掘LFR和LF

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

1）發(fā)現(xiàn)分枝

針對標(biāo)記為f或r的項，根據(jù)每項指針?biāo)肝恢迷贔P-tree上找到對應(yīng)的枝進行挖掘。同時，根據(jù)本項在FP-tree上對應(yīng)的節(jié)點的支持度計數(shù)來確定分枝上其他節(jié)點的支持度計數(shù)。如圖4所示，以案例事務(wù)集合D的FP-tree為例，I5和I3分別標(biāo)記為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

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

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

圖3 挖掘標(biāo)記為r項的分支流程圖

圖4 I5和I3生成的LFR和LF

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

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

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

具體偽代碼如下所示：

1.gen-LFR（FP-tree，F(xiàn)R-list，minsup）｛∕發(fā)現(xiàn)分枝

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

3.if item.link≠null then

4.branchset←find branch（item.link，F(xiàn)P-tree）；

5. foreach branch in Branchsetdo

6.F←find-Fore-part（branch，F(xiàn)R-list）；

7.R←find-Rear-part（branch，F(xiàn)R-list）；

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

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

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

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

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

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

∕合并項集生成 LFR，LF

16.CFRt，CFj←aggregate IFRt，F(xiàn)Sj∕將相同的 IFRt，F(xiàn)Sj進行合并生成候選項集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 實驗結(jié)果分析

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

FRFP與其他算法比較：

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

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

圖5 數(shù)據(jù)集規(guī)模運行時間對比

2）生成關(guān)聯(lián)規(guī)則數(shù)對比。統(tǒng)計實驗1中三種算法生成的關(guān)聯(lián)規(guī)則數(shù)，如下表2所示。

表2 關(guān)聯(lián)規(guī)則結(jié)果對比

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

FRFP算法自身性能分析：

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

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

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

5 結(jié)語

本文提出的FRFP算法，立足于優(yōu)化項約束關(guān)聯(lián)規(guī)則約束條件不夠明確具體的問題，通過對規(guī)則前后部具體只出現(xiàn)哪些項進行明確的約束，從而更進一步減少冗余關(guān)聯(lián)規(guī)則的產(chǎn)生，滿足用戶的需求。但FRFP在挖掘?qū)崟r更新的事務(wù)集時，效果欠佳。因此，如何挖掘?qū)崟r動態(tài)更新的事務(wù)集將是下一步研究的重點內(nèi)容。