數據流中離群和變化發(fā)現(xiàn)研究.pdf

1、數據挖掘是從數據庫中識別出有效的、新穎的、潛在有用的并最終可理解模式的非平凡過程，其在功能上的健壯性和應用領域的廣泛性已被研究者一致認同．十多年來，眾多學者圍繞數據挖掘這一主題開展深入而系統(tǒng)的研究與探索工作，并已出現(xiàn)大量研究成果．特別是近幾年來，隨著計算機技術深入應用，數據流(Data Stream)作為一類新的數據模型，對現(xiàn)有的數據挖掘算法研究提出了有力的挑戰(zhàn)．數據流廣泛出現(xiàn)諸如金融應用、網絡監(jiān)視、通信數據管理、Web應用以及傳感器網

2、絡數據處理等眾多領域中．由于數據流數據具有潛在無限，只能進行一遍或較少次數的掃描，實時到達等特點，因而對基于數據流模型的數據挖掘算法提出了更高的要求，數據流數據挖掘算法業(yè)已成為了研究的熱點問題。 在眾多的數據挖掘任務中，離群檢測和變化檢測由于其在知識發(fā)現(xiàn)中所發(fā)揮的重要作用而得到重視和深入研究．但是現(xiàn)有的離群檢測和變化檢測技術大多針對傳統(tǒng)的靜態(tài)數據集，不能直接應用于數據流數據。 針對以上所述對數據流中離群知識發(fā)現(xiàn)的需求以及

3、目前離群點檢測算法時間空間復雜度較高的問題，本論文以Turnstile型數據流數據為研究對象，首先提出了一種基于動態(tài)網格劃分的離群點快速檢測算法．為減少候選離群點的規(guī)模，算法利用數據主體性的特點，對數據空間采用了快速直接、時間相關的動態(tài)劃分方法，過濾大量主體數據，而僅對較小數量的候選離群點進行近似離群度計算．文中給出了網格的劃分、存儲、篩選以及離群點檢測的具體方法，并分析了算法的時間空間復雜度．通過在真實和仿真數據集上的測試，驗證了算法

4、的有效性。 其次本論文同時將離群點檢測問題擴展到分布式數據流環(huán)境下，提出了基于核密度估計的分布式數據流離群點檢測算法．本論文將不同節(jié)點的數據流放在同等的地位上，將它們作為全局數據流的子集，著重討論全局環(huán)境下的離群點檢測問題．算法在每個分布節(jié)點維護本地數據流的密度估計信息，并在此基礎上由中心節(jié)點生成全局密度估計信息，而各個節(jié)點利用該信息檢測本地的離群點．算法對分布環(huán)境下節(jié)點間的協(xié)調通訊、統(tǒng)計信息維護以及離群點檢測等問題進行詳細的討

5、論，并通過實驗驗證算法的可行性和有效性。 第三，本論文從數據空間分布密度變化的角度，針對現(xiàn)有算法的局限性，提出相應的改進方法，并進行理論和實驗上的討論．本論文采用滑動窗口模型下的計數方式對數據分布的變化進行考察，該方法可以及時有效的發(fā)現(xiàn)數據空間中的密度變化情況，并對變化區(qū)域進行動態(tài)的跟蹤檢測以及可視化表示。 綜上，數據流中的離群和變化模式檢測是一類重要的數據挖掘方法，本文針對該問題，提出了一系列改進算法，這些新算法將有效