數(shù)據(jù)挖掘系列關(guān)聯(lián)規(guī)則評價

前面我們討論的關(guān)聯(lián)規(guī)則都是用支持度和自信度來評價的，如果一個規(guī)則的自信度高，我們就說它是一條強規(guī)則，但是自信度和支持度有時候并不能度量規(guī)則的實際意義和業(yè)務(wù)關(guān)注的興趣點。

一個誤導(dǎo)我們的強規(guī)則

看這樣一個例子，我們分析一個購物籃數(shù)據(jù)中購買游戲光碟和購買影片光碟之間的關(guān)聯(lián)關(guān)系。交易數(shù)據(jù)集共有10,000條記錄，其中購買6000條包含游戲光碟，7500條包含影片光碟，4000條既包含游戲光碟又包含影片光碟。數(shù)據(jù)集如下表所示：

假設(shè)我們設(shè)置得最小支持度為30%，最小自信度為60%。從上面的表中，可以得到：support(買游戲光碟—>買影片光碟)=4000/10000=40%，confidence(買游戲光碟—>買影片光碟)=4000/7500*100%=66%（寫錯了，應(yīng)該是4000/6000）。這條規(guī)則的支持度和自信度都滿足要求，因此我們很興奮，我們找到了一條強規(guī)則，于是我們建議超市把影片光碟和游戲光碟放在一起，可以提高銷量。

可是我們想想，一個喜歡的玩游戲的人會有時間看影片么，這個規(guī)則是不是有問題，事實上這條規(guī)則誤導(dǎo)了我們。在整個數(shù)據(jù)集中買影片光碟的概率p(買影片)=7500/10000=75%，而買游戲的人也買影片的概率只有66%，66%<75%恰恰說明了買游戲光碟抑制了影片光碟的購買，也就是說買了游戲光碟的人更傾向于不買影片光碟，這才是符合現(xiàn)實的。

從上面的例子我們看到，支持度和自信度并不能過成功濾掉那些我們不感興趣的規(guī)則，因此我們需要一些新的評價標準，下面介紹六中評價標準：相關(guān)性系數(shù)，卡方指數(shù)，全自信度、最大自信度、Kulc、cosine距離。

相關(guān)性系數(shù)lift

從上面游戲和影片的例子中，我們可以看到游戲和影片不是正相關(guān)的，因此用相關(guān)性度量關(guān)聯(lián)規(guī)則可以過濾這樣的規(guī)則，對于規(guī)則A—>B或者B—>A，lift(A,B)=P(A交B)/(P(A)*P(B))，如果lift(A,B)>1表示A、B呈正相關(guān)，lift(A,B)<1表示A、B呈負相關(guān)，lift(A,B)=1表示A、B不相關(guān)（獨立）。實際運用中，正相關(guān)和負相關(guān)都是我們需要關(guān)注的，而獨立往往是我們不需要的，兩個商品都沒有相互影響也就是不是強規(guī)則，lift(A,B)等于1的情形也很少，一般只要接近于1我們就認為是獨立了。

注意相關(guān)系數(shù)只能確定相關(guān)性，相關(guān)不是因果，所以A—>B或者B—>A兩個規(guī)則的相關(guān)系數(shù)是一樣的，另外lift(A,B)=P(A交B)/(P(A)*P(B))=P(A)*P(B|A)/(P(A)*P(B))=P(B|A)/P(B)=confidence(A—>B)/support(B)=confidence(B—>A)/support(A)。

卡方系數(shù)

卡方分布是數(shù)理統(tǒng)計中的一個重要分布，利用卡方系數(shù)我們可以確定兩個變量是否相關(guān)?？ǚ较禂?shù)的定義:

公式中的observed表示數(shù)據(jù)的實際值,expected表示期望值,不理解沒關(guān)系,我們看一個例子就明白了。

上面表格的括號中表示的是期望值，(買影片，買游戲)的期望值E=6000*(7500/10000)=4500，總體記錄中有75%的人買影片，而買游戲的有6000人，于是我們期望這6000人中有75%(即4500)的人買影片。其他三個值可以類似計算得到?，F(xiàn)在我們計算一下，買游戲與買影片的卡方系數(shù)：

卡方系數(shù)X=(4000-4500)^2/4500+(3500-3000)^2/3000+(2000-1500)^2/1500+(500-1000)^2/1000=555.6。

卡方系數(shù)需要查表才能確定值的意義，基于置信水平和自由度(r-1)*(c-1)=(行數(shù)-1)*(列數(shù)-1)=1，查表得到自信度為(1-0.001)的值為6.63，555.6大于6.63，因此拒絕A、B獨立的假設(shè)，即認為A、B是相關(guān)的，而expected(買影片，買游戲)=4500>4000,因此認為A、B呈負相關(guān)。這里需要一定的概率統(tǒng)計知識。如果覺得不好理解，可以用其他的評價標準。

