離群數據挖掘綜述

（福州大學 福建省空間信息工程研究中心 數據挖掘與信息共享教育部重點實驗室， 福建 福州 350002）

摘 要：通過對當前有代表性的離群數據挖掘算法的分析和比較，總結了各算法的特性及優缺點，為使用者選擇、學習、改進算法提供了依據。此外，針對高維數據和空間數據中離群檢測的特殊性，在現有算法的基礎上，分析了高維數據和空間數據離群檢測需要注意的一些問題，以便于研究者提出新的有效的算法。

關鍵詞：數據挖掘； 離群檢測； 異常； 高維離群

中圖法分類號：TP391文獻標識碼：A

文章編號：0013695(2006)08-0008-06

Review of Outlier Detection

HUANG Hongyu， LIN Jiaxiang， CHEN Chongcheng， FAN Minghui

(Key Laboratory of Data Mining Information Sharing of Ministry of Education， Spatial Information Research Center of Fujian， Fuzhou University， Fuzhou Fujian 350002， China)

Abstract: This paper compared and analyzed major outlier detection algorithms. Their features were summarized to help users choose， study and improve algorithm for outlier detection. Attention was paid to highdimensional data and spatial data because of their unique data structures as better and efficient algorithm is needed to deal with these types of data.

Key words: Data Mining; Outliers Detection; Exception; HighDimension Outliers

1引言

自從20世紀90年代中期數據挖掘引起人們的廣泛興趣以來，它便得到了迅猛的發展。通常，數據挖掘被劃分為四種類型[2]，即相關依賴關系的發現、類別的判定、類別的描述、離群或異常(Outlier)數據挖掘。前三類是針對數據集中的大部分數據記錄均服從的數據模式，而離群檢測的目的在于找出隱含在海量數據中相對稀疏而孤立的異常數據模式，這是離群檢測與關聯規則等傳統的面向數據主體的數據挖掘的主要區別。早期，對數據集進行預處理時，通常把離群點當作噪聲，或修正離群點的值以減少其對正常數據的影響。盡管離群檢測是為了發現數據集中極少數的一些數據，然而離群數據挖掘常常比其他類型的挖掘來得更有價值，因為一萬個正常的記錄很可能只覆蓋一條規則，而十個離群很可能就意味著十條不同的規則。實際生活中，離群檢測有著很廣泛的應用，如網絡入侵檢測、信用卡惡意透支、貸款證明的審核等。

離群挖掘通常可以看作三個子問題：①什么樣的數據是異常，即離群點的定義；②有效挖掘離群的方法；③離群點的意義，即離群挖掘結果的合理解釋。到目前為止，離群點還沒有一個被普遍采納的定義，Hawkins[3]對離群定義在一定意義上揭示了離群點的本質：“離群點與其他點如此不同，以至于讓人懷疑它們是由另外一個不同的機制產生的。”現有的離群點的定義大多是在Hawkins定義的基礎上給出的一個定量化描述。

統計學上，離群數據挖掘與聚類分析一定程度上是相似的，因為聚類的目的在于尋找性質相同或相近的記錄，并歸為一個類，根據離群的意義，那些與所有類別性質都不一樣的記錄則為離群點。因此，早期的離群檢測多見于統計領域，一些典型的具有離群檢測功能的聚類算法有CLARANS，DBSCAN，OPTICS等[4～10]。然而，離群檢測與聚類分析有著本質的區別，因為聚類的目的主要在于尋找類別，離群點只是它們的一個附屬物，因此，由聚類算法挖掘得到的離群點通常是不準確的。

近年來，研究人員提出了大量的離群檢測算法[1，2，13，19～22]，大致可以把它們歸納為以下幾類：基于統計的方法、基于密度的方法、基于深度的方法、基于距離的方法和基于偏離的方法[52]。下面我們對各檢測算法進行綜述。

2離群檢測

2．1．基于統計的離群檢測算法

