一種基于預判篩選的頻繁項集挖掘算法

李德辰,呂一帆,趙學健

(1.南京郵電大學 物聯網學院,江蘇 南京 210023; 2.南京郵電大學 現代郵政學院,江蘇 南京 210003)

0 引 言

近年來，數據挖掘技術在各行各業的決策支持活動中扮演著越來越重要的角色[1-2]。關聯規則分析作為數據挖掘最活躍的研究領域之一，在精準營銷[3]、個性化醫療診斷[4]、網絡優化與管理[5]等領域均有著廣泛的應用。所謂關聯規則就是隱藏在海量數據中的事物之間的聯系和規律。在數據量急劇膨脹的今天，如何從海量數據中快速、高效地找出這些隱藏信息，提高關聯規則分析算法的效率，具有十分重要的意義和應用價值。關聯規則挖掘通常分兩步進行：頻繁項集挖掘，即找出所有滿足最小支持度的項集，找出的這些項集稱為頻繁項集；生成關聯規則，在第一步產生的頻繁項集的基礎上生成滿足最小置信度的規則，產生的規則稱為強規則。頻繁項集挖掘作為關聯規則挖掘技術的關鍵步驟，其性能對關聯規則挖掘具有重要的意義。

Agrawal和Skrikant在1994年提出了第一個關聯規則分析算法——Apriori算法[6]。Apriori算法是最經典的關聯規則分析算法之一。Apriori算法使用重復迭代的方法生成頻繁項集。首先掃描數據庫，得到所有項目的出現頻率，并與給定的最小支持度閾值進行比較，得到頻繁1-項集L1。接下來，對頻繁1-項集進行自連接，并根據頻繁項集的向下閉包特性進行剪枝，產生候選頻繁項集2-項集C2，接下來進行掃描數據庫判決，得到頻繁2-項集L2。以此類推，直至得到所有頻繁項集為止。

Apriori算法在對候選頻繁項集進行剪枝操作的過程中，用到了頻繁項集的向下閉包特性。該特性是指如果一個集合是頻繁項集，則它的所有子集都是頻繁項集；反之，如果一個集合不是頻繁項集，則它的所有超集都不是頻繁項集。Apriori算法利用頻繁項集的向下閉包特性對候選頻繁項集進行剪枝，從而有效地控制候選項集的指數增長。

從上述可以看出，Apriori算法生成關聯規則的過程包含兩個步驟：挖掘隱藏在海量數據集中的所有頻繁項集；根據挖掘出的頻繁項集生成關聯規則。其中第二步相對比較簡單，第一步才是Apriori算法實現關聯規則分析的關鍵，當然也是決定算法性能優劣的關鍵。目前對于Apriori算法的改進方法也大多數是針對第一步進行的。

Apriori算法產生頻繁項集的過程有兩個重要特點。首先，Apriori算法通過重復迭代生成頻繁項集，在由候選頻繁項集生成頻繁項集的過程中，都要通過掃描數據庫對候選頻繁項集進行判別；其次，Apriori算法在每次迭代過程中，都要通過自連接生成候選頻繁項集。這兩個特點使得算法雖然思想簡單，較容易實現，但是卻存在兩個缺點：在規則產生過程中，算法必須反復掃描事務庫，I/O負載較大，且算法的運行效率較低；在自連接的過程中，會產生過多候選項集，使得挖掘的候選項集所含的項數過多，導致計算量驚人。這兩個缺點使得Apriori算法在處理一些項集較多且長度較長的事務數據庫時，顯得力不從心。

為了克服Apriori算法存在的上述缺點，提出一種A_RSPS算法(Apriori with random sampling based prejudgment and screening)。通過對原始數據集的隨機取樣，進行Apriori算法計算，得出樣本頻繁項集的支持度集合，再計算原始數據集的頻繁項集，遍歷數據之前通過之前得到的樣本支持度集合進行預判篩選對候選項集進行二次剪枝，并且引入阻尼因子和補償因子對預判篩選產生的誤差進行修正，以減少掃描數據庫的次數，降低算法的運算時間，提高算法的運算效率。

1 相關研究

