王宇一

（江蘇信息職業(yè)技術(shù)學(xué)院信息化建設(shè)與管理中心，江蘇無錫 214153）

1 Apriori算法

Apriori算法首先利用遞歸的方法對數(shù)據(jù)進行逐層挖掘找出所有的頻集，然后從這些頻集中產(chǎn)生關(guān)聯(lián)規(guī)則，最后除去那些小于用戶預(yù)設(shè)的最小可信度和最小支持度的規(guī)則，留下的便是需要的強關(guān)聯(lián)規(guī)則。Apriori算法的主要描述如下［1］：

事務(wù)數(shù)據(jù)庫F；最小支持度min_s。

輸出：F的頻繁項集L。

（1）L1={frequent_1-itemsets}；//初始產(chǎn)生的頻繁1-項集的集合；

（2）for（x=2；Lx-1≠；x++）{//由頻繁x-1-項集產(chǎn)生頻繁x-項集；

（3）Cx=ap_hxx（Lx-1）；//調(diào)用函數(shù) ap_hxx，由 Lx-1 產(chǎn)生新的候選項集 Cx；

（4）for all affairs t∈D do{//對于事務(wù)數(shù)據(jù)庫F中的每一個事務(wù)t；

（5）Ct=subset（Cx，t）；//t中所包含的候選項集Cx；

（6）return L=∪xLx；//頻繁項集L為輸出結(jié)果。

函數(shù)ap_hxx通過連接產(chǎn)生新的候選項集，并根據(jù)“頻繁路徑+Apriori性質(zhì)”的定義對Ck內(nèi)的候選項集進行刪選，刪除那些不包含頻繁路徑子集的候選項集。

只要檢查候選項集的子集是否為頻繁路徑集，就可判斷該候選項集是否為頻繁路徑集。這里用函數(shù)has_apriori_s完成非頻繁路徑子集的測試，描述如下［1］：

funtion has_apriori_s（C，Lx-1）{//C 為候選 x項集，Lx-1為頻繁 x-1項集。

（1）for each（x-1）-subset s ofC//對每個 k-1 項子集 s；

（2）ifs Lk-1 then//如果s不在Lk-1中則返回true，即從Ck中刪除。

2 Apriori算法的不足

Apriori算法通過遞歸搜索的方法［2］來產(chǎn)生強關(guān)聯(lián)規(guī)則。該算法雖然簡單易懂，容易實現(xiàn)，但在實際應(yīng)用中仍有許多不足之處。

2.1 重復(fù)掃描數(shù)據(jù)庫

在Apriori算法中掃描數(shù)據(jù)庫的次數(shù)是根據(jù)頻繁項集的長度而定的，這就是說每產(chǎn)生一次頻繁項集都要掃描一次數(shù)據(jù)庫，直到產(chǎn)生出最大頻繁項集為止。

2.2 候選項集太多

用Apriori算法生成關(guān)聯(lián)規(guī)則的過程中會產(chǎn)生大量的候選項集，這些候選項集又會帶來大量的中間數(shù)據(jù)［2］。

2.3 執(zhí)行時間較長

在頻繁項集的長度較大而事務(wù)并沒有減少的情況下，Apriori算法需要消耗較長的時間才能完成對非頻繁項集的刪選工作。

2.4 挖掘效率較低

Apriori算法只是單純依靠設(shè)定的支持度來產(chǎn)生強關(guān)聯(lián)規(guī)則［3］，并沒有考慮到項目的重要性［4］，如此導(dǎo)致了大量無用規(guī)則的產(chǎn)生，大大降低了挖掘的效率。

2.5 分析數(shù)據(jù)不全面

因為算法設(shè)定了最小支持度，所以無法對小于這個支持度的事務(wù)進行分析。同時算法的效率還會隨著支持度的變小而降低。

3 改進的Apriori算法

3.1 改進算法的描述

用Apriori算法進行數(shù)據(jù)挖掘時掃描數(shù)據(jù)庫的次數(shù)與頻繁項集的長度有關(guān)，如頻繁項集的長度為N時就需掃描數(shù)據(jù)庫N次，這樣不僅給網(wǎng)絡(luò)的傳輸造成了一定的負(fù)擔(dān)，還明顯降低了Apriori算法的挖掘效率。因此本文在設(shè)計Apriori改進算法時，考慮改變原有數(shù)據(jù)庫的存儲結(jié)構(gòu)，建立臨時二進制數(shù)據(jù)庫，并采用二進制位的方法來表示項目在事務(wù)集中出現(xiàn)的情況，如項目在某事務(wù)中出現(xiàn)就用“1”來表示，反之用“0”來表示，然后通過設(shè)定的最小支持度(min_sup)對候選項集進行刪選，直到產(chǎn)生出最大頻繁項集為止。如此較好地減少了掃描數(shù)據(jù)庫的次數(shù)和產(chǎn)生候選項集的個數(shù)，大大提高了算法的效率。

3.2 改進算法在頻繁路徑挖掘中的具體步驟

3.2.1 創(chuàng)建臨時二進制數(shù)據(jù)庫

抽取RFID數(shù)據(jù)庫中圖書的路徑數(shù)據(jù)組成事務(wù)數(shù)據(jù)庫，并把圖書的屬性值嵌入路徑記錄來作為事務(wù)數(shù)據(jù)庫中的事務(wù)P；同時用單個形如（location，times）的路徑段或?qū)傩灾祦肀硎臼聞?wù)中的每個項目（path）；之后通過對事務(wù)數(shù)據(jù)庫的掃描來創(chuàng)建臨時二進制數(shù)據(jù)庫，該數(shù)據(jù)庫以項目為主鍵，另用二進制位來表示項目的事務(wù)集，也就是每個項目依次在所有事務(wù)中出現(xiàn)的情況，如它在某事務(wù)中出現(xiàn)就用“1”表示，未出現(xiàn)則用“0”表示；最后統(tǒng)計“1”的個數(shù)作為各項目的支持?jǐn)?shù)（countp），countp=supportp*|DB|，所以min_countp=min_supportp*|DB|，其中|DB|為事務(wù)P的總數(shù)。

