基于MARS和概率規劃的離群值檢測算法

王瑞豪，童英華，2+，馮忠嶺

(1.青海師范大學 計算機學院，青海 西寧 810008；2.青海師范大學 省部共建藏語智能信息處理及應用國家重點實驗室，青海 西寧 810008；3.青海師范大學 物理與電子信息學院，青海 西寧 810008)

0 引 言

物聯網(internet of things，IoT)是將分散在世界各地的數百萬個對象、傳感器節點進行連接、通信和數據交換，并使用其傳感器生成大量數據的網絡[1]。IoT已經影響人們日常生活中的許多領域，如城市、家庭、健康部門等[2]，并將對社會產生重大影響。此外，隨著技術的進步，嵌入式傳感器設備的數據收集能力也逐步提高，從而增加了來自物理世界的數據和更多連續的數據流。數據代表了連接網絡世界和物理世界的橋梁[3]。物理世界到數字世界的數據流動將擴展計算機對周圍環境的認識，從而人類將獲得無處不在的服務。新產品和服務的質量很大程度上依賴于物聯網設備所收集的數據質量。

文獻[4-6]表明了數據質量(data quality，DQ)對數據挖掘過程的重要性，以及低DQ對這些過程結果有效性的影響，從而得出應確保DQ和準確性的結論。文獻[7，8]提出了物聯網的許多因素包括部署規模、資源有限和連接中斷正在危及生產數據的質量。DQ中這些偏差的一個主要表現是數據離群值[9-11]。為了避免低DQ所帶來的后果，需要對數據離群值進行處理，以提高數據的質量。

本文提出了一種結合多元回歸MARS模型和概率規劃的多元離群點檢測方法。本方法使用一個多變量自適應回歸樣條曲線MARS模型來擬合具有單一因變量的多個預測因子變量，然后MARS模型的殘差被用作可推廣的、完全貝葉斯概率模型的輸入，以檢測離群值。最后，將該算法成功應用于物聯網數據的離群值分析。

1 相關工作

基于回歸模型與離群值檢測已經有很多研究，主要集中在如何檢測和處理離群值。文獻[12]提出了一種貝葉斯方法，使用回歸模型中的殘差來檢測離群值，利用線性回歸模型中的標準化殘差評估離群值，并利用離群值概率的后驗分布假設非先驗信息。這些后驗概率被建模為學生t分布，以便更好地捕捉分布尾部的外圍值。文獻[13-16]使用離群值檢測方法改進線性回歸模型。本文關注的不是離群值如何影響回歸模型，而是如何基于回歸模型的輸出來檢測離群值。學生化殘差和馬氏距離等技術可用于評估回歸模型數據輸出中可能的離群值。文獻[17]使用幾種常用技術，如學習殘差來檢測離群值以改進回歸模型，文章采用檢測方法自動發現儀器浮標記錄中可能存在的離群值，如颶風，以保護分析結果不受這些罕見事件的影響，即刪除或記錄這些事件，以創建干凈的基線數據集進行分析。結果表明，貝葉斯方法與其它方法如標準化殘差和預測不一致性診斷的結果相似。

2 多元變量離群值檢測方法

離群值是位于主要數據分組之外的某個值，或者不適合某個正常模型的數據點[12]，其中模型可以基于距離、密度、回歸等。檢測和標記離群值的一種簡單方法是提供一個上限或下限閾值，但前提是要了解整個數據集。

在許多情況下，例如檢測欺詐，使用多個變量可以在檢測和調查可能的離群值時提供有價值的信息。與單變量方法相比，使用多變量輸入數據檢測離群值的技術研究較少。研究多元離群值、回歸模型和單變量的一個原因是，在多元回歸的背景下，單變量離群值可能不是極端的，并且在雙變量或單變量分析中，多元離群值可能無法檢測到。在本節中將簡要討論兩種常用的多變量離群值檢測方法，用于發現潛在的外圍數據點。

2.1 馬氏距離

馬氏距離(Mahalanobis distance)考慮了多元分布的數據規模，這些分布表示觀察的概率。馬氏距離與歐幾里德距離相似，只是它沿著不相關的方向標準化了數據[18]。馬氏距離給出了從一個錯誤值到預測變量(自變量)所有觀測值的質心的距離。一個大的距離表示一個觀測值是由預測值定義的空間中的一個離群值。式(1)定義了馬氏距離

