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

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

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

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

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

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