于守健 周羿陽(yáng)

(東華大學(xué)計(jì)算機(jī)學(xué)院 上海 201600)

基于前綴項(xiàng)集的Apriori算法改進(jìn)

于守健 周羿陽(yáng)

(東華大學(xué)計(jì)算機(jī)學(xué)院 上海 201600)

關(guān)聯(lián)規(guī)則的挖掘是數(shù)據(jù)挖掘中一個(gè)重要內(nèi)容，主要目的是找到事務(wù)數(shù)據(jù)庫(kù)中的有趣的模式。Apriori算法是關(guān)聯(lián)規(guī)則挖掘的最經(jīng)典算法之一，但是它本身存在著效率上的瓶頸。在深入了解Apriori算法前提下，提出基于前綴項(xiàng)集的候選集存儲(chǔ)結(jié)構(gòu)，并利用哈希表在快速查找上的優(yōu)勢(shì)，大大提高了經(jīng)典Apriori算法在連接步驟和剪枝步驟中的效率。實(shí)驗(yàn)證明改進(jìn)后的Apriori算法在一定支持度下比經(jīng)典Apriori算法有著更大的效率優(yōu)勢(shì)，并且支持度越小時(shí)提升效率越大。

數(shù)據(jù)挖掘 Apriori算法 前綴項(xiàng)集 關(guān)聯(lián)規(guī)則 哈希表

0 引 言

隨著計(jì)算機(jī)技術(shù)在各個(gè)行業(yè)的迅猛發(fā)展，各行業(yè)所產(chǎn)生的數(shù)據(jù)也越來(lái)越多，但是如何在這些海量數(shù)據(jù)中獲取有價(jià)值的信息也成了一個(gè)新的問(wèn)題。數(shù)據(jù)挖掘，即數(shù)據(jù)知識(shí)發(fā)現(xiàn)，正是在這個(gè)大背景下應(yīng)運(yùn)而生。數(shù)據(jù)挖掘[1]是從大量的數(shù)據(jù)中挖掘出隱含的、未知的、用戶可能感興趣的知識(shí)和規(guī)則。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中的一個(gè)重要內(nèi)容，它最先由Agrawal等提出[2]，主要解決的是顧客交易事務(wù)庫(kù)中項(xiàng)集之間的關(guān)聯(lián)規(guī)則問(wèn)題。隔年，Agrawal等人又提出了計(jì)算關(guān)聯(lián)規(guī)則的最經(jīng)典的算法，即Apriori算法[3]，它是由k-項(xiàng)集來(lái)推斷(k+1)-項(xiàng)集并通過(guò)剪枝來(lái)獲得k-項(xiàng)集的算法。但是由于Apriori算法在計(jì)算候選集中的計(jì)算瓶頸問(wèn)題，近年來(lái)也出現(xiàn)了針對(duì)不同方面的的算法改進(jìn)方式。Zhang等[4]提出了基于分類的改進(jìn)的Apriori算法，在效率上有一定程度的提升。Jia等[5]從事務(wù)數(shù)據(jù)庫(kù)劃分和動(dòng)態(tài)項(xiàng)集統(tǒng)計(jì)的角度對(duì)經(jīng)典Apriori算法進(jìn)行改進(jìn)。Liu等[6]在研究煤炭隱患數(shù)據(jù)時(shí)提出了數(shù)據(jù)庫(kù)矩陣化的方法來(lái)進(jìn)一步提升算法效率。Wang等[7]提出一種優(yōu)化的方法來(lái)減少對(duì)事務(wù)庫(kù)重復(fù)搜索的次數(shù)，從而達(dá)到提高效率的目的。Vaithiyanathan等[8]針對(duì)事務(wù)數(shù)據(jù)庫(kù)中相同興趣的關(guān)系對(duì)其進(jìn)行壓縮的方法來(lái)改進(jìn)算法效率。Lin[9]提出基于MapReduce計(jì)算模型的Apriori算法以提高大量數(shù)據(jù)的候選集生成效率。Zhang等[10]是從要分析的數(shù)據(jù)，即醫(yī)療數(shù)據(jù)的特征出發(fā)，提出一種針對(duì)該數(shù)據(jù)特點(diǎn)的改進(jìn)Apriori算法。