研究人員對頻繁項集挖掘算法進行了研究，取得了大量研究成果。文獻[7]采用矩陣的方法表示數據庫，每個項目對應矩陣的一行，每個事務對應矩陣的一列，則矩陣的行向量之和為所對應項目在各事務中出現的次數，即該項目的支持度。可以看出，通過對矩陣的操作實現頻繁項集的挖掘，無需多次掃描數據庫，可以提高關聯規則分析算法的時間效率，但是算法的空間復雜度較大。文獻[8]使用Hash表存儲事務數據以減少存儲空間，同時使計算頻繁項集更高效方便。此外，通過刪除無用項表可以減少掃描Hash表的數量。用該方法在不損失頻繁項集的前提下提高了發現頻繁項集的效率。文獻[9]對產生的每一個項集，采用包含兩個線性表的類進行存儲。事務標識符列表由支持該項集的所有事務標識符組成。因此一個項集的支持度就等于該項集的事務標識符列表長度。候選項集的支持度只要取其相應子集的事務標識符列表的交集得到，從而避免了為得到候選項集的支持度而去掃描數據庫。文獻[10]提出了一種新的產生候選集的方法，在k-1項頻繁集中的一個項集與其余所有項集進行連接，把連接得到的不同k項集存儲，然后立即確定所有符合剪枝后的候選k項集。這樣就省略了尋找k項集的所有k-1項子集的費時剪枝操作，從而使剪枝步的平均掃描量大為減少。文獻[11]把算法和負關聯規則理論相結合，提出了一種基于負關聯規則的數據挖掘算法。文獻[12]提出的算法只需要一次數據庫掃描。該算法在掃描數據庫并計算每個項目的支持度時不會產生支持度為0的候選項，減少了候選項的數量。該文獻還提到利用基于聚類的算法通過壓縮事務數據庫，通過節省無效的數據庫掃描以提高算法的效率。文獻[13]提出了基于用戶的興趣度的預處理的算法。該算法使用興趣項排除不相關的項目以減少候選集D，其采用的紡織數據庫包含眾多參數，改進的算法只需要其中兩個參數，同樣減少了數據庫掃描。文獻[14]提出了一種有效的貪婪算法，以在給定的事務數據庫中生成不相交的頻繁項集的集合。該算法從給定的不相交頻繁項集開始，發現更頻繁的項目集。文獻[15]提出預判篩選算法，該算法在Apriori算法連接、剪枝的基礎上，添加了預判篩選的步驟，通過使用先驗概率對候選頻繁k項集集合進行縮減優化，并且引入阻尼因子和補償因子對預判篩選產生的誤差進行修正，以減少掃描數據庫的次數，降低算法的運算時間，提高算法的運算效率。文中正是基于該文獻提出的預判篩選的思想，結合采樣思想進行的改進。

2 A_RSPS算法

2.1 相關定義

假設D是挖掘的事務數據庫，該數據庫中包含n個事務，即D={T1,T2,…,Tn}。I為數據庫中全部項目的集合I={I1,I2,…,Im}。對?Tq∈D，有Tq?I(1≤a≤n)。如果項目集X包含k個不同的項目，稱X為k項集。如果X?Tq，稱項集出現在事務Tq中，所有可能的k項集X組成集合Ck。統計該事件在D中發生的頻率Px，稱為X在D中的支持度(support)，給出一個D的最小支持度min_support，若Px>min_support，則稱X為頻繁k項集，所有可能的頻繁k項集X組成集合Lk。

對于給定的事務數據庫D，給定的最小支持度為min_support。D中客觀存在的頻繁項集集合為L，包含N個成員；運行ARSPS算法所得頻繁項目集集合為La。屬于集合La但不屬于集合L的項集數量記為Nf，屬于集合L但不屬于集合La的項集數量記為No。文中稱屬于集合La但不屬于集合L的項集為誤判項集，其中誤判率MR=Nf/N，稱屬于集合L但不屬于集合La的項集為遺漏項集，其中遺漏率OR=No/N。

2.2 算法描述

ARSPS算法尋找頻繁項集的過程如下：

