基于AP-CAN的增量關聯挖掘算法研究

洪 炎，張 磊，嚴加琪

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

關聯規則學習（associate rule learning）是指從一定數據或其他信息載體中挖掘項目及對象之間的相關性，其結果可以揭示數據中隱藏的關聯模式。通常關聯規則挖掘過程主要包含兩個階段：第一階段必須從資料集合中找出所有的高頻項目組，第二階段在這些高頻項目組中產生關聯規則[1]。

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

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

1 CAN-tree算法

增量關聯規則挖掘領域主要包括Apriori增量挖掘算法、FP-tree頻繁模式增長算法和基于自然序樹的CAN-tree算法。CAN-tree采用前綴樹的結構，在構建時相同項目共用一個節點，將事務集中，每個項目按序依次插入CAN-tree中，隨之生成有序的CAN-tree，在進行增量關聯規則挖掘時，更新的事務排序可直接插入構建好的CAN-tree中。相較其他算法，CAN-tree算法的優勢在于動態數據的挖掘，只需掃描一次事務集即可構建CAN-tree，提高了增量關聯規則挖掘效率。

CAN-tree算法采用先建樹后挖掘的方法找出事務中的頻繁項集，建樹過程：

（1）按特定的序列（一般包括字典序、字母序等）為樹設計一個項目頭表；

（2）創建一個樹的根節點root；

（3）全局掃描數據庫，將每一條事務的項目依照項目頭表進行排序，對排序后每個項目x進行樹的節點插入操作；

（4）遍歷與x同名節點路徑，若其對應已建立的同名節點的父節點與執行插入事務中項x的前項名相同，則將與x項同名節點的計數增加1，否則創建一個新節點N1，新節點N1的父節點與插入事務中x項的前項名相同，按此方式直到所有項全部插入。

CAN-tree挖掘頻繁項集過程：

（1）從CAN樹節點自下而上挖掘，先找最下面的項，構建每個項的條件模式基（CPB），再順著CAN樹，找出所有包含該項的前綴路徑，即該項的條件模式基；

（2）累加每個CPB上的項的頻繁度計數，過濾低于最小支持度的項，構建條件FP-tree；

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

CAN-tree中存儲了事務集中的全部數據，當事務集條數或支持度改變時，建樹無需掃描原事務集，但大量存儲的數據使構建CAN-tree的規模過大，占用系統內存。

2 AP-CAN快速構建算法

當CAN-tree 算法的樹規模過大時，挖掘頻繁項集的效率明顯下降，在處理多事務數據庫時，為提高挖掘效率需降低CAN 樹規模。表1 第2 列為更新前事務集表，其中每條事務的項目均已按字母序排序，構建的CAN樹如圖1所示。從圖1可以看出，按字母序排序后的樹中的節點分散，在最小支持度已知條件下包含事務集中所有項，導致樹的規模過大。如果在構建CAN 樹前就篩選出不滿足最小支持度的項，讓相同的項共用一個樹節點，則可有效減小CAN 樹規模，減少挖掘頻繁項的時間。基于此，本研究提出一種先聚類后按數據量排序的AP-CAN 算法，即首先按項目的最小支持度刪除低于最小支持度的項，然后將剩余項按其支持度計數大小對每條事務重新降序排列，此方法可大大減少節點個數，削減CAN樹規模。按支持度重新排序后的事務集如表1第3列所示，構建的AP-CAN樹如圖2所示。

表1 更新前后事務集表

從圖2 可以看出AP-CAN 樹規模較小，樹中僅有7 個節點，先聚類后按數據量排序的方式較傳統的排序方式所得到的樹規模顯著減小。

圖2 AP-CAN樹

改進后的AP-CAN樹和傳統FP樹不同，有以下優點：

（1）改進后的AP-CAN 樹只需對數據庫進行一次掃描即可構造樹，而FP樹則需要對數據庫進行兩次掃描，節省了掃描數據庫所需的時間，提高后續挖掘的效率；

