一種挖掘負(fù)關(guān)聯(lián)規(guī)則的有效方法

張雅芬，王 新

(云南民族大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，云南昆明650500)

1 問題概述

傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法是依賴于支持度和置信度來挖掘的，它最初是由Agrawal等于1993年提出來的［1-2］，經(jīng)典的Apriori算法也被同時(shí)提出.關(guān)聯(lián)規(guī)則的任務(wù)就是挖掘出同時(shí)滿足支持度和置信度最小閾值的規(guī)則.

下面來看一個(gè)例子［3-4］，希望分析愛喝咖啡和愛喝茶的人之間的關(guān)系.收集一組人關(guān)于飲料偏愛的信息，并匯總在表1中.

表1 1 000個(gè)人的飲料偏愛

支持度s=喝茶同時(shí)喝咖啡的人數(shù)/總?cè)藬?shù)=150/1 000=15%，置信度c=喝茶同時(shí)喝咖啡的人數(shù)/喝茶的人數(shù)=150/200=75%.發(fā)現(xiàn)該條規(guī)則的支持度和置信度都很高，似乎喜歡喝茶的人也喜歡喝咖啡.但是再仔細(xì)觀察表中的數(shù)據(jù)可以發(fā)現(xiàn)，不管他是否喝茶，喝咖啡的人的比例為800/1 000=80%，而喝咖啡的飲茶者卻只占75%.這說明一個(gè)人如果喝茶，則他喝咖啡的可能性由80%下降到75%.從該實(shí)例中可以發(fā)現(xiàn)置信度的缺陷在于該度量忽略了規(guī)則后件中項(xiàng)集的支持度.更奇怪的是喝咖啡的飲茶者所占的比例75%實(shí)際少于所有喝咖啡的人所占的比例80%，這表明飲茶者和喝咖啡的人之間存在著一種逆關(guān)系，這也是種關(guān)聯(lián)規(guī)則，只是它是一種負(fù)相關(guān)［4］，稱之為負(fù)關(guān)聯(lián)規(guī)則，與之相對(duì)的傳統(tǒng)關(guān)聯(lián)規(guī)則即為正關(guān)聯(lián)規(guī)則.

在上述實(shí)例中發(fā)現(xiàn)基于這種框架的關(guān)聯(lián)規(guī)則挖掘存在一定的缺陷和局限性，在挖掘過程中，將會(huì)丟失許多有價(jià)值的信息，從而給決策者帶來一定的誤導(dǎo).因此在挖掘過程中，需要重視負(fù)關(guān)聯(lián)規(guī)則的挖掘.例如在購(gòu)物籃分析中，負(fù)關(guān)聯(lián)規(guī)則表明顧客購(gòu)買某些商品有可能就不購(gòu)買某些商品，這對(duì)決策者設(shè)計(jì)商店布局有一定的導(dǎo)向性;在投資、營(yíng)銷或者廣告策劃等諸多領(lǐng)域的決策過程中，負(fù)關(guān)聯(lián)規(guī)則同樣有著不容忽視的作用.

對(duì)于負(fù)關(guān)聯(lián)規(guī)則的研究，最初是由Brin等在文獻(xiàn)［5］中提出2個(gè)頻繁項(xiàng)集間的負(fù)相關(guān);Savasere等在文獻(xiàn)［6］中研究了強(qiáng)負(fù)關(guān)聯(lián)規(guī)則問題;WU Xindong等［7］提出一種PR模型.之后許多學(xué)者研究關(guān)于負(fù)關(guān)聯(lián)規(guī)則算法以及改進(jìn)，如文獻(xiàn)［8-9］.本文提出了一種結(jié)合相關(guān)系數(shù)和最小興趣度2個(gè)度量的負(fù)關(guān)聯(lián)規(guī)則算法，其中相關(guān)系數(shù)用以識(shí)別關(guān)聯(lián)規(guī)則是正規(guī)則還是負(fù)規(guī)則，比較方便簡(jiǎn)單，避免了對(duì)決策者的誤導(dǎo);最小興趣度保證了所挖掘產(chǎn)生的負(fù)關(guān)聯(lián)規(guī)則的有效性，避免了大量冗余的規(guī)則產(chǎn)生，給決策者帶來一定的導(dǎo)向性.并且通過實(shí)驗(yàn)證明該算法是有效的.

