對Apriori算法的研究及改進

丁 麗，孫高峰

（1.亳州職業(yè)技術(shù)學(xué)院信息工程系，安徽 亳州 236800；2.安徽電力亳州供電公司電力調(diào)度控制中心，安徽 亳州 236800）

隨著信息技術(shù)的發(fā)展，數(shù)據(jù)庫中存放的信息越來越多，從大量的數(shù)據(jù)中提取有價值的信息變得越來越難，數(shù)據(jù)挖掘正是為了滿足這種需求應(yīng)運而生的。數(shù)據(jù)挖掘 （data mining），是從存放在數(shù)據(jù)倉庫、數(shù)據(jù)庫或其他信息庫中的大量數(shù)據(jù)中，尋找有價值信息的過程［1］。數(shù)據(jù)挖掘又稱為數(shù)據(jù)中的知識發(fā)現(xiàn)KDD，即從數(shù)據(jù)庫中發(fā)現(xiàn)隱藏的知識［2］。關(guān)聯(lián)是指兩個或多個變量值之間存在的相互聯(lián)系。關(guān)聯(lián)規(guī)則挖掘就是尋找給定的大量數(shù)據(jù)中項集之間存在的某種規(guī)律的過程。它是數(shù)據(jù)挖掘中的一個熱點，近幾年被廣泛研究和應(yīng)用［3］。關(guān)聯(lián)規(guī)則最重要的算法是Apriori算法。關(guān)聯(lián)規(guī)則的研究揭示了數(shù)據(jù)庫中事先不知道的、不同項的依賴關(guān)系。比如，通過對顧客所購買的商品進行分析，發(fā)現(xiàn)購買方便面的顧客很多也同時購買了火腿腸，可以考慮把方便面和火腿腸擺放在一起，可能會增加二者的銷售量。

1 關(guān)聯(lián)規(guī)則概述

1.1 關(guān)聯(lián)規(guī)則的基本概念

所謂關(guān)聯(lián)規(guī)則就是形如A＝＞B，表示若A成立則B成立。在進行關(guān)聯(lián)分析時需要計算規(guī)則A＝＞B的概率，其實質(zhì)是一個條件概率P（B︱A）。相關(guān)的概念有以下幾個：

1）項、項集

項是數(shù)據(jù)庫中不可分割的最小數(shù)據(jù)單位，一般用i表示。項的集合稱為項集，包含K個項的項集稱為K項集。設(shè)I＝｛i1，i2，…，im｝是項的集合。每個交易T（Transaction）是數(shù)據(jù)項的一個子集，T?I。與任務(wù)相關(guān)的交易的集合用D表示，對于每一條交易記錄記為TID［4］。

2）關(guān)聯(lián)規(guī)則

設(shè)A是一個項集，當(dāng)且僅當(dāng)A?T。關(guān)聯(lián)規(guī)則是具有A＝＞B的蘊涵式，其中A?I，B?I，且A∩B＝φ［5］。

3）支持度

支持度用于描述規(guī)則的有用性。如果D中有%S的交易記錄包含A∪B，則記關(guān)聯(lián)規(guī)則A＝＞B的支持度為 %S［6］。即support（A＝＞B）＝ %S＝P（A∪B），最小支持度記為min＿sup。

4）置信度

置信度用于描述規(guī)則的確定性。如果D中包含A的交易記錄中，有%C也包含B，則記關(guān)聯(lián)規(guī)則A＝＞B的支持度為%C。即confidence（A＝＞B）＝%C＝P（B｜A），最小置信度記為min＿conf。

同時滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則稱為強關(guān)聯(lián)規(guī)則。

5）頻繁項集

如果項集A的支持度不小于設(shè)定的最小支持度，即support（A）≥min＿sup［7］，則稱項集A為頻繁項集。頻繁1－項集的集合記為L1，頻繁K-項集的集合記為Lk。

1.2 關(guān)聯(lián)規(guī)則應(yīng)用實例

例如：設(shè)I＝｛A，B，C，D，E｝，某超市數(shù)據(jù)庫中有一組如表1所示的銷售記錄。表中有8次交易記錄，每次交易都記錄了一起購買的商品代碼。

表1 商品銷售數(shù)據(jù)

表2 L1和支持度計數(shù)

表3 L2和支持度計數(shù)

表4 L3和支持度計數(shù)

假設(shè)關(guān)聯(lián)規(guī)則的支持度計數(shù)至少為2，即最小支持度為2／8＝25%，則將符合條件的項集和支持度計數(shù)列出，如表2，3，4所示。

