楊 勇, 張 磊, 曲福恒, 劉俊杰, 陳 強

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

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

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

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

1 相關定義

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

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

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

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

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

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

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

TI中每個項目集的長度為1～NP(最大項目集), 本文將TI的每個成員稱為THIT(THI的項目子集),THIT的數(shù)量為2NP-1. 因為NP通常很小, 所以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ù)庫的重復掃描. 首先將數(shù)據(jù)集轉(zhuǎn)化成Boole矩陣MatrixDB和Matrixdb, 然后利用生成的可壓縮Boole矩陣對頻繁項集進行挖掘. 挖掘過程中需要多次迭代, 每次迭代前都對MatrixDB和Matrixdb進行壓縮, 以釋放存儲空間并減少邏輯“與”操作的時間消耗. 該算法的關鍵步驟是矩陣轉(zhuǎn)換、 矩陣運算和矩陣壓縮. 雖然FBCM算法較FUP算法性能有較大提高, 但該算法仍存在生成候選集過多、 頻繁掃描LDB的問題.

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

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

圖2 不同LDB的FBCM算法效率

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

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

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

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

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

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

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

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

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

圖3 取出THI前需掃描LDB候選集構造

圖4 改進后需掃描LDB的候選集構造

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

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

3.2 候選集剪枝

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

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

例如： 頻繁2項集

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中項集生成C3候選集前將項集{AD}從L2中刪除.

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

3.3 算法流程

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

算法1THIMFUP算法.

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

輸出：LDB∪db.

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

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

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

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

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

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

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

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

步驟9) 重復步驟3)～8)直到找到所有的頻繁項集, 算法結束.

3.4 復雜度分析

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

假設k表示生成的第k代項集, 1

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

(1)

(2)

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

4 實驗分析

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

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

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

4.2 實驗方法與結果

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

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

4.2.1 生成頻繁項集的準確性對比

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

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

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

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

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

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

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

4.3 實驗結果分析

由上述實驗結果可見, 在實驗條件相同的前提下, 在兩個測試數(shù)據(jù)集上, 本文算法與FUP算法和FBCM算法相比性能更優(yōu). 在最佳的NP參數(shù)下, 對于支持度閾值較小、 數(shù)據(jù)集較大且生成較多頻繁項集數(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%. 再結合圖7(A)和圖8(A)所示的效率增長情況可知,THI在數(shù)據(jù)集中占比越高, 算法在該數(shù)據(jù)集上的性能越優(yōu)越, 而實際應用中交易數(shù)據(jù)形成的數(shù)據(jù)集, 因為生活必需品的存在, 其中THI的頻率通常較高, 因此本文算法應用價值較大.

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