關(guān)聯(lián)規(guī)則挖掘中數(shù)據(jù)增量方式比較研究

程敏*，郭曉軍，李驍，何佶星

?

關(guān)聯(lián)規(guī)則挖掘中數(shù)據(jù)增量方式比較研究

程敏*，郭曉軍，李驍，何佶星

(西南石油大學(xué)計算機(jī)科學(xué)學(xué)院，四川成都610500）

隨著電子商務(wù)的迅速發(fā)展，不僅交易數(shù)據(jù)程爆炸式增長，而且商品類別日新月異。因此，實(shí)時地、高效地、準(zhǔn)確地獲得頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則對于商品的銷售和推薦有著現(xiàn)實(shí)的指導(dǎo)意義?，F(xiàn)有的工作針對交易數(shù)據(jù)的動態(tài)變化提出了很多增量式的挖掘算法，但只有較少的研究工作解決屬性的增量變化問題。本文設(shè)計了一個增量算法來解決商品種類增加而引起的頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則的更新問題。分析實(shí)際的賣家場景，商品的種類往往以兩種方式動態(tài)增加，即一次只增加一種商品和一次性增加多種商品，其中，前者被稱為逐一增加，后者被稱為批量增加。針對商品不同的增加方式，分別提出兩種挖掘子算法（addOneByOne與addAll），電商賣家可以根據(jù)實(shí)際情況來選擇相應(yīng)的解決方案。豐富的實(shí)驗(yàn)在真實(shí)商品交易數(shù)據(jù)集上進(jìn)行，討論了兩種子算法和經(jīng)典的Apriori算法在挖掘結(jié)果、運(yùn)行時間兩方面的性能。實(shí)驗(yàn)結(jié)果表明：1）兩種子算法所得的結(jié)果完全一致；2）最好情況下，addOneByOne算法所用平均時間比addAll少2.93倍，比Apriori快12.85倍。

增量關(guān)聯(lián)規(guī)則；數(shù)據(jù)增加方式；時間效率

引言

隨著時間的推移，數(shù)據(jù)挖掘技術(shù)逐漸被應(yīng)用到各個行業(yè)領(lǐng)域中。諸多數(shù)據(jù)挖掘算法被提出解決各類實(shí)際問題便于決策分析，如分類、聚類、關(guān)聯(lián)規(guī)則挖掘等。關(guān)聯(lián)規(guī)則挖掘[1-3]被廣泛地應(yīng)用于購物數(shù)據(jù)分析、醫(yī)療檢測、天氣預(yù)測等。目前，對關(guān)聯(lián)規(guī)則挖掘的研究已經(jīng)有很多算法被提出[4]。其中，Apriori算法是最為經(jīng)典的算法，簡單易懂，但它要求多次掃描數(shù)據(jù)庫并會產(chǎn)生大量的中間候選集。較Apriori算法而言，F(xiàn)P-tree算法[5-7]很好解決了多次掃描的問題。但是，隨著社會的發(fā)展以及關(guān)聯(lián)規(guī)則挖掘研究的深入，為了更好的解決實(shí)際問題，增量關(guān)聯(lián)規(guī)則挖掘的研究日益緊迫。

增量關(guān)聯(lián)規(guī)則的研究具有非常重要的現(xiàn)實(shí)意義。目前，已經(jīng)有很多增量關(guān)聯(lián)規(guī)則挖掘的相關(guān)算法被提出來。FUP[8,9]算法通過利用已知頻繁項(xiàng)集的支持度，過濾掉許多中間候選集，相比直接運(yùn)用Apriori算法而言，效率更高。FUP2算法[10]在FUP算法的基礎(chǔ)上進(jìn)一步做了優(yōu)化，通過利用先前的挖掘結(jié)果減少了計算出行規(guī)則的代價。IUA[11]算法研究了在有效利用已挖掘的結(jié)果的基礎(chǔ)上，最小支持度閾值發(fā)生變化時的高效更新問題，以空間代價換取時間代價，提高效率。FIUA2算法[12]掃描數(shù)據(jù)庫的次數(shù)遠(yuǎn)小于FUP算法，性能更加優(yōu)越。文獻(xiàn)[13]在引入前綴廣義表結(jié)構(gòu)的前提下，提出了一種增量式更新算法，克服了多次掃描數(shù)據(jù)庫和產(chǎn)生大量候選集的缺陷。文獻(xiàn)[14]提出了具有時間約束的增量規(guī)則挖掘算法TIDM。此外，針對時態(tài)數(shù)據(jù)庫的增量關(guān)聯(lián)規(guī)則的挖掘也有很多有重要貢獻(xiàn)的研究[15]?；贔P-tree算法的增量關(guān)聯(lián)規(guī)則挖掘的研究也有眾多有效的算法[16-19]。TDUP算法[20]提出一種三支模式解決了重復(fù)掃描數(shù)據(jù)庫和在線更新時規(guī)則的維護(hù)問題。文獻(xiàn)[21]中為維持?jǐn)?shù)據(jù)更新時的頻繁項(xiàng)集，提出了一種通過預(yù)先存儲可能的頻繁項(xiàng)集的方法提高挖掘的效率。文獻(xiàn)[22]根據(jù)時間區(qū)間來區(qū)分不同數(shù)據(jù)的重要性，提出了一種基于時間權(quán)值的增量優(yōu)化關(guān)聯(lián)規(guī)則挖掘算法。

