基于興趣度度量的正負關聯規則挖掘方法研究

馬彥勤，武 彤，鄧烜堃

(貴州大學 計算機科學與技術學院，貴州 貴陽 550025)

0 引 言

關聯規則挖掘算法最初是為解決購物籃問題而提出的頻繁項集挖掘算法，主要是從大規模數據集中挖掘出符合頻度規則的有趣的關聯規則，挖掘出的關聯規則主要用于提高商品銷售量。大多數關聯規則通過支持度-置信度框架得出，在此框架下得出的關聯規則只是滿足一定的支持度和置信度，并沒有考慮規則前件和后件的相關性，并不是有趣的，其結果會對生產銷售決策起誤導作用[1]。例如在滿足了支持度與置信度閾值的要求下，產生了“買X=>買Y”這條關聯規則，意味著顧客在買X的情況下同時也會購買Y，但實際上在X的條件下購買Y的概率遠遠小于單獨購買Y的概率，這條關聯規則并不是有趣的。為此通過興趣度度量這一概念對生成的關聯規則進行篩選，去除無趣的規則，保留有趣的規則。

在挖掘關聯規則的過程中，人們通常只關注于正強關聯規則，像“買了X同樣也會買Y”這樣的正關聯規則，往往忽略了負關聯規則同樣對決策支持具有重大的作用[2]。在大規模數據集中，兩個項目之間不僅有正相關的關系，也有負相關的關系。像經典的“啤酒-尿布”關聯規則就是正相關關系，顧客在買啤酒的同時會把尿布帶回去，這一規則也充分揭露了一個現象，愛喝啤酒的丈夫在下班后既要買啤酒也要給自己的孩子買尿布，而“可樂-茶”這一關聯規則就是負相關關系，它們之間的功能相互替代，是二選一的關系。

針對以上提出的兩個問題，為了過濾掉在支持度-置信度框架下產生的關聯規則中的無趣規則，引入了興趣度度量，對關聯規則進行篩選，避免無趣規則對決策執行的誤導作用。為了掌握更全面的決策信息，在進行正關聯規則挖掘的同時，也進行負關聯規則的挖掘。

從數據挖掘的角度，負關聯規則和正關聯規則具有同樣重要的價值，在相關決策制定過程中，發揮了自己獨特的作用，越來越受到大家的重視[3]。為此，在現有幾種興趣度度量的基礎上，提出了一種新的興趣度度量，來解決數據挖掘中正負關聯規則的問題。

1 Apriori算法簡介

1.1 Apriori算法

Apriori算法是通過掃描事物集合采用逐層搜索策略來產生頻繁K項集的。首先，掃描數據庫，找出頻繁1項集；基于頻繁1項集，進行自連接、剪枝后，再次掃描數據庫，產生頻繁2項集；依次類推找出頻繁K項集，直至找到最大的頻繁項集[4]。

在關聯規則挖掘頻繁項集的過程中，主要分為兩個步驟：連接步和剪枝步[5]。連接步：為了找到候選K項集CK，需要頻繁K-1項集LK-1，進行自連接，即LK-1*LK-1，當兩項集的前K-2項相同時，它們是可連接的。剪枝步：候選項集CK是頻繁項集LK的超集，如果CK中某個候選項集有一個K-1子集不屬于LK-1，則這個候選項集可以被修剪掉，不再考慮[6]。

在關聯規則的挖掘過程中，主要做兩方面的工作：挖掘頻繁項集和生成關聯規則[7]。頻繁項集是滿足一定出現頻率的項集，頻率的確定由支持度決定，在挖掘的過程中設定最小支持度，大于最小支持度的項集就是頻繁的。關聯規則是形如X=>Y這樣的蘊涵式，在發現頻繁項集之后，通過置信度公式來判斷關聯規則是否符合要求。

1.2 相關概念

1.2.1 支持度

支持度是指項目元素占事務集合的百分比，用以判斷項集是否是頻繁項集的指標[8]。

