陳 柳，馮 山

(四川師范大學數(shù)學與軟件科學學院，成都610068)(*通信作者電子郵箱634050177@qq．com)

0 引言

關(guān)聯(lián)規(guī)則挖掘(Associated Rule Mining)是重要的數(shù)據(jù)挖掘研究課題。傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘只研究AB型規(guī)則［1－3］。實際上AB、AB和AB型負關(guān)聯(lián)規(guī)則普遍存在，自項集負相關(guān)(Negative Relationship of Itemset)［4］提出以來，其研究得到廣泛關(guān)注［5－15］。正負關(guān)聯(lián)規(guī)則挖掘中，限制規(guī)則數(shù)量和提取真正有趣的規(guī)則是挖掘算法設(shè)計的關(guān)鍵［6］。傳統(tǒng)算法通常采用支持度－置信度框架［1］來達到該目的。但是，當同時挖掘各型正負關(guān)聯(lián)規(guī)則時，使用支持度－置信度框架理論可能會出現(xiàn)相互矛盾的規(guī)則［7］，如AB和AB或AB和AB同時出現(xiàn)。為此，人們引入了相關(guān)性度量對支持度－置信度框架進行擴充和修改以避免其發(fā)生［6－10］。在相關(guān)度－支持度－置信度框架下的正負關(guān)聯(lián)規(guī)則挖掘中，圍繞相關(guān)性度量和支持度閾值設(shè)置的研究已比較完善。文獻［8－9］采用卡方測量項集相關(guān)性。文獻［6－7，10］針對卡方無法判斷項集正相關(guān)還是負相關(guān)的不足，提出采用Lift度量。文獻［11］對比分析了7種相關(guān)性度量方法的內(nèi)在聯(lián)系與區(qū)別，給出了它們各自的適用范圍。文獻［12］提出了約束正負關(guān)聯(lián)規(guī)則挖掘中頻繁項集與非頻繁項集數(shù)量的一種兩級支持度閾值法。在文獻［12］基礎(chǔ)上，文獻［13］提出了多級支持度閾值法以進一步限制規(guī)則數(shù)量。文獻［14］將多支持度法應(yīng)用到正負關(guān)聯(lián)規(guī)則挖掘算法中，有效地限制了規(guī)則數(shù)量。但是，在相關(guān)度－支持度－置信度框架下，現(xiàn)有正負關(guān)聯(lián)規(guī)則置信度閾值設(shè)置方法還存在局限。文獻［8］針對單級置信度閾值法閾值設(shè)置較低會產(chǎn)生過多低可信度規(guī)則和設(shè)置較高又會遺漏有趣規(guī)則的不足，提出四置信度閾值法，但各個閾值的設(shè)定并未考慮不同類型規(guī)則置信度間的內(nèi)在約束。為此，文獻［7，10］在考慮了規(guī)則置信度間的內(nèi)在變化與約束關(guān)系后，以四種關(guān)聯(lián)規(guī)則同時挖掘為前提，提出對AB、AB類規(guī)則和AB、AB類規(guī)則分別設(shè)置不同置信度閾值P-mc和N-mc(P-mc+N-mc=1)的雙閾值法，但該方法仍然難以有效控制低可信度規(guī)則的數(shù)量，并且易遺漏有趣規(guī)則。

