基于頻繁模式樹的正負項目集挖掘

趙旭俊

(太原科技大學計算機科學與技術學院，太原030024)

關聯規則是數據挖掘的一個主要研究方向，它主要是發現大量數據中的項集與項集之間存在的有趣的相互關系。R.Agrawal在1993年第一次提出關聯規則的相關概念[1]，在此之后很多研究者對關聯規則的相關問題進行了大量的探討與研究。傳統的關聯規則算法僅能挖掘正關聯規則[2-4]，如“買了雞蛋的顧客很有可能買火腿”這樣的規則，而忽略了“買了雞蛋的顧客很可能不去買鴨蛋”這樣的負規則。但是在競爭與投資分析等重多領域決策制訂中，負規則起了非常重要的作用。從規則的的正確性與完整性角度來看，負規則與正規則—起為決策者能做出正確決策提供全面和完整的信息，二者缺一不可。正因為這樣，負規則的研究變得越來越重要。

在國外的研究中，Brin S首次提到了關于頻繁項目集之間的負相關[5];Savasere A等人提出了一種挖掘負關聯規則的思想[6]，其算法是用戶需要事先確定層次分類結構，但是這一點很難做到，而且與實際不相符合;Do Trong針對一些漸進挖掘頻繁模式的算法，不能擴展到現實世界的數據庫的問題，提出一種挖掘頻繁漸進閉模式算法[7]，使得挖掘閉頻繁項集的時間逐步線性;之后，Zhou Jiayi等人提出了采用圖形處理單元(GPU)來執行FPM以達到提高挖掘效率的目的[8]，在該算法中，根據GPU硬件劃界的特點，設計一個緊湊的數據結構用來存儲整個數據庫的數據;屈百達[9]提出采用FPTree提取正負關聯規則，但沒有考慮用戶的興趣度。本文在充分考慮用戶感興趣模式的基礎上，采用一階謂詞邏輯作為用戶感興趣的背景知識表示技術，提出了一種基于背景知識的包含正負項目集的頻繁模式樹，給出了針對正負項目集的約束頻繁模式樹的構造算法NCFP-Construct，，該算法不但可以發現所有的正規則而且能找到所有的負規則，在整個挖掘過程中只需掃描兩次數據庫，故算法是有效和可行的。

1 相關概念

定義1 對于已知的項集M、N，其中M∩N=?，能生成8種形式的關聯規則:1、M?N;2、﹁M=＞N;3、M?﹁N;4、﹁M= ＞﹁N;5、N= ＞M;6、N=＞﹁M;7、﹁N= ＞M;8、﹁N= ＞﹁M.其中5～8同1～4相對應，將1～4中規則前后件互換就能得到5～8.因此，在后面敘述中，只考慮關聯規則的前4種形式，其中把1稱為正關聯規則，相應地2～4稱為負關聯規則。負關聯規則也有支持度和置信度，其定義同正關聯規則相同，只是在描述上分別用﹁M和﹁N分別代替了原來的M和N.

定義2 設L={l1，l2，…，lm}是項目的集合，而集合中元素稱為項或項目，設D為交易數據庫，則|D|表示數據庫中的記錄數，事務表示為T={t1，t2，…，tn}，而且每個事務由唯一的標識TID進行描述。

定義3 若M?L，N?L，且M∩N=?，記sup(M)表示D中含M的事務數，則M的支持度為|M|/|D|，同理，M∪N的支持度為|M∪N|/|D|，記為sup(M∪N)。

定義4 規則M?N在交易數據庫D中的置信度定義為conf(M?N)=|M∪N|/|M|，即同時包含M和N的記錄數與包含M的記錄數之比，由此很容易推出不包含某項集M的支持度計算方法為:

1、sup(﹁M)=1-sup(M)

2、sup(M∪﹁N)=sup(M)-sup(M∪N)

3、sup(﹁M∪N)=sup(N)-sup(M∪N)

4、sup(﹁M∪ ﹁N)=1-sup(N)-sup(M)+sup(M∪N)

引理1|D|為交易數據庫中記錄的總個數，對任意的負項目﹁M，設其對應的正項目M支持度計數(即在數據庫中出現的次數)為A.count，那么﹁A的支持度計數為:﹁A.count=|D|-A.count.

