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

1、現(xiàn)存的序列模式挖掘算法多是基于瞬時(shí)事件的,然而在現(xiàn)實(shí)世界中很多事件都是發(fā)生在一段時(shí)間內(nèi),例如語(yǔ)言分析,網(wǎng)絡(luò)檢測(cè)等,時(shí)間間隔事件序列頻繁模式挖掘在這些領(lǐng)域都有很重要的應(yīng)用。本文的主要研究?jī)?nèi)容正是帶有時(shí)間間隔的事件序列頻繁模式挖掘。
　　與傳統(tǒng)的序列模式挖掘不同的是時(shí)間間隔事件之間的關(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í)場(chǎng)景。另外本文簡(jiǎn)單的描述了影響頻繁模式生成的各種興趣度衡量,并且基于現(xiàn)實(shí)情況,本文采用支持度為興趣度衡量。
　　而本文最主要的貢獻(xiàn)是本文提出了一種基于“候選頻繁模式生成—支持度計(jì)算”的高效算法,并且在兩個(gè)階段都提出了改進(jìn)策略。首先在候選頻繁模式生成階段不同于傳統(tǒng)的方法中利用k層頻繁模式與k層頻繁模式生成k+1層候選頻繁模式集,本文提出用k層頻繁模式與2層頻繁模式構(gòu)成k+1層候選頻繁模

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

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