高維數(shù)據(jù)流聚類分析及離群點(diǎn)檢測研究.pdf

1、數(shù)據(jù)挖掘是在海量數(shù)據(jù)中提取隱含的、未知的、潛在有用的知識(shí)或信息模式的決策支持方法，是20世紀(jì)90年代初解決“數(shù)據(jù)豐富、知識(shí)貧乏”問題應(yīng)運(yùn)而生的一種新技術(shù)．十多年來，眾多學(xué)者圍繞數(shù)據(jù)挖掘這一主題開展深入而系統(tǒng)的研究與探索工作，并已出現(xiàn)諸多研究成果．特別是近幾年來，隨著計(jì)算機(jī)技術(shù)深入應(yīng)用擻據(jù)流(Data Stream)作為一類新的數(shù)據(jù)模型，對現(xiàn)有的數(shù)據(jù)挖掘技術(shù)研究提出了新的要求擻據(jù)流廣泛出現(xiàn)在諸如金融應(yīng)用、網(wǎng)絡(luò)監(jiān)視、通信數(shù)據(jù)管理、Web 應(yīng)

2、用以及傳感器網(wǎng)絡(luò)數(shù)據(jù)處理等眾多領(lǐng)域．由于數(shù)據(jù)流具有快速、無限、連續(xù)、只能一遍掃描等特點(diǎn)，因而對基于數(shù)據(jù)流模型的數(shù)據(jù)挖掘技術(shù)提出了更高的要求，數(shù)據(jù)流數(shù)據(jù)挖掘算法亦已成為重要的研究課題． 在眾多的數(shù)據(jù)挖掘任務(wù)中，聚類分析和離群點(diǎn)檢測由于其在知識(shí)發(fā)現(xiàn)中所發(fā)揮的重要作用而得到重視和深入研究．目前，針對大規(guī)模高維數(shù)據(jù)的聚類分析和離群點(diǎn)檢測問題，研究人員業(yè)已提出了一些有效的算法，其中子空間技術(shù)是解決其“維數(shù)災(zāi)難”的方法之一但是高維數(shù)據(jù)流的

3、數(shù)據(jù)挖掘算法的研究剛剛起步，“維數(shù)災(zāi)難”以及數(shù)據(jù)流數(shù)據(jù)本身所固有的特性，使得這一研究更具有其特有的難度． 針對數(shù)據(jù)流中聚類分析的需求以及現(xiàn)有數(shù)據(jù)流聚類算法無法有效處理高維數(shù)據(jù)流的不足，本論文首先提出了基于Hoeffding界的高維數(shù)據(jù)流的子空間聚類發(fā)現(xiàn)及維護(hù)算法．該算法將數(shù)據(jù)流分段(分段長度由Hoeffding界確定)，在數(shù)據(jù)流分段上進(jìn)行子空間聚類，通過迭代逐步得到滿足聚類精度要求的聚類結(jié)果．同時(shí)針對數(shù)據(jù)流的動(dòng)態(tài)性，算法對聚類結(jié)

4、果進(jìn)行調(diào)整和維護(hù)；其次，研究了數(shù)據(jù)流的聚類演化分析，針對現(xiàn)有算法的局限性，提出了相應(yīng)的改進(jìn)算法，并進(jìn)行理論和實(shí)驗(yàn)上的討論．內(nèi)容主要包括金字塔時(shí)間結(jié)構(gòu)的改進(jìn)，子空間密集網(wǎng)格的計(jì)數(shù)方法以及聚類演化分析的策略等；最后針對考察特定時(shí)間周期內(nèi)數(shù)據(jù)流數(shù)據(jù)的應(yīng)用需求，提出了基于時(shí)間相關(guān)滑動(dòng)窗口的高維數(shù)據(jù)流聚類算法．該算法能夠有效處理Turnstile型數(shù)據(jù)流的聚類問題，著重討論了子空間網(wǎng)格的內(nèi)存保存機(jī)制，滑動(dòng)窗口中數(shù)據(jù)的更新方式以及對于Turnsti

5、le型數(shù)據(jù)流的適應(yīng)性． 本論文還針對高維類別屬性數(shù)據(jù)流離群點(diǎn)檢測問題，首先提出了基于加權(quán)頻繁模式離群因子(WFPOF)的數(shù)據(jù)流離群點(diǎn)檢測算法．該算法利用WFPOF能夠有效度量高維數(shù)據(jù)離群度的特點(diǎn)，結(jié)合可適應(yīng)離群點(diǎn)檢測處理需求的數(shù)據(jù)流頻繁模式發(fā)現(xiàn)維護(hù)方法，快速檢測離群點(diǎn)．同時(shí)通過數(shù)據(jù)衰減系數(shù)的設(shè)定，可以有效的處理數(shù)據(jù)流數(shù)據(jù)中的概念轉(zhuǎn)移問題．該算法還對數(shù)值屬性和混合屬性的數(shù)據(jù)流的處理、數(shù)據(jù)離群原因的解釋以及類離群點(diǎn)檢測問題進(jìn)行了深入

6、討論．本論文進(jìn)一步將離群點(diǎn)檢測問題擴(kuò)展到分布式數(shù)據(jù)流環(huán)境下，提出了基于時(shí)間相關(guān)滑動(dòng)窗口和WFPOF的高維分布式數(shù)據(jù)流離群點(diǎn)檢測算法．該算法將不同站點(diǎn)的數(shù)據(jù)流放在同等地位上，將它們作為全局?jǐn)?shù)據(jù)流的子集，在每個(gè)分布站點(diǎn)上維護(hù)本地?cái)?shù)據(jù)流的頻繁模式，并在此基礎(chǔ)上由中心站點(diǎn)生成全局頻繁模式，而各分布站點(diǎn)利用全局頻繁模式計(jì)算WFPOtF值，檢測本地的離群點(diǎn)．算法對分布環(huán)境下站點(diǎn)間的協(xié)調(diào)通信以及局部頻繁模式和全局頻繁模式的維護(hù)等問題進(jìn)行了詳細(xì)的討論，