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

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

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

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

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

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

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

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

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