一種基于頻繁模式樹的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法
2008-04-12 00:00:00屈百達(dá)陳莉平
現(xiàn)代電子技術(shù) 2008年8期
摘 要：當(dāng)前關(guān)聯(lián)規(guī)則挖掘主要著眼于正關(guān)聯(lián)規(guī)則，如A→B的關(guān)聯(lián)規(guī)則的挖掘，這種單一的只對正關(guān)聯(lián)規(guī)則的挖掘方式存在嚴(yán)重的弊端，他掩蓋了數(shù)據(jù)之間存在的隱含負(fù)關(guān)聯(lián)規(guī)則，進(jìn)而無法得出一些正關(guān)聯(lián)規(guī)則中某些項目間相互制約的負(fù)關(guān)聯(lián)關(guān)系。在關(guān)聯(lián)規(guī)則概念和性質(zhì)的基礎(chǔ)上提出了基于頻繁模式樹的拓展式的正、負(fù)項目的關(guān)聯(lián)規(guī)則挖掘算法，通過對數(shù)據(jù)庫的遍歷形成前綴鏈表，不僅挖掘包含所有正項目的關(guān)聯(lián)規(guī)則，而且還能夠挖掘出所有包含負(fù)項目的關(guān)聯(lián)規(guī)則，不會造成負(fù)關(guān)聯(lián)規(guī)則的淹沒。并對算法的效率和可行性進(jìn)行分析，該算法在描述關(guān)聯(lián)規(guī)則項目間的相互獨立程度上比已有的單一挖掘負(fù)項目的關(guān)聯(lián)規(guī)則算法更具優(yōu)勢。
關(guān)鍵詞：關(guān)聯(lián)規(guī)則；正關(guān)聯(lián)規(guī)則；負(fù)關(guān)聯(lián)規(guī)則；頻繁模式樹
中圖分類號：TP311文獻(xiàn)標(biāo)識碼：B
文章編號：1004-373X(2008)08-090-04
Positive and Negative Association Rules Mining Algorithm Based on FPNtree
QU Baida，CHEN Liping
(Communication and Control Engineering College，Southern Yangtze University，Wuxi，214122，China)
Abstract：In current，association rules mining mainly focuses on positive association rules，as A→B，which has serious disadvantages only to mine positive association rules.It conceals connotative negative association rules among datas，so as not to explain certain items′ restriction relation in positive association rules.Positive and negative association rules mining algorithm based on FPNtree is proposed built on association rules conception and qualities of association rules.Traversing its prefix linked lists which can mine association rules comprising positive items as well as association rules with negative items，not causing negative association rules′ losses.Efficiency and feasibility of algorithm is analysed and has predominance over single algorithm only mining negative association rules in describing indeendence among association rules items.
Keywords：association rules;positive association rules;negative association rules;FPNtree
關(guān)聯(lián)規(guī)則是從大量的數(shù)據(jù)中挖掘出有隱含關(guān)系的一種方法，自從文獻(xiàn)［1］提出關(guān)聯(lián)規(guī)則的問題以后，大量的學(xué)者對其進(jìn)行了深入的研究和探討。關(guān)聯(lián)規(guī)則為：設(shè)有事件A和B，正關(guān)聯(lián)規(guī)則類似與事件A導(dǎo)致事件B，形如A→B這樣的表達(dá)式，他只能使交易數(shù)據(jù)庫出現(xiàn)的項集發(fā)生正面關(guān)聯(lián)，無法發(fā)現(xiàn)數(shù)據(jù)中隱藏的另一種關(guān)系：負(fù)關(guān)聯(lián)關(guān)系，事件A導(dǎo)致事件B不發(fā)生，即某數(shù)據(jù)項集A的出現(xiàn)會減少另一數(shù)據(jù)項集B的出現(xiàn)機會，甚至使得B不出現(xiàn)。但在實際中對負(fù)關(guān)聯(lián)規(guī)則的研究卻比較少，然而負(fù)關(guān)聯(lián)規(guī)則依然能帶來有價值的規(guī)則，這對于決策的作用也是不可忽視的。在商業(yè)領(lǐng)域，負(fù)關(guān)聯(lián)規(guī)則可以幫助決策者犧牲自身小的利益為代價消弱某些大的商業(yè)欺騙以換取更大的利益；在醫(yī)療領(lǐng)域中，可以根據(jù)某些癥狀的存在與另外一些癥狀的不存在得到某一診斷結(jié)果；企業(yè)、市場可以通過綜合考慮正、負(fù)關(guān)聯(lián)關(guān)系，在銷售、投資時同時考慮一些有利因素和不利因素，迎接更大的挑戰(zhàn)。
盡管在應(yīng)用中負(fù)關(guān)聯(lián)規(guī)則非常重要，但由于研究起步晚且難度較大，負(fù)關(guān)聯(lián)規(guī)則的挖掘還沒有能夠出現(xiàn)一種像Apriori[2]那樣成熟，XinDong Wu在文獻(xiàn)\\[35\\]中正式提出負(fù)關(guān)聯(lián)規(guī)則的同時還提出一種能同時挖掘正、負(fù)關(guān)聯(lián)規(guī)則的算法，在挖掘出正頻繁項集的基礎(chǔ)上考察他們的支持度和興趣度，當(dāng)他們不滿足閾值要求時再考慮對應(yīng)的負(fù)項集的支持度和興趣度，如果負(fù)項集滿足要求，就從中挖掘出包含負(fù)項目的關(guān)聯(lián)規(guī)則。這種算法思想無法挖掘出所有包含負(fù)項目的頻繁項集，該算法在生成頻繁項目集時會造成丟失。針對以上問題，在包含正、負(fù)項目的一般化關(guān)聯(lián)規(guī)則進(jìn)行了比較深入地研究上，提出一種基于頻繁模式樹混合正、負(fù)項目的一般化關(guān)聯(lián)規(guī)則挖掘算法，該算法不僅挖掘包含所有正項目的關(guān)聯(lián)規(guī)則，而且還能夠挖掘出所有包含負(fù)項目的關(guān)聯(lián)規(guī)則。
1 負(fù)關(guān)聯(lián)規(guī)則挖掘
1.1 單一正關(guān)聯(lián)規(guī)則缺陷
[HTH]例1:[HTSS]假設(shè)有5 000個數(shù)據(jù)集，其中包含事件A和B，同時包含事件A和B記為A∪B，包含A的有3 000項，包含B的有2 500項，minsup=0.2，minconf＝0.3，supp(A∪B)＝0.25＞0.2，conf(A→B)=0.42＞0.3，得到A→B是強關(guān)聯(lián)規(guī)則，再考慮A→B，supp(A∪B)＝0.35＞0.2，conf(A→B)=0.58＞0.3，A→B也是強關(guān)聯(lián)規(guī)則，說明由于A的發(fā)生B發(fā)生的概率反而下降了，因此A和B應(yīng)該是相互削弱的關(guān)系。這與A→B相矛盾。由于conf(A→B)＞conf(A→B)，A→B應(yīng)該更可靠，因此A和B應(yīng)該是負(fù)相關(guān)的的關(guān)系。
文獻(xiàn)［35］提出首先考慮正項集，當(dāng)正項集無法滿足最小支持度和最小信度時再考慮負(fù)項集時，然而在例1中按照這種先挖掘正關(guān)聯(lián)規(guī)則再挖掘負(fù)關(guān)聯(lián)規(guī)則的做法將會淹沒有效的負(fù)關(guān)聯(lián)規(guī)則，進(jìn)而造成某些潛在負(fù)關(guān)聯(lián)規(guī)則的丟失，本文提出基于頻繁模式樹的正負(fù)關(guān)聯(lián)規(guī)則平行挖掘算法，同時考慮正項集和負(fù)項集。
1.2 負(fù)項目
設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合中有項集A和項集B。形如A→B，A→B，A→B的關(guān)聯(lián)規(guī)則稱為負(fù)關(guān)聯(lián)規(guī)則，負(fù)的關(guān)聯(lián)規(guī)則的支持度和置信度的定義和正關(guān)聯(lián)規(guī)則相同，只是分別用A和B分別代替了原來的A和B。
首先介紹一個計算支持度計數(shù)的定理。
[HTH]定理1 [HTSS] |DB|為事務(wù)數(shù)據(jù)庫中事務(wù)的總個數(shù)，對任意的負(fù)項目A，設(shè)他對應(yīng)的正項目A支持度計數(shù)(即在數(shù)據(jù)庫中出現(xiàn)的次數(shù))為A.count，那么A的支持度為:
A.count=|DB|-A.count(1)
證明：因為A.count＋A.count＝|DB|;所以A.count=|DB|-A.count，這是顯然成立的。
應(yīng)用該定理，掃描原始數(shù)據(jù)庫，利用式(1)可以計算出所有負(fù)項目的支持度計數(shù)，然后將所有支持度計數(shù)不小于最小支持度計數(shù)minCount的正、負(fù)項目合并成一個集合，作為頻繁1項集L1；用正整數(shù)記錄正項目，用負(fù)整數(shù)記錄負(fù)項目，并且在頻繁1項集中，將各項按照絕對值的升序排列，如果同時含有絕對值相等的一對正、負(fù)項目，按照負(fù)項目在對應(yīng)正項目前一位的原則，形成一個有序序列。
2 含負(fù)項目的頻繁模式樹FPN_tree的構(gòu)造
2.1 基本概念
J.Han等提出一種用頻繁模式樹FP_Tree產(chǎn)生頻繁集的fp_Tree算法，借助與定義對含負(fù)項目的頻繁模式樹（frequent pattern tree with negations，F(xiàn)P_Tree）進(jìn)行如下的定義：
(1) 他由一個根(值為1)、項目前綴子樹(作為根的子女)和一個頻繁項頭表組成。
(2) 每個項目前綴子樹中的節(jié)點包括3個域：item，count和first其中item記錄節(jié)點表示的項目，他可以是正項目也可以是負(fù)項目：count表示該項目出現(xiàn)的頻度；first用于連接樹中同名節(jié)點，如果不存在同名節(jié)點，則值為“1”。Current表示項目指針，child，parent，Sibling分別表示節(jié)點的子，父，和兄結(jié)構(gòu)的指針。
(3) 頻繁項頭表的表項包括2個域：頻繁項目名HEADS:HEADS［i］.item=S［i］.item; HEADS［i］.count=S［i］.count; HEADS［i］.first=NULL。
2.2 算法思想及其方法描述
前綴鏈表遍歷算法的基本思想是將事務(wù)數(shù)據(jù)庫中滿足最小支持度的所有項目看成是鏈表中的各個結(jié)點。每條事務(wù)看成是從某個結(jié)點經(jīng)若干中間結(jié)點到達(dá)終結(jié)點的路徑。從中找出滿足最小置信度的路徑即為所要發(fā)現(xiàn)的正負(fù)關(guān)聯(lián)規(guī)則。下面給出了頻繁模式樹FPN_tree構(gòu)造過程的具體算法：
(1) 第一次遍歷事務(wù)數(shù)據(jù)庫TID，用正整數(shù)記錄正項目，用負(fù)整數(shù)記錄負(fù)項目，利用式(1)統(tǒng)計各正項目及其負(fù)項目的出現(xiàn)頻率，并計算所有正負(fù)項目的支持度。
(2) 將所有支持度計數(shù)不小于最小支持度計數(shù)minCount的正、負(fù)項目合并成一個集合。
(3) 對上述集合的順序進(jìn)行調(diào)整，將各項按照絕對值的升序排列，如果同時含有絕對值相等的一對正、負(fù)項目，按照負(fù)項目在對應(yīng)正項目前一位的原則，形成一個有序序列，作為頻繁1項集S1。
(4) 初始化表頭數(shù)組HEADS:HEADS［i］.item=S［i］.iten;HEADS［i］.count=S［i］.count；HEADS［i］.first=NULL；
(5) 將重排后各事務(wù)T調(diào)用函數(shù)insert(PL，T，parent)(首次調(diào)用時parent為NULL)插至前綴鏈表中。
FPNtree中由于引入了負(fù)項目，其構(gòu)造方法與FPTree有所不同。對于數(shù)據(jù)庫中的每個事務(wù)T，如果某個正頻繁項出現(xiàn)在T中，說明T含有該正頻繁項：如果某個負(fù)頻繁項對應(yīng)的正項目不出現(xiàn)在T中，說明T中隱含有該負(fù)頻繁項。構(gòu)造FPN_tree的主要思想就是將每個事務(wù)中包含的正頻繁項和隱含的負(fù)頻繁項按照S1的順序插入到FPN_tree。
insert(PL，T，parent)
{c=getfirstitem(T);if(c=′’′)return;
If(PL=NULL)
{new(PL);PL>item=c;PL>count=1;PL>child=NULL;PL>parent=parent;
PL>sibling=NUILL：
i=location(c);new(q);q>current=PL;q>next=HEADS［i］.first;HEADS［i］.first=q；
insert(PL>child，T=delete(T，c)，PL)}
else
if(PL>item==c){PL>count++;insert(PL>child，T=delete(T，c)，PL);}
if(PL>sibling==NULL)
{new(P);P>item=c;P>count=1;P>child=NULL;P>parent=parent;
p>sibling=PL>sibling；
PL>sibling=P;i=location(c);new(q);q>current=P；
q>next=HEADS［i］.first;HEADS［i］.first=q;insert(P>child，T=delete(T，c).P);}
else insert(PL>sibling，T，parent);}
2.3 應(yīng)用舉例
假設(shè)有表1所示的數(shù)據(jù)庫DB，最小支持度為3，構(gòu)造含負(fù)項目的頻繁模式樹。
表1 各項目支持度計算[HT6K]
項目abcde-a-b-c-d-e
支持度4311423552[HJ0]
掃描DB，統(tǒng)計各正項的支持度計數(shù)，并由式(1)計算負(fù)項的支持度計數(shù)，結(jié)果如表1所示，選出F中支持度大于3的項，選出頻繁項集Ll { a:4，-b:3，b:3-c:5，-d:5 ，e:4}。同時計算所有事務(wù)的正負(fù)頻繁項1項集，如表2所示。(各節(jié)點以item，name，count形式記錄)并依次將各事務(wù)中的正、負(fù)頻繁項插入到FPN_tree中，如最終得到含負(fù)項目的頻繁模式樹如圖1所示。
表2 事務(wù)數(shù)據(jù)庫1及頻繁項[HT6K]
事務(wù)TIDTID1TID2TID3TID4TID5TID6
項目a，b，eb，da，ca，eea，b，e[HJ0]
頻繁項a，b，-c，-d，eb，-ca，-b，-da，-b，-c，-d，-e-b，-c，-d，ea，b，-c，-d，e
圖1 正負(fù)頻繁模式樹
3 從FPN_tree中挖掘包含正、負(fù)項目的頻繁項集
一般從頻繁模式樹中挖掘關(guān)聯(lián)規(guī)則只需遍歷事務(wù)數(shù)據(jù)庫2次，第一次形成前綴鏈表，第二次確定某條事務(wù)是否與前綴鏈表的一條路徑重合或者部分重合，從而發(fā)現(xiàn)關(guān)聯(lián)規(guī)則。第二次遍歷事務(wù)數(shù)據(jù)庫TID，對重排后的每條事務(wù)T，若當(dāng)前事務(wù)T完全或部分重合了前綴鏈表的某一路徑，且滿足大于小于minconf約束，就得到關(guān)聯(lián)規(guī)則，本文采用在上述頻繁模式樹的基礎(chǔ)上產(chǎn)生一個條件FP樹，從而挖掘出所有的正負(fù)關(guān)聯(lián)規(guī)則。
[HTH]算法2：[HTSS]
算法2建立在算法1所產(chǎn)生的FPNtree上面。他會遞歸調(diào)用自己，并且反復(fù)調(diào)用算法2產(chǎn)生新的FPtree。
輸入：一棵用算法一建立的樹Tree；
輸出：所有的頻繁集。
步驟：
調(diào)用FPN_tree (Tree，1)下面是對過程FPgrowth的偽碼描述。
ProcedureFPN_tree (Tree，a)
ifTree只有一條路徑P
then對P中的節(jié)點的每一個組合（記為β）做(1)
(1) 產(chǎn)生頻繁集α∪β，并且把他的支持度指定為β中節(jié)點的最小支持度。
else對Tree的頭表從表尾到表頭的每一個表項(記為a)做(2)~(5)。
(2) 產(chǎn)生頻繁集β=a∪α，并且支持度為a的支持度。
(3) 建立β的條件模式庫(conditional pattern base)和β的條件樹(conditionalFPtree)Tree2
(4)if Tree2!=。
(5)then調(diào)用FPgrowth(Tree2，β)。
從圖1中的表項b出發(fā)，首先可以得到一個頻繁集（b:3)。進(jìn)而得到包含b的所有模式。順著b表項的nodelink域，找到所有b的路徑
接著考慮-b，先得到（-b:3），順著他的nodelink得到2條路徑，
其次從表項e出發(fā)，先可以得到一個頻繁集（e:4)。然后，得到包含e的所有模式。順著e表項的nodeink域，找出所有e的路徑
最后考慮-c，先還是得到(-c:5)，順著他的nodelink得到4條路徑，
表3 條件模式庫和FP樹
項條件模式庫條件FP樹
b{(
-b{
e{
a
-d{
-c{
4 算法性能分析
FPN_tree算法與現(xiàn)有的挖掘負(fù)項目的關(guān)聯(lián)規(guī)則的算法相比，在性能上主要有以下優(yōu)點：
(1) 能夠挖掘出所有的負(fù)關(guān)聯(lián)規(guī)則：目前大多數(shù)含負(fù)項目的關(guān)聯(lián)規(guī)則挖掘算法主要通過考慮頻繁正項集的支持度和置信度，當(dāng)他們不滿足要求時，才考慮對應(yīng)的負(fù)項集。但是對于非正頻繁項而其對應(yīng)負(fù)項頻繁的項集就不能被挖掘出來，因此不能挖掘出所有含負(fù)項目的關(guān)聯(lián)規(guī)則。FPN_tree算法將所有的正、負(fù)頻繁項壓縮到頻繁模式樹中，從中挖掘所有長度的頻繁項集，所以能挖掘出所有包含正、負(fù)項目的關(guān)聯(lián)規(guī)則。
(2) 不會使原始數(shù)據(jù)庫增大：算法[6，7]為了挖掘出所有含負(fù)項目的關(guān)聯(lián)規(guī)則，將所有項目的對應(yīng)負(fù)項目都擴展到原始數(shù)據(jù)集中，再從中找出頻繁項集，這樣使得本來就龐大的數(shù)據(jù)庫又?jǐn)U大了1倍。本文提出的FPN_tree算法只是將頻繁的正、負(fù)項目壓縮的頻繁模式樹中，采用這種壓縮結(jié)[LL]構(gòu)存儲負(fù)項目以及正項目，有利于使得原始數(shù)據(jù)庫減小。
(3) 很多挖掘含負(fù)項目的關(guān)聯(lián)規(guī)則挖掘算法都是基于Apriori算法，這需要多次掃描數(shù)據(jù)庫產(chǎn)生大量的候選項集，通過反復(fù)掃描數(shù)據(jù)庫模式匹配來檢查一個很大的候選項集。FPN_tree算法將頻繁項集壓縮到一顆頻繁模式樹，使用模式增長方法挖掘出所有的頻繁項集，從而減少了時間和空間的占用，最終產(chǎn)生出所有滿足條件的正負(fù)關(guān)聯(lián)規(guī)則。另外，F(xiàn)PN_tree算法進(jìn)一步提高了算法的效率，即使會生成矛盾規(guī)則，通過規(guī)則的致信度的比較，就能夠得出滿足要求的關(guān)聯(lián)規(guī)則。
5 結(jié) 語
本文對包含正、負(fù)項目的一般化關(guān)聯(lián)規(guī)則進(jìn)行比較深入地研究，提出一種基于頻繁模式樹的混合正、負(fù)項目的關(guān)聯(lián)規(guī)則的FPN_tree算法。該算法將事務(wù)數(shù)據(jù)庫中出現(xiàn)的正項目和隱含的負(fù)項目信息映射到內(nèi)存中進(jìn)行處理，平行挖掘正負(fù)關(guān)聯(lián)規(guī)則。該算法打破了先挖掘正關(guān)聯(lián)規(guī)則，其次再挖掘負(fù)關(guān)聯(lián)規(guī)則這種單一的挖掘模式，從而造成重要負(fù)關(guān)聯(lián)規(guī)則的丟失。同時該算法在描述關(guān)聯(lián)規(guī)則項目間的相互獨立程度上比已有的單一挖掘負(fù)項目的關(guān)聯(lián)規(guī)則算法更具優(yōu)勢。
參 考 文 獻(xiàn)
［1］Agrawa1 R，Imielinski T，Swami A.Mining Association Rules between Sets of Items in Large Database［A］.Proceedings of the 1993 ACMSIGMOD Internatlona1 Conference on Management of Data［C］.Washington DC，USA，1993:207216.
［2］Agrawal R，Srikant R.Fast Algorithm for Mining Association rules［A］.In：Proceedings of the 20th International Conference on VIDB［C］.Santiago，Chile:1994:487499.
［3］Wu X，Zhang C，Zhang S.Mining both Positive and Negative Association Rules\\[J\\].In：Proc.of ICML，2002:658665.
［4］Savasere A，Omiecinski E，Navathe S.Mining for Strong Negative Associations in a Large Database of Customer Transactions［C］.Proceedings of IEEE 14th Intl.Conference on Data Engineering，1998.
［5］WeiGuang Teng，MingJyh Hsieh，MingSyan Chen.On the Mining of Substitution Rules for Statistically Dependent Items［C］.Data Mining，ICDM，Proceedings 2002IEEE International Conference，2002.
［6］JeanFranqois Baulicaut，Artur Bykowski，Baptiste Jeud.Towards the Tractable Discovery of Association Rules with Negations ［C］.FQAS′00，2000:425434.
［7］左萬利，劉居紅.包含正負(fù)屬性的關(guān)聯(lián)規(guī)則及其挖掘［J］.蘭州大學(xué)學(xué)報:自然科學(xué)版，1999，33(8):288292.
作者簡介 屈百達(dá) 男，1956年出生，博士研究生，教授。研究方向為現(xiàn)代控制技術(shù)與應(yīng)用、模式識別與數(shù)據(jù)處理、運籌與決策。
陳莉平 女，1981年出生，陜西漢中人，江南大學(xué)在讀碩士研究生。研究方向為數(shù)據(jù)挖掘、決策支持。
注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文
