基于傾斜時(shí)間窗口的頻繁項(xiàng)集挖掘算法研究.pdf

1、當(dāng)今的信息社會(huì)的中，人們每天都要處理各種各樣的信息和數(shù)據(jù)。隨著信息的爆炸式增長(zhǎng)，許多應(yīng)用中需要處理的數(shù)據(jù)規(guī)模也越來(lái)越大，這些數(shù)據(jù)以快速的、大量的、按時(shí)間順序連續(xù)到達(dá)，這種數(shù)據(jù)模式就是數(shù)據(jù)流。由于數(shù)據(jù)流的流動(dòng)性和無(wú)限性的特點(diǎn)，原有頻繁項(xiàng)集挖掘算法已很難完成基于數(shù)據(jù)流上的挖掘任務(wù)。這些挑戰(zhàn)吸引了許多人對(duì)數(shù)據(jù)流中頻繁項(xiàng)集挖掘進(jìn)行了大量研究?，F(xiàn)在，數(shù)據(jù)流中頻繁項(xiàng)集挖掘已成為數(shù)據(jù)挖掘中的熱點(diǎn)之一。
　　 FP-stream算法可以實(shí)現(xiàn)在線

2、挖掘多時(shí)間粒度的頻繁項(xiàng)集。作為一個(gè)經(jīng)典的挖掘算法，F(xiàn)P-stream算法具有較好的時(shí)間效率。但它的不足之處在于：算法使用FP-growth算法來(lái)生成頻繁項(xiàng)集和計(jì)算支持?jǐn)?shù)，需要很大的內(nèi)存開銷和時(shí)間開銷；整個(gè)挖掘過程中，所有的歷史信息數(shù)據(jù)都存于內(nèi)存中，隨著時(shí)間的推移內(nèi)存空間將急劇的膨脹。所以，內(nèi)存開銷巨大是FP-stream算法最大的缺點(diǎn)。
　　 針對(duì)上述問題，本文將在原算法的基礎(chǔ)之上，采用一種新的數(shù)據(jù)結(jié)構(gòu)（LR-Trie樹及樹結(jié)點(diǎn)

3、）來(lái)存儲(chǔ)頻繁項(xiàng)集及其對(duì)應(yīng)的傾斜時(shí)間窗口。同時(shí)引入了垂直的二進(jìn)制向量表示法存儲(chǔ)事務(wù)數(shù)據(jù)以提高時(shí)空效率。由于構(gòu)造了新的樹結(jié)點(diǎn)結(jié)構(gòu)，可以方便地完成LR-Trie樹的線性存儲(chǔ)和結(jié)點(diǎn)查詢。另外將LR-Trie樹分割為若干子樹并以文件的形式存儲(chǔ)，在內(nèi)存中建立項(xiàng)和文件的索引表，按需調(diào)入文件，極大地減少了內(nèi)存消耗。實(shí)驗(yàn)表明，改進(jìn)后的算法在不明顯降低原算法時(shí)間效率的前提下，提高了內(nèi)存空間利用率。該算法適用于對(duì)時(shí)間要求不高，但對(duì)內(nèi)存空間要求較高的應(yīng)用。