基于緩沖區(qū)技術(shù)的增量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法

劉雯婷，周 軍

基于緩沖區(qū)技術(shù)的增量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法

劉雯婷，周 軍

（遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院，遼寧 錦州 121001）

利用傳統(tǒng)的FP-tree算法對(duì)增量數(shù)據(jù)進(jìn)行挖掘，需要多次建樹(shù)，效率較低。CAN-tree算法雖避免了多次建樹(shù)，但當(dāng)數(shù)據(jù)增量改變時(shí)，需多次更新樹(shù)，并且伴隨有數(shù)據(jù)丟失的現(xiàn)象發(fā)生。針對(duì)以上問(wèn)題，提出了一種基于緩沖區(qū)技術(shù)的增量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法，算法利用緩沖區(qū)技術(shù)避免數(shù)據(jù)丟失的情況發(fā)生，有效提高關(guān)聯(lián)規(guī)則的挖掘效率，實(shí)驗(yàn)結(jié)果表明算法是有效的。

增量數(shù)據(jù)；關(guān)聯(lián)規(guī)則；緩沖區(qū)

隨著互聯(lián)網(wǎng)的飛速發(fā)展，大數(shù)據(jù)和云計(jì)算已成為學(xué)術(shù)界的熱點(diǎn)研究對(duì)象。伴隨信息時(shí)代的不斷發(fā)展，各行業(yè)積累了海量數(shù)據(jù)，人們希望通能夠過(guò)技術(shù)的進(jìn)步來(lái)有效存儲(chǔ)并挖掘這些數(shù)據(jù)，關(guān)聯(lián)規(guī)則技術(shù)是數(shù)據(jù)挖掘中的重要部分，主要用于發(fā)現(xiàn)事務(wù)數(shù)據(jù)庫(kù)中項(xiàng)與項(xiàng)間的隱藏聯(lián)系。目前大多數(shù)的增量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法都是在Apriori算法[1]以及FP-Growth算法[2]上進(jìn)行改進(jìn)所得到的。牛海玲等[3]將Apriori算法進(jìn)行并行處理，引入矩陣從而有效減少掃描數(shù)據(jù)庫(kù)的次數(shù)，利用局部和全局剪枝方法來(lái)減小候選項(xiàng)集數(shù)目。易彤等[4]在FP-tree的基礎(chǔ)上引入支持度函數(shù)概念，避免大量候選項(xiàng)集的生成。程廣等[5]將FP-Growth算法與MapReduce方法相結(jié)合，提高關(guān)聯(lián)規(guī)則挖掘效率。但上述這些改進(jìn)算法仍存在諸多問(wèn)題，需要多次掃描數(shù)據(jù)庫(kù)，當(dāng)數(shù)據(jù)量改變時(shí)需重新建樹(shù)，在挖掘過(guò)程中，因?yàn)橐４骓?xiàng)集信息，需多次遞歸生成條件FP-tree，浪費(fèi)大量時(shí)間和空間。為克服上述這些問(wèn)題，Leung等[6]提出了CAN-tree算法，項(xiàng)目按用戶指定的順序（字母序、字典序等）排序后，掃描2次數(shù)據(jù)庫(kù)即可完成建樹(shù)工作。鄒力鵾等[7]和陳剛等[8]通過(guò)將父子節(jié)點(diǎn)結(jié)構(gòu)改為子父節(jié)點(diǎn)結(jié)構(gòu)，來(lái)提高構(gòu)造條件模式基的速度。胡軍等[9]使用數(shù)據(jù)量排序替代用戶指定的排序方法，提出基于數(shù)據(jù)量排序的CAN-tree算法，減小樹(shù)的規(guī)模。但上述方法依然不能解決當(dāng)數(shù)據(jù)增量到來(lái)時(shí)由于到達(dá)速度過(guò)快或處理不及時(shí)所造成的數(shù)據(jù)丟失等問(wèn)題。針對(duì)上述這些問(wèn)題提出了基于緩沖區(qū)的關(guān)聯(lián)規(guī)則挖掘算法，能夠防止數(shù)據(jù)丟失并且提高頻繁項(xiàng)集挖掘效率。

1 CAN-tree算法

1.1 算法概述