基于統計的方法[11]是出現得最早的離群點檢測方法，它基于對小概率事件的判別來實現對數據樣本異常的鑒別。其主要思想是假定數據集服從某種分布或概率模型，通過不一致檢驗把那些嚴重偏離分布曲線的記錄視為離群點。這方面比較有代表性的有1967年Mikey， Dunn Clark提出的基于“均數漂移”[38]模型的單點診斷量[39]，1970年Gentleman Wilk提出的群組診斷量[40]，1972年Tietjen Moore提出的單樣本k個離群點的統計量E_k[41]，1985年Marasinghe提出的改進的E_k統計量F_k[41]，1989年Rosner提出的單樣本多個離群檢測算法ESD(Generalized Extreme Studentized Deviate)方法[42]，1991年Paul Fung改進了ESD方法參數k選擇的主觀性，提出了回歸分析的GESR(Generalized Extreme Studentized Deviate Resi dual)方法[42]。近年來，多樣本的離群檢測方法也得到了一定的發展，總的思路是先盡量得到一個不含離群點的“干凈集”[37]，然后在此基礎上對剩余的其他數據點進行逐步離群檢測。

基于統計的方法檢測出來的離群點很可能被不同的分布模型檢測出來，可以說產生這些離群點的機制可能不唯一，解釋離群點的意義時經常發生多義性，這是基于統計方法的一個缺陷；其次，基于統計的方法在很大程度上依賴于待挖掘的數據集是否滿足某種概率分布模型[29]，模型的參數、離群點的數目等對基于統計的方法都有非常重要的意義，而確定這些參數通常都比較困難。為克服這一問題，一些人提出對數據集進行分布擬合，但分布擬合存在兩個問題[46]：①給出的分布可能不適合任一標準分布；②即使存在一個標準分布，分布擬合的過程耗時太長。此外，基于統計的離群檢測算法大多只適合于挖掘單變量的數值型數據，目前幾乎沒有多元的不一致檢驗，對于大多數的應用來說，例如圖像和地理數據，數據集的維數卻可能是高維的。實際生活中，以上缺陷都大大限制了基于統計的方法的應用，使得它主要局限于科研計算，算法的可移植性較差。

2.2.基于距離的離群檢測算法

基于距離的離群點最早是由Knorr和Ng[2，23]提出的，他們把記錄看作高維空間中的點，離群點被定義為數據集中與大多數點之間的距離都大于某個閾值的點，通常被描述為DB(pct，d_min)，數據集T中一個記錄O稱為離群點，當且僅當數據集T中至少有pct部分的數據與O的距離大于d_min。換一種角度考慮，記M=N×(1-pct)，離群檢測即判斷與點O距離小于d_min的點是否多于M。若是，則O不是離群點，否則O是離群點。基于距離的離群點定義包含并拓展了基于統計的思想，即使數據集不滿足任何特定分布模型，它仍能有效地發現離群點，特別是當空間維數比較高時，算法的效率比基于密度的方法要高得多[7]。算法具體實現時，首先給出記錄間距離的度量[20]，常用的是絕對距離（曼哈頓距離）、歐氏距離和馬氏距離。在給出了距離的度量并對數據進行一定的預處理以后，任意給定參數pct和d_min就可以根據離群的定義來檢測離群。Rastogi Ramaswamy在上面基于距離的離群點定義的基礎上，提出改進的基于距離的k-最近鄰（k-NN）離群檢測算法[24，30]。用D^k(P)表示點P的第k個最近鄰點的距離，首先計算出數據集T中所有點的k-最近鄰距離，然后按值大小降序排列，算法把排在最前面的n₀個點標記為n₀個離群點。此算法的一個主要缺陷是要計算所有點的D^k(P)，每計算一個點的D^k(P)就要掃描一次數據集，對于大數據集，其I/O次數常常使得算法的計算效率非常低。針對k-最近鄰算法的這個主要缺陷，不少人對算法進行了不同程度的改進，如基于索引的算法引進索引的思想來提高算法的效率[1，47]；循環嵌套算法主要從減少操作的I/O次數方面來改善算法的效率[2，47]；基于單元的算法通過結合點的局部密度的方法來提高異常檢測的效率[1，48]。

基于距離的離群檢測方法中，算法需要事先確定參數pct和d_min，對于不同的數據集這往往是一件比較困難的事情，特別是d_min，不同聚類密度的數據集d_min會有很大的差異，而這一般沒有規律可循，因此，對于給定的不同d_min，異常檢測結果通常具有很大的不穩定性[65]。另一方面，基于距離的方法理論上能處理任意維任意類型的數據，當屬性數據為區間標度等非數值屬性時，記錄之間的距離不能直接確定，通常需要把屬性轉換為數值型[25，26]，再按定義計算記錄之間的距離。當空間的維數大于三維時，由于空間的稀疏性，距離不再具有常規意義，因此很難為異常給出合理的解釋。針對這個問題，一些人通過將高維空間映射轉換到子空間的辦法來解決數據稀疏的問題，此方法在聚類算法中用得比較多[10，18]，Agarwal R.等人[10]曾試著用這種投影變換的方法來挖掘離群。總的來說，基于距離的離群檢測方法具有比較直觀的意義，算法比較容易理解，因此在實際中應用得比較多。

