亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        關(guān)聯(lián)規(guī)則中經(jīng)典的Apriori算法研究

        2014-07-15 07:47:08朱建斌
        卷宗 2014年5期
        關(guān)鍵詞:剪枝項(xiàng)集事務(wù)

        摘 要:本文主要介紹了關(guān)聯(lián)規(guī)則中的Apriori算法。通過(guò)對(duì)該算法的研究,挖掘數(shù)據(jù)之間的聯(lián)動(dòng)關(guān)系。

        關(guān)鍵詞:關(guān)聯(lián);Apriori

        Apriori算法使用了逐層查尋的方式,一遍一遍的掃描事務(wù)數(shù)據(jù)庫(kù),得到各層頻繁K項(xiàng)集,并利用當(dāng)層得到的K項(xiàng)集,生成候選的(K+1)項(xiàng)集,直到不能再生成頻繁K項(xiàng)集為止。關(guān)聯(lián)挖掘問(wèn)題被分成如下2個(gè)問(wèn)題:⑴尋找所有的這樣的項(xiàng)的集合,它們的支持度不小于用戶(hù)指定的最小支持度閾值,這樣的集合稱(chēng)為頻繁項(xiàng)集。⑵利用頻繁項(xiàng)集產(chǎn)生規(guī)則。一般的想法是,如果B1,B2,B3和B1,B2是頻繁項(xiàng)集,那么通過(guò)計(jì)算置信度,conf=P(B1B2B3)/P(B1B2)來(lái)確定{B1,B2,B3}這個(gè)規(guī)則是否成立,當(dāng)它不小于最小置信度閾值時(shí),規(guī)則成立。為了避免需要算出所有項(xiàng)集的支持度,Apriori引入了候選項(xiàng)集概念,并將候選項(xiàng)集記為Ck。這里需要介紹關(guān)聯(lián)規(guī)則兩條重要的性質(zhì),如下:(1)頻繁項(xiàng)集的所有非空子集也必須是頻繁的。 (2)非頻繁項(xiàng)集的所有超集一定是非頻繁的。

        例如,如果項(xiàng)集{ B1,B2}是非頻繁的,即數(shù)據(jù)庫(kù)中同時(shí)包含的B1,B2的事務(wù)的個(gè)數(shù)小于min_sup,那么數(shù)據(jù)庫(kù)中同時(shí)包含B1,B2,B3的事務(wù)的個(gè)數(shù)肯定是小于min_sup的,即{B1,B2,B3}一定是非頻繁的。而Apriori算法只運(yùn)用了性質(zhì)(1),通過(guò)已經(jīng)找到的頻繁項(xiàng)集去構(gòu)造更大的頻繁項(xiàng)集,就是候選項(xiàng)集Ck,它是有可能成為頻繁k項(xiàng)集的項(xiàng)集的集合。使用Lk-1生成Lk的詳細(xì)過(guò)程如下:(1)連接步驟:通過(guò)Lk-1∞Lk-1來(lái)生成Ck:如果Lk-1中兩個(gè)頻繁項(xiàng)集L1和L2的前(k-2)個(gè)項(xiàng)相同,但L1的第(k-1)項(xiàng)排在L2的第(k-1)項(xiàng)的前面,那么將它們合在一起可以形成一個(gè)k項(xiàng)集。(2)修剪步驟:A.如果Ck中一個(gè)候選k項(xiàng)集的某個(gè)(k-1)子項(xiàng)集不在Lk-1中,則將該候選項(xiàng)集從Ck中刪除。B.對(duì)仍在Ck中的沒(méi)被刪除的候選k項(xiàng)集,掃描數(shù)據(jù)庫(kù)來(lái)計(jì)算它們的支持度計(jì)數(shù),生成Lk,Lk中包含了Ck中支持度不小于min_sup的所有項(xiàng)集,它們都是k項(xiàng)頻繁項(xiàng)集。

        1 算法的偽碼實(shí)現(xiàn)

        算法的偽碼表示如下:

        輸入: D:事務(wù)數(shù)據(jù)庫(kù);

        min_sup:最小支持度計(jì)數(shù)閾值。

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

        方法:

        (1) L1={frequent 1-itemsets};

        for(k=2;Lk-1≠,k++)

        { Ck=apriori-gen(Lk-1); for each transaction t∈D

        {Ct=subset(Ck,t);

        for each candidate c∈Ct

        c.count++;}

        Lk={c∈Ck|c.count≥min_sup}}

        return L=kLk

        (2) procedure apriori-gen(Lk-1:frequent (k-1)-itemsets)

        for each itemset L1∈Lk-1

        for each itemset L2∈Lk-1

        if (L1[1]^L2[1])= (L1[2]^L2[2])=^…^ (L1[k-1]

        {

        c=L1∞L2;

        if has_infrequent_subset(c,Lk-1)then

        delete c; else

        add c to Ck;

        } return Ck;

        (3) procedure has_infrequent_subset(c,Lk-1)

        for each (k-1)-subset s of c

        if sLk-1

        return TRUE;

        return FALSE;

        2 算法的實(shí)例

        假設(shè)數(shù)據(jù)庫(kù)中有10個(gè)事務(wù),數(shù)據(jù)庫(kù)如下:

        表2.2 原始數(shù)據(jù)庫(kù)

        事務(wù)TID 項(xiàng)集

        TID1 B1,B2,B3

        TID2 B2,B3,B5

        TID3 B3,B4

        TID4 B1,B2,B3

        TID5 B1,B3

        TID6 B2,B5

        TID7 B1,B2

        TID8 B2,B3

        TID9 B2,B4

        TID10 B1,B3,B5

        (1)第一次執(zhí)行,找出項(xiàng)集中所有的項(xiàng)構(gòu)成候選1項(xiàng)集C1,并對(duì)每個(gè)項(xiàng)統(tǒng)計(jì)出現(xiàn)的次數(shù)。如果規(guī)定的最小支持度計(jì)數(shù)min_sup=2(2為絕對(duì)支持度),則找出候選1項(xiàng)集中大于min_sup的項(xiàng),然后構(gòu)成頻繁一項(xiàng)集L1。

        (2)第二次執(zhí)行是為了求的2項(xiàng)集L2,這里需要對(duì)L1進(jìn)行自身連接產(chǎn)生C2。設(shè)n=|L1|表示的是L1中項(xiàng)的個(gè)數(shù),那么C2產(chǎn)生的2項(xiàng)集的個(gè)數(shù)則是n(n-1)/2,如果項(xiàng)集太多的話(huà),那么如此多的項(xiàng)集對(duì)時(shí)間效率和空間容量是個(gè)巨大的考驗(yàn)。而本例的項(xiàng)集較小,連接步之后,

        再進(jìn)行剪枝步,由于1項(xiàng)集都是頻繁的,所以不用剪枝,都進(jìn)入C2中。

        (3)將各個(gè)項(xiàng)集的支持度計(jì)數(shù)與最小支持度計(jì)數(shù)閾值進(jìn)行比較,刪除小于min_sup的項(xiàng)集,結(jié)果就是L2,即頻繁2項(xiàng)集。然后對(duì)L2進(jìn)行自連接,連接完成后進(jìn)行剪枝,這里需

        要根據(jù)Apriori算法的性質(zhì)來(lái)刪除部分項(xiàng)集,然后產(chǎn)生候選項(xiàng)集C3。根據(jù)性質(zhì),頻繁項(xiàng)集的各個(gè)子集都是頻繁的,刪除C3中不頻繁的項(xiàng)集{B1,B2,B5},{B1,B3, B5}。這樣在后面的掃描過(guò)程中就不需要計(jì)算它們的支持度了。

        (4)得到候選項(xiàng)集C3后,再在原始數(shù)據(jù)庫(kù)中掃描一次,計(jì)算各個(gè)項(xiàng)集的支持度,然后

        把小于min_sup的項(xiàng)集刪除,得到頻繁3項(xiàng)集L3。

        (5)因?yàn)長(zhǎng)3中只有一個(gè)項(xiàng)集,無(wú)法再產(chǎn)生4項(xiàng)集了,因此算法結(jié)束,把前面的頻繁項(xiàng)集綜合起來(lái),構(gòu)成了全部的頻繁項(xiàng)集。這樣,運(yùn)用Apriori算法就求得了所有的頻繁項(xiàng)集。

        作者簡(jiǎn)介

        朱建斌(1980-),江西南昌人,本科.研究方向:電工電子。

        猜你喜歡
        剪枝項(xiàng)集事務(wù)
        “事物”與“事務(wù)”
        基于分布式事務(wù)的門(mén)架數(shù)據(jù)處理系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)
        人到晚年宜“剪枝”
        基于YOLOv4-Tiny模型剪枝算法
        河湖事務(wù)
        不確定數(shù)據(jù)的約束頻繁閉項(xiàng)集挖掘算法
        剪枝
        一種面向不平衡數(shù)據(jù)分類(lèi)的組合剪枝方法
        一種頻繁核心項(xiàng)集的快速挖掘算法
        SQLServer自治事務(wù)實(shí)現(xiàn)方案探析
        成年性生交大片免费看| 亚洲综合免费在线视频| 中文字幕人妻精品一区| 久久久久久av无码免费网站下载| 亚洲av之男人的天堂网站| 国产最新AV在线播放不卡| 亚洲一区二区在线视频,| 免费国产在线视频自拍白浆| 亚洲欧美一区二区三区在线| 精品国产一区二区三区AV小说| 午夜在线观看一区二区三区四区| 手机看片久久第一人妻| 爽爽精品dvd蜜桃成熟时电影院 | 夜色阁亚洲一区二区三区| 亚洲一区丝袜美腿在线观看| 国产精品一区二区三区播放| 欧美又大又色又爽aaaa片| 热99精品| 久久本道久久综合一人| 综合图区亚洲另类偷窥| 人妻少妇av中文字幕乱码| 中文字幕亚洲人妻系列| 三级网站亚洲三级一区| 伊人久久精品无码二区麻豆 | 日本一区二区偷拍视频| 一区二区三区内射美女毛片| 国产自偷亚洲精品页65页| 欧美亚洲国产丝袜在线| 午夜福利视频一区二区二区| 亚洲国产av玩弄放荡人妇系列| 日韩在线第二页| 国产一区二区三区在线观看免费版| 国产精品久久久久久久久久红粉| 综合无码一区二区三区| 亚洲国产综合专区在线电影| 手机在线观看av资源| 中文字幕日韩一区二区不卡| 亚洲AV一二三四区四色婷婷| 精品亚洲av一区二区| 人人妻人人澡人人爽欧美一区双 | 国产精品一久久香蕉国产线看观看|