步驟1:對D進行隨機取樣取其子集Ds，取適當的Δ2，以(1-Δ2)*min_support對Ds進行Apriori算法運算構建頻繁項集Ls，與對應的支持度集合sample_support組成一個篩選用的預判概率集合PS_set(Ls,sample_support)。

步驟2:掃描事務數據庫D，對D中包含項目It的事務數Nt進行統計，其中It∈I，得到候選1項集C1=I，及其支持度集合support={Nt/|D|,∈[1,m]}。

步驟3:對于C1中的每一個候選項Ci，判斷它是否存在于之前的先驗概率集合PS_set中，如果不在則把它從C1中刪去，如果有，取適當的Δ1，如果Ci大于min_support*(1+Δ1)那就把它添加到L1，并且從C1中刪除。最后掃描C1，刪除那些Nt

步驟4:假設Lk-1已生成，現在可用它來生成Lk，Lk-1與自身進行連接得到候選k項集Ck,k∈{2,3,4…}，第1次執行時k=2，每循環執行一次k加1。

連接過程如下：對于?x1,x2∈Lk-1，若x1[1]=x2[1],x1[2]=x2[2],x1[k-2]=x2[k-2],…,x1[k-1]=x2[k-1]，則將x1,x2連接生成候選項c={x1[1],x1[2],…,x1[k-1],x2[k-1]}。

步驟5:根據Apriori原理(如果某個項集是頻繁的，那么它的所有子集也是頻繁的)，從候選k項集Ck中刪除所有k-1項子集不完全包含在頻繁k-1項集Lk-1中的項。

步驟6:對于剪枝后的Ck中的每一個候選項Ci，判斷它是否存在于之前的先驗概率集合PS_set中，如果不存在則把它從Ck中刪去，如果存在且大于min_support*(1+Δ1)，那就把它添加到Lk，并且從Ck中刪除。

步驟7:掃描數據庫，判斷預判篩選后的每個成員是否滿足最小支持度要求，滿足則加入頻繁項集循環執行直至為空，不能發現更大的頻繁項目集為止。

步驟 8:最終獲得的頻繁項目集集合為L。

3 實驗分析