CAN-tree是Leung所提出的針對(duì)增量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘問(wèn)題的算法。CAN-tree采用了前綴樹(shù)結(jié)構(gòu)從而讓更多的相同項(xiàng)合并在一起。算法要求事務(wù)中的各個(gè)項(xiàng)按照某種用戶指定的順序(一般采用字典序、字母序等)排序后再進(jìn)行構(gòu)建CAN-tree，這樣當(dāng)新數(shù)據(jù)到來(lái)時(shí)可以直接插入到原來(lái)的CAN-tree結(jié)構(gòu)中，避免了重新建樹(shù)和再次掃描數(shù)據(jù)庫(kù)，提高關(guān)聯(lián)規(guī)則增量更新的效率。

定義1 設(shè)項(xiàng)的集合為={1,2,......,i}，={1,2,......,t}為事務(wù)集合。每條事務(wù)t包含的項(xiàng)集為的子集。

定義2 項(xiàng)的集合成為項(xiàng)集，若某項(xiàng)集包含個(gè)項(xiàng)，則稱其為-項(xiàng)集。

定義4 用戶設(shè)置最小支持度閾值為minsup，若項(xiàng)集I出現(xiàn)的頻率不小于minsup，則項(xiàng)集I為頻繁項(xiàng)集[10]。

1.2 算法構(gòu)建過(guò)程

(1)掃描事務(wù)數(shù)據(jù)庫(kù)DB，獲得各數(shù)據(jù)項(xiàng)以及支持度計(jì)數(shù)，按指定順序?qū)⑹聞?wù)排序并創(chuàng)建根節(jié)點(diǎn)root。

(2)將完成排序的事務(wù)逐項(xiàng)按照步驟(3)的方法插入樹(shù)中。

(3)遍歷與事務(wù)中項(xiàng)目同名的路徑，如果項(xiàng)目所對(duì)應(yīng)的相同節(jié)點(diǎn)的父親結(jié)點(diǎn)與插入的項(xiàng)目前項(xiàng)名字相同，則將與相同的結(jié)點(diǎn)計(jì)數(shù)進(jìn)行加一操作，否則，創(chuàng)建一個(gè)新結(jié)點(diǎn)，將新結(jié)點(diǎn)的計(jì)數(shù)設(shè)置為1并將其鏈接到具有相同前項(xiàng)名的結(jié)點(diǎn)之中。

(4)將事務(wù)數(shù)據(jù)庫(kù)中的所有數(shù)據(jù)進(jìn)行插入操作，完成CAN-tree的構(gòu)建工作。

2 AB-tree算法

2.1 提出背景

當(dāng)建立FP-tree時(shí)，需掃描數(shù)據(jù)庫(kù)來(lái)獲取各個(gè)項(xiàng)的支持度計(jì)數(shù)及排序，當(dāng)最小支持度或數(shù)據(jù)量發(fā)生改變時(shí)，需要重新建樹(shù)。CAN-tree算法則與FP-tree算法不同，項(xiàng)的順序確定后，CAN-tree結(jié)構(gòu)即是唯一的，數(shù)據(jù)量發(fā)生改變或最小支持度改變時(shí)，結(jié)構(gòu)不變，但數(shù)據(jù)量改變時(shí)，需要多次更新樹(shù)，更改樹(shù)的中每個(gè)節(jié)點(diǎn)的支持度計(jì)數(shù)，浪費(fèi)資源，并且伴隨有數(shù)據(jù)丟失的情況出現(xiàn)。

針對(duì)上述問(wèn)題提出了一種基于緩沖區(qū)技術(shù)的AB-tree算法，通過(guò)緩沖區(qū)防止數(shù)據(jù)丟失的情況發(fā)生并且提高挖掘效率。緩沖區(qū)是指在內(nèi)存中預(yù)留出指定大小的空間用來(lái)對(duì)輸入(輸出)的數(shù)據(jù)進(jìn)行臨時(shí)存儲(chǔ)。使用緩沖區(qū)技術(shù)能減少實(shí)際物理讀寫(xiě)次數(shù)，創(chuàng)建緩沖區(qū)時(shí)就分配好內(nèi)存，可重復(fù)使用，有效減少動(dòng)態(tài)分配和回收內(nèi)存的次數(shù)。

2.1 算法偽代碼

輸入：數(shù)據(jù)集DB

輸出：頻繁項(xiàng)集FI

(1)data=preproccess(DB)//預(yù)處理數(shù)據(jù)集，將商品按序編碼

