海量不確定數據集中離群點快速檢測方法仿真

林 雪

(重慶師范大學涉外商貿學院，重慶 合川 401520)

1 引言

離散點檢測作為數據挖掘中的一項重要技術，可為了解、分析數據提供參考和研究基礎，被廣泛應用于檢測網絡異常事件、物體監測等方面，可有效避免或降低不必要的數據損失[1]，避免對結果造成影響。因此，離散點檢測技術的研究得到廣泛關注。現階段離散點檢測技術主要應用于傳統數據庫中，雖然存在一定的可信性，但在實際收集和處理數據的過程上會受到諸多因素的影響，數據的不確定性會降低檢測速度和檢測準確性。相關研究人員對此展開深入研究，試圖在提高檢測效率的同時，降低計算復雜程度。

曹科研等[2]人提出基于密度的局部異常檢測中，根據不確定數據模型的異常點定義進行數據集局部檢測。在無法精確計算概率的情況下，通過估計局部異常點因子檢測算法(PUDOL)，降低計算復雜程度。仿真證明該方法在計算能力方面性能較強，但檢測精度較低。朱樹才等[3]人針對實際系統中采集的數據流具有不確定性的問題，根據滑動基本窗口采樣(Sliding basic window sampling，SBWS)算法以及高斯過程回歸(Gaussian process regression，GPR)模型特征，提出了基于SBWS—GPR預測模型的不確定性多數據流的異常檢測方法。在時間序列收集的歷史數據集中，引入索引號進行聚類，分析數據集與索引號間的映射關系，通過滑動窗口實時匹配離散點，完成對單數據流的離散點檢測。該方法經過實驗驗證，具有較高的檢測精度，但檢測速度無法達到標準。

由于上述傳統方法無法確保檢測精度，且檢測速度慢、計算復雜度高，因此，提出一種新的海量不確定數據集中離群點快速檢測方法。首先確定出不確定數據集中的離群點，通過OPTICS算法，計算出離群屬性，再引入鄰域密度，構建快速監測模型，充分考慮不確定數據集中離散點的確認，以確保離散點的檢測精度，從而實現離群點的快速準確的檢測。

本文所提出的方法會將數據挖掘和預處理的工作簡化，為后續的研究提供準確的數據支持。

2 不確定數據集中離群點判定

在不確定數據集中，與樣本點行為特征不一致的點，稱為離群點。對其進行判定，要確保數據集中的離群點檢測樣本不會被誤刪，同時保證不確定數據集中離群點檢測的精準度，針對不確定數據集中離群點判定過程如下：

假設數據集中待處理點表示為Q={qj|qj∈R3，j=1，2，…，M}，代表需進行計算和處理的期望點為P={pi|pi∈R3，i=1，2，…，n}，使用F表示期望點集的特征，O={oi|oi∈R3，i=1，2，…，m}則被看作點集Q的離群點，需滿足下列條件：

1)當Q=P∪O時，數據集中任意一點均可被看作離群點；

2)當P∩O=?時，離群點與內點無任何交集，其中一點屬于離群點或者內點；

3)當P(F(pi))=TRUE時，通常數據集中的期望點集的行為特征具有一致性；

4)當?D(Q)=D(P)時，D(x)表示適當觀測數據，對Q與P的特征期望相同。

檢測數據集中離群點的云數據可盡量降低測量誤差等因素造成的數據錯誤，更加接近實際數值，提升了不確定數據集中離群點提取、計算、重構、可視化程度等的準確性及有效程度。

如表1所示，為初始數據集經過處理后得到的不確定數據集，用于描述概率維度對離群點檢測的影響。Tuple用于表示不確定數據集中的標識，Value-1和Value-2代表其中的兩種屬性，Conf用于表示可信程度。

表1 不確定數據集

與判斷確定數據集中離群點不同，在海量不確定數據集中，判斷離群點需采用可能世界模型，其原理是將檢測對象開展成為多個可能世界，再根據相關參數判斷是否在數量閾值范圍內，并對數據集中離散點進行逐個判定。

如表2所示，為檢測對象t1數據集內所有構成可能世界部分的實例，假設t1范圍參數設為d=20，相鄰數據閾值離群點檢測設k=2，在前5項數據中，t1的相鄰數據小于k，在后續數據中，不小于k。因此可看出，僅依據范圍參數和數量閾值無法判定得到的檢測結果是否為離群點，一定要計算被測對象是否為離群點的可能性，作為判定海量不確定數據中離群點的重要依據。

表2 構成的可能事件及概率