2 負(fù)關(guān)聯(lián)規(guī)則的相關(guān)知識(shí)

負(fù)關(guān)聯(lián)規(guī)則指的是在2個(gè)項(xiàng)集之間的互斥或否定關(guān)系，其形如A??B，?A?B，?A??B，其中?A，?B分別表示交易中不含有A，B．如在商場(chǎng)中A表示購(gòu)買茶葉，B表示購(gòu)買咖啡，則?A表示不購(gòu)買茶葉，?B表示不購(gòu)買咖啡，因此A??B表示顧客購(gòu)買茶葉則不會(huì)購(gòu)買咖啡的相關(guān)規(guī)則，此即為一條負(fù)關(guān)聯(lián)規(guī)則.下面給出負(fù)關(guān)聯(lián)規(guī)則的相關(guān)定義，其中min_sup為最小支持度閾值，min_conf為最小置信度閾值：

定義1 對(duì)于給定的項(xiàng)集A，B其中A∩B=?，A，B之間共有8種關(guān)聯(lián)規(guī)則，如下所示：

其中⑤～⑧和①～④是對(duì)應(yīng)的，其中①和⑤稱為正關(guān)聯(lián)規(guī)則，②～④稱為負(fù)關(guān)聯(lián)規(guī)則．因此在本文中主要討論負(fù)關(guān)聯(lián)規(guī)則②～④．

定義2 一個(gè)有意義的負(fù)關(guān)聯(lián)規(guī)則必須滿足以下3個(gè)條件：

① A∩B=?;

② sup(A)≥min_sup且sup(B)≥min_sup;

③ sup(A∪?B)≥min_sup或者sup(?A∪B)≥min_sup或者sup(?A∪?B)≥min_sup．

對(duì)于負(fù)關(guān)聯(lián)規(guī)則支持度和置信度計(jì)算可以參考文獻(xiàn)［10］．下面將根據(jù)負(fù)關(guān)聯(lián)規(guī)則的支持度和置信度的計(jì)算方法求解上述例子的相關(guān)度量．為簡(jiǎn)單起見，茶事務(wù)用t表示，咖啡事務(wù)用c表示，則對(duì)于該實(shí)例中的負(fù)關(guān)聯(lián)規(guī)則形式如下：t→? c，? t→c，? t→? c．則可以得出：

① sup(t→c)=0．15，conf(t→c)=0．75．

② sup(t→? c)=0．05，sup(? t→c)=0．65，sup(? t→? c)=0．15;

③ conf(t→? c)=0．25，conf(? t→c)=0．812 5，conf(? t→? c)=0．187 5．

可以假設(shè)最小支持度閾值min_sup=0.15，最小置信度閾值min_conf=0.55.很容易得到?t→c是1條強(qiáng)負(fù)關(guān)聯(lián)規(guī)則.這意味著不飲茶者會(huì)可能提高喝咖啡的可能性.此時(shí)出現(xiàn)的矛盾是：到 底是還是通過對(duì)本文中提到的例子進(jìn)行分析可知它是一個(gè)負(fù)相關(guān)，并且是一個(gè)強(qiáng)負(fù)關(guān)聯(lián)規(guī)則，與強(qiáng)正關(guān)聯(lián)規(guī)則相對(duì)［10］.

3 負(fù)關(guān)聯(lián)規(guī)則的識(shí)別和有效性

