海量不確定數(shù)據(jù)集中離群點(diǎn)快速檢測(cè)方法仿真

林 雪

(重慶師范大學(xué)涉外商貿(mào)學(xué)院，重慶 合川 401520)

1 引言

離散點(diǎn)檢測(cè)作為數(shù)據(jù)挖掘中的一項(xiàng)重要技術(shù)，可為了解、分析數(shù)據(jù)提供參考和研究基礎(chǔ)，被廣泛應(yīng)用于檢測(cè)網(wǎng)絡(luò)異常事件、物體監(jiān)測(cè)等方面，可有效避免或降低不必要的數(shù)據(jù)損失[1]，避免對(duì)結(jié)果造成影響。因此，離散點(diǎn)檢測(cè)技術(shù)的研究得到廣泛關(guān)注。現(xiàn)階段離散點(diǎn)檢測(cè)技術(shù)主要應(yīng)用于傳統(tǒng)數(shù)據(jù)庫(kù)中，雖然存在一定的可信性，但在實(shí)際收集和處理數(shù)據(jù)的過(guò)程上會(huì)受到諸多因素的影響，數(shù)據(jù)的不確定性會(huì)降低檢測(cè)速度和檢測(cè)準(zhǔn)確性。相關(guān)研究人員對(duì)此展開(kāi)深入研究，試圖在提高檢測(cè)效率的同時(shí)，降低計(jì)算復(fù)雜程度。

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

由于上述傳統(tǒng)方法無(wú)法確保檢測(cè)精度，且檢測(cè)速度慢、計(jì)算復(fù)雜度高，因此，提出一種新的海量不確定數(shù)據(jù)集中離群點(diǎn)快速檢測(cè)方法。首先確定出不確定數(shù)據(jù)集中的離群點(diǎn)，通過(guò)OPTICS算法，計(jì)算出離群屬性，再引入鄰域密度，構(gòu)建快速監(jiān)測(cè)模型，充分考慮不確定數(shù)據(jù)集中離散點(diǎn)的確認(rèn)，以確保離散點(diǎn)的檢測(cè)精度，從而實(shí)現(xiàn)離群點(diǎn)的快速準(zhǔn)確的檢測(cè)。

本文所提出的方法會(huì)將數(shù)據(jù)挖掘和預(yù)處理的工作簡(jiǎn)化，為后續(xù)的研究提供準(zhǔn)確的數(shù)據(jù)支持。

2 不確定數(shù)據(jù)集中離群點(diǎn)判定

在不確定數(shù)據(jù)集中，與樣本點(diǎn)行為特征不一致的點(diǎn)，稱為離群點(diǎn)。對(duì)其進(jìn)行判定，要確保數(shù)據(jù)集中的離群點(diǎn)檢測(cè)樣本不會(huì)被誤刪，同時(shí)保證不確定數(shù)據(jù)集中離群點(diǎn)檢測(cè)的精準(zhǔn)度，針對(duì)不確定數(shù)據(jù)集中離群點(diǎn)判定過(guò)程如下：

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

1)當(dāng)Q=P∪O時(shí)，數(shù)據(jù)集中任意一點(diǎn)均可被看作離群點(diǎn)；

2)當(dāng)P∩O=?時(shí)，離群點(diǎn)與內(nèi)點(diǎn)無(wú)任何交集，其中一點(diǎn)屬于離群點(diǎn)或者內(nèi)點(diǎn)；

3)當(dāng)P(F(pi))=TRUE時(shí)，通常數(shù)據(jù)集中的期望點(diǎn)集的行為特征具有一致性；

4)當(dāng)?D(Q)=D(P)時(shí)，D(x)表示適當(dāng)觀測(cè)數(shù)據(jù)，對(duì)Q與P的特征期望相同。