上述提到的改進(jìn)算法大多是通過(guò)減少對(duì)事務(wù)數(shù)據(jù)庫(kù)遍歷的次數(shù)來(lái)提高算法的效率，但是這些算法并沒(méi)有針對(duì)Apriori算法的兩個(gè)重要步驟，即連接和剪枝步驟進(jìn)行改進(jìn)。本文將針對(duì)經(jīng)典Apriori算法的這兩個(gè)重要步驟，即連接步驟和剪枝步驟，采用一種新的基于前綴項(xiàng)集的存儲(chǔ)方式，并利用哈希表快速查找的特征來(lái)提高改進(jìn)算法在兩個(gè)步驟中的查找效率。本文首先介紹經(jīng)典Apriori算法以及其不足之處，再具體介紹算法的改進(jìn)之處，最后介紹在具體數(shù)據(jù)集上經(jīng)典Apriori算法與改進(jìn)Apriori算法的效率比較。

1 Apriori算法

1.1 Apriori 算法介紹

Apriori算法是一種經(jīng)典的挖掘關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集算法，其基本思想是使用逐層迭代方法，先求得k-項(xiàng)集，再由k-項(xiàng)集去探索(k+1)-項(xiàng)集。Apriori算法利用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)，首先找出頻繁1-項(xiàng)集的集合，記作L1。用L1得到2-項(xiàng)集的集合L2，再用L2得到L3，直至不能找到頻繁k-項(xiàng)集。Apriori算法的主要包括下面3個(gè)步驟：

(1) 連接步驟：連接k-頻繁項(xiàng)集生成(k+1)-候選項(xiàng)集，記作Ck+1。連接的條件是2個(gè)k-項(xiàng)集的前(k-1)項(xiàng)相等且它們的第k項(xiàng)不相等。記li[j]為li中的第j項(xiàng)，則條件為：

l1[1]=l2[1]∧l1[2]=l2[2]∧…∧l1[k-1]=l2[k-1]∧l1[k]≠l2[k]其中l(wèi)1和l2是k-項(xiàng)集集合Lk的子集，l1[k]≠l2[k]是確保不產(chǎn)生重復(fù)的k-項(xiàng)集。由l1和l2連接產(chǎn)生的結(jié)果項(xiàng)集為：

{l1[1],l1[2],l1[3],…,l1[k],l2[k]}

(2) 剪枝步驟：從候選項(xiàng)集Ck+1中挑選出真實(shí)頻繁項(xiàng)集Lk+1。因?yàn)楹蜻x項(xiàng)集Ck+1是真實(shí)頻繁項(xiàng)集Lk+1的超集。根據(jù)Apriori性質(zhì)：頻繁k-項(xiàng)集的任意子集必定也是頻繁的，即頻繁k-項(xiàng)集的任意(k-1)-項(xiàng)集也必定是頻繁的。利用此性質(zhì)查找是否Ck+1的k-項(xiàng)子集是否都在Lk中，如果不成立，則將該候選(k+1)-項(xiàng)集從Ck+1中刪除。

(3) 計(jì)數(shù)步驟：掃描數(shù)據(jù)庫(kù)，累加(k+1)-候選集在數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)。再根據(jù)給定的最小支持度閾值生成(k+1)-項(xiàng)集。

1.2 Apriori算法的不足

Apriori是挖掘關(guān)聯(lián)規(guī)則的最經(jīng)典算法之一，但是也存在著效率不高的問(wèn)題。Apriori算法的時(shí)間消耗主要在以下3個(gè)方面：

(1) 在連接步驟，利用k-項(xiàng)集連接產(chǎn)生(k+1)-候選項(xiàng)集時(shí)，判斷連接條件時(shí)比較次數(shù)太多。假設(shè)Lk中有m個(gè)k-項(xiàng)集，則連接步驟需要進(jìn)行比較的時(shí)間復(fù)雜度為O(k×m2)。

(3) 在計(jì)數(shù)步驟中，對(duì)Ck+1中候選項(xiàng)集的支持度計(jì)數(shù)中，需要掃描次數(shù)據(jù)庫(kù)|Ck+1|。

上述即經(jīng)典Apriori算法的時(shí)間消耗的主要三個(gè)方面，在引言中提到的改進(jìn)的算法也主要是針對(duì)其中的第三個(gè)步驟，即計(jì)數(shù)步驟作出改進(jìn)以提升效率，本文將針對(duì)其中的前兩個(gè)步驟，即連接步驟和剪枝步驟的計(jì)算瓶頸，提出一種基于前綴項(xiàng)集的改進(jìn)Apriori算法。

2 Apriori算法改進(jìn)

2.1 算法改進(jìn)思想

在1.2節(jié)中已經(jīng)分析了傳統(tǒng)Apriori算法的不足之處，所以對(duì)其改進(jìn)也著重在1.2節(jié)中提到的3個(gè)步驟中。由于Apriori算法中記錄中的各項(xiàng)均已經(jīng)是按字典排序的，因此由Apriori算法生成的候選項(xiàng)集也是有序的。

