基于最頻繁項(xiàng)提取和候選集剪枝的THIMFUP算法

楊 勇, 張 磊, 曲福恒, 劉俊杰, 陳 強(qiáng)

(1. 長春理工大學(xué) 計算機(jī)科學(xué)技術(shù)學(xué)院, 長春 130022； 2. 長春師范大學(xué) 教育學(xué)院, 長春 130032)

關(guān)聯(lián)規(guī)則挖掘技術(shù)是數(shù)據(jù)挖掘[1]領(lǐng)域最常用的技術(shù)之一, 其可從復(fù)雜的數(shù)據(jù)中得到不同項(xiàng)集之間的隱藏規(guī)律, 從而為各行業(yè)的發(fā)展提供輔助決策, 目前關(guān)聯(lián)規(guī)則挖掘技術(shù)已得到廣泛關(guān)注.

目前, 對關(guān)聯(lián)規(guī)則增量挖掘算法的研究相對較少, 其主要分為兩類： 第一類是以Apriori算法[2]為基礎(chǔ)的基于迭代的增量算法, 如FUP(fast update algorithm)[3],FUP2[4],IUA(incremental updating algorithm)[5]等; 第二類是以FP-growth[6]為基礎(chǔ)的基于樹結(jié)構(gòu)的增量算法, 如Cat-tree[7]和Can-tree[8]等, 該類算法以樹結(jié)構(gòu)[9]為基礎(chǔ), 挖掘過程不會生成候選集, 也不需要掃描數(shù)據(jù)庫, 但過于依賴事物的順序, 并且當(dāng)數(shù)據(jù)集過大時, 生成的樹結(jié)構(gòu)太復(fù)雜, 對內(nèi)存消耗較大, 不適合大數(shù)據(jù)集環(huán)境下的規(guī)則挖掘. 因此, 本文主要考慮基于迭代的關(guān)聯(lián)規(guī)則增量算法. 除FUP算法外, 針對增量規(guī)則挖掘問題, 目前基于FUP算法已提出了很多改進(jìn)算法, 如黃德才等[10]提出了Pruning FUP算法, 通過減少對數(shù)據(jù)庫的掃描次數(shù)提高算法效率; 閆仁武等[11]提出了基于時間權(quán)值的增量更新算法, 通過對不同時期數(shù)據(jù)加權(quán)[12]以控制效率和規(guī)則的準(zhǔn)確性； 朱曉峰等[13]提出了基于MapReduce[14]的FUP算法, 利用并行化提高了運(yùn)算效率; 尹艷紅[15]提出了IUTS算法, 結(jié)合FUP和IUA算法的思想, 從支持度和數(shù)據(jù)庫兩個角度解決了挖掘問題； 張步忠等[16]對已有的增量算法進(jìn)行了詳細(xì)綜述； 耿志強(qiáng)等[17]提出了基于矩陣的關(guān)聯(lián)規(guī)則增量算法(MFUP), 利用矩陣避免了數(shù)據(jù)庫的重復(fù)掃描； Zhang等[18]提出了FUP-HAUIMI算法, 在性能較高的條件下提高了規(guī)則的實(shí)用性; 曾子賢等[19]提出了MIFP-Apriori算法, 通過結(jié)合矩陣和改進(jìn)頻繁模式樹減少候選集冗余.

FBCM算法[20]是對MFUP算法的進(jìn)一步改進(jìn), 利用矩陣壓縮[21]的思想減小解的搜索空間, 并將算法對數(shù)據(jù)庫的掃描運(yùn)算轉(zhuǎn)化成Boole矩陣[22]的邏輯“與”運(yùn)算, 使數(shù)據(jù)庫的掃描次數(shù)降低到一次, 對增量挖掘效果較好. 但當(dāng)數(shù)據(jù)庫過大或支持度較小時, 該算法并未考慮到兩個問題： 一是原數(shù)據(jù)庫DB生成的原頻繁項(xiàng)集庫LDB的規(guī)模也會很大, 頻繁對LDB進(jìn)行掃描會降低算法性能； 二是算法挖掘過程中生成大量的候選集, 對候選集的處理也會影響算法效率. 針對上述問題, 本文基于數(shù)據(jù)庫中最頻繁項(xiàng)[23], 降低算法對LDB的掃描次數(shù), 并結(jié)合候選集剪枝思想, 減少算法生成候選集的數(shù)目, 對FBCM算法進(jìn)行優(yōu)化改進(jìn).

