蘇雪峰，郭燕萍，胡 彧

(1.山西大學(xué)商務(wù)學(xué)院，山西太原030031；2.太原理工大學(xué)，山西太原030024)

基于二級剪枝策略的正負(fù)關(guān)聯(lián)模式挖掘算法

蘇雪峰1，郭燕萍1，胡 彧2

(1.山西大學(xué)商務(wù)學(xué)院，山西太原030031；2.太原理工大學(xué)，山西太原030024)

為了解決負(fù)關(guān)聯(lián)規(guī)則挖掘中海量項集問題和一級剪枝策略效率不高的問題，首先給出一種計算項集和關(guān)聯(lián)規(guī)則興趣度的數(shù)學(xué)模型，然后提出基于興趣度的項集剪枝和關(guān)聯(lián)規(guī)則剪枝的二級剪枝策略，最后提出一種新的基于二級剪枝策略的正負(fù)關(guān)聯(lián)模式挖掘算法B-PANR。該算法采用新的剪枝技術(shù)，避免無效的或者無趣的正負(fù)模式產(chǎn)生，正負(fù)關(guān)聯(lián)規(guī)則數(shù)量和挖掘時間明顯降低，挖掘效率得到很大提高。理論分析和實驗結(jié)果表明，與現(xiàn)有代表性挖掘算法PARamp;NAR和IPARamp;NAR比較，B-PANR算法在挖掘效率、剪枝效果和穩(wěn)定性方面具有很好的表現(xiàn)，并且具有良好的擴(kuò)展性。

興趣度；剪枝；正負(fù)關(guān)聯(lián)規(guī)則；B-PANR算法

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中重要研究分支和研究熱點之一，旨在從大量數(shù)據(jù)中發(fā)現(xiàn)和分析項集之間有趣的各種關(guān)聯(lián)，以揭示隱藏其中的事務(wù)內(nèi)在本質(zhì)聯(lián)系。其早期的研究是以正關(guān)聯(lián)規(guī)則挖掘為主，典型的關(guān)聯(lián)規(guī)則算法是Agrawal等人于1993年提出的Apriori算法。在Apriori算法的基礎(chǔ)上，出現(xiàn)了很多改進(jìn)算法[1]。典型的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法是Wu等提出的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法[2]，在此基礎(chǔ)上，產(chǎn)生了很多改進(jìn)的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法，如基于多支持度的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法以及基于頻繁模式樹的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法[3]等。

與挖掘正關(guān)聯(lián)規(guī)則相比，從數(shù)據(jù)庫中挖掘負(fù)關(guān)聯(lián)規(guī)則面臨的挑戰(zhàn)是候選項集數(shù)量巨大，如何有效地生成候選項集并進(jìn)行合理的剪枝是當(dāng)前關(guān)聯(lián)規(guī)則挖掘的兩大基本問題。針對這些問題，文獻(xiàn)[2]提出了基于Apriori框架同時生成頻繁項集和非頻繁項集的方法，并利用興趣度在候選項集生成和關(guān)聯(lián)規(guī)則生成兩個階段進(jìn)行剪枝。然而，當(dāng)前的正關(guān)聯(lián)規(guī)則剪枝技術(shù)研究比較充分，而對挖掘正負(fù)關(guān)聯(lián)規(guī)則的項集剪枝和正負(fù)規(guī)則剪枝研究不是很深入。為此，本文從候選項集生成和剪枝兩個層面展開研究。

1 相關(guān)知識

1.1 正負(fù)關(guān)聯(lián)規(guī)則的定義

定義1已知A?I，B?I且A?B=?，C1∈{A,?A}，C2∈{B,?B}，ms為最小支持度閾值，mc為最小置信度閾值，關(guān)聯(lián)規(guī)則C1=＞C2若滿足：(1)supp(A)≥ms且 supp(B)≥ms;(2)supp(C1=＞C2)≥ms;(3)conf(C1=＞C2)≥mc,則稱C1=＞C2為有意義的正負(fù)關(guān)聯(lián)規(guī)則[4]。

1.2 支持度與置信度的計算

設(shè)A，B為事務(wù)數(shù)據(jù)庫D中的項集，其中A?B=，supp(A)為A的支持度，則正負(fù)關(guān)聯(lián)規(guī)則支持度與置信度的計算公式如式(1)至式(7)所示[4]：

