一種基于數(shù)學形態(tài)學的離群點檢測算法

1、碩士研究生學位論文題目 一種基于數(shù)學形態(tài)學的離群點檢測算法An Outlier Detection Algorithm Based on Mathematical Morphology摘要數(shù)據(jù)挖掘是在海量的數(shù)據(jù)中提取隱含的、未知的、潛在有用的知識或信息模式的決策支持方法。在信息爆炸的今天，數(shù)據(jù)挖掘顯得尤為重要。一個人的噪聲可能是另一個人的信號，忽視或降低離群點的存在性都將可能導致重要隱藏信息的丟失。在一些從數(shù)據(jù)庫中發(fā)現(xiàn)知識 (KDD)的應用實踐中，發(fā)掘特別的實例，不具備一般數(shù)據(jù)特性的數(shù)據(jù)對象或離群點比找出普通模式更加令人感興趣。因此，離群點本身可能是非常重要的，例如在欺詐探測中，離群點可能預示

2、著欺詐行為?？傊x群點檢測是數(shù)據(jù)挖掘領域一個重要的研究方向。本文在分析已有離群點算法的基礎上，提出了一種基于數(shù)學形態(tài)學的離群點檢測算法。該算法首次把數(shù)學形態(tài)學的理論引入到離群點檢測中，采用啟發(fā)式方法自動檢測離群點，無論是點狀、線狀，還是各種復雜的面狀(凸面形狀、非凸面形狀、環(huán)面形狀等)數(shù)據(jù)集，算法都能正確和精確地找出離群點，而對于非均勻密度數(shù)據(jù)集、多密度的數(shù)據(jù)集，算法也同樣地能找出離群點。算法考慮了離群點“局部”的概念。無論與怎樣的方式輸入感興趣的數(shù)據(jù)，對算法確定離群點都沒有任何影響。此外，由于使用的是啟發(fā)式的方法檢測，用戶只需要輸入感興趣的數(shù)據(jù)作為輸入，而無需輸入其它參數(shù)即能自動確定出離群

3、點。同時，該算法既適用于柵格系統(tǒng)又適用于矢量系統(tǒng)，且便于進行并行高速處理。算法循環(huán)地用半徑由小到大遞增變化的圓形結構元對數(shù)據(jù)庫中的各數(shù)據(jù)點作閉運算，具體地說是半徑由0開始，以增幅為1進行變化，這一過程中非鄰接點個數(shù)以不同速度逐漸減少，當半徑為0時所有的數(shù)據(jù)點都為非鄰接點，當半徑增大到一定程度時，非鄰接點個數(shù)為0。隨著結構元半徑的不斷增大，找出非鄰接點個數(shù)與半徑之間存在的關系，最終檢測出數(shù)據(jù)庫中存在的離群點。大量實驗和理論分析表明該算法是可行的和有效的，能從數(shù)據(jù)庫中正確并且精確無誤地找出離群點。關鍵詞：數(shù)據(jù)挖掘，離群點檢測，數(shù)學形態(tài)學，閉運算，非鄰接點ABSTRACTData mining is

4、 a decision support approach that extracts hidden, unknown, potentially useful knowledge and pattern from huge volume of data. Information is growing at exponential rates and data mining is particularly important in the information age or digital age. Outlier detection is important areas in data min

5、ing. Ones noise is maybe ones signal. For many KDD (Knowledge Discovery in Databases) applications, it is more interesting to find the exceptional instances or the outliers than to find the common pattern or knowledge. Therefore, outlier itself is perhaps very important. Outlier detection has import

6、ant applications in the fields of credit-card fraud detection, monitoring criminal actives in E-commerce, network robustness analysis, intrusion detection, and even the analysis of performance statistics of professional athletes. To sum up, outlier detection is a very significant subject in data min

7、ing.In this paper, based on the analysis of existing outlier detection algorithms, a new algorithm of outlier detection that is called ODMM (an Outlier Detection algorithm based on Mathematical Morphology) is presented, which combines mathematical morphology with outlier detection firstly, and it is

8、 automatically outlier detection by a heuristic method. ODMM could discover all outliers precisely and correctly no matter what the distributions of datasets are, including point-shaped datasets, line-shaped datasets and complicated, intricate, compound face-shaped datasets (convex-shaped datasets,

9、non-convex-shaped datasets, loop-shaped datasets, etc.). With regard to non-equal density datasets and multi-density datasets ODMM also could find outliers precisely and correctly. The notion of a “l(fā)ocal” outlier is considered in ODMM. Moreover, users just need to input the interested databases, and

10、 do not need to input any other parameters as the input of ODMM because outliers could be determined by a heuristic method. In the meanwhile, ODMM could be implemented in vector databases as well as in raster databases and the algorithm is convenient for parallel computing. The order of the algorith

11、m input has not an effect on ODMM.ODMM performs closing operation by using the circular structuring element increasing scale for all data points in databases. Specifically, the increasing scale means the radius of element increases by 1 once from 0. In this process, the count of non-adjacent data po

12、ints decrease with different velocities. All data points in the databases are non-adjacent when the radius is 0 and the count of non-adjacent data points is 0 when the radius is large enough. As the radius of structuring element is larger and larger we could find out the relationship between the cou

13、nt of non-adjacent data points and the radius. Finally, the outliers in databases could be detected according to the relationship.Both theoretical analysis and extensive experimental analysis confirm that ODMM is feasible and effective. The new algorithm could discover all outliers effectively, accu

14、rately and precisely in the databases.Key Words: Data Mining, Outlier Detection, Mathematical Morphology, Closing Operation, Non-adjacent Data Points目錄摘要IABSTRACTII第0章 引言10.1 研究目的和意義10.2 研究的內容和思路10.3 論文組織結構1第1章 相關技術31.1 數(shù)據(jù)挖掘概述31.1.1 數(shù)據(jù)挖掘概念31.1.2 數(shù)據(jù)挖掘的功能和方法31.1.3 數(shù)據(jù)挖掘的主要研究問題51.2 離群點檢測相關理論和算法61.2.2 基于

