數(shù)據(jù)流挖掘若干問題的研究.pdf

1、隨著計算機網(wǎng)絡、數(shù)據(jù)庫、多媒體等技術的飛速發(fā)展和日益普及，數(shù)據(jù)流模型在傳感器網(wǎng)絡、金融證券分析、數(shù)據(jù)挖掘、制造業(yè)和天文等領域得到了廣泛的應用。和傳統(tǒng)的數(shù)據(jù)模型相比，數(shù)據(jù)流模型具有截然不同的特點：數(shù)據(jù)量無窮：對問題要求快速響應；數(shù)據(jù)概念隨時間變化。傳統(tǒng)的數(shù)據(jù)挖掘技術主要是針對靜態(tài)和有限的數(shù)據(jù)，很難被應用到數(shù)據(jù)流這種新的模型中去，這促使越來越多的研究人員深入研究數(shù)據(jù)流模型，設計出新的數(shù)據(jù)處理方案。本文分析了當前數(shù)據(jù)流挖掘中的頻繁元素挖掘、數(shù)

2、據(jù)流分類、卸載處理和特征選擇等關鍵技術，并針對其中的一些問題提出了改進方案和算法。主要工作和創(chuàng)新點有： 1.提出了HCOUNT+算法來挖掘數(shù)據(jù)流上的頻繁元素。HCOUNT+算法采用了一個輔助的措施來改進HCOUNT算法，雖然增加了有限的空間開銷，但較大地提高了HCOUNT算法的準確率。HCOUNT+算法僅需要(1+α)·e/ε·ln(-M/lnp)(α＜1)個計數(shù)器，就能夠估算每個元素的值，且最大誤差不超過ε。在此基礎之上，本文

3、還提出了SL-HCOUNT+算法來挖掘數(shù)據(jù)流上最近出現(xiàn)的所有頻繁元素，而不僅僅是傳統(tǒng)算法所挖掘的TOP-K的頻繁元素。理論證明HCOUNT+算法和SL-HCOUNT+算法在挖掘頻繁元素上具有較好的時間復雜度和空間復雜度，實驗結果證實了這兩種算法有較高的查詢精度。 2.提出了基于邏輯回歸的ELRClass算法來處理數(shù)據(jù)流的分類問題。邏輯回歸有一些優(yōu)良的特點：運行效率高；能在小樣本上獲得很高的分類準確率；能非線性處理離散的和連續(xù)的數(shù)

4、據(jù)。ELRClass算法使用邏輯回歸到滑動窗口中的數(shù)據(jù)，持續(xù)監(jiān)測和更新當前的分類器。如果分類器性能的變壞是由于突發(fā)噪聲而引起，則保持原有的分類器。如果檢測到概念發(fā)生漂移，則構建和使用新的分類器。實驗結果驗證了ELRClass算法的有效性。 3.提出了幾個基于支持向量機的算法來處理數(shù)據(jù)流的多分類問題。本文首先分別為一對一算法、一對多算法和DB2算法提出了一個增量式的改進算法One2One，One2Rest和LDB2，這些算法有對大

5、容量數(shù)據(jù)進行多分類的能力。在每個增量步驟僅僅保留支持向量，這些支持向量加到下一個批次數(shù)據(jù)作為訓練樣本，構建若干個二分類器。在測試階段，LDB2算法平均使用logN2個分類器，One2All算法使用N個分類器，One2One算法使用N(N-1)/2個分類器，所以LDB2算法比One2All算法和One2One算法的測試速度都要快。實驗結果顯示LDB2算法比One2One算法和One2Rest算法的分類交叉準確率都要高。本文還提出了一個能實

6、時檢測局部概念漂移并隨之自適應調整的數(shù)據(jù)流分類算法IncreDB2。當局部概念漂移出現(xiàn)時，IncreDB2算法不是重新構造一個全新的DB2層次分類樹，而是僅更新漂移所影響的局部結點，具有較好時間運行效率。實驗結果表明該算法可以有效解決數(shù)據(jù)流分類中出現(xiàn)的局部概念漂移的問題。 4.提出了RLS算法來進行數(shù)據(jù)流管理系統(tǒng)的卸載處理。本文指出查詢操作符的選擇率會由于卸載操作的執(zhí)行而改變，在卸載操作前后可能會有突變。而傳統(tǒng)的卸載算法在確定卸

7、載地點時候，通常假定選擇率在卸載前和卸載后保持不變，這使傳統(tǒng)算法得到的卸載地點并不是最合適的。與傳統(tǒng)卸載算法不同的是，RLS算法使用卸載操作后的選擇率，而不是卸載操作前的選擇率來確定最合適的卸載地點。實驗結果表明RLS算法具有較好的查詢準確率。 5.提出了兩個基于OCFS算法的特征選擇算法POCFS和POCFS+。大部分的特征選擇算法是貪婪算法，不能提供最優(yōu)解，而最近提出的基于正交中心思想的最優(yōu)特征選擇算法(OCFS算法)能依據(jù)