基于水平加權(quán)關(guān)聯(lián)規(guī)則挖掘算法的研究*

亓文娟

(武夷學(xué)院)

0 引言

經(jīng)典的Apriori算法在進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)存在數(shù)據(jù)庫(kù)中各項(xiàng)目具有著相似的出現(xiàn)頻率和相同的重要性兩個(gè)前提假設(shè)，但是現(xiàn)實(shí)世界數(shù)據(jù)庫(kù)中的數(shù)據(jù)并非如此，當(dāng)數(shù)據(jù)庫(kù)中的各項(xiàng)目出現(xiàn)的頻率相差較大時(shí)，就會(huì)出現(xiàn)最小支持度閾值設(shè)置的兩難局面，為了解決這一問(wèn)題，Liu［1］等學(xué)者提出了一種多支持度關(guān)聯(lián)規(guī)則挖掘MS-Apriori算法，但該算法認(rèn)為各項(xiàng)目的重要性相同．文獻(xiàn)［2］提出了一種基于概率的多最小支持度關(guān)聯(lián)規(guī)則算法，有效挖掘出發(fā)生概率較低事件中的關(guān)聯(lián)規(guī)則，但存在著候選項(xiàng)集增多的缺點(diǎn)．文獻(xiàn)［3］提出了使用相關(guān)項(xiàng)目集中各項(xiàng)目最小支持度中的最大值來(lái)實(shí)現(xiàn)剪枝．為了區(qū)分各項(xiàng)目具有不同的重要性，需要根據(jù)各項(xiàng)目的重要性程度設(shè)置不同的權(quán)值，即加權(quán)關(guān)聯(lián)規(guī)則挖掘．加權(quán)關(guān)聯(lián)規(guī)則挖掘分為水平加權(quán)關(guān)聯(lián)規(guī)則挖掘、垂直加權(quán)關(guān)聯(lián)規(guī)則挖掘和混合加權(quán)關(guān)聯(lián)規(guī)則挖掘．水平加權(quán)關(guān)聯(lián)規(guī)則挖掘中項(xiàng)目的權(quán)值體現(xiàn)的是項(xiàng)目對(duì)決策的重要程度，垂直加權(quán)關(guān)聯(lián)規(guī)則挖掘中項(xiàng)目的權(quán)值隨著時(shí)間的變化而變化，混合加權(quán)關(guān)聯(lián)規(guī)則挖掘就是同時(shí)包含水平和垂直加權(quán)的關(guān)聯(lián)規(guī)則挖掘問(wèn)題．本文深入分析了水平加權(quán)關(guān)聯(lián)規(guī)則典型算法MINWAL(O)的思想，指出了算法的不足及優(yōu)化算法，旨在對(duì)加權(quán)關(guān)聯(lián)規(guī)則挖掘算法的擴(kuò)展和改進(jìn)奠定基礎(chǔ)．

1 加權(quán)關(guān)聯(lián)規(guī)則定義

假定事務(wù)數(shù)據(jù)庫(kù)D，項(xiàng)目的集合I={i1，i2，i3，…，in}，每一筆交易都是 I的子集，W={w1，w2，w3，…，wn}為I的權(quán)重集，其中項(xiàng)目ij對(duì)應(yīng)的權(quán)重是wj，表示項(xiàng)目的ij重要程度，且0≤ wj≤1，j={1，2，…，n}．加權(quán)關(guān)聯(lián)規(guī)則形如 X?Y，其中X?I，Y?I，并且X∩Y=?．項(xiàng)集X在D中的支持度和置信度分別用 Support(X)，confidence(X)表示，根據(jù)傳統(tǒng)關(guān)聯(lián)規(guī)則可得到加權(quán)關(guān)聯(lián)規(guī)則的相關(guān)定義．

定義1 項(xiàng)集加權(quán)支持度為:

定義2 X?Y的加權(quán)支持度為:

定義3 X?Y的加權(quán)置信度為:

加權(quán)關(guān)聯(lián)規(guī)則就是挖掘同時(shí)滿足最小加權(quán)支持度閾值和最小加權(quán)置信度閾值的規(guī)則．

2 加權(quán)關(guān)聯(lián)規(guī)則MINWAL(O)算法