15、統(tǒng)計的離群點檢測81.2.3 基于距離的離群點檢測91.2.4 基于密度的離群點檢測181.2.5 基于偏離的離群點檢測和基于深度的離群點檢測251.3 本章小結26第2章 數(shù)學形態(tài)學圖像處理與分析272.1 數(shù)學形態(tài)學與圖像處理概述272.2 二值腐蝕和膨脹272.2.1 腐蝕272.2.2 膨脹322.3 二值開運算和閉運算362.3.1 開運算362.3.2 閉運算392.3.3 開閉運算的濾波性質402.4 像素區(qū)域412.5 閉運算的一個實例422.6 本章小結45第3章 基于數(shù)學形態(tài)學的離群點檢測算法(ODMM)473.1 實驗分析473.1.1 實驗1473.1.2 實驗2593

16、.1.3 實驗3663.2 分析實驗結果733.3 基于數(shù)學形態(tài)學的離群點檢測算法(ODMM)743.4 本章小結77第4章 ODMM算法分析794.1 ODMM算法的正確性794.2 ODMM算法的精度804.3 ODMM算法的執(zhí)行時間804.4 ODMM算法的局限性854.5 本章小結86第5章 總結及展望87附錄88參考文獻92攻讀碩士學位期間發(fā)表文章目錄95致謝96第0章 引言0.1 研究目的和意義 下面從兩個方面來考慮研究的目的和意義：(1) 離群點研究的意義：一個人的噪聲可能是另一個人的信號，因此忽視或降低離群點的存在性都將可能導致重要隱藏信息的丟失，離群點檢測問題是數(shù)據(jù)挖掘中的一

17、個重要任務。(2) 論文研究的目的和意義：論文首次將數(shù)學形態(tài)學的方法引入到離群點檢測中。論文所提出的算法能正確的、精確的、有效的檢測出離群點，具有現(xiàn)實意義，并可在矢量系統(tǒng)中實現(xiàn)，具有實用價值。用戶只需要輸入感興趣的數(shù)據(jù)作為輸入即能自動確定出離群點。同時，由于其本質上是并行的，便于并行高速處理，應用于未來的并行空間數(shù)據(jù)庫時更具有優(yōu)越性。0.2 研究的內容和思路1. 論文首先介紹了數(shù)據(jù)挖掘的理論框架，闡述了目前離群點檢測的相關理論、主要算法和優(yōu)化方法。2. 詳細介紹了與論文相關的數(shù)學形態(tài)學和圖像處理的基本理論和方法，并結合例子分析說明。3. 從數(shù)學形態(tài)學的數(shù)學理論基礎出發(fā)，在大量實驗的基礎上，根據(jù)

18、結構元由小到大而引起的變化規(guī)律，提出了基于數(shù)學形態(tài)學的離群點檢測算法(ODMM)，該算法運用啟發(fā)式方法可自動檢測出離群點。此外，還對比基于距離的離群點檢測方法闡述了該算法具有的優(yōu)勢。4. 最后通過結合算法分析和實驗結果證明其正確性、合理性、精確性、可行性、有效性和局限性。0.3 論文組織結構本文共分6章。除本章外，其余部分按以下方式組織：第1章 系統(tǒng)地研究了數(shù)據(jù)挖掘和離群點檢測的相關理論第2章 數(shù)學形態(tài)學圖像處理與分析第3章 從實驗中提出基于數(shù)學形態(tài)學的離群點檢測算法(ODMM)第4章 結合理論和實驗對ODMM算法進行分析第5章 總結并展望第1章 相關技術1.1 數(shù)據(jù)挖掘概述1.1.1 數(shù)據(jù)挖

19、掘概念數(shù)據(jù)挖掘(Data Mining，簡稱DM)，或稱從數(shù)據(jù)庫中發(fā)現(xiàn)知識(Knowledge Discovery in Databases，簡稱KDD)，定義為“從數(shù)據(jù)庫中發(fā)現(xiàn)隱含的、先前不知道的、潛在有用的信息”，或者“從大量數(shù)據(jù)中發(fā)現(xiàn)正確的、新穎的、潛在有用并能夠被理解的知識過程”1。KDD側重于目的和結果，DM側重于處理過程和方法，研究者們經(jīng)常把它們等同起來，或放在一起使用。DM和KDD的定義還有一些不同的表達形式，但其本質是一樣的，即從數(shù)據(jù)庫中提取隱含的、感興趣的、高水平的模式。隨著計算機信息處理技術的進步，數(shù)據(jù)和數(shù)據(jù)庫急劇膨脹，而數(shù)據(jù)庫中隱藏的豐富的知識遠遠沒有得到的充分的發(fā)掘和利

20、用，數(shù)據(jù)庫急劇增長與人們對數(shù)據(jù)庫處理和理解的困難之間形成了強烈的反差。DM和KDD技術就是在這種狀況下應運而生的，也是人工智能、機器學習技術發(fā)展的結果，其目的是為數(shù)據(jù)庫理解與應用提供自動化、智能化的手段。DM和KDD是多學科和多種技術交叉綜合的新領域，它綜合了機器學習、數(shù)據(jù)庫、專家系統(tǒng)、模式識別、統(tǒng)計、管理信息系統(tǒng)、基于知識的系統(tǒng)、可視化等領域的有關技術，因而數(shù)據(jù)挖掘與知識發(fā)現(xiàn)方法是豐富多彩的。研究者們從不同的角度研究KDD，提出了不同理論框架，例如證據(jù)理論(Evidence Theory)、Rough集理論(Rough Sets Theory)等。1.1.2 數(shù)據(jù)挖掘的功能和方法數(shù)據(jù)挖掘功能