(1)

2.2 K-均值聚類

數據空間的劃分有不同的方法，其中一種方法是K-均值聚類[19]。K-均值聚類的目標是最小化數據點到聚類的距離，或者減少聚類內的方差，通過最小化平方誤差函數來實現，如式(2)所示

(2)

式中：J是目標函數，k是簇的數目，n是觀測數據點的數目，xi是i的觀測，cj是簇j的質心。因為K-均值聚類試圖最小化簇內平方和，所以它總是給較大的簇賦予更多的權重。此外，K-均值聚類對數據進行了一些假設，包括以下內容：每個變量分布的方差都是球形的，或者聚類的分布是相似的，每個星團的觀測數量大致相等。如果這些假設中的任何一個不成立，K-均值聚類將不會按預期運行，產生誤導性或不正確的結果。

總之，在上述各種研究離群點檢測方法時都有規范性假設，另一個重要因素是數據分布的形狀。一般來說，大多數常見的離群點檢測技術在正態分布數據上都有很好的表現。鉸鏈函數同樣對數據應用變換函數有助于創建多元正態分布，但變換并不總是有效的，任何結果都必須轉換回原始空間。這些方法的這一弱點可能導致檢測出不正確的離群值，特別是在非正態分布的數據集中。

3 基于MARS回歸模型和概率規劃的多元離群點檢測算法

本節詳細介紹提出的基于MARS回歸模型和概率規劃的多元離群點檢測方法的兩個必要組成部分，即MARS回歸模型和概率模型。3.1節利用MARS模型計算出學生化殘差，以便概率模型使用這些殘差來檢測離群值；3.2節通過貝葉斯推理得出概率規劃的可信區間；3.3節概率模型的實現。

3.1 MARS回歸模型

MARS是一個非參數回歸模型，它解釋了變量之間的非線性及其相互作用[20]。MARS利用鉸鏈函數作為分段線性函數(擬合數據)，并通過組合鉸鏈函數的變量關系而形成的非線性函數。MARS的優點是有利于創建多變量模型，包括鉸鏈函數能夠自動劃分輸入數據，在某種程度上包含輸入數據中離群值的影響和快速預測。此外，自動特征選擇選出最相關的特征，從而在使用模型檢測具有多個變量的離群值時減少噪聲和可能的離群值。MARS執行自動變量選擇，適用于大型數據集，比傳統線性模型更靈活。式(3)描述了使用MARS構建的模型

(3)

式中：ci為常數系數，基函數Bi(x) 可取值為1，也可取值為鉸鏈函數max(0，x-ci) 或max(0，ci-x)。

H=X(XTX)-1XT

(4)

(5)

(6)

其中，H是hat矩陣，它是設計矩陣X在列空間上的正交投影，ε是絕對殘差，σ2是殘差的方差，hii是hat矩陣對角線上的值，t是學生化殘差。本模型利用多變量MARS模型殘差結果來實現數據可能存在的離群值概率。

3.2 概率規劃與貝葉斯推理

概率規劃利用高級語言來創建概率模型并自動求解，本模型結合了概率規劃，用于檢測物聯網數據中的離群值，并實現完整的貝葉斯推理。貝葉斯推理提供了一種將新的證據與先前的信念或假設相結合的方法，通過應用貝葉斯規則來實現，貝葉斯公式如式(7)所示

(7)

在貝葉斯規則中，P(A) 是事件A的先驗概率，P(X) 是X的先驗概率，P(X|A) 是給定事件A的X的相似性，P(A|X) 是后驗概率。

概率規劃作為一種通用的推理技術，能夠建立某一事件或特征的模型，如異常點的檢測，并對預測進行概率推理，從過去的事件中推斷原因，從過去的經驗中學習以改進預測。概率規劃的核心是概率推理，概率模型是用編程語言來實現的。這在一定程度上是因為概率程序被解釋為一種分布，人們可以從中使用工具來詢問有關分布的問題。此外，這些建模語言將隨機事件作為原語合并，如前所述，它們是基于運行環境處理推理。還有其它可用的表示類型語言，如貝葉斯信念網絡和隱馬爾可夫模型。然而，這些方法只是簡單的模擬，而不是機器學習。概率程序類似于可以運行和分析的模擬。

