高效數(shù)據(jù)流和海量文本處理算法研究.pdf

1、隨著網(wǎng)絡(luò)通信技術(shù)的迅速發(fā)展，以數(shù)據(jù)流形式呈現(xiàn)的數(shù)據(jù)大量涌現(xiàn)在各個信息處理領(lǐng)域。例如無限傳感器網(wǎng)絡(luò)中傳回基站的傳感數(shù)據(jù)流，人們?yōu)g覽網(wǎng)頁時產(chǎn)生的網(wǎng)絡(luò)點擊流，還有證券買賣產(chǎn)生的實時交易信息等等。數(shù)據(jù)流具有數(shù)據(jù)量大，持續(xù)快速產(chǎn)生，數(shù)據(jù)分布隨時間變化等等特點。而傳統(tǒng)靜態(tài)數(shù)據(jù)集合中的分析處理技術(shù)往往只適用于處理那些可存儲在磁盤上的有限靜態(tài)數(shù)據(jù)。這些傳統(tǒng)技術(shù)往往都需要多次掃描所處理的全部數(shù)據(jù)，從而使得將它們直接于處理數(shù)據(jù)流時，會帶來嚴(yán)重的低效率和高代

2、價。面對這些持續(xù)快速到達(dá)的海量數(shù)據(jù)流，如何利用有限的資源來有效的分析處理它們成為時下最為關(guān)心的問題。典型的數(shù)據(jù)流分析處理問題包括數(shù)據(jù)流聚類,數(shù)據(jù)流變化檢測,副本檢測等等。
　　 隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)信息的監(jiān)測和管理中急需處理海量文本數(shù)據(jù)(如大量的網(wǎng)絡(luò)網(wǎng)頁)。而傳統(tǒng)的文本分析處理技術(shù)僅適用于處理小規(guī)模的文本數(shù)據(jù)，而難以處理海量的文本數(shù)據(jù)。典型的文本處理問題包括文本分類，文本聚類和文本信息抽取等等。
　　 本文對數(shù)據(jù)流和海

3、量文本處理技術(shù)中若干關(guān)鍵問題進(jìn)行了深入研究，主要包括以下內(nèi)容：
　　 1.一種適用于高維數(shù)據(jù)流變化檢測算法：
　　 本文首先將數(shù)據(jù)流上的變化檢測問題轉(zhuǎn)化為尋找變化顯著單元格的問題。基于頻繁模式挖掘FP算法，設(shè)計一種記錄數(shù)據(jù)流中網(wǎng)格的經(jīng)驗分布變化值的數(shù)據(jù)結(jié)構(gòu)--VT樹（variation tree），并通過搜索VT樹中的路徑來發(fā)現(xiàn)高維數(shù)據(jù)流中所有經(jīng)驗分布變化值大于ε的網(wǎng)格。
　　 2.一種基于代表點的高維數(shù)據(jù)流上聚

4、類算法
　　 傳統(tǒng)的基于網(wǎng)格的聚類算法難以適用于處理處理演化的高維數(shù)據(jù)流。本文對高維數(shù)據(jù)流中數(shù)據(jù)點的每一個維度屬性進(jìn)行單獨量化，并用量化得到的每個維度上的代表點來替代傳統(tǒng)基于網(wǎng)格的聚類算法中的固定劃分區(qū)間。本文算法中代表點是隨著不斷流過的高維數(shù)據(jù)流而演化變化的，從而能比其他數(shù)據(jù)流聚類算法更好的捕捉到演化高維數(shù)據(jù)流中聚類。
　　 3.一種滑動窗口上數(shù)據(jù)流副本檢測的有效算法
　　 本文出一種新的數(shù)據(jù)結(jié)構(gòu)：Flag B

5、loom Filter(FBF)。這種新的數(shù)據(jù)結(jié)構(gòu)改進(jìn)了目前最有效的Decaying Bloom Filter(DBF)?；贔BF，本文提出了一種高效的算法來解決滑動窗口上數(shù)據(jù)流副本檢測問題。給定滑動窗口大小W，計數(shù)器個數(shù)M，F(xiàn)BF比DBF多使用M比特空間，但FBF的誤是率是DBF的2k/(k+1)，其中k=[ln(2)M/W]≥2為使用的哈希函數(shù)個數(shù)。給定同樣的內(nèi)存空間G和滑動窗口大小W（FBF使用的計數(shù)器個數(shù)是DBF的logW/(

6、logW+1)）FBF的誤是率上界為(0.25)k(1-1/logW)(1+k(1-1/logW))。當(dāng)W≥32時，這個上界比DBF的誤是率要小。
　　 4.一種滑動窗口上概率數(shù)據(jù)流副本檢測有效算法
　　 針對確定性數(shù)據(jù)流的副本檢測方法無法保存概率數(shù)據(jù)流中元素的存在概率。基于Counting Bloom Filter，本文提出了一種新的數(shù)據(jù)結(jié)構(gòu)Floating Counter Bloom Filter(FCBF)。基于F

7、CBF結(jié)構(gòu)，我們提出了一種滑動窗口上概率數(shù)據(jù)流的副本檢測算法。給定滑動窗口大小W和浮點計數(shù)器個數(shù)N，針對滑動窗口上的一個元素t，我們的方法以概率1-(1/2)ln(2)*N/W輸出該元素的精確存在概率。
　　 5.針對海量文本的KNN改進(jìn)分類算法：
　　 面對海量文本數(shù)據(jù)時，傳統(tǒng)的KNN分類算法無論在分類精度還是分類時間方面都明顯效果很差。針對這個問題，基于最小化學(xué)習(xí)誤差的增量的思想，本文將學(xué)習(xí)型矢量量化(LVQ)和生長