由項集 ｛A，B，C｝，可以得到如表5所示的關(guān)聯(lián)規(guī)則。

若最小置信度為60% ，則｛A，C｝＝＞ ｛B｝為強規(guī)則。

若最小置信度為50%，則｛B，C｝＝＞｛A｝也是強規(guī)則。

表5 關(guān)聯(lián)規(guī)則和置信度

2 Apriori算法

2.1 Apriori算法思想

Apriori算法是關(guān)聯(lián)規(guī)則中最重要的一種挖掘頻繁項集的算法，它是由R.Agrawal和R.Srikant于1994年提出的［8］。它使用層次迭代的搜索方法，由k-項集尋找（k＋1）-項集，被公認(rèn)為最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法。首先，掃描數(shù)據(jù)庫，統(tǒng)計出只有一個元素的項集出現(xiàn)的支持度計數(shù)（或稱為頻數(shù)），得出候選1－項集C1，再根據(jù)設(shè)定的最小支持度計數(shù)，把不滿足最小支持度計數(shù)的項集刪掉，得到頻繁1－項集L1。然后，由L1統(tǒng)計出包含兩個元素的項集，得出候選2－項集C2，掃描數(shù)據(jù)庫，統(tǒng)計C2中每個項集的計數(shù)，選擇滿足最小支持度的項集，得到頻繁2－項集L2。接著由L2尋找候選3－項集C3，再由C3得出頻繁3－項集L3。重復(fù)這個過程，直到找不到頻繁K項集LK為止。其過程可以形如：C1→L1→C2→L2→C3→L3→……尋找每個LK都要掃描數(shù)據(jù)庫一次，數(shù)據(jù)庫的大小直接影響Apriori算法的運算速度。Apriori性質(zhì)：頻繁項集的所有非空子集都必須是頻繁的［9］。如果項集I不滿足最小支持度，則I不是頻繁的，如果項A添加到I，則1UA也不是頻繁的。也就是說，非頻繁項集的超集都是非頻繁項集。

Apriori性質(zhì)可以用于壓縮搜索空間，因此可以提高頻繁項集挖掘的效率。根據(jù)Apriori性質(zhì)，由LK－1尋找Lk（k≥2）的過程分為以下兩步：

（1）連接。將Lk－1與自身連接產(chǎn)生候選K-項集Ck

（2）剪枝。首先，如果Ck的（k-1）項子集不在Lk－1中，則該候選項是非頻繁的，把它從Ck中刪除。然后，結(jié)合最小支持度產(chǎn)生Lk。

2.2 Apriori算法的不足

Apriori算法雖然對候選集的大小進行了壓縮，能夠比較有效地產(chǎn)生頻繁項目集，但在效率上卻存在著一定的不足，主要表現(xiàn)為：

（1）數(shù)據(jù)庫重復(fù)掃描的次數(shù)太多。在由CK尋找LK的過程中，CK中的每一項都需要掃描事務(wù)數(shù)據(jù)庫進行驗證，以決定其是否加入Lk，存在的頻繁K-項集越大，重復(fù)掃描的次數(shù)就越多。這一過程耗時太大，增加了系統(tǒng)1／0開銷，處理效率低［10］，不利于實際應(yīng)用。

（2）產(chǎn)生的候選集可能過于龐大。如果一個頻繁1-項集包含100個項，那么頻繁2-項集就有C2100個，為找到元素個數(shù)為100的頻繁項集，如｛b1，b2，…，b100｝，那么就要掃描數(shù)據(jù)庫100次，產(chǎn)生的候選項集總個數(shù)為：

對于一個這樣龐大的項集，計算機難以存儲和計算，挖掘效率低下。

3 改進的Apriori算法

為了減少數(shù)據(jù)庫的掃描次數(shù)、支持度計數(shù)的統(tǒng)計量以及大量無用候選項的產(chǎn)生所帶來的弊端，提高挖掘的效率，在經(jīng)典的Apriori算法的基礎(chǔ)上提出了改進的Apriori算法。

與國外的機構(gòu)庫建設(shè)的高速發(fā)展相比，我國目前還處于起步階段。吳建中[3]2004年初發(fā)表文章探討了機構(gòu)庫對圖書館整體管理模式的沖擊，將知識庫的概念引入我國。2005年7月，北京大學(xué)圖書館率領(lǐng)國內(nèi)50多所高等院校圖書館聯(lián)合發(fā)表《圖書館合作與信息資源共享武漢宣言》，在宣言中明確指出我國高校圖書館應(yīng)“建設(shè)特色館藏，開展特色服務(wù)，建立一批特色學(xué)術(shù)機構(gòu)庫（Institutional Depository）”[4]。從那之后，機構(gòu)知識庫的建設(shè)在國內(nèi)，特別是我國高校圖書館逐步開啟[5]。

