基于Apriori算法的數(shù)據(jù)挖掘算法研究

李晉芳

（晉城廣播電視大學(xué)，山西晉城 048026）

一、引言

關(guān)聯(lián)規(guī)則挖掘是一項最有影響的數(shù)據(jù)挖掘技術(shù)，尤其在針對交易數(shù)據(jù)的分析上，更是發(fā)揮了重要的作用。關(guān)聯(lián)規(guī)則廣泛應(yīng)用在各個領(lǐng)域中，除了電信網(wǎng)絡(luò)、商品市場、電子商務(wù)風(fēng)險管理及庫存控制之外，也涉及到商業(yè)情報和市場營銷領(lǐng)域。關(guān)聯(lián)規(guī)則挖掘技術(shù)的重點就在于頻繁項目集的挖掘。經(jīng)過大量文獻(xiàn)的調(diào)查顯示，關(guān)聯(lián)規(guī)則挖掘中要花費巨大的處理時間去計算發(fā)現(xiàn)頻繁項目集。我們注意到，大部分的算法發(fā)現(xiàn)頻繁模式需要多次遍歷數(shù)據(jù)庫，導(dǎo)致大量的磁盤讀取，造成了巨大的I/O負(fù)載。Apriori算法是關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法，它采用自下而上的方式，搜索枚舉出所有的頻繁項集。本文提出的Apriori算法的改進(jìn)版本，則采用自上而下的方式，避免生成不必要的模式規(guī)則，從而大大減少了數(shù)據(jù)庫掃描的次數(shù)。

二、相關(guān)工作

數(shù)據(jù)挖掘（Data Mining）就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際應(yīng)用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識的過程。其中最有名的、最流行的數(shù)據(jù)挖掘技術(shù)是關(guān)聯(lián)規(guī)則和頻繁項集挖掘算法。該算法最初是由Agrawal等人提出的購物籃分析。由于該算法顯著的實用性，關(guān)聯(lián)規(guī)則挖掘已成為大家都熱衷于研究的課題。

繼Apriori算法之后，不同的學(xué)者針對此算法的弱點提出了很多種改進(jìn)算法，其中J.Han等提出了不產(chǎn)生候選挖掘頻繁項集的方法—FP-樹頻集算法。此算法采用分而治之的策略，在經(jīng)過第一遍掃描之后，把數(shù)據(jù)庫中的頻集壓縮進(jìn)一棵頻繁模式樹（FP-tree），同時依然保留其中的關(guān)聯(lián)信息，隨后再將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻集相關(guān)，然后再對這些條件庫分別進(jìn)行挖掘。當(dāng)原始數(shù)據(jù)量很大的時候，也可以結(jié)合劃分的方法，使得一個FP-tree可以放入主存中。實驗表明，F(xiàn)P-growth對不同長度的規(guī)則都有很好的適應(yīng)性，同時在效率上較之Apriori算法有巨大的提高。它是關(guān)聯(lián)規(guī)則挖掘發(fā)展的又一個里程碑。

盡管FP樹算法對Apriori算法進(jìn)行了改進(jìn)，但它仍然繼承了Apriori算法掃描多遍數(shù)據(jù)庫的缺點。需要注意的是，為了減少數(shù)據(jù)庫掃描的次數(shù)，同時用較少的執(zhí)行速度，以減少內(nèi)存空間，就導(dǎo)致了需要進(jìn)行大量的磁盤讀取工作，由此給I/O子系統(tǒng)造成了巨大的負(fù)擔(dān)。這些相關(guān)問題促使我們繼續(xù)進(jìn)行這方面的研究工作。由此，我們提出了一種新的改進(jìn)的Apriori算法，從而減少了程序運行的時間和空間。

三、頻繁項集和關(guān)聯(lián)規(guī)則

