基于AP-CAN的增量關(guān)聯(lián)挖掘算法研究

洪 炎，張 磊，嚴(yán)加琪

（安徽理工大學(xué)電氣與信息工程學(xué)院，安徽淮南 232001）

關(guān)聯(lián)規(guī)則學(xué)習(xí)（associate rule learning）是指從一定數(shù)據(jù)或其他信息載體中挖掘項(xiàng)目及對(duì)象之間的相關(guān)性，其結(jié)果可以揭示數(shù)據(jù)中隱藏的關(guān)聯(lián)模式。通常關(guān)聯(lián)規(guī)則挖掘過(guò)程主要包含兩個(gè)階段：第一階段必須從資料集合中找出所有的高頻項(xiàng)目組，第二階段在這些高頻項(xiàng)目組中產(chǎn)生關(guān)聯(lián)規(guī)則[1]。

1994年Agrawal等提出了Apriori算法[2]，采用先連接后剪枝的方法處理選出的候選集來(lái)獲取頻繁項(xiàng)集，該方法需要兩次掃描全局事務(wù)數(shù)據(jù)庫(kù)而生成大量候選集。為了克服Apriori算法的局限性，2000年Han等提出了基于樹(shù)型的頻繁模式增長(zhǎng)（FP-Growth）算法[3]，將提供頻繁項(xiàng)集的數(shù)據(jù)庫(kù)壓縮到一棵頻繁模式樹(shù)中，占用了更大內(nèi)存。以上方法均適用于處理靜態(tài)數(shù)據(jù)。為處理動(dòng)態(tài)數(shù)據(jù)的挖掘問(wèn)題，Leung等提出了基于自然序樹(shù)CAN-tree結(jié)構(gòu)構(gòu)建算法[4]，該算法克服了FP-tree構(gòu)建算法占用內(nèi)存大的不足，但在處理大數(shù)據(jù)集時(shí)的挖掘效率卻會(huì)降低。

CAN-tree 利用樹(shù)型存儲(chǔ)了所有數(shù)據(jù)，可以在改變數(shù)據(jù)量或最小支持度下多次挖掘。Sadat 等[5]在2015年將CAN-tree算法和FP-Growth算法相比，發(fā)現(xiàn)在最小支持度較高時(shí)，CAN-tree算法的效率更好，但在最小支持度較低時(shí)，CAN-tree算法效率低于FP-Growth算法。2008年鄒力鹍等[6]提出用子父節(jié)點(diǎn)指針替代原父子節(jié)點(diǎn)指針，可快速生成條件模式樹(shù)。2014年陳剛等[7]提出一種基于CAN-tree的快速構(gòu)造算法，通過(guò)增加基于hash表的輔助存儲(chǔ)結(jié)構(gòu)、減少項(xiàng)目的查找時(shí)間來(lái)提高算法效率。Roul等[8]在2014年提出了生成和歸并樹(shù)。但是以上方法均未改變CAN-tree存儲(chǔ)規(guī)模，導(dǎo)致不同數(shù)據(jù)量對(duì)算法的效率影響過(guò)大。為減少CAN-tree規(guī)模，在提高挖掘效率的同時(shí)優(yōu)化CAN-tree算法的穩(wěn)定性，本文提出一種基于AP-CAN的增量關(guān)聯(lián)挖掘算法。

1 CAN-tree算法

增量關(guān)聯(lián)規(guī)則挖掘領(lǐng)域主要包括Apriori增量挖掘算法、FP-tree頻繁模式增長(zhǎng)算法和基于自然序樹(shù)的CAN-tree算法。CAN-tree采用前綴樹(shù)的結(jié)構(gòu)，在構(gòu)建時(shí)相同項(xiàng)目共用一個(gè)節(jié)點(diǎn)，將事務(wù)集中，每個(gè)項(xiàng)目按序依次插入CAN-tree中，隨之生成有序的CAN-tree，在進(jìn)行增量關(guān)聯(lián)規(guī)則挖掘時(shí)，更新的事務(wù)排序可直接插入構(gòu)建好的CAN-tree中。相較其他算法，CAN-tree算法的優(yōu)勢(shì)在于動(dòng)態(tài)數(shù)據(jù)的挖掘，只需掃描一次事務(wù)集即可構(gòu)建CAN-tree，提高了增量關(guān)聯(lián)規(guī)則挖掘效率。

