王 璇

(福建對(duì)外經(jīng)濟(jì)貿(mào)易職業(yè)技術(shù)學(xué)院信息技術(shù)系，福建 福州 350016)

一種帶興趣度的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法

王 璇

(福建對(duì)外經(jīng)濟(jì)貿(mào)易職業(yè)技術(shù)學(xué)院信息技術(shù)系，福建 福州 350016)

針對(duì)負(fù)關(guān)聯(lián)規(guī)則挖掘所帶來(lái)的問(wèn)題，提出加入最大支持度來(lái)控制頻繁項(xiàng)集生成規(guī)模，改進(jìn)了相關(guān)性的計(jì)算公式，并將其用作正負(fù)關(guān)聯(lián)規(guī)則的興趣度來(lái)剔除無(wú)興趣的關(guān)聯(lián)規(guī)則，限制關(guān)聯(lián)規(guī)則中的前后件項(xiàng)目個(gè)數(shù)來(lái)保證挖掘出的關(guān)聯(lián)規(guī)則的實(shí)用性和可理解性。最后，給出一種能夠同時(shí)挖掘正負(fù)關(guān)聯(lián)規(guī)則的算法，實(shí)驗(yàn)結(jié)果表明算法是有效的、可行的。

正負(fù)關(guān)聯(lián)規(guī)則;最大支持度;興趣度;相關(guān)性

0 引言

關(guān)聯(lián)規(guī)則挖掘最早由Agrawal等人在文獻(xiàn)[1]中提出，它用形如A?B的蘊(yùn)含式來(lái)表示項(xiàng)集A的出現(xiàn)帶動(dòng)項(xiàng)集B的出現(xiàn)，從而揭示了數(shù)據(jù)之間有意義的關(guān)聯(lián)。關(guān)聯(lián)規(guī)則自提出以來(lái)得到深入的研究，并廣泛應(yīng)用于商業(yè)、金融、電信等行業(yè)。但是，傳統(tǒng)形式的關(guān)聯(lián)規(guī)則只能挖掘出數(shù)據(jù)之間正面的關(guān)聯(lián)，而無(wú)法發(fā)現(xiàn)數(shù)據(jù)間的負(fù)關(guān)聯(lián)，即項(xiàng)集A的出現(xiàn)會(huì)降低項(xiàng)集B的出現(xiàn)或使B不出現(xiàn)。在實(shí)際應(yīng)用中，尤其是在投資分析和競(jìng)爭(zhēng)分析等許多領(lǐng)域，負(fù)關(guān)聯(lián)規(guī)則與正關(guān)聯(lián)規(guī)則一起為正確決策提供更加全面的信息，其作用是不可低估的。

相比正關(guān)聯(lián)規(guī)則，人們對(duì)負(fù)關(guān)聯(lián)規(guī)則的研究起步較晚。1997年，文獻(xiàn)[2]中首次提到了2個(gè)頻繁項(xiàng)集間的負(fù)關(guān)聯(lián)問(wèn)題;文獻(xiàn)[3]研究了強(qiáng)負(fù)關(guān)聯(lián)規(guī)則問(wèn)題;文獻(xiàn)[4]對(duì)負(fù)關(guān)聯(lián)規(guī)則進(jìn)行了形式定義;文獻(xiàn)[5]引入相關(guān)性度量來(lái)區(qū)別不同形式的正負(fù)關(guān)聯(lián)規(guī)則，避免挖掘出互相矛盾的關(guān)聯(lián)規(guī)則;文獻(xiàn)[6]通過(guò)引入過(guò)頻繁項(xiàng)集解決負(fù)關(guān)聯(lián)規(guī)則中的頻繁項(xiàng)集爆炸問(wèn)題。研究表明，引入負(fù)關(guān)聯(lián)規(guī)則后，生成的頻繁項(xiàng)集數(shù)量將迅速增長(zhǎng)，同時(shí)也出現(xiàn)了更多無(wú)用及矛盾的規(guī)則。本文通過(guò)引入最大支持度及最小興趣度等約束條件，有效地控制了負(fù)關(guān)聯(lián)規(guī)則挖掘中頻繁項(xiàng)集數(shù)量的過(guò)快增長(zhǎng)，并進(jìn)一步約束生成的關(guān)聯(lián)規(guī)則，較好地解決了以上問(wèn)題。