雖然以上算法從不同角度及不同程度上解決了增量關(guān)聯(lián)規(guī)則挖掘中的一些問題，但為了更好的應(yīng)對實(shí)際問題，如何更加簡便高效地更新新增商品后的規(guī)則仍亟待解決。本文在同時考慮增加新商品前后最小支持度與最小置信度不變的同時，在保證已挖掘頻繁項(xiàng)集和規(guī)則有效的前提下，提出兩種不同的方案，從數(shù)據(jù)新增數(shù)量和新增方式的角度出發(fā)，通過實(shí)驗(yàn)研究了不同方案下算法結(jié)果的一致性及方案的有效性。本文第1節(jié)簡述了增量關(guān)聯(lián)規(guī)則的問題描述并給出了所涉及的算法描述；第2節(jié)對相關(guān)算法示例說明；第3節(jié)應(yīng)用真實(shí)數(shù)據(jù)集進(jìn)行測試并對實(shí)驗(yàn)結(jié)果加以分析；最后，對本文的工作加以總結(jié)并指出進(jìn)一步的工作方向。

1 問題描述與理論分析

1.1 增量關(guān)聯(lián)規(guī)則的描述

靜態(tài)關(guān)聯(lián)規(guī)則挖掘是在固定數(shù)據(jù)集和支持度下，發(fā)現(xiàn)數(shù)據(jù)中的頻繁項(xiàng)集及強(qiáng)關(guān)聯(lián)規(guī)則。本文研究了屬性增加的增量關(guān)聯(lián)規(guī)則挖掘。設(shè)數(shù)據(jù)集，數(shù)據(jù)集的大小，其中事務(wù)項(xiàng)集，項(xiàng)集是I的子集且為關(guān)聯(lián)規(guī)則。X在數(shù)據(jù)集中出現(xiàn)的次數(shù)為count(X)，其支持度：，若（為最小支持度，取值為0~1），稱X為頻繁項(xiàng)。規(guī)則置信度：，若則稱X→Y為強(qiáng)關(guān)聯(lián)規(guī)則。

假設(shè)已知n個商品并且均為既得頻繁項(xiàng)集，新增加m個商品且計算后這些商品也是頻繁項(xiàng)，數(shù)據(jù)模型如表1所示，得到如下結(jié)果：

…….

表1 數(shù)據(jù)模型

圖1 理論頻繁項(xiàng)集增加個數(shù)

若n=20和m=10, 20, 30, 40, 50，以長度為1、2、3的頻繁項(xiàng)集為例對比頻繁項(xiàng)增加的個數(shù)，如圖1所示，隨著新商品的增加，頻繁項(xiàng)的數(shù)量也呈現(xiàn)遞增的趨勢，尤其是三階及其以上頻發(fā)項(xiàng)的數(shù)量增加更為明顯。當(dāng)然，設(shè)置不同的最小支持度和最小置信度會得到不同的挖掘結(jié)果。理論上，最小支持度的值越小，得到的挖掘結(jié)果就越多，若最小支持度的值設(shè)置恰當(dāng)，會出現(xiàn)四階頻繁項(xiàng)集，五階頻繁項(xiàng)乃至更多階的頻繁項(xiàng)，從而得到更多的規(guī)則。