CAN-tree算法采用先建樹(shù)后挖掘的方法找出事務(wù)中的頻繁項(xiàng)集，建樹(shù)過(guò)程：

（1）按特定的序列（一般包括字典序、字母序等）為樹(shù)設(shè)計(jì)一個(gè)項(xiàng)目頭表；

（2）創(chuàng)建一個(gè)樹(shù)的根節(jié)點(diǎn)root；

（3）全局掃描數(shù)據(jù)庫(kù)，將每一條事務(wù)的項(xiàng)目依照項(xiàng)目頭表進(jìn)行排序，對(duì)排序后每個(gè)項(xiàng)目x進(jìn)行樹(shù)的節(jié)點(diǎn)插入操作；

（4）遍歷與x同名節(jié)點(diǎn)路徑，若其對(duì)應(yīng)已建立的同名節(jié)點(diǎn)的父節(jié)點(diǎn)與執(zhí)行插入事務(wù)中項(xiàng)x的前項(xiàng)名相同，則將與x項(xiàng)同名節(jié)點(diǎn)的計(jì)數(shù)增加1，否則創(chuàng)建一個(gè)新節(jié)點(diǎn)N1，新節(jié)點(diǎn)N1的父節(jié)點(diǎn)與插入事務(wù)中x項(xiàng)的前項(xiàng)名相同，按此方式直到所有項(xiàng)全部插入。

CAN-tree挖掘頻繁項(xiàng)集過(guò)程：

（1）從CAN樹(shù)節(jié)點(diǎn)自下而上挖掘，先找最下面的項(xiàng)，構(gòu)建每個(gè)項(xiàng)的條件模式基（CPB），再順著CAN樹(shù)，找出所有包含該項(xiàng)的前綴路徑，即該項(xiàng)的條件模式基；

（2）累加每個(gè)CPB上的項(xiàng)的頻繁度計(jì)數(shù)，過(guò)濾低于最小支持度的項(xiàng)，構(gòu)建條件FP-tree；

（3）遞歸挖掘每個(gè)條件FP-tree，累加后綴頻繁項(xiàng)集，直到條件FP-tree為空或者條件FP-tree只有一條路徑。

CAN-tree中存儲(chǔ)了事務(wù)集中的全部數(shù)據(jù)，當(dāng)事務(wù)集條數(shù)或支持度改變時(shí)，建樹(shù)無(wú)需掃描原事務(wù)集，但大量存儲(chǔ)的數(shù)據(jù)使構(gòu)建CAN-tree的規(guī)模過(guò)大，占用系統(tǒng)內(nèi)存。

2 AP-CAN快速構(gòu)建算法

當(dāng)CAN-tree 算法的樹(shù)規(guī)模過(guò)大時(shí)，挖掘頻繁項(xiàng)集的效率明顯下降，在處理多事務(wù)數(shù)據(jù)庫(kù)時(shí)，為提高挖掘效率需降低CAN 樹(shù)規(guī)模。表1 第2 列為更新前事務(wù)集表，其中每條事務(wù)的項(xiàng)目均已按字母序排序，構(gòu)建的CAN樹(shù)如圖1所示。從圖1可以看出，按字母序排序后的樹(shù)中的節(jié)點(diǎn)分散，在最小支持度已知條件下包含事務(wù)集中所有項(xiàng)，導(dǎo)致樹(shù)的規(guī)模過(guò)大。如果在構(gòu)建CAN 樹(shù)前就篩選出不滿(mǎn)足最小支持度的項(xiàng)，讓相同的項(xiàng)共用一個(gè)樹(shù)節(jié)點(diǎn)，則可有效減小CAN 樹(shù)規(guī)模，減少挖掘頻繁項(xiàng)的時(shí)間?；诖耍狙芯刻岢鲆环N先聚類(lèi)后按數(shù)據(jù)量排序的AP-CAN 算法，即首先按項(xiàng)目的最小支持度刪除低于最小支持度的項(xiàng)，然后將剩余項(xiàng)按其支持度計(jì)數(shù)大小對(duì)每條事務(wù)重新降序排列，此方法可大大減少節(jié)點(diǎn)個(gè)數(shù)，削減CAN樹(shù)規(guī)模。按支持度重新排序后的事務(wù)集如表1第3列所示，構(gòu)建的AP-CAN樹(shù)如圖2所示。

