數(shù)據(jù)流模式挖掘算法及應(yīng)用研究.pdf

1、隨著各行業(yè)對數(shù)據(jù)越來越重視和信息技術(shù)的快速發(fā)展，產(chǎn)生的數(shù)據(jù)越來越全面，同時(shí)數(shù)據(jù)量也在快速的增長;并且各行業(yè)又要求能及時(shí)對已產(chǎn)生的數(shù)據(jù)進(jìn)行挖掘和分析，這使得數(shù)據(jù)流挖掘技術(shù)愈發(fā)重要。由于數(shù)據(jù)流具有海量性、實(shí)時(shí)性和動態(tài)變化性的特點(diǎn)，這就要求數(shù)據(jù)流上的挖掘算法有較高的時(shí)空效率。盡管數(shù)據(jù)流上數(shù)據(jù)挖掘技術(shù)取得了一定的進(jìn)展，但是挖掘算法的時(shí)空效率仍然是當(dāng)前數(shù)據(jù)挖掘領(lǐng)域中的研究焦點(diǎn)之一。
　　本文主要研究了數(shù)據(jù)流模式挖掘算法，包括傳統(tǒng)數(shù)據(jù)集類型中

2、的頻繁模式挖掘以及大數(shù)據(jù)集下的頻繁模式挖掘、不確定數(shù)據(jù)流中的頻繁模式挖掘、和高效用模式挖掘。本文首先對已有的頻繁模式和高效用模式挖掘算法進(jìn)行了回顧，詳細(xì)的介紹了算法Apriori和FP-Growth等;然后在對典型的挖掘算法和最新研究成果進(jìn)行分析研究的基礎(chǔ)上，深入研究了傳統(tǒng)數(shù)據(jù)中的頻繁模式挖掘、不確定數(shù)據(jù)上的頻繁模式挖掘和具有效用值的數(shù)據(jù)中的高效用模式挖掘算法。本文取得了如下的創(chuàng)新性研究成果:
　　(1)在傳統(tǒng)數(shù)據(jù)的頻繁模式挖掘算

3、法研究中，提出新的尾節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)和一種最多兩次MapReduce的并行挖掘算法。針對數(shù)據(jù)流中的頻繁模式挖掘問題，采用尾節(jié)點(diǎn)和尾節(jié)點(diǎn)表來提高窗口內(nèi)數(shù)據(jù)更新的時(shí)間效率和維護(hù)的空間效率;并通過提高窗口內(nèi)頻繁模式挖掘算法的時(shí)間效率，進(jìn)而提高數(shù)據(jù)流中模式挖掘的整體時(shí)間效率。針對大數(shù)據(jù)下的數(shù)據(jù)流頻繁模式挖掘問題，首先通過一次MapReduce找到局部頻繁模式做為候選項(xiàng)集，然后通過給出的剪枝策略對候選項(xiàng)集進(jìn)行剪枝，最后進(jìn)行第二次MapReduce對候

4、選項(xiàng)集中剩余項(xiàng)集進(jìn)行支持?jǐn)?shù)統(tǒng)計(jì);在多數(shù)情況下，該算法不需要第二次MapReduce就可以有效的挖掘到所有的頻繁模式。
　　(2)在不確定事務(wù)數(shù)據(jù)的頻繁模式挖掘算法研究中，提出具有更高壓縮率的樹結(jié)構(gòu)來改進(jìn)不確定數(shù)據(jù)集及數(shù)據(jù)流上的頻繁模式挖掘算法。首先利用數(shù)組來存儲事務(wù)項(xiàng)集的概率，然后將事務(wù)概率在數(shù)組中的索引和事務(wù)項(xiàng)集映射到一棵樹上，從而可以有效的降低維護(hù)不確定數(shù)據(jù)集的樹節(jié)點(diǎn)個(gè)數(shù)。在此基礎(chǔ)上，結(jié)合滑動窗口技術(shù)，同時(shí)給出兩種新的樹結(jié)構(gòu)分

5、別來維護(hù)窗口中數(shù)據(jù)和挖掘過程中的子數(shù)據(jù)集，保證在挖掘的過程中使窗口中事務(wù)項(xiàng)集的信息不會從樹上丟失;從而使頻繁模式挖掘算法的時(shí)空效率得到較大的提升。另外，本文還提出一種新的具有權(quán)重的頻繁模式挖掘模型和算法;該模型主要是將項(xiàng)的權(quán)重值引入到頻繁模式的挖掘過程中，將權(quán)重值大的模式考慮到挖掘結(jié)果中。
　　(3)在高效用模式挖掘算法研究中，提出避免使用高估效用值的不產(chǎn)生候選項(xiàng)集的挖掘算法。首先本文提出一個(gè)新的樹結(jié)構(gòu)來維護(hù)事務(wù)項(xiàng)集及效用值信息，