基于二級剪枝策略的正負關聯模式挖掘算法

蘇雪峰，郭燕萍，胡 彧

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

基于二級剪枝策略的正負關聯模式挖掘算法

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

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

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

興趣度；剪枝；正負關聯規(guī)則；B-PANR算法

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

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

1 相關知識

1.1 正負關聯規(guī)則的定義

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

1.2 支持度與置信度的計算

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

1.3 相關性計算

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

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

文獻[4]證明了項集A與B之間相關性具有如下關系：

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

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

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

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

2.1 關聯規(guī)則的興趣度

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

根據正負關聯規(guī)則支持度與置信度計算的相關公式，對上述公式進行推導，過程如下：

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

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

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

2.2 項集的興趣度

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

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

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

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

InterestA,B的值域為[-1,1]，其值在0的兩側對稱，且當InterestA,B＜0時，項集A與B負相關，InterestA,B＞0時，項集A與B正相關，InterestA,B=0時，項集A與B相互獨立。

2.3 二級剪枝策略

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

2.3.1 項集剪枝

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

2.3.2 關聯規(guī)則剪枝

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

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

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

3 算法設計

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

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

輸入：事務數據庫D；最小支持度閾值ms；最小興趣度閾值mi；

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

過程：

算法2：基于興趣度的正負關聯規(guī)則生成算法PositiveAndNegtativeRules

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

輸出：正負關聯規(guī)則集合AR；過程：

4 實驗與分析

4.1 實驗設計

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

表1 合成數據的基本特征

4.2 實驗結果

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

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

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

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

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

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

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

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

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

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

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

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

4.3 實驗結果分析

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

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

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

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

5 結語

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

[1]宋威,李晉宏.徐章艷，等.一種新的頻繁項集精簡表示方法及其挖掘算法的研究[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]董祥軍,王淑靜,宋瀚濤，等.負關聯規(guī)則的研究[J].計算機工程,2004,24(11)：978-981.

[5]呂杰林,陳是維.基于相關性度量的關聯規(guī)則挖掘[J].浙江大學學報,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

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

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

〔責任編輯 高?！?/p>