1 相關(guān)知識(shí)

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

設(shè) I={i1，i2，…，in}是 n個(gè)不同項(xiàng)目的集合，D={T1，T2…，Tm}為事務(wù)數(shù)據(jù)庫(kù)，其中事務(wù) Tj?I(1≤j≤m)。一條負(fù)關(guān)聯(lián)規(guī)則就是一個(gè)形如A?﹁ B(或﹁ A?B，﹁ A?﹁ B)的蘊(yùn)涵式[4]，其中，A，B?T，A∩B=?，且滿足 sup(A?﹁ B)≥min_sup，conf(A?﹁ B)≥min_conf。

對(duì)于一條支持度為sup，置信度為conf的負(fù)關(guān)聯(lián)規(guī)則A?﹁B，表示在事務(wù)數(shù)據(jù)庫(kù)D中有(100×sup)%的事務(wù)包含A但不包含B，包含A的事務(wù)中有(100×conf)%的事務(wù)不包含B。負(fù)關(guān)聯(lián)規(guī)則揭示了事務(wù)之間互相排斥的一種關(guān)系，具有十分重要的現(xiàn)實(shí)意義。

限于篇幅，僅討論A?﹁B型的負(fù)關(guān)聯(lián)規(guī)則挖掘問(wèn)題，其思想亦適合于﹁A?B型的負(fù)關(guān)聯(lián)規(guī)則。另外，﹁A?﹁B型的負(fù)關(guān)聯(lián)規(guī)則挖掘比較簡(jiǎn)單，實(shí)際應(yīng)用不多，因此不再討論。

1.2 負(fù)關(guān)聯(lián)規(guī)則的支持度、置信度計(jì)算

與正關(guān)聯(lián)規(guī)則挖掘相同，要生成包含負(fù)項(xiàng)目的頻繁項(xiàng)集，需要計(jì)算每個(gè)負(fù)項(xiàng)集的支持度。由于負(fù)項(xiàng)目表示不發(fā)生的項(xiàng)集，直接計(jì)算其支持度比較困難。文獻(xiàn)[5]中提出了一種利用相應(yīng)正項(xiàng)集的支持度導(dǎo)出負(fù)項(xiàng)集支持度的方法，即負(fù)關(guān)聯(lián)規(guī)則AB的支持度計(jì)算公式為:

同理可得置信度計(jì)算公式，即:

2 負(fù)關(guān)聯(lián)規(guī)則挖掘中的問(wèn)題及解決方法

2.1 過(guò)頻繁項(xiàng)集與最大支持度

在傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘中，對(duì)頻繁項(xiàng)集剪枝的策略是根據(jù)頻繁項(xiàng)集的Apriori性質(zhì)，即一個(gè)頻繁項(xiàng)集的所有非空子集都必須是頻繁的，反之，任意非頻繁項(xiàng)集的所有超集也一定是非頻繁的。對(duì)于一般的數(shù)據(jù)集，大多數(shù)項(xiàng)集的支持度都不高，因此，在頻繁項(xiàng)集生成過(guò)程中，使用最小支持度對(duì)候選項(xiàng)集的重要程度進(jìn)行評(píng)估，如果某個(gè)項(xiàng)集支持度小于最小支持度閾值，則其所有超集也是非頻繁的，因而可以對(duì)該項(xiàng)集及所有超集進(jìn)行剪枝，從而有效地減少計(jì)算量。相比于正關(guān)聯(lián)規(guī)則挖掘，在負(fù)關(guān)聯(lián)規(guī)則挖掘中，高支持度的負(fù)項(xiàng)集非常普遍，因?yàn)槠鋵?duì)應(yīng)的正項(xiàng)目的支持度若為sup(i)，則該負(fù)項(xiàng)目的支持度sup(﹁i)=1-sup(i)≈1。因此，在負(fù)關(guān)聯(lián)規(guī)則挖掘中，僅僅依靠最小支持度來(lái)對(duì)項(xiàng)集剪枝，效果并不理想，無(wú)法控制頻繁項(xiàng)集的指數(shù)級(jí)增長(zhǎng)。

