基于傾斜時間窗口的頻繁項集挖掘算法研究.pdf

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

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

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