什么是離群點

??離群點是一個數(shù)據(jù)對象，它顯著不同于其他數(shù)據(jù)對象，好像它是被不同的機制產(chǎn)生的一樣。有時也稱非離群點為“正常數(shù)據(jù)”，離群點為“異常數(shù)據(jù)”。
??離群點不同于噪聲數(shù)據(jù)。噪聲是被觀測變量的隨機誤差或方差。一般而言，噪聲在數(shù)據(jù)分析（包括離群點分析）中不是令人感興趣的。如在信用卡欺詐檢測，顧客的購買行為可以用一個隨機變量建模。一位顧客可能會產(chǎn)生某些看上去像“隨機誤差”或“方差”的噪聲交易，如買一份較豐盛的午餐，或比通常多要了一杯咖啡。這種交易不應該視為離群點，否則信用卡公司將因驗證太多的交易而付出沉重代價。因此，與許多其他數(shù)據(jù)分析和數(shù)據(jù)挖掘任務一樣，應該在離群點檢測前就刪除噪聲。
??離群點檢測是有趣的，因為懷疑產(chǎn)生它們的機制不同于產(chǎn)生其他數(shù)據(jù)的機制。因此，在離群點檢測時，重要的是搞清楚為什么檢測到的離群點被某種其他機制產(chǎn)生。通常，在其余數(shù)據(jù)上做各種假設，并且證明檢測到的離群點顯著違反了這些假設。

離群點的類型

離群點可以分成三類：全局離群點、情境（或條件）離群點和集體離群點。

2.1 全局離群點

在給定的數(shù)據(jù)集中，一個數(shù)據(jù)對象是全局離群點，如果它顯著的偏離數(shù)據(jù)集中的其他對象。全局離群點是最簡單的一類離群點，大部分的離群點檢測方法都旨在找出全局離群點。

2.2 情境離群點

在給定的數(shù)據(jù)集中，一個數(shù)據(jù)對象是情境離群點，如果關于對象的特定情境，它顯著的偏離其他對象。情境離群點又稱為條件離群點，因為它們條件的依賴于選定的情境。一般地，在情境離群點檢測中，所考慮數(shù)據(jù)對象的屬性劃分成兩組：
情境屬性：數(shù)據(jù)對象的情境屬性定義對象的情境。一般為靜態(tài)屬性變量，如信用卡欺詐檢測中，不同年齡、不同地區(qū)的人消費情況是不同的，先按照靜態(tài)屬性將人群大致分類，再檢測每一類的離群點，會得到更好的結果。
行為屬性：定義對象的特征，并用來評估對象關于它所處的情境是否為離群點。在上述例子中，行為屬性可以是消費金額，消費頻率等
情境離群點分析為用戶提供了靈活性，因為用戶可以在不同情境下考察離群點，這在許多應用中都是非常期望的。

2.3 集體離群點

給定一個數(shù)據(jù)集，數(shù)據(jù)對象的一個子集形成集體離群點，如果這些對象作為整體顯著的偏離整個數(shù)據(jù)集。如一家供應鏈公司，每天處理數(shù)以千計的訂單和出貨。如果一個訂單的出貨延誤，則可能不是離群點，因為統(tǒng)計表明延誤時常發(fā)生。然而，如果有一天有100個訂單延誤，則必須注意。這100個訂單整體來看，形成一個離群點，盡管如果單個考慮，它們每個或許都不是離群點。你可能需要更詳細地整個考察這些訂單，搞清楚出貨問題。
與全局和情境離群點檢測不同，在集體離群點檢測中，不僅必須考慮個體對象的行為，而且還要考慮對象組群的行為。因此，為了檢測集體離群點，需要關于對象之間聯(lián)系的背景知識，如對象之間的距離或相似性測量方法。

離群點檢測方法

3.1 統(tǒng)計學方法

