Apriori算法及其實(shí)現(xiàn)

1、精品好資料學(xué)習(xí)推薦數(shù)據(jù)挖掘設(shè)計(jì)論文院（系） 理學(xué)院 專 業(yè) 信息與計(jì)算科學(xué) 指導(dǎo)老師 劉建偉 班 級(jí) 101001班 姓 名 龍?jiān)葡?、黃健 時(shí) 間 2013年7月4日 Apriori算法及其實(shí)現(xiàn)內(nèi)容摘要經(jīng)典的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法Apriori 算法廣泛應(yīng)用于各種領(lǐng)域，通過(guò)對(duì)數(shù)據(jù)的關(guān)聯(lián)性進(jìn)行了分析和挖掘，挖掘出的這些信息在決策制定過(guò)程中具有重要的參考價(jià)值。信息技術(shù)的不斷推廣應(yīng)用，如何充分利用這些數(shù)據(jù)信息為各個(gè)行業(yè)決策者提供決策支持成為一個(gè)十分迫切的又棘手的問(wèn)題，人們除了利用現(xiàn)有的關(guān)系數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)查詢語(yǔ)句得到一般的直觀的信息以外，必須挖掘其內(nèi)含的、未知的卻又實(shí)際存在的數(shù)據(jù)關(guān)系。著名的Apriori

2、算法是一種挖掘關(guān)聯(lián)規(guī)則的算法。本文通過(guò)對(duì)Apriori算法的基本思想，挖掘出內(nèi)含的數(shù)據(jù)關(guān)系，并實(shí)現(xiàn)Apriori算法。關(guān)鍵字：數(shù)據(jù)挖掘，關(guān)聯(lián)規(guī)則，Apriori算法目錄1 人員分工- 1 -2 數(shù)據(jù)挖掘定義- 1 -3 關(guān)聯(lián)規(guī)則介紹- 3 -4 Apriori算法背景介紹- 3 -5 Apriori算法的描述- 5 -5.1 Apriori算法的說(shuō)明- 5 -4.2 Apriori算法的描述- 6 -4.3 Apriori算法的舉例- 6 -6 設(shè)計(jì)要求- 7 -7 設(shè)計(jì)原理- 7 -8 程序流程圖- 8 -9 程序運(yùn)行環(huán)境- 8 -10 測(cè)試數(shù)據(jù)- 8 -11 程序運(yùn)行結(jié)果- 9 -12 參

3、考資料- 10 -13設(shè)計(jì)總結(jié)- 11 -13.1黃健總結(jié)- 11 -13.2龍?jiān)葡榭偨Y(jié)- 11 -14程序源代碼見(jiàn)附錄1- 11 - 11 - / 141 人員分工黃健、龍?jiān)葡閮扇朔止っ鞔_，對(duì)Apriori算法都已熟練掌握。黃?。寒?huà)出程序流程圖，負(fù)責(zé)實(shí)現(xiàn)書(shū)上Apriori基本算法。龍?jiān)葡椋菏煜に惴?，測(cè)試程序，通過(guò)查閱資料，做出數(shù)據(jù)挖掘的流程，并了解Apriori改進(jìn)的一些算法，主要負(fù)責(zé)論文。2 數(shù)據(jù)挖掘定義數(shù)據(jù)挖掘（Data Mining）就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識(shí)的過(guò)程。與數(shù)據(jù)挖掘相近的同義