采用Python語言實現了Apriori和改進的A_RSPS算法，并通過實驗對兩個算法進行了對比。數據集使用Frequent Item-set Mining Dataset Repository(http://fimi.ua.ac.be/data/)網站提供的IBM Almaden Quest研究組生成的數據，算法增加的取樣步驟中設置取事務數的一定百分比作為采樣數據，引入阻尼因子和補償因子兩個參數，通過合理設置阻尼因子1和補償因子2可有效降低誤判率和遺漏率。

首先，設計實驗1對阻尼因子和補償因子的取值進行分析，每一組實驗采用控制變量法，相同參數重復實驗5次取平均值。表1表示min_support=0.02，阻尼因子Δ1取值從0.05到0.25的過程中事務數分別為5k，10k，25k，50k對應的頻繁項集誤判率。由表可知，當同一大小數據集Δ1取值變大時誤判率逐漸減小，當Δ1取值確定時誤判率隨事務數增大而減小，尤其當事務數大于10k后，Δ1大于0.1后發生誤判的概率已經低于1%。

表1 阻尼因子-誤判率

實驗2的數據如表2所示，表示min_support=0.02，補償因子Δ2取值從0.05到0.2變化過程中5k，10k，25k，50k四組事務數據庫的遺漏率。同實驗1一樣，事務數越大，遺漏率越小，Δ2越大，遺漏率越小。尤其在事務數較小的情況下，Δ2取較小值則會造成較大的遺漏率，而數據集很大時則遺漏率小于1%，可以接受。

表2 補償因子-遺漏率

實驗3對算法運行時間與事務數規模的關系進行了分析，設置min_support=0.02，在保證誤判率和遺漏率的情況下Apriori和改進的A_RSPS算法運行時間如圖1所示。由圖1可見，Apriori算法的運行時間隨著事務數增大迅速增加，100k事務數的數據集需要約193 s，而改進算法對于100k事務數的數據集需要約34 s。可以看出，A_RSPS相對于Apriori算法來說，時間效率得到了較大提升。

圖1 算法運行時間隨事務數的變化

實驗4對算法運行時間隨最小支持度min_support的變化情況進行了分析。對于10k的數據集，在保證誤判率和遺漏率的情況下，分別設置min_support為0.01，0.02，0.04，0.08，為保證min_support取較小情況下的誤判率不會過高，選擇10%取樣，設置Δ1=0.4，Δ2=0.35，見表3。

表3 最小支持度對運行時間的影響

實驗5對算法取樣率對運行時間、遺漏率和誤判率的影響進行分析。設定min_support=0.02，10k數據集，Δ1=0.25，Δ2=0.25，分別取樣5%，10%，15%，20%，25%，在同一參數下進行5次測試取均值，相應的運行時間、遺漏率和誤判率如表4所示。由該表可知，改進算法占原始算法時間比隨著取樣率的增加而增加，15%取樣率時約需要消耗44%原始Apriori算法所需的時間，同時，遺漏率和誤判率相應減少，在30%取樣率時已經幾乎不出現遺漏和誤判了，而取10%以下取樣率時遺漏率和誤判率會明顯增大，不宜采用。

表4 算法取樣率對運行時間、遺漏率和誤判率的影響

4 結束語

文中提出一種基于預判篩選和采樣思想的關聯規則挖掘算法A_RSPS。該算法在對數據集處理之前取樣部分數據進行經典Apriori算法計算得出樣本數據的支持度，在原始算法連接、剪枝的基礎上，增加了預判篩選的步驟，通過使用樣本計算得到的支持度對候選頻繁k項集集合進行縮減優化，從而減少關聯規則挖掘過程中掃描數據庫的次數。此外，算法引入阻尼因子和補償因子對預判篩選引起的誤判率和遺漏率進行控制。經實驗驗證，A_RSPS算法在保證誤判率和遺漏率的前提下降低了算法的運算時間，提高了算法的運算效率。

參考文獻：

[1] 王光宏,蔣 平.數據挖掘綜述[J].同濟大學學報:自然科學版,2004,32(2):246-252.

[2] 畢建欣,張岐山.關聯規則挖掘算法綜述[J].中國工程科學,2005,7(4):88-94.

[3] 阮利男.大數據時代精準營銷在京東的應用研究[D].成都：電子科技大學,2016.

[4] 黃新霆,包小源,俞國培,等.醫療大數據驅動的個性化醫療服務引擎研究[J].中國數字醫學,2014,9(8):5-7.

[5] 岳彥杰.基于規則的網絡數據關聯分析器的優化設計[D].哈爾濱:哈爾濱工業大學,2008.

[6] AGRAWAL R,SRIKANT R.Fast algorithms for mining association rules[C]//Proceedings of the 20th international conference on very large data bases.[s.l.]:[s.n.],1994:487-499.

[7] 馬盈倉.挖掘關聯規則中Apriori算法的改進[J].計算機應用與軟件,2004,21(11):82-84.

[8] 陳文慶,許 棠.關聯規則挖掘Apriori算法的改進與實現[J].微機發展(現名：計算機技術與發展),2005,15(8):155-157.

[9] 劉華婷,郭仁祥,姜 浩.關聯規則挖掘Apriori算法的研究與改進[J].計算機應用與軟件,2009,26(1):146-149.

[10] 胡吉明,鮮學豐.挖掘關聯規則中Apriori算法的研究與改進[J].計算機技術與發展,2006,16(4):99-101.

[11] 張 璽.數據挖掘中關聯規則算法的研究與改進[D].北京:北京郵電大學,2014.

[12] RAJESWARI K.Improved Apriori algorithm-a comparative study using different objective measures[J].International Journal of Computer Science and Information Technologies,2015,6(3):3185-3191.

[13] INGLE M G,SURYAVANSHI N Y.Association rule mining using improved Apriori algorithm[J].International Journal of Computer Applications,2015,112(4):37-41.

[14] PALSHIKAR G K,KALE M S,APTE M M.Association rules mining using heavy itemset[C]//Proceedings of data & knowledge engineering.[s.l.]:[s.n.],2007.

[15] 趙學健,孫知信,袁 源.基于預判篩選的高效關聯規則挖掘算法[J].電子與信息學報,2016,38(7):1654-1659.