表1 更新前后事務(wù)集表

從圖2 可以看出AP-CAN 樹(shù)規(guī)模較小，樹(shù)中僅有7 個(gè)節(jié)點(diǎn)，先聚類(lèi)后按數(shù)據(jù)量排序的方式較傳統(tǒng)的排序方式所得到的樹(shù)規(guī)模顯著減小。

圖2 AP-CAN樹(shù)

改進(jìn)后的AP-CAN樹(shù)和傳統(tǒng)FP樹(shù)不同，有以下優(yōu)點(diǎn)：

（1）改進(jìn)后的AP-CAN 樹(shù)只需對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次掃描即可構(gòu)造樹(shù)，而FP樹(shù)則需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行兩次掃描，節(jié)省了掃描數(shù)據(jù)庫(kù)所需的時(shí)間，提高后續(xù)挖掘的效率；

（2）在挖掘動(dòng)態(tài)數(shù)據(jù)庫(kù)時(shí)，改進(jìn)后的AP-CAN樹(shù)可在原有樹(shù)中進(jìn)行修改，不受項(xiàng)目增減的影響，而FP樹(shù)每次改變數(shù)據(jù)庫(kù)時(shí)都需重新建樹(shù)。

3 基于AP聚類(lèi)算法裁剪數(shù)據(jù)庫(kù)

在對(duì)數(shù)據(jù)庫(kù)的每條事務(wù)排序前，首先基于數(shù)據(jù)庫(kù)中每個(gè)項(xiàng)目的支持度進(jìn)行AP聚類(lèi)，將原始數(shù)據(jù)庫(kù)劃分為兩個(gè)集群（如圖3所示），用python隨機(jī)生成含100個(gè)項(xiàng)目的事務(wù)集，在一定的最小支持度下通過(guò)AP聚類(lèi)算法分為不滿(mǎn)足最小支持度的項(xiàng)目集C1和滿(mǎn)足最小支持度的項(xiàng)目集C2。然后，從數(shù)據(jù)庫(kù)中刪除不滿(mǎn)足最小支持度的集群C1，削減了原事務(wù)集的項(xiàng)目條數(shù)，根據(jù)聚類(lèi)后的集群可以獲取事務(wù)集的頻繁項(xiàng)目及其支持度。AP聚類(lèi)后不僅會(huì)在建立基于哈希結(jié)構(gòu)的項(xiàng)頭表時(shí)免除掃描數(shù)據(jù)庫(kù)，也可以直接將低于最小支持度的項(xiàng)舍去，這樣在構(gòu)建CAN-tree前就可以通過(guò)減小樹(shù)的規(guī)模來(lái)提高算法效率。

圖3 基于項(xiàng)目支持度的聚類(lèi)結(jié)果

3.1 增量更新排序數(shù)據(jù)庫(kù)

對(duì)于滿(mǎn)足最小支持度的項(xiàng)目集群按其支持度排序更新數(shù)據(jù)庫(kù)，將每條事務(wù)中支持度大的項(xiàng)目放在前面，支持度小的項(xiàng)目放在后面，對(duì)經(jīng)過(guò)排序后的數(shù)據(jù)庫(kù)構(gòu)建CAN樹(shù)時(shí)讓原本分散的節(jié)點(diǎn)在具有相同數(shù)據(jù)項(xiàng)時(shí)共用節(jié)點(diǎn)，所構(gòu)建的CAN樹(shù)規(guī)模大大減小。

3.2 增加基于哈希樹(shù)結(jié)構(gòu)的項(xiàng)頭表