(2)tree = createTree(data)//建立CAN-tree

(3)FI_Can = findFI(tree)//查找CAN-tree中頻繁項(xiàng)集大于最小支持度的項(xiàng)集

(4)If Cache_size >= Cache_threshold: //如果緩沖區(qū)中數(shù)據(jù)的數(shù)量大于預(yù)設(shè)值

(5)FI = FUP (FI_Can. FI_AB)//通過(guò)FUP算法查找滿足條件的頻繁項(xiàng)集FI

圖1和圖2分別為CAN-tree算法以及AB-tree算法處理數(shù)據(jù)的流程。

圖1 CAN-tree算法處理流程

圖2 AB-tree算法處理流程

從中可以看到，采用傳統(tǒng)的CAN-tree算法時(shí)，每增加1條數(shù)據(jù)，需要更新樹(shù)中節(jié)點(diǎn)計(jì)數(shù)，當(dāng)數(shù)據(jù)大量快速到達(dá)時(shí)，容易造成數(shù)據(jù)丟失；當(dāng)新數(shù)據(jù)到達(dá)時(shí)間間隔較大時(shí)，需要等待較長(zhǎng)時(shí)間。AB-tree算法利用緩沖區(qū)技術(shù)，有效避免數(shù)據(jù)丟失現(xiàn)象發(fā)生，當(dāng)新數(shù)據(jù)到達(dá)時(shí)間間隔較大時(shí)，由于并行處理，可以提高算法的挖掘效率。

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

3.1 建樹(shù)過(guò)程

假設(shè)原始數(shù)據(jù)庫(kù)如表1所示，掃描1次數(shù)據(jù)庫(kù)，獲得每個(gè)項(xiàng)集的支持度計(jì)數(shù)如表2所示并建立如圖3所示的CAN-tree，設(shè)置最小支持度minsup=10%。

表1 原始數(shù)據(jù)庫(kù)DB

表2 項(xiàng)的支持度計(jì)數(shù)

圖3 CAN-tree

根據(jù)掃描數(shù)據(jù)庫(kù)后得到的各項(xiàng)支持度計(jì)數(shù)以及最小支持度閾值（即≥3.7），求得頻繁一項(xiàng)集為{a} {c} j5i0abt0b {e} {f}，通過(guò)頻繁一項(xiàng)集構(gòu)造候選二項(xiàng)集為{a,b} {a,c} {a,d} {a,e} {a,f} {b,c} {b,d} {b,e} {b,f}{c,d} {c,e} {c,f} {d,e} {d,f}{e,f}，掃描CAN-tree，得到候選二項(xiàng)集中每個(gè)項(xiàng)出現(xiàn)的次數(shù)并將其所占的比率與所設(shè)定的minsup進(jìn)行比較，大于minsup的即為頻繁二項(xiàng)集，上述例子中L2={{a,c} {a,e} {a,f} {b,c} {b,f} {c,d} {c,f} {d,f} {e,f}}同理，頻繁三項(xiàng)集{c,d,f}。

3.2 增量數(shù)據(jù)的處理

隨著信息時(shí)代的發(fā)展，要求對(duì)數(shù)據(jù)的處理要更加迅速準(zhǔn)確。由于增量數(shù)據(jù)隨時(shí)間變化不斷更新且數(shù)據(jù)量巨大，因此只能對(duì)數(shù)據(jù)進(jìn)行有限次數(shù)的掃描，而且不能將其全部放入內(nèi)存之中，往往只能選中其中重要的數(shù)據(jù)將其存入計(jì)算機(jī)中[11]。許多人選擇滑動(dòng)窗口技術(shù)來(lái)解決增量數(shù)據(jù)的更新問(wèn)題，但當(dāng)窗口滑動(dòng)時(shí)，要?jiǎng)h除樹(shù)中原有的舊事物中的項(xiàng)，需頻繁更新樹(shù)結(jié)構(gòu)，開(kāi)銷(xiāo)巨大。為了解決上述問(wèn)題，本文采用了緩沖區(qū)技術(shù)，預(yù)留出指定空間來(lái)對(duì)更新的數(shù)據(jù)進(jìn)行存儲(chǔ)，避免頻繁更新樹(shù)結(jié)構(gòu)以及數(shù)據(jù)丟失從而提高算法效率。將新增的每一條數(shù)據(jù)存入緩沖區(qū)，設(shè)置緩沖區(qū)大小為5。新增數(shù)據(jù)庫(kù)如表3所示。