本文提出的算法基于相關(guān)系數(shù)和最小興趣度，其中相關(guān)系數(shù)用以識(shí)別關(guān)聯(lián)規(guī)則是正規(guī)則還是負(fù)規(guī)則，避免了對(duì)決策者的誤導(dǎo);最小興趣度保證了所挖掘產(chǎn)生的負(fù)關(guān)聯(lián)規(guī)則的有效性，避免了大量冗余的規(guī)則產(chǎn)生.

3.1 相關(guān)系數(shù)

設(shè)隨機(jī)變量X，Y的相關(guān)系數(shù)［11］或者標(biāo)準(zhǔn)協(xié)方差為記為 ρXY．其中 D(X)，D(Y)為變量 X，Y的標(biāo)準(zhǔn)差．Cov(X，Y)為X，Y的協(xié)方差．一般地當(dāng)ρXY=0時(shí)，稱X與Y不相關(guān);當(dāng)0＜ρXY≤1，則變量X與Y正相關(guān)，表明隨機(jī)變量Y隨X的增大而增大;當(dāng)-1≤ρXY＜0，則變量X與Y充分負(fù)相關(guān)，表明隨機(jī)變量Y隨X的增大而減少．

4 算法描述

在上述的例子中，不難發(fā)現(xiàn)并不是所有的頻繁項(xiàng)集產(chǎn)生的規(guī)則都是有趣的.因此在挖掘規(guī)則的過程中加入了最小興趣度，對(duì)規(guī)則的產(chǎn)生進(jìn)行了剪枝，從而在一定程度上減少了搜索空間和存儲(chǔ)空間.在此算法中假設(shè)頻繁項(xiàng)集已經(jīng)產(chǎn)生.算法如下：

輸入：L：頻繁項(xiàng)集;min_conf為最小置信度;min_interest為最小興趣度;ρ是相關(guān)系數(shù)的值;

輸出：INAR(有趣負(fù)關(guān)聯(lián)規(guī)則的集合)。

1)初始化INAR=?;

2)計(jì)算相關(guān)系數(shù)

for each itemset I in L，I=A∪B?L and A∩B=? do{

① ρ=correlation(A，B)

② if-1≤ρ＜0 then

{

if conf(A→?B)≥min_conf and(sup(A∪? B)-sup(A)sup(?B))≥min_interest then

INAR=INAR∪{A→?B};

if conf(? A→B)≥min_conf and(sup(? A∪B)-sup(? A)sup(B))≥min_interest then

INAR=INAR∪{? A→B};

}

if 0＜ρ≤1 then

{

if conf(? A→? B)≥min_conf and(sup(? A∪? B)-sup(? A)sup(? B))≥min_interest then;

INAR=INAR∪{? A→? B};

}

}

3)return INAR.

算法中步驟2)通過計(jì)算相關(guān)系數(shù)，并且如果滿足最小興趣度的值，此時(shí)才產(chǎn)生規(guī)則，并且產(chǎn)生的規(guī)則是用戶感興趣的.包括①計(jì)算相關(guān)系數(shù);②滿足相關(guān)系數(shù)條件和最小興趣度的值，輸出形如A→?B，?A→B，?A→?B的有趣的負(fù)關(guān)聯(lián)規(guī)則;步驟3)返回結(jié)果INAR，結(jié)束整個(gè)算法.

表2 事務(wù)數(shù)據(jù)集

表3 關(guān)聯(lián)規(guī)則數(shù)比較

5 實(shí)驗(yàn)

為了證明算法的有效性，考慮如表2所示的小型事務(wù)交易表［7］，其中包括10條交易數(shù)據(jù)和6個(gè)項(xiàng).表中TID表示每條交易的標(biāo)識(shí)符號(hào)，分別用 T1，T2，…，T10表示;表中的 A，B，…，F(xiàn)等分別表示每條交易所包含的對(duì)象．若以購(gòu)物籃事務(wù)為例，如A，B，D表示的是顧客購(gòu)買的商品的集合.具體的實(shí)驗(yàn)是基于Matlab的仿真效果.一般設(shè)min_sup=0.2，min_conf=0.40.表3中列出了本文算法與經(jīng)典的Apriori算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較.