全自信度

全自信度all_confidence的定義如下：all_confidence(A,B)=P(A交B)/max{P(A),P(B)}

=min{P(B|A),P(A|B)}

=min{confidence(A—>B),confidence(B—>A)}

對于前面的例子，all_confidence(買游戲，買影片)=min{confidence(買游戲—>買影片),confidence(買影片—>買游戲)}=min{66%,53.3%}=53.3%?？梢钥闯鋈孕哦炔皇橐粋€好的衡量標準。

最大自信度

最大自信度則與全自信度相反，求的不是最小的支持度而是最大的支持度，max_confidence(A,B)=max{confidence(A—>B),confidence(B—>A)}，不過感覺最大自信度不太實用。

Kulc

Kulc系數(shù)就是對兩個自信度做一個平均處理：kulc(A,B)=(confidence(A—>B)+confidence(B—>A))/2。，kulc系數(shù)是一個很好的度量標準，稍后的對比我們會看到。

cosine(A,B)

cosine(A,B)=P(A交B)/sqrt(P(A)*P(B))=sqrt(P(A|B)*P(B|A))=sqrt(confidence(A—>B)*confidence(B—>A))

七個評價準則的比較

這里有這么多的評價標準，究竟哪些好，哪些能夠準確反應(yīng)事實，我們來看一組對比。

上表中，M表示購買了牛奶、C表示購買了咖啡,M表示不購買牛奶，C表示不購買咖啡，下面來看6個不同的數(shù)據(jù)集，各個度量標準的值

我們先來看前面四個數(shù)據(jù)集D1-D4，從后面四列可以看出，D1,D2中milk與coffee是正相關(guān)的，而D3是負相關(guān)，D4中是不相關(guān)的，大家可能覺得，D2的lift約等于1應(yīng)該是不相關(guān)的，事實上對比D1你會發(fā)現(xiàn)，lift受MC的影響很大，而實際上我們買牛奶和咖啡的相關(guān)性不應(yīng)該取決于不買牛奶和咖啡的交易記錄，這正是lift和卡方的劣勢，容易受到數(shù)據(jù)記錄大小的影響。而全自信度、最大自信度、Kulc、cosine與MC無關(guān)，它們不受數(shù)據(jù)記錄大小影響?？ǚ胶蚻ift還把D3判別為正相關(guān)，而實際上他們應(yīng)該是負相關(guān)，M=100+1000=1100，如果這1100中有超過550的購買coffee那么就認為是正相關(guān)，而我們看到MC=100<550，可以認為是負相關(guān)的。

上面我們分析了全自信度、最大自信度、Kulc、cosine與空值無關(guān)，但這幾個中哪一個更好呢？我們看后面四個數(shù)據(jù)集D4-D6,all_conf與cosine得出相同的結(jié)果，即D4中milk與coffee是獨立的，D5、D6是負相關(guān)的，D5中support（C-->M）=0.91而support（M-->C）=0.09，這樣的關(guān)系，簡單的認為是負相關(guān)或者正相關(guān)都不妥，Kulc做平均處理倒很好，平滑后認為它們是無關(guān)的，我們再引入一個不平衡因子IR(imbalance ratio):

IR(A,B)=|sup(a)-sup(B)|/(sup(A)-sup(B)-sup(A交B))（注：應(yīng)為(sup(A)+sup(B)-sup(A交B)）

D4總IR(C,M)=0，非常平衡，D5中IR(C,M)=0.89,不平衡，而D6中IR(C,M)=0.99極度不平衡，我們應(yīng)該看到Kulc值雖然相同但是平衡度不一樣，在實際中應(yīng)該意識到不平衡的可能，根據(jù)業(yè)務(wù)作出判斷，因此這里我們認為Kulc結(jié)合不平衡因子的是較好的評價方法。

另外weka中還使用 Conviction和Leverage。Conviction(A,B) = P(A)P(B)/P(AB)， Leverage(A,B) = P(A交B)-P(A)P(B)，Leverage是不受空值影響，而Conviction是受空值影響的。

總結(jié)

本文介紹了9個關(guān)聯(lián)規(guī)則評價的準則，其中全自信度、最大自信度、Kulc、cosine，Leverage是不受空值影響的，這在處理大數(shù)據(jù)集是優(yōu)勢更加明顯，因為大數(shù)據(jù)中想MC這樣的空記錄更多，根據(jù)分析我們推薦使用kulc準則和不平衡因子結(jié)合的方法。