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

(1. 長(zhǎng)春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院, 長(zhǎng)春 130022； 2. 長(zhǎng)春師范大學(xué) 教育學(xué)院, 長(zhǎng)春 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)注.

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

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

1 相關(guān)定義

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

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

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

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

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

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

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

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

2 FBCM算法問(wèn)題分析

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

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

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

圖2 不同LDB的FBCM算法效率

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

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

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

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

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

2) 每次迭代都會(huì)生成過(guò)多和無(wú)用的候選集.

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

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

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

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

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

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

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

3.2 候選集剪枝

定理1若一個(gè)項(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ì), 如果迭代過(guò)程中生成多個(gè)頻繁K項(xiàng)集, 則每個(gè)包含項(xiàng)X的K頻繁項(xiàng)集, 都會(huì)有(k-1)個(gè)包含項(xiàng)X的頻繁(K-1)項(xiàng)集作為子集, 且這些子集都是頻繁的. 由于頻繁K項(xiàng)集的個(gè)數(shù)可能有多個(gè), 所以項(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)化的目的是減少迭代過(guò)程中的候選集數(shù)目, 從而減少對(duì)LDB的掃描次數(shù). 但后續(xù)對(duì)取出的THI處理過(guò)程使算法整體的處理候選集數(shù)目并未減少, 所以為減少處理候選集數(shù)目, 本文根據(jù)定理1, 在下一代候選集生成前對(duì)其進(jìn)行剪枝, 以避免無(wú)用候選集的生成. 減少候選集數(shù)目會(huì)降低算法在支持計(jì)數(shù)和篩選工作的耗時(shí), 從而提高算法的挖掘效率.

3.3 算法流程

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

算法1THIMFUP算法.

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

輸出：LDB∪db.

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

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

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

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

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

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

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

步驟8) 在進(jìn)行下一次迭代前, 利用定理1對(duì)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)集生成新的候選集, 并對(duì)新候選集進(jìn)行篩選. 針對(duì)每次迭代, 下面給出算法的時(shí)間復(fù)雜度分析, 以說(shuō)明本文算法與FBCM算法在時(shí)間復(fù)雜度上的關(guān)系, 并給出兩種算法的空間復(fù)雜度.

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

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

(1)

(2)

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

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開(kāi)發(fā)平臺(tái). 使用JAVA編程語(yǔ)言進(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)典測(cè)試數(shù)據(jù)集. 其中, Mushroom是蘑菇生長(zhǎng)記錄的真實(shí)數(shù)據(jù)集, 共有事務(wù)數(shù)8 124個(gè), 事物平均長(zhǎng)度為23, 記為A1； T10I4D100K是IBM Almaden Quest研究組生成器合成的數(shù)據(jù)集, 共有事務(wù)數(shù)100 000個(gè), 事物平均長(zhǎng)度為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)取平均值, 并且為了測(cè)試本文THIMFUP算法的性能, 實(shí)驗(yàn)將FUP算法、 FBCM算法在同等條件下的實(shí)驗(yàn)結(jié)果與其進(jìn)行對(duì)比.

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

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

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

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

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

4.2.2 支持度變化算法效率對(duì)比

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

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

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

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

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

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