應用該引理，掃描原始數據庫，可以計算出所有正負項目的支持度計數，然后利用定義4計算其支持度，將所有支持度不小于最小支持度閾值的正、負項目合并成一個集合，作為頻繁l-項集L，用正整數記錄正項目，用負整數記錄負項目，并且在頻繁1-項集中，將各項按照絕對值的降序排列，如果同時含有絕對值相等的一對正、負項目，按照負項目在對應正項目前一位的原則，形成一個有序序列。

2 含負項目的約束頻繁模式樹構造

2.1 一階謂詞邏輯與背景知識

謂詞是表示一個個體的性質或若干個個體之間的關系的詞。謂詞邏輯是一種形式語言系統，它采用邏輯方法進行推理，可以用來表示屬性之間的存在關系。而關聯規則是描述事務屬性之間的隱含關系，因此采用一階謂詞邏輯能夠恰當描述指導關聯規則挖掘所需背景知識。此過程是將用戶感興趣模式通過一階謂詞邏輯進行描述，因此首先需要定義謂詞，通過謂詞描述背景知識，并明確指出各個謂詞的含義，然后將謂詞通過邏輯運算符號連接起來，生成確定的謂詞公式，以此表達完整的關聯規則挖掘所需的背景知識。設定如下幾個謂詞:UserInteresting(g(r))、ItemSupport(g(r)，k)、UserInterested(g(r))、UserP(g(r))和 UserQ(g(r)).其中r是數據庫中的某一關系表的表名，g是確定的函詞，用其表示關系表r到其屬性的映射，因此g(r)表示的是屬性集合。謂詞 UserInteresting(g(r))表示用戶感興趣的模式一定包含g(r)項目子集;謂詞ItemSupport(g(r)，k)表示是g(r)項目集的支持度一定大于等于閾值k;謂詞UserInterested(g(r))表示在前一次關聯規則挖掘中用戶感興趣的模式包含g(r);謂詞 UserP(g(r))和UserQ(g(r))是不同用戶根據需要定義自己的需求，因此含義也由用戶自己進行確定。

定義5 設r是事務數據庫中的關系表的表名，g表示映射，k是用戶確定的最小支持度(0≤k≤1)，則由上述謂詞組成的謂詞公式可表示背景知識G.

(1)UserInteresting(g(r))

(2)ItemSupport(g(r)，k)= ＞UserInteresting(g(r))

(3)UserInterested(g(r))=＞UserInteresting(g(r))

(4)UserP(g(r))∧ UserQ(g(r))=＞UserInteresting(g(r))

在定義5中，UserInteresting(g(r))表示用戶直接給出感興趣的項目集;ItemSupport(g(r)，k)→UserInteresting(g(r))表示在上次關聯規則挖掘中，如果項目集g(r)的支持度大于等于閾值k，那么在下次關聯規則挖掘中g(r)將成為用戶感興趣的模式集;UserInterested(g(r))=＞UserInteresting(g(r))表示如果用戶在上次關聯規則挖掘中對項目集g(r)感興趣，那么在下次挖掘中也將對其感興趣;謂詞公式UserP(g(r))∧UserQ(g(r))=＞UserInteresting(g(r))中UserP和UserQ是不同用戶根據需要定義自己的需求，具體含義也由用戶確定，UserP和UserQ可以是空式，也可以是合取式。

定義6 設事務數據庫用D表示、用戶感興趣的背景知識用G表示，如果從數據庫D中挖掘的模式P符合背景知識G的約束，將其記為G(P)=True，反之，如果從數據庫D中挖掘的模式P不符合背景知識G的約束，我們將其記為G(P)=False.

定義7 設事務數據庫用D表示、用戶輸入的最小支持度閾值用σmin表示，用戶感興趣的背景知識用G表示，如果頻繁模式L滿足G(L)=True，則稱L為約束頻繁模式。

2.2 約束頻繁模式樹(CFP樹)及構造

J.Han等提出一種用頻繁模式樹FP-Tree提取頻繁項目集的算法，借助其頻繁模式樹的定義對約束頻繁模式樹進行如下的定義:

定義8 設用戶感興趣的背景知識用G表示，對于任意一顆頻繁模式樹，如果從根結點到所有葉子結點的路徑中，所提取的所有頻繁模式P，都能滿足G(P)=True，則稱此頻繁模式樹為約束頻繁模式樹CFP-Tree.