檢測(cè)數(shù)據(jù)集中離群點(diǎn)的云數(shù)據(jù)可盡量降低測(cè)量誤差等因素造成的數(shù)據(jù)錯(cuò)誤，更加接近實(shí)際數(shù)值，提升了不確定數(shù)據(jù)集中離群點(diǎn)提取、計(jì)算、重構(gòu)、可視化程度等的準(zhǔn)確性及有效程度。

如表1所示，為初始數(shù)據(jù)集經(jīng)過(guò)處理后得到的不確定數(shù)據(jù)集，用于描述概率維度對(duì)離群點(diǎn)檢測(cè)的影響。Tuple用于表示不確定數(shù)據(jù)集中的標(biāo)識(shí)，Value-1和Value-2代表其中的兩種屬性，Conf用于表示可信程度。

表1 不確定數(shù)據(jù)集

與判斷確定數(shù)據(jù)集中離群點(diǎn)不同，在海量不確定數(shù)據(jù)集中，判斷離群點(diǎn)需采用可能世界模型，其原理是將檢測(cè)對(duì)象開(kāi)展成為多個(gè)可能世界，再根據(jù)相關(guān)參數(shù)判斷是否在數(shù)量閾值范圍內(nèi)，并對(duì)數(shù)據(jù)集中離散點(diǎn)進(jìn)行逐個(gè)判定。

如表2所示，為檢測(cè)對(duì)象t1數(shù)據(jù)集內(nèi)所有構(gòu)成可能世界部分的實(shí)例，假設(shè)t1范圍參數(shù)設(shè)為d=20，相鄰數(shù)據(jù)閾值離群點(diǎn)檢測(cè)設(shè)k=2，在前5項(xiàng)數(shù)據(jù)中，t1的相鄰數(shù)據(jù)小于k，在后續(xù)數(shù)據(jù)中，不小于k。因此可看出，僅依據(jù)范圍參數(shù)和數(shù)量閾值無(wú)法判定得到的檢測(cè)結(jié)果是否為離群點(diǎn)，一定要計(jì)算被測(cè)對(duì)象是否為離群點(diǎn)的可能性，作為判定海量不確定數(shù)據(jù)中離群點(diǎn)的重要依據(jù)。

表2 構(gòu)成的可能事件及概率

假設(shè)數(shù)據(jù)集中的點(diǎn)分別獨(dú)立，此時(shí)可得

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

(1)

p(w0)表示離群點(diǎn)w0出現(xiàn)概率值，由表2可知，所有數(shù)據(jù)概率和不超過(guò)1.5，若t1符合檢測(cè)要求，則t1為離群點(diǎn)。由此可看出，在進(jìn)行海量不確定數(shù)據(jù)離群點(diǎn)檢測(cè)時(shí)，不僅需要參數(shù)和數(shù)量閾值，同時(shí)還需獲取到概率閾值。經(jīng)過(guò)上述步驟，可準(zhǔn)確判定出待檢測(cè)的離群點(diǎn)。

3 離群點(diǎn)快速檢測(cè)

3.1 局部待檢測(cè)離群點(diǎn)定位

要實(shí)現(xiàn)離群點(diǎn)的快速檢測(cè)，提高檢測(cè)速度，對(duì)局部待檢測(cè)離群點(diǎn)進(jìn)行定位至關(guān)重要。通常運(yùn)用掃描方式檢測(cè)不確定數(shù)據(jù)集[4]中離群點(diǎn)，但由于密度誤差導(dǎo)致檢測(cè)速度過(guò)慢。在不確定數(shù)據(jù)集中每個(gè)點(diǎn)都包含了一定的信息向量，密集區(qū)域點(diǎn)的信息量大，而離群點(diǎn)屬于無(wú)用的信息，去空間分布較小，信息含量少，因此，可設(shè)置適當(dāng)倍數(shù)的標(biāo)準(zhǔn)差可作為判定離群點(diǎn)的閾值。