（2）在挖掘動態數據庫時，改進后的AP-CAN樹可在原有樹中進行修改，不受項目增減的影響，而FP樹每次改變數據庫時都需重新建樹。

3 基于AP聚類算法裁剪數據庫

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

圖3 基于項目支持度的聚類結果

3.1 增量更新排序數據庫

對于滿足最小支持度的項目集群按其支持度排序更新數據庫，將每條事務中支持度大的項目放在前面，支持度小的項目放在后面，對經過排序后的數據庫構建CAN樹時讓原本分散的節點在具有相同數據項時共用節點，所構建的CAN樹規模大大減小。

3.2 增加基于哈希樹結構的項頭表

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

3.3 改進CAN-tree結構

構建新型的CAN-tree，首先對數據庫進行預處理，基于每個項目的支持度計數對數據庫進行AP聚類劃分集群，從數據庫中刪除不頻繁的項目，根據聚類后的集群獲取頻繁項目及其支持計數，記錄頻繁項目并更新數據庫。然后，構建一個項頭表（基于哈希結構的輔助存儲表），按項目支持度對更新后數據庫中每條事務進行增量排序，對每個項目進行樹的節點插入操作。具體實現流程如圖4所示。

圖4 AP-CAN算法實現流程圖

4 實驗結果分析

實驗環境為Intel core i7-9750CPU，8GB內存，window10 操作系統，所有算法均使用python3.7編程實現。實驗使用了T10I4D100K和movieItem 兩個公開數據集，T10I4D100K數據集具有事務條數多的特點，movieItem 數據集中單個事務數據比較長，大量單個條目達500 項。實驗采用3 種挖掘算法來進行對比實驗。

4.1 基于模式樹構建時間對比實驗

將T10I4D100K 數據集分別導入APCAN、CAN-tree、FP-growth這3種不同的算法中，在最小支持度為0.1的條件下，3種算法建樹所需時間如圖5 所示。從圖5 的測試結果可以看出，FP-growth 算法在建樹時由于要對項頭表進行大量排序工作，時間效率最低；AP-CAN算法由于削減了數據集規模，故建樹時間相較于傳統CAN-tree算法效率更高。

圖5 T10I4D100K數據集下3種算法的建樹時間對比

4.2 基于T10I4D100K數據集對比實驗

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

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

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

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

圖7 T10I4D100K 數據集下3 種算法的挖掘時間對比

4.3 基于moveItem數據集對比實驗

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

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

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

在最小支持度分別為0.02、0.04、0.06、0.08、0.10條件下，3種算法的挖掘時間如圖9所示。從圖9 來看，FP-growth 算法在數據量增加時，項頭表要進行大量排序工作，而CAN-tree 算法中保留了大量非頻繁項目，增加了大量新節點，也需花費部分時間。因此，FP-growth 算法和CAN-tree 算法的挖掘時間遠遠高于AP-CAN算法的，而且隨著最小支持度的降低，AP-CAN算法的挖掘效率的提升效果越顯著。

圖9 movieItem數據集下3種算法的挖掘時間對比

綜上分析，基于AP-CAN的增量關聯挖掘算法在處理不同類型的數據集時，在誤差允許的條件下，基于不同數據量下的挖掘效率和不同支持度下的挖掘效率相近，挖掘效率約為傳統的CAN-tree算法的3倍，約為FP-growth關聯規則挖掘算法的10倍。

5 結論

綜上所述，針對動態數據本文提出了一種基于AP-CAN的增量關聯挖掘算法，該算法在引入AP聚類算法的基礎上，通過改變數據量排序方式對數據進行優化處理，增加了一個基于哈希函數輔助存儲結構對項頭表加以改進。在movieItem和T10I4D100K數據集上的實驗表明，本文提出的AP-CAN算法可有效減少CAN-tree的規模，提高增量關聯規則挖掘效率，在數據挖掘領域有較高的應用價值。