亓文娟

(武夷學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，福建 武夷山 354300)

0 引言

關(guān)聯(lián)規(guī)則(association rule)是數(shù)據(jù)挖掘(data mining)研究的主要領(lǐng)域之一，用于發(fā)現(xiàn)大型數(shù)據(jù)集中項(xiàng)集之間有趣的聯(lián)系．傳統(tǒng)的關(guān)聯(lián)規(guī)則只關(guān)注于挖掘出項(xiàng)集間的正關(guān)聯(lián)規(guī)則，即形如“購(gòu)買(mǎi)了香煙也會(huì)購(gòu)買(mǎi)啤酒”這樣的規(guī)則，而忽視了“購(gòu)買(mǎi)香煙不會(huì)購(gòu)買(mǎi)啤酒”這樣的負(fù)關(guān)聯(lián)規(guī)則，但在實(shí)際應(yīng)用中，負(fù)關(guān)聯(lián)規(guī)則同樣隱含著有價(jià)值的信息，反映了完全不同的決策問(wèn)題，在許多領(lǐng)域，正、負(fù)關(guān)聯(lián)規(guī)則一起為正確決策提供更加全面的信息，其作用不可低估．

1 相關(guān)概念

設(shè)I=[i1,i2,,i3,…in]項(xiàng)的集合，事務(wù)數(shù)據(jù)集D，對(duì)于每個(gè)事務(wù)T滿足T?I．每個(gè)事務(wù)表示符TID．對(duì)于項(xiàng)集A?I，B?I，A∩B=?，A,B間共有8種形式的關(guān)聯(lián)規(guī)則：

(1)A→B；(2)A→B；(3)A→B；(4)A→B；(5)B→A；(6)B→A；(7)B→A；(8)B→A；

對(duì)于前4種關(guān)聯(lián)規(guī)則，稱(1)為正關(guān)聯(lián)規(guī)則，(2)～(4)為負(fù)關(guān)聯(lián)規(guī)則，其中規(guī)則A→B表示項(xiàng)集A的出現(xiàn)會(huì)抑制項(xiàng)集B的出現(xiàn)，規(guī)則A→B表示項(xiàng)集A不出現(xiàn)會(huì)誘導(dǎo)項(xiàng)集B的出現(xiàn)，規(guī)則A→B表示項(xiàng)集A的不出現(xiàn)會(huì)抑制項(xiàng)集B的出現(xiàn)．規(guī)則(5)～(8)與(1)～(4)相對(duì)應(yīng)，本文不予討論．

針對(duì)事務(wù)數(shù)據(jù)集D，項(xiàng)集A和B同時(shí)出現(xiàn)的事務(wù)數(shù)與所有事務(wù)數(shù)的比值稱為規(guī)則A→B的支持度，即

Sup(A→B)=|A∪B|/|D|，

項(xiàng)集A和B同時(shí)出現(xiàn)的事務(wù)數(shù)與包含A的事務(wù)數(shù)的比值稱為規(guī)則A→B的置信度，即

Conf(A→B)=|A∪B|/|A|．

則對(duì)于規(guī)則A→B來(lái)說(shuō)表示事務(wù)數(shù)據(jù)集D中有(100×Sup)%的事務(wù)包含項(xiàng)集A但不包含項(xiàng)集B，包含A的事務(wù)中有(100×Conf)%的事務(wù)不包含項(xiàng)集B．

2 負(fù)關(guān)聯(lián)規(guī)則概述

2.1 支持度和置信度

負(fù)關(guān)聯(lián)規(guī)則表示項(xiàng)集之間的否定聯(lián)系，由于它含有不存在的項(xiàng)集(A或B)的特殊性，根據(jù)概率論的有關(guān)知識(shí)，可以利用正項(xiàng)集的支持度得到負(fù)關(guān)聯(lián)規(guī)則的支持度[1]：

(2)sup(A→B)=sup(A)-sup(A∪B)；

同理得到負(fù)關(guān)聯(lián)規(guī)則的置信度：

(1)conf(A→B)=

=1-conf(A→B)；

它們之間存在如下的關(guān)系：

(1)conf(A→B)+conf(A→B)=1；

2.2 “支持度—置信度”架構(gòu)的局限性