如圖1所示，海量不確定數(shù)據(jù)集中有2個(gè)較為明顯的簇群，現(xiàn)假設(shè)C1代表包含離群點(diǎn)的內(nèi)點(diǎn)簇群，C2表示正常內(nèi)點(diǎn)簇群，O1及O2均為離群點(diǎn)，采用任意檢測(cè)方法，當(dāng)閾值過(guò)大時(shí)，僅O1為正確的離群點(diǎn)，O2則被看作內(nèi)點(diǎn)；當(dāng)閾值較小時(shí)，O1、O2、C1經(jīng)檢測(cè)均為離群點(diǎn)。

圖1 大量不確定數(shù)據(jù)集中局部離群點(diǎn)

傳統(tǒng)離群點(diǎn)檢測(cè)方式需要自行設(shè)置判定閾值，該閾值數(shù)據(jù)為整體判定閾值，隨機(jī)可能性大，對(duì)檢測(cè)結(jié)果會(huì)產(chǎn)生很大影響，誤差較大[5]。同理，固定閾值判定檢測(cè)方法對(duì)密集數(shù)據(jù)點(diǎn)的適應(yīng)性較差，將不均勻特征考慮其中，在判斷海量大數(shù)據(jù)集中離群點(diǎn)時(shí)進(jìn)行調(diào)整，從而提高檢測(cè)速度。

3.2 離群屬性計(jì)算

針對(duì)海量不確定數(shù)據(jù)，對(duì)局部離群點(diǎn)的定位具有片面性及局限性，還需對(duì)立群屬性進(jìn)行計(jì)算。離群點(diǎn)通常僅在數(shù)據(jù)集中占據(jù)一小部分，為了提高計(jì)算速度，在確保檢測(cè)結(jié)果準(zhǔn)確程度的同時(shí)，還可降低檢測(cè)算法的計(jì)算量，需使用OPTICS算法完成對(duì)初始數(shù)據(jù)的聚類，通過(guò)構(gòu)建的數(shù)據(jù)集排序表示數(shù)據(jù)結(jié)構(gòu)[6]。

在海量數(shù)據(jù)集中，所占比例較小的離群數(shù)據(jù)使整體數(shù)據(jù)集的不確定性增大，根據(jù)從數(shù)據(jù)集中判定出的離群點(diǎn)及不同離群對(duì)象與屬性的權(quán)值關(guān)系[7]，來(lái)提高離群點(diǎn)檢測(cè)的準(zhǔn)確程度。

(2)

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

當(dāng)進(jìn)行LCOF數(shù)值計(jì)算時(shí)，在利用信息熵的基礎(chǔ)上，使用加權(quán)距離反映出不同屬性對(duì)數(shù)據(jù)集中離群點(diǎn)的影響[9]，以此提升檢測(cè)速度。在數(shù)據(jù)集D中選取兩個(gè)數(shù)據(jù)對(duì)象，使用p和q表示，設(shè)p在屬性ai的數(shù)值為fai(p)，則可得到數(shù)據(jù)對(duì)象p和q的加權(quán)值表達(dá)式為

(3)

其中，wi表示數(shù)據(jù)對(duì)象p在i維中的權(quán)值，如果維度i不是離群屬性，此時(shí)wi取值為1。

3.3 離群點(diǎn)快速檢測(cè)模型構(gòu)建

結(jié)合上述離群屬性的計(jì)算結(jié)果，通過(guò)查詢數(shù)據(jù)集中各點(diǎn)與領(lǐng)域點(diǎn)集間的距離[10]，對(duì)統(tǒng)計(jì)結(jié)果進(jìn)行檢測(cè)。首先，需計(jì)算出查詢點(diǎn)與鄰域點(diǎn)集k的距離平均值，以及整體距離的平均值。然后，計(jì)算全部點(diǎn)與其域點(diǎn)集k的距離標(biāo)準(zhǔn)差[11]值。最后，設(shè)置一個(gè)標(biāo)準(zhǔn)差閾值，用于檢測(cè)判定的離群點(diǎn)。

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

(4)

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