為此，本文引入最大支持度，對(duì)支持度大于最大支持度的包含負(fù)項(xiàng)目的項(xiàng)集稱為過(guò)頻繁項(xiàng)集，參照文獻(xiàn)[6]給出其定義:

定義1設(shè)能產(chǎn)生有興趣的關(guān)聯(lián)規(guī)則項(xiàng)集的最大支持度為max_sup，項(xiàng)集X為包含負(fù)項(xiàng)目的項(xiàng)集，如果sup(X)＞max_sup，則稱X為過(guò)頻繁項(xiàng)集。

文獻(xiàn)[6]中還證明了過(guò)頻繁項(xiàng)集的一個(gè)性質(zhì):

性質(zhì)1過(guò)頻繁項(xiàng)集及其所有超集不可能產(chǎn)生有興趣的關(guān)聯(lián)規(guī)則。

反之，對(duì)于滿足最大支持度閾值的項(xiàng)集A，即對(duì)sup(A)≤max_sup，容易證明以下性質(zhì):

性質(zhì)2設(shè)項(xiàng)集A滿足最大支持度閾值，則其所有超集也滿足最大支持度閾值。

證明設(shè)項(xiàng)集B?A，則有sup(B)≤sup(A)。已知sup(A)≤max_sup，故有sup(B)≤sup(A)≤max_sup，命題得證。

由性質(zhì)1和性質(zhì)2可知，對(duì)項(xiàng)集最大支持度的計(jì)算只要在生成頻繁1-項(xiàng)集時(shí)剔除支持度大于最大支持度的項(xiàng)集，即可保證后面的頻繁k-項(xiàng)集(k≥2)都滿足最大支持度閾值。因此，在頻繁項(xiàng)集生成過(guò)程中，結(jié)合最大支持度和最小支持度的閾值限制，對(duì)項(xiàng)集進(jìn)行剪枝，可以有效地控制頻繁項(xiàng)集的生成規(guī)模。

2.2 關(guān)聯(lián)規(guī)則的相關(guān)性

許多研究表明，基于傳統(tǒng)的支持度—置信度評(píng)價(jià)框架生成的關(guān)聯(lián)規(guī)則很多是無(wú)意義的，甚至是矛盾的，主要原因之一是支持度—置信度框架無(wú)法對(duì)規(guī)則前后件之間的關(guān)聯(lián)程度作更深入的評(píng)價(jià)。Brin等人在文獻(xiàn)[7]中提出了相關(guān)性的概念，用于判斷規(guī)則前后件的相關(guān)程度，具體定義如下:

corrA，B的取值范圍是[0，∞)，具體的取值有3種關(guān)系:

①corrA，B＞1，此時(shí) A和 B為正相關(guān)，表示二者相互提升了對(duì)方出現(xiàn)的可能性，值越大則關(guān)聯(lián)程度越高;

②corrA，B=1，此時(shí)A和B相互獨(dú)立，表示二者的出現(xiàn)與對(duì)方無(wú)關(guān);

③corrA，B＜1，此時(shí) A和 B為負(fù)相關(guān)，表示二者相互降低了對(duì)方出現(xiàn)的可能性，值越小則負(fù)關(guān)聯(lián)程度越高。

