數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則衡量方法的改進(jìn)

趙軍民,王軍豪,高 蔚

(河南城建學(xué)院,河南平頂山467036)

1 關(guān)聯(lián)規(guī)則

假設(shè)I是一個項集,對于一個特定的事務(wù)數(shù)據(jù)庫D,其中每個事務(wù)T是I的非空子集,即每一個交易都與一個唯一的標(biāo)識符TID(Transaction ID)對應(yīng)。對項集I和事務(wù)數(shù)據(jù)庫D,T中所有滿足用戶指定的最小支持度Minsup(Minsupport)的項集(即大于或者等于Minsup的項集I的非空子集)稱為頻繁項集(Frequent Itemsets)。在頻繁項集中挑選出所有不被其他元素包含的頻繁項集稱為最大頻繁項集(Maximum Frequent Itemsets)。事務(wù)數(shù)據(jù)庫D在項集I上滿足最小支持度以及最小信任度Minconf(Minconfidence)的關(guān)聯(lián)規(guī)則被稱為強(qiáng)關(guān)聯(lián)規(guī)則,否則就被稱為弱關(guān)聯(lián)規(guī)則[1]。

2 基于興趣度約束的關(guān)聯(lián)規(guī)則

在數(shù)據(jù)挖掘的過程中,通常情況下可能會挖掘出上千條的規(guī)則,但是并不是所有的規(guī)則都對用戶有用。為了提高挖掘出的規(guī)則的質(zhì)量,使之對用戶來說更新穎、更容易理解,就需要一個更有效的挖掘算法。為了以用戶的需求和興趣為最大目標(biāo),盡量減少掃描次數(shù),將無意義的和虛假的規(guī)則剔除掉,這里引入了一種約束條件-興趣度約束。當(dāng)前最常見、也是最常用的兩個興趣度度量是支持度和信任度,但是僅靠這兩個度量標(biāo)準(zhǔn)還存在一定的缺陷[2]:

⑴會產(chǎn)生大量的規(guī)則,而其中的大部分是顯而易見的或不相關(guān)的;

⑵用戶沒有充分利用領(lǐng)域知識和職業(yè)直覺。用戶的職業(yè)直覺往往對知識發(fā)現(xiàn)的過程具有重大的價值;

⑶沒有提供好的度量令人感興趣程度的方法,而從數(shù)據(jù)中發(fā)現(xiàn)令人感興趣的規(guī)則是數(shù)據(jù)挖掘的一個重要目標(biāo)。

在實(shí)際應(yīng)用中,挖掘的關(guān)聯(lián)規(guī)則可能因?yàn)橐韵略蚴ビ腥ば?①挖掘的規(guī)則符合先驗(yàn)知識或期望值;②挖掘的規(guī)則可能涉及非有趣屬性或?qū)傩越M合;③規(guī)則冗余。本文主要討論關(guān)聯(lián)規(guī)則令人感興趣程度的度量問題,并給出一種新的綜合度量方法。

3 關(guān)聯(lián)規(guī)則的綜合度量

要看一條規(guī)則是不是有趣的,要從確定性、有用性、非預(yù)期性和簡潔性幾個方面進(jìn)行綜合的度量[3]。

3.1 確定性

確定性是規(guī)則的有效性以及值得信賴程度的反映。在挖掘過程中,對于像A?B這樣的關(guān)聯(lián)規(guī)則,它的確定性度量就是信任度。信任度是對關(guān)聯(lián)規(guī)則的準(zhǔn)確度的衡量,表示一個商品的購買暗示著另一個商品的購買。

3.2 有用性

有用性是用來衡量一條規(guī)則是否具有有趣性的一個重要因素,它可以用支持度來進(jìn)行度量。支持度表示用這條規(guī)則可以推出百分之幾的目標(biāo),它也是對關(guān)聯(lián)規(guī)則重要性的度量,支持度說明了這條規(guī)則在所有事務(wù)中占多大的代表性。

3.3 簡潔性

簡潔性是針對規(guī)則的形式而言的,一般指規(guī)則的總體簡潔性,是用來衡量關(guān)聯(lián)規(guī)則的最終可理解程度的指標(biāo),并用規(guī)則的屬性個數(shù)或者規(guī)則中出現(xiàn)的操作符來進(jìn)行定義的[4]。它表現(xiàn)在兩個方面:一方面表現(xiàn)在規(guī)則的項數(shù)上,如果規(guī)則項數(shù)很多,會不利于對這條規(guī)則的理解。因此,規(guī)則的項數(shù)越少,規(guī)則的簡潔性越好。另一方面表現(xiàn)在規(guī)則所包含的抽象層次上,規(guī)則包含的抽象層次越高,它對應(yīng)的解釋力越強(qiáng)。

3.4 非預(yù)期性

具有非預(yù)期性的規(guī)則是那些提供新的信息或者跟先驗(yàn)知識相矛盾的規(guī)則。非預(yù)期的規(guī)則出乎客戶的意料,與用戶的期望相矛盾。傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法中,用條件概率P(B︱A)=P(A∪B)/P(A)來表示,也就是用信任度作為約束對規(guī)則的非預(yù)期性進(jìn)行判斷,但它只是給定的A和B的條件概率的估計值,而并沒有度量A和B之間蘊(yùn)涵的實(shí)際強(qiáng)度。我們將項集I1和I2之間的影響程度用提升度來進(jìn)行度量。

定義1:提升度(lift)是利用相關(guān)分析來描述規(guī)則內(nèi)在價值的度量,它所描述的是項集I1對I2的影響力的大小。提升度越高,表示I1的出現(xiàn)對I2出現(xiàn)的可能性影響越大,它是對I1和I2之間蘊(yùn)涵的實(shí)際強(qiáng)度的度量。提升度是一個比值:

也可以用P(I2︱I1)/P(I2)來表示。它又分為兩種情況:

⑴當(dāng)lift＞1時,表示I1和I2是相關(guān)的,代表I1的出現(xiàn)蘊(yùn)涵了I2的出現(xiàn),此規(guī)則是非預(yù)期的、有效的或者有趣的。

⑵當(dāng)lift＜1時,表示 I1和I2是不相關(guān)的,規(guī)則不是非預(yù)期的,是無效的、無趣的,應(yīng)將其刪除。

提升度的值越大,表明兩者之間的相關(guān)性就越強(qiáng),規(guī)則越有效、越有趣,其利用的價值也就越大[5]。

根據(jù)上面規(guī)則的度量標(biāo)準(zhǔn),需要對強(qiáng)關(guān)聯(lián)度重新進(jìn)行定義,定義如下所示:

定義2:對于事務(wù)數(shù)據(jù)庫D,如果I1?I2能同時滿足以下條件,則稱之為強(qiáng)關(guān)聯(lián)規(guī)則,否則就稱之為弱關(guān)聯(lián)規(guī)則,其中Maxlen為最大規(guī)劃長度。

那么,在事務(wù)數(shù)據(jù)庫D中挖掘關(guān)聯(lián)規(guī)則的問題也就變?yōu)?產(chǎn)生所有支持度、信任度分別大于最小支持度和最小信任度,規(guī)則長度小于最小規(guī)則長度,并且提升度的值大于1的關(guān)聯(lián)規(guī)則,也就是找出所有的強(qiáng)關(guān)聯(lián)規(guī)則。

4 基于綜合度量的關(guān)聯(lián)規(guī)則算法設(shè)計

以Apriori算法為基礎(chǔ),保留原有的最小支持度、最小信任度這兩個衡量指標(biāo),并將提升度(lift)以及最大規(guī)則長度這兩個衡量標(biāo)準(zhǔn)引入到算法中,使之挖掘出更有趣、有效的關(guān)聯(lián)規(guī)則。

算法1:產(chǎn)生長度不超過Maxlen的頻繁項集

輸入:事務(wù)數(shù)據(jù)庫D;最小支持度閾值Minsup;最大規(guī)則長度的閾值Maxlen

輸出:頻繁項集L

算法2:產(chǎn)生有趣的關(guān)聯(lián)規(guī)則

輸入:頻繁項集L;最小支持度閾值Minsup;最小信任度閾值Minconf;提升度閾值lift;最大規(guī)則長度的閾值Maxlen

輸出:強(qiáng)關(guān)聯(lián)規(guī)則R

{頻繁項集Lk的所有子集

for每一個s都屬于SK

If信任度≥Minconf and提升＞1 then輸出強(qiáng)關(guān)聯(lián)規(guī)則R

5 算法實(shí)現(xiàn)及性能分析

使用Microsoft Visual Basic實(shí)現(xiàn)Apriori算法,并引入支持度、信任度、提升度及規(guī)則長度相結(jié)合的綜合度量標(biāo)準(zhǔn)。此程序可以任意輸入支持度、信任度、提升度和規(guī)則長度的閾值,并統(tǒng)計運(yùn)行過程所耗費(fèi)的時間。

程序界面如圖1所示。

圖1 關(guān)聯(lián)規(guī)則算法運(yùn)行界面

由于Apriori算法在運(yùn)行過程中需要多趟掃描數(shù)據(jù)庫,使得算法的運(yùn)行非常耗時。可以分別利用事務(wù)數(shù)據(jù)量為100、200、500、1000、2000、5000、10000和50000的數(shù)據(jù)集在相同環(huán)境下對程序進(jìn)行測試,結(jié)果如表1和圖2所示。

表1 算法運(yùn)行時間

圖2 算法運(yùn)行效率

表1、圖2利用綜合衡量的方法處理經(jīng)過整理的數(shù)據(jù)。這里設(shè)最小支持度為0.1,最小信任度為0.25,提升度(lift)應(yīng)大于或等于1,最大規(guī)則長度為3。通過運(yùn)行后得到了有效的關(guān)聯(lián)規(guī)則,與單純的支持度-信任度相比,減少了無效的關(guān)聯(lián)規(guī)則。表2是列出的部分關(guān)聯(lián)規(guī)則。

表2 關(guān)聯(lián)規(guī)則

6 小結(jié)

分析表1和圖2可知,隨著數(shù)據(jù)量的變大,算法所需時間呈指數(shù)上升趨勢。因?yàn)樾枰啻螔呙钄?shù)據(jù)庫,所以I/O負(fù)載太大,對每次K循環(huán),候選項集中的每個元素都必須通過掃描一次數(shù)據(jù)庫來進(jìn)行驗(yàn)證是否加入頻繁項集。另外,算法還有可能產(chǎn)生非常龐大的候選項集,太大的候選項集對時間和主存空間都是一種很大的挑戰(zhàn)。所以,該算法雖然有一定改善,仍需要進(jìn)一步的改進(jìn)。

[1]陳景民.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘技術(shù)[M].北京:電子工業(yè)出版社,2002.

[2]B Padmanab han,A Tu zhilin.Unexpectedness as a measure of interestingnessinknowledge discovery[J].DecisionSupport System,1999:303-318.

[3]Fayyad U,Piantesky-shapiro G.From Data Mining to Knowledge Discovery.Advances in Knowledge Discovery and Data Mining[J].California:AAAI Press,1996:1-363.

[4]Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].范明,孟小峰,譯.北京:機(jī)械工業(yè)出版社,2001.

[5]吳永梁,陳爍.基于改善度計算的有效關(guān)聯(lián)規(guī)則[J].計算機(jī)工程,2003,29(13):98-100.