基于距離的方法與基于統計的方法相比，不需要用戶擁有任何領域知識，與序列異常相比，在概念上更加直觀。更重要的是，距離異常接近Hawkins的異常本質定義。然而，三種類型的基于距離的離群檢測算法中，基于索引的算法和循環——嵌套算法需要O(k×n²) 的時間開銷，因此在大數據集中還有待于改進；而基于單元的算法，雖然與n具有線性的時間關系，但是它與k成指數關系，這限制了它在高維空間中的應用，此外，基于單元的算法還需要事先確定參數pct，d_min以及單元的大小，這使得算法的可行性比較差；高維空間中，基于索引的方法由于需要事先建立數據集的索引，建立與維護索引也要花大量的時間。因此三種方法對于高維空間中的大數據集，算法的效率都不高[47]。

2.3基于密度的離群檢測算法

基于密度的離群檢測算法[12，66]一般都建立在距離的基礎上，某種意義上可以說基于密度的方法是基于距離的方法中的一種，但基于密度的異常觀點比基于距離的異常觀點更貼近Hawkins的異常定義，因此能夠檢測出基于距離的異常算法所不能識別的一類異常數據——局部異常[66]。基于密度的方法主要思想是將記錄之間的距離和某一給定范圍內記錄數這兩個參數結合起來，從而得到“密度”的概念，然后根據密度判定記錄是否為離群點。

Breunig等人提出的基于局部離群因子的異常檢測算法LOF[4，13，41]是基于密度方法的一個典型例子。它首先產生所有點的MinPts-鄰域及MinPts-距離，并計算到其中每個點的距離；對低維數據，利用網格進行k-NN查詢，計算時間為O(n)；對中維或中高維數據，采用如X樹等索引結構，使得進行k-NN查詢的時間為O(logn)，整個計算時間為O(nlogn )；對特高維數據，索引結構不再有效，時間復雜度提高到 O(n²)[66，67]。然后計算每個點的局部異常因子，最后根據局部異常因子來挖掘離群。LOF算法中，離群點被定義為相對于全局的局部離群點，這與傳統離群的定義不同，離群不再是一個二值屬性(要么是離群點，要么是正常點)，它擯棄了以前所有的異常定義中非此即彼的絕對異常觀念，更加符合現實生活中的應用。LOF算法中充分體現了“局部”的概念，每個點都給出了一個離群程度，離群程度最強的那幾個點被標記為離群點。此外，Aggarwal[18]也提出了一個結合子空間投影變換的基于密度的高維離群檢測算法。

2.4基于深度的離群檢測算法

基于深度的離群點檢測算法[21，22]的主要思想是先把每個記錄標記為k維空間里的一個點，然后根據深度的定義(常用Peeling Depth Contours[22]定義)給每個點賦予一個深度值；再根據深度值按層組織數據集，深度值較小的記錄是離群點的可能性比深度值較大的記錄大得多，因此算法只需要在深度值較小的層上進行離群檢測，不需要在深度值大的記錄層進行離群檢測。基于深度的方法比較有代表性的有Struyf和Rousseeuw提出的DEEPLOC[19]算法。雖然，理論上基于深度的識別算法可以處理高維數據，然而實際計算時，k維數據的多層操作中，若數據集記錄數為N，則操作的時間復雜度為Ω (N_[k/2])。因此，當維數 k≤3 時處理大數據集時還有可能是高效的，而當k≥4 時，算法的效率就非常低。也就是說，已有的基于深度的離群點檢測算法無法挖掘高維數據，只有當k≤3時計算效率才是可接受的。

2.5基于偏移的離群檢測算法