21、用于指定數(shù)據(jù)挖掘任務中要找的數(shù)據(jù)類型。下面我們介紹數(shù)據(jù)挖掘的功能以及它們可以發(fā)現(xiàn)的模式類型：1. 特征化(Characterization)。從與學習任務相關的一組數(shù)據(jù)中提取出關于這些數(shù)據(jù)的特征式，這些特征式表達了該數(shù)據(jù)集的總體特征。它是目標類數(shù)據(jù)(學習數(shù)據(jù))的一般特征或特性的匯總。2. 區(qū)分(Discrimination)。通過對學習數(shù)據(jù)和對比數(shù)據(jù)的處理，提取出關于學習數(shù)據(jù)的主要特征，這些特征可以將學習數(shù)據(jù)與對比數(shù)據(jù)分開來。例如：通過對某種疾病與其他疾病的癥狀的比較，可以提取出該疾病相對于其他疾病的區(qū)分規(guī)則，利用這些規(guī)則就可以區(qū)分出這種疾病。3. 分類(Classification)。根據(jù)數(shù)

22、據(jù)的不同特征，將其劃歸為不同的類，這些類(導出模型)是事先利用訓練數(shù)據(jù)集(即其類標記已知的數(shù)據(jù)對象)建立起來的。例如：利用當前的病例數(shù)據(jù)可以建立各種疾病的分類規(guī)則。對于新的病人，根據(jù)其癥狀及分類規(guī)則，可以知道疾病的種類。4. 預測(Prediction)。通過對數(shù)據(jù)的分析處理，估計數(shù)據(jù)庫中某些丟失數(shù)據(jù)的可能值或一個數(shù)據(jù)集中某種屬性值的分布情況。一般是利用數(shù)學統(tǒng)計的方法，找出與所要預測的屬性相關的屬性并根據(jù)相似數(shù)據(jù)的分析估算屬性值的分布情況。例如：根據(jù)同一單位內其他職工的工資，可以預測某一職工的可能工資。5. 關聯(lián)規(guī)則(Association Rule)。是發(fā)現(xiàn)數(shù)據(jù)對象間的相互依賴關系，一個關聯(lián)

23、規(guī)則的形式為：，即“”的規(guī)則，其中，是屬性-值對。關聯(lián)規(guī)則解釋為“滿足中條件的數(shù)據(jù)庫元組多半也滿足中條件”。如果、出現(xiàn)，那么、一定出現(xiàn)，這表明數(shù)據(jù)、和數(shù)據(jù)、有著某種聯(lián)系。例如：在對疾病癥狀的研究過程中，人們也許會發(fā)現(xiàn)，某些癥狀的出現(xiàn)一定會伴隨其他一些癥狀的出現(xiàn)，通過對這種現(xiàn)象的深入研究，也許會找到攻克疾病的方法。7. 聚類(Clustering)。根據(jù)所處理的數(shù)據(jù)的一些屬性，對這批數(shù)據(jù)進行分類，這種分類是基于當前所處理的數(shù)據(jù)。與分類和預測不同，聚類分析數(shù)據(jù)對象，而不考慮已知的類標記。一般情況下，訓練數(shù)據(jù)中不提供類標記，因為不知道從何開始。聚類，可以用于產生這種標記。經(jīng)過聚類以后的數(shù)據(jù)，在各類之

24、間其相似程度很小，而在某一類內部，其數(shù)據(jù)的相似度則很大。聚類結束后，每類中的數(shù)據(jù)由唯一的標志進行標識，類中數(shù)據(jù)的共同特征也被提取出來用于對該類的特征描述。例如：可以通過對一組新型疾病的聚類，形成每類疾病的特征描述，這樣可以對這些疾病進行識別。8. 離群點挖掘(Outlier Mining)。數(shù)據(jù)庫中可能包含一些數(shù)據(jù)對象，它們與數(shù)據(jù)的一般行為或模型不一致，這些對象就是離群點。離群點數(shù)據(jù)分析稱為離群點挖掘。離群點可以使用統(tǒng)計實驗檢測。它假設一個數(shù)據(jù)分布或概率模型，并使用距離度量，到其他聚類的距離很大的對象被視為離群點?；谄畹姆椒ㄍㄟ^考慮一群對象主要特征上的差別識別離群點，而不是使用統(tǒng)計或距離度

25、量。例如：在醫(yī)療分析中，發(fā)現(xiàn)對多種治療方式的不尋常反映。上面我們介紹了數(shù)據(jù)挖掘的功能，下面我們介紹數(shù)據(jù)挖掘所使用的主要方法：1. 數(shù)學統(tǒng)計方法。使用這種方法一般是首先建立一個數(shù)學模型或統(tǒng)計學模型，然后根據(jù)這種模型提取出有關的知識。例如：可由訓練數(shù)據(jù)建立一個Bayesian網(wǎng)，然后，根據(jù)該網(wǎng)的一些參數(shù)及聯(lián)系權值提取出相關的知識。2. 機器學習方法。大多數(shù)機器學習方法是利用人類的認知模型模仿人類的學習方法從數(shù)據(jù)中提取知識，由于機器學習經(jīng)過多年的研究，已取得了一些較滿意的成果，因此在KDD中可以利用目前已經(jīng)比較成熟的機器學習方法。3. 面向數(shù)據(jù)庫方法。隨著數(shù)據(jù)庫技術的發(fā)展，其中的一些數(shù)據(jù)處理方法不斷

