一種基于頻繁模式樹的正負關聯規則挖掘算法
2008-04-12 00:00:00屈百達陳莉平
現代電子技術 2008年8期
摘 要：當前關聯規則挖掘主要著眼于正關聯規則，如A→B的關聯規則的挖掘，這種單一的只對正關聯規則的挖掘方式存在嚴重的弊端，他掩蓋了數據之間存在的隱含負關聯規則，進而無法得出一些正關聯規則中某些項目間相互制約的負關聯關系。在關聯規則概念和性質的基礎上提出了基于頻繁模式樹的拓展式的正、負項目的關聯規則挖掘算法，通過對數據庫的遍歷形成前綴鏈表，不僅挖掘包含所有正項目的關聯規則，而且還能夠挖掘出所有包含負項目的關聯規則，不會造成負關聯規則的淹沒。并對算法的效率和可行性進行分析，該算法在描述關聯規則項目間的相互獨立程度上比已有的單一挖掘負項目的關聯規則算法更具優勢。
關鍵詞：關聯規則；正關聯規則；負關聯規則；頻繁模式樹
中圖分類號：TP311文獻標識碼：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
關聯規則是從大量的數據中挖掘出有隱含關系的一種方法，自從文獻［1］提出關聯規則的問題以后，大量的學者對其進行了深入的研究和探討。關聯規則為：設有事件A和B，正關聯規則類似與事件A導致事件B，形如A→B這樣的表達式，他只能使交易數據庫出現的項集發生正面關聯，無法發現數據中隱藏的另一種關系：負關聯關系，事件A導致事件B不發生，即某數據項集A的出現會減少另一數據項集B的出現機會，甚至使得B不出現。但在實際中對負關聯規則的研究卻比較少，然而負關聯規則依然能帶來有價值的規則，這對于決策的作用也是不可忽視的。在商業領域，負關聯規則可以幫助決策者犧牲自身小的利益為代價消弱某些大的商業欺騙以換取更大的利益；在醫療領域中，可以根據某些癥狀的存在與另外一些癥狀的不存在得到某一診斷結果；企業、市場可以通過綜合考慮正、負關聯關系，在銷售、投資時同時考慮一些有利因素和不利因素，迎接更大的挑戰。
盡管在應用中負關聯規則非常重要，但由于研究起步晚且難度較大，負關聯規則的挖掘還沒有能夠出現一種像Apriori[2]那樣成熟，XinDong Wu在文獻\\[35\\]中正式提出負關聯規則的同時還提出一種能同時挖掘正、負關聯規則的算法，在挖掘出正頻繁項集的基礎上考察他們的支持度和興趣度，當他們不滿足閾值要求時再考慮對應的負項集的支持度和興趣度，如果負項集滿足要求，就從中挖掘出包含負項目的關聯規則。這種算法思想無法挖掘出所有包含負項目的頻繁項集，該算法在生成頻繁項目集時會造成丟失。針對以上問題，在包含正、負項目的一般化關聯規則進行了比較深入地研究上，提出一種基于頻繁模式樹混合正、負項目的一般化關聯規則挖掘算法，該算法不僅挖掘包含所有正項目的關聯規則，而且還能夠挖掘出所有包含負項目的關聯規則。
1 負關聯規則挖掘
1.1 單一正關聯規則缺陷
[HTH]例1:[HTSS]假設有5 000個數據集，其中包含事件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是強關聯規則，再考慮A→B，supp(A∪B)＝0.35＞0.2，conf(A→B)=0.58＞0.3，A→B也是強關聯規則，說明由于A的發生B發生的概率反而下降了，因此A和B應該是相互削弱的關系。這與A→B相矛盾。由于conf(A→B)＞conf(A→B)，A→B應該更可靠，因此A和B應該是負相關的的關系。
文獻［35］提出首先考慮正項集，當正項集無法滿足最小支持度和最小信度時再考慮負項集時，然而在例1中按照這種先挖掘正關聯規則再挖掘負關聯規則的做法將會淹沒有效的負關聯規則，進而造成某些潛在負關聯規則的丟失，本文提出基于頻繁模式樹的正負關聯規則平行挖掘算法，同時考慮正項集和負項集。
1.2 負項目
設任務相關的數據D是數據庫事務的集合中有項集A和項集B。形如A→B，A→B，A→B的關聯規則稱為負關聯規則，負的關聯規則的支持度和置信度的定義和正關聯規則相同，只是分別用A和B分別代替了原來的A和B。
首先介紹一個計算支持度計數的定理。
[HTH]定理1 [HTSS] |DB|為事務數據庫中事務的總個數，對任意的負項目A，設他對應的正項目A支持度計數(即在數據庫中出現的次數)為A.count，那么A的支持度為:
A.count=|DB|-A.count(1)
證明：因為A.count＋A.count＝|DB|;所以A.count=|DB|-A.count，這是顯然成立的。
應用該定理，掃描原始數據庫，利用式(1)可以計算出所有負項目的支持度計數，然后將所有支持度計數不小于最小支持度計數minCount的正、負項目合并成一個集合，作為頻繁1項集L1；用正整數記錄正項目，用負整數記錄負項目，并且在頻繁1項集中，將各項按照絕對值的升序排列，如果同時含有絕對值相等的一對正、負項目，按照負項目在對應正項目前一位的原則，形成一個有序序列。
2 含負項目的頻繁模式樹FPN_tree的構造
2.1 基本概念
J.Han等提出一種用頻繁模式樹FP_Tree產生頻繁集的fp_Tree算法，借助與定義對含負項目的頻繁模式樹（frequent pattern tree with negations，FP_Tree）進行如下的定義：
(1) 他由一個根(值為1)、項目前綴子樹(作為根的子女)和一個頻繁項頭表組成。
(2) 每個項目前綴子樹中的節點包括3個域：item，count和first其中item記錄節點表示的項目，他可以是正項目也可以是負項目：count表示該項目出現的頻度；first用于連接樹中同名節點，如果不存在同名節點，則值為“1”。Current表示項目指針，child，parent，Sibling分別表示節點的子，父，和兄結構的指針。
(3) 頻繁項頭表的表項包括2個域：頻繁項目名HEADS:HEADS［i］.item=S［i］.item; HEADS［i］.count=S［i］.count; HEADS［i］.first=NULL。
2.2 算法思想及其方法描述
前綴鏈表遍歷算法的基本思想是將事務數據庫中滿足最小支持度的所有項目看成是鏈表中的各個結點。每條事務看成是從某個結點經若干中間結點到達終結點的路徑。從中找出滿足最小置信度的路徑即為所要發現的正負關聯規則。下面給出了頻繁模式樹FPN_tree構造過程的具體算法：
(1) 第一次遍歷事務數據庫TID，用正整數記錄正項目，用負整數記錄負項目，利用式(1)統計各正項目及其負項目的出現頻率，并計算所有正負項目的支持度。
(2) 將所有支持度計數不小于最小支持度計數minCount的正、負項目合并成一個集合。
(3) 對上述集合的順序進行調整，將各項按照絕對值的升序排列，如果同時含有絕對值相等的一對正、負項目，按照負項目在對應正項目前一位的原則，形成一個有序序列，作為頻繁1項集S1。
(4) 初始化表頭數組HEADS:HEADS［i］.item=S［i］.iten;HEADS［i］.count=S［i］.count；HEADS［i］.first=NULL；
(5) 將重排后各事務T調用函數insert(PL，T，parent)(首次調用時parent為NULL)插至前綴鏈表中。
FPNtree中由于引入了負項目，其構造方法與FPTree有所不同。對于數據庫中的每個事務T，如果某個正頻繁項出現在T中，說明T含有該正頻繁項：如果某個負頻繁項對應的正項目不出現在T中，說明T中隱含有該負頻繁項。構造FPN_tree的主要思想就是將每個事務中包含的正頻繁項和隱含的負頻繁項按照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 應用舉例
假設有表1所示的數據庫DB，最小支持度為3，構造含負項目的頻繁模式樹。
表1 各項目支持度計算[HT6K]
項目abcde-a-b-c-d-e
支持度4311423552[HJ0]
掃描DB，統計各正項的支持度計數，并由式(1)計算負項的支持度計數，結果如表1所示，選出F中支持度大于3的項，選出頻繁項集Ll { a:4，-b:3，b:3-c:5，-d:5 ，e:4}。同時計算所有事務的正負頻繁項1項集，如表2所示。(各節點以item，name，count形式記錄)并依次將各事務中的正、負頻繁項插入到FPN_tree中，如最終得到含負項目的頻繁模式樹如圖1所示。
表2 事務數據庫1及頻繁項[HT6K]
事務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 正負頻繁模式樹
3 從FPN_tree中挖掘包含正、負項目的頻繁項集
一般從頻繁模式樹中挖掘關聯規則只需遍歷事務數據庫2次，第一次形成前綴鏈表，第二次確定某條事務是否與前綴鏈表的一條路徑重合或者部分重合，從而發現關聯規則。第二次遍歷事務數據庫TID，對重排后的每條事務T，若當前事務T完全或部分重合了前綴鏈表的某一路徑，且滿足大于小于minconf約束，就得到關聯規則，本文采用在上述頻繁模式樹的基礎上產生一個條件FP樹，從而挖掘出所有的正負關聯規則。
[HTH]算法2：[HTSS]
算法2建立在算法1所產生的FPNtree上面。他會遞歸調用自己，并且反復調用算法2產生新的FPtree。
輸入：一棵用算法一建立的樹Tree；
輸出：所有的頻繁集。
步驟：
調用FPN_tree (Tree，1)下面是對過程FPgrowth的偽碼描述。
ProcedureFPN_tree (Tree，a)
ifTree只有一條路徑P
then對P中的節點的每一個組合（記為β）做(1)
(1) 產生頻繁集α∪β，并且把他的支持度指定為β中節點的最小支持度。
else對Tree的頭表從表尾到表頭的每一個表項(記為a)做(2)~(5)。
(2) 產生頻繁集β=a∪α，并且支持度為a的支持度。
(3) 建立β的條件模式庫(conditional pattern base)和β的條件樹(conditionalFPtree)Tree2
(4)if Tree2!=。
(5)then調用FPgrowth(Tree2，β)。
從圖1中的表項b出發，首先可以得到一個頻繁集（b:3)。進而得到包含b的所有模式。順著b表項的nodelink域，找到所有b的路徑
接著考慮-b，先得到（-b:3），順著他的nodelink得到2條路徑，
其次從表項e出發，先可以得到一個頻繁集（e:4)。然后，得到包含e的所有模式。順著e表項的nodeink域，找出所有e的路徑
最后考慮-c，先還是得到(-c:5)，順著他的nodelink得到4條路徑，
表3 條件模式庫和FP樹
項條件模式庫條件FP樹
b{(
-b{
e{
a
-d{
-c{
4 算法性能分析
FPN_tree算法與現有的挖掘負項目的關聯規則的算法相比，在性能上主要有以下優點：
(1) 能夠挖掘出所有的負關聯規則：目前大多數含負項目的關聯規則挖掘算法主要通過考慮頻繁正項集的支持度和置信度，當他們不滿足要求時，才考慮對應的負項集。但是對于非正頻繁項而其對應負項頻繁的項集就不能被挖掘出來，因此不能挖掘出所有含負項目的關聯規則。FPN_tree算法將所有的正、負頻繁項壓縮到頻繁模式樹中，從中挖掘所有長度的頻繁項集，所以能挖掘出所有包含正、負項目的關聯規則。
(2) 不會使原始數據庫增大：算法[6，7]為了挖掘出所有含負項目的關聯規則，將所有項目的對應負項目都擴展到原始數據集中，再從中找出頻繁項集，這樣使得本來就龐大的數據庫又擴大了1倍。本文提出的FPN_tree算法只是將頻繁的正、負項目壓縮的頻繁模式樹中，采用這種壓縮結[LL]構存儲負項目以及正項目，有利于使得原始數據庫減小。
(3) 很多挖掘含負項目的關聯規則挖掘算法都是基于Apriori算法，這需要多次掃描數據庫產生大量的候選項集，通過反復掃描數據庫模式匹配來檢查一個很大的候選項集。FPN_tree算法將頻繁項集壓縮到一顆頻繁模式樹，使用模式增長方法挖掘出所有的頻繁項集，從而減少了時間和空間的占用，最終產生出所有滿足條件的正負關聯規則。另外，FPN_tree算法進一步提高了算法的效率，即使會生成矛盾規則，通過規則的致信度的比較，就能夠得出滿足要求的關聯規則。
5 結 語
本文對包含正、負項目的一般化關聯規則進行比較深入地研究，提出一種基于頻繁模式樹的混合正、負項目的關聯規則的FPN_tree算法。該算法將事務數據庫中出現的正項目和隱含的負項目信息映射到內存中進行處理，平行挖掘正負關聯規則。該算法打破了先挖掘正關聯規則，其次再挖掘負關聯規則這種單一的挖掘模式，從而造成重要負關聯規則的丟失。同時該算法在描述關聯規則項目間的相互獨立程度上比已有的單一挖掘負項目的關聯規則算法更具優勢。
參 考 文 獻
［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］左萬利，劉居紅.包含正負屬性的關聯規則及其挖掘［J］.蘭州大學學報:自然科學版，1999，33(8):288292.
作者簡介 屈百達 男，1956年出生，博士研究生，教授。研究方向為現代控制技術與應用、模式識別與數據處理、運籌與決策。
陳莉平 女，1981年出生，陜西漢中人，江南大學在讀碩士研究生。研究方向為數據挖掘、決策支持。
注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文
