關(guān)聯(lián)規(guī)則中Apriori算法的研究與改進(jìn)

宋小小 陳曉輝 劉沖

桂林理工大學(xué) 廣西 541004

0 引言

數(shù)據(jù)挖掘是一門新興起的交叉學(xué)科，主要研究事務(wù)數(shù)據(jù)庫(kù)、關(guān)系數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng)之間潛在有用的新穎的規(guī)律。它的主要方法包括：分類、關(guān)聯(lián)規(guī)則、聚類、特征、回歸分析、變化和偏差分析等。關(guān)聯(lián)規(guī)則挖掘就是從海量的數(shù)據(jù)中尋找數(shù)據(jù)項(xiàng)間的關(guān)聯(lián)關(guān)系，它是數(shù)據(jù)挖掘領(lǐng)域中研究的熱點(diǎn)問(wèn)題。關(guān)聯(lián)規(guī)則表示數(shù)據(jù)庫(kù)中一組對(duì)象之間具有某種關(guān)聯(lián)關(guān)系的規(guī)則，其主要挖掘?qū)ο笫鞘聞?wù)數(shù)據(jù)庫(kù)。這種數(shù)據(jù)庫(kù)大量的應(yīng)用在零售業(yè)，而條形碼技術(shù)的發(fā)展使得數(shù)據(jù)的收集變得更加方便、更加完整。關(guān)聯(lián)規(guī)則就是在這些交易項(xiàng)目中去尋找某種關(guān)聯(lián)關(guān)系。1993年，Agrawal等人首先提出了挖掘顧客交易項(xiàng)目中項(xiàng)集間的關(guān)聯(lián)規(guī)則問(wèn)題，此后諸多的研究人員對(duì)關(guān)聯(lián)規(guī)則挖掘問(wèn)題進(jìn)行了大量的研究與改進(jìn)。

1 Apriori算法

1.1 算法簡(jiǎn)介

Apriori算法是1993年由Agrawal等人提出的一個(gè)經(jīng)典的挖掘關(guān)聯(lián)規(guī)則算法，它通過(guò)對(duì)事務(wù)數(shù)據(jù)庫(kù)的多趟掃描來(lái)發(fā)現(xiàn)所有的頻繁項(xiàng)目集。

該算法采用“逐層搜索”的迭代方法，利用向下封閉特性，由 k-頻繁項(xiàng)目集生成(k+1)-頻繁項(xiàng)目集。第一趟掃描數(shù)據(jù)庫(kù)計(jì)算出 1-頻繁項(xiàng)目集集合(記為：L1)；接著，反復(fù)行下面的兩個(gè)步驟計(jì)算k-頻繁項(xiàng)目集，直到生成k-頻繁項(xiàng)目集的集合(記為：Lk)為空：

(1) 連接：(k-1)-頻繁項(xiàng)目集集合進(jìn)行自連接運(yùn)算，生成候選k-項(xiàng)目集集合。

(2) 剪枝：上一步生成的候選k-項(xiàng)目集集合是k-頻繁項(xiàng)目集集合的超集。通過(guò)掃描數(shù)據(jù)庫(kù)計(jì)算候選k-項(xiàng)目集集合中每個(gè)候選項(xiàng)目集的支持度，并與給定的最小支持度進(jìn)行比較，較大的就是k-頻繁項(xiàng)目集。

1.2 算法分析

經(jīng)典的Apriori挖掘算法在執(zhí)行“連接，剪枝”步驟中，需要多次掃描數(shù)據(jù)庫(kù)并生成大量的候選項(xiàng)目集。當(dāng)數(shù)據(jù)庫(kù)太大或者挖掘?qū)哟翁顣r(shí), 算法耗時(shí)太多甚至無(wú)法完成。在剪枝步，由大量的候選項(xiàng)目集而造成的頻繁模式匹配問(wèn)題，這些都嚴(yán)重影響了Apriori 算法的效率。

1.3 算法的基本原理

性質(zhì)1 K項(xiàng)數(shù)據(jù)項(xiàng)目集是頻繁項(xiàng)目集的必要條件是它的所有k-1項(xiàng)子集均是頻繁項(xiàng)目集。