1.2 相關(guān)算法描述

根據(jù)文獻(xiàn)[23,24]，本文假設(shè)是經(jīng)過長期實(shí)踐證明的穩(wěn)定的既得頻繁項(xiàng)集（增加新商品之前）。本文在進(jìn)行增量計算時，僅使用新的交易數(shù)據(jù)集中中所包含的商品以及新增加的商品所對應(yīng)的交易數(shù)據(jù)，即中不包含新增商品之前非頻繁的商品的交易記錄。交易記錄數(shù)據(jù)集中數(shù)據(jù)表示對某一商品的購買數(shù)量。如果沒有購買某一商品，則在交易記錄數(shù)據(jù)集中對應(yīng)為0。先計算長度為1的頻繁項(xiàng)，用新增的商品在交易數(shù)據(jù)集中所對應(yīng)的數(shù)據(jù)進(jìn)行計算，得到新增頻繁項(xiàng)集。再通過與間的排列組合形成更大長度的項(xiàng)，計算其是否為頻繁項(xiàng)，然后計算該項(xiàng)中的強(qiáng)關(guān)聯(lián)規(guī)則。若前一長度的頻繁項(xiàng)集為空，則停止計算，否則繼續(xù)計算下一長度的頻繁項(xiàng)。

既得挖掘結(jié)果是一種經(jīng)過符合長期實(shí)踐，趨于穩(wěn)定的數(shù)據(jù)。不同的數(shù)據(jù)增加方式在計算時，實(shí)質(zhì)都是對不同數(shù)據(jù)的數(shù)據(jù)量統(tǒng)計，針對同一數(shù)據(jù)集，在最小支持度和最小置信度不變的條件下進(jìn)行計算，所得結(jié)果也就能夠保證一致性。

1.3 方案介紹

在此算法基礎(chǔ)上，本文提出如下兩種方案及對比參考方案：

圖2 逐一增加流程圖

圖3 批量增加流程圖

2 示例說明

設(shè)新增商品前的交易數(shù)據(jù)如表2所示，新增商品后的交易數(shù)據(jù)如表3所示，最小支持度：，最小置信度：；原商品集合，新增商品集合，故既得頻繁項(xiàng)和規(guī)則所包含的元素集合。

表2 新增商品前交易數(shù)據(jù)

表3 新增商品后的交易數(shù)據(jù)

以上三種算法得到的結(jié)果一致。

3 實(shí)驗(yàn)

本實(shí)驗(yàn)采用真實(shí)交易數(shù)據(jù)集作為測試數(shù)據(jù)集（http://download.csdn.net/detail/guoshiwei536/9213281），通過復(fù)制、交換數(shù)據(jù)確定增加項(xiàng)的數(shù)據(jù)集，從而模擬增量計算過程。使用Java語言在window10（64位，4G內(nèi)存）系統(tǒng)環(huán)境下利用myEclipse10.0軟件進(jìn)行3種方案的算法實(shí)現(xiàn)，根據(jù)不同的數(shù)據(jù)增加方式所得結(jié)果進(jìn)行對比。其中，本數(shù)據(jù)集中共約5000條交易數(shù)據(jù)，5種新商品個數(shù)以10為梯度成等差增加（10,20,30,40,50），最小支持度和最小置信度的值保持與歷史挖掘設(shè)定值一致。根據(jù)頻繁項(xiàng)長度的不同，多次試驗(yàn)，分別依次對獲取各長度的頻繁項(xiàng)集所用的平均增加時間作對比。圖3、圖4、圖5分別表示3種方式在長度為1,2,3的頻繁項(xiàng)集在10次試驗(yàn)的情況下所用平均增加時間的對比。

圖3 Frequency_len_1

圖4 Frequency_len_2

圖5 Frequency_len_3

圖3、圖4、圖5顯示，無論頻繁項(xiàng)的長度如何，隨著商品新增個數(shù)的增加，三種方式所用的增加時間都是線性增加的；頻繁項(xiàng)的長度越長，所用的時間越多；對比三種方式，的效率最高，的效率高于。