由于引入了權(quán)重的概念，區(qū)分了項(xiàng)目的不同重要程度，但也帶來(lái)了新的問(wèn)題，即加權(quán)頻繁項(xiàng)集中不再符合普通關(guān)聯(lián)規(guī)則中頻繁項(xiàng)集所具有的反單調(diào)性，加權(quán)頻繁項(xiàng)集的子集有可能不是加權(quán)頻繁項(xiàng)集，因此必須采用新的解決方法．MINWAL(O)算法是由Cai C H等人在1998年提出的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法［4］，該算法提出k-支持期望的概念，用于候選項(xiàng)集的剪枝操作，縮小了候選項(xiàng)集的規(guī)模．

2．1 k- 支持期望

假定事務(wù)數(shù)據(jù)庫(kù)D，其交易總數(shù)為n，對(duì)于任一k-項(xiàng)目集X，其支持?jǐn)?shù)記為SC(X)，即事務(wù)數(shù)據(jù)庫(kù)D中包含X的交易個(gè)數(shù)．如果X為加權(quán)頻繁項(xiàng)集，則SC(X)應(yīng)滿足下式:

令I(lǐng)為所有項(xiàng)的集合，Y為一個(gè)q-項(xiàng)集(q＜k)，在剩余項(xiàng)目集合(I-Y)中，權(quán)值最大的前(k-q)個(gè)項(xiàng)為{wr1，wr2，…wr(k-q)}，則包含項(xiàng)集Y的任一k-項(xiàng)集的最大可能權(quán)值為

第1個(gè)和式是q-項(xiàng)集Y中各項(xiàng)目的權(quán)值之和，第2個(gè)和式是剩余的前k-q個(gè)項(xiàng)目的最大權(quán)值之和．由公式1和公式2可以推出:如果包含Y的k-項(xiàng)集是頻繁的，那么其最低支持?jǐn)?shù)必須滿足下式:

稱B(Y，k)是項(xiàng)集Y的k-支持期望．為了保證Y的k-項(xiàng)集有可能是頻繁的，這里支持?jǐn)?shù)采用向上取整的方式．在加權(quán)關(guān)聯(lián)規(guī)則挖掘中對(duì)候選頻繁項(xiàng)集進(jìn)行剪枝的依據(jù)是B(Y，k)．

2．2MINWAL(O)算法

MINWAL(O)算法是基于Apriori算法的逐層搜索迭代思想，兩個(gè)算法都是通過(guò)頻繁項(xiàng)集來(lái)生成候選項(xiàng)集，但剪枝的依據(jù)不同，Apriori算法采用Apriori性質(zhì)進(jìn)行剪枝，而MINWAL(O)算法采用項(xiàng)集的k-支持期望進(jìn)行剪枝，即保守估算任何可能成為其他加權(quán)頻繁項(xiàng)集子集的候選項(xiàng)，如果候選項(xiàng)的支持?jǐn)?shù)不小于k-支持期望值就予以保留，否則刪除．MINWAL(O)算法的偽代碼如下:

MINWAL(O)算法的步驟如下:

MINWAL(O)算法:挖掘加權(quán)關(guān)聯(lián)規(guī)則．

輸入:(1)交易數(shù)據(jù)庫(kù)D，權(quán)重集W;

(2)最小加權(quán)支持度閾值wminsup和最小置信度閾值minconf;

輸出:加權(quán)關(guān)聯(lián)規(guī)則

begin

(1)size=Scan(D);//找出交易數(shù)據(jù)庫(kù)D中頻繁項(xiàng)集的最大可能長(zhǎng)度

(2)L=?;

(3)for(i=1;i≤size;i++)//最大候選項(xiàng)集長(zhǎng)度不大于size

(4)Ci=Li=?;

(5)for each transaction in D do

(6)(SC，C1)=Count(D，W);//累計(jì)1-項(xiàng)集的支持?jǐn)?shù)，計(jì)算1-項(xiàng)集的k-支持期望，保留支持?jǐn)?shù)不小于k-支持期望的1-項(xiàng)集為C1

(7)for(k=2;k≤size;k++){

(8)Ck=Join(Ck-1);//Ck是候選k-項(xiàng)集，Join(Ck-1)與Apriori算法的Gen函數(shù)類似

(9)Ck=Prune(Ck);//Prune(Ck)用于k-項(xiàng)集的剪枝操作

(10)(Ck，Lk)=Checking(Ck，D);//Lk是頻繁k-項(xiàng)集，遍歷交易數(shù)據(jù)庫(kù)D，更新Ck中所有候選項(xiàng)集的支持計(jì)數(shù)

(11)L=L∪Lk;}