本文結(jié)合規(guī)則的項集相關(guān)性和正負關(guān)聯(lián)規(guī)則置信度隨項集支持度取值大小變化的內(nèi)在特點，提出了一種新的正負關(guān)聯(lián)規(guī)則兩級置信度閾值設(shè)置方法(Positive and Negative association rule's TWO Minimum Confidence，PNMC-TWO)。理論推演和實驗結(jié)果均表明，新方法能更有效控制正負關(guān)聯(lián)規(guī)則的數(shù)量和提取有趣關(guān)聯(lián)規(guī)則。新方法充分結(jié)合了四種規(guī)則置信度的變化規(guī)律，對置信度閾值的設(shè)置不是盲目的，基于它所提取的知識或規(guī)則更可靠和有效。

1 預(yù)備知識

1．1 關(guān)聯(lián)規(guī)則的支持度－置信度框架

設(shè) I={i1，i2，…，in} 是問題域的項集，D={T1，T2，…，Tm}是事務(wù)數(shù)據(jù)庫，|D|表示事務(wù)個數(shù)，Ti由事務(wù)標識符TIDi和對應(yīng)的項集ITi描述，ITiI，1 ≤i≤|D|。項集 AITi時稱事務(wù)Ti支持A，sup_c(A)表示項集A在D中的支持度計數(shù)，則A在D中支持度sup(A)=sup_c(A)/|D|。設(shè)ms是支持度閾值，sup(A)≥ms時稱項集A為頻繁項集。

定義1 關(guān)聯(lián)規(guī)則支持度。D中同時包含規(guī)則前件和后件的事務(wù)在D中的占比，簡記sup。

定義2 關(guān)聯(lián)規(guī)則置信度。D中同時包含規(guī)則前件和后件的事務(wù)在包含前件的事務(wù)中的占比，簡記conf。

支持度－置信度框架:在D中篩選出同時滿足支持度閾值(ms)和置信度閾值(mc)的強關(guān)聯(lián)規(guī)則。

1．2 負關(guān)聯(lián)規(guī)則支持度與置信度的計算方法

sup(A)=1－sup(A)

sup(A∪B)=sup(A)－sup(A∪B)

sup(A∪B)=sup(B)－sup(A∪B)

sup(A∪B)=1－sup(A)－sup(B)+sup(A∪B)

由定義2，負關(guān)聯(lián)規(guī)則的置信度計算方法如下:

1．3 正負關(guān)聯(lián)規(guī)則的相關(guān)度－支持度－置信度框架

在正負關(guān)聯(lián)規(guī)則挖掘中，為了避免矛盾規(guī)則的出現(xiàn)，可在支持度－置信度框架中加入項集相關(guān)性度量以進一步約束關(guān)聯(lián)規(guī)則。項集的相關(guān)性度量［11］可定義如下:

KA，B的取值范圍為［0，1］:KA，B＞ 0．5 時 A 和 B 正相關(guān);KA，B=0．5時 A和B相互獨立;KA，B＜ 0．5時 A和B負相關(guān)。

定理1［7］項集A和B正相關(guān)時僅需挖掘AB和AB類規(guī)則;A和B負相關(guān)時僅需挖掘AB和AB類規(guī)則;A和B相互獨立時不需挖掘規(guī)則。

定理1的實際應(yīng)用中，通常會設(shè)正相關(guān)強度判定閾值k1和負相關(guān)強度判定閾值k2來降低挖掘出的規(guī)則數(shù)量和提取真正感興趣的規(guī)則。由此可得相關(guān)度－支持度－置信度框架:1)獲取滿足正、負相關(guān)強度閾值的關(guān)聯(lián)規(guī)則;2)提取滿足ms和mc約束的強關(guān)聯(lián)規(guī)則。

1．4 正負關(guān)聯(lián)規(guī)則置信度間的關(guān)系

由前述負關(guān)聯(lián)規(guī)則支持度和置信度的計算關(guān)系可知，正負關(guān)聯(lián)規(guī)則置信度的計算均與規(guī)則的項集支持度緊密相關(guān)，并且四種正負關(guān)聯(lián)規(guī)則的置信度間還有如下約束關(guān)系成立:

對四種正負關(guān)聯(lián)規(guī)則的置信度取值范圍的研究有助于更合理地確定有效關(guān)聯(lián)規(guī)則的置信度閾值。為此，文獻［8］給出了基于項集支持度的規(guī)則置信度取值范圍界定規(guī)律。

定理3 四種正負關(guān)聯(lián)規(guī)則置信度取值范圍:

定理2表明，四種關(guān)聯(lián)規(guī)則置信度之間存在互補關(guān)系。定理3表明，規(guī)則置信度取值范圍的確定與規(guī)則的項集支持度緊密相關(guān)，且在不同項集支持度取值下規(guī)則的置信度取值范圍存在差異。顯然，單級置信度閾值難以有效反映四種規(guī)則置信度間的約束關(guān)系，也沒有考慮四種規(guī)則置信度間的差異。而四級置信度閾值法又無法反映四種規(guī)則置信度間變化的有機聯(lián)系。鑒于此，兩級置信度閾值法更為合理。

2 結(jié)合項集相關(guān)性的兩級置信度閾值設(shè)置法

