頻繁模式挖掘算法研究.pdf

1、頻繁模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)基本問(wèn)題，研究?jī)?nèi)容一般包括項(xiàng)目集合、項(xiàng)目序列和時(shí)間序列等各種數(shù)據(jù)中的頻繁模式挖掘。其方法被廣泛應(yīng)用于許多其它數(shù)據(jù)挖掘任務(wù)中，如關(guān)聯(lián)規(guī)則、分類(lèi)和聚類(lèi)、周期分析、相似性查詢(xún)等等。由于問(wèn)題本身的基礎(chǔ)性和內(nèi)在復(fù)雜性，頻繁模式挖掘方法成為許多研究者關(guān)注的課題。 本文對(duì)頻繁模式挖掘的算法進(jìn)行了研究。重點(diǎn)研究了以下幾個(gè)方面的頻繁模式挖掘算法問(wèn)題：項(xiàng)目集合的完全頻繁模式和部分頻繁模式挖掘算法；項(xiàng)目序列中的Web頻

2、繁路徑挖掘算法；時(shí)間序列的頻繁模式挖掘算法等。本文研究?jī)?nèi)容和創(chuàng)新工作主要包括以下幾個(gè)方面： 對(duì)頻繁模式挖掘算法中常用的數(shù)據(jù)結(jié)構(gòu)FP-tree進(jìn)行了深入的研究，提出了多種FP-tree的新操作方法，包括FP-tree的拆分、合并、投影等操作，使FP-tree在頻繁模式挖掘算法中得到更加靈活的運(yùn)用，從而有利于提高算法的效率。 提出了在項(xiàng)目集合中挖掘頻繁模式的FP-DFS算法和FIPT算法。前者用于完全頻繁模式挖掘，后者用于部

3、分頻繁模式挖掘。FP-DFS算法以FP-tree為基本數(shù)據(jù)結(jié)構(gòu)，但不再使用條件模式基遞歸地構(gòu)造FP-tree，而是通過(guò)使用本文提出的FP-tree的新操作方法，以及新的搜索策略和剪枝策略，提高算法的搜索效率，并且減少了對(duì)內(nèi)存的占用。FIPT算法的特點(diǎn)是將概念格與FP-tree結(jié)合起來(lái)，通過(guò)使用本文提出的FP-tree的新操作方法提高概念格的更新效率，解決了批處理大量事務(wù)時(shí)的效率問(wèn)題，而生成的概念格又可用于增量挖掘。 對(duì)于項(xiàng)目序列

4、的頻繁模式挖掘，重點(diǎn)研究了其中的Web頻繁訪(fǎng)問(wèn)路徑挖掘問(wèn)題，提出了基于網(wǎng)頁(yè)模糊分類(lèi)的Web事務(wù)識(shí)別方法，并在此基礎(chǔ)上提出了一種挖掘頻繁訪(fǎng)問(wèn)路徑的高效混合式算法WDHP。WDHP算法繼承了DHP算法使用hash樹(shù)過(guò)濾候選集以及裁剪數(shù)據(jù)庫(kù)的基本方法，當(dāng)數(shù)據(jù)庫(kù)被邏輯裁剪到一定程度時(shí)，便將數(shù)據(jù)庫(kù)以FP-tree的方式存儲(chǔ)于內(nèi)存，并在內(nèi)存中完成后繼的挖掘，既減少了內(nèi)存占用，又提高了算法的運(yùn)行效率。 對(duì)于時(shí)間序列的頻繁模式挖掘，本文首先分析

5、了時(shí)間序列子序列聚類(lèi)方法中存在的問(wèn)題，提出了一種基于小波濾波的聚類(lèi)算法。在此基礎(chǔ)上，進(jìn)一步提出了基于小波濾波的時(shí)間序列頻繁模式挖掘算法，F(xiàn)requent-Wavelet算法。Frequent-Wavelet算法的基本原理是使時(shí)間序列通過(guò)多孔平滑濾波器組，然后對(duì)來(lái)自多個(gè)尺度序列的子序列進(jìn)行聚類(lèi)，從而將時(shí)間序列的頻繁模式挖掘問(wèn)題轉(zhuǎn)化為項(xiàng)目序列的頻繁模式挖掘問(wèn)題。由于成功地解決了時(shí)間序列頻繁模式挖掘中的平凡相似和時(shí)間軸伸縮問(wèn)題，與同類(lèi)算法相比