目前評(píng)價(jià)關(guān)聯(lián)規(guī)則的主要標(biāo)準(zhǔn)是支持度和置信度閾值,盡管通過(guò)這兩個(gè)參數(shù)可以有效的剪掉一些無(wú)意義的規(guī)則，但在實(shí)際應(yīng)用中僅按此準(zhǔn)則來(lái)挖掘是不夠的．

假設(shè)某超市交易數(shù)據(jù)庫(kù)中顧客一次購(gòu)買(mǎi)煙酒的情況如表1所示，最小支持度和最小置信度分別為0.3和0.6．那么“購(gòu)買(mǎi)啤酒→購(gòu)買(mǎi)香煙”的支持度Sup=400/1000=0.4，置信度Conf=400/600=0.67，該規(guī)則是強(qiáng)關(guān)聯(lián)規(guī)則，說(shuō)明購(gòu)買(mǎi)啤酒的顧客通常也會(huì)購(gòu)買(mǎi)香煙，然而事實(shí)上 “不購(gòu)買(mǎi)啤酒→購(gòu)買(mǎi)香煙”的可能性為350/400=87.5%，這就說(shuō)明購(gòu)買(mǎi)啤酒的顧客會(huì)購(gòu)買(mǎi)香煙的可能性小于不購(gòu)買(mǎi)啤酒的顧客購(gòu)買(mǎi)香煙的可能性，到底是“購(gòu)買(mǎi)啤酒→購(gòu)買(mǎi)香煙”還是“不購(gòu)買(mǎi)啤酒→購(gòu)買(mǎi)香煙”，對(duì)于正負(fù)關(guān)聯(lián)規(guī)則中相互矛盾規(guī)則的出現(xiàn)，顯然是由“支持度—置信度”不合理的評(píng)價(jià)標(biāo)準(zhǔn)產(chǎn)生的．

表1 某超市交易數(shù)據(jù)庫(kù)煙酒銷售情況

2.3 項(xiàng)集的相關(guān)性

通過(guò)上面的例子可以看出，在支持度—置信度架構(gòu)的基礎(chǔ)上生成的很多關(guān)聯(lián)規(guī)則不僅沒(méi)有實(shí)用價(jià)值，甚至是有誤導(dǎo)性和錯(cuò)誤的，所以說(shuō)強(qiáng)關(guān)聯(lián)規(guī)則不一定是有趣的．為了避免正負(fù)關(guān)聯(lián)規(guī)則中矛盾規(guī)則的出現(xiàn)，根據(jù)相關(guān)性挖掘數(shù)據(jù)項(xiàng)之間有趣的聯(lián)系．

CorrA,B表示項(xiàng)集A和項(xiàng)集B的興趣度，取值范圍是[0，+∞)，取值分3種情況：如果CorrA,B>1,則A、B是正相關(guān)的，表示A的出現(xiàn)提升了B的出現(xiàn)，取值范圍是(1，+∞),CorrA,B的值越大，兩者的關(guān)聯(lián)程度越高；如果CorrA,B<1,則A、B是負(fù)相關(guān)的,表示A的出現(xiàn)降低了B的出現(xiàn)，取值范圍是(0，1)；如果CorrA,B=1，說(shuō)明A、B相互獨(dú)立，沒(méi)有相關(guān)性．

針對(duì)表1中的數(shù)據(jù)，“購(gòu)買(mǎi)啤酒→購(gòu)買(mǎi)香煙”的相關(guān)性為：sup(購(gòu)買(mǎi)啤酒)=600/1000=0.6,sup(購(gòu)買(mǎi)香煙)=750/1000=0.75，sup(購(gòu)買(mǎi)啤酒和香煙)=400/1000=0.4,則興趣度=0.4/(0.6*0.75)=0.89 <1,所以購(gòu)買(mǎi)啤酒和購(gòu)買(mǎi)香煙之間是負(fù)相關(guān)的，說(shuō)明顧客購(gòu)買(mǎi)啤酒不但不會(huì)提升香煙的銷量，反而會(huì)減少．不難證明項(xiàng)集A，B間4種形式關(guān)聯(lián)規(guī)則的相關(guān)性之間存在以下關(guān)系：如果興趣度CorrA,B>1，則有興趣度Corr<1；興趣度CorrA,B<1；興趣度Corr>1；反之亦反之，因此在進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)，只要對(duì)項(xiàng)集的相關(guān)性進(jìn)行判斷，就可以避免在關(guān)聯(lián)規(guī)則挖掘時(shí)正負(fù)矛盾規(guī)則的出現(xiàn)，也就是說(shuō)當(dāng)興趣度CorrA,B>1時(shí)僅挖掘A→B和A→B型關(guān)聯(lián)規(guī)則，當(dāng)興趣度CorrA,B<1時(shí)僅挖掘A→B和A→B型關(guān)聯(lián)規(guī)則，當(dāng)興趣度CorrA,B=1時(shí)A、B無(wú)相關(guān)性，不需要挖掘．