基于偏移的離群檢測算法(Deviation－based Outlier Detection)[14～16，28]通過對測試數據集主要特征的檢驗來發現離群點。目前，基于偏移的檢測算法大多都停留在理論研究上，實際應用比較少。以下三種是比較有代表性的：①Arning[14]采用了系列化技術的方法來挖掘離群，由于算法對異常存在的假設太過理想化，因此并沒有得到普遍的認同，對于現實復雜數據，其效果不太好，經常遺漏了不少的異常數據；②Sarawagi[15]應用OLAP數據立方體引進了發現驅動的基于偏移的異常檢測算法；③Jagadish[16]給出了一個高效的挖掘時間序列中異常的基于偏移的檢測算法。雖然，基于偏移的離群檢測算法理論上可以挖掘各種類型的數據，但是由于要事先知道數據的主要特征，而現實世界中的數據集一方面由于數據量比較大，另一方面由于屬性比較多，因此這方面的特征往往不容易發現，當確定記錄之間的相異度函數時，如果選擇不合適，則得到的離群挖掘結果很可能不盡人意，所以本方法在實際問題中應用得比較少。表1列出了上述各種類型的離群檢測方法的一些主要特性。

總的來說，以上各離群檢測算法，除基于統計的方法外，大多基于數據挖掘的思想，它們不需要對數據集的分布特征附加任何假設，而只需從數據集本身出發對數據進行檢測，發現其中包含的異常模式，這使得算法具有較大的可行性和可移植性。然而，大部分檢測方法多存在一個缺陷，即把算法重點放在離群點的識別上，而常常忽略了用戶最關心的離群點的現實意義。此外，實際生活中的數據往往具有較大的噪聲，異常模式只存在于低維子空間中，而高維空間中的異常都比較難確定，傳統的離群檢測算法在數據特性完全不同的高維數據中性能急劇下降。例如Knorr Ng等人[27]提出的基于距離的FindAllOutsD；Joshi等人[35]提出的基于機器學習方法的二階段規則推導算法NP－rule；Yu等人[60]提出的基于小波變換的FindOut和Breuning等人[13]提出的基于密度的LOF等沒有充分考慮離群點檢測問題的特點，在內存有限的條件下，缺乏數據的預處理，經常導致頻繁的數據交換和難以容忍的空間復雜度，且算法一般均有 O(N×logN )以上的時間復雜度。在處理海量高維數據中，算法經常無法獲得令人滿意的響應速度，有些算法甚至失效。

3高維離群檢測算法

到目前為止提出的大多數離群檢測算法對高維數據的異常檢測效果都不是很理想。高維空間離群檢測與其他數據集的離群檢測差別甚大的原因主要有兩個：①高維空間數據的稀疏性經常導致所有記錄在傳統距離的意義上都很有可能是離群點[10]，因此，高維空間中很難找到一個通用的離群產生機制；②高維空間中的離群檢測算法的計算復雜度通常都比較高，算法的執行效率極低[44]。高維空間中的異常檢測通常采用Aggarwal Yu提出的高維數據異常檢測方法[45]，基本思想是把高維空間投影到子空間，采用演化計算來尋找最優子空間，降低空間的維數，然后利用傳統的檢測算法來發現異常。具體實現時，高維空間中異常模式的檢測通常是非常困難的，一個最簡單的辦法是考慮數據維的所有可能組合，對所有子空間進行異常模式的搜索。這種方法雖然能找出全局最優的離群點，然而對于具有n個屬性的數據集，可能的維數組合數為2ⁿ，對于高維數據，這個數字將是一個天文數字，因此算法的執行效率非常差。針對這一缺陷，近年來Aggarwal Yu 運用遺傳算法[43]優化了這個問題的求解，并取得良好效果。其他的典型算法還有：SLOT(Subspace Local Outlier Test)[13]，它通過對低維子空間中離散系數上下限的估計，預先去除大量不可能成為異常的數據，從而大大提高了算法的效率。Bially[34，60，61]提出了利用分形中的空間填充曲線Hilbert曲線，將多維空間中的對象映射到低維子空間，根據變換保持空間聚集特性不變來解決挖掘高維空間中的離群點。

Aggarwal[18]提出了高維空間中值得思考的幾點建議：①處理好高維空間中數據的稀疏問題；②合理地解釋離群產生的原因；③必須確定適當的度量，以解釋K維子空間中離群的物理意義；④超高維數據離群檢測算法的時空效率問題；⑤當決定某個點是否是離群點時，必須能為局部數據行為提供價值。因此，要提高高維空間中離群檢測的效率，我們必須進一步改善獲得的投影子空間。在傳統的直接映射到某個低維子空間，或按屬性加權平均求得一個綜合傾斜度的投影之前，先對數據進行旋轉變化，求出數據的一個基準生成器，再把數據映射到一個改進的基準坐標面上，按各屬性加權進行離群檢測，這樣得到的離群點通常都能比較真實地反映離群，也能比較好地解釋離群點的意義。然而，基于投影的高維空間離群檢測僅能對數值屬性數據進行分析處理，對名稱標度等非數值屬性，如何選擇一個合適的投影子空間還有待于進一步研究。總之，要構造好的高維空間離群檢測算法，我們必須充分利用高維數據自身的特性，處理好數據集的主體聚類性與稀疏性之間的矛盾，以提高異常檢測算法的效率。

