• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘Apriori算法的兩種優(yōu)化分析

      2019-11-11 07:36:12
      韶關(guān)學(xué)院學(xué)報 2019年9期
      關(guān)鍵詞:剪枝項集事務(wù)

      張 超

      (亳州學(xué)院 電子與信息工程系,安徽 亳州236800)

      Apriori算法是關(guān)聯(lián)規(guī)則挖掘技術(shù)的最基本算法[1].目前關(guān)聯(lián)規(guī)則的并行數(shù)據(jù)挖掘算法大都以Apriori算法為基礎(chǔ),它具有無可替代的獨特地位,其效率的優(yōu)化研究已成為廣大學(xué)者關(guān)注的熱點.Apriori算法本質(zhì)主要包含兩個方面問題,第一個是找出事務(wù)數(shù)據(jù)庫中所有的頻繁數(shù)據(jù)項集.第二個是如何生成強關(guān)聯(lián)規(guī)則.兩個方面相比較,第一方面的問題是算法的核心[2].基于此,對算法進行優(yōu)化,就應(yīng)把重點放在找出頻繁數(shù)據(jù)項集方面.

      1 Apriori算法概述

      1.1 原理

      Apriori算法的核心思想是基于頻繁項集理論的遞歸方法,采用逐層搜索的迭代方法挖掘出在目標(biāo)事務(wù)數(shù)據(jù)庫中所有頻繁項集,直至找到最高階頻繁項集即止,最后通過對獲得的頻繁項集進行計算得到強關(guān)聯(lián)規(guī)則[3-5].其中,現(xiàn)設(shè)候選k-項集集合表示為Ck,頻繁k-項集集合表示為Lk.經(jīng)過一次掃描后,即可快捷得出L1.執(zhí)行第k(k>1)次掃描時,由Lk-1生成Ck.然后根據(jù)Ck繼續(xù)進行掃描,對照每個元素的支持度,刪減不符合者,最后即可求得Lk.依據(jù)此思路可依次求得Lk+1,Lk+2,Lk+3…….若某次計算Ck為空時,算法自然結(jié)束.

      1.2 生成頻繁項集的過程

      Apriori算法的基本思想是基于頻繁項集生成過程,使用遞推方式推演出頻繁項集,使用頻繁項集Lk-1產(chǎn)生頻繁項集Lk,其過程分為連接和剪枝兩步[6].Apriori算法生成頻繁相集的第一步驟為連接步,即計算Lk由 Lk-1自身作連接得到 Ck.假若 Lk-1中含有項集 l1及 l2,li為(k-1)項集,規(guī)定 li[j]為 li的項,j為項的序號.對于 li,使得 li[1]<li[2]<…<.對于 l1和 l2,假設(shè) l1和 l2是可連接的,那么它們從第 1 個到第(k-2)個的項都應(yīng)當(dāng)分別對應(yīng)相等.即(l1[1]=l2[1])∩(l1[2]=l2[2])∩…∩(l1[k-2]=l2[k-2])∩(=l1[k-1]<l2[k-1]).其中 l1[k-1]<l2[k-1]限定不產(chǎn)生重復(fù)現(xiàn)象,最后的結(jié)果項集可記作:(l1[1],l1[2],…,l1[k-1],l1[k-2]).

      第二步驟為剪枝步,按照在給定的事務(wù)數(shù)據(jù)庫D中,任意大項集的子集都是大項集,任意弱項集的超集都是弱項集[7]的性質(zhì),可以刪除Ck中對應(yīng)的支持度不滿足的某個子集.

      1.3 主要步驟

      設(shè)min-sup表示最小支持度,則有以下步驟:(1)掃描數(shù)據(jù),并生成C1;(2)根據(jù)min-sup的要求,由C1推導(dǎo)出 L1;(3)k>1 時,按照(4)、(5)、(6)的次序重復(fù)執(zhí)行;(4)對 Lk-1執(zhí)行連接和剪枝操作,并得出 Ck;若Ck=Φ,執(zhí)行(7),不然,執(zhí)行(5);(5)按照 min-sup 的要求,由候選 Ck推導(dǎo)出 Lk;(6)如 L≠Φ,k=k+1,執(zhí)行(4);否則執(zhí)行(7);(7)由min-sup的具體要求,基于頻繁項集進一步推導(dǎo)出強關(guān)聯(lián)規(guī)則.

      2 Apriori算法的應(yīng)用求解過程

      一個大型購物中心的數(shù)據(jù)庫事務(wù)包括T1、T2……T9,|D|=9.基于Apriori算法求D中頻繁項集,Ti表示事務(wù)名,Pi表示商品名,Ci表示候選 i—項集集合,Li表示頻繁項集, 規(guī)定 min-sup=2,T1={P1P2P5}、T2={P2P4}、T3={P2P3}、T4={P1P2P4}、T5={P1P3}、T6={P2P3}、T7={P1P3}、T8={P1P2P3P5}、T9={P1P2P3}.

      具體求解過程如下:第一次C1→L1,按照min-sup=2的要求,對原數(shù)據(jù)庫D進行掃描C1={{P1}{P2}{P3}{P4}{P5}}各項集的支持度分別為6、7、6、2、2.繼而對C1掃描,不需要刪除任何項目,求得L1=C1且支持度不變。

      第二次求解C2→L2,在第一次求解出L1結(jié)果的基礎(chǔ)上,進一步求得C2=L1∞L1。C2={{P1P2}{P1P3}{P1P4}{P1P5}{P2,P3}{P2,P4}{P2,P5}{P3,P4}{P3,P5}{P4,P5}},在剪枝步中 C2無須刪除.對其掃描后可求得 C2的各項支持度分別為 4、4、1、2、4、2、2、0、1、0. 結(jié)合支持度 min-sup=2 的要求, 刪除不滿足后三項要求者即可得到 L2。L2={{P1P2}{P1P3}{P1P4}{P1P5}{P2,P3}{P2,P4}{P2,P5}},其中各項的支持度分別為 4、4、1、2、4、2、2.

      第三次求解C3→L3,在第二次的結(jié)果的基礎(chǔ)上,對L2進行自身連接得到C3,再由其對應(yīng)的支持度數(shù)即可求得L3.步驟如下:

      (1) 執(zhí)行連接操作:C3=L2∞L2={{P1,P2},{P1,P3},{P1,P5},{P2,P3},{P2,P4},{P2,P5}} ∞ {{P1,P2},{P1,P3},{P1,P5},{P2,P3},{P2,P4},{P2,P5}}={{P1,P2,P3},{P1,P2,P5},{P1,P3,P5},{P2,P3,P4},{P2,P3,P5},{P2,P4,P5}}.

      (2)執(zhí)行剪枝操作:根據(jù)有關(guān)性質(zhì),上步結(jié)果中的后4個均要刪除.以{P1,P3,P5}為例,其對應(yīng)的2項子集分別包括{P1,P3}、{P1,P5}、{P3,P5}.L2中存在{P1,P3}、{P1,P5}但不包括{P3,P5},因而不是頻繁的.剪枝后得到 C3={{P1,P2,P3},{P1,P2,P5}}.

      (3)結(jié)合統(tǒng)計支持度,C3的各元素均符合.即 L3={{P1,P2,P3},{P1,P2,P5}}.

      第四次掃描:求解 C4=L3∞L3,L3∞L3={{P1,P2,P3,P5}},但其子集{P2,P3,P5}不屬于 L3范疇,因此它不是頻繁的,理應(yīng)刪除.至此求解全過程結(jié)束.

      3 Apriori算法效率的優(yōu)化

      綜上分析,進行推導(dǎo)Ck的連接操作通常要做大量繁雜的比較.但即便如此,卻并不保證得到的一定為候選項集.這樣一來,連接操作的有效性就比較差,往往在許多時候都是無效的.若能夠去除無效的連接比較,簡化剪枝步驟,而使執(zhí)行連接之后得到的都歸屬于候選項集,那么算法效率將得到真正的優(yōu)化提升.基于這種思路,筆者提出一種優(yōu)化后的Apriori-A算法.

      3.1 Apriori-A算法思想

      首先,執(zhí)行對 Lk-1掃描,并記錄項集:{l1[1]},{l1[1],l1[2]},…,{l1[1],l1[2],…,l1[k-2],l1[k-1]},{l2[1]},{l2[1],l2[2]},…,{l2[1],l2[2],…,l2[k-2],l2[k-1]},{l3[1]},….基于描述方便,令 li是一個 k 項集,li={li[1],li[2],…,li[k-1],li[k]},由算法性質(zhì)可知,若 li歸屬于 Ck,那么 Lk-1應(yīng)包含其以下的 k-1 個 k-1 項集.綜上分析,進而得到規(guī)律:在掃描中,設(shè)項集{li[1]},{li[1],li[2]}的出現(xiàn)機會分別為 Q1和 Q2,那么必有 Q1≥k-1,Q2≥k-2.以此類推,項集{li[1],li[2],…,li[k-1]]}出現(xiàn)機會 Qk-1≥1.假定 Q1、Q2分別是{li[1]},{li[1],li[2]}的掃描次數(shù),若 k-1>Q1,則執(zhí)行刪除操作,即將 Lk-1中凡是以 li[1]開始的 k-1項集一律刪除.假若 k-1≤Q1,則將 Q2與 k-2 進行比較.依此類推分析,假若 k-2>Q2,把 Lk-1中凡是以項集{li[1],li[2]}起頭的全部刪除,如果k-2≤Q2,就接著與后面的項集掃描次數(shù)繼續(xù)比較.

      這種優(yōu)化的策略,實際上是以數(shù)字比較和刪除操作為手段,進而實現(xiàn)了刪除Lk-1中大量的無效項集.此優(yōu)化算法的優(yōu)點在于事先大大減少了冗余的連接,最后以連接操作生成k項集,只要通過一次比較操作即得出是否歸屬于Ck.該優(yōu)化思想基于先刪除后連接,以減少冗余的連接為前提條件,進而實現(xiàn)減少剪枝步中的判斷量,最終實現(xiàn)提升數(shù)據(jù)挖掘效率的目的.

      3.2 Apriori-A算法應(yīng)用分析

      例 1: L3={{O,P,Q},{O,P,T},{P,Q,R},{P,Q,S},{P,R,S},{Q,R,S},{Q,S,T},{R,S,T}}.

      基于Apriori-A算法,其刪減操作過程見表1.執(zhí)行得到結(jié)果={{P,Q,R},{P,Q,S}},然后執(zhí)行它的自連接操作,最終得到{P,Q,R,S}的四項集.由于子集{Q,R,S}∈L3,所以 C4={P,Q,R,S},通過驗證,得出結(jié)論是完全正確.

      表1 刪減L3中項集的過程

      本例中,如執(zhí)行經(jīng)典 Apriori算法,則首先執(zhí)行連接操作,求得{O,P,Q,T}、{P,Q,R,S}兩個項集.然后執(zhí)行剪枝步驟,若在最壞的極端情況下,則要對{O,P,Q}、{O,P,T}、{O,Q,T}、{P,Q,T}、{P,Q,R}、{P,Q,S}、{P,R,S}、{Q,R,S}等8個項集都要判斷其是否在L3范圍之內(nèi).綜上分析,在本優(yōu)化算法中,只需執(zhí)行連接操作求得相應(yīng)的四項集,在后面的剪枝步驟中,再判斷其子項集{Q,R,S}同L3有無歸屬關(guān)系成立即可.相比而言,優(yōu)化后的Apriori-A算法效率明顯地提升.

      3.3 Apriori-B算法思想

      通過深入分析和研究后,還可得知另一結(jié)論:判別一個項集是否歸屬于Lk,對Ck中的所有對象還需進一步明確其支持度計數(shù).一般來說,用于關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)庫的數(shù)據(jù)量都是非常龐大的.從先前分析來看,繁瑣冗余的掃描則在很大程度上使得算法的效率大幅降低.試想,假如能夠應(yīng)用某種策略使得掃描次數(shù)大幅簡略,則算法的優(yōu)化就自然輕松實現(xiàn).這樣一來,問題的根源在于運用何種恰當(dāng)?shù)牟呗阅軌蚴沟脭?shù)據(jù)庫的掃描大幅精簡.

      按照上述思路,現(xiàn)提出另一種優(yōu)化策略.具體如下:引入一個C’K,在此集合中的任一對象標(biāo)記成<TID,{XK}>,XK表示為潛在的頻繁K—項集.C’K作如下特性的定義,數(shù)據(jù)庫表示為D,事務(wù)表示為T,若k=l,C’K和D是一致的,其本質(zhì)上可看作是用{I}代替了項目i.若K>1,C’K中包含的對象同T保持完全相同,即可表示為:<t.TID,{C∈C’K∣C?t}>.歸結(jié)到實際,就是先得到頻繁 1-項集,并同步生成了 C’1.

      從第二步起始,諸如此類,即可往復(fù)循環(huán),直至不再有頻繁項目集的生成.現(xiàn)假定第k步出現(xiàn)了循環(huán),基于描述方便,分為兩步說明.其一,先由第K-1步中得到LK-1,對其連接生成候選頻繁K-項目集CK,并同步生成集合C’K,繼續(xù)在C’K中搜索,即可統(tǒng)計出對應(yīng)CK的支持度.究其根源是基于這一理論:如果一個事務(wù)不包含任何候選K-項集,則C’K中將沒有這個事務(wù)的目錄,所以C’K的目錄數(shù)據(jù)必然小于數(shù)據(jù)庫中事務(wù)的數(shù)據(jù),特別是當(dāng)k值很大時[8-10].并且這種情況,極有可能因k值的增長,而呈現(xiàn)愈來明顯的趨勢.進而可以推知,當(dāng)K值較大時,由于事務(wù)T基本上沒什么候選項,所以任一目錄同對應(yīng)事務(wù)T相比,均要小于.同理,若當(dāng)K值較小時,對于任一個T的候選K-項目集,C’K的一個目錄就可以完全涵概,所以任一目錄同對應(yīng)事務(wù)T相比,均較大.

      3.4 實例算法應(yīng)用分析

      例 2:有一數(shù)據(jù)庫 D,包含 4 個事務(wù)表示為 T10、T20、T30、T40,support表示其支持度,T10={P1,P3,P4},T20={P2,P3,P5},T30={P1,P2,P3,P5},T40={P2, P5},最小支持度 min-sup=2.

      按照經(jīng)典的Aprior算法對數(shù)據(jù)庫D進行掃描后得到C1,其中TSD分別包括{P1}、{P2}、{P3}、{P4}、{P5}五項,求解得到各自的support分別對應(yīng)為2、3、3、1、3.由min-sup=2,在C1中繼續(xù)掃描則需要刪除{P4},即求得L1的 4 項分別包括{P1}、{P2}、{P3}、{P5}.對 L1掃描后,可得到上述 4 項各自的 support分別對應(yīng)為 2、3、3、3.繼續(xù)求 C2=L1∞L1,其分別包括{P1P2}、{P1P3}、{P1P5}、{P2P3}、{P2P5}、{P3P5}等 6 項,對其掃描得到各自的 support分別對應(yīng)為 1、2、1、2、3、2.由 min-sup=2,在 C2中繼續(xù)掃描后需要刪除{P1P2}、{P1P5},剩余的即構(gòu)成了 L2,其內(nèi)在四項分別為{P1P3}、{P2P3}、{P2P5}、{P3P5}等 ,掃描后得到對應(yīng)的支持度分別為 2、2、3、2.繼續(xù)求解 C3=L2∞L2,求其結(jié)果僅包括{P2P3P5},掃描后其支持度為2,符合min-sup要求,因此L3=C3,其結(jié)果也僅包括{P2P3P5}且支持度為2.

      若執(zhí)行優(yōu)化的Apriori-B算法,其步驟可分為三步.第一步求解L1,對數(shù)據(jù)庫D掃描得到C’1,其四個事務(wù)的構(gòu)成分別為{P1},{P3},{P4};{P2},{P3},{P5};{P1},{P2},{P3},{P5};{P2}, {P5}等四項.對 C’1繼續(xù)掃描可得到 L1,其四個事務(wù)的構(gòu)成分別為{P1}、{P2}、{P3}、{P5}四項,對應(yīng) support分別為 2、3、3、3.

      第二步求解 L2,先計算 C2=L1∞L1,其構(gòu)成包括{P1P2}、{P1P3}、{P1P5}、{P2P3}、{P2P5}、{P3P5}等六項.對 C2掃描后可以得到C’2,其內(nèi)在的四個事務(wù)的值分別為 {{P1P3}}、{{P2P3}{P2P5}{P3P5}}、{{P1P2}{P1P3}{P1P5}{P2P3}{P2P5}{P3P5}}、{{P2P5}}等四項.繼續(xù)對C’2掃描,結(jié)合最小支持度min-sup=2的要求,即可求得L2的四項其分別為{P1P3}、{P2P3}、{P2P5}、{P3P5},對應(yīng)支持度分別是 2、2、3、2.

      第三步求解 L3,首先計算 C3=L2∞L2,求得 C3僅包含一項{P2P3P5},繼續(xù)對 C3掃描可得到 C’3.C’3包含兩個事務(wù)T20、T30,對應(yīng)的構(gòu)成值分別為{{P2P3P5}}、{{P2P3P5}}.以此類推,繼續(xù)掃描 C’3即可求出 L3,只含有一個對象{P2P3P5},且其支持度為2.

      經(jīng)對比分析后不難看出,應(yīng)用Apriori-B算法僅僅是在第一步掃描對象是原數(shù)據(jù)庫D,而在后續(xù)的第二和第三步中,掃描對象均為前一次所得到的候選數(shù)據(jù)庫C’k.并且可知,若k值不斷增大,同原數(shù)據(jù)庫D相比而言,前者要遠遠小于后者.如此來看,采用Apriori-B算法,確實可減少I/O時間,可以大幅提升算法效率.

      3.5 算法效率實驗驗證

      以亳州學(xué)院教學(xué)評價系統(tǒng)數(shù)據(jù)進行挖掘為例,實驗環(huán)境:Win7,eclipse,Java編程語言,計算機配置酷睿i5 3.0 GHz,內(nèi)存4 G,硬盤1 T.算法運行時長對比分析見圖1.經(jīng)典Apriori如①,Apriori-A如②,Apriori-B如③.從圖1的情況可觀測到①的線條始終位于②、③之上.運用改進后的Apriori-A算法、Apriori-B算法在事務(wù)數(shù)相等的情況下運行時間較經(jīng)典Apriori算法更短,效率更高.從事務(wù)數(shù)規(guī)模不斷增大的趨勢來看,算法效率改善的愈加明顯,算法優(yōu)化具有較強的應(yīng)用意義.

      圖1 算法運行對比分析

      4 結(jié)語

      頻繁數(shù)據(jù)項集的生成是關(guān)聯(lián)規(guī)則挖掘的核心問題.Apriori—A算法思想是從刪除無效連接,以減少冗余的連接為前提條件,進而實現(xiàn)了減少剪枝步中的判斷量;Apriori—B算法則以候選事務(wù)數(shù)據(jù)庫替代原數(shù)據(jù)庫D,實現(xiàn)了大幅減少掃描次數(shù).經(jīng)定性分析和定量驗證,兩種優(yōu)化策略均在特定案例可以使之效率有效提升.但兩種優(yōu)化算法依然存在較為繁瑣的數(shù)據(jù)庫掃描操作,算法效率仍有較大的提升空間.

      猜你喜歡
      剪枝項集事務(wù)
      “事物”與“事務(wù)”
      基于分布式事務(wù)的門架數(shù)據(jù)處理系統(tǒng)設(shè)計與實現(xiàn)
      人到晚年宜“剪枝”
      基于YOLOv4-Tiny模型剪枝算法
      河湖事務(wù)
      剪枝
      天津詩人(2017年2期)2017-03-16 03:09:39
      關(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
      SQLServer自治事務(wù)實現(xiàn)方案探析
      莲花县| 新泰市| 安龙县| 察隅县| 响水县| 东海县| 阿拉善左旗| 临西县| 满洲里市| 盐山县| 甘谷县| 亳州市| 罗田县| 右玉县| 精河县| 十堰市| 霍邱县| 海门市| 孝昌县| 灵川县| 木里| 佛教| 汉沽区| 荆州市| 沾益县| 达拉特旗| 平果县| 依安县| 扎兰屯市| 临夏县| 神池县| 庆城县| 都兰县| 潜山县| 林甸县| 琼海市| 枣阳市| 伊宁县| 葫芦岛市| 尉犁县| 建宁县|