1.3 相關(guān)性計算

由于關(guān)聯(lián)規(guī)則A=＞B的置信度只是在給定A條件下B的概率估計，它并不能反映A與B之間相關(guān)的強(qiáng)度，而關(guān)聯(lián)規(guī)則蘊涵的應(yīng)該是正相關(guān)關(guān)系，負(fù)相關(guān)關(guān)系的關(guān)聯(lián)規(guī)則是沒有實際意義的。目前普遍采用的計算項集相關(guān)性的方法是Brin[4]提出的公式：

其中corrA,B∈[0,+∞)，當(dāng)corrA,B＜1時，項集A和B為負(fù)相關(guān)，表示A與B呈抑制作用；當(dāng)corrA,B=1時，項集A和B相互獨立；當(dāng)corrA,B＞1時，項集A和B為正相關(guān)，表示A與B互相促進(jìn)。

文獻(xiàn)[4]證明了項集A與B之間相關(guān)性具有如下關(guān)系：

(1)當(dāng)corrA,B＞1 時 ，corr?A,B＜1 ，corrA,?B＜1 ，corr?A?,B＞ 1 ；

(2)當(dāng)corrA,B=1 時 ，corr?A,B=1 ，corrA,?B=1 ，corr?A?,B=1 。

2 基于興趣度模型的二級剪枝策略

在corrA,B的基礎(chǔ)上提出了興趣度模型，用來更精確地反映關(guān)聯(lián)規(guī)則相關(guān)的程度，同時克服了corrA,B在臨界值1的兩側(cè)值的分布不對稱的不足。

2.1 關(guān)聯(lián)規(guī)則的興趣度

conf(A=＞B)＜conf(?A=＞B)表明購買A的情況下購買B的概率比不購買A的情況下購買B的概率要低，購買A對購買B起抑制作用，A與B之間是負(fù)相關(guān)關(guān)系，?A,B為正相關(guān)關(guān)系。所以很自然地可建立如下興趣度模型[5]：

根據(jù)正負(fù)關(guān)聯(lián)規(guī)則支持度與置信度計算的相關(guān)公式，對上述公式進(jìn)行推導(dǎo)，過程如下：

由上述等式可得出如下規(guī)范化興趣度模型：

其中max{corrA,B-corr?A,B}為規(guī)范化因子，使得興趣度的值域為[-1，1]。容易證明當(dāng)corrA,B＞1時；Interest(A=＞B)＞0，corrA,B＜1時，Interest(A=＞B)＜0；corrA,B=1時，Interest(A=＞B)=0；|Interest(A=＞B)|的值越大，相關(guān)性越強(qiáng)。

定義2已知A?I，B?I且A?B=?，C1∈{A,?A}，C2∈{B,?B}，ms為最小支持度閾值，mc為最小置信度閾值，mi為最小興趣度閾值，C1=＞C2是有意義的關(guān)聯(lián)規(guī)則，且|Interest(C1=＞C2)|≥mi，則稱C1=＞C2為有趣的關(guān)聯(lián)規(guī)則。

2.2 項集的興趣度

當(dāng)項集{AB}的相關(guān)性corrA,B＞1時,關(guān)聯(lián)規(guī)則A=＞Bt?A=＞?B的前件和后件是正相關(guān)關(guān)系，若兩個規(guī)則的興趣度都小于mi，則項集{AB}應(yīng)該剪枝；若兩個規(guī)則中有一個規(guī)則的興趣度小于mi，項集{AB}保留，不滿足mi要求的規(guī)則在關(guān)聯(lián)規(guī)則生成階段剪枝；故可選擇兩個規(guī)則最大的興趣度作為項集{AB}的興趣度，項集{AB}的興趣度記為：

InterestA,B=max{Interest(A=＞B),Interest(?A=＞?B)},

同理，當(dāng)項集{AB}項集的相關(guān)性corrA,B＜1時，只生成關(guān)聯(lián)規(guī)則A=＞?B和?A=＞B，故

當(dāng)項集{AB}項集的相關(guān)性corrA,B=0時，不生成任何形式的關(guān)聯(lián)規(guī)則，項集{AB}應(yīng)該剪枝。將三種情況綜合可得項集{AB}的興趣度模型為：