4、詞有數(shù)據(jù)融合、數(shù)據(jù)分析和決策支持等。這個(gè)定義包括好幾層含義：數(shù)據(jù)源必須是真實(shí)的、大量的、含噪聲的；發(fā)現(xiàn)的是用戶感興趣的知識(shí)；發(fā)現(xiàn)的知識(shí)要可接受、可理解、可運(yùn)用；并不要求發(fā)現(xiàn)放之四海皆準(zhǔn)的知識(shí)，僅支持特定的發(fā)現(xiàn)問(wèn)題。從廣義上理解，數(shù)據(jù)、信息也是知識(shí)的表現(xiàn)形式，但是人們更把概念、規(guī)則、模式、規(guī)律和約束等看作知識(shí)。人們把數(shù)據(jù)看作是形成知識(shí)的源泉，好像從礦石中采礦或淘金一樣。原始數(shù)據(jù)可以是結(jié)構(gòu)化的，如關(guān)系數(shù)據(jù)庫(kù)中的數(shù)據(jù)；也可以是半結(jié)構(gòu)化的，如文本、圖形和圖像數(shù)據(jù)；甚至是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。發(fā)現(xiàn)知識(shí)的方法可以是數(shù)學(xué)的，也可以是非數(shù)學(xué)的；可以是演繹的，也可以是歸納的。發(fā)現(xiàn)的知識(shí)可以被用于信息管理，查

5、詢優(yōu)化，決策支持和過(guò)程控制等，還可以用于數(shù)據(jù)自身的維護(hù)。因此，數(shù)據(jù)挖掘是一門(mén)交叉學(xué)科，它把人們對(duì)數(shù)據(jù)的應(yīng)用從低層次的簡(jiǎn)單查詢，提升到從數(shù)據(jù)中挖掘知識(shí)，提供決策支持。在這種需求牽引下，匯聚了不同領(lǐng)域的研究者，尤其是數(shù)據(jù)庫(kù)技術(shù)、人工智能技術(shù)、數(shù)理統(tǒng)計(jì)、可視化技術(shù)、并行計(jì)算等方面的學(xué)者和工程技術(shù)人員，投身到數(shù)據(jù)挖掘這一新興的研究領(lǐng)域，形成新的技術(shù)熱點(diǎn)。數(shù)據(jù)挖掘是一種新的商業(yè)信息處理技術(shù)，其主要特點(diǎn)是對(duì)商業(yè)數(shù)據(jù)庫(kù)中的大量業(yè)務(wù)數(shù)據(jù)進(jìn)行抽取、轉(zhuǎn)換、分析和其他模型化處理，從中提取輔助商業(yè)決策的關(guān)鍵性數(shù)據(jù)。簡(jiǎn)而言之，數(shù)據(jù)挖掘其實(shí)是一類深層次的數(shù)據(jù)分析方法。數(shù)據(jù)分析本身已經(jīng)有很多年的歷史，只不過(guò)在過(guò)去數(shù)據(jù)收集和

6、分析的目的是用于科學(xué)研究，另外，由于當(dāng)時(shí)計(jì)算能力的限制，對(duì)大數(shù)據(jù)量進(jìn)行分析的復(fù)雜數(shù)據(jù)分析方法受到很大限制。現(xiàn)在，由于各行業(yè)業(yè)務(wù)自動(dòng)化的實(shí)現(xiàn)，商業(yè)領(lǐng)域產(chǎn)生了大量的業(yè)務(wù)數(shù)據(jù)，這些數(shù)據(jù)不再是為了分析的目的而收集的，而是由于純機(jī)會(huì)的（Opportunistic）商業(yè)運(yùn)作而產(chǎn)生。分析這些數(shù)據(jù)也不再是單純?yōu)榱搜芯康男枰?，更主要是為商業(yè)決策提供真正有價(jià)值的信息，進(jìn)而獲得利潤(rùn)。但所有企業(yè)面臨的一個(gè)共同問(wèn)題是：企業(yè)數(shù)據(jù)量非常大，而其中真正有價(jià)值的信息卻很少，因此從大量的數(shù)據(jù)中經(jīng)過(guò)深層分析，獲得有利于商業(yè)運(yùn)作、提高競(jìng)爭(zhēng)力的信息，就像從礦石中淘金一樣，數(shù)據(jù)挖掘也因此而得名。因此，數(shù)據(jù)挖掘可以描述為：按企業(yè)既定業(yè)務(wù)目