1 相關(guān)定義

原頻繁項(xiàng)集庫LDB: 表示原數(shù)據(jù)庫DB挖掘得到的頻繁項(xiàng)集集合;

總頻繁項(xiàng)集庫LDB∪db: 表示加入數(shù)據(jù)庫db后挖掘得到的最新頻繁項(xiàng)集集合;

最小支持度[24]閾值Sup： 支持計數(shù)大于該閾值的項(xiàng)集為頻繁項(xiàng)集;

最頻繁項(xiàng)THI： 表示數(shù)據(jù)庫中出現(xiàn)次數(shù)最多的項(xiàng)目;

項(xiàng)目個數(shù)NP： 表示從數(shù)據(jù)庫中選擇THI的個數(shù);

項(xiàng)目列表TH： 表示從數(shù)據(jù)庫中選擇THI構(gòu)成的列表;

TH的非空子集列表TI: 包含TH列表內(nèi)項(xiàng)目所有可能的非空組合.

TI中每個項(xiàng)目集的長度為1～NP(最大項(xiàng)目集), 本文將TI的每個成員稱為THIT(THI的項(xiàng)目子集),THIT的數(shù)量為2NP-1. 因?yàn)镹P通常很小, 所以THIT的數(shù)量(TI的大小)也很小. 例如NP=4, 并且2,5,8,10是從數(shù)據(jù)庫中選出的THI, 則TH={2,5,8,10}.TH的所有非空子集都是THIT(如{2,5,8}和{2,10}). 因此|TI|=24-1=15, 所以

2 FBCM算法問題分析

FBCM算法源于FUP算法, 是解決支持度不變前提下數(shù)據(jù)庫增加的規(guī)則挖掘問題, 相對于FUP算法, 該算法挖掘的效率更高, 在挖掘過程中避免了對數(shù)據(jù)庫的重復(fù)掃描. 首先將數(shù)據(jù)集轉(zhuǎn)化成Boole矩陣MatrixDB和Matrixdb, 然后利用生成的可壓縮Boole矩陣對頻繁項(xiàng)集進(jìn)行挖掘. 挖掘過程中需要多次迭代, 每次迭代前都對MatrixDB和Matrixdb進(jìn)行壓縮, 以釋放存儲空間并減少邏輯“與”操作的時間消耗. 該算法的關(guān)鍵步驟是矩陣轉(zhuǎn)換、 矩陣運(yùn)算和矩陣壓縮. 雖然FBCM算法較FUP算法性能有較大提高, 但該算法仍存在生成候選集過多、 頻繁掃描LDB的問題.

本文利用Accidents數(shù)據(jù)集和T10I4D100K數(shù)據(jù)集對FBCM算法進(jìn)行測試, 從這兩個數(shù)據(jù)集內(nèi)各抽取100條數(shù)據(jù)作為新增數(shù)據(jù)庫db, 實(shí)驗(yàn)測試結(jié)果如圖1和圖2所示. 測試1是取T10I4D100K數(shù)據(jù)集, 不斷縮小支持度所得到的算法效率. 測試2是使用Accidents數(shù)據(jù)集, 測試LDB遞增時的算法效率. 圖1和圖2的實(shí)驗(yàn)結(jié)果很好地顯示了FBCM算法存在的問題：

圖1 不同支持度下的FBCM算法效率

圖2 不同LDB的FBCM算法效率

1) 由圖1可見, 支持度為0.012時是為曲線的拐點(diǎn), 當(dāng)支持度小于拐點(diǎn)時, 算法的時間消耗快速增長, 其原因是當(dāng)支持度減小到拐點(diǎn)時, 算法產(chǎn)生的候選集數(shù)目會迅速提升, 處理大量的候選集會增加算法的時間消耗;