26、完善并趨于成熟。在KDD中，利用現(xiàn)有的一些啟發(fā)式方法，可以提取出數(shù)據(jù)庫中的一些特征知識。4. 混合方法。上述各種方法各有其優(yōu)缺點，為提高KDD的效率，可將各種方法有機地結合在一起，取長補短，以發(fā)現(xiàn)更有價值的知識。5. 其他方法。除了上述方法以外，還有其他一些方法，如數(shù)據(jù)可視化技術，知識表示技術等等。1.1.3 數(shù)據(jù)挖掘的主要研究問題數(shù)據(jù)挖掘的主要研究問題從以下幾個方面考慮：挖掘方法和用戶交互，性能問題及各種數(shù)據(jù)類型的多樣性問題。1. 挖掘方法和用戶交互問題方面(1) 在數(shù)據(jù)庫中挖掘不同類型的知識；(2) 多個抽象層的交互知識挖掘；(3) 結合背景知識；(4) 數(shù)據(jù)挖掘查詢語言和特定的數(shù)據(jù)挖掘；

27、(5) 數(shù)據(jù)挖掘結果的表示和顯示；(6) 處理噪聲和不完全數(shù)據(jù)；(7) 興趣度問題。2. 性能方面(1) 數(shù)據(jù)挖掘算法的有效性和可伸縮性；(2) 并行、分布式和增量挖掘算法。3.關于數(shù)據(jù)庫類型的多樣性問題(1) 關系的和復雜的數(shù)據(jù)類型的處理；(2) 由異種數(shù)據(jù)庫和全球信息系統(tǒng)挖掘信息。1.2 離群點檢測相關理論和算法“離群點是什么？”經(jīng)常存在一些數(shù)據(jù)對象，它們不符合數(shù)據(jù)的一般模型。這樣的數(shù)據(jù)對象被稱為離群點(outlier)，它們與數(shù)據(jù)的其他部分不同或不一致。到目前為止，離群點還沒有一個正式的，為人們普遍接收的定義。Hawkins的定義2揭示了離群點的本質：“離群點的表現(xiàn)與其它點如此不同，不禁

28、讓人懷疑它們是由另外一種完全不同的機制產生的?！彪x群點是不具備數(shù)據(jù)一般特性的數(shù)據(jù)對象。從回歸診斷的角度看，離群點是那些與既定模型有較大的偏離或者說與擬合模型比較不相容的點3，是那些遠離其它絕大多數(shù)觀測值的點，通常具有較大的殘差。離群點產生的原因可分為主觀原因和客觀原因。所謂主觀原因就是人們在收集和記錄的時候出現(xiàn)錯誤所造成的壞點，或者說是人為因素造成明顯的數(shù)據(jù)記錄不正確或由于沒有考慮到實際因素而導致了嚴重錯誤解釋。對這種情況下離群點的處理是無爭議的，一般沒有什么困難?？陀^原因從統(tǒng)計的因素看由兩類機制造成，即重尾分布(heavy-tailed distribution)和混合分布(mixture

29、distribution)，這兩類機制影響了離群點的發(fā)生及人們在發(fā)現(xiàn)之后的處理方法。離群點可能是度量或執(zhí)行錯誤所導致的。例如：一個人的年齡為-999可能是程序對未記錄的年齡的缺省設置所產生的。另外，離群點也可能是固有的數(shù)據(jù)變異的結果。例如，一個公司的首席執(zhí)行官的工資自然遠遠高于公司的其他雇員的工資，成為一個離群點。KDD中多數(shù)聚類算法，例如：CLARANS4，DBSCAN5，BIRCH6，STING7，WaverCluster8，DenClue9，CLIQUE10，Chameleon，SNN(Shared Nearest Neighbor)11，K-MEANS，CURE，F(xiàn)CM(Fuzzy C

30、-means)，brFCM12，P(clustering based on closed paris)13，多階段等密度線算法14等，都能夠發(fā)現(xiàn)一些離群點情況，但是，因為聚類算法的主要目標是發(fā)現(xiàn)簇，而不是發(fā)現(xiàn)離群點，聚類算法或者對這些離群點情況不敏感，或者忽視這些離群點情況。事實上，許多數(shù)據(jù)挖掘算法試圖使離群點的影響最小化，或者排出它們。但是，我們必須意識到：一個人的噪聲可能是另一個人的信號，因此離群點檢測是數(shù)據(jù)挖掘領域一個重要的研究方向，忽視或降低離群點的存在性都將可能導致重要的隱藏信息的丟失。在一些KDD的應用實踐中，發(fā)掘特別的實例，不具備一般數(shù)據(jù)特性的數(shù)據(jù)對象或離群點比找出普通模式更加令

31、人感興趣。因此，離群點本身可能是非常重要的，例如在欺詐探測中，離群點可能預示著欺詐行為。這樣，離群點探測和分析是一個重要的數(shù)據(jù)挖掘任務，被稱為離群點挖掘。離群點挖掘有著廣泛的應用。像上面提到的，它能用于欺詐監(jiān)測，例如探測不尋常的信用卡使用或電信服務。此外，它在市場分析或偵探電子商務犯罪中可用于確定極低或極高收入的客戶的消費行為，或者在醫(yī)療分析中發(fā)現(xiàn)對多種治療方式的不尋常反映。因此，離群點檢測用于發(fā)現(xiàn)不具備數(shù)據(jù)一般特性的數(shù)據(jù)對象。它可應用到許多領域，如網(wǎng)絡入侵檢測、電信和信用卡欺騙、氣象預報、客戶分類等。在電子商務和金融服務領域中的欺詐等犯罪行為監(jiān)測，有關離群點情況的信息比常規(guī)模式更有價值。離群