P(X=>Y)=P(X∪Y)

(1)

1.2.2 置信度

置信度是指在事物集合中，在包含項目X的條件下包含項目Y的概率，用以判斷X=>Y關聯規則是否為強關聯規則[9]。

Conf(X=>Y)=P(Y|X)

(2)

1.2.3 關聯規則

關聯規則是形如X=>Y的蘊涵式，X和Y都是屬于項目集合里的項集，X是規則前件，Y是規則后件，X=>Y代表了前后件之間的相關性。大于最小支持度和最小可信度的關聯規則即為強關聯規則[5]。

2 包含正負關聯規則的興趣度度量

在支持度-置信度框架下，無法過濾無趣的不相關的關聯規則，為此引入興趣度度量對之前的評價標準進行擴充，使得在支持度-置信度-興趣度框架下，挖掘出有趣的正負關聯規則。

2.1 提升度度量

文獻[10]介紹了提升度度量，公式如下：

Interest(X?Y)=P(X∪Y)/P(X)P(Y)

(3)

提升度度量是一種基于概率的簡單的興趣度度量，用來評估前件X的出現對于后件Y的出現是否具有提升作用，反應了前件X和后件Y之間的相關關系。當Interest(X=>Y)>1時，表明前件X和后件Y是正相關的，X的出現會提高Y出現的概率。當0≤Interest(X=>Y)<1時，表明前件X和后件Y是負相關的，X的出現會降低Y出現的概率。當Interest(X=>Y)=1時，表明前件X和后件Y是相互獨立的，兩者的出現并不相互影響。

2.2 基于差異思想興趣度度量

文獻[11]介紹了差異思想興趣度度量，公式表示如下：

(4)

在此興趣度度量中，Conf(X=>Y)是指在前件X的發生下發生Y的概率；P(Y)是指項目Y在整體事物集中出現的概率；兩者做差值運算，其正負結果顯示了前件X對后件Y的相關性。分母取值置信度和支持度的最大值來做一個標準化因子，使得整個興趣度度量取值范圍控制在[-1，1]之間。當Conf(X=>Y)-P(Y)>0時，0Y)≤1，說明X和Y是正相關的，X的出現對Y的出現有提升作用；當Conf(X=>Y)-P(Y)<0時，-1≤Interest(X=>Y)<0，說明X和Y是負相關，X的出現可能會引起Y不出現；當Conf(X=>Y)-P(Y)=0時，Interest(X=>Y)=0，說明X和Y是相互獨立的，X的出現不會影響Y的出現。

2.3 余弦度量

文獻[12]介紹了余弦度量，公式如下：

(5)

余弦度量是在提升度度量的基礎上改進而來的，兩者雖然整體上看起來類似，但是余弦度量比起提升度度量多了零不變性質，使其在進行興趣度度量時不受事物總數的影響。其興趣度度量的取值和提升度度量的取值范圍一樣，正負關聯規則的判斷條件也一樣。

3 新的含正負關聯規則的興趣度度量

如果關聯規則X=>Y為有趣關聯規則，說明關聯規則X=>Y不僅滿足相應的支持度和置信度，而且在X出現的條件下Y出現的概率要比Y單獨出現的概率大，即購買X產品會促進Y產品的銷量[13]，根據相關性度量的相關性質，不難得出Conf(X=>Y)>Conf(X=>Y)[14]。Conf(X=>Y)>Conf(X=>Y)說明在購買X的條件下購買Y的概率大于不購買X的條件下購買Y的概率，基于此提出一種新的含正負關聯規則的興趣度度量，公式如下：

(6)

在進行興趣度計算時，因為要進行正負關聯規則挖掘，涉及到對正負關聯規則支持度和置信度的計算。而Apriori算法在進行頻繁項集挖掘時，得到的是正項集的支持度和置信度的關系，在進行負項集支持度和置信度計算時，利用相關定理通過正項集的支持度和置信度的值，求出負項集的支持度和置信度。根據概率之間的相關性質和文獻[15]的介紹得到定理1。

