淺談加權頻繁項集挖掘的研究進展

房新秀

摘要：加權頻繁項集挖掘是目前研究熱點之一。自從關聯規則挖掘提出以來，大部分的研究工作都圍繞頻繁項集挖掘問題進行。傳統的關聯挖掘算法往往忽略數據庫中各個項目的重要程度區別，因此利用加權關聯規則是有意義的。十幾年來，學者們從不同的角度進行改進從而提高挖掘加權頻繁項集算法的效率。本文首先分析了頻繁項集挖掘現狀，其次對加權頻繁項集挖掘進行深入分析，最后通過對比頻繁項集與加權頻繁項集算法，對未來的工作進行了展望。

關鍵詞：關聯規則;頻繁項集;加權關聯規則;加權頻繁項集;算法

中圖分類號：TP301.6? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）27-0225-02

Abstract： Mining frequent weighted itemsets is one of the hotspots of research at present. Since the association rule mining was put forward， most of the research work has focused on frequent itemset mining. Traditional association mining algorithms often ignore the differences between items in the database in importance， so it is meaningful to use weighted association rules. For more than a decade， Scholars have improved the efficiency of the mining weighted frequent itemset algorithm from different angles. Firstly ， this paper analyzes the current situation of frequent itemset mining， then makes an in-depth analysis of weighted frequent itemset mining， and finally looks forward to the future work by comparing the frequent itemset algorithm and the weighted frequent itemset algorithm.

Key words：asocciation rule; frequent itemsets; weight asocciation rule; weighted frequent itemsets; algorithm

1 頻繁項集挖掘現狀

自從Agrawal在1993年首次提出關聯規則[1-2]分析問題后，大部分的研究工作都圍繞頻繁項集挖掘問題進行。目前已經提出了許多算法來挖掘頻繁項集。這些算法分為靜態挖掘和動態挖掘。靜態挖掘又分為兩類：（1）使用“候選生成”方法的算法;（2）使用“模式增長”方法的算法。同時，頻繁項集挖掘方法并不只是局限于挖掘關聯規則，還可以廣泛應用于相關性分析、孤立點分析、分類和聚類等，多種數據挖掘任務和入侵檢測、序列模式、Web挖掘、top-k頻繁項集等多種數據挖掘應用和數據分析處理任務中。因此，頻繁項集挖掘問題是一個具有重要理論意義和廣闊應用背景的研究課題，收到理論界和產業界的廣泛重視。

2 加權頻繁項集挖掘現狀

傳統的關聯挖掘算法往往忽略數據庫中各個項目的重要程度的區別。因此，在分析實際數據時，利用加權關聯規則是有意義的。它發現那些出現頻率較低但權值比較大的重要頻繁項集。

Ramkumar（1998）等人首次提出挖掘加權頻繁項集的問題。由Yun和Leggett發起的第一種方法是使用平均函數來評估權重的一個項目集，當向其添加新項時，項集的權重可以增加或減少，因此不滿足向下封閉屬性。為了解決這個問題，Yun等人 （2006）提出了一種上限模型，其采用最大權重值作為每個交易的權重上限，并且每個項目在預定的權重范圍內被分配不同的權重值。后來lan等人在2015年提出了序列最大權重模型，以加強對子序列的加權支持的上限，從而減少數據挖掘中候選人數。第一種方法在挖掘過程中同時考慮項目集的權重和支持。然而，這種方法認為事務是相同的，但是在實踐中，事務具有不同的重要性。

