『壹』 聚類分析法
聚類分析，亦稱群分析或點分析，是研究多要素事物分類問題的數量方法。其基本原理是，根據樣本自身的屬性，用數學方法按照某些相似性或差異性指標，定量地確定樣本之間的親疏關系，並按親疏關系的程度對樣本進行聚類（徐建華，1994）。
聚類分析方法，應用在地下水中，是在各種指標和質量級別標准約束條件下，通過樣品的各項指標監測值綜合聚類，以判別地下水質量的級別。常見的聚類分析方法有系統聚類法、模糊聚類法和灰色聚類法等。
（一）系統聚類法
系統聚類法的主要步驟有：數據標准化、相似性統計量計算和聚類。
1.數據標准化
在聚類分析中，聚類要素的選擇是十分重要的，它直接影響分類結果的准確性和可靠性。在地下水質量研究中，被聚類的對象常常是多個要素構成的。不同要素的數據差異可能很大，這會對分類結果產生影響。因此當分類要素的對象確定之後，在進行聚類分析之前，首先對聚類要素進行數據標准化處理。
假設把所考慮的水質分析點（G）作為聚類對象（有m個），用i表示（i=1，2，…，m）；把影響水質的主要因素作為聚類指標（有n個），用j表示（j=1，2，…，n），它們所對應的要素數據可用表4-3給出。在聚類分析中，聚類要素的數據標准化的方法較多，一般採用標准差法和極差法。
表4-3 聚類對象與要素數據
對於第j個變數進行標准化，就是將xij變換為x′ij。
（1）總和標准化
區域地下水功能可持續性評價理論與方法研究
這種標准化方法所得的新數據x′ij滿足
區域地下水功能可持續性評價理論與方法研究
（2）標准差標准化
區域地下水功能可持續性評價理論與方法研究
式中：
由這種標准化方法所得的新數據x′ij，各要素的平均值為0，標准差為1，即有
區域地下水功能可持續性評價理論與方法研究
（3）極差標准化
區域地下水功能可持續性評價理論與方法研究
經過這種標准化所得的新數據，各要素的極大值為1，極小值為0，其餘的數值均在［0，1］閉區間內。
上述式中：xij為j變數實測值；xj為j變數的樣本平均值；sj為樣本標准差。
2.相似性統計量
系統聚類法要求給出一個能反映樣品間相似程度的一個數字指標，需要找到能量度相似關系的統計量，這是系統聚類法的關鍵。
相似性統計量一般使用距離系數和相似系數進行計算。距離系數是把樣品看成多維空間的點，用點間的距離來表示研究對象的緊密關系，距離越小，表明關系越密切。相似系數值表明樣本和變數間的相似程度。
（1）距離系數
常採用歐幾里得絕對距離，其中i樣品與j樣品距離dij為
區域地下水功能可持續性評價理論與方法研究
dij越小，表示i，j樣品越相似。
（2）相似系數
常見的相似系數有夾角餘弦和相關系數，計算公式為
1）夾角餘弦
區域地下水功能可持續性評價理論與方法研究
在式（4-20）中：-1≤cosθij≤1。
2）相關系數
區域地下水功能可持續性評價理論與方法研究
式中：dij為i樣品與j樣品的歐幾里得距離；cosθij為i樣品與j樣品的相似系數；rij為i樣品與j樣品的相關系數；xik為i樣品第k個因子的實測值或標准化值；xjk為j樣品第k個因子的實測值或標准化值；
3.聚類
在選定相似性統計量之後，根據計算結果構成距離或相似性系數矩陣（n×n），然後通過一定的方法把n個樣品組合成不同等級的分類單位，對類進行並類，即將最相似的樣品歸為一組，然後，把次相似的樣品歸為分類級別較高的組。聚類主要有直接聚類法、距離聚類法（最短距離聚類法、最遠距離聚類法）。
（1）直接聚類法
直接聚類法，是根據距離或相似系數矩陣的結構一次並類得到結果，是一種簡便的聚類方法。它首先把各個分類對象單獨視為一類，然後根據距離最小或相似系數最大的原則，依次選出一對分類對象，並成新類。如果一對分類對象正好屬於已歸的兩類，則把這兩類並為一類。每一次歸並，都劃去該對象所在的列與列序相同的行。經過n-1次把全部分類對象歸為一類，最後根據歸並的先後順序作出聚類分析譜系圖。
（2）距離聚類法
距離聚類法包括最短距離聚類法和最遠距離聚類法。最短距離聚類法具有空間壓縮性，而最遠距離聚類法具有空間擴張性。這兩種聚類方法關於類之間的距離計算可以用一個統一的公式表示：
區域地下水功能可持續性評價理論與方法研究
當γ=-0.5時，式（4-22）計算類之間的距離最短；當γ=0.5時，式（4-22）計算類之間的距離最遠。
最短、最遠距離法，是在原來的n×n距離矩陣的非對角元素中找出dpq=min（dij）或dpq=max（dij），把分類對象Gp和Gq歸並為一新類Gr，然後按計算公式：
dpq=min（dpk，dqk）（k≠ p，q） （4-23）
dpq=max（dpk，dqk）（k≠ p，q） （4-24）
計算原來各類與新類之間的距離，這樣就得到一個新的（n-1）階的距離矩陣；再從新的距離矩陣中選出最小或最大的dij，把Gi和Gj歸並成新類；再計算各類與新類的距離，直至各分類對象被歸為一類為止。最後綜合整個聚類過程，作出最短距離或最遠距離聚類譜系圖（圖4-1）。
圖4-1 地下水質量評價的聚類譜系圖
（二）模糊聚類法
模糊聚類法是普通聚類方法的一種拓展，它是在聚類方法中引入模糊概念形成的。該方法評價地下水質量的主要步驟，包括數據標准化、標定和聚類3個方面（付雁鵬等，1987）。
1.數據標准化
在進行聚類過程中，由於所研究的各個變數絕對值不一樣，所以直接使用原始數據進行計算就會突出絕對值大的變數，而降低絕對值小的變數作用，特別是在進行模糊聚類分析中，模糊運算要求必須將數據壓縮在［0，1］之間。因此，模糊聚類計算的首要工作是解決數據標准化問題。數據標准化的方法見系統聚類分析法。
2.標定與聚類
所謂標定就是計算出被分類對象間的相似系數rij，從而確定論域集U上的模糊相似關系Rij。相似系數的求取，與系統聚類分析法相同。
聚類就是在已建立的模糊關系矩陣Rij上，給出不同的置信水平λ（λ∈［0，1］）進行截取，進而得到不同的分類。
聚類方法較多，主要有基於模糊等價關系基礎上的聚類與基於最大樹的聚類。
（1）模糊等價關系方法
所謂模糊等價關系，是指具有自反性（rii=1）、對稱性（rij=rji）與傳遞性（R·R⊆R）的模糊關系。
基於模糊等價關系的模糊聚類分析方法的基本思想是：由於模糊等價關系R是論域集U與自己的直積U×U上的一個模糊子集，因此可以對R進行分解，當用λ-水平對R作截集時，截得的U×U的普通子集Rλ就是U上的一個普通等價關系，也就是得到了關於U中被分類對象元素的一種。當λ由1下降到0時，所得的分類由細變粗，逐漸歸並，從而形成一個動態聚類譜系圖（徐建華，1994）。此類分析方法的具體步驟如下。
第一步：模糊相似關系的建立，即計算各分類對象之間相似性統計量。
第二步：將模糊相似關系R改造為模糊等價關系R′。模糊等價關系要求滿足自反性、對稱性與傳遞性。一般而言，模糊相似關系滿足自反性和對稱性，但不滿足傳遞性。因此，需要採用傳遞閉合的性質將模糊相似關系改造為模糊等價關系。改造的方法是將相似關系R自乘，即
R2=R·R
R4=R2·R2
︙
這樣計算下去，直到：R2k=Rk·Rk=Rk，則R′=Rk便是一個模糊等價關系。
第三步：在不同的截集水平下進行聚類。
（2）最大樹聚類方法
基於最大樹的模糊聚類分析方法的基本思路是：最大樹是一個不包含迴路的連通圖（圖4-2）；選取λ水平對樹枝進行截取，砍去權重低於λ 的枝，形成幾個孤立的子樹，每一棵子樹就是一個類的集合。此類分析方法的具體步驟如下。
圖4-2 最大聚類支撐樹圖
第一步：計算分類對象之間的模糊相似性統計量rij，構建最大樹。
以所有被分類的對象為頂點，當兩點間rij不等於0時，兩點間可以用樹干連接，這種連接是按rij從大到小的順序依次進行的，從而構成最大樹。
第二步：由最大樹進行聚類分析。
選擇某一λ值作截集，將樹中小於λ值的樹干砍斷，使相連的結點構成一類，即子樹，當λ由1到0時，所得到的分類由細變粗，各結點所代表的分類對象逐漸歸並，從而形成一個動態聚類譜系圖。
在聚類方法中，模糊聚類法比普通聚類法有較大的突破，簡化了運算過程，使聚類法更易於掌握。
（三）灰色聚類法
灰色聚類是根據不同聚類指標所擁有的白化數，按幾個灰類將聚類對象進行歸納，以判斷該聚類對象屬於哪一類。
灰色聚類應用於地下水水質評價中，是把所考慮的水質分析點作為聚類對象，用i表示（i=1，2，…，n）；把影響水質的主要因素作為聚類指標，用j表示（j=1，2，…，m），把水質級別作為聚類灰數（灰類），用k表示（k=1，2，3）即一級、二級、三級3個灰類（羅定貴等，1995）。
灰色聚類的主要步驟：確定聚類白化數、確定各灰色白化函數fjk、求標定聚類權重ηjk、求聚類系數和按最大原則確定聚類對象分類。
1.確定聚類白化數
當各灰類白化數在數量上相差懸殊時，為保證各指標間的可比性與等效性，必須進行白化數的無量綱化處理。即給出第i個聚類對象中第j個聚類指標所擁有的白化數，i=1，2，…，n；j=1，2，…，m。
2.確定各灰色白化函數
建立滿足各指標、級別區間為最大白化函數值（等於1），偏離此區間愈遠，白化函數愈小（趨於0）的功效函數fij（x）。根據監測值Cki，可在圖上（圖4-3）解析出相應的白化函數值fjk（Cik），j=1，2，…，m；k=1，2，3。
3.求標定聚類權重
根據式（4-25），計算得出聚類權重ηjk的矩陣（n×m）。
區域地下水功能可持續性評價理論與方法研究
式中：ηjk為第j個指標對第k個灰類的權重；λjk為白化函數的閾值（根據標准濃度而定）。
圖4-3 白化函數圖
註：圖4-3白化函數f（x）∈［0，1］，具有下述特點：①平頂部分，表示該量的最佳程度。這部分的值為最佳值，即系數（權）為1，f（x）=max=1（峰值），x∈［x2，x3］。②白化函數是單調變化的，左邊部分f（x）=L（x），單調增，x∈（x1，x2］，稱為白化的左支函數；右邊部分f（x）=R（x），單調減，x∈［x3，x4），稱為白化的右支函數。③白化函數左右支函數對稱。④白化函數，為了簡便，一般是直線。⑤白化函數的起點和終點，一般來說是人為憑經驗確定。
4.求聚類系數
σik=∑fjk（dij）ηjk （4-26）
式中：σik為第i個聚類對象屬於第k個灰類的系數，i=1，2，…，n；k=1，2，3。
5.按最大原則確定聚類對象分類
由σik構造聚類向量矩陣，行向量最大者，確定k樣品屬於j級對應的級別。
用灰色聚類方法進行地下水水質評價，能最大限度地避免因人為因素而造成的「失真、失效」現象。
聚類方法計算相對復雜，但是計算結果與地下水質量標准級別對應性明顯，能夠較全面反映地下水質量狀況，也是較高層次定量研究地下水質量的重要方法。
『貳』 異常檢測方法 二
離群點是一個數據對象，它顯著不同於其他數據對象，好像它是被不同的機制產生的一樣。有時也稱非離群點為「正常數據」，離群點為「異常數據」。
離群點不同於雜訊數據。雜訊是被觀測變數的隨機誤差或方差。一般而言，雜訊在數據分析（包括離群點分析）中不是令人感興趣的。如在信用卡欺詐檢測，顧客的購買行為可以用一個隨機變數建模。一位顧客可能會產生某些看上去像「隨機誤差」或「方差」的雜訊交易，如買一份較豐盛的午餐，或比通常多要了一杯咖啡。這種交易不應該視為離群點，否則信用卡公司將因驗證太多的交易而付出沉重代價。因此，與許多其他數據分析和數據挖掘任務一樣，應該在離群點檢測前就刪除雜訊。
離群點檢測是有趣的，因為懷疑產生它們的機制不同於產生其他數據的機制。因此，在離群點檢測時，重要的是搞清楚為什麼檢測到的離群點被某種其他機制產生。通常，在其餘數據上做各種假設，並且證明檢測到的離群點顯著違反了這些假設。
離群點可以分成三類：全局離群點、情境（或條件）離群點和集體離群點。
在給定的數據集中，一個數據對象是全局離群點，如果它顯著的偏離數據集中的其他對象。全局離群點是最簡單的一類離群點，大部分的離群點檢測方法都旨在找出全局離群點。
在給定的數據集中，一個數據對象是情境離群點，如果關於對象的特定情境，它顯著的偏離其他對象。情境離群點又稱為條件離群點，因為它們條件的依賴於選定的情境。一般地，在情境離群點檢測中，所考慮數據對象的屬性劃分成兩組：
情境屬性 ：數據對象的情境屬性定義對象的情境。一般為靜態屬性變數，如信用卡欺詐檢測中，不同年齡、不同地區的人消費情況是不同的，先按照靜態屬性將人群大致分類，再檢測每一類的離群點，會得到更好的結果。
行為屬性 ：定義對象的特徵，並用來評估對象關於它所處的情境是否為離群點。在上述例子中，行為屬性可以是消費金額，消費頻率等
情境離群點分析為用戶提供了靈活性，因為用戶可以在不同情境下考察離群點，這在許多應用中都是非常期望的。
給定一個數據集，數據對象的一個子集形成集體離群點，如果這些對象作為整體顯著的偏離整個數據集。如一家供應鏈公司，每天處理數以千計的訂單和出貨。如果一個訂單的出貨延誤，則可能不是離群點，因為統計表明延誤時常發生。然而，如果有一天有100個訂單延誤，則必須注意。這100個訂單整體來看，形成一個離群點，盡管如果單個考慮，它們每個或許都不是離群點。你可能需要更詳細地整個考察這些訂單，搞清楚出貨問題。
與全局和情境離群點檢測不同，在集體離群點檢測中，不僅必須考慮個體對象的行為，而且還要考慮對象組群的行為。因此，為了檢測集體離群點，需要關於對象之間聯系的背景知識，如對象之間的距離或相似性測量方法。
離群點檢測的統計學方法對數據的正常性做假定。假定數據集中的正常對象由一個隨機過程（生成模型）產生。因此，正常對象出現在該隨機模型的高概率區域中，而低概率區域中的對象是離群點。
離群點檢測的統計學方法的一般思想是：學習一個擬合給定數據集的生成模型，然後識別該模型低概率區域中的對象，把它們作為離群點。有許多不同方法來學習生成模型，一般而言，根據如何指定和如何學習模型，離群點檢測的統計學方法可以劃分成兩個主要類型： 參數方法和非參數方法。
參數方法: 假定正常的數據對象被一個以為參數的參數分布產生。該參數分布的概率密度函數給出對象被該分布產生的概率。該值越小，越可能是離群點。
非參數方法: 並不假定先驗統計模型，而是試圖從輸入數據確定模型。非參數方法的例子包括直方圖和核密度估計。
假定數據集由一個正態分布產生，然後，可以由輸入數據學習正態分布的參數，並把低概率的點識別為離群點。
在正態分布的假定下，區域包含99.7%的數據，包含95.4%的數據，包含68.3%的數據。視具體情況而定，將其區域外的數據視為離群點。
這種直截了當的統計學離群點檢測方法也可以用於可視化。例如盒圖方法使用五數概況繪制一元輸入數據：最小的非離群點值（Min）、第一個四分位數（Q1）、中位數（Q2）、第三個四分位數（Q3）和最大的非離群點值（Max）。
四分位數極差（IQR）定義為Q3-Q1。比Q1小1.5倍的IQR或者比Q3大1.5倍的IQR的任何對象都視為離群點，因為Q1-1.5 IQR和Q3+1.5 IQR之間的區域包含了99.3%的對象。
（1）使用馬哈拉諾比斯距離檢測多元離群點。
對於一個多元數據集，設為均值向量。對於數據集中的對象，從到的馬哈拉諾比斯（Mahalanobis）距離為其中S是協方差矩陣。是一元數據，可以對它進行離群點檢測。如果被確定為離群點，則也被視為離群點。
（2）使用統計量的多元離群點檢測。
在正態分布的假設下，統計量可以用來捕獲多元離群點。對於對象，統計量是
其中，是在第維上的值，是所有對象在第維上的均值，而是維度。如果對象的統計量很大，則該對象是離群點。
（3）使用混合參數分布
在許多情況下，數據是由正態分布產生的假定很有效。然而，當實際數據很復雜時，這種假定過於簡單。在這種情況下，假定數據是被混合參數分布產生的。
混合參數分布中用期望最大化（EM）演算法來估計參數。具體情況比較復雜，可以參考韓家煒的《數據挖掘：概念與技術》一書。
在離群點檢測的非參數方法中，「正常數據」的模型從輸入數據學習，而不是假定一個先驗。通常，非參數方法對數據做較少假定，因而在更多情況下都可以使用。
使用直方圖檢測離群點
包括如下兩步：
步驟1： 構造直方圖。盡管非參數方法並不假定任何先驗統計模型，但是通常確實要求用戶提供參數，以便由數據學習。如指定直方圖的類型（等寬或等深的）和其他參數（如直方圖中的箱數或每個箱的大小）。與參數方法不同，這些參數並不指定數據分布的類型（如高斯分布）。
步驟2： 檢測離群點。為了確定一個對象是否是離群點，可以對照直方圖檢驗它。在最簡單的方法中，如果該對象落入直方圖的一個箱中，則該對象被看做是正常的，否則被認為是離群點。
對於更復雜的方法，可以使用直方圖賦予每個對象一個離群點得分。一般可以令對象的離群點得分為該對象落入的箱的容積的倒數。得分越高，表明是離群點的概率越大。
使用直方圖作為離群點檢測的非參數模型的一個缺點是，很難選擇一個合適的箱尺寸。一方面，如箱尺寸太小，則由很多正常對象都會落入空的或稀疏箱，因而被誤識別為離群點。這將導致很高的假正例率或低精度。相反，如果箱尺寸太大，則離群點對象可能滲入某些頻繁的箱中，這將導致很高的假負例率或召回率。為了解決這些問題，使用核密度估計來估計數據的概率密度分布。具體參考韓家煒的《數據挖掘：概念與技術》。
給定特徵空間中的對象集，可以使用距離度量來量化對象間的相似性。基於鄰近性的方法假定：離群點對象與它最近鄰的鄰近性顯著偏離數據集中其他對象與它們近鄰之間的鄰近性。
有兩種類型的基於鄰近性的離群點檢測方法：基於距離的和基於密度的方法。基於距離的離群點檢測方法考慮對象給定半徑的鄰域。一個對象被認為是離群點，如果它的鄰域內沒有足夠多的其他點。基於密度的離群點檢測方法考察對象和它近鄰的密度。這里，一個對象被識別為離群點，如果它的密度相對於它的近鄰低得多。
對於待分析的數據對象集D，用戶可以指定一個距離閾值r來定義對象的合理鄰域。對於每個對象o，可以考察o的r-鄰域中的其他對象的個數。如果D中大多數對象都遠離o，即都不在o的r-鄰域中，則o可以被視為一個離群點。
令是距離閾值，是分數閾值。對象是一個離群點，如果
其中是距離度量。
如何計算-離群點？一是嵌套循環方法，時間復雜度為。當數據集很大時，該方法的開銷很大。為了改進性能，可以用基於網格的方法來實現。具體見韓家煒《數據挖掘》一書。
基於距離的離群點檢測從全局考慮數據集。由於以下兩個原因，這種離群點被看成「全局離群點」：
l 例如，一個-離群點至少遠離（用參數r定量）數據集中的對象。換言之，這種離群點遠離數據的大多數。
l 為了檢測基於距離的離群點，需要兩個距離參數，它們用於每個離群點對象。
現實世界的許多數據集都呈現更復雜的結構，那裡對象可能關於其局部鄰域，而不是關於整個數據分布而被視為離群點。如下圖，基於距離的離群點檢測方法不能捕獲像o1和o2這樣的局部離群點。
那麼，如何確切地定義如圖所示的局部離群點？這里關鍵的思想是，需要把對象周圍的密度與對象鄰域周圍的密度進行比較。基於密度的離群點檢測方法的基本假定是：非離群點對象周圍的密度與其鄰域周圍的密度類似，而離群點對象周圍的密度顯著不同於其鄰域周圍的密度。
基於聚類的方法通過考察對象與簇之間的關系檢測離群點。直觀地，離群點是一個對象，它屬於小的偏遠簇，或不屬於任何簇。
這導致三種基於聚類的離群點檢測的一般方法。考慮一個對象。
l 該對象屬於某個簇嗎？如果不，則它被識別為離群點。
l 該對象與最近的簇之間的距離很遠嗎？如果是，則它是離群點。
l 該對象是小簇或稀疏簇的一部分嗎?如果是，則該簇中的所有對象都是離群點。
下面對每一種方法考察一個例子。
例1 把離群點檢測為不屬於任何簇的對象。如圖1所示，使用基於密度的聚類方法，如DBSCAN,注意到黑色點都屬於簇，白色點a不屬於任何簇，因而被認為是離群點。
圖1 對象a是離群點，因為 它不屬於任何簇
圖2 離群點（a,b,c）都（關於簇中心）遠離距它們最近的簇
例2 使用到最近簇的距離的基於聚類的離群點檢測。如圖2所示，使用k-均值聚類方法，可以把圖2中的數據點劃分成3個簇，如圖中不同符號所示，每個簇中心用「+」標記。對於每個對象o，都可以根據該對象與最近簇中心的距離，賦予該對象一個離群點得分。假設到o的最近中心為c,則o與c之間的距離為dist(o,c)，c與指派到c的對象之間的平均距離為L,比率度量與平均值的差異程度。在圖2中，點a,b和c都相對遠離它們的對應中心，因而被懷疑是離群點。
例3 檢測小簇中的離群點
迄今為止我們看到的每種方法都只檢測個體離群點，因為它們一次把一個對象與數據集中的簇進行比較。然而，在大型數據中，一些離群點可能是類似的，並且形成一個小簇。例如，在入侵檢測中，使用相同手段攻擊系統的黑客可能形成一個簇。迄今為止所討論的方法可能被這種離群點所欺騙。
為了解決這一問題，第三種基於聚類的離群點檢測方法識別小簇或稀疏簇，並宣告這些簇中的對象也是離群點。這種方法的一個例子是FindCBLOF演算法，其方法如下。
（1） 找出數據集中的簇，並把它們按大小降序排列。該演算法假定大部分數據點都不是離群點，它使用一個參數來區別大簇和小簇。任何至少包含數據集中百分之（如，=90%）數據點的簇都被視為大簇，而其餘的簇被看成小簇。
（2） 對於每個數據點賦予基於簇的局部離群點因子（CBLOF），對於屬於大簇的點，它的CBLOF是簇的大小和該點與簇的相似性的乘積。對於屬於小簇的點，它的CBLOF用小簇的大小和該點與最近的大簇的相似性的乘積計算。
CBLOF用統計學方法定義點和簇之間的相似性，代表點屬於簇的概率。該值越大，點與簇越相似。CBLOF值可以檢測遠離任何簇的離群點。
基於聚類的離群點檢測方法具有如下優點。首先，它們可以檢測離群點，而不要求數據是有標號的，即它們以無監督方式檢測。它們對許多類型的數據都有效。簇可以看成是數據的概括，一旦得到簇，基於聚類的方法只需要把對象與簇進行比較，以確定該對象是否是離群點，這一過程通常很快，因為與對象總數相比，簇的個數通常很小。
基於聚類的方法的缺點是：它的有效性高度依賴於所使用的聚類方法。這些方法對於離群點檢測而言可能不是最優的。對於大型數據集，聚類方法通常開銷很大，這可能成為一個瓶頸。
如果訓練數據具有類標號，則離群點檢測可以看做分類問題。基於分類的離群點檢測方法的一般思想是，訓練一個可以區分「正常」數據和離群點的分類模型。
基於分類的離群點檢測方法通常使用一類模型（單分類模型SVDD），即構造一個僅描述正常類的分類器，不屬於正常類的任何樣本都被視為離群點。
基於分類的方法和基於聚類的方法可以聯合使用，以半監督的方式檢測離群點。
例通過半監督學習檢測離群點
如上圖所示，其中對象被標記為「正常」或「離群點」，或者沒有標號。使用基於聚類的方法，發現一個大簇C和一個小簇C1。因為C中的某些對象攜帶了標號「正常」，因此可以把該簇的所有對象（包括沒有標號的對象）都看做正常對象。在離群點檢測中，使用這個簇的一類模型來識別離群點。類似的，因為簇C1中的某些對象攜帶標號「離群點」，因此宣布C1中的所有對象都是離群點。未落入C模型中的任何對象（如a）也被視為離群點。
與一般的離群點檢測相比，識別情境離群點需要分析對應的情境信息。情境離群點檢測方法可以根據情境是否可以清楚地識別而分成兩類。
這類方法適用於情境可以被清楚識別的情況，其基本思想是把情境離群點檢測問題轉換成典型的離群點檢測問題。具體地說，對於給定的數據對象，用兩步來評估該對象是否是離群點。第一步，使用對象的情境屬性識別對象的情境。第二步，使用一種傳統的離群點檢測方法，估計該對象的離群點得分。
在某些應用中，清楚地把數據劃分成情境是不方便的或不可行的。這時，可以關於情境對正常行為建模。使用一個訓練數據集，這種方法訓練一個模型，關於情境屬性的值，預測期望的行為屬性值。然後，為了確定一個數據對象是否是情境離群點，可以在該對象的情境屬性上使用該模型。如果該對象的行為屬性值顯著地偏離該模型的預測值，則該對象被宣布為情境離群點。
通過使用連接情境和行為的預測模型，這些方法避免直接識別具體情境。許多分類和預測技術都可以用來構建這種模型，如回歸、馬爾科夫模型和有窮狀態自動機等等。
與情境離群點檢測一樣，集體離群點檢測方法也可以劃分為兩類。第一類方法把問題歸結為傳統的離群點檢測。其策略是識別結構單元，把每個結構單元（例如，子序列、時間序列片段、局部區域或子圖）看做是一個數據對象，並提取特徵。這樣，集體離群點檢測問題就轉換成在使用提取的特徵構造的「結構化對象」集上的離群點檢測。一個結構單元代表原數據集中的一組對象，如果該結構單元顯著地偏離提取的特徵空間中的期望趨勢，則它是一個集體離群點。
為集體離群點檢測預先定義結構單元可能是困難的，或者是不可能的。因此，第二類方法直接對結構單元的期望行為建模。例如，為了在時間序列中檢測離群點，一種方法是從序列中學習馬爾科夫模型。因此，一個子序列被宣布為集體離群點，如果它顯著地偏離該模型。
一般地，高維數據的離群點檢測方法應該應對以下挑戰：
l 離群點的解釋：不僅應該能夠識別檢測離群點，而且能夠提供離群點的解釋。離群點的解釋可能是，例如，揭示離群點的特定子空間，或者關於對象的「離群點性」的評估。這種解釋可以幫助用戶理解離群點的含義和意義。
l 數據的稀疏性：這些方法應該能處理高維空間的稀疏性。隨著維度的增加，對象之間的距離嚴重地被雜訊所左右。因此，高維空間中的數據通常是稀疏的。
l 數據子空間：它們應該以合適的方式對離群點建模，例如，自適應現實離群點的子空間和捕獲數據的局部變化。在所有的子空間上使用固定的距離閾值來檢測離群點捕食一種好想法，因為兩個對象之間的距離隨著維度增加而單調增加。
l 關於維度的可伸縮性：隨著維度的增加，子空間的數量指數增加。包含所有可能的子空間的窮舉組合探索不是可伸縮的選擇。
高維數據的離群點檢測方法可以劃分成三種主要方法，包括擴充的傳統離群點檢測、發現子空間中的離群點和對高維離群點建模。
一種高維數據離群點檢測方法是擴充的傳統離群點檢測方法。它使用傳統的基於鄰近性的離群點模型。然而，為了克服高維空間中鄰近性度量惡化問題，它使用其他度量，或構造子空間並在其中檢測離群點。
HilOut演算法就是這種方法的一個例子。HitOut找出基於距離的離群點，但在離群點檢測中使用距離的秩，而不是絕對距離。具體地說，對於每個對象o，HitOut找出o的k個最近鄰，記作nn1(o),nn2(o)……nnk(o),其中k是一個依賴於應用的參數。參數o的權重定義為
所有對象按權重遞減序定秩。權重最高的top-p個對象作為離群點輸出，其中p是另一個用戶指定的參數。
HilOut演算法計算每個對象的k-最近鄰開銷很大，當維度很高並且數據很大時不能伸縮。
另一種方法則是通過維歸約，把高維離群點檢測問題歸結為較低維上的離群點檢測。其基本思想是，把高維空間歸約到低維空間，那裡標準的距離度量仍然能夠區分離群點。如果能夠找到這樣的較低維空間，則可以用傳統的離群點檢測方法。
為了降低維度，可以對離群點檢測使用或擴充一般的特徵特徵選擇和提取方法。例如，可以用主成分分析（PCA）來提取一個低維空間。
高維數據中離群點檢測的另一種方法是搜索各種子空間中的離群點。其唯一的優點是，如果發現一個對象是很低維度的子空間的離群點，則該子空間提供了重要信息，解釋該對象為什麼和在何種程度上是離群點。
如何檢測子空間中的離群點，一種方法是基於網格的子空間離群點檢測。具體做法見韓家煒《數據挖掘》。
另一種方法是試圖直接為高維離群點建立一個新模型。這種方法通常避免鄰近性度量，而是採用新的啟發式方法來檢測離群點。具體做法見韓家煒《數據挖掘》。
『叄』 什麼是基於聚類的離群點監測方法
本論文提出來一個聚類方法用以檢測離群點。通過使用k均值聚類演算法來從數據集中劃分聚類。離聚類中心比較近的點不太可能是離群點，同時我們可以從聚類中去除掉這些點。接下來計算剩下的點和離群點的距離。需要計算的離群點度的降低可能是由於一些點的去除。我們聲明離群度最高的點作為離群點。實驗數據使用真實數據集，並論證得知，即使所計算的數據比較少，但所提出的方法比現存的方法優越。
『肆』 數據挖掘之離群點檢測的方法
離群點檢測是數據挖掘中重要的一部分，它的任務是發現與大部分其他對象顯著不同的對象。大部分數據挖掘方法都將這種差異信息視為雜訊而丟棄，然而在一些應用中，罕見的數據可能蘊含著更大的研究價值。
離群點的檢測已經被廣泛應用於電信和信用卡的詐騙檢測、貸款審批、電子商務、網路入侵和天氣預報等領域。
離群點的主要成因有：數據來源於不同的類、自然變異、數據測量和手機誤差。
從數據范圍來看，分為全局離群點和局部離群點，整體來看，某些對象沒有離群特徵，但是從局部來看，卻顯示了一定的離群性。
從數據類型來看，分為數值型離群點和分類型離群點，這是以數據集的屬性類型進行劃分的。
從屬性的個數來看，分為一維離群點和多維離群點，一個對象可能有一個或多個屬性。
大部分的基於統計的離群點檢測方法是構建一個概率分布模型，並計算對象符合該模型的概率，把具有低概率的對象視為離群點。基於統計模型的離群點檢測方法的前提是必須知道數據集服從什麼分布；對於高維數據，檢驗效果可能很差。
通常可以在數據對象之間定義鄰近性度量，把原理大部分點的對象視為離群點。二位或三維的數據可以做散點圖觀察；大數據集不適用；對參數選擇敏感；具有全局閾值，不能處理具有不同密度區域的數據集
考慮數據集可能存在不同密度區域這一事實，從基於密度的觀點分析，離群點是在低密度區域中的對象。一個對象的離群點得分是該對象周圍密度的逆。給出了對象是離群點的定量度量，並且即使數據具有不同的區域也能夠很好的處理；大數據集不適用；參數選擇是困難的。
一種利用聚類檢測離群點的方法是丟棄遠離其他簇的小簇；另一種更系統的方法，首先聚類所有帝鄉，然後評估對象屬於簇的程度。基於聚類技術來發現離群點可能是高度有效的；聚類演算法產生的簇的質量對該演算法產生的離群點的質量影響非常大。
基於統計模型的離群點檢測方法需要滿足統計學原理，如果分布一直，則檢驗可能非常有效。基於鄰近度的離群點檢測方法比統計學方法更一般、更容易使用，因為確定數據集有意義的鄰近度量比確定他的統計分布更容易。基於密度的離群點檢測與基於鄰近度的離群點檢測密切相關，因為密度常用鄰近度定義：一種是定義密度為到K個最鄰近的平均距離的倒數，如果該距離小，則密度高；另一種是使用DBSCAN聚類演算法，一個對象周圍的密度等於該對象指定距離d內對象的個數。
『伍』 異常點檢測方法
一、基本概念
異常對象被稱作離群點。異常檢測也稱偏差檢測和例外挖掘。
常見的異常成因：數據來源於不同的類（異常對象來自於一個與大多數數據對象源（類）不同的源（類）的思想），自然變異，以及數據測量或收集誤差。
異常檢測的方法：
（1）基於模型的技術：首先建立一個數據模型，異常是那些同模型不能完美擬合的對象；如果模型是簇的集合，則異常是不顯著屬於任何簇的對象；在使用回歸模型時，異常是相對遠離預測值的對象。
（2）基於鄰近度的技術：通常可以在對象之間定義鄰近性度量，異常對象是那些遠離其他對象的對象。
（3）基於密度的技術：僅當一個點的局部密度顯著低於它的大部分近鄰時才將其分類為離群點。
二、異常點檢測的方法
1、統計方法檢測離群點
統計學方法是基於模型的方法，即為數據創建一個模型，並且根據對象擬合模型的情況來評估它們。大部分用於離群點檢測的統計學方法都是構建一個概率分布模型，並考慮對象有多大可能符合該模型。離群點的概率定義：離群點是一個對象，關於數據的概率分布模型，它具有低概率。這種情況的前提是必須知道數據集服從什麼分布，如果估計錯誤就造成了重尾分布。異常檢測的混合模型方法：對於異常檢測，數據用兩個分布的混合模型建模，一個分布為普通數據，而另一個為離群點。
聚類和異常檢測目標都是估計分布的參數，以最大化數據的總似然（概率）。聚類時，使用EM演算法估計每個概率分布的參數。然而，這里提供的異常檢測技術使用一種更簡單的方法。初始時將所有對象放入普通對象集，而異常對象集為空。然後，用一個迭代過程將對象從普通集轉移到異常集，只要該轉移能提高數據的總似然（其實等價於把在正常對象的分布下具有低概率的對象分類為離群點）。（假設異常對象屬於均勻分布）。異常對象由這樣一些對象組成，這些對象在均勻分布下比在正常分布下具有顯著較高的概率。
優缺點：（1）有堅實的統計學理論基礎，當存在充分的數據和所用的檢驗類型的知識時，這些檢驗可能非常有效；（2）對於多元數據，可用的選擇少一些，並且對於高維數據，這些檢測可能性很差。
2、基於鄰近度的離群點檢測。
一個對象是異常的，如果它遠離大部分點。這種方法比統計學方法更一般、更容易使用，因為確定數據集的有意義的鄰近性度量比確定它的統計分布更容易。一個對象的離群點得分由到它的k-最近鄰的距離給定。離群點得分對k的取值高度敏感。如果k太小（例如1），則少量的鄰近離群點可能導致較低的離群點得分；如果k太大，則點數少於k的簇中所有的對象可能都成了離群點。為了使該方案對於k的選取更具有魯棒性，可以使用k個最近鄰的平均距離。
優缺點：（1）簡單；（2）缺點：基於鄰近度的方法需要O(m^2)時間，大數據集不適用；（3）該方法對參數的選擇也是敏感的；（4）不能處理具有不同密度區域的數據集，因為它使用全局閾值，不能考慮這種密度的變化。
3、基於密度的離群點檢測。
從基於密度的觀點來說，離群點是在低密度區域中的對象。一個對象的離群點得分是該對象周圍密度的逆。基於密度的離群點檢測與基於鄰近度的離群點檢測密切相關，因為密度通常用鄰近度定義。一種常用的定義密度的方法是，定義密度為到k個最近鄰的平均距離的倒數。如果該距離小，則密度高，反之亦然。另一種密度定義是使用DBSCAN聚類演算法使用的密度定義，即一個對象周圍的密度等於該對象指定距離d內對象的個數。需要小心的選擇d，如果d太小，則許多正常點可能具有低密度，從而具有高離群點得分。如果d太大，則許多離群點可能具有與正常點類似的密度（和離群點得分）。使用任何密度定義檢測離群點具有與基於鄰近度的離群點方案類似的特點和局限性。特殊地，當數據包含不同密度的區域時，它們不能正確的識別離群點。
為了正確的識別這種數據集中的離群點，我們需要與對象鄰域相關的密度概念，也就是定義相對密度。常見的有兩種方法：（1）使用基於SNN密度的聚類演算法使用的方法；（2）用點x的密度與它的最近鄰y的平均密度之比作為相對密度。
使用相對密度的離群點檢測（局部離群點要素LOF技術）：首先，對於指定的近鄰個數（k），基於對象的最近鄰計算對象的密度density(x,k) ，由此計算每個對象的離群點得分；然後，計算點的鄰近平均密度，並使用它們計算點的平均相對密度。這個量指示x是否在比它的近鄰更稠密或更稀疏的鄰域內，並取作x的離群點得分（這個是建立在上面的離群點得分基礎上的）。
優缺點：
（1）給出了對象是離群點的定量度量，並且即使數據具有不同的區域也能夠很好的處理；
（2）與基於距離的方法一樣，這些方法必然具有O(m2)的時間復雜度。對於低維數據使用特定的數據結構可以達到O(mlogm)；
（3）參數選擇是困難的。雖然LOF演算法通過觀察不同的k值，然後取得最大離群點得分來處理該問題，但是，仍然需要選擇這些值的上下界。
4、基於聚類的技術
一種利用聚類檢測離群點的方法是丟棄遠離其他簇的小簇。這個方法可以和其他任何聚類技術一起使用，但是需要最小簇大小和小簇與其他簇之間距離的閾值。這種方案對簇個數的選擇高度敏感。使用這個方案很難將離群點得分附加到對象上。一種更系統的方法，首先聚類所有對象，然後評估對象屬於簇的程度（離群點得分）（基於原型的聚類可用離中心點的距離來評估，對具有目標函數的聚類技術該得分反映刪除對象後目標函數的改進（這個可能是計算密集的））。基於聚類的離群點：一個對象是基於聚類的離群點，如果該對象不強屬於任何簇。離群點對初始聚類的影響：如果通過聚類檢測離群點，則由於離群點影響聚類，存在一個問題：結構是否有效。為了處理該問題，可以使用如下方法：對象聚類，刪除離群點，對象再次聚類（這個不能保證產生最優結果）。還有一種更復雜的方法：取一組不能很好的擬合任何簇的特殊對象，這組對象代表潛在的離群點。隨著聚類過程的進展，簇在變化。不再強屬於任何簇的對象被添加到潛在的離群點集合；而當前在該集合中的對象被測試，如果它現在強屬於一個簇，就可以將它從潛在的離群點集合中移除。聚類過程結束時還留在該集合中的點被分類為離群點（這種方法也不能保證產生最優解，甚至不比前面的簡單演算法好，在使用相對距離計算離群點得分時，這個問題特別嚴重）。
對象是否被認為是離群點可能依賴於簇的個數（如k很大時的雜訊簇）。該問題也沒有簡單的答案。一種策略是對於不同的簇個數重復該分析。另一種方法是找出大量小簇，其想法是（1）較小的簇傾向於更加凝聚，（2）如果存在大量小簇時一個對象是離群點，則它多半是一個真正的離群點。不利的一面是一組離群點可能形成小簇而逃避檢測。
優缺點：
（1）基於線性和接近線性復雜度（k均值）的聚類技術來發現離群點可能是高度有效的；
（2）簇的定義通常是離群點的補，因此可能同時發現簇和離群點；
（3） 產生的離群點集和它們的得分可能非常依賴所用的簇的個數和數據中離群點的存在性；
（4）聚類演算法產生的簇的質量對該演算法產生的離群點的質量影響非常大。
新穎性和離群值檢測
離群值檢測：訓練數據包含離群值，即與其他觀測值相距甚遠的觀測值。離群檢測估計器會嘗試擬合訓練數據最集中的區域，忽略異常觀察。
新穎性檢測：訓練數據不受異常值的污染，有興趣檢測新觀察值是否是異常值。該情況下離群值也稱為新穎性。
離群值檢測和新穎性檢測均用於異常檢測，離群值檢測稱為無監督異常檢測，新穎性檢測稱為半監督異常檢測。離群值檢測的情況下，離群值/異常不能形成密集的群集，可假設離群值/異常位於低密度區域；新穎性檢測的情況下，只要新穎性/異常位於訓練數據的低密度區域，就可以形成密集的簇。
通過對玩具數據集進行異常檢測比較異常檢測演算法
數據集中包含一種或兩種模式（高密度區域），以說明演算法處理多模式數據的能力。
對於每個數據集，將生成15%的樣本作為隨機均勻雜訊。該比例是OneClassSVM的nu參數和其他異常值檢測演算法的污染參數提供的值。離群值之間的決策邊界以黑色顯示，但是LOF除外，因為當採用LOF用於離群值檢測時，沒有適用於新數據的預測方法。
OneClassSVM對異常值敏感，對異常值檢測執行的不好。當訓練集不受異常值污染時，此估計器最適合新穎性檢測。即不適用在高維中進行離群值檢測或者不對基礎數據的分布進行任何假設，OneClassSVM在這些情況下可能會根據其超參數給出有用的結果。
covariance EllipticEnvelope（協方差橢圓密度）假定數據是高斯分布並學習一個橢圓。在數據不是單峰時，會退化。此估計器對異常值具有魯棒性。
IsolationFrorest和LocalOutlierFactor針對多模式數據集效果顯著。LOF針對第三種數據集，明顯優於其它三種估計器，該數據集中兩種模式的密度不同。LOF的局部方面，即它僅將一個樣本的異常評分與其鄰居評分作比較，從何體現了該方法的優勢。
針對最後一個均勻分布在超立方體中的數據集，很難說一個樣本比另一個樣本異常得多。除了OneClassSVM有些過擬合外，所有估計器都針對該情況提出不錯的解決方案。針對這種情況，應該仔細觀察樣本的異常分數，性能好的估算器應該為所有樣本分配相似的分數。
使用局部離群因子（LOF）進行離群值檢測
LOF演算法是一種無監督的異常檢測方法，可計算給定數據點相對於其鄰居的局部密度偏差。其中密度遠低於其鄰居的樣本為異常值。
LOF演算法的優勢在於同時考慮了數據集的局部和全局屬性：即使在異常樣本具有不同底層密度的數據集中，仍能保持良好性能。問題不在於樣本有多孤立，而在於樣本相對於周圍鄰域有多孤立。
通常考慮的鄰居數量（1）大於群集必須包含的最小樣本數量，以便其他樣本可以是相對於該群集的局部離散值；（2）小於可能是局部異常值的最大進距采樣數，此類消息通常不可用，採用n_neighbors=20。
具有局部異常值的新穎性檢驗
LOF是一種無監督的異常檢測方法，可計算給定數據點相對於其鄰居的局部密度偏差，密度遠低於其鄰居的樣本為異常值。LOF用於新穎性檢驗時，切勿在訓練集上使用預測、決定函數、實例得分，會導致結果錯誤。只能對新的看不見的數據（不在訓練集中）使用這些方法。
通常考慮鄰居數量（1）大於群集必須包含的最小樣本數，以便其他樣本可以是相對於該群集的局部離群值；（2）小於可能是局部異常值的最大進距采樣數，此類消息通常不可用，採用n_neighbors=20。
隔離林
在高維數據集中執行異常檢測的一種有效方法是使用隨機森林，分離的觀察通過隨機選擇一個函數，隨機選擇所選擇的特徵的最大值和最小值之間的分割值。遞歸分區可用樹結構表示，隔離樣本所需的拆分數量等於從根節點到終止結點的路徑長度。隨機樹的森林中的平均路徑長度是對正態性和決策函數的度量。隨機分區產生的異常路徑明顯較短，因此如果隨機樹森林為特定樣本生成的較短路徑，則該樹代表的值很可能是異常的。
OneClassSVM
無監督的離群值檢測，支持高維分布，基於libsvm
不假定數據分布的任何參數形式，可以更好的對數據的復雜形狀進行建模，能夠捕獲真實的數據結構，難點在於調整核函數寬度參數，以便在數據散布矩陣的形狀和數據過度擬合的風險間取得折中。
協方差橢圓密度
用於檢測高斯分布數據集中的異常值的對象
經驗協方差估計（作為非穩健估計）受到觀測值異質結構的高度影響；魯棒協方差估計能夠集中於數據分布的主要模式，但是它堅持假設數據是高斯分布，產生了對數據結構的某些估計，在一定程度上是准確的。
HBOS單維效果極佳，但是標准差方法的mask 掩碼效應嚴重。例如 數據通常在100以內，但是有兩個異常點，500，1000000。這個演算法就不能檢出500這個異常點。
對比而言，孤立森林理論上更適合大數據的異常檢測，且無掩碼效應。孤立森林確定異常時訓練只用樣本數據。每顆樹樣本數量默認只有256個，默認只用100顆樹。所以理論上25600個樣本就能確定海量數據中的異常點了。
Sklearn的 isolation forest 例子默認是讀入全量數據再采樣。如果配上warm up 選項就能分批放入采樣。
異常檢測的深度學習研究綜述