表3 新增數(shù)據(jù)庫(kù)db

建樹(shù)與挖掘過(guò)程與原始數(shù)據(jù)庫(kù)一致，最終得到頻繁項(xiàng)集為{a} {c} j5i0abt0b {e} {c,e} {d,e}。

增量數(shù)據(jù)與靜態(tài)數(shù)據(jù)有所不同，具有實(shí)時(shí)性并且與靜態(tài)數(shù)據(jù)挖掘相比過(guò)程更加復(fù)雜，一些在原數(shù)據(jù)庫(kù)中偶然發(fā)生的事務(wù)，在接下來(lái)的時(shí)間段內(nèi)很可能經(jīng)常發(fā)生。本文利用頻繁項(xiàng)集的性質(zhì)：若數(shù)據(jù)庫(kù)由若干部所分組成，其中一個(gè)項(xiàng)集是頻繁項(xiàng)集，則它至少在一個(gè)部分中是頻繁的。證明過(guò)程如下。

假設(shè)項(xiàng)集L為數(shù)據(jù)庫(kù)DB中的頻繁項(xiàng)集，但L在DB的每個(gè)部分中都是非頻繁項(xiàng)集，設(shè)最小支持度為s，DB的元素總數(shù)為n，DB中每一部分的元素個(gè)數(shù)分別為12...。

證明 設(shè)L為數(shù)據(jù)庫(kù)S中的頻繁項(xiàng)集，數(shù)據(jù)庫(kù)S由原始數(shù)據(jù)庫(kù)S1和新增數(shù)據(jù)庫(kù)S2構(gòu)成，若L在S1和S2中均為非頻繁項(xiàng)集，則L在S1和S2中支持度分別小于s*S1、s*S2，則S的總支持度S.count

設(shè)原始數(shù)據(jù)庫(kù)為DB，新增數(shù)據(jù)庫(kù)為db，當(dāng)數(shù)據(jù)更新時(shí)，會(huì)出現(xiàn)下面4種情況：(1)項(xiàng)集c在DB和db中均為頻繁項(xiàng)集；(2)項(xiàng)集c在DB中為頻繁項(xiàng)集，在db中為非頻繁項(xiàng)；(3)項(xiàng)集c在db中為頻繁項(xiàng)集，在DB中為非頻繁項(xiàng)；(4)項(xiàng)集c在DB和db中均為非頻繁項(xiàng)集。

在(1)的情況下，c一定為頻繁項(xiàng)集，(4)的情況下，c一定為非頻繁項(xiàng)集，對(duì)于情況(2)和(3)，利用公式，確定c是否為頻繁項(xiàng)集。上述例子的頻繁項(xiàng)集為{a} {c} j5i0abt0b {e} {f} {a,c} {a,e} {a,f} {c,d} {c,f} {d,f} {c,e}。

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

實(shí)驗(yàn)數(shù)據(jù)由數(shù)據(jù)模擬器產(chǎn)生，設(shè)置最小支持度為10%，緩沖區(qū)大小設(shè)置為1 000。實(shí)驗(yàn)環(huán)境如下：Intel(R) Xeon(R) CPU@2.30 GHz，內(nèi)存大小為13 GB，操作系統(tǒng)為L(zhǎng)inux，開(kāi)發(fā)環(huán)境為Python。

實(shí)驗(yàn)從2方面進(jìn)行，一方面比較本文算法與CAN-tree算法的建樹(shù)時(shí)間，另一方面比較AB-Tree算法與CAN-tree算法挖掘關(guān)聯(lián)規(guī)則的時(shí)間，從圖4可以看出當(dāng)數(shù)據(jù)增量式到來(lái)時(shí)，由于CAN-tree算法需要隨著數(shù)據(jù)到達(dá)更新樹(shù)中節(jié)點(diǎn)的計(jì)數(shù)，時(shí)間較長(zhǎng)；而本文提出的算法，由于利用緩沖區(qū)技術(shù)并行計(jì)算，隨著數(shù)據(jù)量增多，算法優(yōu)勢(shì)明顯。從圖5可以看出，由于本文無(wú)需構(gòu)建頻繁模式基，挖掘頻繁項(xiàng)集的時(shí)間小于CAN-tree算法，并且本文算法隨著數(shù)據(jù)到達(dá)的時(shí)間間隔增大，優(yōu)勢(shì)更加明顯。