定義9 在定義8的基礎上，能夠得到含負項目的約束頻繁模式樹的定義，即可定義為滿足下面4個條件的樹型結構:①包含一個值為“NULL”的根結點(可用root描述)，root的孩子是項前綴子樹集合，該項前綴子樹還包含頻繁項頭表。②項目前綴子樹中的結點都包含3個域:ItemName，ItemCount，ItemNodeLink，其中，ItemName描述項目的名稱，既可以描述正項目也可以描述負項目;ItemCount描述包含該結點的事務計數，即支持度計數;ItemNodeLink是一指針，指向約束頻繁模式樹中具有相同的項目名稱的的下一個結點，當下一個結點不存在時，ItemNodeLink為NULL.③頻繁項目頭表中的每一個結點包含兩個域:FreqName，FreqLink，其中FreqLink為指向約束頻繁模式樹中具有相同名稱的首結點指針。④從根結點到所有葉子結點的路徑中，所提取的所有頻繁模式P，都能滿足G(P)=True.

2.3 算法思想及其方法描述

對于確定的事務數據庫D，最小支持度為σmin、一階謂詞邏輯描述的背景模式為G，由于任意的符合約束的頻繁模式P，滿足G(P)=True，所以并非數據庫D中所有事務都符合要求，只有滿足背景知識G的事務來構造FP樹，才能包含符合約束條件的約束頻繁模式，因此按照下述步驟，通過兩次掃描事務數據庫來實現約束頻繁模式樹的構造:

1)第一次掃描數據庫，正項目采用正整數記錄，負項目采用負整數記錄，利用定義4中給出的公式統計各正項目及其負項目的出現頻率，并計算所有正負項目的支持度。將所有滿足最小支持度閾值條件的正、負項目合并成一個集合;

2)對上述集合的順序進行調整，將各項按照支持度降序排序，如果某對正、負項目的支持度恰好相等，那么按照負項目在前，其對應正項目在后的原則進行排序，生成一個有序序列，這就是正負項目挖掘中的頻繁l項集，用L表示;

3)創建頻繁模式樹的根結點，以“NULL”表示;

4)對于事務數據庫D中任意事務T，判斷T是否滿足背景知識約束，即如果T中不包含定義5中描述的模式，則讀取下一條記錄，否則，執行5);

5)將事務T中頻繁項按頻繁1項集L中的次序進行排序，結果為T'，并按如下步驟來更新約束頻繁模式樹:

(1)在約束頻繁模式樹中，尋找與T'的最長前綴匹配的路徑;

(2)對于該匹配路徑上的結點，其計數增加1;

(3)確定該路徑中最后一個匹配的結點，以此結點為為根結點，在約束頻繁模式樹中依次創建孩子結點，其值依次為T'中剩余頻繁項，其計數為1.

約束頻繁模式樹(CFP-Tree)中由于引入了負項目，其構造方法與傳統約束頻繁模式樹有所不同。對于事務數據庫D中的任意事務T，如果T中包括某個正頻繁項，說明T含有該正頻繁項;如果T中不包括某個負頻繁項所對應的正項目，說明T中隱性包括此負頻繁項。構造約束頻繁模式樹的主要思想就是將每個事務中包含的正頻繁項和隱含的負頻繁項，按照第一次掃描數據庫形成的頻繁1項集L中的順序插入到CFP-Tree.通過上述分析，CFP-Tree構造算法NCFP-Construct，可描述如下:

輸入:一個事務數據庫D、最小支持度閾值σmin和背景知識G(g1，g2，…gk).

輸出:CFP-Tree

步驟:

1)第一次掃描事務數據庫，正項目采用正整數記錄，負項目采用負整數記錄，利用引理1統計各正項目及其負項目的出現頻率，并利用定義4中公式計算所有正負項目的支持度。

2)將所有滿足最小支持度閾值條件的正、負項目合并成一個集合F.

3)如果某對正、負項目的支持度恰好相等，那么按照負項目在前，其對應正項目在后的原則進行排序，生成一個有序序列，這就是正負項目挖掘中的頻繁1項集，用L表示;

4)計算背景知識G(g1，g2，…gk)的支持度Si.

5)每個事務按如下程序執行。

