apriori算法的改進

《apriori算法的改進》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第10卷第l6期2010年6月科學(xué)技術(shù)與工程Vo1．10No．16June20101671·1815(2010)16—4028—04ScienceTechnologyandEn~neefing@2010Sci．Teeh．Engng．Apriori算法的改進劉東洋劉恩(遼寧石油化工大學(xué)計算機與通信工程學(xué)院，撫順113001)摘要介紹數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則的情況。在分析關(guān)聯(lián)規(guī)則挖掘算法的基礎(chǔ)上，對經(jīng)典Apfiofi算法進行改進，改進算法意在通過減少生成候選頻繁項集的數(shù)量和掃描數(shù)據(jù)庫次數(shù)。從而，加快算法的執(zhí)行效率和節(jié)省空間。關(guān)鍵詞數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則Apfio

2、f中圖法分類號TP391．3；文獻標志碼A數(shù)據(jù)挖掘(DataMining)，就是從大量的、不完項的集合，使得，。每一個事務(wù)有一個標識符，全的、有噪聲的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，稱作TID。設(shè)A是一個項集，事務(wù)包含A當且僅提取隱含在其中的、人們事先不知道的、是潛在有當A。關(guān)聯(lián)規(guī)則是形如A日的蘊涵式，其中用的信息和知識的過程¨J。數(shù)據(jù)挖掘算法有決策Ac，Bc，，并且AnB=。關(guān)聯(lián)分析中還包樹算法、分類算法、聚類分析算法、關(guān)聯(lián)算法等。其括兩個重要的參數(shù)，支持度(min—sup)和置信度中，隨著數(shù)據(jù)量的逐年增加和人們對各個數(shù)據(jù)項之(min—conf

3、)。具體定義如下：間關(guān)系的關(guān)注，關(guān)聯(lián)規(guī)則挖掘在數(shù)據(jù)挖掘中占有了支持度：suppo~(A曰)：P(Au曰)：—Na-'--~B—_一×重要的地位，也是數(shù)據(jù)挖掘的主要任務(wù)之一。1993年由Agrawal等人針對購物籃問題提出100％，即A和B這兩個項集在事務(wù)集D中同時出的，其目的是為了發(fā)現(xiàn)數(shù)據(jù)庫中不同項集之間的聯(lián)系現(xiàn)的概率。規(guī)則。通過關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法尋找形如“If(條件)，置信度：confidence()：P(BIA)：×』V^else(結(jié)論)”的規(guī)則，在關(guān)聯(lián)規(guī)則挖掘算法的研究中，100％，即在出現(xiàn)項集的事務(wù)集中，項集也同時Agrawal提出的Apf

4、iofi算法最為經(jīng)典，其基本思想是重復(fù)掃描數(shù)據(jù)庫，根據(jù)一個頻繁集的任意子集都是頻出現(xiàn)的概率。同時滿足最小支持度(min—sup)和最小置信度繁集的原理，可以從長度為k的頻繁集迭代地產(chǎn)生長(min_conf)的規(guī)則稱作強規(guī)則。度為k+1的候選集；再掃描數(shù)據(jù)庫以驗證其是否為頻繁集。但該算法本身固有缺陷是在大數(shù)據(jù)量的項的集合稱為項集(itemset)，包含個項的項時候多次掃描數(shù)據(jù)庫及產(chǎn)生大量候選集。集稱為一項集。項集的出現(xiàn)頻率是包含項集的事務(wù)數(shù)，簡稱為項集的頻率、支持計數(shù)或計數(shù)。如果1關(guān)聯(lián)規(guī)則的基本概念項集的出現(xiàn)頻率大于或等于最小支持度，則稱為頻繁項集

5、_4頻繁一項集的集合通常記作。設(shè)，={i，i，?，}是項的集合。設(shè)任務(wù)相關(guān)聯(lián)規(guī)則的挖掘問題就是生成所有滿足用戶指定的最小支持度(min—sup)和最小置信度(min—的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個事務(wù)是conf)的關(guān)聯(lián)規(guī)則，即這些關(guān)聯(lián)規(guī)則的支持度suppo~2010年3月18日收到(AB)和置信度confidence(AB)分別不小于最小支第一作者簡介：劉東洋(1982一)，男，遼寧石油化工大學(xué)碩士研究持度(min—sup)和最小置信度(min—conf)的關(guān)聯(lián)規(guī)生，研究方向：數(shù)據(jù)挖掘。則。關(guān)聯(lián)規(guī)則的挖掘是一個兩步的過程：16期劉東洋，等：

6、Apriori算法的改進1)找出所有頻率項集：根據(jù)定義，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持計數(shù)一樣。3Apriori算法的缺陷及改進方法2)由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則：根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。3．1算法的缺陷Apriori算法使用逐層搜索的迭代方法，通過低2經(jīng)典關(guān)聯(lián)規(guī)則Apriori算法維頻繁項目集產(chǎn)生高維頻繁項目集。這就導(dǎo)致經(jīng)典Apriori算法存在兩個問題Aproiori算法是第一個關(guān)聯(lián)規(guī)則挖掘算法，它開(1)多次掃描事務(wù)數(shù)據(jù)庫，需要很大的I／O創(chuàng)性地使用基于支持度的剪枝技術(shù)，系統(tǒng)地控制候負載。選項集指數(shù)增長。

7、其核心是使用候選項集找頻繁(2)可能產(chǎn)生龐大的候選集。由一，產(chǎn)生k一項集。該算法的優(yōu)點在于利用Apriori性質(zhì)：一個頻候選集c是呈指數(shù)增長的，在處理大批量信息數(shù)據(jù)繁項集中任一子集也應(yīng)是頻繁項集。有效地剪枝時，使得消耗大量的時間和空問。項目集，盡可能不生成和不計算那些不可能成為頻3．2改進方法繁項目集的候選項目集，從而生成了較小的候選項本文主要是針對產(chǎn)生大量的候選集進行改進。目集集合。以下是Aproiori算法產(chǎn)生頻繁項集不分為了減少候選項集，就要刪除非頻繁項。我們這里的偽代碼：利用Apriori的一個特性：如果k一頻繁項目集中的n乃K：1某個項

8、目在k一頻繁項目集中出現(xiàn)的次數(shù)小于k，那Fk={iIiE，A(?i)≥N×minsup}{發(fā)現(xiàn)所有的頻繁1一么這個項目不可能出現(xiàn)在k+1