4空間數據的離群檢

空間數據自身的獨特性使得其與關系數據存在著巨大的差別，除了包含屬性數據外，還包含了空間關系數據。因此，空間數據集中的異常檢測比關系數據中的離群異常檢測來得復雜，因為空間對象經常受到鄰近對象的影響，因此空間異常檢測只有充分考慮了對象的近鄰點的影響才能獲得有用的知識[63，64]。空間例外是指那些非空間屬性值和鄰域中其他空間對象的非空間屬性明顯不同的空間對象[49，63]，兩個空間對象的差異程度通常用相異度來衡量。由于空間數據自身的特殊性，空間離群點一般是局部不穩定的，這種局部意義上的離群點在全局中不一定仍為離群點。空間例外挖掘是空間數據挖掘領域的一個重要研究內容，例外知識的發現能為我們提供豐富的信息，在地理信息系統、遙感圖像數據勘測、公眾安全與衛生、交通控制、基于地理位置的服務[55]等各種領域有著廣泛的應用。

空間數據集的離群檢測方法大致可以分成三類[57，63]：基于集合的例外、基于多維屬性空間的例外和基于圖的例外。基于集合的例外是在不考慮空間關系的數據集合中，屬性值和其他數據對象屬性值不一致的數據對象。嚴格上講，基于多維屬性空間的例外和基于圖的例外才是真正意義上的空間例外，即屬性值和其空間鄰域中的其他對象明顯不同的空間對象，兩者的不同在于空間鄰域的定義不同，前者的空間鄰域定義是基于距離，而后者的定義是基于圖的連接性。基于多維屬性空間的例外檢測算法則對空間例外與其他數據之間的區別進行檢驗，代表性的算法有Scatterplot[50，52]和Moran Scatterplot[53]；基于圖的例外檢測算法在空間數據的可視化基礎上，將空間離群點突出地顯示出來以達到檢測的效果，典型的算法有Variogram Clouds和Pocket Plots[51，54]以及Shekhar等人在文獻[56，57]中引進的在圖形數據庫中基于點與鄰域點的關系的空間離群點檢測方法。與非空間數據的離群檢測類似，這些算法有個缺點，即可能忽略某些空間離群點，同時，算法可能錯判一些空間離群點。針對這個缺陷，Lu等人在文獻[49]中通過多次循環的方式對算法進行了一定的改進，主要思想是每次循環都只識別一個空間離群點，并修正離群點的值以使它不影響后續的離群點檢測。

5結論與展望

異常檢測在很多領域中有著非常重要的應用，不久的將來它將在更多鄰域中發揮更重要的作用。現有的大多離群檢測算法在高維空間、時間序列以及地理數據中的效率還比較低，算法還或多或少地存在各種不同的缺陷，如何發揮數據集自身的主體聚類性和完備性，最大化相異數據之間的差異，最小化相似數據之間的差異，提高算法的時空效率和可移植性是離群檢測面臨的具有挑戰性的工作。最新文獻表明，地學數據的離群檢測算法、動態環境下異常的增量式挖掘算法、長時間序列離群檢測算法以及基于人工智能的離群檢測算法將是未來一段時間內離群數據挖掘領域的一個主要研究方向。

參考文獻：

[1] Han Jiawei，Kamber M.Data Mining: Concepts and Techniques[M]. Academic Press， 2001.

[2]Knorr E M，Ng R T.Algorithms for Mining Distancebased Outliers in Large Datasets[C]. New York: Proc.of Int. Conf. Very Large Databases(VLDB’98)， 1998.392-403.

[3]Hawkins D. Identification of Outliers[M]. London: Chapman and Hall， 1980.

[4]Ng R T， Han J. Efficient Clustering Methods for Spatial Data Mining[A]. Bocca J B， Jarke M， Zaniolo C. Proc.of the 20th International Conference on Very Large Data Bases[C]. Santiago: Morgan Kaufmann，1994.144-155.