離群點檢測的統(tǒng)計學方法對數(shù)據(jù)的正常性做假定。假定數(shù)據(jù)集中的正常對象由一個隨機過程（生成模型）產(chǎn)生。因此，正常對象出現(xiàn)在該隨機模型的高概率區(qū)域中，而低概率區(qū)域中的對象是離群點。
離群點檢測的統(tǒng)計學方法的一般思想是：學習一個擬合給定數(shù)據(jù)集的生成模型，然后識別該模型低概率區(qū)域中的對象，把它們作為離群點。有許多不同方法來學習生成模型，一般而言，根據(jù)如何指定和如何學習模型，離群點檢測的統(tǒng)計學方法可以劃分成兩個主要類型：參數(shù)方法和非參數(shù)方法。
參數(shù)方法: 假定正常的數(shù)據(jù)對象被一個以為參數(shù)的參數(shù)分布產(chǎn)生。該參數(shù)分布的概率密度函數(shù)給出對象被該分布產(chǎn)生的概率。該值越小，越可能是離群點。
非參數(shù)方法: 并不假定先驗統(tǒng)計模型，而是試圖從輸入數(shù)據(jù)確定模型。非參數(shù)方法的例子包括直方圖和核密度估計。

3.1.1 參數(shù)方法

1、基于正態(tài)分布的一元離群點檢測

??假定數(shù)據(jù)集由一個正態(tài)分布產(chǎn)生，然后，可以由輸入數(shù)據(jù)學習正態(tài)分布的參數(shù)，并把低概率的點識別為離群點。
??在正態(tài)分布的假定下，區(qū)域包含99.7%的數(shù)據(jù)，包含95.4%的數(shù)據(jù)，包含68.3%的數(shù)據(jù)。視具體情況而定，將其區(qū)域外的數(shù)據(jù)視為離群點。
??這種直截了當?shù)慕y(tǒng)計學離群點檢測方法也可以用于可視化。例如盒圖方法使用五數(shù)概況繪制一元輸入數(shù)據(jù)：最小的非離群點值（Min）、第一個四分位數(shù)（Q1）、中位數(shù)（Q2）、第三個四分位數(shù)（Q3）和最大的非離群點值（Max）。
??四分位數(shù)極差（IQR）定義為Q3-Q1。比Q1小1.5倍的IQR或者比Q3大1.5倍的IQR的任何對象都視為離群點，因為Q1-1.5IQR和Q3+1.5IQR之間的區(qū)域包含了99.3%的對象。

2、多元離群點檢測

（1）使用馬哈拉諾比斯距離檢測多元離群點。
對于一個多元數(shù)據(jù)集，設為均值向量。對于數(shù)據(jù)集中的對象，從到的馬哈拉諾比斯（Mahalanobis）距離為其中S是協(xié)方差矩陣。是一元數(shù)據(jù)，可以對它進行離群點檢測。如果被確定為離群點，則也被視為離群點。
（2）使用統(tǒng)計量的多元離群點檢測。
在正態(tài)分布的假設下，統(tǒng)計量可以用來捕獲多元離群點。對于對象，統(tǒng)計量是
其中，是在第維上的值，是所有對象在第維上的均值，而是維度。如果對象的統(tǒng)計量很大，則該對象是離群點。
（3）使用混合參數(shù)分布
在許多情況下，數(shù)據(jù)是由正態(tài)分布產(chǎn)生的假定很有效。然而，當實際數(shù)據(jù)很復雜時，這種假定過于簡單。在這種情況下，假定數(shù)據(jù)是被混合參數(shù)分布產(chǎn)生的。
混合參數(shù)分布中用期望最大化（EM）算法來估計參數(shù)。具體情況比較復雜，可以參考韓家煒的《數(shù)據(jù)挖掘：概念與技術》一書。

3.1.2 非參數(shù)方法

在離群點檢測的非參數(shù)方法中，“正常數(shù)據(jù)”的模型從輸入數(shù)據(jù)學習，而不是假定一個先驗。通常，非參數(shù)方法對數(shù)據(jù)做較少假定，因而在更多情況下都可以使用。

