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

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

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

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

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

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

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

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