32、點挖掘可以描述如下：給定一個n個數(shù)據(jù)點或對象的集合，及預期的離群點的數(shù)目k，發(fā)現(xiàn)與剩余的數(shù)據(jù)相比是顯著相異的、異?；虿灰恢碌念^k個對象。離群點挖掘問題可以被看作兩個子問題：(1) 在給定的數(shù)據(jù)集合中定義什么樣的數(shù)據(jù)可以被認為是不一致的；(2) 找到一個有效的方法來挖掘這樣的離群點。我們討論基于計算機的離群點檢測方法。這些方法可分為五類：統(tǒng)計學方法15，基于距離的方法，基于密度的方法，基于偏離的方法15,16和基于深度的方法。注意，當聚類算法將離群點作為噪聲剔除時，這些算法可以被修改，包括離群點檢測作為執(zhí)行的副產品。1.2.2 基于統(tǒng)計的離群點檢測基于統(tǒng)計的方法15即基于分布的方法，數(shù)據(jù)集合假設

33、一個分布或概率模型(例如一個正態(tài)分布)，即數(shù)據(jù)集滿足的分布是已知的，然后根據(jù)模型對數(shù)據(jù)集中每一個點采用不一致性檢測(discordancy test)來確定離群點。如果與分布或概率模型不符合，就認為它是一個離群點?，F(xiàn)有的不一致性測試方法有100多種17。該檢測要求知道數(shù)據(jù)集參數(shù)(例如假設的數(shù)據(jù)分布)、分布參數(shù)(例如平均值和方差)和預期的離群點的數(shù)目?；诜植嫉姆椒ù嬖诘娜秉c：(1) 大部分只能對單變量分布進行測試；(2) 盡管有些方法可以對多變量分布進行測試，也并沒有使情況好轉，因為對大多數(shù)KDD應用來說，數(shù)據(jù)集的多變量分布是無法預知的；(3) 對每個點進行測試代價太大，而且有時并不能獲得令人

34、滿意的結果。一個統(tǒng)計學的不一致性檢驗檢查兩個假設：一個工作假設(working hypothesis)和一個替代假設(alternative hypothesis)。一個工作假設是一個命題：個對象的整個數(shù)據(jù)集合來自一個初始的分布模型，即如果沒有統(tǒng)計上的顯著證據(jù)支持拒絕這個假設，它就被保留。不一致性檢驗驗證一個對象關于分布是否顯著地大(或者小)。依據(jù)可用的關于數(shù)據(jù)的知識，不同的統(tǒng)計量被提出來用作不一致性檢驗。假設某個統(tǒng)計量被選擇用于不一致性檢驗，對象的該統(tǒng)計量的值為，則構建分布，估算顯著性概率。如果是足夠的小，那么是不一致的，工作假設被拒絕。替代假設被采用，它聲明來自于另一個分布模型。既然可能在

35、一個模型下是離群點，在另一個模型下世非常有效的值，那么結果非常依賴于模型的選擇。替代分布在決定檢驗的能力(即當真的是離群點時工作假設被拒絕的概率)上是非常重要的。有許多不同的替代分布：(1) 固有的替代分布(inherent alternative distribution)：在這種情況下，所有對象來自分布的工作假設被拒絕，而所有對象來自另一個分布的替代假設被接受：和可能是不同的分布，或者是參數(shù)不同的統(tǒng)一分布。對分布的形式存在約束以便它有產生離群點的可能性。例如，它可能有不同的平均值或者離差，或者更長的尾部。(2) 混合替代分布(mixture alternative distribution

36、)：混合替代分布認為不一致性的值不是分布中的離群點，而是來自其他分布的污染物。在這種情況下，替代假設是：(3) 滑動替代分布(slippage alternative distribution)：這個替代分布聲明所有的對象(除了少量外)根據(jù)給定的參數(shù)獨立地來自初始的模型，而剩余的對象是來自修改過的的獨立的觀察，這個的參數(shù)已經(jīng)變化了。基于統(tǒng)計的離群點檢測主要存在的缺點是：(1) 絕大多數(shù)檢驗時針對單個屬性的，而許多數(shù)據(jù)挖掘問題要求在多維空間中發(fā)現(xiàn)離群點。(2) 在許多情況下數(shù)據(jù)分布是未知的。1.2.3 基于距離的離群點檢測基于距離的方法18中，如果一個點與數(shù)據(jù)集中大多數(shù)點之間的距離都大于某個閾值

37、，就是一個離群點。換句話說，不依賴于統(tǒng)計檢測，我們可以將基于距離的孤立點看作是那些沒有“足夠多”鄰居的對象。這一定義包含并擴展了基于分布的思想，當數(shù)據(jù)集不滿足任何標準分布時，基于距離的方法仍能有效的發(fā)祥離群點，而且該方法能夠處理任何維的數(shù)據(jù)。當空間維數(shù)比較高時，算法的效率比基于密度的方法高?；诰嚯x的離群點的概念是由Knorr和Ng提出的19,20?；诰嚯x的離群點檢測存在的缺點：尋找參數(shù)和的合適設置可能涉及多次試探和錯誤。定義1.1 離群點 如果數(shù)據(jù)集合中對象至少有部分與對象的距離大于，或者說數(shù)據(jù)集合中至少有的對象位于距對象有的范圍之外，則對象是一個帶參數(shù)和的基于距離的離群點，即。如圖1.1

38、所示。對進行形式化描述：集合的基數(shù)小于等于的。定義1.2 Hawkins離群點 表示對象，間的距離，用表示和簇的最小距離，即：。圖1.1 離群點部分不依賴于統(tǒng)計檢驗，我們可以將基于距離的離群點看作是那些沒有“足夠多”鄰居的對象，這里的鄰居是基于距給定對象的距離來定義的。與基于統(tǒng)計的方法相比，基于距離的離群點檢測拓廣了多個標準分布不一致性檢驗的思想。 目前已經(jīng)開發(fā)了若干個高效的基于距離的離群點檢測算法，概述如下：(1) 基于索引的算法：給定一個數(shù)據(jù)集合，基于索引的算法采用多維索引結構(例如R樹或k-d樹)，來查找每個對象在半徑d范圍內的鄰居。設是一個離群點的d-領域中可能存在的對象的最大數(shù)目。因