在上述算法中，創建約束頻繁模式樹的根結點，記為T，并且標記為“NULL”，然后對D中的每個交易Trans做如下操作:根據L中的順序，選出并排序Trans中的頻繁項，把Trans中排好序的頻繁項列表記為[p|P]，其中p是第一個元素，P是列表的剩余部分，最后調用 insert_tree([p|P]，T).

函數insert_tree([p|P]，T)的運行如下:如果T有一個子結點N，其項目值恰好等于p，則將N的計數域值增加1;否則創建一個新結點N，使它的count為1，父結點為T，并將node_link和那些具有相同item_name的域串起來.如果P非空，則遞歸調用 insert_tree(P，N).

3 實驗分析

為了進一步驗證算法的有效性、可行性以及針對性，用 PentiumIV-2.0G CPU，512M 內存，Windows XP操作系統，DBMS為ORACLE 9i，用VC++實現了NCFP-Construct算法和頻繁模式挖掘算法FP-growth，并同時實現了 FPN_tree 算法[9]，對其效率做了比較，結果如圖1和圖2所示。采用隨機生成數據作為實驗數據，其屬性數量設定為100，|D|表示事物數據記錄的數目;|T|表示事物數據記錄的平均長度;|I|表示最大頻繁項目集的平均長度;|L|表示最大頻繁項目集的數目;N表示事物項目集的個數。在實驗中，N=1 000，|L|=2 000，|D1|=10 000，|D2|=30 000，|T|=20，|I|=10，實驗結果如圖1、圖 2所示。從圖1、2可看出:NCFP-Construct算法與FPN_tree算法相比，效率有了近50%的提高，說明NCFP-Construct是可行的、有效的。

圖1 |D1|=10 000的實驗結果Fig.1 The experimental results including 10 000 records

圖2 |D2|=30 000的實驗結果Fig.2 The experimental results including 30 000 records

文獻[9]中雖然也采用FP-Tree來構造包含正負項目集的頻繁模式樹，但由于沒有考慮用戶的興趣度，導致生成的FP-Tree非常龐大，效率太低，而且從其樹上提取的關聯規則沒有針對性。本文算法在充分考慮用戶感興趣模式的基礎上，彌補了文獻[9]算法的不足，不僅提高了近50%的效率，而且僅生成用戶感興趣模式，提高了針對性。

4 結束語

對包含正、負項目的一般化關聯規則進行比較深入地研究，在充分考慮用戶感興趣模式的基礎上，提出了一種采用約束頻繁模式樹的正負關聯規則挖掘方法，給出了包含負項目集的約束頻繁模式樹的構造算法NCFP-Construct，從而提高了關聯規則挖掘結果的針對性，實驗結果顯示該方法是有效的。

[1]AGRAWAL R，IMIELINSKI T，SWAMI A.Mining association rules between sets of items in large databases[C]//Proc of 1th Int Conf on Management of Data，Washington DC，USA，1993:207-216.

[2]劉勇，李建中，高宏.從圖數據庫中挖掘頻繁跳躍模式[J].軟件學報，2010，21(10):2477-2493.

[3]弓秀蓮，趙旭俊，張繼福.基于FP樹的特異關聯規則挖掘算法研究[J].太原科技大學學報，2007，28(6):428-432.

[4]馬洋.恒星光譜數據分類規則挖掘系統研究[J].太原科技大學學報，2011，32(4):269-272.

[5]BRIN S，MOTWANI R，SILVERSTEIN C.Beyond market:Generalizing association rules to correlations[C]//Processing of the ACM SIGMOD Conference 1997.New York:ACM Press，1997:265-276.

[6]SAVASERE A，OMIECINSKI E，NAVATHE S.Mining for Strong Negative Rules for Statistically Dependent Items[C]//Proc of ICDM’02，Maebashi，2002:442-449.

[7]DO TRONG DINH THAC，LAURENT ANNE，TERMIER ALEXANDRE.PGLCM:Efficient parallel mining of closed frequent gradual itemsets[C]//IEEE International Conference on Data Mining，Sydney，Australia，2010:138-147.

[8]ZHOU JIAYI，YU KUNMING，WU BINCHANG.Parallel frequent patters mining algorithm on GPU[C]//Conference Proceedings-IEEE International Conference on Systems，Man and Cybernetics.2010:435-440.

[9]屈百達，陳莉平.一種基于頻繁模式樹的正負關聯規則挖掘算法[J].現代電子技術，2008，271(8):90-94.