淺談加權(quán)頻繁項(xiàng)集挖掘的研究進(jìn)展

房新秀

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

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

中圖分類號(hào)：TP301.6? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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àng)集挖掘現(xiàn)狀

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

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

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

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

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

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

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

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

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

參考文獻(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)編輯：王力】