39、此，一旦對象的個鄰居被發(fā)現(xiàn)，就不是離群點。這個算法在最壞情況下的復雜度為，這里是維數(shù)，是數(shù)據(jù)集合中對象的數(shù)目。當增加時，基于索引的算法具有良好的擴展性。(2) 嵌套-循環(huán)算法(NL算法)：嵌套-循環(huán)算法和基于索引的算法有相同的計算復雜度，但它避免了索引結構的構建，試圖最小化I/O的次數(shù)。它把內存的緩沖空間分為兩半，把數(shù)據(jù)集合分為若干個邏輯塊。通過精心選擇邏輯塊裝入每個緩沖區(qū)的順序，I/O效率能夠改善。為了避免建立索引的花費，NL算法使用了一種基于塊和循環(huán)的設計。假設有一個b%數(shù)據(jù)集大小的緩存，算法就將緩存劃分為相等兩個部分，稱為第一和第二數(shù)組。它把數(shù)據(jù)集讀入數(shù)組，直接計算每個實體對的距離。對于

40、每個在第一個數(shù)組內的實體，它的d鄰域被記錄下來，當實體的d鄰域中點的個數(shù)超過M時，則證明該點不是離群點，這時停止計數(shù)，跳出現(xiàn)在的循環(huán)，比較下一個點。假設NL算法有50%的緩存，并用A，B，C，D來代表4個邏輯塊，每個塊記錄了數(shù)據(jù)集1/4的實體。以下面的順序來填充每個數(shù)組，并比較：1. A和A，然后和B，C，D總共有四個塊被讀；2. D和D(不需要讀)，然后和A(不用讀)，B，C有兩塊被讀；3. C和C(不需要讀)，然后和D(不用讀)，A，B總共有兩塊被讀；4. B和B(不需要讀)，然后和C(不用讀)，A，D總共有兩塊被讀。共有十塊被讀，相當于10/4次掃描數(shù)據(jù)集。和索引算法相比，NL算法避免了

41、建立索引結構的花費。很容易看出它的復雜度是，k是數(shù)據(jù)維數(shù)(或屬性個數(shù))。與不考慮I/O效率的一個實體對一個實體的強制算法相比，NL算法有優(yōu)勢，因為它減少了讀的次數(shù)。(3) 基于單元(cell-based)的算法：為了避免的計算復雜度，為駐留內存的數(shù)據(jù)集合開發(fā)了基于單元的算法。它的復雜度是，這里是依賴于單元數(shù)目的常數(shù)，是維數(shù)。在該方法中，數(shù)據(jù)空間被劃分為邊長等于的單元。每個單元有兩個層圍繞著它。第一層的厚度是一個單元，而第二個層的厚度是，如圖1.2所示。該算法逐個單元地對離群點計數(shù)，而不是逐個對象的計數(shù)。對一個給定的單元，它累計三個計數(shù)單元中對象的數(shù)目，單元和第一層中對象的數(shù)目，及單元和兩個層次

42、中的對象數(shù)目。我們把這些計數(shù)分別稱為，。離群點的確定：設是一個離群點的d-領域中可能存在的對象的最大數(shù)目；是單元的總數(shù)；表示橫坐標與縱坐標交匯的單元；是與直接鄰接的所有單元；有一個單元厚，有兩個單元厚；一個單元的單元數(shù)為8，單元數(shù)為40。在當前單元中的一個對象被認為是離群點，僅當小于或等于。如果這個條件不成立。那么該單元中所有的對象可以從進一步的考察中移走，因為它們不可能是離群點。如果小于或等于，那么單元中所有的對象被認為是離群點。否則，如果這個計數(shù)大于，那么單元中的某些對象有可能是離群點。為了檢測這些離群點，逐個對象加以處理。對單元中的每個對象，的第二層的對象被檢查。對單元中的對象，只有那些

43、d-領域內有不超過個點的對象是離群點。一個對象的d-領域由這個對象的單元、它的第一層的全部和它的第二層的部分組成。圖1.2 基于單元算法的數(shù)據(jù)空間算法：1. For q=1, 2, , m, 2. For 每個對象P，把P映射到相應的單元 and 3. For q=1, 2, , m, if then 標為紅色4. For 每個紅色單元，if 的單元中沒有被標為紅色的 then 把的單元全標為粉色。5. For 每個非空且無標色的單元，do(a) 計算 /單元和第一層中對象的數(shù)目(b) If ，把整個單元標為粉色。(c) else ()(1) 計算 /單元和兩個層次中的對象的數(shù)目(2) If

44、，then 單元中所有對象被認為是離群點(3) else () For 單個對象，do /對中每個對象P逐/一考察，若除P外的，則P為一離群點(a) (b) For 層的每個對象Q，do If then (1) (2) If ，P不是一個離群點 goto 5(c)(3)(c) 當層的所有對象掃描完一遍后，若，則P為一離群點基于單元的算法對空間劃分時，生成的單元數(shù)與維數(shù)呈指數(shù)增長，大量的單元數(shù)極大地降低了算法的效率。而實際上，劃分后會生成較多無數(shù)據(jù)點落入的空單元。如果算法只存儲非空單元，則單元間的位置關系將被破壞，使基于單元的算法需要執(zhí)行的近鄰查詢，每次都要遍歷一次所有的單元，算法效率難以保證。

