基于圖的空間離群檢測算法分析與研究.pdf

1、基于圖的空間離群檢測算法分析與研究重慶大學碩士學位論文（學術學位）學生姓名：陳濤指導教師：朱慶生教授專業(yè)：計算機軟件與理論學科門類：工學重慶大學計算機學院二O一三年四月重慶大學碩士學位論文中文摘要I摘要空間離群檢測能夠幫助人們發(fā)現(xiàn)潛在的、有趣的空間數(shù)據模式，并把它用于未來演變趨勢的分析研究。在許多實際情況下，這些不尋常的空間離群事件往往具有出乎意料的研究價值，因此空間離群檢測被廣泛應用于城市的人口普查研究、氣候異常檢測、傳感器異常檢測、

2、衛(wèi)星圖像檢測等重要領域?？臻g離群對象既可以是離群單點，也可以是離群區(qū)域，目前主要的空間離群檢測算法將二者孤立出來，區(qū)別地對待和研究，然而能夠同時檢測空間離群單點與空間離群區(qū)域的研究成果還相對較少?？臻g對象受到空間自相關與空間異質性的影響，空間近鄰關系的對待在很大程度上決定了算法的準確性。本文在研究分析現(xiàn)有離群檢測算法的基礎上，針對空間離群檢測的關鍵問題和已有算法的不足，提出了兩個基于圖的空間離群檢測算法。研究工作主要包括：①研究了離群檢

3、測的基礎技術框架，系統(tǒng)地分析和對比了傳統(tǒng)離群檢測算法的基本原理，并介紹了離群檢測領域中的研究熱點；②全面分析研究了空間數(shù)據所具有的特性，對常見的空間近鄰關系表達方法進行了闡述與比較；分別概述了空間單點檢測算法與空間區(qū)域檢測算法；③利用WDNN(WeightedDelaunayNearestNeighb)圖的構造原理，提出了一種基于裁邊策略的空間離群檢測算法，采用基于二部圖最短邊的空間離群因子，通過反復裁去―最大邊‖來實現(xiàn)空間離群單點和離

4、群區(qū)域二者之間的并發(fā)查找，隔離了―壞鄰居‖對正常數(shù)據的干擾，有效避免了經典算法中常出現(xiàn)的錯誤檢測問題；④在裁邊算法的基礎上，提出了一種基于MST(MinimumSpanningTree)分割策略的改進算法，利用MST的優(yōu)良性質，最大程度地簡化了WDNN圖，減少了原圖中等待裁邊的數(shù)量和相關圖搜索次數(shù)，降低了檢測算法的時間規(guī)模，達到對空間離群快速檢測的目的；論文中使用來自于國家統(tǒng)計局的真實數(shù)據集和一組人工數(shù)據集來進行實驗，直觀地展示了本文算