李婷　張繼周

【摘 要】Apriori算法是挖掘頻繁項(xiàng)集的一種重要方法，但是如果事務(wù)數(shù)據(jù)庫大到難以一次裝入內(nèi)存就會遇到瓶頸。本文給出一種基于分區(qū)技術(shù)的改進(jìn)算法，通過將大的事務(wù)數(shù)據(jù)庫劃分為小的分區(qū)來實(shí)現(xiàn)頻繁項(xiàng)集的挖掘。

【關(guān)鍵詞】關(guān)聯(lián)規(guī)則；Apriori算法；頻繁項(xiàng)集；分區(qū)技術(shù)

【Abstract】Apriori algorithm is an important ways on mining frequent itemsets， but the situation is difficult to handle if the transaction database is very huge. An improving algorithm based on partitioning is given， and the frequent itemsets are obtained by dividing the huge database into small ones.

【Key words】Association rules； Apriori algorithm； Frequent item sets； Partition technique

0 引言

挖掘頻繁模式是數(shù)據(jù)挖掘中的一個重要內(nèi)容，它是研究如何可以找到頻繁出現(xiàn)在數(shù)據(jù)集中的模式。它對于挖掘數(shù)據(jù)之間的相關(guān)和關(guān)聯(lián)性以及發(fā)現(xiàn)頻繁模式起著非常重要的作用。因此，頻繁模式的挖掘成為了數(shù)據(jù)挖掘任務(wù)和數(shù)據(jù)挖掘研究關(guān)注的重要主題之一[1]。

1 基本概念

（1）項(xiàng)集：由若干個項(xiàng)組成的集合，設(shè)I={I1，I2，…，Im}，I是一個項(xiàng)集。

（2）k項(xiàng)集：項(xiàng)集中的元素如果有k個，就稱這個項(xiàng)集為k項(xiàng)集。

（3）關(guān)聯(lián)規(guī)則：設(shè)A和B為兩個項(xiàng)集，A？奐I，B？奐I且A∩B=Φ，則有關(guān)聯(lián)規(guī)則R：A=>B。

（4）支持度（相對支持度）：D中事務(wù)包含A∪B的百分比，也就是概率P（A∪B）。

（5）置信度：D中事務(wù)即包含A同時也包含B的百分比，也就是條件概率P（B|A）。

（6）支持度計數(shù)（絕對支持度）：包含項(xiàng)集的事務(wù)數(shù)。

（7）強(qiáng)關(guān)聯(lián)規(guī)則：滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則[2]。

（8）關(guān)聯(lián)規(guī)則的產(chǎn)生步驟：首先找出所有的頻繁項(xiàng)集，然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。

2 頻繁項(xiàng)集挖掘的Apriori算法

關(guān)聯(lián)規(guī)則產(chǎn)生的一個步驟就是要找出所有的頻繁項(xiàng)集，而這一步是挖掘過程中最重要的，它的開銷遠(yuǎn)遠(yuǎn)大于第二個步驟，因此它的性能的好壞就決定了整體挖掘性能的好壞。Apriori算法是為挖掘布爾類型關(guān)聯(lián)規(guī)則頻集的原創(chuàng)性算法。它是一種逐層搜索的迭代方法，其中k項(xiàng)集用于探索（k+1）項(xiàng)集。首先，通過掃描數(shù)據(jù)庫，找出事務(wù)中包含的所有項(xiàng)，同時對每一項(xiàng)進(jìn)行計數(shù)，得到候選1項(xiàng)集（C1），用每個計數(shù)和最小支持度計數(shù)進(jìn)行比較，得到頻繁1項(xiàng)集（L1）。然后，使用L1通過自身的連接產(chǎn)生C2，通過對C2計數(shù)找出集合L2。再使用相同的方法找出L3，依次如此做下去，直到不能再找到頻繁k項(xiàng)集。

為了提高頻集逐層產(chǎn)生的效率，可以使用先驗(yàn)性質(zhì)來壓縮搜索空間。

先驗(yàn)性質(zhì)：頻繁項(xiàng)集的所有非空子集也一定是頻繁的。

證明：令S是一個頻集，min_sup是最小支持度，D為事務(wù)數(shù)據(jù)庫的集合，|D|為D中的事務(wù)數(shù)，則support_count（S）=min_supX|D|。令S為S的任意一個非空子集，則任何包含項(xiàng)集S的事務(wù)必然會包含項(xiàng)集S。因此，support_count（S）support_count（S）=min_supX|D|，故S也是一個頻集。