一般在構(gòu)建CAN-tree 結(jié)構(gòu)樹(shù)之前，需要設(shè)計(jì)一個(gè)包含所有項(xiàng)目的項(xiàng)頭表，將事務(wù)集中每條事務(wù)按項(xiàng)頭表進(jìn)行排序。本文把按順序查找的項(xiàng)頭表替換為哈希表的數(shù)據(jù)結(jié)構(gòu)，其查找性能比順序查找性能好。在含n個(gè)項(xiàng)的集合中查找某一項(xiàng)，按順序查找的時(shí)間復(fù)雜度為O（n），而按哈希表查找的時(shí)間復(fù)雜度為O（1）。由于在構(gòu)建CAN-tree 時(shí)頻繁地訪問(wèn)項(xiàng)頭表會(huì)花費(fèi)大量時(shí)間，而改進(jìn)后的哈希項(xiàng)頭表實(shí)現(xiàn)了項(xiàng)目的快速查找，在挖掘頻繁項(xiàng)時(shí)大大提高了算法效率。

3.3 改進(jìn)CAN-tree結(jié)構(gòu)

構(gòu)建新型的CAN-tree，首先對(duì)數(shù)據(jù)庫(kù)進(jìn)行預(yù)處理，基于每個(gè)項(xiàng)目的支持度計(jì)數(shù)對(duì)數(shù)據(jù)庫(kù)進(jìn)行AP聚類(lèi)劃分集群，從數(shù)據(jù)庫(kù)中刪除不頻繁的項(xiàng)目，根據(jù)聚類(lèi)后的集群獲取頻繁項(xiàng)目及其支持計(jì)數(shù)，記錄頻繁項(xiàng)目并更新數(shù)據(jù)庫(kù)。然后，構(gòu)建一個(gè)項(xiàng)頭表（基于哈希結(jié)構(gòu)的輔助存儲(chǔ)表），按項(xiàng)目支持度對(duì)更新后數(shù)據(jù)庫(kù)中每條事務(wù)進(jìn)行增量排序，對(duì)每個(gè)項(xiàng)目進(jìn)行樹(shù)的節(jié)點(diǎn)插入操作。具體實(shí)現(xiàn)流程如圖4所示。

圖4 AP-CAN算法實(shí)現(xiàn)流程圖

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

實(shí)驗(yàn)環(huán)境為Intel core i7-9750CPU，8GB內(nèi)存，window10 操作系統(tǒng)，所有算法均使用python3.7編程實(shí)現(xiàn)。實(shí)驗(yàn)使用了T10I4D100K和movieItem 兩個(gè)公開(kāi)數(shù)據(jù)集，T10I4D100K數(shù)據(jù)集具有事務(wù)條數(shù)多的特點(diǎn)，movieItem 數(shù)據(jù)集中單個(gè)事務(wù)數(shù)據(jù)比較長(zhǎng)，大量單個(gè)條目達(dá)500 項(xiàng)。實(shí)驗(yàn)采用3 種挖掘算法來(lái)進(jìn)行對(duì)比實(shí)驗(yàn)。

4.1 基于模式樹(shù)構(gòu)建時(shí)間對(duì)比實(shí)驗(yàn)

將T10I4D100K 數(shù)據(jù)集分別導(dǎo)入APCAN、CAN-tree、FP-growth這3種不同的算法中，在最小支持度為0.1的條件下，3種算法建樹(shù)所需時(shí)間如圖5 所示。從圖5 的測(cè)試結(jié)果可以看出，F(xiàn)P-growth 算法在建樹(shù)時(shí)由于要對(duì)項(xiàng)頭表進(jìn)行大量排序工作，時(shí)間效率最低；AP-CAN算法由于削減了數(shù)據(jù)集規(guī)模，故建樹(shù)時(shí)間相較于傳統(tǒng)CAN-tree算法效率更高。

圖5 T10I4D100K數(shù)據(jù)集下3種算法的建樹(shù)時(shí)間對(duì)比

4.2 基于T10I4D100K數(shù)據(jù)集對(duì)比實(shí)驗(yàn)

將T10I4D100K數(shù)據(jù)集分別導(dǎo)入AP-CAN、CAN-tree、FP-growth這3種不同的算法中，在最小支持度為0.3的條件下，挖掘時(shí)間結(jié)果如圖6所示。

圖6 T10I4D100K數(shù)據(jù)集下3種算法的挖掘時(shí)間。（a）AP-CAN算法；（b）CAN-tree算法；（c）FP-growth算法

從圖6 可以看出，在同一支持度和數(shù)據(jù)量的條件下，AP-CAN 算法的挖掘時(shí)間約為0.47 s，低于CANtree算法且明顯優(yōu)于FP-growth算法的挖掘時(shí)間。