7、標(biāo)，對(duì)大量的企業(yè)數(shù)據(jù)進(jìn)行探索和分析，揭示隱藏的、未知的或驗(yàn)證已知的規(guī)律性，并進(jìn)一步將其模型化的先進(jìn)有效的方法。DM 不能告訴你某個(gè)模型對(duì)你的企業(yè)的實(shí)際價(jià)值DM是一個(gè)工具，他只是幫助商業(yè)人士更深入、更容易地分析數(shù)據(jù)，但是無(wú)法告訴你某個(gè)模型對(duì)你的企業(yè)的實(shí)際價(jià)值，DM中得到的模型必須在現(xiàn)實(shí)生活中進(jìn)行驗(yàn)證，DM不會(huì)在缺乏指導(dǎo)的情況下自動(dòng)的發(fā)現(xiàn)模型。數(shù)據(jù)分析者必須知道你所選用的DM工具是如何工作的，采用的算法的原理是什么。DM永遠(yuǎn)不會(huì)替代有經(jīng)驗(yàn)的商業(yè)分析師或管理人員所起的作用，它只是一個(gè)強(qiáng)大的工具。3關(guān)聯(lián)規(guī)則介紹如果一個(gè)事務(wù)中含有X，則該事務(wù)中很可能含有Y。具體形式為XY，即通?？梢悦枋鰹?當(dāng)一個(gè)事務(wù)中

8、顧客購(gòu)買(mǎi)了一樣?xùn)|西鋼筆(這里X=“鋼筆”)則很可能他同時(shí)還購(gòu)買(mǎi)了墨水(這里Y= 墨水)，這就是關(guān)聯(lián)規(guī)則。在美國(guó)，有一種說(shuō)法是:“尿不濕”和“啤酒”經(jīng)常一起被購(gòu)買(mǎi)。這種說(shuō)法有其一定的現(xiàn)實(shí)意義:1)或許是該年齡段的經(jīng)常喝啤酒的人剛好家庭開(kāi)始養(yǎng)育小孩;2)或許是因?yàn)槠【坪榷?，需要用尿不濕。然而不管怎樣，如果沒(méi)有數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則在這里的應(yīng)用，你是無(wú)論如何想象不出這樣有點(diǎn)驚人的“笑話”。4Apriori算法背景介紹關(guān)聯(lián)規(guī)則挖掘的一個(gè)典型例子是購(gòu)物籃分析。市場(chǎng)分析員要從大量的數(shù)據(jù)中發(fā)現(xiàn)顧客放入其購(gòu)物籃中的不同商品之間的關(guān)系。如果顧客買(mǎi)牛奶，他也購(gòu)買(mǎi)面包的可能性有多大？ 什么商品組或集合顧客多半會(huì)在一次

9、購(gòu)物時(shí)同時(shí)購(gòu)買(mǎi)？例如，買(mǎi)牛奶的顧客有80%也同時(shí)買(mǎi)面包，或買(mǎi)鐵錘的顧客中有70%的人同時(shí)也買(mǎi)鐵釘，這就是從購(gòu)物籃數(shù)據(jù)中提取的關(guān)聯(lián)規(guī)則。分析結(jié)果可以幫助經(jīng)理設(shè)計(jì)不同的商店布局。一種策略是：經(jīng)常一塊購(gòu)買(mǎi)的商品可以放近一些，以便進(jìn)一步刺激這些商品一起銷售，例如，如果顧客購(gòu)買(mǎi)計(jì)算機(jī)又傾向于同時(shí)購(gòu)買(mǎi)財(cái)務(wù)軟件，那么將硬件擺放離軟件陳列近一點(diǎn)，可能有助于增加兩者的銷售。另一種策略是：將硬件和軟件放在商店的兩端，可能誘發(fā)購(gòu)買(mǎi)這些商品的顧客一路挑選其他商品。關(guān)聯(lián)規(guī)則是描述數(shù)據(jù)庫(kù)中數(shù)據(jù)項(xiàng)之間存在的潛在關(guān)系的規(guī)則,形式為“A1A2.Am=B1B2.Bn”,其Ai(i=1,2,.,m),Bj(j=1,2,.,n)是數(shù)