文獻［7，10］的雙置信度閾值法假設(shè)四種關(guān)聯(lián)規(guī)則同時挖掘，且它們的置信度閾值滿足定理2的約束;但是，根據(jù)定理1，在考慮項集A和B相關(guān)性后，AB和AB、AB和AB不會同時出現(xiàn)。實際上，在相關(guān)度－支持度－置信度框架下，文獻［7，10］提出的雙閾值法是無法有效限制低可信度規(guī)則數(shù)量的，并且還容易遺漏一些有趣規(guī)則，因此，本文結(jié)合規(guī)則的項集相關(guān)性，以定理3為基礎(chǔ)，分析了正負關(guān)聯(lián)規(guī)則置信度的變化特點，有如下結(jié)論:關(guān)聯(lián)規(guī)則的項集正相關(guān)時，規(guī)則置信度高低變化趨勢與規(guī)則的項集支持度大小變化趨勢有關(guān);關(guān)聯(lián)規(guī)則的項集負相關(guān)時，規(guī)則的置信度高低變化趨勢與規(guī)則的項集支持度間的差距大小有關(guān)。據(jù)此，本文提出了一種新的兩級置信度閾值設(shè)置方法。新方法包括正負關(guān)聯(lián)規(guī)則的兩個置信度閾值，其設(shè)置還涉及相關(guān)強度判定閾值k1和k2以及規(guī)則的項集支持度差距閾值εmin。

2．1 正負關(guān)聯(lián)規(guī)則置信度變化特點分析

情形1 sup(A)+sup(B)≤1且sup(B)≥sup(A)。

情形2 sup(A)+sup(B)≤1且sup(B)＜sup(A)。

情形3 sup(A)+sup(B)＞1且sup(B)≥sup(A)。

情形4 sup(A)+sup(B)＞1且sup(B)＜sup(A)。

情形1的變形推理過程如下:

因為sup(A)+sup(B)≤1

由此可得表1中情形1所示結(jié)果。情形2、3、4的變形過程與情形1類似。

表2是由定理3得出的幾種典型sup(A)和sup(B)取值下四種關(guān)聯(lián)規(guī)則置信度的取值范圍示例。

文獻［8］在分析四種規(guī)則置信度的特點時僅考慮了sup(A)和sup(B)都大于0．9、sup(A)和 sup(B)都小于0．1等特殊情形。為了提高新兩級置信度閾值法提取規(guī)則的有效性，本文以表1為基礎(chǔ)，結(jié)合關(guān)聯(lián)規(guī)則的項集相關(guān)性及表2中的實例，分析四種正負關(guān)聯(lián)規(guī)則置信度變化的一般特點。

(1)sup(A)和sup(B)都偏小時令sup(A)+sup(B)≤1。對情形1，有conf(AB)∈［0，1］，conf(AB)的左邊界→1－sup(A)/(1－sup(A))=1－1/(1/sup(A)－1)，因sup(A)偏小，故conf(AB)左邊界偏高;對情形2，conf(AB)右界→1，即conf(AB)∈［0，1］，而conf(AB)左邊界→1－1/(1/sup(B)－1)，因sup(B)偏小，故conf(AB)的左邊界偏高。

(2)sup(A)和sup(B)都偏大時令sup(A)+sup(B)＞1，此時，情形3和情形4的conf(AB)左邊界都為1+sup(B)/sup(A)－1/sup(A)→2－1/sup(A)，因為sup(A)＜1且sup(A)偏大，故1/sup(A)→1+，2 －1/sup(A)→1－，可見，conf(AB)偏高。對conf(AB)，當ε→0時都有conf(AB)∈［0，1］。

綜上，項集A和B正相關(guān)時，若sup(A)和sup(B)都偏小，conf(AB)可高可低，但conf(AB)偏高。如表2中1、2行的第5～6列所示;若sup(A)和sup(B)都偏大，conf(AB)偏高，conf(AB)可高可低。如表2中3、4行的第5～6列所示。

表1 不同sup(A)和sup(B)情形下的正負關(guān)聯(lián)規(guī)則置信度的取值范圍Tab．1 Confidence range of positive and negative association rules in different sup(A)and sup(B)situations

表2 不同sup(A)和sup(B)取值下的正負關(guān)聯(lián)規(guī)則的置信度取值范圍示例Tab．2 Examples of confidence range of positive and negative association rules in different values of sup(A)and sup(B)

當sup(A)+sup(B)→1且ε→0時，有:

max{0，(sup(A)+sup(B) －1)/sup(A)}→0

min{1，sup(B)/sup(A)} →1