貝葉斯技術為本模型中的不同參數提供了可信區間。可信區間表明，某個值或參數在區間帶內的概率為80%或95%。這比傳統的置信區間更容易解釋，因為傳統的置信區間表明，如果一個實驗重復多次，那么80%或95%的時間值都在這個區間內。此外，與其它評估結果可信度的方法一樣，如果模型是真實的，那么結果周圍的可信區間是可靠的。

3.3 概率模型

為了創建離群點檢測概率模型，從MARS回歸模型殘差中檢測離群值，作為雙重方法的一部分，本文使用了Stan概率編程語言[21]。在Stan上，后驗分布是每個未知參數的充分條件。這是用Hamiltonian Monte Carlo(HMC)和No-U-Turn采樣器(NUTS)完成的，這兩個采樣器都是在Stan中實現的，用于執行統計推斷。模型擬合是通過指定全似然函數和所有未知參數的先驗分布來完成的。下面將詳細介紹所提出的概率模型算法。

算法：概率模型算法

輸入：長度為N的向量y

輸出：最終離群值概率

(1)intN1;

vector[N1] y;

IntN2;

vector[N2]y2; //數據的輸入

(2)real mu;

realsigma; 平均分布

realnu;//模型所需要的參數, 模型的設計參數的輸入

(3)mu～normal(100,100)//mu平均分布

(4)sigma～normal(100,100)//sigma 標準差分布

(5)nu～cauchy(7,5);

for(i in 1:N1){

y[i]～student_t(nu, mu, sigma);

}//離群值的學生t分布

(6)vector[N2] cdf_prob;//概率累計的數據

(7)vector[N2] ccdf_prob;//數據的逆

(8)vector[N2] prob;

for(i in 1:N2){

cdf_prob[i] = student_t_cdf(y2[i], nu, mu, sigma);

ccdf_prob[i] = 1 - cdf_prob[i];

prob[i] = 2*(cdf_prob[i]*ccdf_prob[i]);

}//生成最終的離群值概率

首先聲明了3個與實際輸入相對應的輸入變量，包括用于評估離群值的總體(或樣本)向量、用于查找離群值的檢查值以及每個向量的長度。Stan要估計的未知模型參數是樣本空間與要檢查的輸入值(從中檢測離群值)的平均值和標準偏差，以及學生t分布的自由度。對于離群值的檢測，假設學生t分布的概率，使用均值、標準差和式(8)中定義的自由度，式(8)顯示概率密度函數

(8)

t分布是對稱的鐘形分布[22]，類似于正態分布，峰值為零。不同的是，數據的擴散比標準正態分布的擴散要大。因此，t分布可以更好地捕捉數據集中更寬的尾部，以便更好地描述離群值分布。

在使用Stan概率編程語言時，概率語句用標準符號表示，如y～Normal(μ，σ)。 這意味著變量y模型數據被聲明為具有給定均值和標準差的正態分布，用這個符號來表示本文的概率模型。

對于最終結果，本文計算了相對于大多數觀測值，觀測到更極端值的概率，該概率存儲在離群值概率模型變量prob中，離群值概率的閾值與數據有關。

4 實驗設計與分析

4.1 實驗設計

本文提出的方法包含兩部分，以檢測離群值和可能的異常行為。MARS模型和相應的殘差是物聯網數據中離群值處理的第一步，它解決了數據集的多變量性質。在為每個專業創建了多元回歸模型后，第二步就涉及到使用生成的學生t分布模型殘差來檢測離群值。模型是通過物聯網數據集和特定的數據種類來建立的。

本研究使用R編程語言和MARS的earth包實現來創建和驗證每個模型。分類和回歸訓練CARET包用于創建最終的MARS模型，并選擇10倍交叉驗證來減少訓練模型的過度擬合。在進行10倍交叉驗證中，將90%的數據集用于模型訓練，10%用于測試，從而能夠使用所有的可用數據來密切估計最終模型的預測性能。為了創建完全貝葉斯異常檢測概率模型，本文使用了Stan概率編程語言的rstan。

4.2 實驗結果及討論