Tetsky-Shapiro提出，如果sup(A∪B)≈sup(A)sup(B)或sup(A∪B)/sup(A)sup(B)≈1,則A、B近似獨(dú)立，規(guī)則A→B無(wú)趣．

CorrA,B=sup(A∪B)-sup(A)sup(B)[3]

CorrA,B取值范圍是(-0.25，+0.25),取值分3種情況：如果CorrA,B>0,則A、B是正相關(guān)的；如果CorrA,B<0,則A、B是負(fù)相關(guān)的；如果CorrA,B=0,則A、B沒(méi)有相關(guān)性；計(jì)算興趣度=0.4-0.6*0.75=-0.05<0,同樣得知購(gòu)買(mǎi)啤酒和購(gòu)買(mǎi)香煙之間是負(fù)相關(guān)關(guān)系．

2.4 四種關(guān)聯(lián)規(guī)則間的置信度關(guān)系研究

當(dāng)同時(shí)研究項(xiàng)集A、B間的正、負(fù)關(guān)聯(lián)規(guī)則(A→B、、A→B、A→B、及A→B)時(shí)，置信度該如何設(shè)置的問(wèn)題變得非常重要．四種關(guān)聯(lián)規(guī)則間支持度和置信度之間有著怎樣的聯(lián)系呢？當(dāng)A，B的支持度變化時(shí)，規(guī)則的置信度是如何變化的呢？為了方便討論，假設(shè)s(A)，s(B)很小時(shí)取值0.1，很大時(shí)取值0.9，下面按四種情況分別進(jìn)行討論[4]．

(1)sup(A)，sup(B)都很小

conf(A→B)的值域是[0，1]；conf(A→B)的值域是[0，1]；conf(A→B)的值域是[0，0.11]；conf(A→B)的值域是[0.89，1]．

(2) sup(A)，sup(B)都很大

conf(A→B)的值域是[0.89，1]；conf(A→B)的值域是[0，0.11]；conf(A→B)的值域是[0，1]；conf(A→B)的值域是[0，1]．

(3) sup(A)很小，sup(B)很大

conf(A→B)的值域是[0，1]；conf(A→B)的值域是[0，1]；conf(A→B)的值域是[0.89，1]；conf(A→B)的值域是[0，0.11]．

(4)sup(A)很大，sup(B)很小

conf(A→B)的值域是[0，0.11]；conf(A→B)的值域是[0.89，1]；conf(A→B)的值域是[0，1]；conf(A→B)的值域是[0，1]．

通過(guò)以上討論，我們得出結(jié)論：當(dāng)同時(shí)研究正、負(fù)關(guān)聯(lián)規(guī)則時(shí)，如何設(shè)置置信度的問(wèn)題變得非常重要，它直接影響到挖掘結(jié)果中關(guān)聯(lián)規(guī)則的數(shù)量，從而影響了用戶選擇所需規(guī)則的難易程度，單一的置信度約束已經(jīng)不能滿足要求，應(yīng)該根據(jù)實(shí)際應(yīng)用為四種形式關(guān)聯(lián)規(guī)則分別設(shè)定置信度；同時(shí)我們發(fā)現(xiàn)四種形式關(guān)聯(lián)規(guī)則的置信度之間存在著制約關(guān)系，在為其設(shè)定置信度時(shí)應(yīng)綜合考慮．

3 負(fù)關(guān)聯(lián)規(guī)則挖掘算法

3.1 基本挖掘算法