4 結(jié)語

本文依據(jù)現(xiàn)實(shí)中出現(xiàn)的增量方式的不同，提出了兩種不同情況下的增量子算法，即批量增加和單個增加。算法在最小支持度和最小置信度不變的情況下，利用已有挖掘結(jié)果，滿足不同情況下的增量計算。通過示例和實(shí)驗(yàn)證明，兩種子算法較經(jīng)典算法而言，都具有更高的挖掘效率，逐一增加的子算法較批量增加的計算方式所需的計算時間更短，效率更高，能更好的應(yīng)用到實(shí)際情況中。應(yīng)對現(xiàn)實(shí)情況類似問題時，在有限的資源和成本前提下，為管理者如何決策益以獲取最大利潤提供高效的依據(jù)選擇方式。下一步的研究目標(biāo)：推廣應(yīng)用于分布式及并行數(shù)據(jù)庫。

[1] Hipp J, Güntzer U, Nakhaeizadeh G. Algorithms for association rule mining—a general survey and comparison[J]. ACM sigkdd explorations newsletter, 2000, 2(1): 58-64.

[2] Kotsiantis S, Kanellopoulos D. Association rules mining: A recent overview[J]. GESTS International Transactions on Computer Science and Engineering, 2006, 32(1): 71-82.

[3] 張步忠, 江克勤, 張玉州. 增量關(guān)聯(lián)規(guī)則挖掘研究綜述[J]. 小型微型計算機(jī)系統(tǒng), 2016, 01:18-23.

[4] 王愛平, 王占鳳, 陶嗣干, 等. 數(shù)據(jù)挖掘中常用關(guān)聯(lián)規(guī)則挖掘算法[J]. 計算機(jī)技術(shù)與發(fā)展, 2010, 20(4): 105-108.

[5] 陸楠, 王喆, 周春光. 基于FP-tree頻集模式的FP-Growth算法對關(guān)聯(lián)規(guī)則挖掘的影響[J]. 吉林大學(xué)學(xué)報: 理學(xué)版, 2003, 41(2):180-185.

[6] Shrivastava V K, Kumar P, Pardasani K R. FP-tree and COFI Based Approach for Mining of Multiple Level Association Rules in Large Databases[J]. International Journal of Computer Science & Information Security, 2010, 7(2).

[7] Qin L X, Luo P, Shi Z Z. Efficiently Mining Frequent Itemsets with Compact FP-Tree[C]// Intelligent Information Processing Ii, Ifip Tc12/wg12.3 International Conference on Intelligent Information Processing. 2004:397-406.

[8] Cheung D W, Han J, Ng V T, et al. Maintenance of discovered association rules in large databases: An incremental updating technique[C]//Data Engineering, 1996. Proceedings of the Twelfth International Conference on. IEEE, 1996: 106-114.

[9] 王新龍, 李強(qiáng). 基于FUP算法的關(guān)聯(lián)規(guī)則增量算法的研究[J]. 微計算機(jī)信息, 2009, 25(3):279-280.

[10] Cheung D W L, Lee S D, Kao B. A General Incremental Technique for Maintaining Discovered Association Rules[C]//DASFAA. 1997, 6: 185-194.

[11] 馮玉才, 馮劍琳. 關(guān)聯(lián)規(guī)則的增量式更新算法[J]. 軟件學(xué)報, 1998, 9(4): 301-306.

[12] 朱玉全, 孫志揮, 季小俊. 基于頻繁模式樹的關(guān)聯(lián)規(guī)則增量式更新算法[J]. 計算機(jī)學(xué)報, 2003, 26(1): 91-96.

[13] 楊明, 孫志揮. 一種基于前綴廣義表的關(guān)聯(lián)規(guī)則增量式更新算法[J]. 計算機(jī)學(xué)報, 2003, 10:1318-1325.

[14] 馬元元, 孫志揮, 高紅梅. 時態(tài)數(shù)據(jù)庫中增量關(guān)聯(lián)規(guī)則的挖掘[J]. 計算機(jī)研究與發(fā)展, 2000, 12:1446-1451.

[15] Amornchewin R, Kreesuradej W. Incremental association rule mining using promising frequent itemset algorithm[C]//Information, Communications & Signal Processing, 2007 6th International Conference on. IEEE, 2007: 1-5.