max{0，(sup(B)－sup(A))/(1－sup(A))}→0

min{sup(B)/(1－sup(A))，1}→1

(1)對于情形1。

(2)對于情形2。

(3)對于情形3。

(4)對于情形4。

綜上，項集A和B負相關(guān)時，若sup(A)+sup(B)→1且ε偏小，兩種規(guī)則的置信度可高可低。此外，有:ε越大(小)，AB和AB中一類規(guī)則的置信度越高(低)，而另一類規(guī)則的置信度可高可低。如表2中最后兩列所示。

2．2 兩級置信度閾值設(shè)置法PNMC-TWO

由上一節(jié)的討論可知:A和B正相關(guān)且支持度偏小時conf(AB)可高可低，但conf(AB)偏高;A和B正相關(guān)且支持度偏大時conf(AB)偏高，conf(AB)可高可低?？紤]到AB類規(guī)則與可信度低的AB類規(guī)則實用性不強［10］，此時可通過設(shè)置高置信度閾值(mc-max)來降低AB類規(guī)則數(shù)量并保證AB類規(guī)則的高可信度。

A和B負相關(guān)時，若sup(A)+sup(B)→1且項集支持度差距ε偏小，conf(AB)和conf(AB)都是可高可低，此時，為了有效防止有趣關(guān)聯(lián)規(guī)則的遺漏，算法可設(shè)置低置信度閾值(mc-min)加以保證。

綜上，正負關(guān)聯(lián)規(guī)則兩級置信度閾值法(PNMC-TWO)的設(shè)置思想如下:設(shè)mc-min為低置信度閾值，mc-max為高置信度閾值。從事務(wù)數(shù)據(jù)庫D中篩選出滿足項集相關(guān)性強度閾值的項集A和B。若A和B正相關(guān)，AB和AB類規(guī)則的置信度閾值用mc-max。若A和B負相關(guān)，AB和AB類規(guī)則的置信度閾值設(shè)置分兩種情形:ε＜εmin時用mc-min，ε≥εmin時用 mc-max。

正負關(guān)聯(lián)規(guī)則挖掘一般分為兩個步驟:1)找出事務(wù)數(shù)據(jù)庫D中滿足用戶要求的所有項集;2)由項集產(chǎn)生強關(guān)聯(lián)規(guī)則。PNMC-TWO用于正負關(guān)聯(lián)規(guī)則提取階段，下面給出該階段的偽代碼。

算法 用PNMC-TWO提取有趣正負關(guān)聯(lián)規(guī)則。

輸入 需要進行相關(guān)性分析的項集集合U，正相關(guān)強度閾值k1和負相關(guān)強度閾值k2，兩級置信度閾值mc-min和mc-max，項集支持度差距閾值εmin，支持度閾值ms。

輸出 正負關(guān)聯(lián)規(guī)則集合PAR和NAR。

2) while(each itemset A，B∈U and A∩B={

3) if(KA，B≥k1){

8) if(KA，B≤k2){

14) else{

19) } //if k2

20)} //while

21)return PAR and NAR

設(shè)U中項集個數(shù)為n，則算法在最壞情況下的時間復(fù)雜度為O(n2)。使用PNMC-TWO時的算法步驟3)～18)時間復(fù)雜度為O(1)，說明新方法的使用不會額外增加用戶所選擇的正負關(guān)聯(lián)規(guī)則挖掘算法的時間開銷。PNMC-TWO置信度閾值設(shè)置法融合了4種正負關(guān)聯(lián)規(guī)則的置信度取值變化規(guī)律，使得兩級置信度閾值的設(shè)定變得更為客觀和科學，更具一般性和適應(yīng)性，有利于有效規(guī)則的提取。

3 實驗分析

為檢驗PNMC-TWO的有效性，本文以文獻［15］的正負關(guān)聯(lián)規(guī)則挖掘算法為統(tǒng)一模型，采用文獻［11］提出的最優(yōu)相關(guān)度量KA，B，與文獻［7，10］的正負關(guān)聯(lián)規(guī)則雙置信度閾值法進行了實驗對比。

實驗環(huán)境:Intel Core i5-5200U 2．20 GHz處理器，4 GB內(nèi)存，Windows 10操作系統(tǒng)，Matlab R2015b編程。事務(wù)數(shù)據(jù)庫:1)小型事務(wù)數(shù)據(jù)集［6］。它包含10個事務(wù)和6個項目;2)某超市某月的銷售數(shù)據(jù)集。它包含747個事務(wù)，196個項，其中非頻繁項集居多;3)UCI上的chess數(shù)據(jù)集。它包含3196個事務(wù)和75個項目，具有高度正關(guān)聯(lián)的特點。

