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

李晉芳

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

一、引言

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

二、相關(guān)工作

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

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

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

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

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

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

1、查找所有大項(xiàng)集（一個(gè)大項(xiàng)目集是一組超過(guò)最小支持度的項(xiàng)目）。

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

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

四、提出的工作

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

該算法分為兩步：

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

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

五、運(yùn)算結(jié)果

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

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

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

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

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

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

六、結(jié)論

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

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

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

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