高效用模式挖掘算法研究及應(yīng)用.pdf

1、在技術(shù)不斷變革的今天，越來越多的數(shù)據(jù)被生產(chǎn)出來。如何從龐雜的數(shù)據(jù)中發(fā)現(xiàn)有趣或有價(jià)值的內(nèi)容成為目前學(xué)術(shù)界和工業(yè)界最為關(guān)注的問題。其中頻繁模式挖掘因其能有效地挖掘出事務(wù)內(nèi)在的聯(lián)系而被廣泛地應(yīng)用于基因分析、文本分類、腫瘤診斷、圖像處理等領(lǐng)域，但是頻繁模式算法中的項(xiàng)在事務(wù)中只有兩種狀態(tài):存在或者不存在。為了解決頻繁模式算法只考慮項(xiàng)是否存在事務(wù)中而忽略了項(xiàng)本身效用的不足，高效用模式挖掘算法被提出。然而目前的高效用模式挖掘算法仍然存在很多不足，其中

2、最主要問題是:(1)算法不易擴(kuò)展;(2)算法缺少對于事務(wù)信息的有效壓縮;(3)算法時(shí)效性低。本文針對這三個(gè)主要問題分別提出了基于靜態(tài)數(shù)據(jù)庫的高效用模式挖掘算法和基于動(dòng)態(tài)增量數(shù)據(jù)庫的增量高效用模式挖掘算法，并取得了優(yōu)異的效果。同時(shí)本文給出了高效用模式挖掘算法在微博好友推薦中的實(shí)際應(yīng)用。本文的主要工作有:
　　1.提出了一個(gè)靜態(tài)數(shù)據(jù)庫中基于投影的高效用模式挖掘算法HUPMP。HUPMP是一階段算法，在進(jìn)行高效用模式挖掘的過程中不產(chǎn)生任

3、何候選模式。
　　2.提出了一個(gè)用以解決動(dòng)態(tài)增量數(shù)據(jù)庫問題的增量高效用算法IHUP。IHUP是在HUPMP的基礎(chǔ)上提出的，充分利用了HUPMP算法的可擴(kuò)展性。
　　3.提出了兩個(gè)有效的結(jié)構(gòu)HUP-Array和HUP-Result分別用來存儲事務(wù)信息和高效用模式。使用HUP-Array結(jié)構(gòu)將事務(wù)進(jìn)行合并壓縮，同時(shí)還極大地提高了算法的可擴(kuò)展性。HUP-Result結(jié)構(gòu)可以對結(jié)果集進(jìn)行快速的查找和更新，使得算法在動(dòng)態(tài)增量數(shù)據(jù)庫的業(yè)

4、務(wù)場景中有更高的響應(yīng)速度。
　　4.制定了四個(gè)策略用來提高算法的時(shí)間性能和減少算法的內(nèi)存消耗。其中項(xiàng)按支持度降序排列策略可以極大地合并事務(wù)，將事務(wù)有效壓縮以節(jié)省內(nèi)存。前綴項(xiàng)之和的策略可以將HUP-Array的比較時(shí)間復(fù)雜度從O(M× N)降到O(1)。緊湊事務(wù)權(quán)重上限策略可以快速對低效用模式進(jìn)行刪減，提高算法性能。只處理新增事務(wù)中的項(xiàng)的策略可以很好應(yīng)對增量高效用模式挖掘中對算法響應(yīng)度高的要求。
　　5.通過實(shí)驗(yàn)分別驗(yàn)證了HU