亓文娟
(武夷學(xué)院)
經(jīng)典的Apriori算法在進行關(guān)聯(lián)規(guī)則挖掘時存在數(shù)據(jù)庫中各項目具有著相似的出現(xiàn)頻率和相同的重要性兩個前提假設(shè),但是現(xiàn)實世界數(shù)據(jù)庫中的數(shù)據(jù)并非如此,當(dāng)數(shù)據(jù)庫中的各項目出現(xiàn)的頻率相差較大時,就會出現(xiàn)最小支持度閾值設(shè)置的兩難局面,為了解決這一問題,Liu[1]等學(xué)者提出了一種多支持度關(guān)聯(lián)規(guī)則挖掘MS-Apriori算法,但該算法認為各項目的重要性相同.文獻[2]提出了一種基于概率的多最小支持度關(guān)聯(lián)規(guī)則算法,有效挖掘出發(fā)生概率較低事件中的關(guān)聯(lián)規(guī)則,但存在著候選項集增多的缺點.文獻[3]提出了使用相關(guān)項目集中各項目最小支持度中的最大值來實現(xiàn)剪枝.為了區(qū)分各項目具有不同的重要性,需要根據(jù)各項目的重要性程度設(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ī)則挖掘中項目的權(quán)值體現(xiàn)的是項目對決策的重要程度,垂直加權(quán)關(guān)聯(lián)規(guī)則挖掘中項目的權(quán)值隨著時間的變化而變化,混合加權(quán)關(guān)聯(lián)規(guī)則挖掘就是同時包含水平和垂直加權(quán)的關(guān)聯(lián)規(guī)則挖掘問題.本文深入分析了水平加權(quán)關(guān)聯(lián)規(guī)則典型算法MINWAL(O)的思想,指出了算法的不足及優(yōu)化算法,旨在對加權(quán)關(guān)聯(lián)規(guī)則挖掘算法的擴展和改進奠定基礎(chǔ).
假定事務(wù)數(shù)據(jù)庫D,項目的集合I={i1,i2,i3,…,in},每一筆交易都是 I的子集,W={w1,w2,w3,…,wn}為I的權(quán)重集,其中項目ij對應(yīng)的權(quán)重是wj,表示項目的ij重要程度,且0≤ wj≤1,j={1,2,…,n}.加權(quán)關(guān)聯(lián)規(guī)則形如 X?Y,其中X?I,Y?I,并且X∩Y=?.項集X在D中的支持度和置信度分別用 Support(X),confidence(X)表示,根據(jù)傳統(tǒng)關(guān)聯(lián)規(guī)則可得到加權(quán)關(guān)聯(lián)規(guī)則的相關(guān)定義.
定義1 項集加權(quán)支持度為:
定義2 X?Y的加權(quán)支持度為:
定義3 X?Y的加權(quán)置信度為:
加權(quán)關(guān)聯(lián)規(guī)則就是挖掘同時滿足最小加權(quán)支持度閾值和最小加權(quán)置信度閾值的規(guī)則.
由于引入了權(quán)重的概念,區(qū)分了項目的不同重要程度,但也帶來了新的問題,即加權(quán)頻繁項集中不再符合普通關(guān)聯(lián)規(guī)則中頻繁項集所具有的反單調(diào)性,加權(quán)頻繁項集的子集有可能不是加權(quán)頻繁項集,因此必須采用新的解決方法.MINWAL(O)算法是由Cai C H等人在1998年提出的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法[4],該算法提出k-支持期望的概念,用于候選項集的剪枝操作,縮小了候選項集的規(guī)模.
假定事務(wù)數(shù)據(jù)庫D,其交易總數(shù)為n,對于任一k-項目集X,其支持數(shù)記為SC(X),即事務(wù)數(shù)據(jù)庫D中包含X的交易個數(shù).如果X為加權(quán)頻繁項集,則SC(X)應(yīng)滿足下式:
令I(lǐng)為所有項的集合,Y為一個q-項集(q<k),在剩余項目集合(I-Y)中,權(quán)值最大的前(k-q)個項為{wr1,wr2,…wr(k-q)},則包含項集Y的任一k-項集的最大可能權(quán)值為
第1個和式是q-項集Y中各項目的權(quán)值之和,第2個和式是剩余的前k-q個項目的最大權(quán)值之和.由公式1和公式2可以推出:如果包含Y的k-項集是頻繁的,那么其最低支持數(shù)必須滿足下式:
稱B(Y,k)是項集Y的k-支持期望.為了保證Y的k-項集有可能是頻繁的,這里支持數(shù)采用向上取整的方式.在加權(quán)關(guān)聯(lián)規(guī)則挖掘中對候選頻繁項集進行剪枝的依據(jù)是B(Y,k).
MINWAL(O)算法是基于Apriori算法的逐層搜索迭代思想,兩個算法都是通過頻繁項集來生成候選項集,但剪枝的依據(jù)不同,Apriori算法采用Apriori性質(zhì)進行剪枝,而MINWAL(O)算法采用項集的k-支持期望進行剪枝,即保守估算任何可能成為其他加權(quán)頻繁項集子集的候選項,如果候選項的支持數(shù)不小于k-支持期望值就予以保留,否則刪除.MINWAL(O)算法的偽代碼如下:
MINWAL(O)算法的步驟如下:
MINWAL(O)算法:挖掘加權(quán)關(guān)聯(lián)規(guī)則.
輸入:(1)交易數(shù)據(jù)庫D,權(quán)重集W;
(2)最小加權(quán)支持度閾值wminsup和最小置信度閾值minconf;
輸出:加權(quán)關(guān)聯(lián)規(guī)則
begin
(1)size=Scan(D);//找出交易數(shù)據(jù)庫D中頻繁項集的最大可能長度
(2)L=?;
(3)for(i=1;i≤size;i++)//最大候選項集長度不大于size
(4)Ci=Li=?;
(5)for each transaction in D do
(6)(SC,C1)=Count(D,W);//累計1-項集的支持數(shù),計算1-項集的k-支持期望,保留支持數(shù)不小于k-支持期望的1-項集為C1
(7)for(k=2;k≤size;k++){
(8)Ck=Join(Ck-1);//Ck是候選k-項集,Join(Ck-1)與Apriori算法的Gen函數(shù)類似
(9)Ck=Prune(Ck);//Prune(Ck)用于k-項集的剪枝操作
(10)(Ck,Lk)=Checking(Ck,D);//Lk是頻繁k-項集,遍歷交易數(shù)據(jù)庫D,更新Ck中所有候選項集的支持計數(shù)
(11)L=L∪Lk;}
(12)Rules.Set=Rules.Gen(L);// 與Apriori算法相同,根據(jù)L中的頻繁項集生成符合最小置信度閾值minconf的加權(quán)關(guān)聯(lián)規(guī)則
End
MINWAL(O)算法雖然解決了加權(quán)關(guān)聯(lián)規(guī)則挖掘中加權(quán)頻繁項集的子集可以不是加權(quán)頻繁項集的問題,但是由于該算法是基于Apriori算法思想,也存在著不足之處:(1)頻繁掃描數(shù)據(jù)庫,生成大量候選項集,運行效率低,極大的影響了算法的性能;(2)利用求和權(quán)值法求得項目加權(quán)支持度,所以加權(quán)支持度可能大于1,這與支持度應(yīng)小于1的實際相矛盾,有悖人們的思維方式;(3)挖掘得到加權(quán)頻繁項集并不是決策者感興趣的,加權(quán)頻繁項集可能包含多個權(quán)值較低的項目,因為權(quán)值之和較高,所以才被挖掘出來.
假設(shè)事務(wù)數(shù)據(jù)庫D,令wminsup=0.4,項目A,B,C,D,E 的權(quán)值分別為 0.2,0.3,0.3,0.6,0.7,如表1 所示.
表1 事務(wù)數(shù)據(jù)庫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,在項集{E}和{ABC}出現(xiàn)的頻繁程度相同時,挖掘到的加權(quán)頻繁項集包含{ABC},而不包含{E}.
針對MINWAL(O)算法的不足,很多學(xué)者對加權(quán)關(guān)聯(lián)規(guī)則進行深入研究,文獻[5]提出了一種基于時序和興趣度約束的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法,該算法首先利用時序滑動函數(shù)對項目事務(wù)集中的數(shù)據(jù)集權(quán)值和發(fā)生概率進行估計,依據(jù)興趣度約束函數(shù)和剪枝定理對數(shù)據(jù)集簡化,然后根據(jù)支持度和k-支持期望進行加權(quán)頻繁事務(wù)集抽取,最后依據(jù)置信度進行加權(quán)關(guān)聯(lián)規(guī)則導(dǎo)出.實驗結(jié)果證明,該算法能夠快速有效地挖掘出符合用戶興趣度的關(guān)聯(lián)規(guī)則.文獻[6]針對事務(wù)數(shù)據(jù)庫長度不變,數(shù)據(jù)庫項目集發(fā)生變化時并且?guī)в袡?quán)重時的關(guān)聯(lián)規(guī)則挖掘問題,提出了一種針對項目集增加的加權(quán)關(guān)聯(lián)規(guī)則更新算法,解決了增加項日集的加權(quán)關(guān)聯(lián)規(guī)則更新問題.文獻[7]針對加權(quán)關(guān)聯(lián)規(guī)則挖掘問題,提出基于關(guān)聯(lián)圖的加權(quán)頻繁項集生成算法及其剪枝策略.該算法掃描一次數(shù)據(jù)庫,通過關(guān)聯(lián)圖節(jié)點的度、是否有邊相連等作為判斷標準,減少生成頻繁項集的計算量,有效提高加權(quán)頻繁項集的生成效率.文獻[8]提出了基于時間聚類的加權(quán)關(guān)聯(lián)規(guī)則算法中權(quán)值設(shè)置方法,運用布爾向量的關(guān)系運算思想,設(shè)計了一種基于聚類和壓縮矩陣的加權(quán)關(guān)聯(lián)規(guī)則算法—CCMW算法.該算法通過聚類和對相同事務(wù)進行計數(shù)來壓縮矩陣以減小數(shù)據(jù)庫規(guī)模,并且只需掃描一次數(shù)據(jù)庫,無需產(chǎn)生候選項集直接生成加權(quán)頻繁項集.文獻[9]針對現(xiàn)有加權(quán)關(guān)聯(lián)規(guī)則模型中加權(quán)支持度定義和加權(quán)頻繁項集挖掘算法的不足,給出了挖掘加權(quán)頻繁項集的新算法——MWFI算法,該挖掘加權(quán)頻繁項集能保證:在項集出現(xiàn)的頻繁程度相同的情況下,如果權(quán)重小的項集是加權(quán)頻繁項集,權(quán)重大的項集一定是加權(quán)頻繁項集.但該算法存在,重復(fù)掃描數(shù)據(jù)庫,產(chǎn)生大量的候選項集的不足.
針對布爾關(guān)聯(lián)規(guī)則apriori算法在挖掘頻繁項集時,沒有充分考慮當(dāng)數(shù)據(jù)庫中項目的出現(xiàn)頻率和重要程度相差很大這兩種情況,本文提出了加權(quán)關(guān)聯(lián)規(guī)則的概念,重點研究了水平加權(quán)關(guān)聯(lián)規(guī)則MINWAL(O)算法的基本思想,同時指出該算法的不足及優(yōu)化算法,針對加權(quán)關(guān)聯(lián)規(guī)則的挖掘,有待進一步研究.
[1] 王瑄.多最小支持度下的關(guān)聯(lián)規(guī)則研究[D].長春理工大學(xué),2008.
[2] 田啟明,王麗珍,尹群.一種基于概率的多最小支持度挖掘算法[J].計算機仿真,2006(7):115-118.
[3] 何朝陽,趙劍鋒,江水.最大值控制的多最小支持度關(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] 楊澤民.基于時序和興趣度約束的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法研究[J].計算機科學(xué),2013(3):259-262.
[6] 鄒長忠,傅清祥.一種新的加權(quán)關(guān)聯(lián)規(guī)則增量更新算法[J].福州大學(xué)學(xué)報,2008(8):501-505.
[7] 陳文.基于關(guān)聯(lián)圖的加權(quán)關(guān)聯(lián)規(guī)則挖掘算法[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.