3.2.2 生成頻繁1-路徑集

用統(tǒng)計好的項目支持?jǐn)?shù)依次與指定的最小支持?jǐn)?shù)進行比較，如其支持?jǐn)?shù)大于等于最小支持?jǐn)?shù)，那么該項就是頻繁路徑，如小于則為非頻繁路徑；最后根據(jù)比較結(jié)果，刪除非頻繁路徑，得到長度為1的頻繁1-路徑集。

3.2.3生成頻繁2-路徑集

先將頻繁1-路徑集中所有的項目兩兩相交，也就是進行二進制位的與運算，并統(tǒng)計運算結(jié)果中“1”的個數(shù)來作為項目的新支持?jǐn)?shù)，得到包含2個路徑段和屬性值的候選2-路徑集；接著同樣把新支持?jǐn)?shù)與最小支持?jǐn)?shù)進行比較，最后刪除候選集中的非頻繁路徑，得到長度為2的頻繁2-路徑集。

3.2.4 生成頻繁k-路徑集

從頻繁3-路徑集開始，只需求前k-2項相同的兩個項目的交集，不同的則不需再重復(fù)運算，就可生成符合的所有頻繁路徑集。當(dāng)再沒有新的頻繁路徑產(chǎn)生時，最終的頻繁路徑集就是最大頻繁路徑集。

3.3 改進算法在頻繁路徑挖掘中的應(yīng)用舉例

設(shè)事務(wù)數(shù)據(jù)庫為D，其事務(wù)P的總數(shù)為4，即|DB|=4，指定最小支持度（min_sup）為0.5，據(jù)上所述，可得到最小支持?jǐn)?shù)（min_cup）為2。路徑數(shù)據(jù)中各地點的含義為：c，倉庫；j，書架；r，閱覽室。停留以“小時”為時間單位，如表1所示。

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

首先把表1中的項數(shù)N與最小支持?jǐn)?shù)2進行比較，然后通過對事務(wù)數(shù)據(jù)庫D的一次掃描來創(chuàng)建臨時二進制數(shù)據(jù)庫，它以項目（path）為主鍵，并用二進制位來表示項目的事務(wù)集，也就是代表 （c，1）、（j，2）、（r，7）、（r，5）、（c，30）、（小說）、（散文）、（隨筆）這8個項分別在每條事務(wù)（路徑）中出現(xiàn)的情況，如有出現(xiàn)則用“1”表示，未出現(xiàn)則用“0”表示；最后統(tǒng)計“1”的個數(shù)作為各項目的支持?jǐn)?shù)（countp），如表2所示。

表2 臨時二進制數(shù)據(jù)庫

由于最小支持?jǐn)?shù)為 2，而表 2 中（r，7）、（c，30）、（散文）、（隨筆）的支持?jǐn)?shù)為 1，其支持?jǐn)?shù)≤最小支持?jǐn)?shù)，所以（r，7）、（c，30）、（散文）、（隨筆）是非頻繁路徑，它們更不屬于最大頻繁路徑集，因此將其刪除，得到長度為1的頻繁1-路徑集，如表3所示。

表3 頻繁1-路徑集表