使用直方圖檢測離群點
包括如下兩步：
步驟1：構造直方圖。盡管非參數(shù)方法并不假定任何先驗統(tǒng)計模型，但是通常確實要求用戶提供參數(shù)，以便由數(shù)據(jù)學習。如指定直方圖的類型（等寬或等深的）和其他參數(shù)（如直方圖中的箱數(shù)或每個箱的大?。?。與參數(shù)方法不同，這些參數(shù)并不指定數(shù)據(jù)分布的類型（如高斯分布）。
步驟2：檢測離群點。為了確定一個對象是否是離群點，可以對照直方圖檢驗它。在最簡單的方法中，如果該對象落入直方圖的一個箱中，則該對象被看做是正常的，否則被認為是離群點。

對于更復雜的方法，可以使用直方圖賦予每個對象一個離群點得分。一般可以令對象的離群點得分為該對象落入的箱的容積的倒數(shù)。得分越高，表明是離群點的概率越大。

使用直方圖作為離群點檢測的非參數(shù)模型的一個缺點是，很難選擇一個合適的箱尺寸。一方面，如箱尺寸太小，則由很多正常對象都會落入空的或稀疏箱，因而被誤識別為離群點。這將導致很高的假正例率或低精度。相反，如果箱尺寸太大，則離群點對象可能滲入某些頻繁的箱中，這將導致很高的假負例率或召回率。為了解決這些問題，使用核密度估計來估計數(shù)據(jù)的概率密度分布。具體參考韓家煒的《數(shù)據(jù)挖掘：概念與技術》。

3.2 基于鄰近性的方法

??給定特征空間中的對象集，可以使用距離度量來量化對象間的相似性?；卩徑缘姆椒俣ǎ弘x群點對象與它最近鄰的鄰近性顯著偏離數(shù)據(jù)集中其他對象與它們近鄰之間的鄰近性。
??有兩種類型的基于鄰近性的離群點檢測方法：基于距離的和基于密度的方法?；诰嚯x的離群點檢測方法考慮對象給定半徑的鄰域。一個對象被認為是離群點，如果它的鄰域內(nèi)沒有足夠多的其他點?；诿芏鹊碾x群點檢測方法考察對象和它近鄰的密度。這里，一個對象被識別為離群點，如果它的密度相對于它的近鄰低得多。

3.2.1 基于距離的離群點檢測

對于待分析的數(shù)據(jù)對象集D，用戶可以指定一個距離閾值r來定義對象的合理鄰域。對于每個對象o，可以考察o的r-鄰域中的其他對象的個數(shù)。如果D中大多數(shù)對象都遠離o，即都不在o的r-鄰域中，則o可以被視為一個離群點。
令是距離閾值，是分數(shù)閾值。對象是一個離群點，如果
其中是距離度量。
如何計算-離群點？一是嵌套循環(huán)方法，時間復雜度為。當數(shù)據(jù)集很大時，該方法的開銷很大。為了改進性能，可以用基于網(wǎng)格的方法來實現(xiàn)。具體見韓家煒《數(shù)據(jù)挖掘》一書。

3.2.2 基于密度的離群點檢測

基于距離的離群點檢測從全局考慮數(shù)據(jù)集。由于以下兩個原因，這種離群點被看成“全局離群點”：
l 例如，一個-離群點至少遠離（用參數(shù)r定量）數(shù)據(jù)集中的對象。換言之，這種離群點遠離數(shù)據(jù)的大多數(shù)。
l 為了檢測基于距離的離群點，需要兩個距離參數(shù)，它們用于每個離群點對象。
現(xiàn)實世界的許多數(shù)據(jù)集都呈現(xiàn)更復雜的結構，那里對象可能關于其局部鄰域，而不是關于整個數(shù)據(jù)分布而被視為離群點。如下圖，基于距離的離群點檢測方法不能捕獲像o1和o2這樣的局部離群點。
那么，如何確切地定義如圖所示的局部離群點？這里關鍵的思想是，需要把對象周圍的密度與對象鄰域周圍的密度進行比較?；诿芏鹊碾x群點檢測方法的基本假定是：非離群點對象周圍的密度與其鄰域周圍的密度類似，而離群點對象周圍的密度顯著不同于其鄰域周圍的密度。