為了進(jìn)一步觀察3 種算法的挖掘效率，取最小支持度為0.05，將基礎(chǔ)數(shù)據(jù)量定為40 000，每次使用不同增量進(jìn)行實(shí)驗(yàn)，結(jié)果如圖7 所示。從圖7 可以看出，AP-CAN 算法的數(shù)據(jù)挖掘時(shí)間比FP-growth 算法的挖掘時(shí)間要少，其原因在于FP-growth 算法及CAN-tree算法所構(gòu)建的樹(shù)規(guī)模過(guò)大，挖掘頻繁項(xiàng)時(shí)耗費(fèi)大量時(shí)間，而AP-CAN 算法所構(gòu)建的樹(shù)經(jīng)過(guò)AP 聚類(lèi)算法的削減后規(guī)模顯著減小。從圖7還可以看出，當(dāng)數(shù)據(jù)量逐漸增大時(shí)，樹(shù)的規(guī)模也在變大，AP-CAN 算法的低時(shí)間復(fù)雜度特性就越明顯。

圖7 T10I4D100K 數(shù)據(jù)集下3 種算法的挖掘時(shí)間對(duì)比

4.3 基于moveItem數(shù)據(jù)集對(duì)比實(shí)驗(yàn)

將movieItem 數(shù)據(jù)集分別導(dǎo)入AP-CAN、CAN-tree、FP-growth 這3 種算法中，在最小支持度為0.1 的條件下，挖掘時(shí)間結(jié)果如圖8所示。

圖8 movieItem數(shù)據(jù)集下3種算法的挖掘時(shí)間。（a）AP-CAN算法；（b）CAN-tree算法；（c）FP-growth算法

從圖8可以看出，在同一支持度和數(shù)據(jù)量的條件下，和圖6相比，對(duì)于movieItem數(shù)據(jù)集AP-CAN算法的挖掘時(shí)間約為3.26 s，大大優(yōu)于CAN-tree算法的13.30 s和FP-growth算法的27.78 s。

在最小支持度分別為0.02、0.04、0.06、0.08、0.10條件下，3種算法的挖掘時(shí)間如圖9所示。從圖9 來(lái)看，F(xiàn)P-growth 算法在數(shù)據(jù)量增加時(shí)，項(xiàng)頭表要進(jìn)行大量排序工作，而CAN-tree 算法中保留了大量非頻繁項(xiàng)目，增加了大量新節(jié)點(diǎn)，也需花費(fèi)部分時(shí)間。因此，F(xiàn)P-growth 算法和CAN-tree 算法的挖掘時(shí)間遠(yuǎn)遠(yuǎn)高于AP-CAN算法的，而且隨著最小支持度的降低，AP-CAN算法的挖掘效率的提升效果越顯著。

圖9 movieItem數(shù)據(jù)集下3種算法的挖掘時(shí)間對(duì)比

綜上分析，基于AP-CAN的增量關(guān)聯(lián)挖掘算法在處理不同類(lèi)型的數(shù)據(jù)集時(shí)，在誤差允許的條件下，基于不同數(shù)據(jù)量下的挖掘效率和不同支持度下的挖掘效率相近，挖掘效率約為傳統(tǒng)的CAN-tree算法的3倍，約為FP-growth關(guān)聯(lián)規(guī)則挖掘算法的10倍。

5 結(jié)論

綜上所述，針對(duì)動(dòng)態(tài)數(shù)據(jù)本文提出了一種基于AP-CAN的增量關(guān)聯(lián)挖掘算法，該算法在引入AP聚類(lèi)算法的基礎(chǔ)上，通過(guò)改變數(shù)據(jù)量排序方式對(duì)數(shù)據(jù)進(jìn)行優(yōu)化處理，增加了一個(gè)基于哈希函數(shù)輔助存儲(chǔ)結(jié)構(gòu)對(duì)項(xiàng)頭表加以改進(jìn)。在movieItem和T10I4D100K數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文提出的AP-CAN算法可有效減少CAN-tree的規(guī)模，提高增量關(guān)聯(lián)規(guī)則挖掘效率，在數(shù)據(jù)挖掘領(lǐng)域有較高的應(yīng)用價(jià)值。