(12)Rules．Set=Rules．Gen(L);// 與Apriori算法相同，根據(jù)L中的頻繁項(xiàng)集生成符合最小置信度閾值minconf的加權(quán)關(guān)聯(lián)規(guī)則

End

2．3 算法不足

MINWAL(O)算法雖然解決了加權(quán)關(guān)聯(lián)規(guī)則挖掘中加權(quán)頻繁項(xiàng)集的子集可以不是加權(quán)頻繁項(xiàng)集的問(wèn)題，但是由于該算法是基于Apriori算法思想，也存在著不足之處:(1)頻繁掃描數(shù)據(jù)庫(kù)，生成大量候選項(xiàng)集，運(yùn)行效率低，極大的影響了算法的性能;(2)利用求和權(quán)值法求得項(xiàng)目加權(quán)支持度，所以加權(quán)支持度可能大于1，這與支持度應(yīng)小于1的實(shí)際相矛盾，有悖人們的思維方式;(3)挖掘得到加權(quán)頻繁項(xiàng)集并不是決策者感興趣的，加權(quán)頻繁項(xiàng)集可能包含多個(gè)權(quán)值較低的項(xiàng)目，因?yàn)闄?quán)值之和較高，所以才被挖掘出來(lái)．

假設(shè)事務(wù)數(shù)據(jù)庫(kù)D，令wminsup=0．4，項(xiàng)目A，B，C，D，E 的權(quán)值分別為 0．2，0．3，0．3，0．6，0．7，如表1 所示．

表1 事務(wù)數(shù)據(jù)庫(kù)D

采用MINWAL(O)算法:

Wsup{E}=0．7 × 2/4=0．35;

Wsup{ABC}=(0．2+0．3+0．3)× 2/4=0．4;

可以看出，Wsup{E}的加權(quán)支持度小于wminsup，在項(xiàng)集{E}和{ABC}出現(xiàn)的頻繁程度相同時(shí)，挖掘到的加權(quán)頻繁項(xiàng)集包含{ABC}，而不包含{E}．

3 加權(quán)關(guān)聯(lián)規(guī)則的優(yōu)化