性質(zhì)2 K頻繁項(xiàng)目集的所有K-1維非空子集均是頻繁項(xiàng)目集。

定理1 若K維數(shù)據(jù)項(xiàng)目集X = { i1, i2，…，ik}中，存在一個(gè)j∈X，使得|Lk-1(j)| ＜ k-1，則X不是頻繁項(xiàng)目集。

其中，|Lk-1(j)|表示(K-1)維頻繁項(xiàng)目集的集合 Lk-1中包含j的個(gè)數(shù)。

證明 假設(shè)X是K維頻繁項(xiàng)目集，根據(jù)性質(zhì)1，X的k個(gè)(k-1)項(xiàng)目子集都在Lk-1中，其中每一個(gè)項(xiàng)目p∈L均出現(xiàn)k-1次，故?p∈L，均有| Lk-1(p)|≥k-1，這與條件矛盾，故X不是頻繁項(xiàng)目集。

推論1 如果k-1維頻繁項(xiàng)集集合Lk-1中包含單個(gè)項(xiàng)目i的個(gè)數(shù)小于k-1，則i不可能包含在頻繁k-項(xiàng)集中。

2 改進(jìn)的Apriori算法

Apriori算法中對(duì)數(shù)據(jù)庫(kù)的處理，目前普遍采用的是水平數(shù)據(jù)庫(kù)結(jié)構(gòu)。本文借鑒文獻(xiàn)的思想，將水平結(jié)構(gòu)變換為垂直對(duì)應(yīng)關(guān)系。經(jīng)過(guò)這樣變換，很容易計(jì)算1-項(xiàng)目集的支持度，同時(shí)很容易計(jì)算候選項(xiàng)目集的支持度，并且只在計(jì)算1-項(xiàng)目集時(shí)需要對(duì)整個(gè)數(shù)據(jù)庫(kù)進(jìn)行訪問(wèn)。

改進(jìn)的Apriori算法思路如下：

(1) 首先掃描整個(gè)數(shù)據(jù)庫(kù)，記錄支持每個(gè)項(xiàng)目的事務(wù)ID號(hào)。經(jīng)過(guò)統(tǒng)計(jì)后，計(jì)算出每個(gè)項(xiàng)目的支持度，并與最小支持度進(jìn)行比較，進(jìn)而得出1-項(xiàng)目集。

(2) 由1-項(xiàng)目集中的項(xiàng)目進(jìn)行兩兩連接，生成候選2-項(xiàng)目集。然后計(jì)算候選 2-項(xiàng)目集中每個(gè)項(xiàng)目集的事務(wù)計(jì)數(shù)(事務(wù)計(jì)數(shù)等于項(xiàng)目集中的每個(gè)項(xiàng)目事務(wù)的交集)，與最小支持事務(wù)數(shù)進(jìn)行比較，進(jìn)而得出2-項(xiàng)目集。

(3) 以此類推，生成候選k-項(xiàng)目集。根據(jù)定理1和推論1，刪除候選k-項(xiàng)目集中不可能為k-項(xiàng)目集的項(xiàng)目，然后計(jì)算候選k-項(xiàng)目集中每個(gè)項(xiàng)目集的事務(wù)計(jì)數(shù)，與最小支持事務(wù)數(shù)進(jìn)行比較，進(jìn)而得出k-項(xiàng)目集。

(4) 重復(fù)步驟3，直到生成K頻繁項(xiàng)目集的集合為空。

改進(jìn)的Apriori算法描述如下：

3 實(shí)驗(yàn)與結(jié)果分析

與經(jīng)典的Apriori挖掘算法相比, 改進(jìn)后的挖掘算法有如下優(yōu)點(diǎn)：

(1) 算法只在計(jì)算頻繁1-項(xiàng)目集時(shí)需要對(duì)整個(gè)數(shù)據(jù)庫(kù)進(jìn)行訪問(wèn)，在計(jì)算候選k項(xiàng)目集的支持度時(shí)，僅需要數(shù)據(jù)庫(kù)中頻繁k-1項(xiàng)集信息。而隨著k的增大，頻繁項(xiàng)目集的數(shù)目不斷減少。

