基于情節(jié)規(guī)則匹配的數(shù)據(jù)流預測研究.pdf

1、隨著互聯(lián)網(wǎng)、數(shù)據(jù)庫和嵌入式技術(shù)的飛速發(fā)展以及現(xiàn)實應(yīng)用需求的持續(xù)推動,一種被稱為數(shù)據(jù)流的全新數(shù)據(jù)類型已廣泛應(yīng)用在傳感器數(shù)據(jù)處理、網(wǎng)絡(luò)安全監(jiān)控、金融證券管理、事務(wù)日志分析等眾多領(lǐng)域。與傳統(tǒng)數(shù)據(jù)庫截然不同,由一系列值對(事件類型,時間戳)構(gòu)成的數(shù)據(jù)流具有高速、無界、連續(xù)、時變的特點,這些特點使得面向傳統(tǒng)數(shù)據(jù)庫的數(shù)據(jù)挖掘算法難以直接應(yīng)用到數(shù)據(jù)流的分析中。作為數(shù)據(jù)流分析的重要任務(wù)之一,數(shù)據(jù)流預測在面臨巨大挑戰(zhàn)的同時也迎來了前所未有的應(yīng)用機遇,并已

2、成為學術(shù)界和工業(yè)界的研究熱點。本文在總結(jié)國內(nèi)外相關(guān)研究工作的基礎(chǔ)上,針對數(shù)據(jù)流預測涉及的頻繁情節(jié)挖掘、頻繁閉情節(jié)挖掘、無冗余情節(jié)規(guī)則抽取、情節(jié)規(guī)則匹配等四個關(guān)鍵問題展開了深入探討,形成了一個數(shù)據(jù)流預測的研究體系,主要貢獻包括:
　　1.提出了一個事件序列上的頻繁情節(jié)挖掘算法MANEPI。頻繁情節(jié)刻畫了現(xiàn)實應(yīng)用中用戶或系統(tǒng)的行為?，F(xiàn)有的頻繁情節(jié)挖掘算法大多基于最小發(fā)生或非重疊發(fā)生來計算一個情節(jié)的支持度,容易導致情節(jié)發(fā)生的“過計數(shù)”問

3、題或不能很好地刻畫一個情節(jié)中事件類型之間的緊隨關(guān)系。另外,這些算法均采用了與Apriori算法一樣的廣度優(yōu)先搜索策略,需要多遍掃描事件序列,并且產(chǎn)生了大量的候選情節(jié)。然而,算法MANEPI基于最小且非重疊發(fā)生的概念來計算一個情節(jié)的支持度,并采用深度優(yōu)先的搜索策略,只需單遍掃描事件序列且不產(chǎn)生任何候選情節(jié)。此外,MANEPI利用情節(jié)的Apriori性質(zhì)避免了不必要的情節(jié)增長,進一步縮小了頻繁情節(jié)的搜索空間。理論分析和實驗評估證明MANEP

4、I具有較高的挖掘效率和挖掘質(zhì)量。
　　2.提出了一個事件序列上的頻繁閉情節(jié)挖掘算法FCEMiner。頻繁閉情節(jié)集是所有頻繁情節(jié)的一個無損壓縮表示。盡我們所知,Clo_episodd[58]是目前僅有的一個頻繁閉情節(jié)挖掘算法。盡管只需單遍掃描事件序列,但是Clo_episode采用了廣度優(yōu)先的搜索策略,在挖掘過程中產(chǎn)生了大量的候選情節(jié)。另外,該算法基于最小發(fā)生來計算一個情節(jié)的支持度,也會導致情節(jié)發(fā)生的“過計數(shù)”問題。然而,算法FCE

5、Miner‘采用了與MANEPI一樣的搜索策略和支持度定義來發(fā)現(xiàn)頻繁情節(jié)的簡約且完備集,并利用特殊前向擴展的非閉一致性避免了冗余的閉合性檢查,進一步縮小了頻繁閉情節(jié)的搜索空間,加速了挖掘過程。理論分析和實驗評估證明FCEMiner能夠高效地發(fā)現(xiàn)事件序列上的頻繁閉情節(jié)。
　　3.提出了一個事件序列上的無冗余情節(jié)規(guī)則抽取算法Extractor。情節(jié)規(guī)則描述了頻繁情節(jié)之間的因果關(guān)系?，F(xiàn)有的情節(jié)規(guī)則抽取算法主要存在三個問題:第一,基于滑動

6、窗口或最小發(fā)生來計算一個情節(jié)的支持度,致使頻繁情節(jié)的挖掘質(zhì)量不高;第二,直接由頻繁情節(jié)產(chǎn)生情節(jié)規(guī)則,導致規(guī)則數(shù)量過于龐大且存在冗余;第三,盡管利用一些修剪技術(shù)來篩選冗余的情節(jié)規(guī)則,但這種后期的修剪處理增加了算法的時間代價。然而,算法Extractor采用最小且非重疊發(fā)生的支持度定義和深度優(yōu)先的搜索策略來發(fā)現(xiàn)頻繁閉情節(jié)及其生成子,保證了頻繁閉情節(jié)及其生成子的挖掘質(zhì)量和挖掘效率;利用非生成子情節(jié)的Apriori性質(zhì),避免了冗余的生成子判斷;

7、直接由頻繁閉情節(jié)及其生成子來產(chǎn)生無冗余情節(jié)規(guī)則,提高了情節(jié)規(guī)則的生成質(zhì)量和生成效率。理論分析和實驗評估證明Extractor能夠有效抽取給定事件序列上所有的無冗余情節(jié)規(guī)則。
　　4.提出了一個數(shù)據(jù)流上基于情節(jié)規(guī)則匹配的預測算法Predictor。研究歷史流數(shù)據(jù)的潛在規(guī)律并應(yīng)用這些規(guī)律對未來流數(shù)據(jù)作出預測,能夠為許多現(xiàn)實應(yīng)用提供重要的決策支持?，F(xiàn)有的數(shù)據(jù)流預測算法大多采用回歸分析或規(guī)則匹配的方法?；貧w分析方法預測速度快,但只適于線性

8、數(shù)據(jù)預測;規(guī)則匹配方法可預測線性和非線性數(shù)據(jù),但存在規(guī)則形式嚴格、預測區(qū)間受限或過時、規(guī)則過于匹配等問題。然而,算法Predictor使用無冗余情節(jié)規(guī)則作為待匹配規(guī)則,保證了待匹配規(guī)則內(nèi)涵的代表性和形式的一般性。預測時Predictor為每個情節(jié)規(guī)則分別使用了一個自動機,通過單遍掃描數(shù)據(jù)流來同時跟蹤這些自動機的狀態(tài)變遷,以搜索每個規(guī)則前件最近的最小且非重疊發(fā)生,這樣不僅將無界的數(shù)據(jù)流映射到有限的狀態(tài)空間,而且避免了對情節(jié)規(guī)則的過于匹配。