2) 由圖2可見, 當(dāng)LDB逐漸增大時, 曲線的斜率越來越大, 算法挖掘過程消耗的時間與LDB的增加并不成正比, 而是以類似指數(shù)的形式快速增長, 這使算法的挖掘效率越來越低, 其原因是算法每代新頻繁項(xiàng)集的確定都要多次掃描LDB, 隨著LDB逐漸增大, 頻繁的掃描耗時也會快速增加, 且LDB越大, 生成的候選集越多, 對候選集的支持計數(shù)和篩選工作耗時也會增加.

3 FBCM算法的優(yōu)化改進(jìn)

由上述分析可知, 雖然FBCM算法改進(jìn)了FUP算法頻繁掃描數(shù)據(jù)庫的問題, 但算法運(yùn)行過程中仍存在兩個影響算法效率的問題：

1) 每次迭代時都要頻繁掃描原頻繁項(xiàng)集庫LDB；

2) 每次迭代都會生成過多和無用的候選集.

因此, 為進(jìn)一步提高關(guān)聯(lián)規(guī)則增量挖掘的效率, 本文針對上述兩個問題對算法進(jìn)行優(yōu)化.

3.1 LDB掃描次數(shù)優(yōu)化

對于FBCM算法, 每次迭代產(chǎn)生候選集都需要掃描LDB, 以此判斷該候選集是否進(jìn)行后續(xù)的操作, 所以每次迭代過程中候選集的數(shù)量決定對LDB的掃描次數(shù). 因此, 只需降低迭代過程中的候選集數(shù)目即可達(dá)到算法優(yōu)化的目的.

圖3 取出THI前需掃描LDB候選集構(gòu)造

圖4 改進(jìn)后需掃描LDB的候選集構(gòu)造

與其他項(xiàng)集相比, 數(shù)據(jù)庫中的THI在每次迭代生成候選集中重復(fù)出現(xiàn)的次數(shù)最多, 并且包含THI的項(xiàng)集在LDB中也占比很大. 因此取出數(shù)據(jù)集中的THI, 使其不參與正常的迭代過程. 根據(jù)Apriori算法給出的迭代剪枝性質(zhì)[1], 每次迭代時, 候選集生成階段會忽略這些項(xiàng)目及其超集, 從而將原來迭代過程中要生成的候選集分成兩部分, 一部分像FBCM算法在迭代中處理, 而取出部分單獨(dú)處理, 進(jìn)而大量減少迭代過程中候選集的數(shù)目, 如圖3和圖4所示. 通過這種每代候選集的改變, 使算法極大降低了對LDB的掃描次數(shù).

取出的THI不參與迭代過程, 對其進(jìn)行重組生成TI集合, 利用TI中的所有THIT與每代正常迭代生成的頻繁項(xiàng)集進(jìn)行拼接組成新項(xiàng)集, 利用Boole矩陣的邏輯“與”操作對該項(xiàng)集進(jìn)行支持度計數(shù), 將數(shù)目大于支持?jǐn)?shù)閾值的項(xiàng)集加入到LDB∪db中, 通過該步對取出的項(xiàng)集進(jìn)行處理, 從而不影響整個算法結(jié)果的精度.

3.2 候選集剪枝

定理1若一個項(xiàng)X在所有頻繁(K-1)項(xiàng)集中出現(xiàn)的次數(shù)小于k-1, 則所有包含X的(K-1)項(xiàng)集都不能再與其他項(xiàng)集連接生成頻繁K項(xiàng)集.

證明： 關(guān)聯(lián)規(guī)則挖掘的剪枝性質(zhì)為頻繁項(xiàng)集的子集都是頻繁的. 根據(jù)該性質(zhì), 如果迭代過程中生成多個頻繁K項(xiàng)集, 則每個包含項(xiàng)X的K頻繁項(xiàng)集, 都會有(k-1)個包含項(xiàng)X的頻繁(K-1)項(xiàng)集作為子集, 且這些子集都是頻繁的. 由于頻繁K項(xiàng)集的個數(shù)可能有多個, 所以項(xiàng)X在所有頻繁(K-1)項(xiàng)集中出現(xiàn)的次數(shù)至少為k-1, 從而結(jié)論成立.

