<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    posts - 30,  comments - 3,  trackbacks - 0
    Apriori算法乃是關聯規則挖掘的經典算法,盡管是94年提出的算法,然而至今也有著旺盛的生命力。在互聯網科學領域,也有著廣泛的應用,因此還是值得大家都對此學習一下。

    一、術語
    1.支持度:support,所有實例中覆蓋某一項集的實例數。
    2.置信度:confidence。對于X→Y這個規則,如果數據庫的包含X的實例數的c%也包含Y,則X→Y的置信度為c%。
    3.頻繁項集:也稱large itemsets,指支持度大于minsup(最小支持度)的項集

    二、思想
    1.Apriori算法思想與其它關聯規則挖掘算法在某些方面是相同的。即首先找出所有的頻繁項集,然后從頻繁項集中抽取出規則,再從規則中將置信度小于最小置信度的規則剃除掉。

    2.若項集i為頻繁項集,則其所有子集必為頻繁項集。因此,Apriori算法思想在于從頻繁的k-1項集中合并出k項集,然后剃除掉子集有不是頻繁項集的k項集。

    3.先從數據庫中讀出每條實例,對于設定閾值,選出頻繁1項集,然后從頻繁1項集中合并,并剃除掉包含非頻繁1項集子集的2項集……

    4.符號說明:
    Lk:Set of large(frequent) k-itemsets
    Ck:Set of candidate k-itemsets
    apriori-gen()函數通過合并k-1的頻繁項集,生成Ck

    三、算法描述
    1) Apriori基本算法
     1L1={large 1-itemsets};
     2for(k=2;Lk-1!=Φ;k++)
     3{
     4  Ck=apriori-gen(Lk-1);
     5  for(all transaction t∈D)
     6  {
     7     Ct=subset(Ck,t);
     8     for(all candidates c∈Ct)
     9        c.count++;
    10  }

    11  Lk={c∈Ck|c.count>=minsup}
    12}

    13Answer=∪k Lk;

    2)apriori-gen()函數
        這個函數將Lk-1(即所有k-1頻繁項集的集合)作為參數,返回一個Lk的超集(即Ck
        算法如下:
    1insert into Ck
    2select p.item1, p.item2 ,p.itemk-1,q.itemk-1
    3from Lk-1 p, Lk-1 q
    4where p.item1=q.item1, p.item2=q.item2 , p.itemk-1<q.itemk-1
       
        然后通過剪枝,剃除掉Ck中某些子集不為頻繁k-1項集的項集,算法如下:
    1for(all items c∈Ck)
    2{
    3     for(all k-1 itemsets s of c)
    4     {
    5        if(s
    ∉Lk-1)
    6           delete c from Ck;
    7     }

    8}
       
    3)從頻繁項集中生成規則
    1for(all l∈Answer)
    2{
    3  A=set of nonempty-subset(l);
    4  for(all aA)
    5  {
    6    output a→(l-a);
    7  }

    8}
      

    四、舉例(這里將minsup=1,mincof=0.5)
    L3={{1 2 3}{1 2 4}{1 3 4}{1 3 5}{2 3 4}}
    在合并步驟時,選取L3中,前兩個項都相同,第三個項不同的項集合并,如{1 2 3}與{1 2 4}合并、{1 3 4}與{1 3 5}合并成{1 2 3 4}和{1 3 4 5}。因此,C4={{1 2 3 4}{1 3 4 5}},但是由于{1 3 4 5}中某子集{3 4 5}并未在L3中出現,因此,將{1 3 4 5}剃除掉,所以L4={{1 2 3 4}}。
    然后以L4為例,選取出關聯的規則:
    L4中{1 2 3 4}項集中抽取出(這里只列出左邊為3項的情況):
    {1 2 3}→4
    {1 2 4}→3
    {1 3 4}→2
    {2 3 4}→1
    顯然,因為只有一個4項集,因此,這四條規則的置信度都為100%。因此,全數為關聯規則。

    五、Apriori變體
        有些Apriori變體為追求時間效率,不是從L1→C2→L2→C3→....的步驟產生,而是從L1→C2→C3'..產生。

    參考文獻:
    Agrawal, Rakesh, Srikant, Ramakrishnan. Fast algorithms for mining association rules in large databases. Very Large Data Bases, International Conference Proceedings, p 487, 1994   
    posted on 2012-02-27 13:08 Seraphi 閱讀(780) 評論(0)  編輯  收藏

    只有注冊用戶登錄后才能發表評論。


    網站導航:
     
    主站蜘蛛池模板: 久久夜色精品国产亚洲av| 免费无码又爽又刺激聊天APP| 拔擦拔擦8x华人免费久久| 亚洲噜噜噜噜噜影院在线播放 | 亚洲免费闲人蜜桃| 国产亚洲婷婷香蕉久久精品| 一级午夜a毛片免费视频| 久久伊人亚洲AV无码网站| 成人自慰女黄网站免费大全| 亚洲国产成人一区二区三区| 可以免费观看的毛片| 久久久久久亚洲精品| 中文字幕成人免费视频| 亚洲av产在线精品亚洲第一站| 两个人的视频高清在线观看免费| 波多野结衣亚洲一级| 永久黄网站色视频免费直播| 自拍偷自拍亚洲精品偷一| 亚洲成A人片在线观看中文| 一级日本高清视频免费观看| 亚洲Av熟妇高潮30p| 国产成人精品免费午夜app| 亚洲欧美乱色情图片| 亚洲欧洲久久久精品| 免费无码又爽又刺激网站直播| 久久精品国产亚洲AV电影| 99久久免费精品国产72精品九九| 色欲aⅴ亚洲情无码AV| 亚洲中文字幕无码久久精品1| 99热这里只有精品免费播放| 国产亚洲精品成人AA片| 亚洲国产人成中文幕一级二级| 久草福利资源网站免费| 亚洲依依成人亚洲社区| 久久久久亚洲AV无码专区网站 | 亚洲人成色在线观看| 免费少妇a级毛片| 久久青草国产免费观看| 亚洲乱码在线观看| 亚洲综合伊人久久大杳蕉| 一本岛高清v不卡免费一三区|