目前，負(fù)關(guān)聯(lián)規(guī)則挖掘的兩種基本算法分別是直接Apriori算法和“近似”負(fù)關(guān)聯(lián)規(guī)則算法．直接Apriori算法將事務(wù)集看成是一個(gè)布爾矩陣，從初始的項(xiàng)目集的補(bǔ)集中挖掘正負(fù)關(guān)聯(lián)規(guī)則．假定給定一個(gè)初始項(xiàng)目集的布爾矩陣，它的每一行代表一個(gè)事務(wù)，對(duì)于每一列，增加一個(gè)列，初始項(xiàng)目集的補(bǔ)集將初始項(xiàng)目集的每一個(gè)字節(jié)0、1互換．雖然直接Apriori算法可以挖掘出所有的正、負(fù)頻繁項(xiàng)集，但對(duì)原始數(shù)據(jù)集進(jìn)行了擴(kuò)充，導(dǎo)致擴(kuò)充后的數(shù)據(jù)集比較龐大，大大降低了算法的效率．“近似”負(fù)關(guān)聯(lián)規(guī)則算法首先采用傳統(tǒng)的關(guān)聯(lián)規(guī)則算法挖掘出正關(guān)聯(lián)規(guī)則，然后通過(guò)相關(guān)定理推導(dǎo)出負(fù)關(guān)聯(lián)規(guī)則，由于該算法完全沒(méi)有考慮數(shù)據(jù)集中的非頻繁正項(xiàng)集，挖掘出來(lái)的負(fù)關(guān)聯(lián)規(guī)則數(shù)量是有限的．

3.2 負(fù)關(guān)聯(lián)規(guī)則改進(jìn)算法

負(fù)關(guān)聯(lián)規(guī)則挖掘不僅考慮事務(wù)中包含的項(xiàng)目，還要考慮事務(wù)中不包含的項(xiàng)目，它隱含著非常有價(jià)值的信息，目前很多學(xué)者對(duì)負(fù)關(guān)聯(lián)規(guī)則進(jìn)行深入研究，提出了一些改進(jìn)算法．

文獻(xiàn)[5]提出了一種用于挖掘正、負(fù)關(guān)聯(lián)規(guī)則的Ex_Apriori算法，該算法不僅能挖掘出負(fù)關(guān)聯(lián)規(guī)則，而且在生成規(guī)則的過(guò)程中引入了興趣度，縮小了計(jì)算的復(fù)雜性，刪除了大量無(wú)用的關(guān)聯(lián)規(guī)則；文獻(xiàn)[6]提出了采用鏈表來(lái)實(shí)現(xiàn)正負(fù)關(guān)聯(lián)規(guī)則的挖掘算法PN_MAR，該算法采用二進(jìn)制數(shù)的方式表示事務(wù)是否包含項(xiàng)集中的元素，提高了算法的效率．文獻(xiàn)[7]提出了一種能夠同時(shí)挖掘正負(fù)關(guān)聯(lián)規(guī)則的算法IP_NARM,該算法加入最大支持度來(lái)控制頻繁項(xiàng)集的生成規(guī)模，同時(shí)采用改進(jìn)后的相關(guān)性刪除無(wú)趣的關(guān)聯(lián)規(guī)則；文獻(xiàn)[8]將相關(guān)系數(shù)作為關(guān)聯(lián)規(guī)則生成的判定條件，并給出了基于相關(guān)系數(shù)的正、負(fù)關(guān)聯(lián)規(guī)則挖掘算法PN_AR；文獻(xiàn)[9]文提出了基于兩級(jí)多支持度的2LMS-inFS-FS算法，有效限制了頻繁項(xiàng)集與非頻繁項(xiàng)集的數(shù)量；文獻(xiàn)[10]引入過(guò)頻繁項(xiàng)集的概念，對(duì)項(xiàng)集中負(fù)項(xiàng)目的個(gè)數(shù)進(jìn)行限制，較好的解決了負(fù)關(guān)聯(lián)規(guī)則挖掘中頻繁項(xiàng)集數(shù)量爆炸問(wèn)題；文獻(xiàn)[11]提出了一種負(fù)關(guān)聯(lián)規(guī)則增量更新算法NIUA，該算法大大縮短了掃描事務(wù)數(shù)據(jù)庫(kù)的時(shí)間，但會(huì)產(chǎn)生龐大的非頻繁項(xiàng)集；文獻(xiàn)[12]提出了從數(shù)據(jù)庫(kù)中提取全部負(fù)關(guān)聯(lián)規(guī)則的ANAR算法，通過(guò)對(duì)頻繁模式樹(shù)DFP-tree的建立、剪枝及結(jié)點(diǎn)合并，獲取全部極小非頻繁項(xiàng)集ASI和全部非頻繁項(xiàng)集，同時(shí)采用相關(guān)度作為規(guī)則興趣度量，最終形成全部負(fù)關(guān)聯(lián)規(guī)則．