InterestA,B的值域為[-1,1]，其值在0的兩側(cè)對稱，且當(dāng)InterestA,B＜0時，項集A與B負(fù)相關(guān)，InterestA,B＞0時，項集A與B正相關(guān)，InterestA,B=0時，項集A與B相互獨立。

2.3 二級剪枝策略

在正負(fù)關(guān)聯(lián)規(guī)則挖掘過程中，目前的研究主要在關(guān)聯(lián)規(guī)則生成階段進(jìn)行剪枝。眾多研究表明，頻繁項集中只有一小部分項集能生成有趣的關(guān)聯(lián)規(guī)則，所以在頻繁項集生成過程中實施剪枝也非常重要。

2.3.1 項集剪枝

由項集興趣度的定義可知，當(dāng)項集興趣度小于最小興趣度閾值mi，這些項集不可能生成有趣的關(guān)聯(lián)規(guī)則，項集剪枝就是要對這類項集實施剪枝。若項集X不滿足條件（10）約束，則需要將其剪枝，否則保留。

2.3.2 關(guān)聯(lián)規(guī)則剪枝

已知頻繁項集X={AB}，當(dāng)InterestA,B＜0,則生成關(guān)聯(lián)規(guī)則A=＞?B，?A=＞B；當(dāng)InterestA,B＞0,則生成關(guān)聯(lián)規(guī)則A=＞B，?A=＞?B。關(guān)聯(lián)規(guī)則A=＞B是有趣關(guān)聯(lián)規(guī)則需要滿足最小支持度閾值ms，最小置信度閾值mc和最小興趣度閾值mi。故A=＞B是有趣關(guān)聯(lián)規(guī)則需要滿足條件（11）的約束，否則實施剪枝。

同理，關(guān)聯(lián)規(guī)則A=＞?B，?A=＞B，?A=＞?B是否有趣也可按上述方法進(jìn)行驗證。

二級剪枝策略可以采取一致的最小興趣度閾值mi，即項集和關(guān)聯(lián)規(guī)則興趣度閾值相等；也可以采取不一致的最小興趣度閾值，即分別設(shè)置項集和關(guān)聯(lián)規(guī)則興趣度閾值為mi和mri，且mi＜mri。一致閾值實現(xiàn)簡單易于理解，二級閾值更加靈活，擴(kuò)展性強(qiáng)。

3 算法設(shè)計

本文設(shè)計的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法B-PANR(Both Positive and Negative Association)分成搜索有趣頻繁項集和生成正負(fù)關(guān)聯(lián)規(guī)則兩個子過程，并在兩個子過程中分別使用項集興趣度和關(guān)聯(lián)規(guī)則興趣度實施剪枝。

算法1：有趣項集生成算法Search-ItemsetsOfInterest

輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值ms；最小興趣度閾值mi；

輸出：有趣項集的集合IL；

過程：

算法2：基于興趣度的正負(fù)關(guān)聯(lián)規(guī)則生成算法PositiveAndNegtativeRules

輸入：有趣項集的集合IL；最小支持度閾值ms；最小置信度閾值mc；最小興趣度閾值mi；

輸出：正負(fù)關(guān)聯(lián)規(guī)則集合AR；過程：

4 實驗與分析

4.1 實驗設(shè)計