從表3中可以發(fā)現(xiàn)，經(jīng)典Apriori算法得到正關(guān)聯(lián)規(guī)則數(shù)是24，但無法發(fā)現(xiàn)負(fù)關(guān)聯(lián)規(guī)則的存在;而通過本文的算法可以直接得到負(fù)關(guān)聯(lián)規(guī)則數(shù)，正關(guān)聯(lián)規(guī)則在運(yùn)行中不出現(xiàn)，從而節(jié)省了一定的存儲(chǔ)空間.同時(shí)根據(jù)表中所顯示的當(dāng)min_interest取0和0.05時(shí)，負(fù)關(guān)聯(lián)規(guī)則數(shù)由39減少到12，被刪除的負(fù)關(guān)聯(lián)規(guī)則數(shù)明顯增多，這說明提高最小興趣度能夠減少一些無意義的規(guī)則出現(xiàn)，刪除了一些無意義的負(fù)關(guān)聯(lián)規(guī)則數(shù)目，使得剩余的規(guī)則數(shù)目減少了，便于用戶從中選擇有意義的規(guī)則，從而保證了挖掘出來的負(fù)關(guān)聯(lián)規(guī)則是用戶感興趣的，提高了負(fù)關(guān)聯(lián)規(guī)則的挖掘的效率，因此此算法是有效的.

6 結(jié)語

本文通過實(shí)例引出傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法在挖掘過程中存在的問題，將興趣度和相關(guān)系數(shù)兩者進(jìn)行結(jié)合，從一定程度上減少了大量無趣的負(fù)關(guān)聯(lián)規(guī)則的產(chǎn)生.但是此種方法在一定程度上還存在一定的局限性，后將作進(jìn)一步完善.

［1］ AGRAWAL R.Mining association rules between sets of items in large database［C］//Proceeding of the 1993 ACM SIGM OD International Conference on Management of Data.New York：ACM Press，1993：207-216.

［2］AGRAWAL R，SRIKANT R.Fast algorithms for mining association rules［C］//Proceeding of the 20th VLDB Conference.Santiago：Morgan Kaufmann，1994：487-499.

［3］ CORNELIS C，YAN Peng，ZHANG Xing，et al.Minning postive and negative association rules from large databases［C］//2006 IEEE Conference on CIS.Bangkol：IEEE，2006：613-618.

［4］TAN Pangning，STEINBACH M，KUMAR V.數(shù)據(jù)挖掘?qū)д摚跰］.范明，范宏建，譯.北京：人民郵電出版社，2006.

［5］ BRIN S，MOTWANI R，SILVERSTEIN C.Beyond market baskets：Generalizing association rules to correlations［C］//Processing of the ACM SIGMOD Conference.New York：ACM，1997：265-276.

［6］ SAVASERE A，OMIECINSKI E，NAVATHE S.Mining for strong negative association in a large database of customer transation［C］//In：Proceedings of the 1998 International Conference on Data Engineering.Orlando：IEEE，1998：494-502.

［7］ WU Xindong，ZHANG C，ZHANG S.Mining both positive and negative associations rules［C］//Proceedings of the 19th ICML.New York：Springer Verlag，2002：658-665.

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

［9］董祥軍，宋瀚濤，姜合.基于最小興趣度的正、負(fù)關(guān)聯(lián)規(guī)則挖掘［J］.計(jì)算機(jī)工程與應(yīng)用，2004，24(2)：24-27.

［10］汪際和，陳平，王新.一種基于信息表的關(guān)聯(lián)規(guī)則挖掘方法［J］.云南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，19(6)：432-434.

［11］陳榮江.概率論與數(shù)理統(tǒng)計(jì)［M］.北京：北京大學(xué)出版社，2006.

［12］ SHAIRO P.Discovery，analysis，and presentation of strong rules［C］//G Piatetsky Shapiro，W Frawley eds.Knowledge discovery in Databases.AAAI Press/MIT Press，1991：229-248.