早期的研究只保留了相關(guān)性大于1的規(guī)則，即正關(guān)聯(lián)規(guī)則，而其他情況只進(jìn)行簡(jiǎn)單的刪除。文獻(xiàn)[5]中使用相關(guān)性概念來(lái)區(qū)分正負(fù)關(guān)聯(lián)規(guī)則，并證明了當(dāng)corrA，B＞1時(shí)，產(chǎn)生A?B型規(guī)則;則有:

當(dāng) corrA，B＜1 時(shí)，產(chǎn)生 A?﹁ B 型規(guī)則;當(dāng) corrA，B=1時(shí)，不生成關(guān)聯(lián)規(guī)則。

2.3 相關(guān)性的改造

文獻(xiàn)[8]中對(duì)相關(guān)性進(jìn)行了修正，將其用作正負(fù)關(guān)聯(lián)規(guī)則的興趣度，但是依然沒有克服相關(guān)性取值的缺陷，即其取值沒有上限，且在值1兩側(cè)不對(duì)稱，這將不便于用戶設(shè)置統(tǒng)一的門檻值。本文在文獻(xiàn)[8]的基礎(chǔ)上對(duì)相關(guān)性加以進(jìn)一步的改造，將其值域映射到[-1，1]區(qū)間內(nèi)，從而作為正負(fù)關(guān)聯(lián)規(guī)則評(píng)價(jià)的一個(gè)新的興趣度，定義如下:

定義3對(duì)一條候選關(guān)聯(lián)規(guī)則A?B，其興趣度為:

假設(shè)λ =sup(B)為常數(shù)(0 ＜λ ＜1)，intrA，B可改寫為:

由圖1 可以看出，intrA，B∈(0，1]時(shí)，A 和B 正相關(guān)，此時(shí)產(chǎn)生 A?B 型規(guī)則;intrA，B∈(0，-1]時(shí)，A和 B負(fù)相關(guān)，此時(shí)產(chǎn)生 A?﹁B型規(guī)則;intrA，B=0時(shí)，A和B互相獨(dú)立，不生成規(guī)則。具體計(jì)算時(shí)可將式(1)展開，即:

圖 1 intrA，B與 corrA，B的關(guān)系

由于有最小/最大支持度的限制，sup(A)和sup(B)的值域?yàn)?0，1)，因此 intrA，B的取值范圍為(-1，1)。在正負(fù)項(xiàng)目一起進(jìn)行挖掘時(shí)，為方便設(shè)置統(tǒng)一的門檻值，可將intrA，B＜0的情況映射到(0，1)的區(qū)域，即|intrA，B|≥min_intr，而不必再分別對(duì)正、負(fù)關(guān)聯(lián)規(guī)則設(shè)置不同的興趣度閾值。

3 算法描述

雖然引入最大支持度從一定程度上控制了包含負(fù)項(xiàng)目的頻繁項(xiàng)集的規(guī)模，以及加入興趣度閾值來(lái)進(jìn)一步約束生成的關(guān)聯(lián)規(guī)則，但是仍然會(huì)生成大量的關(guān)聯(lián)規(guī)則，尤其當(dāng)數(shù)據(jù)集中包含的項(xiàng)目比較多時(shí)。實(shí)際上，若一條關(guān)聯(lián)規(guī)則所包含的項(xiàng)目個(gè)數(shù)越多，該規(guī)則的可理解性就越差，所具有的實(shí)用價(jià)值往往也越低。因此，還要對(duì)關(guān)聯(lián)規(guī)則的前后件項(xiàng)目個(gè)數(shù)進(jìn)行限制，以保證挖掘出來(lái)的關(guān)聯(lián)規(guī)則的實(shí)用性和可理解性。

包含正負(fù)項(xiàng)目的關(guān)聯(lián)規(guī)則挖掘可以分解為2個(gè)子問(wèn)題:①求出事務(wù)數(shù)據(jù)庫(kù)D中的所有正負(fù)項(xiàng)目的頻繁項(xiàng)集L;②從頻繁項(xiàng)集L中生成滿足約束條件的所有正負(fù)關(guān)聯(lián)規(guī)則。對(duì)第1個(gè)子問(wèn)題已有多個(gè)現(xiàn)成的算法可以借鑒，如 Apriori、FP-growth等，本算法基于FP樹，采用含正負(fù)項(xiàng)目的FP 樹構(gòu)造算法Con_FPN_tree[9]。因此，第2個(gè)子問(wèn)題是算法的核心問(wèn)題。