3.1 改進的Apriori算法分析

1）理論基礎(chǔ)：Apriori性質(zhì)及其推論。

性質(zhì)1：頻繁項集的所有非空子集都必須是頻繁的。（Apriori性質(zhì)，記為性質(zhì)1）

性質(zhì)2：若頻繁K-項集Lk中各個項可以做鏈接產(chǎn)生Lk＋1，則Lk中每個元素在Lk中出現(xiàn)的次數(shù)應(yīng)大于或等于K，若小于K，則刪除該項在Lk中所有的事務(wù)集［11］。（Apriori性質(zhì)的推論，記為性質(zhì)2）

2）具體實現(xiàn)原理

首先把事務(wù)數(shù)據(jù)庫D轉(zhuǎn)化成布爾表，然后轉(zhuǎn)置［12］。轉(zhuǎn)置后的布爾表格中，列表示事務(wù)，行表示項集。用邏輯值1和0表示每一個項在每一個事務(wù)中的存在與否，1表示存在，0表示不存在。通過對此布爾表進行挖掘運算實現(xiàn)對事務(wù)數(shù)據(jù)庫D的挖掘。

3.2 改進的Apriori算法挖掘步驟

1）首先，把事務(wù)數(shù)據(jù)庫表轉(zhuǎn)化成布爾表，轉(zhuǎn)置，掃描轉(zhuǎn)置后的布爾表，記錄每行1的個數(shù)，并存儲在列的最右側(cè)，每行中1的個數(shù)即為該項的支持度計數(shù)，得出候選1－項集C1的集合。再把C1中支持度計數(shù)小于最小支持度計數(shù)的項所在的行刪除，得到簡化的事務(wù)數(shù)據(jù)布爾表D1和頻繁1－項集L1。

2）鏈接L1，產(chǎn)生頻繁2－項集L2。不需要掃描原數(shù)據(jù)庫，只要掃描D1即可。將D1中每兩行按位作邏輯與運算，結(jié)果用邏輯值1和0表示，得到2－候選項集的集合C2，然后掃描計數(shù)，得出2－項集的支持度計數(shù)，刪除支持度計數(shù)小于最小支持度計數(shù)的項，得到D2’和L2’。計算各項在L2’中出現(xiàn)的次數(shù)。（要求各項在Lk中出現(xiàn)的次數(shù)大于或等于K，若小于K，則刪除該項在Lk中所有的事務(wù)集。）刪除出現(xiàn)次數(shù)小于2的項集，得到再次簡化的事務(wù)數(shù)據(jù)庫布爾表D2和L2。

3）當(dāng)K≥3時，重復(fù)2），直到找到最大頻繁項集為止。

此方法不需要重復(fù)掃描數(shù)據(jù)庫，支持度計數(shù)的統(tǒng)計也比較容易，也不會產(chǎn)生過多的冗余，因此，可以在很大程度上降低挖掘的復(fù)雜度，提高挖掘算法的效率。

3.3 改進的Apriori算法描述

3.4 改進的Apriori算法舉例

現(xiàn)有一事務(wù)數(shù)據(jù)庫表D，如表6所示。設(shè)定最小支持度計數(shù)為3。

表6 事務(wù)數(shù)據(jù)庫表D

表7 布爾表DT

下面是改進的Apriori算法的運行過程。（1）首先將數(shù)據(jù)庫表D轉(zhuǎn)換成布爾表DT，如表7所示。

對表7轉(zhuǎn)置，然后掃描，并記錄各個項支持度的個數(shù)，得到候選1-項集C1，如表8所示。

表8 候選1-項集C1

表9 數(shù)據(jù)庫表D1

表10 頻繁1-項集L1

將C1中不滿足最小支持度計數(shù)的項｛B｝、｛D｝、｛G｝、｛H｝所在的行刪除，得到精簡的數(shù)據(jù)庫表D1和頻繁1－項集L1，如表9、10所示。

（2）對表D1，每兩行求交集，并掃描計數(shù)，得到2－候選項集的集合C2’，如表11所示。

表11 C2’

圖1 C2、L2’

將C2’中支持度計數(shù)小于最小支持度計數(shù)的項｛AE｝、｛AF｝所在的行刪除，得到C2和L2’，計算各項在L2’中出現(xiàn)的次數(shù)，如圖1所示。