[5]Ester M， Kriefel H P， Sander J， et al.A Densitybased Algorithm for Discovering Clusters in Large Spatial Databases with Noise[A]. Simoudis E， Han J， Fayyad U M. Proc.of the 2nd International Confe rence on Knowledge Discovery and Data Mining[C]. Portland: AAAI Press， 1996.226-231.

[6]Zhang T， Ramakrishnan R， Linvy M. Birch: An Efficient Data Clustering Method for Very Large Databases[A]. Jagadish H V， Mumick I S. Proc.of the ACM SIGMOD International Conference on Management of Data[C]. Montreal: ACM Press， 1996.103-114.

[7]Wang W， Yang J， Muntz T R. Sting: A Statistical Information Grid Approach to Spatial Data Mining[A]. Jarke M， Carey M J， Dittrich K R， et al. Proc.of Bases[C]. Athens: Morgan Kaufmann， 1997.186-195.

[8]Sheikholeslami G， Chatterjee S， Zhang A. WaveCluster: A Multi resolution Clustering Approach for Very Large Spatial Databases[A]. Gupta A， Shmueli O， Widom J. Proc.ofthe 24th International Conference on Very Large Databases[C]. New York: Morgan Kaufmann， 1998.428-439.

[9]Hinneburg A， Keim D A. An Efficient Approach to Clustering in Large Multimedia Databases with Noise[A]. Agrawal R， Stolorz P E， Piatetsky Shapiro G. Proc.of the 4th International Conference on Knowledge Discovery and Data Mining[C]. New York: AAAI Press，1998.58-65.

[10]Agrawal R， Gehrke J， Gunopulos D， et al. Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications[A]. Haas L M， Tiwary A. Proc.of the ACM SIGMOD International Conference on Management of Data[C]. Seattle: ACM Press， 1998.94-105.

[11]Barnett V， Lewis T. Outliers in Statistical Data[M]. New York: John Wiley Sons， 1994.

[12]Breunig M M ， Kriegel H P， Ng R T， et al. Optics of: Identifying Density based Local Outliers[A]. Zytkow J M， Rauch. Proc.of the 3rd European Conference on Principles and Practice of Knowledge Discovery in Databases， Lecture Notes in Computer Science 1704[C]. Prague: Springer， 1999.262-270.

[13]Breuning M M， Kriegel H P， Ng R T， et al. LOF: Identifying Density based Local Outliers[A]. Chen W， Naughton J F， Bernstein. Proc.of the ACM SIGMOD International Conference on Management of Data[C]. Dallas: ACM Press， 2000.93-104.

[14]Arning A， Agrawal R， Raghavan P. A Linear Method for Deviation Detection in Large Databases[C]. Proc.of 1996 Int. Conf. Data Mining and Knowledge(Special Issue on High Performance Data Mi ning )， 2000.

[15]Sarawagi S， Agrawal R， Megiddo N. Discovery driven Exploration of OLAP Data Cubes[C]. Valencia: Proc.of Int. Conf. Extending Database Technonlogy(EDBT’98)， 1998.168-182.

[16]Jagadish H V， Koudas N， Muthukrishnan S. Mining Deviants in a Time Series Databases[C]. Edinburgh: Proc.of Int. Conf. Very Large Databases(VLDB’99)， 1999.102-113.

[17]Aggarwal C C， Yu P. Outlier Detection for High Dimensional Data[A]. Aref W G.Proc.of the ACM SIGMOD International Conference on Mana gement of Data[C]. Santa Barbara: ACM Press， 2001.37-47.

[18]Aggarwal C C， Yu P. Finding Generalized Projected Clusters in High Dimensional Spaces[A]. Chen W， Naughton J F， Bernstein P A. Proc.of the ACM SIGMOD International Conference on Management of Data[C]. Dallas: ACM Press， 2000.70-81.

[19]Struyf A， Rousseeuw P J. High dimensional Computation of the Deepest Location[J]. Computational Statistics and Data Analysis， 2000，34:415-426.

[20]袁志發，周靜芋. 多元統計分析[M]. 北京:科學出版社， 2002. 242-243.

[21]Tukey J W. Exploratory Data Analysis[M]. MA: AddisonWesley and Sons， Inc.， 1994.

[22]Preparata F， Shamos M. Computational Geometry: An Introduction[M]. SpringerVerlag， 1988.

[23]Knorr E， Ng R. Finding Intensional Knowledge of Distancebased Outliers[C]. Scotland: Proc.of the 25th VLDB Conference Edinburgh， 1999.211-222.

