高維數據流聚類分析及離群點檢測研究.pdf

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

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

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

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

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

6、討論．本論文進一步將離群點檢測問題擴展到分布式數據流環(huán)境下，提出了基于時間相關滑動窗口和WFPOF的高維分布式數據流離群點檢測算法．該算法將不同站點的數據流放在同等地位上，將它們作為全局數據流的子集，在每個分布站點上維護本地數據流的頻繁模式，并在此基礎上由中心站點生成全局頻繁模式，而各分布站點利用全局頻繁模式計算WFPOtF值，檢測本地的離群點．算法對分布環(huán)境下站點間的協調通信以及局部頻繁模式和全局頻繁模式的維護等問題進行了詳細的討論，