宋小小 陳曉輝 劉沖

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

0 引言

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

1 Apriori算法

1.1 算法簡介

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

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

(1) 連接：(k-1)-頻繁項目集集合進行自連接運算，生成候選k-項目集集合。

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

1.2 算法分析

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

1.3 算法的基本原理

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

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

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

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

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

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

2 改進的Apriori算法

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

改進的Apriori算法思路如下：

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

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

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

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

改進的Apriori算法描述如下：

3 實驗與結(jié)果分析

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

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

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

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

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

表1 兩種算法在不同項集個數(shù)下的運行時間

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

4 結(jié)語

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

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

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

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

[4]曾萬聰,周緒波,戴勃等.關(guān)聯(lián)規(guī)則挖掘的矩陣其法[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]毛國君,段立娟,王實,石云.數(shù)據(jù)挖掘原理與方法.北京:清華大學(xué)出版社.2007.

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

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

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

[11]馬盈倉.挖掘關(guān)聯(lián)規(guī)則中 Apriori算法的改進.計算機應(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.