由于A在L2’中出現(xiàn)的次數(shù)小于2，所以應(yīng)將C2中含A的項，即｛AC｝所在的行刪除，得到精簡的數(shù)據(jù)庫表D2和頻繁2－項集L2，如表12、13所示。

表12 數(shù)據(jù)庫表D2

表13 頻繁2－項集L2

（3）掃描D2，對D2中每兩行求交，得到精簡的數(shù)據(jù)庫表D3和頻繁3－項集L3，如表14、15所示。

表14 數(shù)據(jù)庫表D3

表15 頻繁3－項集L3

從以上過程可以看出，改進的算法在計算支持度個數(shù)時，每次不需要掃描全部數(shù)據(jù)庫，只需要在精簡的數(shù)據(jù)庫表中掃描各項所在的行就可，大大節(jié)省了時間；另外，改進的算法在由頻繁K-項集生成頻繁（k＋1）-項集時，對Lk中元素的個數(shù)進行計數(shù)處理，根據(jù)計數(shù)結(jié)果刪除了出現(xiàn)次數(shù)小于K的元素，減少了組合的個數(shù)，從而減少了循環(huán)判斷的次數(shù)，提高了運算效率。

4 兩種算法的性能比較

為了證實改進的Apriori算法的性能，對改進的Apriori算法和經(jīng)典Apriori算法的效率進行對比。實驗數(shù)據(jù)來源于亳州職業(yè)技術(shù)學(xué)院圖書館數(shù)據(jù)庫，實驗硬件環(huán)境CPU為AMD Athlon（速龍）II X2 245雙核，內(nèi)存為4GDDR2 800MHz；操作系統(tǒng)是Windows XP，數(shù)據(jù)庫為Microsoft SQL Server 2000，編輯語言為Visual c＃。性能對比曲線如圖2所示。

從圖2中可以看出改進的Apriori算法性能優(yōu)于經(jīng)典的Apriori算法，尤其在交易事務(wù)條數(shù)比較多的情況下，效果更加明顯。

5 結(jié)束語

本文通過對經(jīng)典Apriori進行分析研究，找出其不足之處，然后針對其不足之處提出了相應(yīng)的改進，并給出了具體的運算實例。

圖2 算法性能比較

［1］毛國軍.數(shù)據(jù)挖掘原理與算法（第二版）［M］.北京：清華大學(xué)出版社，2007：10-12.

［2］趙志升，羅德林，李海英.數(shù)據(jù)挖掘技術(shù)與應(yīng)用［J］.河北北方學(xué)院學(xué)報：自然科學(xué)版，2006，22（06）：63-66.

［3］崔學(xué)文.關(guān)聯(lián)規(guī)則挖掘算法Apriori在學(xué)生成績分析中的應(yīng)用［J］.河北北方學(xué)院學(xué)報：自然科學(xué)版，2011，27（01）：44-47.

［4］王新.不完全數(shù)據(jù)庫中關(guān)聯(lián)規(guī)則的兩種求估方法［J］.計算機應(yīng)用.2004，24（08）：63.

［5］Han J W，Kamber M，范明，等.數(shù)據(jù)挖掘概念與技術(shù)［M］.北京：機械工業(yè)出版社，2007：153-155.

［6］譚建豪，等.數(shù)據(jù)挖掘技術(shù)［M］.北京：水利水電出版社，2009：83-86.

［7］周艷山.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究及應(yīng)用［D］.哈爾濱：哈爾濱理工大學(xué)，2005.

［8］蔣盛益，李霞，鄭琪.數(shù)據(jù)挖掘原理與實踐［M］.北京：電子工業(yè)出版社，2011：8-11.

［9］黃明，魏靜波，牛娃.對 Apriori算法的進一步改進［J］.大連鐵道學(xué)院學(xué)報，2006，24（04）：47-49.

［10］彭儀普，熊擁軍.關(guān)聯(lián)規(guī)則挖掘 AprioriTid算法優(yōu)化研究［J］.計算機工程，2006，（05）：20-25.

［11］葉福蘭，施忠興.Apriori算法的改進及應(yīng)用［J］.現(xiàn)代計算機，2009（09）：96-97.

［12］劉耀南.Apriori算法的分析及應(yīng)用［J］.佛山科學(xué)技術(shù)學(xué)院學(xué)報：自然科學(xué)版，2012，30（03）：70-74.

［13］邵渝濱.利用關(guān)聯(lián)規(guī)則增量式更新算法挖掘Web日志［D］.重慶：重慶大學(xué)，2003.