例如： 頻繁2項(xiàng)集

L2={{AC},{AB},{BC},{AD},{AF},{CF}},

L2中A出現(xiàn)4次,B出現(xiàn)2次,C出現(xiàn)3次,D出現(xiàn)1次,F出現(xiàn)2次, 則在用L2中項(xiàng)集生成C3候選集前將項(xiàng)集{AD}從L2中刪除.

算法優(yōu)化的目的是減少迭代過程中的候選集數(shù)目, 從而減少對LDB的掃描次數(shù). 但后續(xù)對取出的THI處理過程使算法整體的處理候選集數(shù)目并未減少, 所以為減少處理候選集數(shù)目, 本文根據(jù)定理1, 在下一代候選集生成前對其進(jìn)行剪枝, 以避免無用候選集的生成. 減少候選集數(shù)目會降低算法在支持計數(shù)和篩選工作的耗時, 從而提高算法的挖掘效率.

3.3 算法流程

對FBCM算法優(yōu)化后, 得到THIMFUP算法的流程如下.

算法1THIMFUP算法.

輸入: 原數(shù)據(jù)庫DB, 原頻繁項(xiàng)集庫LDB, 新增數(shù)據(jù)庫db;

輸出：LDB∪db.

步驟1) 矩陣轉(zhuǎn)換： 將數(shù)據(jù)庫DB和db轉(zhuǎn)換為兩個事務(wù)與項(xiàng)關(guān)系的Boole矩陣, 當(dāng)項(xiàng)在事務(wù)中存在時用“1”表示, 否則用“0”表示；

步驟2) 求出db的一頻繁項(xiàng)集, 與LDB中的一頻繁項(xiàng)集進(jìn)行交叉得到一候選集合C1, 對C1中集合計數(shù), 得到最新的一頻繁項(xiàng)集L1DB∪db, 并將LDB中變成不頻繁的項(xiàng)集單獨(dú)儲存在X中, 用于篩選后續(xù)項(xiàng)集；

步驟3) 根據(jù)得到的新一頻繁項(xiàng)集對矩陣進(jìn)行縱向精簡, 刪除不是頻繁項(xiàng)集項(xiàng)目的列；

步驟4) 按照NP從L1DB∪db取出THI, 對THI重組得到TH和TI, 對TI內(nèi)的元素THIT進(jìn)行計數(shù)處理, 保留大于支持度閾值的THIT加入到LDB∪db中；

步驟5) 利用X中存儲的項(xiàng)集對LDB進(jìn)行篩選, 并將篩選后不頻繁的項(xiàng)集存入X中, 然后對矩陣進(jìn)行橫向精簡, 刪除矩陣行中“1”的個數(shù)小于迭代次數(shù)的行；

步驟6) 用L1DB∪db中剩余的項(xiàng)集生成下一代候選集, 并用矩陣對候選集進(jìn)行支持計數(shù), 將計數(shù)大于支持?jǐn)?shù)閾值的項(xiàng)集加入到LDB∪db中, 并將這部分頻繁項(xiàng)集稱為正常迭代產(chǎn)生的頻繁項(xiàng)集, 記為La;

步驟7) 將上一代La中的項(xiàng)集與THIT連接生成新項(xiàng)集, 并利用矩陣對新項(xiàng)集進(jìn)行支持計數(shù), 將支持計數(shù)大于支持?jǐn)?shù)閾值的項(xiàng)集加入到LDB∪db中；

步驟8) 在進(jìn)行下一次迭代前, 利用定理1對La中項(xiàng)集進(jìn)行剪枝, 并用剪枝后的La進(jìn)行下一次迭代；

步驟9) 重復(fù)步驟3)～8)直到找到所有的頻繁項(xiàng)集, 算法結(jié)束.

3.4 復(fù)雜度分析

