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

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

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

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

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

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

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

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