基于加權(quán)多重最小支持度的挖掘算法研究.pdf

1、隨著數(shù)據(jù)流的不斷發(fā)展和應(yīng)用,在數(shù)據(jù)流環(huán)境下的數(shù)據(jù)挖掘已經(jīng)成為獲取信息的主要方式,尤其是最大頻繁模式的挖掘已成為當(dāng)今的研究熱點,它能提供決策支持和商業(yè)預(yù)測,因此在實際中有很大應(yīng)用價值。
　　最小項目支持度MIS(Minimum Item Support)是對數(shù)據(jù)流中的每個數(shù)據(jù)項,設(shè)置關(guān)鍵屬性的支持度,以便對數(shù)據(jù)項進行修剪后的挖掘;而最大頻繁模式MFPs(Maximal Frequent Patterns)是在MIS的基礎(chǔ)上挖掘最大頻

2、繁模式。現(xiàn)有的最大頻繁模式 MFPs雖然具有較高的壓縮比,但只是考慮了支持度的挖掘條件,而沒有區(qū)分每個頻繁模式的權(quán)重,無法反應(yīng)實際屬性信息。因此對 MFPs算法進一步擴充和完善是十分有意義的。在分析和總結(jié)MFPs的算法優(yōu)缺點的基礎(chǔ)上,本文進一步做了以下的研究工作:
　　1.現(xiàn)有MFPs算法對頻繁模式的挖掘過程中,會產(chǎn)生大量的中間集,耗費了大量的時間和空間,并且沒有考慮到多重支持度的挖掘條件。針對上述問題,本文構(gòu)造了數(shù)據(jù)存儲結(jié)構(gòu)CP

3、LMS-tree(Compact Preorder Linked Multiple Supports tree),并提出了能夠滿足多重最小支持度的頻繁模式挖掘算法MSCP-growth(Multiple Support-Conditional Pattern growth):通過數(shù)據(jù)結(jié)構(gòu)中構(gòu)建的屬性 iflag來表示子序列是否為頻繁項,mps來表示最小的MIS值,并將上述兩個屬性值作為修剪條件,通過對存儲的頻繁數(shù)據(jù)項設(shè)置不同的支持度來挖

4、掘頻繁模式,可以較大減少頻繁模式候選集產(chǎn)生的數(shù)量,快速地獲得有價值的頻繁模式。最后通過實驗將所提算法與傳統(tǒng)算法PLWAP-Mine進行比較,驗證了MSCP-growth算法在執(zhí)行時間、頻繁模式候選集和頻繁模式產(chǎn)生的數(shù)量,以及空間占用大小等性能上優(yōu)于PLWAP-Mine算法。
　　2.在數(shù)據(jù)流環(huán)境下,現(xiàn)有的加權(quán)最大頻繁模式 WMFPs(Weighted Maximal Frequent Patterns)算法,對頻繁模式的挖掘需要多

5、次數(shù)據(jù)庫掃描,并且沒有充分利用加權(quán)因子與最小支持度相結(jié)合的優(yōu)勢,產(chǎn)生大量的無價值最大頻繁模式候選集,針對上述問題,構(gòu)造了一個新的數(shù)據(jù)存儲結(jié)構(gòu)MWS-tree(Maximal Weight Streams tree),通過利用最大加權(quán)值MW(Maximal Weight)為修剪條件,較大地減少了最大頻繁模式的搜索范圍;同時構(gòu)建包含支持度索引信息的數(shù)組WMFP-array(Weighted Maximal Frequent Patterns

6、 array),通過此數(shù)組的支持度索引信息來減少對數(shù)據(jù)庫掃描的次數(shù),并以單一路徑與數(shù)據(jù)項加權(quán)支持度相結(jié)合,減少遍歷樹結(jié)構(gòu)的次數(shù)。
　　3.在 MWS-tree基礎(chǔ)上,提出了最大加權(quán)數(shù)據(jù)流算法 MWS(Maximal Weight Streams),算法利用數(shù)據(jù)項的權(quán)重信息WI(Weight information)和最小支持度閥值δ進行最大頻繁模式的挖掘,并對挖出的頻繁模式進行子集檢查操作,將最后結(jié)果存儲于最大頻繁模式數(shù)據(jù)結(jié)構(gòu) W