房新秀

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

關(guān)鍵詞：關(guān)聯(lián)規(guī)則;頻繁項集;加權(quán)關(guān)聯(lián)規(guī)則;加權(quán)頻繁項集;算法

中圖分類號：TP301.6? ? ? ? 文獻(xiàn)標(biāo)識碼：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 頻繁項集挖掘現(xiàn)狀

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

2 加權(quán)頻繁項集挖掘現(xiàn)狀

傳統(tǒng)的關(guān)聯(lián)挖掘算法往往忽略數(shù)據(jù)庫中各個項目的重要程度的區(qū)別。因此，在分析實際數(shù)據(jù)時，利用加權(quán)關(guān)聯(lián)規(guī)則是有意義的。它發(fā)現(xiàn)那些出現(xiàn)頻率較低但權(quán)值比較大的重要頻繁項集。

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

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

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

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

3 結(jié)束語

通過分析以上算法，比較頻繁項集和加權(quán)頻繁項集算法之后，采用滿足向下閉合屬性去挖掘加權(quán)頻繁項集。在未來的工作中，通過分析現(xiàn)有算法存在的不足，在已有算法的基礎(chǔ)上去改進(jìn)數(shù)據(jù)結(jié)構(gòu)，提高算法的效率，減少內(nèi)存;同時考慮規(guī)則的時間適用性和項目的權(quán)重，去尋找一種考慮時間約束的加權(quán)關(guān)聯(lián)規(guī)則挖掘的有效算法。從而大大提高關(guān)聯(lián)規(guī)則挖掘的效率，避免決策者做出一些錯誤的決定。

參考文獻(xiàn)：

[1] JiaweiHan， MichelineKamber， JianPei， et al. 數(shù)據(jù)挖掘：概念與技術(shù)[M]. 機(jī)械工業(yè)出版社， 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.

【通聯(lián)編輯：王力】