[24]Knorr E， Ng R. A Unified Approach for Mining Outliers: Properties and Computation[C]. Newport Beach: Proc.of Int. Conf. Knowledge Discovery and Data Mining(KDD’97)， 1997.219-222.

[25]S D Bay， M Schwabacher. Mining Distancebased Outliers in Near Linear Time with Randomization and a Simple Pruning Rule[C]. Washington DC: SIGKDD’03， 2003.

[26]S Ramaswamy， R Rastogi， K Shim. Efficient Algorithms for Mining Outliers from Large Data Sets[C]. Proceedings of the ACM SIGMOD Conference， 2000.427-438.

[27]E M Knorr， R T Ng， V Tucakov. Distancebased Outliers: Algorithms and Applications[J]. VLDB Journal: Very Large Databases， 2000，237-253.

[28]鄭建國，焦李成.偏差檢測挖掘方法研究[J].計算機工程， 2001，27(8):3335.

[29]史東輝，張春陽，蔡慶生.離群數據的挖掘方法研究[J]. 小型微型計算機系統， 2001，22(10):234-236.

[30]F Angiulli， C Pizzuti. Fast Outlier Detection in High Dimensional Spaces[C]. Proceedings of the 6th European Conference on the Principles of Data Mining and Knowledge Discovery， 2002.15-16.

[31]史東輝，蔡慶生，倪志偉，等.基于規則的分類數據離群挖掘方法[J].計算機研究與發展，2000，37(9):109-110.

[32]姜靈敏.基于相似系數和檢測孤立點的聚類算法[J].計算機工程，2003，29(11):183-185.

[33]陸聲鏈，林士敏.基于距離的孤立點檢測及其應用[J].計算機與數字工程，2003，12(22):31-33.

[34]Bially T. Spacefilling Curves: Their Generation and Their Application to Bandwidth Reduction[J]. IEEE Trans. on Info. Theory， 1969，15(6):658-664.

[35]魏藜，宮學慶，錢衛寧，等. 高維空間中的離群點發現[J].軟件學報， 2002，13(2):280-290.

[36]Yang FengZhao， Zhu YangYong. IncLOF: An Incremental Algorithm for Mining Local Outliers in Dynamic Environment[J]. Computer Research and Development， 2004，41(3):477-484.

[37]Karjalainen L P， Somani M， C Porter. Regression and Solute Drag Models for the Activation Energy of Static Recrystallisation in Hotworked Steels[J]. Materials Science Forum， 2003，426432(2):1181-1188.

[38]Maneesh K Singh， Narendra Ahuja. Meanshift Segmentation with Waveletbased Bandwidth Selection[C]. Proceedings of the 6th IEEE Workshop on Applications of Computer Vision(WACV’02)， 2002.

[39]Beckman R J， Cook RD. Outliers[J]. Technometrics， 1983，25:119-163.

[40]Gentleman J F， Wilk MB. Detecting Outliers in a Twoway Table: Statistical Behavior of Residuals[J]. Technometrics， 1975，17:1-14.

[41]Marasinghe MG. A Multistage Procedure for Detecting Several Outliers in Linear Regression[J]. Technometrics， 1985，27:395-399.

[42]Paul S T， Fung K Y. A Generalized Extreme Studentized Residual Multipleoutlierdetection Procedure in Linear Regression[J].Technometrics， 1991，33:339-348.

[43]Li Ai Bing. Evaluation on Slope Stability Using Visual Quick Nerval Network[J]. Kuangye Yanjiu Yu Kaifa， 2001，21(5):8-11.

[44]Berchtold C， Bohm， H P Kriegel. Improving the Query Performance of Highdimensional Index Structures by Bulk Load Operations[C]. Proc.of EDBT， 1998.

[45]N Katayama， S Satoh. The SRtree: An Index Structure for Highdimensional Nearest Neighbor Queries[C]. Proc.of ACM SIGMOD Int. Conf. on Management of Data， 1997.369-380.

[46]范大昭，雷蓉，張永生.從地理數據庫中探測奇異值[J]. 測繪科學， 2004，29(5):12.

[47]S D Bay， M Schwabacher. Mining Distancebased Outliers in Near Linear Time with Randomization and a Simple Pruning Rule[C]. Washington， DC: SIGKDD’03， 2003.

[48]F Anguylli， C Pizzuti. Fast Outlier Detection in High Dimensional Spaces[C]. Proceedings of the 6th European Conference on the Principles of Data Mining and Knowledge Discovery， 2002.15-16.

