基于關(guān)聯(lián)規(guī)則挖掘的apriori改進算法

《基于關(guān)聯(lián)規(guī)則挖掘的apriori改進算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、基于關(guān)聯(lián)規(guī)則挖掘的Apriori改進算法　　摘要關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘技術(shù)的一個重要分支，其中Apriori算法是最經(jīng)典和最有影響力的算法。本文在討論和分析了關(guān)聯(lián)規(guī)則挖掘的基本概念后，提出了一種減少掃描數(shù)據(jù)庫次數(shù)的改進算法。改進后的算法分析證明，它可以有效地提高數(shù)據(jù)挖掘的性能?！　　娟P(guān)鍵詞】關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)挖掘Apriori算法　　數(shù)據(jù)挖掘是從大量數(shù)據(jù)中挖掘有趣模式和知識的過程，數(shù)據(jù)源包括數(shù)據(jù)庫、數(shù)據(jù)倉庫、Web、其他信息存儲庫或動態(tài)地流入系統(tǒng)的數(shù)據(jù)?，F(xiàn)今計算機技術(shù)與數(shù)據(jù)庫技術(shù)在飛速地發(fā)展，如何從海量的數(shù)據(jù)中快速準確地找出有用的信息是數(shù)據(jù)挖掘問題中的一項重要研究內(nèi)容。　　在1994年，由Ag

2、rawal提出的Apriori算法，是關(guān)聯(lián)規(guī)則里的一項基本算法，它的基本思想是重復掃描數(shù)據(jù)庫，由長度為k的頻繁項集進行迭代計算產(chǎn)生長度為k+1的候選集，再對數(shù)據(jù)庫進行掃描判斷其是否為頻繁項集?！　≡谶^往的研究當中，許多文獻提出了基于Apriori算法的改進。林佳雄等人提出的基于數(shù)組向量的Apriori算法改進，該算法改進了連接比較的次數(shù)、減少不必要事務(wù)的掃描和提高了算法對內(nèi)存空間的利用效率。曹瑩等人提出的基于向量矩陣優(yōu)化頻繁項的改進Apriori算法，趙學健等人的一種正交鏈表存儲的改進Apriori算法，該算法Apriori算法復雜的自連接和剪枝過程進行了優(yōu)化，簡化了頻繁項目集的生成過程，提

3、高了Apriori算法的時間效率?！　?關(guān)聯(lián)規(guī)則挖掘的概況　　關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中的一個很重要的課題，顧名思義，它是從數(shù)據(jù)背后發(fā)現(xiàn)事物之間可能存在的關(guān)聯(lián)或者聯(lián)系。最早是為了發(fā)現(xiàn)超市交易數(shù)據(jù)庫中不同的商品之間的關(guān)系。目的在于發(fā)現(xiàn)數(shù)據(jù)項之間的潛在關(guān)系，通過它提取出的信息將有助于人們把握和預測行業(yè)發(fā)展規(guī)律，從而更好地制定發(fā)展計劃和規(guī)避風險?！　∧敲磫栴}如下所述：假設(shè)I={i1，i2，...im}是所有項目的集合，D是一個數(shù)據(jù)庫，事務(wù)T是一個子項（TI）。每個T都有自己獨特的標識。A是由項目組成的集合，即項集。T包含A，當且僅當AT。如果項集A的項目數(shù)為k，則稱為k維項目集。項集A的出現(xiàn)頻率是包

4、含項集的事務(wù)數(shù)，簡稱為項集的支持度。如果項集支持度超過由用戶給定的最小支持度閾值，則稱為頻繁項集，簡稱頻繁集?！　￡P(guān)聯(lián)規(guī)則是形如的蘊涵式，其中，X稱為關(guān)聯(lián)規(guī)則的先導，Y稱為后繼。其中，關(guān)聯(lián)規(guī)則X與Y存在支持度和置信度。關(guān)聯(lián)規(guī)則在D中的支持度（support）是D中事務(wù)同時包含X和Y的百分比，即概率。置信度（confidence）是D中事務(wù)已經(jīng)包含X的情況下，包含Y的百分比，即條件概率。如果滿足最小支持度閾值和最小置信度閾值，則認為關(guān)聯(lián)規(guī)則是有趣的。　　2Apriori算法　　2.1核心思想　　最著名的關(guān)聯(lián)規(guī)則挖掘算法是Apriori算法，它是一種以概率為基礎(chǔ)的關(guān)聯(lián)規(guī)則算法，能實現(xiàn)從少到多，從

5、簡單到復雜尋找極大頻繁集。Apriori算法主要利用了向下封閉屬性：如果一個項集是頻繁項目集，那么它的非空子集必定是頻繁項目集。在運算過程中首先生成1-頻繁項目集，再利用1-頻繁項目集生成2-頻繁項目集，然后根據(jù)2-頻繁項目集生成3-頻繁項目集，依次類推，直至生成所有的頻繁項目集。最后從頻繁項目集中找出符合條件的關(guān)聯(lián)規(guī)則?！　?.2算法過程　　Apriori算法采用遞推的方法來生成所需的頻繁集，主要步驟如下：　?。?）制定最小支持度及最小置信度；　?。?）Apriori算法使用了候選項集的概念，通過掃描數(shù)據(jù)庫產(chǎn)生候選項目集，如果候選項目集的支持度不小于最小支持度，則該候選項目集為頻繁項目集；

6、　?。?）從數(shù)據(jù)庫中讀入所有事務(wù)數(shù)據(jù)，得出候選1項集C1及相應(yīng)的支持度數(shù)據(jù)，通過將每個1項集的支持度與最小支持度比較，得出頻繁項集合L1，然后將這些頻繁1項集兩兩連接，產(chǎn)生候選2項集和C2；　?。?）然后再次掃描數(shù)據(jù)庫得到候選2項集合C2的支持度，將2項集的支持度與最小支持度比較，確定頻繁2項集。類似地，利用這些頻繁2項集L2產(chǎn)生候選3項集和確定頻繁3項集，以此類推；　?。?）反復掃描數(shù)據(jù)庫，與最小支持度比較，產(chǎn)生更高項的頻繁項集合，再結(jié)合產(chǎn)生下一級候選項集，直到不再產(chǎn)生出新的候選項集為止；　　3Apriori算法的改進及分析　　3.1改進算法的思想　　關(guān)聯(lián)規(guī)則是其支持度和置信度分別滿足用戶

7、給定閾值的規(guī)則，發(fā)現(xiàn)關(guān)聯(lián)規(guī)則需要如下兩步驟：　?。?）找出所有的頻繁集，其最后出現(xiàn)的頻率和預定義的最小支持度是相同的?！　。?）強關(guān)聯(lián)規(guī)則是由頻繁集產(chǎn)生的，它必須滿足最小支持度和最小置信度?！　〉茿priori算法由于需要多次掃描數(shù)據(jù)庫，而造成過重的I/0負擔，因此改進算法將通過減少數(shù)據(jù)庫掃描次數(shù)的方式來減輕I/0負擔。　　改進算法的思想就是利用頻繁k+1項集中的任一元素，一定可以表示成頻繁k項集中某一元素