本文算法每次迭代主要分為兩步： 1) 更新LDB中原頻繁項(xiàng)集; 2) 利用更新后的頻繁項(xiàng)集生成新的候選集, 并對新候選集進(jìn)行篩選. 針對每次迭代, 下面給出算法的時間復(fù)雜度分析, 以說明本文算法與FBCM算法在時間復(fù)雜度上的關(guān)系, 并給出兩種算法的空間復(fù)雜度.

假設(shè)k表示生成的第k代項(xiàng)集, 1

在挖掘第k代頻繁項(xiàng)集時, 本文算法的第一步操作時間復(fù)雜度最差時,LDB中的m個項(xiàng)集都要統(tǒng)計其在db中的計數(shù)以更新項(xiàng)集的支持計數(shù), 對于每個項(xiàng)集采用矩陣的邏輯“與”進(jìn)行計數(shù), 只需統(tǒng)計結(jié)果中“1”的個數(shù), 開銷為d, 所以該步算法的開銷為md.

(1)

(2)

本文算法和FBCM算法的空間復(fù)雜度為O(Nω), 其中N為數(shù)據(jù)庫事務(wù)總數(shù),ω為事務(wù)的平均寬度. 算法的空間復(fù)雜度主要消耗在數(shù)據(jù)集轉(zhuǎn)化的Boole矩陣的存儲上, 即矩陣的長度×寬度.

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)環(huán)境： AMD Ryzen7 3.2 GHz 8核處理器, Windows10 64位操作系統(tǒng), 內(nèi)存為16 GB, Eclipse開發(fā)平臺. 使用JAVA編程語言進(jìn)行算法實(shí)現(xiàn).