(1) 基于前綴項(xiàng)集的存儲(chǔ)方式

在新提出的基于前綴項(xiàng)集的改進(jìn)算法中，我們引入一種新的存儲(chǔ)項(xiàng)集的方法——基于前綴項(xiàng)集的存儲(chǔ)方法。對(duì)于每個(gè)項(xiàng)集我們修改其保存方式：對(duì)于Lk中各k-項(xiàng)集我們采用類似Map結(jié)構(gòu)的Hash表來(lái)保存，其中key為k-項(xiàng)集的前(k-1)-項(xiàng)內(nèi)容，value為k-項(xiàng)集的第k項(xiàng)內(nèi)容。再將LK中所有項(xiàng)集保存在一個(gè)Map中，對(duì)于具有相同key，即相同前(k-1)-項(xiàng)內(nèi)容的k-項(xiàng)集，則該key對(duì)應(yīng)的value值為其value，即第k-項(xiàng)內(nèi)容的并集。

例如：數(shù)據(jù)庫(kù)如表1所示，設(shè)最小支持度為2。

表1 事務(wù)表TD

傳統(tǒng)的Apriori算法掃描數(shù)據(jù)庫(kù)，得到每個(gè)項(xiàng)在數(shù)據(jù)庫(kù)中出現(xiàn)的次數(shù)，并得到1-項(xiàng)集及計(jì)數(shù)，再基于1-項(xiàng)集迭代產(chǎn)生滿足最小支持度的2-項(xiàng)集及計(jì)數(shù)。下面是傳統(tǒng)的Apriori算法得到的內(nèi)容如表2所示。

表2 傳統(tǒng)存儲(chǔ)方式

利用基于前綴項(xiàng)集的保存方式如表3所示。

表3 基于前綴項(xiàng)集存儲(chǔ)方式

表3中，因?yàn)?-項(xiàng)集只有一個(gè)項(xiàng)，所以其前綴內(nèi)容設(shè)為NULL；在上表中還可以清楚地看到若前綴的長(zhǎng)度為n，則其代表的項(xiàng)集長(zhǎng)度則為(n+1)，因?yàn)関alue中記錄的是該項(xiàng)集的最后一個(gè)項(xiàng)的內(nèi)容。

(2) 基于前綴項(xiàng)集的連接步驟

在基于前綴項(xiàng)集存儲(chǔ)方式的建立后，在連接步驟進(jìn)行k-項(xiàng)集間的連接操作時(shí)，則只要對(duì)相同前綴-key的value中任意兩個(gè)項(xiàng)進(jìn)行合并，再加上該前綴-key即可成為新的(k+1)-項(xiàng)候選項(xiàng)集。例如，對(duì)表3中的2-項(xiàng)集進(jìn)行連接，前綴-key為A對(duì)應(yīng)的value集中連接操作可得到{{B,C},{B,D},{C,D}}，前綴-key為B對(duì)應(yīng)的value集中連接操作可得到{{C,D},{C,E},{D,E}}。

(3) 基于前綴項(xiàng)集的剪枝步驟

由1.1節(jié)中對(duì)傳統(tǒng)剪枝步驟的介紹可以知道，(k+1)-候選項(xiàng)集是由LK中的兩個(gè)k-項(xiàng)集連接得到，并且如果(k+1)-候選項(xiàng)集的某個(gè)k-項(xiàng)子集不在Lk中時(shí)，該(k+1)-候選項(xiàng)即從Ck+1中移除。下面提出一個(gè)定理：

定理1 如果由兩個(gè)k-項(xiàng)集、，連接產(chǎn)生的(k+1)-項(xiàng)集的k-項(xiàng)子集不在Lk中，則該k-項(xiàng)子集中必然同時(shí)包含l1[k]，l2[k]。

證明：l1、l2連接后得到的(k+1)-項(xiàng)候選集為{l1[1],l1[2],l1[3],…,l1[k],l2[k]}。

如果該(k+1)-項(xiàng)候選集的k-項(xiàng)子集不同時(shí)包含l1[k]，l2[k]，則可能的情況只有l(wèi)1[1]、l1[2]，l1[3]…,l1[k]、l1[1]，l1[2]，l1[3]，…，l2[k]}即、l1、l2。而l1、l2屬于Lk，所以若k-項(xiàng)子集不屬于Lk，則k-項(xiàng)子集中必同時(shí)包含l1[k]，l2[k]。