45、為了實現(xiàn)近鄰查詢，又由于其查詢范圍為一個超立方體的區(qū)域(不能采用傳統(tǒng)的多維索引結構，如R*-tree21、SR-tree22、X-tree23等來存儲非空單元)，而不是傳統(tǒng)索引結構上可查詢的球形區(qū)域，因此，提出一種索引結構CD-Tree(cell dimension tree)24，只存儲了非空單元，同時保持單元間的鄰居關系，使近鄰查詢易于實現(xiàn)?；趩卧乃惴ú榻o出如何確定劃分粒度的方法。如果采用粗粒度劃分，不能體現(xiàn)出算法的優(yōu)勢；如果采用細粒度劃分，生成的單元數(shù)較多，使得算法的性能下降。提出一種基于劃分的數(shù)據(jù)偏斜度(skew of data，簡稱SOD)24概念，以此來指導劃分。假設是有界、

46、全部有序域的集合，是一個維數(shù)據(jù)空間，其中表示的個維或個屬性域。表示上的個點的集合，其中，表示一個數(shù)據(jù)點，為數(shù)據(jù)點的第維的值。定義1.3 數(shù)據(jù)集的劃分 將數(shù)據(jù)集所分布空間的每個維劃分為相等的間隔段，生成不相交超矩形單元的集合，它覆蓋整個數(shù)據(jù)集所分布的空間。每個單元的空間位置表示為，其中對應的間隔序號，間隔號從1到間隔段總數(shù)，稱為數(shù)據(jù)集的一個劃分。根據(jù)定義1.3可知，單元的總數(shù)，其中為第維的間隔段數(shù)量。CD-Tree24的結構數(shù)據(jù)集劃分后生成了單元的集合，只把非空單元存入CD-Tree中。CD-Tree的定義如下。定義1.4 CD-Tree 數(shù)據(jù)集在劃分下生成的CD-Tree結構如下：1. 它有一

47、個根結點，共有k+1層，其中k是數(shù)據(jù)集的維數(shù)。2. 數(shù)據(jù)集的一維對應于CD-Tree的一層，第k+1層對應所有非空的單元。3. 除了第k+1層，第i層(非葉結點層)中的結點包括形如(cNO,Pointer)的內部結點，其中cNO是一個關鍵字，也是一個單元在第i維上的間隔號；Pointer是一個指針，在第k層，它指向一個葉結點。在其他層的內部結構點中，它指向下一層結點，該結點包含與本單元對應下一維的所有相異非空單元的序號。4. 從根結點到葉結點的一條路徑對應一個單元。 圖1.3 一棵CD-Tree的實例圖1.3(a)是一個劃分下的單元結構，共有兩維，每維等分成6個間隔段，編號為1至6?；疑膯卧?/p>

48、表示非空的單元。例如Cell(2,3)表示兩維的編號分別為2和3的單元。圖1.3(b)表示了與這個單元結構相對應的CD-Tree結構。這個CD-Tree共有3層，前兩層分別對應數(shù)據(jù)的兩個維，最后一層為葉結點層，對應所有單元。第1維有6個間隔段，但只有2，3，5和6包含數(shù)據(jù)對象，這樣，根結點有4個內部結點。根結點的第1個內部結點2指向第2層結點有兩個間隔號2和3，說明在第2維上與第1維的間隔號2相對應有兩個單元非空，分別為(2,2)和(2,3)。從根結點到葉結點的一條路徑為一個單元。在葉結點上要存儲這個單元上的一些信息，如落入該單元的數(shù)據(jù)點數(shù)等。CD-Tree的構建過程是，計算數(shù)據(jù)對象落入單元的

49、坐標值，然后在相應的層次的結點中，以關鍵字按升序插入結點。數(shù)據(jù)偏斜度(SOD)24由于劃分后非空單元數(shù)量與數(shù)據(jù)偏斜程度有關，因此我們試圖找出一種度量來估計劃分后的非空單元數(shù)，進而指導劃分。傳統(tǒng)的衡量數(shù)據(jù)偏斜的度量，如方差，不能用來估計非空單元數(shù)。在圖1.4(a)中，方差小的數(shù)據(jù)集劃分后生成的非空單元數(shù)較少；在圖1.4(b)中，方差大的數(shù)據(jù)集劃分后生成的非空單元數(shù)也較少；在圖1.4(c)中，方差大小介于兩者之間的數(shù)據(jù)集，劃分后生成的非空單元數(shù)最多。這是因為劃分后生成的非空單元的所占的比例表示數(shù)據(jù)填充數(shù)據(jù)空的程度，而方差衡量的是數(shù)據(jù)與其平均值相對應的偏斜度，與劃分無關。(a)(b)(c)圖1.4

50、不同劃分下的偏斜度用于衡量數(shù)據(jù)空間劃分后無數(shù)據(jù)點落入空單元所占比例，進而指導對數(shù)據(jù)的劃分及優(yōu)化CD-Tree結構。定義1.5 數(shù)據(jù)集在劃分下的偏斜度 數(shù)據(jù)集在劃分下的偏斜度定義為其中，為數(shù)據(jù)點，為第個單元的數(shù)據(jù)點數(shù)，為單元個數(shù)，是分布在單元格中的平均數(shù)據(jù)點數(shù)。表示空間數(shù)據(jù)填滿的程度，有如下性質：性質1.1 偏斜度表示數(shù)據(jù)集在劃分下的偏斜度。當時，無偏斜；越接近于1，其偏斜程度越大。定理1.1 一個數(shù)據(jù)集在下的偏斜度等于，其中為數(shù)據(jù)點數(shù)大于平均數(shù)據(jù)點數(shù)的單元的數(shù)據(jù)點數(shù)。定理1.1說明，當計算偏斜度時，不必訪問所有單元，只需訪問數(shù)據(jù)點數(shù)大于平均點數(shù)的單元，這樣簡化了偏斜度的計算。定義1.5 子劃分

