間隔事件流上的頻繁情節(jié)挖掘方法研究.pdf

1、隨著信息時代的到來，人們需要分析處理越來越多的數(shù)據(jù)，而這些海量數(shù)據(jù)的背后隱藏著大量的人們所需要的規(guī)則和知識，數(shù)據(jù)挖掘就是隨著人們的這一需要應運而生的。雖然最近幾十年對數(shù)據(jù)挖掘技術(shù)的研究已經(jīng)很成熟，但隨著RFID、Sensor等EDGE(Electronic Data Gathering Equipment)設(shè)備的廣泛應用，出現(xiàn)了大量的事件流數(shù)據(jù)。傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)往往針對靜態(tài)數(shù)據(jù)進行處理，對這種事件流數(shù)據(jù)不適用。
　　頻繁情節(jié)挖掘

2、是事件流挖掘領(lǐng)域中的重要方面。目前對頻繁情節(jié)挖掘的研究主要針對靜態(tài)數(shù)據(jù)和點事件類型的數(shù)據(jù)，但是在真實情況下，對事件流的處理往往比靜態(tài)數(shù)據(jù)更有意義，而且事件的發(fā)生很多是帶有時間間隔的，不可能完全按照點事件類型進行處理。本文針對這些問題，提出了在具有時間間隔的事件流上進行頻繁情節(jié)挖掘的算法，可以有效地把事件流和時間間隔事件結(jié)合起來解決。
　　首先，對于時間間隔事件，提出了基于關(guān)系元組的表示方法，它可以有效的區(qū)分出滑動窗口內(nèi)所有的頻繁情

3、節(jié)，避免了傳統(tǒng)的對有時間間隔事件處理時，丟失情節(jié)的情況。但是基于關(guān)系元組的表示方法還存在一些問題，所以在此基礎(chǔ)上本文又提出了基于矩陣的表達方法，它可以使用戶清楚的了解所挖掘出的頻繁情節(jié)的內(nèi)部關(guān)系。
　　其次，因為我們?nèi)粘Ｉ钪薪佑|的事件類型往往是有間隔的，即事件需要持續(xù)一段時間后才結(jié)束，而現(xiàn)階段的挖掘方法都不能處理這種間隔事件。所以本文提出了一種關(guān)系線索樹和B+樹相結(jié)合的方法，它可以對事件流中的間隔事件進行頻繁情節(jié)挖掘，可以構(gòu)建并

4、有效地存儲事件流中滑動窗口內(nèi)的所有情節(jié)，也避免了對源數(shù)據(jù)的多次掃描。
　　最后，本文在此基礎(chǔ)上提出了一種基于線性鏈表的深度優(yōu)先算法，它采用深度優(yōu)先構(gòu)建線性鏈表的方法，針對最小發(fā)生情節(jié)，采用一種最小誤差系數(shù)的修剪方法對滑動窗口內(nèi)的情節(jié)進行修剪，在一定程度上減少了時間和空間代價的消耗。
　　通過實驗可以發(fā)現(xiàn)，本文所提出的針對具有時間間隔的事件流上的頻繁情節(jié)挖掘算法可以很快地對新到來的事件進行處理，并挖掘出滑動窗口內(nèi)的所有頻繁情節(jié)