正負關聯規(guī)則兩級置信度閾值設置方法

陳 柳，馮 山

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

0 引言

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

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

1 預備知識

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

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

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

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

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

1．2 負關聯規(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ī)則的置信度計算方法如下:

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

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

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

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

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

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

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

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

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

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

2 結合項集相關性的兩級置信度閾值設置法

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

2．1 正負關聯規(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所示結果。情形2、3、4的變形過程與情形1類似。

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

文獻［8］在分析四種規(guī)則置信度的特點時僅考慮了sup(A)和sup(B)都大于0．9、sup(A)和 sup(B)都小于0．1等特殊情形。為了提高新兩級置信度閾值法提取規(guī)則的有效性，本文以表1為基礎，結合關聯規(guī)則的項集相關性及表2中的實例，分析四種正負關聯規(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正相關時，若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ī)則置信度的取值范圍Tab．1 Confidence range of positive and negative association rules in different sup(A)and sup(B)situations

表2 不同sup(A)和sup(B)取值下的正負關聯規(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負相關時，若sup(A)+sup(B)→1且ε偏小，兩種規(guī)則的置信度可高可低。此外，有:ε越大(小)，AB和AB中一類規(guī)則的置信度越高(低)，而另一類規(guī)則的置信度可高可低。如表2中最后兩列所示。

2．2 兩級置信度閾值設置法PNMC-TWO

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

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

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

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

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

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

輸出 正負關聯規(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

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

3 實驗分析

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

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

實驗參數:表 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。

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

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

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

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

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

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

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

4 結語

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