因此在生成候選k-項(xiàng)集之前，可以使用上述性質(zhì)來進(jìn)行剪枝，這樣可以減去大量的k-項(xiàng)集，從而大大壓縮了候選k-項(xiàng)集。

3 基于分區(qū)的算法改進(jìn)

事務(wù)數(shù)據(jù)庫有時候會很大而無法一次全部裝入內(nèi)存，此時可以進(jìn)行事務(wù)數(shù)據(jù)庫的劃分。分區(qū)的大小和分區(qū)的數(shù)目要使得每個分區(qū)都能夠放入內(nèi)存。過程如圖所示：

首先，把D中的事務(wù)劃分成n個非重疊的分區(qū)，如果D中事務(wù)的最小相對支持度閾值為min_sup，則每個分區(qū)的最小支持度計數(shù)為min_supX該分區(qū)的事務(wù)數(shù)。對于每個分區(qū)，掃描數(shù)據(jù)庫，找出所有的局部頻繁項(xiàng)集[3]。局部頻集可能是也可能不是整個數(shù)據(jù)庫D的頻集。然而，D的任何頻集必須作為局部頻集至少出現(xiàn)在一個分區(qū)中，證明如下：

證明：反證法。假設(shè)頻集在D的任何一個分區(qū)都不頻繁。令F為任意一個頻集，D為事務(wù)數(shù)據(jù)庫集合，C為D中的事務(wù)總數(shù)，A為D中包含F(xiàn)的事務(wù)總數(shù)，min_sup為最小支持度。因?yàn)镕是一個頻集，所以A=CXmin_sup。將D分成n個不重疊的分區(qū)：d1，d2，d3，…，dn，令C1，C2，C3，…，Cn為分區(qū)d1，d2，d3，…，dn各自對應(yīng)的事務(wù)數(shù)，則C=C1+C2+C3+…+Cn。令a1，a2，a3，…，an為分區(qū)d1，d2，d3，…，dn中包含F(xiàn)的事務(wù)數(shù)，則A=a1+a2+a3+…+an。因此A=a1+a2+a3+…+an=（C1+C2+C3+…+Cn）Xmin_sup。因?yàn)榍懊嬉呀?jīng)假設(shè)F在D中任意一個分區(qū)d1，d2，d3，…，dn中都不頻繁，則a1

因此，所有局部頻集都是D的候選項(xiàng)集，來自所有分區(qū)的局部頻集作為D的全局候選項(xiàng)集。然后，第二次掃描數(shù)據(jù)庫D，評估每個候選的實(shí)際支持度，以確定全局頻繁項(xiàng)集。它的優(yōu)化算法步驟為：（1）把數(shù)據(jù)庫劃分成一些模塊大小相當(dāng)?shù)膲K，記為N塊；（2）在每一塊內(nèi)產(chǎn)生一組自己的頻繁項(xiàng)集；記為Li；（3）最后合并這些項(xiàng)集生成一個全局候選的頻繁項(xiàng)集；（4）在數(shù)據(jù)庫內(nèi)，計算全局候選的頻繁項(xiàng)集的支持度，得到確定的最終的頻繁項(xiàng)集。

4 結(jié)語

通過上述對基于劃分?jǐn)?shù)據(jù)庫的Apriori算法的描述，可以清楚的知道改進(jìn)算法與原始的算法思想的異同，也完整體現(xiàn)了改進(jìn)算法的解題思路和所在優(yōu)勢，它把一個大而復(fù)雜的數(shù)據(jù)庫劃分成許多小的結(jié)構(gòu)簡單的數(shù)據(jù)庫，大大減小了因?yàn)楹蜻x集呈指數(shù)增長的問題，減少了候選集的構(gòu)造，縮短了時間；減少了不必要候選集生成的個數(shù)，節(jié)省了內(nèi)存空間，提高了算法的效率。

【參考文獻(xiàn)】

[1]Jiawei Han，Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].2版.范明，孟小鋒，譯.北京：機(jī)械工業(yè)出版社，2010.

[2]王麗珍，周麗華，陳紅梅，等.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘原理及應(yīng)用[M].北京：科學(xué)出版社，2005.

[3]王榮福，余麗娜，等.基于劃分技術(shù)對Apriori算法的改進(jìn)[J].科技創(chuàng)新導(dǎo)報，2008（12）.

[責(zé)任編輯：湯靜]