定理1：設D為事務數據集，I為屬于事務集的項目集合，X,Y為屬于I的項目，X∩Y=?，P(X)為X的支持度。

P(X)=1-P(X)

P(X∪Y)=P(X)-P(X∪Y)

P(X∪Y)=P(Y)-P(X∪Y)

P(X∪Y)=1-P(X)-P(Y)+P(X∪Y)

在此新興趣度度量下，根據正負關聯規則關系，可以得出以下定理。

定理2：若Interest(X=>Y)>0，則

(2)Interest(X=>Y)<0；

證明:因為

Conf(X?Y)>Conf(X?Y)

得出:

Interest(X?Y)=

由以上定理可知，當Interest(X=>Y)>0時，蘊涵式X=>Y是正關聯規則，項目X的出現對項目Y的出現有提升作用。當Interest(X=>Y)<0時，蘊涵式X=>Y是負關聯規則，項目X的出現對項目Y的出現有抑制作用。其他負關聯規則X=>Y，X=>Y，X=>Y同理。當蘊涵式X=>Y(或者X=>Y)的值大于0時，X=>Y，X=>Y的值小于0，正反關聯關系成對應狀態，不會同時出現，產生矛盾狀態。

4 算法設計

基于新的興趣度度量和正負關聯規則定理，根據Apriori算法挖掘過程，進行正負關聯規則挖掘。在挖掘之前，根據要挖掘的數據集的實際特點，設定合適的支持度和置信度，在支持度-置信度-興趣度框架下，能夠最大限度地挖掘出具有實際價值的正負關聯規則。

算法：挖掘正負關聯規則(D，min_P，min_Conf，Interest(X=>Y))

輸入：事務數據集D；最小支持度min_P；最小置信度min_Conf；興趣度Interest(X=>Y)。

輸出：正負關聯規則集合PN_set。

Step1:C=min_P_Search(D)；//根據最小支持度閾值，挖掘頻繁項集，放入集合C中

Step2:R=min_Conf_Search(C)；//根據最小置信度閾值，挖掘出符合最小置信度的強關聯規則，放入集合R中

Step3:foreach(itemsetminR)//根據興趣度度量公式定理，求出正負關聯規則，放入集合PN_set

X=m.pre;//X為強關聯規則的前件

Y=m.post;//Y為強關聯規則的后件

If(Interest(X=>Y)>0) //正相關

PN_set=PN_set∪{X=>Y}；

IfP(X=>Y)≥min_P && Conf(X=>Y)≥min_Conf

If(Interest(X=>Y)<0) //負相關

IfP(X=>Y)≥min_P && Conf(X=>Y)≥

min_Conf

IfP(X=>Y)≥min_P && Conf(X=>Y)≥min_Conf

PN_set=PN_set∪{X=>Y}；

Step4：return PN_set。

該算法首先通過最小支持度閾值挖掘出頻繁項集，通過最小置信度閾值挖掘出強關聯規則，然后運用提出的興趣度度量公式挖掘出符合要求的正負關聯規則。當關聯規則X=>Y的興趣度大于0時，說明規則前件和后件正相關，將正關聯規則并入PN_set集合中，然后判斷X=>Y的支持度和置信度的取值是否滿足最小支持度和最小置信度閾值，若滿足，將關聯規則X=>Y并入PN_set集合。關聯規則X=>Y的興趣度小于0時，判斷X=>Y和X=>Y的支持度和置信度的取值是否滿足最小支持度和最小置信度閾值，若滿足，將關聯規則并入PN_set集合。

5 算法驗證及分析

在提出的挖掘正負關聯規則算法的基礎上，為驗證算法的效率和性能，對算法進行驗證和分析。驗證在Windows 10操作系統下，使用SQL Server 2008數據庫，Visual Studio 2017軟件，C#語言實現。數據集由3 000個用戶的超市購物數據組成，算法在不同的支持度和置信度閾值的設定下進行驗證，結果如表1所示。