設(shè)I={i1，i2…，in}為所有項目的集合，設(shè)A是一個由項目構(gòu)成的集合，稱為項集。事務(wù)T是一個項目子集,每一個事務(wù)具有唯一的事務(wù)標(biāo)識Tid。事務(wù)T包含項集A，當(dāng)且僅當(dāng)AT。如果項集A中包含k個項目，則稱其為k項集。S為事務(wù)數(shù)據(jù)庫，項集A在事務(wù)數(shù)據(jù)庫S中出現(xiàn)的次數(shù)占S中總事務(wù)的百分比叫做項集的支持度（support）。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集。

Apriori算法用來進(jìn)行頻繁項集的挖掘，算法中關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)分解成兩個步驟：

1、查找所有大項集（一個大項目集是一組超過最小支持度的項目）。

2、從大項目集中生成關(guān)聯(lián)規(guī)則。

只有同時滿足最小支持度和最小置信度閾值的項目才會被關(guān)聯(lián)規(guī)則考慮。

四、提出的工作

現(xiàn)在有許多算法通過訪問路徑來生成頻繁訪問模式。但他們在執(zhí)行時間和內(nèi)存需求方面的效率較低。本文提出的算法是FP-樹算法的改進(jìn)版本，該算法不會使用遞歸來生成頻繁模式。它保持了數(shù)據(jù)庫的頻繁模式樹，這是一個擴(kuò)展的前綴樹結(jié)構(gòu)，其中存儲了頻繁模式關(guān)鍵的信息。該算法不同于FP-樹算法，它不使用遞歸。該算法在掃描一次數(shù)據(jù)庫的基礎(chǔ)上生成一個頁表，該表存儲了一些相關(guān)信息，有關(guān)用戶訪問網(wǎng)頁的次數(shù)和存儲該網(wǎng)頁模式樹的指針字段。頁表節(jié)點根據(jù)頁數(shù)進(jìn)行排序。樹節(jié)點就是頻繁項目。頁表節(jié)點用于生成頻繁訪問模式。從存儲樹節(jié)點的頁表seqptr開始，然后從底部到根節(jié)點來遍歷整個樹。在遍歷時，若滿足條件總頁數(shù)＞min_sup則將此節(jié)點添加到頻繁樹中。如果不滿足這個條件，則將其移到樹的下一個路徑中。最終，利用反向遍歷樹來為用戶生成所有的頻繁模式。

該算法分為兩步：

步驟1：根據(jù)來自用戶文件中的訪問路徑來構(gòu)建頻繁訪問模式樹，并記錄每個頁面的訪問次數(shù)。

該算法的第一步和FP樹算法一樣，但在第二步算法中采用向后遍歷來尋找頻繁訪問模式，因此，遍歷這些樹的執(zhí)行時間就會減少。

五、運算結(jié)果

該算法使用的是AMD處理器，主內(nèi)存256 MB，虛擬內(nèi)存756 MB，本地磁盤空間40 GB操作系統(tǒng)是微軟的Windows XP。該算法采用的是JAVA1.4.2實現(xiàn)的。

下圖顯示了比較結(jié)果。

比較1：Apriori算法和改進(jìn)算法時間結(jié)果比較

圖1 Apriori算法和改進(jìn)算法時間結(jié)果的比較

比較2：Apriori算法和改進(jìn)算法內(nèi)存使用情況的比較

圖2 Apriori算法和改進(jìn)算法內(nèi)存使用情況的比較

六、結(jié)論

本文基于Apriori算法的缺點，開發(fā)了一個改進(jìn)的版本，此算法是采用無候選集來生成頻繁模式的方法，不需要使用遞歸來生成頻繁模式，采用自上而下的方式，避免生成不必要的模式規(guī)則，從而大大減少了數(shù)據(jù)庫掃描的次數(shù)，以此來提高程序運行的時間和空間。

［1］岳鵬宇.Apriori算法的探討［J］.山西經(jīng)濟(jì)管理干部學(xué)院學(xué)報，2012（4）.

［2］丁一琦.基于Apriori算法的數(shù)據(jù)挖掘技術(shù)研究［J］.現(xiàn)代計算機，2012（36）.

［3］張琪.基于 Apriori算法的數(shù)據(jù)挖掘系統(tǒng)設(shè)計［J］.計算機光盤軟件與應(yīng)用，2013（15）.