apriori算法的改進(jìn)

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

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

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

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

5、_4頻繁一項(xiàng)集的集合通常記作。設(shè)，={i，i，?，}是項(xiàng)的集合。設(shè)任務(wù)相關(guān)聯(lián)規(guī)則的挖掘問題就是生成所有滿足用戶指定的最小支持度(min—sup)和最小置信度(min—的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個(gè)事務(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ī)則的挖掘是一個(gè)兩步的過程：16期劉東洋，等：

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

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

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