表1 算法驗證結果

驗證結果顯示，在支持度-置信度框架下，所篩選出來的關聯規則要多于在支持度-置信度-興趣度框架下的正關聯規則。因為在支持度-置信度閾值的篩選下，沒有考慮到前后件的相關性，得出的正關聯規則并不都是有趣的。在支持度-置信度-興趣度框架下引入了興趣度,充分解決了關聯規則評價標準的問題，把不滿足相關性無趣的關聯規則過濾掉了。

除此之外，通過興趣度度量得到的正負關聯規則的數量遠遠大于在支持度-置信度框架下得到的關聯規則的數量。在支持度-置信度框架下得到的關聯規則只是滿足了最小支持度和置信度的強關聯規則。該算法不僅挖掘出了有趣的正關聯規則，還把有趣的帶實際意義的負關聯規則也進行了挖掘，所以在整體上比經典算法要有效得多。

6 結束語

為了能夠挖掘出有效的正負關聯規則，在現有幾種興趣度度量基礎上提出了一種新的興趣度度量。在真實的超市購物數據集上進行了算法驗證，根據相關正負興趣度度量的性質對強關聯規則進行篩選，挖掘出了有趣的正負關聯規則，證明了該算法的有效性。

參考文獻：

[1] SHEU J J,CHU K T.Mining association rules between posi-

tive word-of-mouth on social network sites and consumer acceptance:a study for derivative product of animations,comics,and games[J].Telematics & Informatics,2017,34(4):22-33.

[2] TALAEIKHOEI M,NEMATIREZVANI H,FISCHERAUER S F,et al.Emotion regulation strategies mediate the associations of positive and negative affect to upper extremity physical function[J].Comprehensive Psychiatry,2017,75:85-93.

[3] KEARNS S M,CREAVEN A M.Individual differences in positive and negative emotion regulation:which strategies explain variability in loneliness?[J]. Personality and Mental Health,2016,11(1):64-74.

[4] REIMERT I,FONG S,RODENBURG T B,et al.Emotional states and emotional contagion in pigs after exposure to a positive and negative treatment[J].Applied Animal Behaviour Science,2017,193:37-42.

[5] WANG Bowei,CHEN Dan,SHI Benyun,et al.Comprehensive association rules mining of health examination data with an extended FP-Growth method[J].Mobile Networks & Applications,2017,22(2):267-274.

[6] 呂杰林,陳是維.基于相關性度量的關聯規則挖掘[J].浙江大學學報：理學版,2012,39(3):284-288.

[7] WU Xindong,ZHANG Chengqi,ZHANG Shichao.Efficient mining of both positive and negative association rules[J].ACM Transactions on Information Systems,2004,22(3):381-405.

[8] 余 玲.客觀興趣度模型及其在關聯分類中的應用研究[D].成都:西南交通大學,2010.

[9] 邢 玲,宋章浩,馬 強.基于混合行為興趣度的用戶興趣模型[J].計算機應用研究,2016,33(3):661-664.

[10] WROBEL M,SUNDARARAGHAVAN H G.Positive and negative cues for modulating neurite dynamics and receptor expression[J].Biomedical Materials,2017,12(2):025016.

[11] 王微微,夏秀峰,李曉明.一種基于用戶行為的興趣度模型[J].計算機工程與應用,2012,48(8):148-151.

[12] 梁寶華,蔡 敏.正負關聯規則挖掘方法的改進及其應用[J].計算機工程,2010,36(16):44-46.

[13] 張玉芳,熊忠陽,彭 燕,等.基于興趣度含正負項目的關聯規則挖掘方法[J].電子科技大學學報,2010,39(3):407-411.

[14] 李偉東,倪志偉,劉 曉.基于興趣度的關聯規則挖掘[J].計算機技術與發展,2007,17(6):80-82.

[15] 陳寧軍,高志年.一種改進的正負關聯規則挖掘算法[J].計算機科學,2011,38(12):191-193.