由定理1可知，在進(jìn)行剪枝過(guò)程中只需考慮(k+1)-項(xiàng)候選集中同時(shí)包含用于連接的兩個(gè)k-項(xiàng)集尾項(xiàng)的可能的k-項(xiàng)子集即可。針對(duì)表3中的例子，遍歷可能出錯(cuò)的2-項(xiàng)子集可以得到如表4所示。

表4 剪枝過(guò)程

如表4中所示，只有{{B,C},{B,E}}是可能的2-項(xiàng)候選子集，再加上其對(duì)應(yīng)的前綴-key，得到{{A,B,C},{A,B,E}}，即得剪枝后的3-項(xiàng)候選子集C3。

得到(k+1)-項(xiàng)候選集后，再遍歷原始數(shù)據(jù)庫(kù)，執(zhí)行計(jì)數(shù)步驟，即找出滿足最小支持度的k-項(xiàng)集，針對(duì)表3中例子，可以知道{{A,B,C},{A,B,E}}都滿足最小支持度，所以將他們加入到基于前綴項(xiàng)集存儲(chǔ)中，如表5所示。

表5 3-項(xiàng)集存儲(chǔ)方式

2.2 算法實(shí)現(xiàn)

完整的算法可描述為：

輸入：事務(wù)數(shù)據(jù)庫(kù)D，最小支持度min_sup

輸出：頻繁項(xiàng)集L

1) L1=D的1-項(xiàng)集

2) Map map;

3) 將L1導(dǎo)入map中，key為null，value為L(zhǎng)1中項(xiàng)的并集

4) for(k=2;Lk-1φ;k++){

5) Ck=pre_apriori_gen(map,k-2);

6) 對(duì)Ck中每個(gè)項(xiàng)集計(jì)數(shù)，Lk={c∈Ck|c.count>min_sup}

7) }

8) Return ;

procedurepre_apriori_gen(map:Map;k:int)

1) for each key in map{

2) if(key.length()==k){

3) c:=key與(value中任意兩個(gè)值)的有序組合;

4) if(map.containsKey(c[0:k])){

5) If(c的任意(k+1)子集存在于map的(key,value)中){

6) 將c加入Ck;

7) }

8) }

9) else continue；

10) }

11) Return Ck

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

實(shí)驗(yàn)采用的數(shù)據(jù)是瑞金醫(yī)院的糖尿病臨床處方數(shù)據(jù)共120 000行，數(shù)據(jù)中記錄的是每次就診的處方藥品編號(hào)。本實(shí)驗(yàn)運(yùn)行機(jī)器配置為Intel Core i5 2.7 GHz處理器，8 GB 1866 MHz LPDDR3 內(nèi)存。

實(shí)驗(yàn)從兩方面來(lái)對(duì)經(jīng)典Apriori算法和基于前綴項(xiàng)集的Apriori算法來(lái)進(jìn)行效率上的比較：一方面是當(dāng)測(cè)試總數(shù)固定時(shí)不同的支持度下的算法運(yùn)行效率的比較，另一方面是當(dāng)支持度固定后不同的測(cè)試總數(shù)下算法的運(yùn)行效率的比較。

實(shí)驗(yàn)1結(jié)果如下圖所示。

圖1 不同支持度下的運(yùn)行時(shí)間比較

圖1描述的是兩種算法在測(cè)試樣本總數(shù)一定，共12萬(wàn)條數(shù)據(jù)時(shí)，不同的最小支持度下運(yùn)行的時(shí)間比較。從圖1中可以看到，當(dāng)支持度越小時(shí)改進(jìn)的Apriori算法比經(jīng)典Apriori算法的效率優(yōu)勢(shì)越明顯。從圖中還可以看出當(dāng)支持度達(dá)到一定值時(shí)，由于達(dá)到支持度要求的頻繁項(xiàng)集數(shù)很少，所以此時(shí)改進(jìn)算法的效率優(yōu)勢(shì)一般。

表6 不同支持度下時(shí)間及時(shí)間減少率

表6顯示了經(jīng)典Apriori算法和改進(jìn)Apriori算法在不同支持度下的具體運(yùn)行時(shí)間以及后者相對(duì)前者的減少率。

實(shí)驗(yàn)2結(jié)果如圖2所示。

圖2 相同支持度不同測(cè)試總數(shù)下的運(yùn)行時(shí)間比較

圖2描述的是兩種算法在不同測(cè)試總數(shù)，但支持度都為測(cè)試總數(shù)的2%時(shí)運(yùn)行時(shí)間的比較。從圖2可以看出，在相同支持度下測(cè)試總數(shù)越大，算法的運(yùn)行時(shí)間越長(zhǎng)，并且改進(jìn)的Apriori算法相比經(jīng)典Apriori算法在效率上有著穩(wěn)定的提升效果。