為了驗證本文提出的基于興趣度挖掘正負(fù)關(guān)聯(lián)規(guī)則的算法B-PANR的效率與剪枝效果，實驗選取了3個數(shù)據(jù)集、2種類似算法進(jìn)行了對比實驗。實驗數(shù)據(jù)采用頻繁項集和關(guān)聯(lián)規(guī)則挖掘普遍使用的合成數(shù)據(jù)，數(shù)據(jù)來源為 SPMF 網(wǎng)站 http：∕www.philippe-fournier-viger.com∕spmf∕和頻繁項集挖掘數(shù)據(jù)集 http：∕fimi.ua.ac.be∕data∕。數(shù)據(jù)集的特征如表 1所示，其中T表示每一個事務(wù)中平均包含的項目數(shù)，I表示最大的頻繁項集包含的平均項目數(shù)，D表示數(shù)據(jù)集包含的事務(wù)數(shù)。2個類似算法為董祥軍等在文獻(xiàn)[9]中提出的PARamp;NAR算法與呂杰林等在文獻(xiàn)[10]提出基于興趣度的IPARamp;NAR算法，PARamp;NAR算法沒有使用興趣度進(jìn)行剪枝，直接由頻繁項集生成正負(fù)關(guān)聯(lián)規(guī)則，IPARamp;NAR算法在關(guān)聯(lián)規(guī)則生成階段使用興趣度實施剪枝。算法實現(xiàn)是基于SPMF（序列模式挖掘框架）提供的JAVA開源數(shù)據(jù)挖掘程序類庫v0.96(2014.4.6最新發(fā)布)。算法運行計算機(jī)配置為：主頻2.5GHz，內(nèi)存2GB的個人計算機(jī)。

表1 合成數(shù)據(jù)的基本特征

4.2 實驗結(jié)果

4.2.1 支持度閾值變化時挖掘性能比較

為了驗證B-PANR算法在不同支持度下的性能，實驗選取T25I10D10k為實驗數(shù)據(jù)集，設(shè)置mc=0.2，mi=0.1，對比三種算法在最小支持度閾值取不同值的情況下三種算法的運行時間和正負(fù)關(guān)聯(lián)規(guī)則數(shù)量。實驗表明，本文提出的B-PANR算法在不同支持度下運行時間最短，三者的運行時間對比如圖1所示。三種算法在不同支持度下產(chǎn)生的正負(fù)關(guān)聯(lián)規(guī)則數(shù)量如表2所示，其中B-PANR算法生成的規(guī)則數(shù)量最少。

圖1 三種算法在不同支持度下的運行時間比較

表2 三種算法在不同支持度下生成的正負(fù)關(guān)聯(lián)規(guī)則數(shù)量

4.2.2 興趣度閾值變化時挖掘性能比較

為了驗證B-PANR算法在不同興趣度下的性能和剪枝效果，本文設(shè)計了B-PANR與IPARamp;NAR算法的比較實驗，實驗選取T25I10D10k為實驗數(shù)據(jù)集，設(shè)置mc=0.2，ms=0.012。實驗結(jié)果表明，隨著興趣度閾值不斷增大，B-PANR算法的運行時間減少明顯，而IPARamp;NAR算法的運行時間無明顯變化，二者的運行時間如圖2所示；B-PANR算法采用兩階段剪枝策略，隨著興趣度閾值不斷增大，剪枝效果更明顯，產(chǎn)生的規(guī)則數(shù)量遠(yuǎn)遠(yuǎn)小于IPARamp;NAR算法，實驗結(jié)果如表3所示。

圖2B-PANR與IPARamp;NAR算法在不同興趣度下的運行時間比較

表3 B-PANR與IPARamp;NAR算法在不同興趣度下的規(guī)則數(shù)量

4.2.3 不同數(shù)據(jù)環(huán)境下的挖掘性能比較

為了驗證B-PANR算法在不同數(shù)據(jù)環(huán)境下的表現(xiàn)，實驗選取表3中的三個數(shù)據(jù)集，在ms=0.012，mc=0.2，mi=0.1時，三種算法的運行時間比較如圖3所示。

圖3 三種算法在不同數(shù)據(jù)環(huán)境下的運行時間比較

實驗結(jié)果表明B-PANR算法具有很好的可擴(kuò)展性，又能很好地適應(yīng)不同規(guī)模的數(shù)量集，尤其當(dāng)數(shù)據(jù)集T和I較大時，B-PANR算法效果更加明顯。在數(shù)據(jù)集T10I4D100K環(huán)境下，三種算法運行時間沒有明顯差異；在數(shù)據(jù)集T25I10D10k環(huán)境下，B-PANR運行時間略少于其它兩種算法；在數(shù)據(jù)集T20I6D100k環(huán)境下，B-PANR運行時間明顯少于其它兩種算法。

4.3 實驗結(jié)果分析

通過上述三個方面的實驗表明，與IPARamp;NAR和PARamp;NAR算法相比，無論在不同支持度閾值、或者不同的興趣度閾值和不同的數(shù)據(jù)集環(huán)境下，BPANR算法在運行時間和剪枝效果兩個方面都具有一定的優(yōu)勢。