[16] Ezeife C I, Su Y. Mining incremental association rules with generalized FP-tree[C]//Conference of the Canadian Society for Computational Studies of Intelligence. Springer Berlin Heidelberg, 2002: 147-160.

[17] Jian-Ping L, Ying W, Fan-Ding Y. Incremental Mining Alogorithm Pre-FP in Association Rules Based on FP-tree[C]// International Conference on NETWORKING & Distributed Computing. IEEE, 2010:199-203.

[18] 鐘勇發(fā), 呂紅兵. 基于FP-growth的關(guān)聯(lián)規(guī)則增量更新算法[J]. 計算機(jī)工程與應(yīng)用, 2004, 26:174-175.

[19] 趙巖, 姚勇, 劉志鏡. 基于 FP_tree 的頻繁項(xiàng)目集增量式更新算法[J]. 計算機(jī)工程, 2008, 34(11): 63-65.

[20] Li Y, Zhang Z H, Chen W B, et al. TDUP: an approach to incremental mining of frequent itemsets with three-way-decision pattern updating[J]. International Journal of Machine Learning and Cybernetics, 2015: 1-13.

[21] Tsai P S M, Lee C C, Chen A L P. An efficient approach for incremental association rule mining[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, 1999: 74-83.

[22] 李佳. 增量式優(yōu)化關(guān)聯(lián)規(guī)則算法研究及應(yīng)用[D]. 江蘇科技大學(xué), 2010.

[23] 曹增明, 于書舉, 賈豪杰. 多屬性變化的增量關(guān)聯(lián)規(guī)則更新研究[J]. 計算機(jī)工程與應(yīng)用, 2010, 30:138-141.

[24] 邵勇, 陳波, 方杰, 等. 基于屬性變化的增量關(guān)聯(lián)規(guī)則挖掘[J]. Computer Engineering and Applications, 2009, 45(1).

Comparison among Data Incremental Approaches in Association Rule Mining

CHENG Min*, GUO Xiaojun, LI Xiao , HE Jixing

(School of Computer Science, Southwest Petroleum University, Chengdu 610500, China)

With the development of E-commence, not only the explosive of transaction datagrows, but also the commodity categories changes rapidly. Therefore, efficient and accurate getting frequent item sets and association rules in real time has practical significance, In the present work, a lot of incremental mining algorithms have been proposed to deal with the dynamic change of transaction data. But only a few researches have been done to solve the problem of incremental change of attributes. In this paper, we design an incremental algorithm to solve the updating problem of frequent item sets and associational rules. Analysis of the actual situation of the seller, the kind of goods are often dynamically increased in two ways, add only one item at a time and add more than one at a time. Among which, the former named addOneByOne, the latter is addAll. Two kinds of mining algorithms are proposed for different ways to increase the commodity. Then the sellers can choose the appropriate solution based on the actual situation. Extensive experiments are performed on real commodity transaction data. And the performance of two seed algorithms and the classical Apriori algorithm in mining results and running time are discussed. The experimental results show that firstly, the results obtained by the seed algorithms are identical. Secondly, in the best case, the average time of addOneByOne is 2.93 times less than addAll, and it is about 12.85 times faster than Apriori algorithm.

incremental association rule, add way, efficiency

10.19551/j.cnki.issn1672-9129.2017.02.05

TP3

A

1672-9129(2017)02-0028-05

2016-12-23；

2017-01-07。

國家自然科學(xué)基金61379089。

程敏（1991-）女，四川綿陽，學(xué)生，碩士，主要研究方向：數(shù)據(jù)挖掘、關(guān)聯(lián)規(guī)則、推薦系統(tǒng)。

E-mail: cm_913@163.com

引用：程敏, 郭曉軍, 李驍, 等. 關(guān)聯(lián)規(guī)則挖掘中數(shù)據(jù)增量方式比較研究[J]. 數(shù)碼設(shè)計, 2017, 6(2): 28-32.

Cite：Cheng Min, Guo Xiaojun, Li Xiao , et al.Comparison among Data Incremental Approaches in Association Rule Mining [J]. Peak Data Science, 2017,6(2): 28-32.