3.3 基于聚類的方法

基于聚類的方法通過考察對象與簇之間的關系檢測離群點。直觀地，離群點是一個對象，它屬于小的偏遠簇，或不屬于任何簇。
這導致三種基于聚類的離群點檢測的一般方法。考慮一個對象。
l 該對象屬于某個簇嗎？如果不，則它被識別為離群點。
l 該對象與最近的簇之間的距離很遠嗎？如果是，則它是離群點。
l 該對象是小簇或稀疏簇的一部分嗎?如果是，則該簇中的所有對象都是離群點。

下面對每一種方法考察一個例子。

例1 把離群點檢測為不屬于任何簇的對象。如圖1所示，使用基于密度的聚類方法，如DBSCAN,注意到黑色點都屬于簇，白色點a不屬于任何簇，因而被認為是離群點。

圖1 對象a是離群點，因為 它不屬于任何簇

圖2 離群點（a,b,c）都（關于簇中心）遠離距它們最近的簇

例2 使用到最近簇的距離的基于聚類的離群點檢測。如圖2所示，使用k-均值聚類方法，可以把圖2中的數(shù)據(jù)點劃分成3個簇，如圖中不同符號所示，每個簇中心用“+”標記。對于每個對象o，都可以根據(jù)該對象與最近簇中心的距離，賦予該對象一個離群點得分。假設到o的最近中心為c,則o與c之間的距離為dist(o,c)，c與指派到c的對象之間的平均距離為L,比率度量與平均值的差異程度。在圖2中，點a,b和c都相對遠離它們的對應中心，因而被懷疑是離群點。

例3 檢測小簇中的離群點

迄今為止我們看到的每種方法都只檢測個體離群點，因為它們一次把一個對象與數(shù)據(jù)集中的簇進行比較。然而，在大型數(shù)據(jù)中，一些離群點可能是類似的，并且形成一個小簇。例如，在入侵檢測中，使用相同手段攻擊系統(tǒng)的黑客可能形成一個簇。迄今為止所討論的方法可能被這種離群點所欺騙。
為了解決這一問題，第三種基于聚類的離群點檢測方法識別小簇或稀疏簇，并宣告這些簇中的對象也是離群點。這種方法的一個例子是FindCBLOF算法，其方法如下。

（1） 找出數(shù)據(jù)集中的簇，并把它們按大小降序排列。該算法假定大部分數(shù)據(jù)點都不是離群點，它使用一個參數(shù)來區(qū)別大簇和小簇。任何至少包含數(shù)據(jù)集中百分之（如，=90%）數(shù)據(jù)點的簇都被視為大簇，而其余的簇被看成小簇。
（2） 對于每個數(shù)據(jù)點賦予基于簇的局部離群點因子（CBLOF），對于屬于大簇的點，它的CBLOF是簇的大小和該點與簇的相似性的乘積。對于屬于小簇的點，它的CBLOF用小簇的大小和該點與最近的大簇的相似性的乘積計算。
CBLOF用統(tǒng)計學方法定義點和簇之間的相似性，代表點屬于簇的概率。該值越大，點與簇越相似。CBLOF值可以檢測遠離任何簇的離群點。
基于聚類的離群點檢測方法具有如下優(yōu)點。首先，它們可以檢測離群點，而不要求數(shù)據(jù)是有標號的，即它們以無監(jiān)督方式檢測。它們對許多類型的數(shù)據(jù)都有效。簇可以看成是數(shù)據(jù)的概括，一旦得到簇，基于聚類的方法只需要把對象與簇進行比較，以確定該對象是否是離群點，這一過程通常很快，因為與對象總數(shù)相比，簇的個數(shù)通常很小。
基于聚類的方法的缺點是：它的有效性高度依賴于所使用的聚類方法。這些方法對于離群點檢測而言可能不是最優(yōu)的。對于大型數(shù)據(jù)集，聚類方法通常開銷很大，這可能成為一個瓶頸。