(5)

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

(6)

則海量不確定數(shù)據(jù)集中的鄰域點(diǎn)集k的方差表現(xiàn)形式為

(7)

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

(8)

因此，結(jié)合式(8)，可求得海量不確定數(shù)據(jù)集中所有點(diǎn)的鄰域點(diǎn)集k距離整體的標(biāo)準(zhǔn)差值δ，其方程為

(9)

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

(10)

其中，δ表示標(biāo)準(zhǔn)差。

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

圖2 數(shù)據(jù)集中鄰域點(diǎn)k分布曲線

在海量不確定數(shù)據(jù)集中，內(nèi)點(diǎn)集和離群點(diǎn)集在密度上存在較大的差距。將鄰域點(diǎn)k的密度特征作為檢測(cè)離群點(diǎn)的重要指標(biāo)，運(yùn)用對(duì)鄰域密度特征進(jìn)行動(dòng)態(tài)調(diào)整，通過(guò)標(biāo)準(zhǔn)差閾值完成離群點(diǎn)的檢測(cè)。因此，可看出在海量不確定數(shù)據(jù)集中，鄰域密度直接影響離群點(diǎn)的檢測(cè)結(jié)果。

綜上所述，完成了海量不確定數(shù)據(jù)集中離群點(diǎn)快速檢測(cè)方法。

4 仿真研究

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

通過(guò)對(duì)離群屬性的計(jì)算，構(gòu)建基于鄰域密度的快速檢測(cè)模型，將離群點(diǎn)參數(shù)up設(shè)為0.9995，ud設(shè)為20.2，λ設(shè)為0.8。

如下圖3所示為文獻(xiàn)[2]方法、文獻(xiàn)[3]方法和所提方法的檢測(cè)算法參數(shù)運(yùn)行時(shí)間，隨著ud數(shù)據(jù)量增大，所用時(shí)間也增加，對(duì)比三種不同方法的檢測(cè)運(yùn)算參數(shù)運(yùn)行時(shí)間，得到對(duì)比結(jié)果如圖3所示。

圖3 三種不同方法的檢測(cè)運(yùn)算參數(shù)運(yùn)行時(shí)間

分析圖3結(jié)果可知，文獻(xiàn)[2]方法的檢測(cè)算法運(yùn)行耗時(shí)平均約為22s，當(dāng)參數(shù)ud的值為3.5時(shí)，出現(xiàn)最大耗時(shí)為30s；文獻(xiàn)[3]方法的檢測(cè)算法運(yùn)行耗時(shí)平均約為10s，當(dāng)參數(shù)ud的值為7.5時(shí)，出現(xiàn)最大耗時(shí)為17s；所提方法的檢測(cè)算法運(yùn)行耗時(shí)平均約為5s，當(dāng)參數(shù)ud的值為5時(shí)，出現(xiàn)最大耗時(shí)為10s；對(duì)比三種方法的實(shí)驗(yàn)結(jié)果可得，所提方法的運(yùn)行時(shí)間最短，更具優(yōu)越性。

在對(duì)海量不確定數(shù)據(jù)離群點(diǎn)進(jìn)行檢測(cè)時(shí)，如圖4不確定數(shù)據(jù)集所示，兩條包含10個(gè)數(shù)據(jù)點(diǎn)的傾斜線相交于x軸原點(diǎn)a，b為其中一點(diǎn)，c為斜線至原點(diǎn)最遠(yuǎn)的點(diǎn)?？芍庇^地看出點(diǎn)a和點(diǎn)c具有一定的分布模式，離群概率最高為點(diǎn)b。

圖4 不確定數(shù)據(jù)集