10、據(jù)庫(kù)中的數(shù)據(jù)項(xiàng).數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)規(guī)則即根據(jù)一個(gè)事務(wù)中某些項(xiàng)的出現(xiàn),可推導(dǎo)出另一些項(xiàng)在同一事務(wù)中也出現(xiàn)。挖掘關(guān)聯(lián)規(guī)則的問(wèn)題描述如下:設(shè): I=i1,i2.,im是所有項(xiàng)目的集合. D是所有事務(wù)的集合(即數(shù)據(jù)庫(kù)), 每個(gè)事務(wù)T是一些項(xiàng)目的集合, T包含在I中, 每個(gè)事務(wù)可以用唯一的標(biāo)識(shí)符TID來(lái)標(biāo)識(shí). 設(shè)X為某些項(xiàng)目的集合,如果X包含在T中, 則稱事務(wù)T包含X, 關(guān)聯(lián)規(guī)則則表示為如下形式(X包含在T)=(Y包含在T)的蘊(yùn)涵式, 這里X包含在I中, Y包含在I中, 并且XY=. 其意義在于一個(gè)事務(wù)中某些項(xiàng)的出現(xiàn),可推導(dǎo)出另一些項(xiàng)在同一事務(wù)中也出現(xiàn) (為簡(jiǎn)單化,將(X包含在T)=(Y包含在T)表示為X

11、=Y, 這里,=稱為關(guān)聯(lián)操作, X稱為關(guān)聯(lián)規(guī)則的先決條件, Y稱為關(guān)聯(lián)規(guī)則的結(jié)果).事務(wù)集D中的規(guī)則X=Y是由支持度s(support)和置信度c(confidence)約束,置信度表示規(guī)則的強(qiáng)度, 支持度表示在規(guī)則中出現(xiàn)的頻度。數(shù)據(jù)項(xiàng)集X的支持度s(X)是D中包含X的事務(wù)數(shù)量與D的總事務(wù)數(shù)量之比, 但為下文便于敘述, 數(shù)據(jù)項(xiàng)集X的支持度是用數(shù)據(jù)庫(kù)D中包含X的數(shù)量來(lái)表示;規(guī)則X=Y的支持度s定義為: 在D中包含XY的事務(wù)所占比例為s%, 表示同時(shí)包含X和Y的事務(wù)數(shù)量與D的總事務(wù)量之比; 規(guī)則X=Y的置信度c定義為: 在D中,c%的事務(wù)包含X的同時(shí)也包含Y, 表示D中包含X的事務(wù)中有多大可能性包

12、含Y.最小支持度閾值minsupport表示數(shù)據(jù)項(xiàng)集在統(tǒng)計(jì)意義上的最低主要性. 最小置信度閾值mincontinence表示規(guī)則的最低可靠性. 如果數(shù)據(jù)項(xiàng)集X滿足X.support=minsupport, 則X是大數(shù)據(jù)項(xiàng)集. 一般由用戶給定最小置信度閾值和最小支持度閾值.置信度和支持度大于相應(yīng)閾值的規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則, 反之稱為弱關(guān)聯(lián)規(guī)則. 發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的任務(wù)就是從數(shù)據(jù)庫(kù)中發(fā)現(xiàn)那些置信度、支持度大小等于給定值的強(qiáng)壯規(guī)則.基于上述概念，我們可以很容易得到一些基本結(jié)論:(1) K維數(shù)據(jù)項(xiàng)集XK是頻繁項(xiàng)集的必要條件是它所有K-1維子項(xiàng)集也為頻繁項(xiàng)集，記為XK-1(2)如果K維數(shù)據(jù)項(xiàng)集XK的任意一個(gè)K