假設數據集中的點分別獨立，此時可得

p(w0)=(1-P)×(1-Q)×(1-O)×d

(1)

p(w0)表示離群點w0出現概率值，由表2可知，所有數據概率和不超過1.5，若t1符合檢測要求，則t1為離群點。由此可看出，在進行海量不確定數據離群點檢測時，不僅需要參數和數量閾值，同時還需獲取到概率閾值。經過上述步驟，可準確判定出待檢測的離群點。

3 離群點快速檢測

3.1 局部待檢測離群點定位

要實現離群點的快速檢測，提高檢測速度，對局部待檢測離群點進行定位至關重要。通常運用掃描方式檢測不確定數據集[4]中離群點，但由于密度誤差導致檢測速度過慢。在不確定數據集中每個點都包含了一定的信息向量，密集區域點的信息量大，而離群點屬于無用的信息，去空間分布較小，信息含量少，因此，可設置適當倍數的標準差可作為判定離群點的閾值。

如圖1所示，海量不確定數據集中有2個較為明顯的簇群，現假設C1代表包含離群點的內點簇群，C2表示正常內點簇群，O1及O2均為離群點，采用任意檢測方法，當閾值過大時，僅O1為正確的離群點，O2則被看作內點；當閾值較小時，O1、O2、C1經檢測均為離群點。

圖1 大量不確定數據集中局部離群點

傳統離群點檢測方式需要自行設置判定閾值，該閾值數據為整體判定閾值，隨機可能性大，對檢測結果會產生很大影響，誤差較大[5]。同理，固定閾值判定檢測方法對密集數據點的適應性較差，將不均勻特征考慮其中，在判斷海量大數據集中離群點時進行調整，從而提高檢測速度。

3.2 離群屬性計算

針對海量不確定數據，對局部離群點的定位具有片面性及局限性，還需對立群屬性進行計算。離群點通常僅在數據集中占據一小部分，為了提高計算速度，在確保檢測結果準確程度的同時，還可降低檢測算法的計算量，需使用OPTICS算法完成對初始數據的聚類，通過構建的數據集排序表示數據結構[6]。

在海量數據集中，所占比例較小的離群數據使整體數據集的不確定性增大，根據從數據集中判定出的離群點及不同離群對象與屬性的權值關系[7]，來提高離群點檢測的準確程度。

(2)

式中，Δ(t)為S被分解成D前后信息的變化，該部分減少的數值就是數據集S中被刪除的不確定性，可知，當Δ(t)數值變大時，說明對象t從數據集S中分解刪除后，海量不確定數據集中的“混亂”信息的減少也在增大。

當進行LCOF數值計算時，在利用信息熵的基礎上，使用加權距離反映出不同屬性對數據集中離群點的影響[9]，以此提升檢測速度。在數據集D中選取兩個數據對象，使用p和q表示，設p在屬性ai的數值為fai(p)，則可得到數據對象p和q的加權值表達式為

(3)

其中，wi表示數據對象p在i維中的權值，如果維度i不是離群屬性，此時wi取值為1。

3.3 離群點快速檢測模型構建

結合上述離群屬性的計算結果，通過查詢數據集中各點與領域點集間的距離[10]，對統計結果進行檢測。首先，需計算出查詢點與鄰域點集k的距離平均值，以及整體距離的平均值。然后，計算全部點與其域點集k的距離標準差[11]值。最后，設置一個標準差閾值，用于檢測判定的離群點。

在海量不確定大數據集中，選取任意兩點pi和pj，其坐標值分別表示為(xi，yi，zi)和(xj，yj，zj)，其歐式距離可表示為

(4)

根據式(4)，可得知點pi與其鄰域點集k的平均距離可表示為

(5)

結合式(5)計算結果，則海量不確定數據集中存在n個點時，可得出各點與其鄰域點集k的平均距離數值，表示為

(6)

則海量不確定數據集中的鄰域點集k的方差表現形式為

(7)

將式(6)所得結果代入式(7)中，可得：

(8)

因此，結合式(8)，可求得海量不確定數據集中所有點的鄰域點集k距離整體的標準差值δ，其方程為

(9)

根據離散點判定原理，在一定條件下，如海量不確定隨機變量以正態形式分布，與剩余概率的分布形式近似[12]。因此可判定本組數據滿足正態分布條件。在需檢測的海量不確定數據集中，隨機一點pi的鄰域點k為海量分布向量。

(10)

其中，δ表示標準差。

從圖2可看出其分布曲線。

