基于時間間隔的事件序列頻繁模式挖掘算法研究.pdf

1、現(xiàn)存的序列模式挖掘算法多是基于瞬時事件的,然而在現(xiàn)實(shí)世界中很多事件都是發(fā)生在一段時間內(nèi),例如語言分析,網(wǎng)絡(luò)檢測等,時間間隔事件序列頻繁模式挖掘在這些領(lǐng)域都有很重要的應(yīng)用。本文的主要研究內(nèi)容正是帶有時間間隔的事件序列頻繁模式挖掘。
　　與傳統(tǒng)的序列模式挖掘不同的是時間間隔事件之間的關(guān)系是很復(fù)雜的,這也正是這種序列頻繁模式挖掘的難點(diǎn)。到目前為止多數(shù)文章的關(guān)系定義都是基于Allen關(guān)系定義,本文中的事件關(guān)系定義也是基于 Allen關(guān)系定

2、義,并在此基礎(chǔ)上進(jìn)行了去噪聲處理,使之更適應(yīng)現(xiàn)實(shí)場景。另外本文簡單的描述了影響頻繁模式生成的各種興趣度衡量,并且基于現(xiàn)實(shí)情況,本文采用支持度為興趣度衡量。
　　而本文最主要的貢獻(xiàn)是本文提出了一種基于“候選頻繁模式生成—支持度計算”的高效算法,并且在兩個階段都提出了改進(jìn)策略。首先在候選頻繁模式生成階段不同于傳統(tǒng)的方法中利用k層頻繁模式與k層頻繁模式生成k+1層候選頻繁模式集,本文提出用k層頻繁模式與2層頻繁模式構(gòu)成k+1層候選頻繁模

3、式集,這樣就能減少在合并兩個頻繁模式時的關(guān)于兩個模式中間部分是否相等的比較次數(shù),這種策略在提高算法效率的同時也能夠減少冗余候選頻繁模式的生成。其次,本文的算法維護(hù)一個2-頻繁模式集合,利用一定的策略來盡可能的減小用于合并生成候選集的2-頻繁模式集,使得產(chǎn)生盡量少的候選頻繁模式,提高算法的效率。
　　在支持度計算階段本文同樣提出了兩種改進(jìn)策略。首先本文在構(gòu)造候選頻繁模式集的同時構(gòu)造了索引,指向需要遍歷的客戶序列,這能夠有效的減小算法

4、的搜索空間,提高算法效率。其次不同于傳統(tǒng)的挖掘算法中在計算支持度的時候多次遍歷數(shù)據(jù)庫,本文提出了一種算法,當(dāng)計算具有相同長度的候選頻繁模式的支持度時,只需遍歷一次數(shù)據(jù)庫?？傊疚脑谥С侄扔嬎愕倪^程中一方面減少遍歷數(shù)據(jù)庫的次數(shù),另一方面減少遍歷數(shù)據(jù)庫時的搜索空間。
　　最后,本文提出了仿真數(shù)據(jù)的生成。在此基礎(chǔ)上本文進(jìn)行了兩個方面的實(shí)驗(yàn),一是本文提出了幾個重要的參數(shù)對算法的影響,并且在實(shí)驗(yàn)中驗(yàn)證了提出的理論。二是為了證明本文提出的算法