基于圖4海量不確定數(shù)據(jù)集，設(shè)置初始實(shí)驗(yàn)數(shù)據(jù)為15萬(wàn)、25萬(wàn)、45萬(wàn)、和65萬(wàn)。所提方法在數(shù)據(jù)集中直接進(jìn)行計(jì)算，判斷離群點(diǎn)區(qū)域后，采取代表點(diǎn)以及增量數(shù)據(jù)進(jìn)行數(shù)值計(jì)算，從而判斷是否為離群點(diǎn)。圖5記錄了文獻(xiàn)[2]方法、文獻(xiàn)[3]方法與所提檢測(cè)方法的離群點(diǎn)判定準(zhǔn)確度。

圖5 三種不同方法的離群點(diǎn)判定耗時(shí)對(duì)比

根據(jù)圖5得出，文獻(xiàn)[2]方法無(wú)法判定出離群點(diǎn)，文獻(xiàn)[3]方法可以判定出離群點(diǎn)，但判定準(zhǔn)確度較低，而所提方法能夠準(zhǔn)確的判定出離群點(diǎn)，判定準(zhǔn)確度較高。

漏檢點(diǎn)和誤檢點(diǎn)是直接影響檢測(cè)精度的兩個(gè)重要指標(biāo)，對(duì)文獻(xiàn)[2]方法、文獻(xiàn)[3]方法與所提檢測(cè)方法的漏檢點(diǎn)和誤檢點(diǎn)進(jìn)行測(cè)試，得到三種不同方法的檢測(cè)精度對(duì)比結(jié)果如表3所示。

表3 三種不同方法的檢測(cè)精度對(duì)比

由上述表3的實(shí)驗(yàn)結(jié)果可看出，三種不同方法的檢出離群點(diǎn)個(gè)數(shù)相差不大，文獻(xiàn)[2]方法的漏檢點(diǎn)約為200個(gè)，誤檢點(diǎn)約為41個(gè)；文獻(xiàn)[3]方法的漏檢點(diǎn)約為310個(gè)，誤檢點(diǎn)約為28個(gè)；所提方法的漏檢點(diǎn)約為12個(gè)，誤檢點(diǎn)約為3個(gè)。對(duì)比結(jié)果可以得出，所提方法的漏檢點(diǎn)和誤檢點(diǎn)遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[2]方法和文獻(xiàn)[3]方法的漏檢點(diǎn)和誤檢點(diǎn)，說(shuō)明所提方法的檢測(cè)精度最高。

由仿真結(jié)果表明，本文提出的方法在離群點(diǎn)檢測(cè)時(shí)間、準(zhǔn)確性及漏檢誤檢方面的優(yōu)勢(shì)非常顯著，本方法具有應(yīng)用意義。

5 結(jié)論

在數(shù)據(jù)挖掘與數(shù)據(jù)預(yù)處理等領(lǐng)域，離散點(diǎn)檢測(cè)具有關(guān)鍵作用被高度重視。提出的海量不確定數(shù)據(jù)集中離散點(diǎn)快速檢測(cè)方法，對(duì)離散點(diǎn)進(jìn)行優(yōu)先判定，使用OPTICS算法進(jìn)行離群屬性的計(jì)算，并結(jié)合數(shù)據(jù)集中鄰域點(diǎn)范圍，完成速檢測(cè)模型構(gòu)建。通過(guò)與傳統(tǒng)兩種檢測(cè)方法進(jìn)行對(duì)比仿真，得到結(jié)果表明，在相同參數(shù)情況下，所提方法無(wú)論在算法運(yùn)行時(shí)間上，還是在檢測(cè)精度上，都更具優(yōu)越性，實(shí)現(xiàn)了海量不確定數(shù)據(jù)離群點(diǎn)的快速、準(zhǔn)確的檢測(cè)。本方法為數(shù)據(jù)挖掘與數(shù)據(jù)預(yù)處理等領(lǐng)域提供了切實(shí)有效的處理方法，提高了數(shù)據(jù)處理的效率，數(shù)據(jù)的準(zhǔn)確性及完整性保證了后續(xù)研究的有效性，在實(shí)際工作中可被廣泛應(yīng)用，具有一定的參考價(jià)值。