圖4 算法建樹(shù)時(shí)間對(duì)比圖

圖5 算法挖掘時(shí)間對(duì)比圖

4 結(jié)束語(yǔ)

提出了一種基于緩沖區(qū)的增量數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法，該算法的主要特點(diǎn)為利用緩沖區(qū)技術(shù)實(shí)現(xiàn)并行計(jì)算，提高挖掘效率的同時(shí)能夠有效防止數(shù)據(jù)丟失的現(xiàn)象發(fā)生并且隨著數(shù)據(jù)到達(dá)時(shí)間間隔增大，優(yōu)勢(shì)更加明顯，實(shí)驗(yàn)結(jié)果表明算法有效。

[1] Agrawal R, Iminelinski T, Swami A. Mining association rules between sets of items in large databases[C]//ACM SIGMOD Record. ACM, Washington, D. C, 1993: 207-216.

[2] Ghemawat S, Gobioff H, Leung Shun-tak. The Google FileSystem [C]//Proceedings of the 19th Symposium on Operating Systems Principles. New York, USA: ACM Press, 2003: 29-43.

[3] 牛海玲. 魯慧民, 劉振杰. 基于Spark的Apriori算法的改進(jìn)[J]. 東北師大學(xué)報(bào): 自然科學(xué)版, 2016(1): 84-89.

[4] 易彤, 徐寶文, 吳方君. 一種基于FP樹(shù)的挖掘關(guān)聯(lián)規(guī)則的增量更新算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2004, 27(5): 703-710.

[5] 程廣, 王曉峰. 基于MapReduce的并行關(guān)聯(lián)規(guī)則增量更新算法[J]. 計(jì)算機(jī)工程, 2016(2): 21-32.

[6] Leung C K S, Khan Q I, Hoque T. CanTree: a tree structure for efficient incremental mining of frequent patterns[C]// Fifth IEEE International Conference on Data Mining (ICDM'05), IEEE, 2005: 8.

[7] 鄒力鹍, 張其善. 基于CAN-樹(shù)的高效關(guān)聯(lián)規(guī)則增量挖掘算法[J]. 計(jì)算機(jī)工程, 2008, 34(3): 29-31.

[8] 陳剛, 閆英戰(zhàn), 劉秉權(quán). 一種基于CAN-tree快速構(gòu)建算法[J]. 微電子學(xué)與計(jì)算機(jī), 2014(1): 76-82.

[9] 胡軍，潘皓安. 基于Can樹(shù)的關(guān)聯(lián)規(guī)則增量跟新算法改進(jìn)[J]. 重慶郵電大學(xué)學(xué)報(bào): 自然科學(xué)版, 2018, 30(4): 558-563.

[10] Jiawei Han, Micheline Kamber, Jian Pei, 等. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 機(jī)械工業(yè)出版社, 2012: 159-160.

[11] Wang H, Li F, Tang D, et al. Research on data stream mining algorithm for frequent itemsets based on sliding window model[C]//IEEE, International Conference on Big Data Analysis. IEEE, 2017: 259-263.

Algorithm in Mining Incremental Data Association Rules Based on Buffer Technology

LIU Wen-ting, ZHOU Jun

（School of Electronics & Information Engineering, Liaoning University of Technology, Jinzhou 121001, China）

Using traditional FP-tree Algorithm to mine incremental data requires building trees many times, which is inefficient. Although tree algorithm can avoid building trees many times, it needs to update trees many times when the data increment changes, and the phenomenon of data loss occurs. To solve the above problems, algorithm in mining incremental data association rules based on buffer technology is proposed. The algorithm uses buffer technology to avoid data loss and effectively improve the efficiency of mining association rules. The correctness of the algorithm can be proved by experiments.

incremental data; association rules; buffer technology

TP301.6

A

1674-3261(2020)02-0071-04

10.15916/j.issn1674-3261.2020.02.001

2019-12-11

遼寧省科學(xué)技術(shù)基金(201602372)

劉雯婷(1995-)，女，遼寧錦州人，碩士生。

周 軍(1964-)，女，遼寧錦州人，教授，博士。

責(zé)任編校：孫 林