張雅芬，王 新

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

1 問題概述

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

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

表1 1 000個人的飲料偏愛

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

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

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

2 負關聯(lián)規(guī)則的相關知識

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

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

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

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

① 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．

對于負關聯(lián)規(guī)則支持度和置信度計算可以參考文獻［10］．下面將根據(jù)負關聯(lián)規(guī)則的支持度和置信度的計算方法求解上述例子的相關度量．為簡單起見，茶事務用t表示，咖啡事務用c表示，則對于該實例中的負關聯(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．

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

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

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

3.1 相關系數(shù)

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

4 算法描述

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

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

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

1)初始化INAR=?;

2)計算相關系數(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)通過計算相關系數(shù)，并且如果滿足最小興趣度的值，此時才產生規(guī)則，并且產生的規(guī)則是用戶感興趣的.包括①計算相關系數(shù);②滿足相關系數(shù)條件和最小興趣度的值，輸出形如A→?B，?A→B，?A→?B的有趣的負關聯(lián)規(guī)則;步驟3)返回結果INAR，結束整個算法.

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

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

5 實驗

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

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

6 結語

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

［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ù)挖掘導論［M］.范明，范宏建，譯.北京：人民郵電出版社，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］張倩，王治和，張國治.基于相關系數(shù)的正、負關聯(lián)規(guī)則挖掘算法［J］.陜西理工學院學報，2005，21(4)：35-38.

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

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

［11］陳榮江.概率論與數(shù)理統(tǒng)計［M］.北京：北京大學出版社，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.