關聯規則挖掘中數據增量方式比較研究

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

?

關聯規則挖掘中數據增量方式比較研究

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

(西南石油大學計算機科學學院，四川成都610500）

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

增量關聯規則；數據增加方式；時間效率

引言

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

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

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

1 問題描述與理論分析

1.1 增量關聯規則的描述

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

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

…….

表1 數據模型

圖1 理論頻繁項集增加個數

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

1.2 相關算法描述

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

既得挖掘結果是一種經過符合長期實踐，趨于穩定的數據。不同的數據增加方式在計算時，實質都是對不同數據的數據量統計，針對同一數據集，在最小支持度和最小置信度不變的條件下進行計算，所得結果也就能夠保證一致性。

1.3 方案介紹

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

圖2 逐一增加流程圖

圖3 批量增加流程圖

2 示例說明

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

表2 新增商品前交易數據

表3 新增商品后的交易數據

以上三種算法得到的結果一致。

3 實驗

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

圖3 Frequency_len_1

圖4 Frequency_len_2

圖5 Frequency_len_3

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

4 結語

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

[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] 張步忠, 江克勤, 張玉州. 增量關聯規則挖掘研究綜述[J]. 小型微型計算機系統, 2016, 01:18-23.

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

[5] 陸楠, 王喆, 周春光. 基于FP-tree頻集模式的FP-Growth算法對關聯規則挖掘的影響[J]. 吉林大學學報: 理學版, 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] 王新龍, 李強. 基于FUP算法的關聯規則增量算法的研究[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] 馮玉才, 馮劍琳. 關聯規則的增量式更新算法[J]. 軟件學報, 1998, 9(4): 301-306.

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

[13] 楊明, 孫志揮. 一種基于前綴廣義表的關聯規則增量式更新算法[J]. 計算機學報, 2003, 10:1318-1325.

[14] 馬元元, 孫志揮, 高紅梅. 時態數據庫中增量關聯規則的挖掘[J]. 計算機研究與發展, 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] 鐘勇發, 呂紅兵. 基于FP-growth的關聯規則增量更新算法[J]. 計算機工程與應用, 2004, 26:174-175.

[19] 趙巖, 姚勇, 劉志鏡. 基于 FP_tree 的頻繁項目集增量式更新算法[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] 李佳. 增量式優化關聯規則算法研究及應用[D]. 江蘇科技大學, 2010.

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

[24] 邵勇, 陳波, 方杰, 等. 基于屬性變化的增量關聯規則挖掘[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。

國家自然科學基金61379089。

程敏（1991-）女，四川綿陽，學生，碩士，主要研究方向：數據挖掘、關聯規則、推薦系統。

E-mail: cm_913@163.com

引用：程敏, 郭曉軍, 李驍, 等. 關聯規則挖掘中數據增量方式比較研究[J]. 數碼設計, 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.