數(shù)據(jù)流頻繁項(xiàng)挖掘算法研究與應(yīng)用.pdf

1、數(shù)據(jù)流是按時(shí)間順序到達(dá)的一個(gè)連續(xù)數(shù)據(jù)組成的一個(gè)序列。近年來，挖掘數(shù)據(jù)流的應(yīng)用越來越廣泛。在動(dòng)態(tài)數(shù)據(jù)集上挖掘頻繁項(xiàng)是一項(xiàng)困難的任務(wù)，也是一個(gè)熱點(diǎn)。流數(shù)據(jù)頻繁項(xiàng)挖掘是數(shù)據(jù)流挖掘中的重要組成部分。 目前數(shù)據(jù)流頻繁項(xiàng)挖掘算法的研究成果主要有基于Hash的和基于抽樣的。本文首先對這兩類的經(jīng)典算法的主要思想進(jìn)行了探討，對這些算法在誤差范圍、空間復(fù)雜度和單項(xiàng)處理的時(shí)間復(fù)雜度等方面重點(diǎn)進(jìn)行了比較。接著，本文重點(diǎn)對數(shù)據(jù)流頻繁項(xiàng)挖掘的EC算法進(jìn)行了

2、研究探討。雖然該算法在誤差范圍、空間復(fù)雜度和處理單項(xiàng)數(shù)據(jù)項(xiàng)的時(shí)間復(fù)雜度方面是目前進(jìn)行頻繁項(xiàng)挖掘中的較好算法，但該算法在最壞時(shí)間復(fù)雜度方面沒有給出最壞保證，在精度方面還可以進(jìn)一步提高。然后，本文給出了基于計(jì)數(shù)和局部性原理的頻繁項(xiàng)挖掘算法。一方面，改進(jìn)EC算法維護(hù)樣本集合的方法，將數(shù)據(jù)流每個(gè)數(shù)據(jù)項(xiàng)的最壞處理時(shí)間控制在O(ε<'-1>)；另一方面，根據(jù)局部性原理可知，如果一個(gè)數(shù)據(jù)項(xiàng)被訪問，則該項(xiàng)可能很快被再次訪問。因此，利用增加歷史樣本集，暫

3、存歷史流數(shù)據(jù)的概要信息，通過動(dòng)態(tài)維護(hù)樣本集和歷史樣本集來進(jìn)一步降低輸出頻率值的誤差，用一定的空間換取一定的精度。通過理論分析和實(shí)驗(yàn)驗(yàn)證，通常情況，改進(jìn)算法的誤差更小。而且，最壞時(shí)間復(fù)雜度可以得到保證。最后，在公安局的點(diǎn)擊流頻繁項(xiàng)挖掘系統(tǒng)中該算法得到具體應(yīng)用。訪問者點(diǎn)擊網(wǎng)頁時(shí)形成連續(xù)的、數(shù)據(jù)量巨大的點(diǎn)擊流信息，保存所有數(shù)據(jù)是不現(xiàn)實(shí)的。當(dāng)點(diǎn)擊流信息產(chǎn)生時(shí)，首先，數(shù)據(jù)流處理模塊負(fù)責(zé)接收數(shù)據(jù)、流量控制等。然后，通過數(shù)據(jù)流頻繁項(xiàng)挖掘模塊快速、有效