實(shí)驗(yàn)采用的數(shù)據(jù)為從Frequent Itemset Mining Dataset Repository(http://fimi.ua.ac.be/data/)網(wǎng)站下載的關(guān)聯(lián)規(guī)則挖掘算法的經(jīng)典測試數(shù)據(jù)集. 其中, Mushroom是蘑菇生長記錄的真實(shí)數(shù)據(jù)集, 共有事務(wù)數(shù)8 124個, 事物平均長度為23, 記為A1； T10I4D100K是IBM Almaden Quest研究組生成器合成的數(shù)據(jù)集, 共有事務(wù)數(shù)100 000個, 事物平均長度為10, 記為A2.

4.2 實(shí)驗(yàn)方法與結(jié)果

實(shí)驗(yàn)均在同一環(huán)境下進(jìn)行, 為保證實(shí)驗(yàn)的客觀性與準(zhǔn)確性, 實(shí)驗(yàn)最終結(jié)果均是多次實(shí)驗(yàn)取平均值, 并且為了測試本文THIMFUP算法的性能, 實(shí)驗(yàn)將FUP算法、 FBCM算法在同等條件下的實(shí)驗(yàn)結(jié)果與其進(jìn)行對比.

實(shí)驗(yàn)用A1和A2兩個數(shù)據(jù)集對3種算法進(jìn)行測試, 以A1和A2作為DB, 在A1和A2中分別抽取100條數(shù)據(jù)作為各自的新增數(shù)據(jù)集db, 用數(shù)據(jù)集A1測試時給定NP=5, 用A2測試時, 給定NP=2.

4.2.1 生成頻繁項(xiàng)集的準(zhǔn)確性對比

根據(jù)給定的實(shí)驗(yàn)條件, 不斷縮小3種算法挖掘時的支持度閾值, 計算3種算法在不同支持度閾值下生成頻繁項(xiàng)集的數(shù)量, 實(shí)驗(yàn)結(jié)果如圖5和圖6所示. 由圖5和圖6可見, 在兩個測試數(shù)據(jù)集中, 支持度閾值越小, 3種算法挖掘得到的頻繁項(xiàng)集個數(shù)越多, 相同的支持度閾值下, 本文算法挖掘得到的頻繁項(xiàng)集數(shù)目與FUP和FBCM算法相同, 表明本文算法保證了對規(guī)則挖掘的準(zhǔn)確性, 并未犧牲挖掘結(jié)果的精度提升挖掘速度.

圖5 數(shù)據(jù)集A1在不同支持度下的頻繁項(xiàng)集數(shù)

圖6 數(shù)據(jù)集A2在不同支持度下的頻繁項(xiàng)集數(shù)

4.2.2 支持度變化算法效率對比

根據(jù)給定的實(shí)驗(yàn)條件, 不斷縮小3種算法挖掘時的支持度閾值, 比較3種算法在不同支持度閾值下的挖掘效率, 實(shí)驗(yàn)結(jié)果如圖7和圖8所示. 圖7和圖8是3種算法效率測試的對比, 由于FUP算法在同等條件下耗時過高, 為更好體現(xiàn)實(shí)驗(yàn)效果, 實(shí)驗(yàn)結(jié)果以FBCM算法作為過渡. 根據(jù)圖7和圖8, 在使用兩個數(shù)據(jù)集實(shí)驗(yàn)時, 相同的支持度閾值下, 本文算法和FBCM算法時間消耗遠(yuǎn)低于FUP算法, 并且由圖7(A)和圖8(A)可見： 在數(shù)據(jù)集A1上本文算法的效率比FBCM算法提高了50%以上, 最高達(dá)60%； 在數(shù)據(jù)集A2上提高了15%以上, 最高達(dá)50%. 隨著支持度閾值的不斷降低, 3種算法挖掘的時間消耗都在增加, 但本文算法的增加速度明顯低于FUP和FBCM算法, 并且支持度閾值越低3種算法的差距越大, 本文算法優(yōu)勢越明顯.

圖7 數(shù)據(jù)集A1在不同支持度下的算法效率對比

圖8 數(shù)據(jù)集A2在不同支持度下的算法效率對比

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

由上述實(shí)驗(yàn)結(jié)果可見, 在實(shí)驗(yàn)條件相同的前提下, 在兩個測試數(shù)據(jù)集上, 本文算法與FUP算法和FBCM算法相比性能更優(yōu). 在最佳的NP參數(shù)下, 對于支持度閾值較小、 數(shù)據(jù)集較大且生成較多頻繁項(xiàng)集數(shù)的情形, 本文算法的挖掘效率提升更明顯. 并且數(shù)據(jù)集A2和A1中的THI分布是有差異的, 根據(jù)統(tǒng)計數(shù)據(jù), 在A2中THI出現(xiàn)的頻數(shù)為7 828, 在總事物數(shù)中占比極小, 幾乎可忽略不計, 而在A1中THI的出現(xiàn)頻數(shù)占總事物數(shù)的99%. 再結(jié)合圖7(A)和圖8(A)所示的效率增長情況可知,THI在數(shù)據(jù)集中占比越高, 算法在該數(shù)據(jù)集上的性能越優(yōu)越, 而實(shí)際應(yīng)用中交易數(shù)據(jù)形成的數(shù)據(jù)集, 因?yàn)樯畋匦杵返拇嬖? 其中THI的頻率通常較高, 因此本文算法應(yīng)用價值較大.

綜上所述, 針對FBCM算法在增量挖掘過程中頻繁掃描LDB并生成大量候選集的問題, 本文提出了一種THIMFUP算法, 算法通過提取數(shù)據(jù)集中THI降低了迭代過程中候選集的數(shù)量, 減少了對LDB的掃描次數(shù), 并對取出的THI與迭代中生成的頻繁項(xiàng)集進(jìn)行拼接處理, 保證了算法挖掘的精度, 利用定理1對每代候選集進(jìn)行剪枝, 減少了算法對候選集計數(shù)和篩選的時間消耗. 實(shí)驗(yàn)結(jié)果表明, 本文算法在保證未損失挖掘結(jié)果的情況下, 效率較FBCM算法提高了15%以上, 最高達(dá)60%. 這種效率的提升與THI在數(shù)據(jù)庫中的占比有關(guān),THI在數(shù)據(jù)集中占比越高, 算法的效率提升越明顯, 而在實(shí)際應(yīng)用中交易數(shù)據(jù)集THI的占比通常較高, 從而使算法具有較大的應(yīng)用價值.