數(shù)據(jù)流頻繁模式挖掘及數(shù)據(jù)預測算法研究.pdf

1、在過去的幾年里，數(shù)據(jù)流廣泛出現(xiàn)在傳感器網(wǎng)絡、金融證券管理、網(wǎng)絡監(jiān)控、Web日志以及通信數(shù)據(jù)在線分析等新型應用領域中。由于數(shù)據(jù)流中數(shù)據(jù)的規(guī)模一般都十分龐大、且增長迅速，因此，有限的存儲空間中根本無法完整地保存數(shù)據(jù)流上的全部數(shù)據(jù)，這給數(shù)據(jù)流上的數(shù)據(jù)處理帶來了巨大的挑戰(zhàn)。此外，由于數(shù)據(jù)流數(shù)據(jù)的連續(xù)性與流動性，隨著新的流數(shù)據(jù)連續(xù)到達，數(shù)據(jù)流所包含的知識信息總是在連續(xù)不斷地變化。而對于實際的數(shù)據(jù)流應用而言，挖掘出數(shù)據(jù)流上知識的變化趨勢往往比挖掘知

2、識本身更為重要。因此，人們往往更希望挖掘出數(shù)據(jù)流上最近的某個滑動時間窗口內(nèi)交易數(shù)據(jù)所包含的知識信息。 挖掘數(shù)據(jù)流上的頻繁模式在數(shù)據(jù)流的應用中有著重要研究意義，例如：在網(wǎng)絡監(jiān)控中，對應于異常流量的頻繁模式可能意味著存在網(wǎng)絡攻擊或者網(wǎng)絡擁塞；在商業(yè)銷售記錄中，頻繁模式總是反映那些熱門銷售的產(chǎn)品以及它們之間的關聯(lián)關系；而在傳感器網(wǎng)絡數(shù)據(jù)管理中，挖掘其中的頻繁數(shù)據(jù)集可以有助于去估計那些丟失的數(shù)據(jù)值。然而，由于流數(shù)據(jù)的特點，傳統(tǒng)的靜態(tài)數(shù)據(jù)

3、庫挖掘方法不可能直接應用流數(shù)據(jù)的頻繁模式挖掘，而必須研究新的數(shù)據(jù)流頻繁模式挖掘方法。數(shù)據(jù)流上的頻繁模式挖掘算法要求能夠在單遍掃描流數(shù)據(jù)的基礎上增量處理連續(xù)不斷到達的流數(shù)據(jù)，并用盡可能小的代價維護數(shù)據(jù)流上最新的數(shù)據(jù)大綱。此外，隨著新到達的流數(shù)據(jù)進入滑動時間窗口，窗口內(nèi)最古老的歷史數(shù)據(jù)將從窗口中移出而變得過期。為了消除歷史流數(shù)據(jù)對當前挖掘結(jié)果的影響，數(shù)據(jù)流滑動時間窗口內(nèi)頻繁模式挖掘方法還需要定期刪除數(shù)據(jù)大綱上維護的歷史流數(shù)據(jù)的模式信息，從而

4、提高模式挖掘的正確性。 數(shù)據(jù)流最近的頻繁模式挖掘方法應用模式樹(RFP-tree)增量地維護數(shù)據(jù)流上新到達流數(shù)據(jù)所包含的模式信息，并周期性地對模式樹進行剪枝，刪除那些過期流數(shù)據(jù)所包含的模式分枝以及不頻繁的模式分枝。RFP-tree以維護數(shù)據(jù)流上最近的不多于2N個流數(shù)據(jù)所包含的模式信息為代價，保守地維護了數(shù)據(jù)流上最近的大小為N的滑動時間窗口內(nèi)流數(shù)據(jù)的全部頻繁模式信息。方法還應用保守的計算策略計算模式在滑動時間窗口內(nèi)的近似支持數(shù)，而

5、由保守計算策略得到的模式的近似支持數(shù)總是不小于模式的真實支持數(shù)的，因此，方法總能夠保證滑動時間窗口內(nèi)模式挖掘的覆蓋率達到100％。 為了適應性維護數(shù)據(jù)流上大小可變的滑動時間窗口內(nèi)的頻繁模式，數(shù)據(jù)流任意大小滑動時間窗口內(nèi)頻繁模式挖掘方法應用滑動窗口樹(SW-tree)增量維護數(shù)據(jù)流滑動時間窗口內(nèi)的模式信息。同時，它還應用時間衰減模型衰減流數(shù)據(jù)所包含模式支持數(shù)的權(quán)重，并以此來區(qū)分新產(chǎn)生流數(shù)據(jù)與歷史流數(shù)據(jù)所包含的模式。為了保證模式挖掘的

6、覆蓋率和精度，方法分析了時間衰減模型對模式支持數(shù)的影響，并給出了衰減因子在保證模式挖掘正確性條件下的邊界值。并且，當滑動時間窗口的大小改變時，僅需重新設定合適的衰減因子的值即可重新保證在新的滑動時間窗口下模式挖掘的正確性。 在實際的數(shù)據(jù)流應用中，由于流數(shù)據(jù)的連續(xù)不斷變化導致流數(shù)據(jù)所包含的模式信息也在不斷地變化，因此很難事先估計數(shù)據(jù)流上的頻繁模式信息并給出一個合適的最小支持度門限。數(shù)據(jù)流滑動時間窗口內(nèi)Top-K頻繁模式挖掘方法提供

7、了一個更加直接的挖掘數(shù)據(jù)流上頻繁模式的方法。它無需用戶提供最小支持度門限，而僅需用戶提供預期的頻繁模式集的大小K。它使用Chernoff邊界理論估計窗口內(nèi)第K頻繁模式的支持度，并將其用于動態(tài)維護窗口內(nèi)潛在頻繁的模式信息。根據(jù)理論分析，Chernoff邊界理論能夠為模式挖掘的正確性提供了概率保證。 研究數(shù)據(jù)流上的歷史數(shù)據(jù)的變化趨勢，并預測數(shù)據(jù)流在未來時間窗口內(nèi)的可能值是數(shù)據(jù)流挖掘的一項重要工作。基于馬爾可夫模型的數(shù)據(jù)流預測查詢算法