3.4 基于分類的方法

如果訓練數(shù)據(jù)具有類標號，則離群點檢測可以看做分類問題。基于分類的離群點檢測方法的一般思想是，訓練一個可以區(qū)分“正?！睌?shù)據(jù)和離群點的分類模型。
基于分類的離群點檢測方法通常使用一類模型（單分類模型SVDD），即構造一個僅描述正常類的分類器，不屬于正常類的任何樣本都被視為離群點。
基于分類的方法和基于聚類的方法可以聯(lián)合使用，以半監(jiān)督的方式檢測離群點。
例通過半監(jiān)督學習檢測離群點

如上圖所示，其中對象被標記為“正常”或“離群點”，或者沒有標號。使用基于聚類的方法，發(fā)現(xiàn)一個大簇C和一個小簇C1。因為C中的某些對象攜帶了標號“正常”，因此可以把該簇的所有對象（包括沒有標號的對象）都看做正常對象。在離群點檢測中，使用這個簇的一類模型來識別離群點。類似的，因為簇C1中的某些對象攜帶標號“離群點”，因此宣布C1中的所有對象都是離群點。未落入C模型中的任何對象（如a）也被視為離群點。

3.5 挖掘情境離群點和集體離群點

與一般的離群點檢測相比，識別情境離群點需要分析對應的情境信息。情境離群點檢測方法可以根據(jù)情境是否可以清楚地識別而分成兩類。

3.5.1 把情境離群點檢測轉(zhuǎn)換成傳統(tǒng)的離群點檢測

這類方法適用于情境可以被清楚識別的情況，其基本思想是把情境離群點檢測問題轉(zhuǎn)換成典型的離群點檢測問題。具體地說，對于給定的數(shù)據(jù)對象，用兩步來評估該對象是否是離群點。第一步，使用對象的情境屬性識別對象的情境。第二步，使用一種傳統(tǒng)的離群點檢測方法，估計該對象的離群點得分。

3.5.2 關于情境對正常行為建模

在某些應用中，清楚地把數(shù)據(jù)劃分成情境是不方便的或不可行的。這時，可以關于情境對正常行為建模。使用一個訓練數(shù)據(jù)集，這種方法訓練一個模型，關于情境屬性的值，預測期望的行為屬性值。然后，為了確定一個數(shù)據(jù)對象是否是情境離群點，可以在該對象的情境屬性上使用該模型。如果該對象的行為屬性值顯著地偏離該模型的預測值，則該對象被宣布為情境離群點。
通過使用連接情境和行為的預測模型，這些方法避免直接識別具體情境。許多分類和預測技術都可以用來構建這種模型，如回歸、馬爾科夫模型和有窮狀態(tài)自動機等等。

3.5.3 挖掘集體離群點

與情境離群點檢測一樣，集體離群點檢測方法也可以劃分為兩類。第一類方法把問題歸結為傳統(tǒng)的離群點檢測。其策略是識別結構單元，把每個結構單元（例如，子序列、時間序列片段、局部區(qū)域或子圖）看做是一個數(shù)據(jù)對象，并提取特征。這樣，集體離群點檢測問題就轉(zhuǎn)換成在使用提取的特征構造的“結構化對象”集上的離群點檢測。一個結構單元代表原數(shù)據(jù)集中的一組對象，如果該結構單元顯著地偏離提取的特征空間中的期望趨勢，則它是一個集體離群點。
為集體離群點檢測預先定義結構單元可能是困難的，或者是不可能的。因此，第二類方法直接對結構單元的期望行為建模。例如，為了在時間序列中檢測離群點，一種方法是從序列中學習馬爾科夫模型。因此，一個子序列被宣布為集體離群點，如果它顯著地偏離該模型。