圖2 數據集中鄰域點k分布曲線

在海量不確定數據集中，內點集和離群點集在密度上存在較大的差距。將鄰域點k的密度特征作為檢測離群點的重要指標，運用對鄰域密度特征進行動態調整，通過標準差閾值完成離群點的檢測。因此，可看出在海量不確定數據集中，鄰域密度直接影響離群點的檢測結果。

綜上所述，完成了海量不確定數據集中離群點快速檢測方法。

4 仿真研究

針對海量不確定數據集離群點快速檢測方法的有效性，使用基于鄰域密度構建的檢測模型，與傳統方法進行對比實驗驗證，利用(up，ud，λ)離群點參數進行檢測，同時海量不確定數據集要符合一定的函數分布規律。本次仿真使用Matlab構成數據，將其固定長度為1000*1000的矩形區域內，分布順序根據不同的實驗需求決定，在不確定數據集中的數據點可信度范圍為(0～1，0)，大體上為均勻分布。

通過對離群屬性的計算，構建基于鄰域密度的快速檢測模型，將離群點參數up設為0.9995，ud設為20.2，λ設為0.8。

如下圖3所示為文獻[2]方法、文獻[3]方法和所提方法的檢測算法參數運行時間，隨著ud數據量增大，所用時間也增加，對比三種不同方法的檢測運算參數運行時間，得到對比結果如圖3所示。

圖3 三種不同方法的檢測運算參數運行時間

分析圖3結果可知，文獻[2]方法的檢測算法運行耗時平均約為22s，當參數ud的值為3.5時，出現最大耗時為30s；文獻[3]方法的檢測算法運行耗時平均約為10s，當參數ud的值為7.5時，出現最大耗時為17s；所提方法的檢測算法運行耗時平均約為5s，當參數ud的值為5時，出現最大耗時為10s；對比三種方法的實驗結果可得，所提方法的運行時間最短，更具優越性。

在對海量不確定數據離群點進行檢測時，如圖4不確定數據集所示，兩條包含10個數據點的傾斜線相交于x軸原點a，b為其中一點，c為斜線至原點最遠的點。可直觀地看出點a和點c具有一定的分布模式，離群概率最高為點b。

圖4 不確定數據集

基于圖4海量不確定數據集，設置初始實驗數據為15萬、25萬、45萬、和65萬。所提方法在數據集中直接進行計算，判斷離群點區域后，采取代表點以及增量數據進行數值計算，從而判斷是否為離群點。圖5記錄了文獻[2]方法、文獻[3]方法與所提檢測方法的離群點判定準確度。

圖5 三種不同方法的離群點判定耗時對比

根據圖5得出，文獻[2]方法無法判定出離群點，文獻[3]方法可以判定出離群點，但判定準確度較低，而所提方法能夠準確的判定出離群點，判定準確度較高。

漏檢點和誤檢點是直接影響檢測精度的兩個重要指標，對文獻[2]方法、文獻[3]方法與所提檢測方法的漏檢點和誤檢點進行測試，得到三種不同方法的檢測精度對比結果如表3所示。

表3 三種不同方法的檢測精度對比

由上述表3的實驗結果可看出，三種不同方法的檢出離群點個數相差不大，文獻[2]方法的漏檢點約為200個，誤檢點約為41個；文獻[3]方法的漏檢點約為310個，誤檢點約為28個；所提方法的漏檢點約為12個，誤檢點約為3個。對比結果可以得出，所提方法的漏檢點和誤檢點遠遠小于文獻[2]方法和文獻[3]方法的漏檢點和誤檢點，說明所提方法的檢測精度最高。

由仿真結果表明，本文提出的方法在離群點檢測時間、準確性及漏檢誤檢方面的優勢非常顯著，本方法具有應用意義。

5 結論

在數據挖掘與數據預處理等領域，離散點檢測具有關鍵作用被高度重視。提出的海量不確定數據集中離散點快速檢測方法，對離散點進行優先判定，使用OPTICS算法進行離群屬性的計算，并結合數據集中鄰域點范圍，完成速檢測模型構建。通過與傳統兩種檢測方法進行對比仿真，得到結果表明，在相同參數情況下，所提方法無論在算法運行時間上，還是在檢測精度上，都更具優越性，實現了海量不確定數據離群點的快速、準確的檢測。本方法為數據挖掘與數據預處理等領域提供了切實有效的處理方法，提高了數據處理的效率，數據的準確性及完整性保證了后續研究的有效性，在實際工作中可被廣泛應用，具有一定的參考價值。