實驗參數(shù):表 3 中 k1=0．6，k2=0．3，ms=0．3，εmin=0．5。表4中k1=0．6，k2=0．3，ms=0．15，εmin=0．5。表5中k1=0．7，k2=0．3，ms=0．94，εmin=0．5。

在不同的置信度閾值下，兩類雙置信度閾值法在小數(shù)據(jù)集上的挖掘結(jié)果如表3所示，在超市數(shù)據(jù)集上的挖掘結(jié)果如表4所示，在chess數(shù)據(jù)集上的挖掘結(jié)果如表5所示。其中，P-mc表示文獻［7，10］方法中AB和AB型規(guī)則的置信度閾值，N-mc表示文獻［7，10］方法中AB和AB型規(guī)則的置信度閾值，且P-mc+N-mc=1;FAR表示兩種方法提取出的正關(guān)聯(lián)規(guī)則數(shù)量，NAR表示負關(guān)聯(lián)規(guī)則數(shù)量。

表3 小數(shù)據(jù)集上挖掘規(guī)則數(shù)量及運行時間Tab．3 Number of mined rules and running time on small data set

表4 超市數(shù)據(jù)集挖掘規(guī)則數(shù)量及運行時間Tab．4 Number of mined rule and running time on supermarket data set

表5 chess數(shù)據(jù)集挖掘規(guī)則數(shù)量及運行時間Tab．5 Number of mined rule and running time on chess data set

從表3～5可知:當文獻［7，10］雙閾值法中 P-mc與PNMC-TWO中mc-max保持一致時，提取的正關(guān)聯(lián)規(guī)則數(shù)量相同，這表明PNMC-TWO與文獻［7，10］雙閾值法在控制 AB型規(guī)則方面具有同樣好的效果。但是，從表3和表4可觀察到，PNMC-TWO提取出的負關(guān)聯(lián)規(guī)則與原雙閾值法提取出的負關(guān)聯(lián)規(guī)則相比，數(shù)量明顯減少。原因在于，文獻［7，10］的雙閾值法中，如果P-mc很高，N-mc就會很低，它使得大量無趣的低可信度AB和AB型規(guī)則被提取出。而PNMC-TWO由于考慮了規(guī)則置信度的內(nèi)在變化規(guī)律，使之對負關(guān)聯(lián)規(guī)則數(shù)量調(diào)控非常顯著。它既不會遺漏掉有趣的關(guān)聯(lián)規(guī)則，也不會產(chǎn)生過多低可信度的關(guān)聯(lián)規(guī)則?？梢?，在控制規(guī)則數(shù)量和保證規(guī)則有趣方面，PNMC-TWO比文獻［7，10］雙閾值法更有效。

對chess數(shù)據(jù)集挖掘時所需進行相關(guān)性分析的項集對共有7574對，其中99%的相關(guān)度大于0．9，其余的不小于0．3，說明chess數(shù)據(jù)集中有趣項集間是高度正相關(guān)的，所以在P-mc和mc-max對應(yīng)相同時，兩個方法提取出的負關(guān)聯(lián)規(guī)則(全為AB)數(shù)量相同，如表5所示。

可見，對具有不同大小和特點的數(shù)據(jù)集，PNMC-TWO都表現(xiàn)出了良好的有效性和適應(yīng)性。另外，從運行時間來看，PNMC-TWO幾乎不額外增加提取規(guī)則的時間開銷。

4 結(jié)語

在相關(guān)度－支持度－置信度框架下，現(xiàn)有的正負關(guān)聯(lián)規(guī)則置信度閾值設(shè)置方法挖掘出的規(guī)則質(zhì)量不高。結(jié)合規(guī)則的項集相關(guān)性分析，在分析正負關(guān)聯(lián)規(guī)則置信度變化特點基礎(chǔ)上提出了一種更加科學、合理的PNMC-TWO。理論分析和實驗計算表明，新方法能更加有效地控制挖掘出來的規(guī)則數(shù)量，同時還可以確保挖掘出來的規(guī)則是真正有趣的關(guān)聯(lián)規(guī)則。