算法:帶興趣度的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法IPNARM。

輸入:事務(wù)數(shù)據(jù)庫(kù)D，最小支持度 min_sup，最大支持度max_sup，最小置信度min_conf，最小興趣度min_intr，前件包含最大項(xiàng)目個(gè)數(shù)max_former，后件包含最大項(xiàng)目個(gè)數(shù)max_back。

輸出:正關(guān)聯(lián)規(guī)則PRS，負(fù)關(guān)聯(lián)規(guī)則NRS。

①掃描數(shù)據(jù)庫(kù)D，根據(jù)最小支持度min_sup和最大支持度max_sup得到滿足條件的頻繁1-項(xiàng)集，調(diào)用Con_FPN_tree算法，得到包含正負(fù)項(xiàng)目的FPN_tree，再?gòu)腇PN_tree中挖掘出頻繁項(xiàng)集L;

②PRS=?，NRS=?;

③for each li∈L

IPNARM算法的基本思想:①在[min_sup，max_sup]閾值范圍內(nèi)，從FPN_tree中挖掘出所有包含正負(fù)項(xiàng)目的頻繁項(xiàng)集L。②在L中逐一考查關(guān)聯(lián)規(guī)則前件A和后件B，如果滿足前后件項(xiàng)目個(gè)數(shù)的要求，則計(jì)算規(guī)則的興趣度，判斷生成關(guān)聯(lián)規(guī)則的類型，轉(zhuǎn)③，否則執(zhí)行②。③若興趣度滿足最小興趣度閾值且置信度大等于最小置信度，則輸出相應(yīng)的關(guān)聯(lián)規(guī)則，否則轉(zhuǎn)②，直到挖掘完所有的關(guān)聯(lián)規(guī)則。

4 實(shí)驗(yàn)及結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了對(duì)比驗(yàn)證本文算法的性能，在CPU為AMD Athlon 2.01 GHz，內(nèi)存 1 GB，操作系統(tǒng)為Windows XP的環(huán)境下，用Visual C++6.0分別實(shí)現(xiàn)了IPNARM算法、PAR＆NAR_on_P-S_measure算法[8](簡(jiǎn)稱PAR ＆NAR 算法)和文獻(xiàn)[6]中的算法2(簡(jiǎn)稱算法2)。采用的實(shí)驗(yàn)數(shù)據(jù)集來(lái)源于http://www.ics.uci.edu/～ mlearn/MLRepository.html上所提供的蘑菇數(shù)據(jù)庫(kù)(Mushroom Database)，該數(shù)據(jù)庫(kù)有8 124條記錄，事務(wù)的平均長(zhǎng)度為23，包含120個(gè)項(xiàng)目。

IPNARM算法所使用的參數(shù)為:max_sup=0.95，min_conf=0.5，min_intr=0.5，max_former=2，max_back=2。PAR＆NAR算法使用的參數(shù)為:min_conf=0.5，min_intr=0.5;算法 2 使用的參數(shù)為:max_sup=0.95，Nmax_neg=2。分別對(duì)3種算法挖掘的正負(fù)關(guān)聯(lián)規(guī)則數(shù)量和運(yùn)行時(shí)間進(jìn)行對(duì)比實(shí)驗(yàn)。

4.2 結(jié)果分析

實(shí)驗(yàn)結(jié)果如圖2、圖3所示。

圖2 3種算法挖掘出的關(guān)聯(lián)規(guī)則數(shù)量

圖3 3種算法的執(zhí)行時(shí)間

5 結(jié)語(yǔ)