3.6 高維數(shù)據(jù)中的離群點檢測

一般地，高維數(shù)據(jù)的離群點檢測方法應該應對以下挑戰(zhàn)：

l 離群點的解釋：不僅應該能夠識別檢測離群點，而且能夠提供離群點的解釋。離群點的解釋可能是，例如，揭示離群點的特定子空間，或者關于對象的“離群點性”的評估。這種解釋可以幫助用戶理解離群點的含義和意義。
l 數(shù)據(jù)的稀疏性：這些方法應該能處理高維空間的稀疏性。隨著維度的增加，對象之間的距離嚴重地被噪聲所左右。因此，高維空間中的數(shù)據(jù)通常是稀疏的。
l 數(shù)據(jù)子空間：它們應該以合適的方式對離群點建模，例如，自適應現(xiàn)實離群點的子空間和捕獲數(shù)據(jù)的局部變化。在所有的子空間上使用固定的距離閾值來檢測離群點捕食一種好想法，因為兩個對象之間的距離隨著維度增加而單調(diào)增加。
l 關于維度的可伸縮性：隨著維度的增加，子空間的數(shù)量指數(shù)增加。包含所有可能的子空間的窮舉組合探索不是可伸縮的選擇。
高維數(shù)據(jù)的離群點檢測方法可以劃分成三種主要方法，包括擴充的傳統(tǒng)離群點檢測、發(fā)現(xiàn)子空間中的離群點和對高維離群點建模。

3.6.1 擴充的傳統(tǒng)離群點檢測

一種高維數(shù)據(jù)離群點檢測方法是擴充的傳統(tǒng)離群點檢測方法。它使用傳統(tǒng)的基于鄰近性的離群點模型。然而，為了克服高維空間中鄰近性度量惡化問題，它使用其他度量，或構造子空間并在其中檢測離群點。

HilOut算法就是這種方法的一個例子。HitOut找出基于距離的離群點，但在離群點檢測中使用距離的秩，而不是絕對距離。具體地說，對于每個對象o，HitOut找出o的k個最近鄰，記作nn1(o),nn2(o)……nnk(o),其中k是一個依賴于應用的參數(shù)。參數(shù)o的權重定義為

所有對象按權重遞減序定秩。權重最高的top-p個對象作為離群點輸出，其中p是另一個用戶指定的參數(shù)。

HilOut算法計算每個對象的k-最近鄰開銷很大，當維度很高并且數(shù)據(jù)很大時不能伸縮。
另一種方法則是通過維歸約，把高維離群點檢測問題歸結為較低維上的離群點檢測。其基本思想是，把高維空間歸約到低維空間，那里標準的距離度量仍然能夠區(qū)分離群點。如果能夠找到這樣的較低維空間，則可以用傳統(tǒng)的離群點檢測方法。
為了降低維度，可以對離群點檢測使用或擴充一般的特征特征選擇和提取方法。例如，可以用主成分分析（PCA）來提取一個低維空間。

3.6.2 發(fā)現(xiàn)子空間中的離群點

高維數(shù)據(jù)中離群點檢測的另一種方法是搜索各種子空間中的離群點。其唯一的優(yōu)點是，如果發(fā)現(xiàn)一個對象是很低維度的子空間的離群點，則該子空間提供了重要信息，解釋該對象為什么和在何種程度上是離群點。
如何檢測子空間中的離群點，一種方法是基于網(wǎng)格的子空間離群點檢測。具體做法見韓家煒《數(shù)據(jù)挖掘》。

3.6.3 高維離群點建模

另一種方法是試圖直接為高維離群點建立一個新模型。這種方法通常避免鄰近性度量，而是采用新的啟發(fā)式方法來檢測離群點。具體做法見韓家煒《數(shù)據(jù)挖掘》。