本文提出了完整的多變量離群值檢測方法，在本節中將該方法與馬氏距離、K-均值聚類方法進行比較。實驗數據選擇了基于物聯網的霧霾部分數據進行離群值檢測。該實驗數據來源于某地區區委大樓2016年5月3日0點到5月7日下午5點空氣中PM2.5的觀測值，以小時為單位，共計114條數據。

在運行Mahalanobis 距離時，需要確定閾值或距離，將超過閾值或距離的值視為離群值。在比較中，采用降序對數據值相隔距離進行排序。此外，距離的確定是根據數據的種類而確定的，在某種程度上是任意的。計算出的距離在本質上，并不能決定大于該距離的值一定為離群值。可以通過幾種不同的方式使用Mahalanobis距離檢測離群值。其中一種方法使用平均馬氏距離的1.5或3.0倍的值來創建閾值與每個距離進行比較，高于閾值的值被視為離群值。

對于K-均值聚類，關鍵因素是決定數據值聚類的數量。在本文的分析中，使用了肘部方法，它能直觀地描繪集群內方差與集群數量的關系。當方差達到穩定點時，選擇最佳聚類數。

4.2.1 MARS模型分析

圖1給出了MARS模型選出離群值的分析過程。在圖1中，首先通過模型選擇器對數據量進行量化分析，然后計算出數據的累積分布率，通過累積分布率得到了數據值的集群分布圖。經過MARS回歸模型的演算，被標記為27、34、41的數據可能為離群值。MARS模型通過計算出的殘差去檢測離群值，而本文提出的算法可以通過MARS模型計算出的殘差得出數據為離群值的概率。

圖1 MARS模型的分析過程

4.2.2 多變量離群值檢測方法比較

下面將本文提出的概率模型與Mahalanobis距離、K-均值聚類的離群值檢測效果進行比較，結果如圖2所示。

圖2 多變量離群值檢測效果

由圖2可知，K-均值聚類選出的離群值過多并且分散，主要是由于數據值并不是過于的聚集，導致選出的離群值過多，可能存在誤判。本文提出的算法選出的全部離群值與Mahalanobis 距離選出的部分離群值重疊，而K-均值聚類和Mahalanobis 距離選出的離群值只有3個重疊。主要是由于本方法首先通過MARS模型計算出數據的殘差，然后將殘差作為輸入，進而得出數據異常的概率，因此能更準確選出離群值。

4.2.3 可信區間分析

圖3顯示了基于物聯網的霧霾實驗數據中PM2.5的可信區間，在該圖中，黑點表示平均概率，較粗的水平線是80%區間的可信水平，細水平線是95%區間的外部水平。數據的平均概率表明有多大的概率觀察到比該數據值更極端的數據值，概率越低表明很小的概率觀察到比該值更極端的值，則該數據可能為離群值，概率越高，則表示很大概率觀察到比該值更極端的值，更極端的值過多，表明該值也有可能為離群值。所以概率為40%到60%的數據值，處于鐘形分布的中間部分，不太可能為離群值。可信區間的這種分布有助于確定某個值是否為離群值。

圖3 物聯網霧霾數據中PM2.5可信區間

由圖3可知，當間隔位于1%概率閾值左側或右側的值可以被明確地標記為正常值；如果區間超過1%閾值，則該點可視為離群值，反之亦然。例如，被標記為27的數據，該數據與前后數據的間隔過大，超過了1%，并且該數據的較粗水平線過小，可信區間小，所以該值為離群值。具體取決于平均概率與閾值的關系。該信息捕獲了固有的不確定性，可用于幫助創建更好的指標，以了解在給定更多可變數據集的情況下標記離群值，或者相反，在使用可變性較小的數據集標記離群值時設定更嚴格的界限。

5 結束語

提出了一種基于MARS模型和概率規劃的離群值檢測方法，并將該方法應用于物聯網數據的離群值檢測。與其它多變量離群值檢測方法Mahalanobis距離和K-均值聚類相比，本模型返回值是數據為離群值的概率分布，能更準確選出離群值。因此，在給定某些特定數據集時，作為離群值的平均概率可用于確定離群值所需的適當概率閾值。同時，本方法不依賴于設置的距離值閾值，也不需要參數來指定鄰居或集群的數量。此外，本算法對數據分布的影響更加穩健。