針對(duì)負(fù)關(guān)聯(lián)規(guī)則挖掘所帶來(lái)的問(wèn)題，提出加入最大支持度來(lái)控制頻繁項(xiàng)集生成規(guī)模，改進(jìn)了相關(guān)性的計(jì)算公式，并將其用作正負(fù)關(guān)聯(lián)規(guī)則的興趣度來(lái)剔除無(wú)興趣的關(guān)聯(lián)規(guī)則，限制關(guān)聯(lián)規(guī)則中的前后件項(xiàng)目個(gè)數(shù)來(lái)保證挖掘出來(lái)的關(guān)聯(lián)規(guī)則的實(shí)用性和可理解性。提出一種能夠同時(shí)挖掘正負(fù)關(guān)聯(lián)規(guī)則的算法IPNARM，通過(guò)對(duì)比實(shí)驗(yàn)表明算法是有效可行的，尤其是當(dāng)數(shù)據(jù)集中所包含的項(xiàng)目個(gè)數(shù)比較多時(shí)，能夠保證關(guān)聯(lián)規(guī)則挖掘的順利進(jìn)行。

[1]Agrawal R，Imielinaki T，Swami A.Mining Association Rules Between Sets of Items in Large Databases[C]//Washington.D C:Proc of the ACM SIGMOD Conference on Management of Data，1993:207 -216.

[2]Brin S，Motwani R，Silverstein C.Beyond Market:Generalizing Association Rules to Correlations[C]//Processing of the ACM SIGMOD Conference 1997.New York:ACM Press，1997:265 -276.

[3]Savasere A，Omiecinski E，Navathe S.Mining for Strong Negative Associations in a Large Database of Customer Transactions[C]//Proceedings of the IEEE 14th Intl Conference on Data Engineering.Los Alamitos:IEEE - CS，1998:494 -502.

[4]WU Xindong，ZHANG Chengqi，ZHANG Shichao.Mining Both Positive and Negative Association Rules[C]//Proceedings of the 19th International Conference on Machine Learning(ICML- 2002).San Francisco:Morgan Kaufmann Publishers，2002:658-665.

[5]董祥軍，王淑靜，宋瀚濤，等.負(fù)關(guān)聯(lián)規(guī)則的研究[J].北京理工大學(xué)學(xué)報(bào)，2004，24(11):978 -981.

[6]馬占欣，陸玉昌.負(fù)關(guān)聯(lián)規(guī)則挖掘中的頻繁項(xiàng)集爆炸問(wèn)題[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版，2007，47(7):1212 -1215.

[7]Brin S，Motwani R，Silverstein C.Beyond market:Generalizing Association Rules to Correlations[C]//Processing of the ACM SIGMOD Conference 1997.New York:ACM Press，1997:265 -276.

[8]董祥軍，宋瀚濤，姜合，等.基于最小興趣度的正、負(fù)關(guān)聯(lián)規(guī)則挖掘[J].計(jì)算機(jī)工程與應(yīng)用，2004，27(12):24 -26.

[9]張玉芳，彭燕，劉君，等.一種含負(fù)項(xiàng)目的一般化關(guān)聯(lián)規(guī)則挖掘算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006，27(20):3904 -3908.

Algorithm with Interest Measure for Mining Positive and Negative Association Rules

WANG Xuan

(Depatrment of Information Technology，F(xiàn)ujian International Business Economic College，F(xiàn)uzhou 350016)

In terms of the negative association rules mining problems，maximum support is proposed to be used to control the growth of the frequent itemsets.The formula of correlation is improved and used as an interest measure for the positive and negative association rules to get rid of the uninterested rules.The former and back association rules are limited to ensure the practicability and comprehensibility of the association rules.At last，this paper gives the algorithm which can simultaneously mine positive and negative association rules.And the experimental results show that this algorithm is efficient and feasible.

positive and negative association rules;maximum support;interest measure;correlation

TP311.13

A

1671-0436(2011)03/04-0016-05

2011-05-19

王璇(1978— )，女，講師。

責(zé)任編輯:唐海燕