51、(sub-partition) 給定數(shù)據(jù)集的兩個劃分和，如果，使得，即對于所有維上的間隔段，在中均存在間隔段滿足，則稱為的子劃分，表示為。定理1.2 給定數(shù)據(jù)集的兩個劃分、，若，則。定理1.3 給定數(shù)據(jù)集的一個劃分，當時，等于劃分下空單元數(shù)占單元總數(shù)的比例。其中，為數(shù)據(jù)對象個數(shù)，為單元總數(shù)。由定理1.3可知，利用偏斜度估計的空單元數(shù)與實際空單元數(shù)的誤差為，當時，誤差為0.1.2.4 基于密度的離群點檢測基于密度的離群點的定義是在距離的基礎上建立起來的?；诿芏鹊碾x群點檢測方法，將點之間的距離和某一給定范圍內點的個數(shù)這兩個參數(shù)結合起來，得到“密度”的概念，根據(jù)密度來判斷一個點是否是離群點。非局部

52、孤立點探測方法存在的局限性：基于距離的離群點屬“全局”孤立點。然而，現(xiàn)實中存在更復雜的數(shù)據(jù)集結構，存在其他類型的離群點。存在這樣的對象，從鄰居的密度看，它相對于其局部鄰居是孤立的。我們把這些孤立點稱為“局部”離群點。下面將通過一個例子說明在一定條件下使用全局離群點的觀點是充分的和有意義的，但在通常情況下，即簇以不同的密度存在時，非局部孤立點探測方法是有局限性的。圖1.5 二維數(shù)據(jù)集DS1考慮圖1.5給出的例子，簇中有400個對象，簇中有100個對象，還另有兩個對象和，該二維數(shù)據(jù)集共包含502個對象。比更密集。根據(jù)我們剛剛對“局部”離群點的定義，我們希望把和標識為離群點。而根據(jù)Hawkins的定

53、義，在基于距離的離群點框架下，發(fā)生以下情況時，作為是合理的。假如中的每個對象與它最近鄰居的距離大于與間的距離(即：)， 那么作為是合理的，因為可以找出合適的和。而事實上我們不能找出合適的和讓是孤立點而中的對象不是。原因如下：(1) 若，則剩下501個對象與的距離大于，滿足孤立點的條件，但根據(jù)前面的假設，中的每個對象也滿足孤立點的條件。所以，當時，和中的所有對象都是孤立點。(2) 若，容易看出是一個孤立點，但同時中的部分對象也是孤立點，因為集合的基數(shù)總是大于的基數(shù)。因此，當時，若時孤立點則中的部分對象也是孤立點。更糟的是，存在這樣的和能使不是一個孤立點而中的部分是。其他方法對離群點的定義都是二值

54、的(具有0、1屬性)，即：要么是孤立點，要么不是孤立點，不存在中間狀態(tài)，而局部孤立點因子25(LOF)26定義了點的離群程度，它為每個對象設計局部孤立點因子，以此來度量該對象成為離群點的可能性，或者說成為孤立點的度。LOF是局部的而不是全局的，因為離群點的度依賴的是對象與其周圍鄰居的分離程度，而不是相對于剩余的所有對象而言。同時，一個點的離群程度與它周圍的點有關則體現(xiàn)了“局部”的概念。下面詳細介紹局部孤立點因子(LOF)是如何定義的以及其相關性質。定義1.6 對象的距離 任意正整數(shù)，對象的距離()指的是滿足以下條件的，： (1) 至少有個對象使得 (2) 至多有個對象使得 即是與第近的對象到的

55、距離。以上定義需要注意的是，對象可能不是唯一的。定義1.7 對象的距離鄰居 已知的距離，的距離鄰居包含與距離小于等于的所有對象，即。這些對象被稱為的個最近鄰居。在不會發(fā)生混淆時，我們用表示，對于定義3，當對象不唯一時，即與第近的對象有多個時，的基數(shù)大于。舉個例子，假設有1個對象距有1個單位的距離，有2個對象距有2個單位距離，有3個對象距有3個單位的距離，那么等于，為3，因此是6，大于4。如圖1.6所示。圖1.6對象的距離鄰居定義1.8 對象關于對象的可達距離 令為一自然數(shù)，對象關于對象的可達距離定義如下：直觀的看，若對象遠離，則二者間的可達距離就是二者間的實際距離。然而，假如二者足夠靠近的話，

56、二者間的可達距離會是。的值越高，相同領域內對象的可達距離越相近，因此，實際上通過改變值可以起到平滑的效果。在典型的基于密度的聚類算法中存在兩個定義了密度的參數(shù)：(1)一個指定了對象最小數(shù)目的參數(shù)MinPts，和(2)一個指定了具體量的參數(shù)。這兩個參數(shù)決定了聚類算法的密度閾值。即是不同的對象或領域可連接起來，假如它們鄰居的密度超過給出密度閾值。為了挖掘基于密度的孤立點，需要對比不同對象集的密度，這意味著我們必須動態(tài)地確定出對象集的密度。因此，我們只保留下參數(shù)MinPts。對于，計算來測量對象的領域密度的大小。定義1.9 對象的局部可達密度(Local Reachability Density) 對象的局部可達密度定義如下：直觀地看，對象的局部可達密度是的MinPts個最近鄰居的平均可達距離的倒數(shù)。注意到假如所有可達距離的總和為0，也就是和的MinPts個鄰居處在同一坐標位置上，即對點重合在一起，則lrd為無窮。為了簡化，我們把多個具有相同坐標的對象僅視為一個對象定義1.10 對象的(局部)孤立點因子(Local) Outlier Factor) 對象的(局部)孤立點因子定義如下：的孤立點因子緊緊抓住了成為一個孤立點中對度的定義。它是的局部可達密度與的MinPts個最近鄰居的局部可達密度比值的平均。容易看出，的局部可達密度越低，同時