13、-1維子集XK-1，不是頻繁項(xiàng)集，則K維數(shù)據(jù)項(xiàng)集XK本身也不是最大數(shù)據(jù)項(xiàng)集。(3) XK是K維頻繁項(xiàng)集，如果所有K-1維頻繁項(xiàng)集集合XK-1中包含XK的K-1維子項(xiàng)集的個(gè)數(shù)小于K，則XK不可能是K維最大頻繁數(shù)據(jù)項(xiàng)集。證明:很明顯，數(shù)據(jù)項(xiàng)集XK-1:的K-1維子項(xiàng)集的個(gè)數(shù)為K-1。如果高頻繁數(shù)據(jù)項(xiàng)集XK-1，中包含XK的K-1.維子項(xiàng)集的個(gè)數(shù)小于k，則存在XK的K-1維子項(xiàng)集不是頻繁數(shù)據(jù)項(xiàng)集，由結(jié)論(2)知K維數(shù)據(jù)項(xiàng)集本身也不是高頻繁數(shù)據(jù)項(xiàng)集。5 Apriori算法的描述5.1 Apriori算法的說(shuō)明在Apriori算法中,尋找最大項(xiàng)目集的基本思想是: 算法需要對(duì)數(shù)據(jù)集進(jìn)行多步處理.第一步,簡(jiǎn)

14、單統(tǒng)計(jì)所有含一個(gè)元素項(xiàng)目集出現(xiàn)的頻率,并找出那些不小于最小支持度的項(xiàng)目集, 即一維最大項(xiàng)目集. 從第二步開(kāi)始循環(huán)處理直到再?zèng)]有最大項(xiàng)目集生成. 循環(huán)過(guò)程是: 第k步中, 根據(jù)第k-1步生成的(k-1)維最大項(xiàng)目集產(chǎn)生k維侯選項(xiàng)目集, 然后對(duì)數(shù)據(jù)庫(kù)進(jìn)行搜索, 得到侯選項(xiàng)目集的項(xiàng)集支持度, 與最小支持度比較, 從而找到k維最大項(xiàng)目集.為方便后文敘述，現(xiàn)約定如下:1.數(shù)據(jù)庫(kù)事務(wù)中的項(xiàng)目都是以字母順序排列的,每個(gè)項(xiàng)目用來(lái)標(biāo)識(shí), 這里TID表示相應(yīng)事務(wù)的標(biāo)識(shí)符, item則表示項(xiàng)目名稱.2.每個(gè)項(xiàng)目集的項(xiàng)目數(shù)稱為該項(xiàng)目集的size. 當(dāng)項(xiàng)目集的size=k時(shí), 稱該項(xiàng)目集為k-itemset(k維項(xiàng)目集

15、).下文中遇到的以下符號(hào),分別代表相應(yīng)的內(nèi)容k-itemsetk維項(xiàng)目集Lk具有最小支持度的最大k-itemsetCk侯選的k-itemsets(潛在的最大項(xiàng)目集)4.2Apriori算法的描述Apriori算法的第一步是簡(jiǎn)單統(tǒng)計(jì)所有含一個(gè)元素的項(xiàng)集出現(xiàn)的頻率,來(lái)決定最大的一維項(xiàng)目集。在第k步,分兩個(gè)階段,首先用一函數(shù)sc_candidate(候選),通過(guò)第(k-1)步中生成的最大項(xiàng)目集Lk-1來(lái)生成侯選項(xiàng)目集Ck。然后搜索數(shù)據(jù)庫(kù)計(jì)算侯選項(xiàng)目集Ck的支持度。為了更快速地計(jì)算Ck中項(xiàng)目的支持度, 文中使用函數(shù)count_support計(jì)算支持度。4.3 Apriori算法的舉例示例說(shuō)明Aprio