第二種方法源于Tao等人在2003年所做的研究，該研究通過計算事務中項目權重的算術平均值來得到事務權重。首先，項集的加權支持度反映了項集支持和事務具有不同的重要性。其次是它滿足向下封閉屬性。Tao等人在2003年提出了基于生成和檢查候選者策略的算法。但是這個算法因為多次掃描數據庫而耗費時間。Vo，Coenen在2013年提出了WIT-FWIs-Diff算法，該算法采用了WIT數據結構，其中WIT樹是用于存儲權值的IT樹的擴展，WIT-FWIs-Diff算法僅掃描數據庫一次，并采用diffset策略在WIT樹上挖掘FWIs，從而達到高效的查找。但是該算法的缺點是它消耗了很多內存來存儲tidsets，因此它在稀疏數據庫上效果不明顯。Nguyen在2016年提出了IWS算法[3]，IWS算法算法采用IWS數據結構，通過消除tidsets的位向量中的所有0來減少存儲集的內存。但是IWS算法適用于稀疏數據集，對于密集數據集，它具有相反的效果。Lee等人在2017年提出了兩種算法：FWI*TCD[4]、FWI*WSD[4]算法。以上兩種算法均采用了一種新的前綴樹結構來壓縮數據，但是這兩種算法必須通過多次遍歷樹來挖掘FWIs，因此花費了很多時間。

最近Huong Bui等人在2018年提出了一種基于加權N列表的算法[5]，用于挖掘頻繁加權項集（稱為NFWI），該算法使用加權N列表結構（WN列表），即N列表的括展。大大提高了算法的效率。

目前還有許多研究關注WD（Weighted Database）中的模式挖掘，挖掘加權頻繁效用項集[6]、挖掘加權項集平行方法、挖掘加權最大頻繁項集[7]、挖掘不頻繁的加權頻繁項集、加權可消除模式[8]、有趣的加權頻繁模式挖掘、加權時態關聯規則挖掘、等等。但是在挖掘效率方面仍然存在著一定的不足： （1）在掃描數據庫方面：許多算法需要多次掃描數據庫，當數據量很大時，需要消耗的時間更長影響了挖掘效率。（2）在數據項權值設置方面：權值設置過高會導致小概率事件中規則的丟失，權值設置過低容易挖掘出對用戶無價值的規劃。 （3）在連接和剪枝策略方面，每連接一次都會產生大量的頻繁項集，特別是候選2-項集，當數據增多時，產生的候選項集幾乎稱爆炸式增長，降低了挖掘效率。

3 結束語

通過分析以上算法，比較頻繁項集和加權頻繁項集算法之后，采用滿足向下閉合屬性去挖掘加權頻繁項集。在未來的工作中，通過分析現有算法存在的不足，在已有算法的基礎上去改進數據結構，提高算法的效率，減少內存;同時考慮規則的時間適用性和項目的權重，去尋找一種考慮時間約束的加權關聯規則挖掘的有效算法。從而大大提高關聯規則挖掘的效率，避免決策者做出一些錯誤的決定。

參考文獻：

[1] JiaweiHan， MichelineKamber， JianPei， et al. 數據挖掘：概念與技術[M]. 機械工業出版社， 2012.

[2] Grahne， G.， & Zhu， J. （2005）. Fast algorithms for frequent itemset mining using FPtrees. IEEE Transactions on Knowledge and Data Engineering， 17（10）， 1347–1362.

[3] Nguyen H， Vo B， Nguyen M， et al. An efficient algorithm for mining frequent weighted itemsets using interval word segments[J]. Applied Intelligence， 2016， 45（4）： 1008-1020.

[4] Lee G ， Yun U ， Ryu K H . Mining Frequent Weighted Itemsets without Storing Transaction IDs and Generating Candidates[J]. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2017， 25（01）：111-144.

[5] Huong Bui ，Bay Vo ， Ham Nguyen， et al. A weighted N-list-based method for mining frequent weighted itemsets[J]. Expert Systems with application，2018， 96：388-405.

[6] Tran T ， Vo B ， Le T T N ， et al. Text Clustering Using Frequent Weigted Utility Itemsets[J]. Cybernetics and Systems， 2017， 48（3）：193-209.

[7] Yun U， Lee G .Incremental mining of weighted maximal frequent itemsets from dynamic databases[M].2016.

[8] Lee G ， Yun U ， Ryang H . Mining weighted erasable patterns by using underestimated constraint-based pruning technique[M]. IOS Press， 2015.

【通聯編輯：王力】