4 結(jié)論

負(fù)關(guān)聯(lián)規(guī)則同正關(guān)聯(lián)規(guī)則具有同等的重要性，但由于人們對(duì)負(fù)關(guān)聯(lián)規(guī)則的研究起步較晚且難度較大，很多改進(jìn)算法也存在不足之處．本文首先給出了正、負(fù)關(guān)聯(lián)規(guī)則的定義及支持度和置信度的函數(shù)表示，重點(diǎn)分析了關(guān)聯(lián)規(guī)則中“支持度—置信度”架構(gòu)的局限性，提出了利用項(xiàng)集的相關(guān)性來(lái)解決關(guān)聯(lián)規(guī)則中正、負(fù)矛盾規(guī)則出現(xiàn)的問(wèn)題，同時(shí)針對(duì)置信度的設(shè)置進(jìn)行了研究分析，最后對(duì)負(fù)關(guān)聯(lián)規(guī)則挖掘的算法進(jìn)行了討論，旨在為關(guān)聯(lián)規(guī)則的研究奠定基礎(chǔ)．

[1]楊井榮.正負(fù)關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法的研究[D].大連：大連海事大學(xué),2006.

[2]謝文閣,梅紅巖，李 欣，等．基于興趣度的關(guān)聯(lián)規(guī)則在選課分析中的應(yīng)用[J].內(nèi)蒙古大學(xué)學(xué)報(bào)(自然科學(xué)版)，2009，40(2):199～202．

[3]張鐵軍.關(guān)聯(lián)規(guī)則挖掘的相關(guān)問(wèn)題研究[D].西安：西安科技大學(xué)，2009．

[4]董祥軍,陳建斌,崔 林,等.正、負(fù)關(guān)聯(lián)規(guī)則間的置信度關(guān)系研究[J].計(jì)算機(jī)應(yīng)用研究,2005，(7):34～35．

[5]趙海豐,邢永康,楊華麗,等.一種用于挖掘正、負(fù)關(guān)聯(lián)規(guī)則的改進(jìn)Apriori算法[J].計(jì)算機(jī)科學(xué),2006，33(12):242～244．

[6]彭緒山,劉 旸.負(fù)關(guān)聯(lián)規(guī)則挖掘算法的研究與實(shí)現(xiàn).科學(xué)技術(shù)與工程[J].2008，22(8):6127～6129．

[7]王 璇.一種帶興趣度的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法[J].常州工學(xué)院學(xué)報(bào),2011，24(3/4):16～20．

[8]張 倩,王治和,張國(guó)治.基于相關(guān)系數(shù)的正、負(fù)關(guān)聯(lián)規(guī)則挖掘算法[J].陜西理工學(xué)院學(xué)報(bào),2005，21(4):35～38．

[9]李 剛,王洪國(guó),董祥軍,等.基于兩級(jí)多支持度的非頻繁項(xiàng)集挖掘方法[J].鄭州大學(xué)學(xué)報(bào)(理學(xué)版),2007，39(4):94～97．

[10]馬占欣,陸玉昌.負(fù)關(guān)聯(lián)規(guī)則挖掘中的頻繁項(xiàng)集爆炸問(wèn)題[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2007，47(7):1212～1215．

[11]孫寶友,姜 合,趙園園.負(fù)關(guān)聯(lián)規(guī)則增量更新算法[J].計(jì)算機(jī)工程,2009，35(13):69～71．

[12]李 紅,宗 瑜,解浚源.數(shù)據(jù)庫(kù)中全部負(fù)關(guān)聯(lián)規(guī)則挖掘研究[J].計(jì)算機(jī)應(yīng)用與軟件,2011，28(11):105～107．