基于矩陣的數(shù)據(jù)流滑動窗口頻繁項集挖掘算法研究.pdf

1、近年來，出現(xiàn)了一種與傳統(tǒng)靜態(tài)數(shù)據(jù)庫不同的新型數(shù)據(jù)模式——數(shù)據(jù)流，在電子商務(wù)網(wǎng)絡(luò)交易、股市交易、通話日志分析、傳感器網(wǎng)絡(luò)及計算機網(wǎng)絡(luò)安全監(jiān)控等許多領(lǐng)域都存在著廣泛的應(yīng)用。由于數(shù)據(jù)流具有連續(xù)性、無限性、實時性等特點，因而傳統(tǒng)的靜態(tài)數(shù)據(jù)挖掘技術(shù)不能滿足處理和分析數(shù)據(jù)流這種新型數(shù)據(jù)的要求，因此數(shù)據(jù)流挖掘技術(shù)已成為當(dāng)前研究的一個熱點問題。
　　數(shù)據(jù)流頻繁項集挖掘是關(guān)聯(lián)規(guī)則挖掘的基礎(chǔ)與核心。首先介紹了課題的研究背景以及國內(nèi)外的研究現(xiàn)狀，闡述了

2、數(shù)據(jù)流頻繁項集挖掘目前存在的一些問題，然后介紹了數(shù)據(jù)流挖掘相關(guān)的基本概念與理論。
　　針對現(xiàn)有的寬度優(yōu)先頻繁項集挖掘算法存在的需要多次連接，產(chǎn)生大量冗余項集等問題，本文提出了一種基于矩陣的數(shù)據(jù)流滑動窗口頻繁項集挖掘算法TMFI。該算法采用事務(wù)矩陣來存儲數(shù)據(jù)流中的事務(wù)信息，此矩陣即為一個滑動窗口，對滑動窗口中的數(shù)據(jù)進(jìn)行更新時，采用直接覆蓋的方法，這樣能夠減少數(shù)據(jù)的存儲和更新時間，并減少窗口滑動的時間。在挖掘頻繁項集時，采用二項集矩陣

3、存儲二項集的信息，并且沒有采用經(jīng)典的Apriori性質(zhì)，而是采用了一種利用頻繁k-項集擴(kuò)展(k+1)-項集的思想，這樣能夠有效的避免冗余項集的產(chǎn)生，提高挖掘的效率。實驗結(jié)果表明了算法穩(wěn)定行、快速性、準(zhǔn)確性。
　　頻繁項集挖掘算法需要用戶預(yù)先設(shè)定閾值，而閾值的設(shè)定關(guān)系到挖掘結(jié)果的好壞，為了避免用戶設(shè)置不恰當(dāng)?shù)拈撝?，本文又提出了基于滑動窗口的top-k頻繁項集挖掘算法TKFM。top-k頻繁項集的挖掘不需要用戶事先定義最小支持度閾值，

4、而是根據(jù)用戶的需要挖掘最頻繁的k個項集，只需要用戶指定一個k值即可。TKFM算法用滑動窗口對數(shù)據(jù)流進(jìn)行逐條采樣，并用事務(wù)矩陣存儲事務(wù)的相關(guān)信息，用二項集矩陣存儲top-k二項集的信息。利用k-項集擴(kuò)展為(k+1)-項集的思想及事務(wù)矩陣和二項集矩陣的相關(guān)信息，來挖掘當(dāng)前滑動窗口中的頻繁項集。之后，把得到的頻繁項集存儲到數(shù)據(jù)字典Dictionary中，并且按支持度計數(shù)降序排列。在挖掘出新的頻繁項集時，加入到Dictionary中，同時更新b