根據(jù)表 3，把（小說）、（c，1）、（j，2）、（r，5）這 4 個路徑兩兩相交，也就是進行二進制位的與運算，并同樣對運算結(jié)果中“1”的個數(shù)進行統(tǒng)計作為路徑的支持?jǐn)?shù)［1］，得到包含2個路徑段和屬性值的候選2-路徑集，如表4所示。

表4 候選2-路徑集

由于最小支持?jǐn)?shù)為 2，而表 4 中（小說）（r，5）、（j，2）（r，5）的支持?jǐn)?shù)為 1，其支持?jǐn)?shù)≤最小支持?jǐn)?shù)，所以（小說）（r，5）、（j，2）（r，5）是非頻繁路徑，（小說）（r，5）、（j，2）（r，5）更不屬于最大頻繁路徑集，因此將其從候選2-路徑集中刪除，得到長度為2的頻繁2-路徑集，如表5所示。

表5 頻繁2-路徑集

在將表5中長度為2的路徑進行兩兩相交時，先判斷其第1項是否相同，然后只求第1項相同路徑的交集，也就是進行二進制位的與運算，并統(tǒng)計運算結(jié)果中“1”的個數(shù)獲取新的支持?jǐn)?shù)，最后得到包含3個路徑段和屬性值的候選3-路徑集，如表6所示。

由于最小支持?jǐn)?shù)為 2，而表 6 中（c，1）（j，2）（r，5）的支持?jǐn)?shù)是 1，其支持?jǐn)?shù)≤最小支持?jǐn)?shù)，所以（c，1）（j，2）（r，5）是非頻繁路徑，它更不屬于最大頻繁路徑集，因此將其刪除，得到長度為3的頻繁3-路徑集，如表7所示。

表6 候選3-路徑集

表7 頻繁3-路徑集

由于事務(wù)數(shù)據(jù)庫D中事務(wù)P的總數(shù)為4，而頻繁3-路徑集的數(shù)目為1，所以事務(wù)數(shù)據(jù)庫的最大頻繁路徑集為{（小說）（c，1）（j，2）}。

3.4 改進算法的分析

改進算法用二進制位來表示項目的事務(wù)集，并通過二進制的運算來獲得各項目的支持?jǐn)?shù)，然后將支持?jǐn)?shù)與最小支持?jǐn)?shù)進行比較，找出候選項集中的非頻繁項，最后從候選項集中刪除這些非頻繁項來得到頻繁項集。改進算法與經(jīng)典算法相比具有以下優(yōu)勢。

3.4.1 降低訪問數(shù)據(jù)量

改進算法只掃描原始數(shù)據(jù)庫一次，當(dāng)求候選項集Ck的支持?jǐn)?shù)時只需訪問二進制數(shù)據(jù)庫的頻繁k-1項集即可，并且隨著k的增大，頻繁k-1項集卻在減小，因此大大降低了訪問的數(shù)據(jù)量［3］。

3.4.2 快速求得交集

改進算法只需對項目的事務(wù)集進行二進制位的與運算就可完成兩項集的交集。

3.4.3 節(jié)省存儲空間

因為改進算法采用的是二進制數(shù)據(jù)庫，所以大大節(jié)省了事務(wù)的存儲空間，而且對二進制數(shù)進行運算遠比對字符串來得快［4］。

3.4.5 實驗結(jié)果

通過數(shù)據(jù)庫WebDocs的測試來比較經(jīng)典算法與改進算法的性能，同時考慮到基于Apriori的改進算法目前已有很多，為了體現(xiàn)出本文改進算法的優(yōu)越性，在此加入了基于矩陣的Apriori改進算法和基于深度優(yōu)先的Apriori改進算法來進行共同比較。另外，為了比較出幾個算法的實際效率，我們采用相同的最小支持?jǐn)?shù)和最小可信度，且在Pentium雙核E5 300，內(nèi)存1 024 M的環(huán)境下運行。實驗結(jié)果如表8所示。

表8 不同算法的性能比較（min_cup=10 min_conf=0.5）

由表8可知，在事務(wù)數(shù)較少的情況下改進算法的性能與經(jīng)典算法差不多，但隨著事務(wù)數(shù)的增加，改進算法的效率明顯優(yōu)于經(jīng)典算法。因其在任何情況下都只掃描原始數(shù)據(jù)庫一次，而經(jīng)典算法則需根據(jù)最大頻繁項集的長度來確定掃描數(shù)據(jù)庫的次數(shù)［5］。另外從本文的改進算法與另外兩種改進算法的比較來看，本文的改進算法在性能上也略有提高，雖然不是很多，但在事務(wù)數(shù)不斷增加的情況下仍具有一定的優(yōu)越性。