(2) 算法采用垂直對(duì)應(yīng)數(shù)據(jù)庫(kù)結(jié)構(gòu)，通過(guò)該數(shù)據(jù)庫(kù)結(jié)構(gòu)很容易計(jì)算候選項(xiàng)目集的支持度。

(3) 算法在生成一個(gè)候選項(xiàng)目集后就計(jì)算其頻繁度，避免了模式匹配，減少內(nèi)存的使用。

為了進(jìn)一步驗(yàn)證算法的有效性，實(shí)驗(yàn)在內(nèi)存為512MB，CUP主頻為1.7GHZ，操作系統(tǒng)為Windows XP2的環(huán)境下進(jìn)行，并用VC++ 6.0分別實(shí)現(xiàn)了經(jīng)典Apriori算法和本改進(jìn)算法。數(shù)據(jù)由筆者隨機(jī)生成，有2800個(gè)數(shù)據(jù)，90個(gè)項(xiàng)集，最小支持度為15%，實(shí)驗(yàn)結(jié)果如表1所示。

表1 兩種算法在不同項(xiàng)集個(gè)數(shù)下的運(yùn)行時(shí)間

從表中可以看出，經(jīng)過(guò)改進(jìn)的Apriori算法在執(zhí)行速度上有了較大的提高。

4 結(jié)語(yǔ)

本文通過(guò)深入分析經(jīng)典Aprior算法的優(yōu)缺點(diǎn)，在此基礎(chǔ)上提出了改進(jìn)的Apriori關(guān)聯(lián)規(guī)則挖掘算法，并給出了詳細(xì)的算法描述。經(jīng)實(shí)驗(yàn)證明，改進(jìn)的Apriori算法比經(jīng)典的Apriori算法有著更好的頻繁項(xiàng)集的提取速率。

[1]陳應(yīng)霞,陳艷.關(guān)聯(lián)規(guī)則中的 Apriori挖掘算法改進(jìn)[J].長(zhǎng)江大學(xué)學(xué)報(bào)(自然科學(xué)版).2008.

[2]徐章艷,劉美玲,張師超等.Apriori算法的三種優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用.2004.

[3]李云峰,陳建文,程代杰,關(guān)聯(lián)規(guī)則挖掘的研究及對(duì) Apriori算法的改進(jìn)[J].計(jì)算機(jī)工程與科學(xué).2002.

[4]曾萬(wàn)聰,周緒波,戴勃等.關(guān)聯(lián)規(guī)則挖掘的矩陣其法[J].計(jì)算機(jī)工程.2006.

[5]Agrawl R, Shafer J.Parallel Minging of Association Rules:Design，Implementation，and Experience[P].USA: CA95120.1996.

[6]K1einberg J，Papadimitriou C，Raghavan P.Segmentation Problems [A] Proceedings of the 30th Annual Symposiumon the Theory of Computing [C].New York: ACM Press.1998.

[7]毛國(guó)君,段立娟,王實(shí),石云.數(shù)據(jù)挖掘原理與方法.北京:清華大學(xué)出版社.2007.

[8]劉君強(qiáng),孫曉瑩,潘云鶴.關(guān)聯(lián)規(guī)則挖掘技術(shù)研究的新進(jìn)展[J].計(jì)算機(jī)科學(xué).2004.

[9]王偉勤,鄭海.Apriori算法的進(jìn)一步改進(jìn)[J].計(jì)算機(jī)與數(shù)字工程.2009.

[10]楊啟昉,馬廣平.關(guān)聯(lián)規(guī)則挖掘Apriori算法的改進(jìn).計(jì)算機(jī)應(yīng)用[J].2008.

[11]馬盈倉(cāng).挖掘關(guān)聯(lián)規(guī)則中 Apriori算法的改進(jìn).計(jì)算機(jī)應(yīng)用與軟件[J].2004.

[12]Brin S，Motw ani R，Silverstein C.Beyond Market Baskets：Generlizin g Association Rules to Correlations [A].Proceedings of the ACM SIGMOD [C] New Yor k: ACM Press.1996.