B-PANR算法優(yōu)于其它兩種算法的主要原因分析如下：

由于B-PANR算法采用兩級剪枝策略，第一級剪枝通過項集剪枝減少了項集的規(guī)模，第二級剪枝通過關(guān)聯(lián)規(guī)則剪枝減少了關(guān)聯(lián)規(guī)則生成的數(shù)量，兩個階段都節(jié)約了運行時間。所以三種算法中，總體運行時間相對最少。

由于B-PANR算法在項集生成階段對一些興趣度較低的項集實施剪枝，減小了頻繁項集的規(guī)模，所以生成的正負(fù)關(guān)聯(lián)規(guī)則數(shù)量都要少于IPARamp;NAR算法。隨著興趣度閾值的不斷提高，B-PANR算法的剪枝效果更明顯。同時，本文提出的興趣度規(guī)范了興趣度的取值范圍為[-1,1]，克服了corrA,B∈[0,+∞)度量興趣度時興趣度閾值難確定的問題，使得基于興趣度的剪枝效果更穩(wěn)定。

5 結(jié)語

同時挖掘正負(fù)關(guān)聯(lián)規(guī)則面臨的巨大挑戰(zhàn)是海量項集問題，為了提高算法的效率，剪枝是普遍采用的策略。而目前的研究主要在關(guān)聯(lián)規(guī)則生成階段實施剪枝，本文在研究興趣度的基礎(chǔ)之上提出了基于興趣度模型的二級剪枝策略，并設(shè)計了BPANR算法，該算法在運行時間和剪枝效果上都優(yōu)于未實施剪枝的PARamp;NAR與只實施關(guān)聯(lián)規(guī)則剪枝的IPARamp;NAR算法，同時具有良好的穩(wěn)定性和可擴(kuò)展性。

[1]宋威,李晉宏.徐章艷，等.一種新的頻繁項集精簡表示方法及其挖掘算法的研究[J].計算機(jī)研究與發(fā)展,2010,47(2)：277-285.

[2]WU X D,ZHANG C Q,ZHANG S C.Efficient Ming of Both Positive and Negative Association Rules[J].ACM Transactions on Information System,2004,33(3)：318-405.

[3]RUCHI BHARGAVA,SHRIKANT LADE.Effective Positive Negative Association Rule Mining Using Improved Frequent Pattern Tree[J].International Journal of Advanced Research in Computer Science and Software Engineering,2013,3(4)：193-199.

[4]董祥軍,王淑靜,宋瀚濤，等.負(fù)關(guān)聯(lián)規(guī)則的研究[J].計算機(jī)工程,2004,24(11)：978-981.

[5]呂杰林,陳是維.基于相關(guān)性度量的關(guān)聯(lián)規(guī)則挖掘[J].浙江大學(xué)學(xué)報,2012,39(3)：284-292.

Abdtract:In order to solve the question of large itemsets and improve the efficiency of one level pruning in mining negative association rules,the paper proposes a interestingness model to measure the itemset and association rule based on the research of relevance and interestingness of association rules,and designs two stage pruning strategy and B-PANR algorithm which is designed for achieving the two stage pruning strategy.Comparing with PARamp;NAR and IPARamp;NAR algorithm,B-PANR is proved more effective in executing time and pruning by experiments.

Research of Mining Positive and Negative Association Rules Based on Two-level Pruning Strategy

SU Xue-feng1,GUO Yan-ping1,HU Yu2
(1.School of Business,Shanxi University,Taiyuan Shanxi,030031;2.Taiyuan University of Technology,Taiyuan Shanxi,030024)

interestingness;pruning;positive and negative association rules;B-PANR algorithm

TP311

A

1674-0874(2016)01-0016-05

2015-10-20

山西省自然科學(xué)基金項目[2012011013-5]；山西省軟科學(xué)研究項目[2014041061-1]；山西大學(xué)商務(wù)學(xué)院科研項目[2014011]

蘇雪峰(1983-)，男，山西偏關(guān)人，碩士,研究方向：數(shù)據(jù)挖掘與電子商務(wù)。

〔責(zé)任編輯 高海〕