[49]Lu C T， Chen D， Kou Y. Algorithms for Spatial Outlier Detection[C]. The 3rd IEEE International Conference on Data Mining(ICDM’03)， 2003.597-600.

[50]R Haining. Spatial Data Analysis in the Social and Environmental Sciences[M]. Cambridge University Press， 1993.

[51]J Haslett， R Brandley， P Craig， et al. Dynamic Graphics for Exploring Spatial Data with Application to Locating Global and Local Ano malies[J]. The American Statistician， 1991，45:234-242.

[52]A Luc. Exploratory Spatial Data Analysis and Geographic Information Systems[M]. M Painho. New Tools for Spatial Analysis， 1994.45-54.

[53]A Luc. Local Indicators of Spatial Association: LISA[J]. Geographi cal Analysis， 1995，27(2):93-115.

[54]Y Panatier， Variowin. Software for Spatial Data Analysis in 2D[M]. New York: Springer Verlag， 1996.

[55]S Shekhar， S Chawla. A Tour of Spatial Databases[M]. Prentice Hall， 2002.

[56]S Shekhar， C T Lu， P Zhang. Detecting Graphbased Spatial Outlier: Algorithms and Applications(A Summary of Results)[C]. Proc.of the 7th ACMSIGKDD Int’1 Conference on KDD Mining， 2001.

[57]S Shekhar， C T Lu， P Zhang. Detecting Graphbased Spatial Outlier[J]. Intelligent Data Analysis: An International Journal， 2002，6(5):451-468.

[58]王麗珍，何婧. 基于圖的空間例外檢測算法研究[J]. 云南大學學報，2003，25(5):398-400.

[59]Martin Ester， HansPeter Kriegel， Jrg Sander. Algorithms and Applications for Spatial Data Mining[C]. Geographic Data Mining and Knowledge Discovery， Research Monographs in GIS， Taylor and Francis， 2001.

[60]Zheng Binxiang， Du Xiuhua， Xi Yugeng. Outliers Mining in Time Series Data Sets[J]. Journal of Systems Engineering and Electronics， 2002，13(1):93-97.

[61]Zhang Tong， Zhang Xibin， Zhang Shiying. Testing for Outliers in Time Series Using Wavelets[J]. Journal of Systems Science and Complexity， 2003，16(4).

[62]Seng Chuan TAY， Wynne HSU， Kim Hwa LIM. Spatial Data Mi ning: Clustering of Hot Spots and Pattern Recognition[M]. Toulouse France: International Geoscience Remote Sensing Symposium， 2003.

[63]Vandana Janeja，Vijayalakshmi Atluri， Nabil R Adam.Outlaw: Using GeoSpatial Associations for Outlier Detection and Visual Analysis of Cargo Routes[C]. Proceedings of the 2nd National Conference on Digital Government， 2002.

[64]Stephen D Bay， Mark Schwabacher. Near Linear Time Detection of Distancebased Outliers and Applications to Security[C]. SIAM Data Mining Conference， Workshop on Data Mining for Counter Terrorism and Security， 2003.

[65]Shengyi Jiang， Qinghua Li， Kenli Li， et al. GLOF: A New Approach for Mining Local Outlier[C]. International Conference on Machine Learning and Cybernetics， 2003.157-162.

[66]Spiros Papadimitriou， Hiroyuki Kitagawa， et al. LOCI: Fast Outlier Detection Using the Local Correlation Integral[C]. The 19th International Conference on Data Engineering， 2003.315.

[67]Yang Fengzhao， Zhu Yangyong， Shi Baile. IncLOF: An Incremental Algorithm for Mining Local Outliers in Dynamic Environment[J]. Journal of Computer Research and Development， 2004，41(3):477-484

作者簡介：黃洪宇（1971-），男，福建泰寧人，碩士，主要研究方向為資源與環境信息工程、空間數據倉庫與空間數據挖掘等；林甲祥（19628-），男，福建安溪人，碩士研究生，主要研究方向為空間數據挖掘；陳崇成（1968-），男，福建閩清人，副教授，博士，主要研究方向為環境與資源信息工程、空間決策支持系統、自然資源與環境遙感、地理信息網絡共享技術、虛擬地理環境、空間數據倉庫與可視化挖掘等；樊明輝（1974-），男，湖北黃岡人，博士研究生，主要研究方向為環境與資源信息工程、空間決策支持系統、網絡地理信息系統、空間數據倉庫及數據挖掘、網格計算及應用等。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文