16、ri算法運(yùn)作過(guò)程有一數(shù)據(jù)庫(kù)D, 其中有四個(gè)事務(wù)記錄, 分別表示為T(mén)IDItemsT1I1,I3,I4T2I2,I3,I5T3I1,I2,I3,I5T4I2,I5在Apriori算法中每一步創(chuàng)建該步的侯選集.統(tǒng)計(jì)每個(gè)侯選項(xiàng)目集的支持度,并和預(yù)定義的最小支持度比較,來(lái)確定該步的最大項(xiàng)目集.首先統(tǒng)計(jì)出一維項(xiàng)目集,即:C1.這里預(yù)定義最小支持度minsupport=2,侯選項(xiàng)目集中滿足最小支持度要求的項(xiàng)目集組合成最大的1-itemsets.為生成最大的2-itemsets,使用了sc_candidate函數(shù)中join步,即: L1joinL1,并通過(guò)prune步刪除那些C2的那些子集不在L1中的項(xiàng)目集

17、.生成了侯選項(xiàng)目集C2.搜索D中4個(gè)事務(wù),統(tǒng)計(jì)C2中每個(gè)侯選項(xiàng)目集的支持度.然后和最小支持度比較,生成L2.侯選項(xiàng)目集C3是由L2生成.要求自連接的兩個(gè)最大2-itemsets中,第一個(gè)項(xiàng)目相同,在L2中滿足該條件的有I2,I3,I2,I5.這兩個(gè)集合經(jīng)過(guò)join步后, 產(chǎn)生集合I2，I3，I5.在prune步中,測(cè)試I2，I3，I5的子集I3，I5,I2，I3,I2，I5是否在L2中,由L2可以知道I3,I5,I2,I3,I2,I5本身就是最大2-itemsets.即I2,I3,I5的子集都是最大項(xiàng)目集.那么I2,I3,I5為侯選3-itemset.然后搜索數(shù)據(jù)庫(kù)中所有事務(wù)記錄,生成最大的3

18、-tiemsetsL3. 此時(shí), 從L3中不能再生成侯選4-itemset .Apriori算法結(jié)束.6設(shè)計(jì)要求用java代碼實(shí)現(xiàn)Apriori算法，并對(duì)每一步的結(jié)果做輸出，即每一步產(chǎn)生的頻繁項(xiàng)集輸出。7設(shè)計(jì)原理Apriori算法的第一步是簡(jiǎn)單統(tǒng)計(jì)所有含一個(gè)元素的項(xiàng)集出現(xiàn)的頻率,來(lái)決定最大的一維項(xiàng)目集。在第k步,分兩個(gè)階段,首先用一函數(shù)sc_candidate(候選),通過(guò)第(k-1)步中生成的最大項(xiàng)目集Lk-1來(lái)生成侯選項(xiàng)目集Ck。然后搜索數(shù)據(jù)庫(kù)計(jì)算侯選項(xiàng)目集Ck的支持度。為了更快速地計(jì)算Ck中項(xiàng)目的支持度, 文中使用函數(shù)count_support計(jì)算支持度。8程序流程圖9程序運(yùn)行環(huán)境Mye

19、clipse、WindowsXP及其以上10測(cè)試數(shù)據(jù)TIDItemsT100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3設(shè)置min_sup=2，頻繁3項(xiàng)集：項(xiàng)集支持度計(jì)數(shù)I1,I2,I32I1,I2,I52設(shè)置min_sup=3，頻繁2項(xiàng)集：項(xiàng)集支持度計(jì)數(shù)I1,I2 4I1,I3 4I2,I3 411程序運(yùn)行結(jié)果12參考資料1（加）Jiawei Han,Micheline Kamber著.范明等譯.數(shù)據(jù)挖掘：概念與技術(shù).北京：機(jī)械工業(yè)出版社，2001.82 陳京民 數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘技術(shù) 2002.北京電子工業(yè)出版社3