趙軍民,王軍豪,高 蔚

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

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

假設(shè)I是一個(gè)項(xiàng)集,對(duì)于一個(gè)特定的事務(wù)數(shù)據(jù)庫(kù)D,其中每個(gè)事務(wù)T是I的非空子集,即每一個(gè)交易都與一個(gè)唯一的標(biāo)識(shí)符TID(Transaction ID)對(duì)應(yīng)。對(duì)項(xiàng)集I和事務(wù)數(shù)據(jù)庫(kù)D,T中所有滿足用戶指定的最小支持度Minsup(Minsupport)的項(xiàng)集(即大于或者等于Minsup的項(xiàng)集I的非空子集)稱為頻繁項(xiàng)集(Frequent Itemsets)。在頻繁項(xiàng)集中挑選出所有不被其他元素包含的頻繁項(xiàng)集稱為最大頻繁項(xiàng)集(Maximum Frequent Itemsets)。事務(wù)數(shù)據(jù)庫(kù)D在項(xiàng)集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ò)程中,通常情況下可能會(huì)挖掘出上千條的規(guī)則,但是并不是所有的規(guī)則都對(duì)用戶有用。為了提高挖掘出的規(guī)則的質(zhì)量,使之對(duì)用戶來(lái)說(shuō)更新穎、更容易理解,就需要一個(gè)更有效的挖掘算法。為了以用戶的需求和興趣為最大目標(biāo),盡量減少掃描次數(shù),將無(wú)意義的和虛假的規(guī)則剔除掉,這里引入了一種約束條件-興趣度約束。當(dāng)前最常見(jiàn)、也是最常用的兩個(gè)興趣度度量是支持度和信任度,但是僅靠這兩個(gè)度量標(biāo)準(zhǔn)還存在一定的缺陷[2]:

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

⑵用戶沒(méi)有充分利用領(lǐng)域知識(shí)和職業(yè)直覺(jué)。用戶的職業(yè)直覺(jué)往往對(duì)知識(shí)發(fā)現(xiàn)的過(guò)程具有重大的價(jià)值;

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

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

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

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

3.1 確定性

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

3.2 有用性

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

3.3 簡(jiǎn)潔性

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

3.4 非預(yù)期性

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

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

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

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

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

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

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

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

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

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

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

算法1:產(chǎn)生長(zhǎng)度不超過(guò)Maxlen的頻繁項(xiàng)集

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

輸出:頻繁項(xiàng)集L

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

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

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

{頻繁項(xiàng)集Lk的所有子集

for每一個(gè)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ī)則長(zhǎng)度相結(jié)合的綜合度量標(biāo)準(zhǔn)。此程序可以任意輸入支持度、信任度、提升度和規(guī)則長(zhǎng)度的閾值,并統(tǒng)計(jì)運(yùn)行過(guò)程所耗費(fèi)的時(shí)間。

程序界面如圖1所示。

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

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

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

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

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

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

6 小結(jié)

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

[1]陳景民.數(shù)據(jù)倉(cāng)庫(kù)與數(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]吳永梁,陳爍.基于改善度計(jì)算的有效關(guān)聯(lián)規(guī)則[J].計(jì)算機(jī)工程,2003,29(13):98-100.