国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2015-12-02 03:00:58亓文娟
關(guān)鍵詞:剪枝項集置信度

亓文娟

(武夷學(xué)院)

0 引言

經(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ǔ).

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

假定事務(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ī)則.

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

由于引入了權(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ī)模.

2.1 k- 支持期望

假定事務(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).

2.2MINWAL(O)算法

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

2.3 算法不足

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}.

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

針對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)生大量的候選項集的不足.

4 結(jié)束語

針對布爾關(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.

猜你喜歡
剪枝項集置信度
人到晚年宜“剪枝”
硼鋁復(fù)合材料硼含量置信度臨界安全分析研究
基于YOLOv4-Tiny模型剪枝算法
正負關(guān)聯(lián)規(guī)則兩級置信度閾值設(shè)置方法
剪枝
天津詩人(2017年2期)2017-03-16 03:09:39
置信度條件下軸承壽命的可靠度分析
軸承(2015年2期)2015-07-25 03:51:04
關(guān)聯(lián)規(guī)則中經(jīng)典的Apriori算法研究
卷宗(2014年5期)2014-07-15 07:47:08
一種面向不平衡數(shù)據(jù)分類的組合剪枝方法
計算機工程(2014年6期)2014-02-28 01:26:33
一種頻繁核心項集的快速挖掘算法
計算機工程(2014年6期)2014-02-28 01:26:12
多假設(shè)用于同一結(jié)論時綜合置信度計算的新方法?
苍山县| 玉溪市| 土默特左旗| 平果县| 张家港市| 松江区| 平乡县| 枣庄市| 荔波县| 克拉玛依市| 英德市| 神木县| 延安市| 临西县| 和林格尔县| 定远县| 龙口市| 常熟市| 海安县| 庆安县| 紫云| 平安县| 忻城县| 武义县| 甘孜县| 蛟河市| 芦山县| 海城市| 柘城县| 大兴区| 辰溪县| 辽阳市| 渝中区| 永济市| 孟津县| 英德市| 弥渡县| 蓬溪县| 益阳市| 富阳市| 博湖县|