丁 麗，孫高峰

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

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

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

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

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

1）項(xiàng)、項(xiàng)集

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

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

設(shè)A是一個(gè)項(xiàng)集，當(dāng)且僅當(dāng)A?T。關(guān)聯(lián)規(guī)則是具有A＝＞B的蘊(yùn)涵式，其中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。

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

5）頻繁項(xiàng)集

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

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

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

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

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

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

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

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

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

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

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

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

2 Apriori算法

2.1 Apriori算法思想

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

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

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

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

2.2 Apriori算法的不足

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

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

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

對(duì)于一個(gè)這樣龐大的項(xiàng)集，計(jì)算機(jī)難以存儲(chǔ)和計(jì)算，挖掘效率低下。

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

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

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

3.1 改進(jìn)的Apriori算法分析

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

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

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

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

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

3.2 改進(jìn)的Apriori算法挖掘步驟

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

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

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

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

3.3 改進(jìn)的Apriori算法描述

3.4 改進(jìn)的Apriori算法舉例

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

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

表7 布爾表DT

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

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

表8 候選1-項(xiàng)集C1

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

表10 頻繁1-項(xiàng)集L1

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

（2）對(duì)表D1，每?jī)尚星蠼患?，并掃描?jì)數(shù)，得到2－候選項(xiàng)集的集合C2’，如表11所示。

表11 C2’

圖1 C2、L2’

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

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

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

表13 頻繁2－項(xiàng)集L2

（3）掃描D2，對(duì)D2中每?jī)尚星蠼唬玫骄?jiǎn)的數(shù)據(jù)庫(kù)表D3和頻繁3－項(xiàng)集L3，如表14、15所示。

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

表15 頻繁3－項(xiàng)集L3

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

4 兩種算法的性能比較

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

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

5 結(jié)束語(yǔ)

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

圖2 算法性能比較

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

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

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

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

［5］Han J W，Kamber M，范明，等.數(shù)據(jù)挖掘概念與技術(shù)［M］.北京：機(jī)械工業(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ù)挖掘原理與實(shí)踐［M］.北京：電子工業(yè)出版社，2011：8-11.

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

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

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

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

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