針對(duì)MINWAL(O)算法的不足，很多學(xué)者對(duì)加權(quán)關(guān)聯(lián)規(guī)則進(jìn)行深入研究，文獻(xiàn)［5］提出了一種基于時(shí)序和興趣度約束的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法，該算法首先利用時(shí)序滑動(dòng)函數(shù)對(duì)項(xiàng)目事務(wù)集中的數(shù)據(jù)集權(quán)值和發(fā)生概率進(jìn)行估計(jì)，依據(jù)興趣度約束函數(shù)和剪枝定理對(duì)數(shù)據(jù)集簡(jiǎn)化，然后根據(jù)支持度和k-支持期望進(jìn)行加權(quán)頻繁事務(wù)集抽取，最后依據(jù)置信度進(jìn)行加權(quán)關(guān)聯(lián)規(guī)則導(dǎo)出．實(shí)驗(yàn)結(jié)果證明，該算法能夠快速有效地挖掘出符合用戶興趣度的關(guān)聯(lián)規(guī)則．文獻(xiàn)［6］針對(duì)事務(wù)數(shù)據(jù)庫(kù)長(zhǎng)度不變，數(shù)據(jù)庫(kù)項(xiàng)目集發(fā)生變化時(shí)并且?guī)в袡?quán)重時(shí)的關(guān)聯(lián)規(guī)則挖掘問(wèn)題，提出了一種針對(duì)項(xiàng)目集增加的加權(quán)關(guān)聯(lián)規(guī)則更新算法，解決了增加項(xiàng)日集的加權(quán)關(guān)聯(lián)規(guī)則更新問(wèn)題．文獻(xiàn)［7］針對(duì)加權(quán)關(guān)聯(lián)規(guī)則挖掘問(wèn)題，提出基于關(guān)聯(lián)圖的加權(quán)頻繁項(xiàng)集生成算法及其剪枝策略．該算法掃描一次數(shù)據(jù)庫(kù)，通過(guò)關(guān)聯(lián)圖節(jié)點(diǎn)的度、是否有邊相連等作為判斷標(biāo)準(zhǔn)，減少生成頻繁項(xiàng)集的計(jì)算量，有效提高加權(quán)頻繁項(xiàng)集的生成效率．文獻(xiàn)［8］提出了基于時(shí)間聚類的加權(quán)關(guān)聯(lián)規(guī)則算法中權(quán)值設(shè)置方法，運(yùn)用布爾向量的關(guān)系運(yùn)算思想，設(shè)計(jì)了一種基于聚類和壓縮矩陣的加權(quán)關(guān)聯(lián)規(guī)則算法—CCMW算法．該算法通過(guò)聚類和對(duì)相同事務(wù)進(jìn)行計(jì)數(shù)來(lái)壓縮矩陣以減小數(shù)據(jù)庫(kù)規(guī)模，并且只需掃描一次數(shù)據(jù)庫(kù)，無(wú)需產(chǎn)生候選項(xiàng)集直接生成加權(quán)頻繁項(xiàng)集．文獻(xiàn)［9］針對(duì)現(xiàn)有加權(quán)關(guān)聯(lián)規(guī)則模型中加權(quán)支持度定義和加權(quán)頻繁項(xiàng)集挖掘算法的不足，給出了挖掘加權(quán)頻繁項(xiàng)集的新算法——MWFI算法，該挖掘加權(quán)頻繁項(xiàng)集能保證:在項(xiàng)集出現(xiàn)的頻繁程度相同的情況下，如果權(quán)重小的項(xiàng)集是加權(quán)頻繁項(xiàng)集，權(quán)重大的項(xiàng)集一定是加權(quán)頻繁項(xiàng)集．但該算法存在，重復(fù)掃描數(shù)據(jù)庫(kù)，產(chǎn)生大量的候選項(xiàng)集的不足．

4 結(jié)束語(yǔ)

針對(duì)布爾關(guān)聯(lián)規(guī)則apriori算法在挖掘頻繁項(xiàng)集時(shí)，沒(méi)有充分考慮當(dāng)數(shù)據(jù)庫(kù)中項(xiàng)目的出現(xiàn)頻率和重要程度相差很大這兩種情況，本文提出了加權(quán)關(guān)聯(lián)規(guī)則的概念，重點(diǎn)研究了水平加權(quán)關(guān)聯(lián)規(guī)則MINWAL(O)算法的基本思想，同時(shí)指出該算法的不足及優(yōu)化算法，針對(duì)加權(quán)關(guān)聯(lián)規(guī)則的挖掘，有待進(jìn)一步研究．

［1］ 王瑄．多最小支持度下的關(guān)聯(lián)規(guī)則研究［D］．長(zhǎng)春理工大學(xué)，2008．

［2］ 田啟明，王麗珍，尹群．一種基于概率的多最小支持度挖掘算法［J］．計(jì)算機(jī)仿真，2006(7):115-118．

［3］ 何朝陽(yáng)，趙劍鋒，江水．最大值控制的多最小支持度關(guān)聯(lián)規(guī)則挖掘算法［J］，2006(6):103-105．

［4］ 翟罡．Web數(shù)據(jù)挖掘中加權(quán)關(guān)聯(lián)規(guī)則算法的研究［D］．哈爾濱工程大學(xué)，2009．

［5］ 楊澤民．基于時(shí)序和興趣度約束的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法研究［J］．計(jì)算機(jī)科學(xué)，2013(3):259-262．

［6］ 鄒長(zhǎng)忠，傅清祥．一種新的加權(quán)關(guān)聯(lián)規(guī)則增量更新算法［J］．福州大學(xué)學(xué)報(bào)，2008(8):501-505．

［7］ 陳文．基于關(guān)聯(lián)圖的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法［J］．計(jì)算機(jī)工程，2010(7):59-61．

［8］ 羅芳．基于聚類和壓縮矩陣的加權(quán)關(guān)聯(lián)規(guī)則算法的研究與應(yīng)用［D］．華東師范大學(xué)，2010(10):24-37．

［9］ 王艷．一種加權(quán)關(guān)聯(lián)規(guī)則模型及挖掘算法研究［D］．河南大學(xué)，2007．