表7介紹了兩種算法在相同支持率但測(cè)試總數(shù)不同的情況下運(yùn)行的時(shí)間比較，可以看出在支持度為測(cè)試總數(shù)2%時(shí)，改進(jìn)Apriori算法在效率上明顯高于經(jīng)典Apriori算法，并且效率的提升率穩(wěn)定在70%左右。

表7 不用測(cè)試總數(shù)下時(shí)間及時(shí)間減少率

續(xù)表7

實(shí)驗(yàn)表明，基于前綴項(xiàng)集的Apriori算法是有效可行的。

4 結(jié) 語(yǔ)

本文在對(duì)經(jīng)典Apriori算法的深入研究基礎(chǔ)上，指出了該算法在連接、剪枝步驟中的一些局限，并提出了基于前綴項(xiàng)集的數(shù)據(jù)存儲(chǔ)方式以及在該存儲(chǔ)方式上的算法改進(jìn)，使得在連接步驟和剪枝步驟的運(yùn)行時(shí)間得到很大程度的減少。最后在支持度和測(cè)試總數(shù)兩個(gè)維度上的實(shí)驗(yàn)結(jié)果也證明了算法的可行性。

[1] Han J,Kamber M,Pei J.Data mining:Concepts and techniques[J].3rd ed.San Francisco:Morgan Kaufmann Publishers,2001.

[2] Agrawal R,Imieliński T,Swami A.Miningassociationrules between setsof items inlarge databases[C]//Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data,1993:207-216.

[3] Agrawal R,Srikant R.Fast algorithms for mining association rules in large databases[C]//Proceedings of the 20th International Conference on Very Large Data Bases,1994:487-499.

[4] Zhang C S,Li Y.Extension of local association rules mining algorithm based on apriori algorithm[C]//Software Engineering and Service Science (ICSESS),2014 5th IEEE International Conference on.IEEE,2014:340-343.

[5] Jia Y,Xia G,Fan H,et al.An Improved Apriori Algorithm Based on Association Analysis[C]//2012 Third International Conference on Networking and Distributed Computing,2012:208-211.

[6] Liu S,Peng L.Analysis of Coal Mine Hidden Danger Correlation Based on Improved A Priori Algorithm[C]//Intelligent Systems Design and Engineering Applications,2013 Fourth International Conference on.IEEE,2013:112-116.

[7] Wang P,An C,Wang L.An improved algorithm for Mining Association Rule in relational database[C]//Machine Learning and Cybernetics (ICMLC),2014 International Conference on.IEEE,2014,1:247-252.

[8] Vaithiyanathan V,Rajeswari K,Phalnikar R,et al.Improved apriori algorithm based on selection criterion[C]//Computational Intelligence & Computing Research (ICCIC),2012 IEEE International Conference on.IEEE,2012:1-4.

[9] Lin X.MR-Apriori:Association Rules algorithm based on MapReduce[C]//Software Engineering and Service Science (ICSESS),2014 5th IEEE International Conference on.IEEE,2014:141-144.

[10] Zhang W,Ma D,Yao W.Medical Diagnosis Data Mining Based on Improved Apriori Algorithm[J].Journal of Networks,2014,9(5):1339-1345.

[11] Han J,Pei J,Yin Y.Mining Frequent Patterns without Candidate Generation[C]//Proceedings of ACM SIGMOD International Conference on Management of Data,2000:1-12.

THE IMPROVEMENT OF APRIORI ALGORITHM BASED ON PREFIXED-ITEMSET

Yu Shoujian Zhou Yiyang

(CollegeofComputerScienceandTechnology,DonghuaUniversity,Shanghai201600,China)

The mining of association rule is an important method for discovering interesting relations between variables in large databases.Apriori algorithm is one of the most classical algorithms of association rules,but it has bottleneck in efficiency.Thus,a candidate item set storage structure based on prefixed-item set is proposed with the help of the quick search of hash map,and the efficiency of classical Apriori algorithm in connecting and pruning step has been improved greatly.The experiments show that the improved Apriori algorithm does better in efficiency than the classical Apriori algorithm in certain degree’s support,and the smaller support,the better efficiency.

Data mining Apriori algorithm Prefixed-itemset Association rules Hash map

2015-10-21。于守健，副教授，主研領(lǐng)域：Web服務(wù)，企業(yè)應(yīng)用集成，數(shù)據(jù)庫(kù)與數(shù)據(jù)倉(cāng)庫(kù)。周羿陽(yáng)，碩士。

TP3

A

10.3969/j.issn.1000-386x.2017.02.052