基于觀測(cè)點(diǎn)機(jī)制的異常點(diǎn)檢測(cè)算法

于萬國(guó)，何玉林，覃薈霖

1）河北民族師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，河北承德 067055；2）深圳大學(xué)計(jì)算機(jī)與軟件學(xué)院，廣東深圳 518060；3）人工智能與數(shù)字經(jīng)濟(jì)廣東省實(shí)驗(yàn)室（深圳），廣東深圳 518107

異常點(diǎn)檢測(cè)亦稱為離群點(diǎn)檢測(cè)，是數(shù)據(jù)挖掘領(lǐng)域的重要研究分支之一［1-2］，可被視為一種無監(jiān)督機(jī)器學(xué)習(xí)方法，其主要任務(wù)是利用統(tǒng)計(jì)分析或機(jī)器學(xué)習(xí)的方法從群體集合中找出與大多數(shù)數(shù)據(jù)存在明顯不同的數(shù)據(jù)（亦稱為異常點(diǎn)或離群點(diǎn)）.迄今尚無被學(xué)術(shù)界或者工業(yè)界廣泛接受的關(guān)于異常點(diǎn)的明確定義，人們僅能根據(jù)具體的應(yīng)用，基于行業(yè)知識(shí)的積累對(duì)本行業(yè)的異常點(diǎn)給出特定的形式化描述，如黑客入侵［3］、銀行欺詐［4］、儀器故障［5］和災(zāi)害預(yù)警［6］等都與異常點(diǎn)檢測(cè)有密切關(guān)系.

如何平衡計(jì)算復(fù)雜度與檢測(cè)精度之間的矛盾是異常點(diǎn)檢測(cè)領(lǐng)域的關(guān)鍵問題，現(xiàn)有的異常點(diǎn)檢測(cè)算法可歸結(jié)為4類：①基于統(tǒng)計(jì)的異常點(diǎn)檢測(cè).此類算法通常基于給定的數(shù)據(jù)集構(gòu)建一個(gè)統(tǒng)計(jì)模型，再計(jì)算樣本點(diǎn)符合該模型的概率，并將概率值偏低的樣本點(diǎn)標(biāo)記為異常點(diǎn)，如基于先驗(yàn)統(tǒng)計(jì)模型［7］、基于直方圖［8］、基于混合模型［9］的異常點(diǎn)檢測(cè)算法等.②基于聚類的異常點(diǎn)檢測(cè).此類算法先對(duì)給定的數(shù)據(jù)集進(jìn)行聚類，再對(duì)樣本量明顯較少的類簇進(jìn)行進(jìn)一步分析，例如計(jì)算類內(nèi)緊湊度和類間分離度，進(jìn)而確定其是否為異常點(diǎn)簇.代表性的工作包括基于k-means 聚類［10］、基于 DBSCAN 聚類［11］和基于層次聚類［12］的異常點(diǎn)檢測(cè)算法等.③基于距離的異常點(diǎn)檢測(cè).若一個(gè)樣本點(diǎn)距離數(shù)據(jù)集中其他樣本點(diǎn)都很遠(yuǎn)，則該樣本點(diǎn)會(huì)被認(rèn)為是異常點(diǎn).此類算法的重點(diǎn)在于設(shè)計(jì)樣本點(diǎn)之間的距離度量，如基于k-近鄰［13］、基于全局k-近鄰［14］和基于k-近鄰圖［15］的異常點(diǎn)檢測(cè)算法等.④基于密度的異常點(diǎn)檢測(cè).該類算法認(rèn)為正常點(diǎn)所處的類簇密度要高于異常點(diǎn)所處的類簇密度，那些具有低密度值的樣本點(diǎn)通常會(huì)被標(biāo)記為異常點(diǎn).密度度量的設(shè)計(jì)是該類算法研究的重點(diǎn).代表性工作包括基于局部異常因子的異常點(diǎn)檢測(cè)（local outlier factor-based outlier detection，LOFOD）［16］、基于局部相關(guān)積分的異常點(diǎn)檢測(cè)［17］和基于局部異常概率的異常點(diǎn)檢測(cè)［18］等.以上算法針對(duì)不同的應(yīng)用場(chǎng)景已取得了良好的實(shí)際表現(xiàn)，然而它們都沒能很好地解決計(jì)算復(fù)雜度與檢測(cè)精度之間的矛盾，即基于統(tǒng)計(jì)的異常點(diǎn)檢測(cè)算法計(jì)算復(fù)雜度一般相對(duì)較低，但檢測(cè)精度不高；另外3種算法雖然識(shí)別精度相對(duì)較高，但計(jì)算復(fù)雜度普遍較高.

本研究提出一種基于觀測(cè)點(diǎn)機(jī)制的異常點(diǎn)檢測(cè)（observation-point mechanism-based outlier detection，OPOD）算法，是隨機(jī)化學(xué)習(xí)（randomization-based learning）策略在異常點(diǎn)檢測(cè)領(lǐng)域中一種新應(yīng)用，通過在原始的數(shù)據(jù)空間隨機(jī)放置觀測(cè)點(diǎn)，再利用觀測(cè)點(diǎn)來辨別原始數(shù)據(jù)集中的正常點(diǎn)和異常點(diǎn).OPOD算法主要包括4個(gè)關(guān)鍵步驟：①在原始數(shù)據(jù)對(duì)應(yīng)的空間中生成若干隨機(jī)觀測(cè)點(diǎn)；②對(duì)于給定的觀測(cè)點(diǎn)，估計(jì)其與所有樣本點(diǎn)距離值的概率密度函數(shù)；③計(jì)算觀測(cè)點(diǎn)與樣本點(diǎn)之間距離值出現(xiàn)的概率；④融合所有觀測(cè)點(diǎn)對(duì)樣本點(diǎn)觀測(cè)的出現(xiàn)概率以完成對(duì)異常點(diǎn)的檢測(cè).基于PyCharm平臺(tái)生成仿真數(shù)據(jù)集，對(duì)OPOD算法的可行性、合理性和有效性進(jìn)行實(shí)驗(yàn)驗(yàn)證，包括OPOD算法通過觀測(cè)點(diǎn)對(duì)原始空間多維樣本點(diǎn)向一維距離空間的轉(zhuǎn)化、OPOD 算法隨觀測(cè)點(diǎn)數(shù)量增加的收斂性，以及與基于近鄰的異常點(diǎn)檢測(cè)（nearest neighbor-based outlier detection，NNOD）算法和基于局部異常因子的異常點(diǎn)檢測(cè)（local outlier factor-based outlier detection，LOFOD）算法的性能對(duì)比.實(shí)驗(yàn)結(jié)果表明，OPOD 算法具備異常點(diǎn)檢測(cè)能力，且能夠收斂，同時(shí)在觀測(cè)點(diǎn)選取合適的條件下，具有比NNOD 和LOFOD 算法更低的時(shí)間復(fù)雜度和更好的異常點(diǎn)檢測(cè)效果.

1 兩種經(jīng)典的異常點(diǎn)檢測(cè)算法

1.1 NNOD算法

對(duì)于任意給定的屬于數(shù)據(jù)集D的樣本點(diǎn)x，令kNN(x)表示其對(duì)應(yīng)的k近鄰集合，則樣本點(diǎn)x的異常度可被定義為

其中，d(x，y)為樣本點(diǎn)x和樣本點(diǎn)y之間的距離.在給定閾值δ＞ 0 條件下，當(dāng)O(x) ＞δ時(shí)，認(rèn)為樣本點(diǎn)x為異常點(diǎn).由式（1）可見，NNOD算法是基于樣本點(diǎn)x與其k近鄰的平均距離來判斷該樣本點(diǎn)是否為異常點(diǎn)：平均距離越小，表明樣本點(diǎn)x的密度越大（即周圍有鄰居），x是異常點(diǎn)的幾率就越??；反之，樣本點(diǎn)x的密度越?。ㄖ車鸁o鄰居），x是異常點(diǎn)的幾率就越大.NNOD算法的異常點(diǎn)檢測(cè)結(jié)果易受k值的影響.

1.2 LOFOD算法

在LOFOD 算法中，每個(gè)樣本點(diǎn)對(duì)應(yīng)一個(gè)局部異常因子（local outlier factor，LOF），計(jì)算式為

其中，LRD(x)和LRD(y)分別為樣本點(diǎn)x和y的局部可達(dá)密度（local reachability density，LRD），

其中，dreach(x，y)為樣本點(diǎn)x到y(tǒng)的可達(dá)距離，

其中，dk(y)為樣本點(diǎn)y與其第k近鄰之間的距離；d(x，y)為樣本點(diǎn)x與y的距離.為解決 NNOD 算法對(duì)近鄰個(gè)數(shù)敏感的缺陷，LOFOD 算法不僅考慮了樣本點(diǎn)x的密度，還考慮了x的近鄰點(diǎn)的密度.當(dāng)LOF(x)＜1 且越接近1 時(shí)，樣本點(diǎn)x越有可能是正常點(diǎn)；當(dāng)LOF(x)＞1 時(shí)，LOF(x)的值越大，樣本點(diǎn)x越有可能是異常點(diǎn).

綜上可見，NNOD 算法和LOFOD 算法都是從數(shù)據(jù)集樣本點(diǎn)的近鄰入手確定樣本點(diǎn)異常情況.由于兩種算法都要掃描數(shù)據(jù)集中的每個(gè)樣本點(diǎn)來確定近鄰，因此，它們時(shí)間復(fù)雜度都為O(N2L).其中，N為數(shù)據(jù)集的規(guī)模；L為數(shù)據(jù)集的維度.

2 基于觀測(cè)點(diǎn)的異常點(diǎn)檢測(cè)算法

本研究提出一種基于觀測(cè)點(diǎn)的異常點(diǎn)檢測(cè)算法.假設(shè)現(xiàn)有包含N個(gè)L維樣本點(diǎn)的數(shù)據(jù)集D={xn|xn=(xn1，xn2，…，xnL)，xnl∈ R，n= 1，2，…，N；l=1，2，…，L}，D中含有若干異常點(diǎn)，則OPOD 算法檢測(cè)步驟如下.

1）生成隨機(jī)觀測(cè)點(diǎn).在數(shù)據(jù)集D對(duì)應(yīng)的樣本空間中隨機(jī)生成M個(gè)觀測(cè)點(diǎn)p1，p2，…，pM，其中，第m(m= 1，2，…，M) 個(gè) 觀 測(cè) 點(diǎn)pm=(pm1，pm2，…，pmL，)，l= 1，2，…，L.觀測(cè)點(diǎn)數(shù)值的選取 應(yīng) 滿 足其 中 ，分別為數(shù)據(jù)集D的第l維數(shù)據(jù)的最小值和最大值.

2）估計(jì)觀測(cè)點(diǎn)與樣本點(diǎn)之間距離的概率密度函數(shù).依次計(jì)算觀測(cè)點(diǎn)pm與樣本點(diǎn)xn之間的距離值，得到距離集合Sm={sm1，sm2，…，smN}，再利用核密度估計(jì)器確定Sm的概率密度函數(shù)［18］，即

其中，hm為窗口寬度，hm＞0.簡(jiǎn)便起見，本研究選用拇指規(guī)則［19-20］確定窗口寬度，即令hm=其中，σm為Sm的標(biāo)準(zhǔn)差.

3）計(jì)算觀測(cè)點(diǎn)與樣本點(diǎn)之間距離的概率值，即基于估計(jì)的概率密度函數(shù)計(jì)算Sm中距離值出現(xiàn)的概率.對(duì)于給定的極小值Δs＞0，對(duì)應(yīng)出現(xiàn)smn值的概率值為

4）識(shí)別異常點(diǎn).對(duì)于給定的觀測(cè)點(diǎn)pm，由式（6）得到其觀察到的數(shù)據(jù)集D中樣本點(diǎn)xn出現(xiàn)的概率給 定 閾 值ξ＞ 0，若則認(rèn)為樣本點(diǎn)xn為pm觀測(cè)到的異常點(diǎn) ， 并 令xn相 對(duì)pm的 異 常 度tmn= 1； 若則認(rèn)為xn為pm觀測(cè)到的正常點(diǎn)，并令tmn= 0.如此類推，可得到全部觀測(cè)點(diǎn)對(duì)應(yīng)數(shù)據(jù)集D的異常點(diǎn)判別矩陣T=(tmn)M×N.若

則將xn標(biāo)記為異常點(diǎn).其中，為向上取整操作.

對(duì)OPOD算法中的關(guān)鍵步驟和參數(shù)選取做以下解釋.

對(duì)于L維數(shù)據(jù)集，在使用M個(gè)觀測(cè)點(diǎn)從N個(gè)樣本點(diǎn)中進(jìn)行異常點(diǎn)檢測(cè)時(shí)，計(jì)算觀測(cè)點(diǎn)與樣本點(diǎn)之間的距離的時(shí)間復(fù)雜度為O(MNL).對(duì)于基于近鄰和區(qū)域密度的異常點(diǎn)檢測(cè)算法NNOD 和LOFOD 而言，執(zhí)行算法往往需要計(jì)算數(shù)據(jù)集中兩樣本之間的距離，時(shí)間復(fù)雜度為O(N2L).因此，當(dāng)M?N時(shí)，OPOD算法的計(jì)算速度將比NNOD和LOFOD算法快得多.

在進(jìn)行觀測(cè)點(diǎn)與樣本點(diǎn)之間距離的概率密度函數(shù)估計(jì)時(shí)，使用拇指規(guī)則確定核密度估計(jì)器的窗口寬度參數(shù)，主要原因是拇指規(guī)則在計(jì)算窗口寬度參數(shù)時(shí)不依賴迭代的參數(shù)優(yōu)化過程，而是以解析解的形式直接給出窗口寬度，可節(jié)省計(jì)算時(shí)間.

在進(jìn)行異常點(diǎn)識(shí)別時(shí)，采用式（8）對(duì)ξ＞0進(jìn)行選取.

g(s)是均值為μm，標(biāo)準(zhǔn)差為σm的正態(tài)分布函數(shù)，μm為樣本集合Sm的均值，s∈Sm.

3 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

實(shí)驗(yàn)所用計(jì)算機(jī)硬件環(huán)境為Intel CPU i5-8300H，主頻為2.3 GHz，內(nèi)存容量為8 Gbyte，硬盤容量為1 Tbyte；軟件環(huán)境為 Python 3.7.6，Anaconda3，64 bits Window 10操作系統(tǒng).

3.1 OPOD算法的可行性驗(yàn)證

基于PyCharm 平臺(tái)，在給定數(shù)據(jù)的規(guī)模和維度條件下，采用sklearn.datasets 的make_blobs 函數(shù) （https：//scikit-learn. org/stable/modules/generated/sklearn. datasets. make_blobs. html#sklearn. datasets.make_blobs）生成2維仿真數(shù)據(jù)集.其中，仿真數(shù)據(jù)集1共有500個(gè)樣本點(diǎn)，仿真數(shù)據(jù)集2共有1 000個(gè)樣本點(diǎn)，二者都含7 個(gè)異常點(diǎn)，如圖1.數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)類別各異且具有各向同性高斯分布，同時(shí)有少量數(shù)據(jù)的類被標(biāo)注為異常點(diǎn).這些仿真數(shù)據(jù)集均已上傳至百度網(wǎng)盤（https：//pan.baidu.com/s/12IQMPM30G9YW5YXft-Zt-g，提取碼：jd3d）.

圖1 采用sklearn.datasets的make_blobs函數(shù)生成2維仿真數(shù)據(jù)集Fig.1 (Color online)Two dimensional synthetic data sets generated with make_blobs function in sklearn.datasets

使用觀測(cè)點(diǎn)機(jī)制進(jìn)行異常點(diǎn)檢測(cè)是通過將多維空間的數(shù)據(jù)點(diǎn)轉(zhuǎn)換成1 維空間的距離點(diǎn)，在1 維空間中估計(jì)距離值的概率分布，進(jìn)而判斷原始數(shù)據(jù)中哪些樣本點(diǎn)為異常點(diǎn).圖2 為使用OPOD 算法對(duì)仿真數(shù)據(jù)集1 和2 進(jìn)行異常單檢測(cè)的結(jié)果.由圖2 可見，異常點(diǎn)對(duì)應(yīng)的距離值均在概率密度函數(shù)的長(zhǎng)尾部分，概率值較小，通過對(duì)多觀測(cè)點(diǎn)的融合能夠輕易地將它們檢測(cè)出來.實(shí)驗(yàn)結(jié)果表明，樣本點(diǎn)在多維原始空間的分布情況可反映到1維距離空間的觀測(cè)點(diǎn)，樣本分布密集區(qū)域?qū)?yīng)的概率密度函數(shù)值較大，而樣本稀疏區(qū)域?qū)?yīng)的概率密度值相對(duì)較小.

圖2 觀測(cè)點(diǎn)與樣本點(diǎn)之間觀測(cè)距離的概率分布Fig.2 (Color online)Probability distributions of observation distances between observation points and data points

3.2 OPOD算法的合理性驗(yàn)證

分別測(cè)試不同規(guī)模和不同維度的數(shù)據(jù)集對(duì)OPOD 算法性能的影響.其中，算法的表現(xiàn)使用異常點(diǎn)召回率(R)衡量，即被正確檢測(cè)的異常點(diǎn)個(gè)數(shù)與全部異常點(diǎn)個(gè)數(shù)的比值.

首先分析數(shù)據(jù)集規(guī)模與OPOD算法中觀測(cè)點(diǎn)數(shù)量之間的關(guān)系.設(shè)L= 40，正常點(diǎn)的個(gè)數(shù)以步長(zhǎng)100 從1 000 增至4 000，共得到31 個(gè)仿真數(shù)據(jù)集.異常點(diǎn)數(shù)量與正常點(diǎn)數(shù)量的比例保持在1∶100.圖3 給出了在不同規(guī)模數(shù)據(jù)集上，隨著觀測(cè)點(diǎn)數(shù)量(M)的增加，OPOD算法的收斂性示意.

圖3 OPOD算法對(duì)不同規(guī)模數(shù)據(jù)集異常點(diǎn)檢測(cè)的收斂性（L = 40）Fig.3 Convergence of OPOD algorithm for outlier detection under different size data sets(L = 40)

圖4 顯示隨著數(shù)據(jù)集規(guī)模的增加，OPOD 算法所需觀測(cè)點(diǎn)數(shù)量逐漸增加直至收斂.這表明對(duì)于給定維度的數(shù)據(jù)集，所需觀測(cè)點(diǎn)數(shù)量并非隨著數(shù)據(jù)集規(guī)模的增大無限增大，而是有上限的.

圖4 數(shù)據(jù)規(guī)模對(duì)OPOD算法觀測(cè)點(diǎn)個(gè)數(shù)的影響Fig.4 Impact of data size on number of observation points in OPOD algorithm

為考察數(shù)據(jù)集維度與OPOD算法觀測(cè)點(diǎn)之間的關(guān)系，設(shè)置N= 1 010.其中，正常點(diǎn)數(shù)個(gè)為1 000，異常點(diǎn)個(gè)數(shù)為10，數(shù)據(jù)維度以步長(zhǎng)1 從1 增至60，得到60 個(gè)仿真數(shù)據(jù)集.圖5 分別給出了數(shù)據(jù)維度L= 30、40、50和60 時(shí)，隨觀測(cè)點(diǎn)數(shù)量的增加OPOD算法的收斂性.圖6 給出了隨著數(shù)據(jù)集維度的增加，OPOD 算法所需觀測(cè)點(diǎn)數(shù)量需求情況.由圖6可見，隨著數(shù)據(jù)集維度的增加，OPOD 算法所需觀測(cè)點(diǎn)數(shù)量總體呈減少趨勢(shì)，表明算法具有處理高維數(shù)據(jù)異常點(diǎn)檢測(cè)問題的潛能，且數(shù)據(jù)維度越高，所需觀測(cè)點(diǎn)數(shù)量越少.該結(jié)果與“維數(shù)災(zāi)”相對(duì)應(yīng)，即數(shù)據(jù)維度越高，數(shù)據(jù)分布越稀疏，因此只需要較少觀測(cè)點(diǎn)就能夠觀測(cè)到數(shù)據(jù)分布的基本情況.

圖5 OPOD算法對(duì)不同維度數(shù)據(jù)集異常點(diǎn)檢測(cè)的收斂性（N = 1 010）Fig.5 Convergence of OPOD algorithm for different data dimensions(N = 1 010)

圖6 數(shù)據(jù)維度對(duì)OPOD算法觀測(cè)點(diǎn)個(gè)數(shù)的影響Fig.6 Impact of data dimension on number of observation points in OPOD algorithm

以上結(jié)果表明，OPOD 算法性隨著觀測(cè)點(diǎn)數(shù)量的增加呈收斂趨勢(shì)，且隨著數(shù)據(jù)規(guī)模的增加，觀測(cè)點(diǎn)數(shù)量逐漸增加；同時(shí)，隨著數(shù)據(jù)維度的增加，觀測(cè)點(diǎn)數(shù)量逐漸減少.

3.3 OPOD算法的有效性驗(yàn)證

為驗(yàn)證OPOD 算法的有效性，本研究對(duì)OPOD算法與兩種經(jīng)典的基于局部異常因子（local outlier factor，LOF）的異常點(diǎn)檢測(cè)算法 NNOD 和LOFOD 算法進(jìn)行仿真實(shí)驗(yàn)，并對(duì)比它們的運(yùn)行時(shí)間、異常點(diǎn)召回率和誤檢率.其中，誤檢率為錯(cuò)誤檢測(cè)的異常點(diǎn)個(gè)數(shù)與檢測(cè)出的異常點(diǎn)個(gè)數(shù)的比值.NNOD算法和LOFOD 算法中，近鄰的確定和LOF 的計(jì)算分別采用PyOD 工具庫(kù)（https：//pyod.readthedocs.io/en/latest/）中 的 pyod.models.knn 和 pyod.models.lof 代 碼實(shí)現(xiàn).

圖 7 和圖 8 對(duì)比了 NNOD、LOFOD 和 OPOD 算法對(duì)不同規(guī)模、不同維度的仿真數(shù)據(jù)集2進(jìn)行檢測(cè)時(shí)的運(yùn)行時(shí)間.結(jié)果發(fā)現(xiàn)，無論是對(duì)于不同規(guī)模的數(shù)據(jù)集，還是不同維度的數(shù)據(jù)集，OPOD 算法的運(yùn)行時(shí)間最少，表明該算法的計(jì)算復(fù)雜度低.

圖7 NNOD、LOFOD和OPOD算法對(duì)不同規(guī)模數(shù)據(jù)集進(jìn)行異常點(diǎn)檢測(cè)的時(shí)間對(duì)比Fig.7 Time comparison among NNOD,LOFOD and OPOD algorithms for different data sizes

圖8 NNOD、LOFOD和OPOD算法對(duì)不同維度數(shù)據(jù)集進(jìn)行異常點(diǎn)檢測(cè)的時(shí)間對(duì)比Fig.8 Time comparison among NNOD,LOFOD and OPOD algorithms for different data dimensions

選用4個(gè)標(biāo)準(zhǔn)UCI數(shù)據(jù)集（https：//archive.ics.uci.edu/ml/datasets.php），固定某一個(gè)類為正常類，再?gòu)钠溆囝愔忻看坞S機(jī)挑選10 個(gè)樣本作為異常點(diǎn)，重復(fù)30次，正常點(diǎn)和異常點(diǎn)的選擇情況見表1.表2和表3分別對(duì)比了OPOD算法和NNOD算法，以及OPOD算法和LOFOD算法的異常點(diǎn)召回率、誤檢率和運(yùn)行時(shí)間.從中可見，OPOD 算法以較低的時(shí)間復(fù)雜度獲得了較高的召回率和較低的誤檢率，表明OPOD算法的有效性.

表1 OPOD、NNOD和LOFOD算法使用的數(shù)據(jù)集Table 1 The data sets used in comparison among OPOD,NNOD and LOFOD algorithms

表2 OPOD和NNOD算法的召回率、誤檢率和運(yùn)行時(shí)間Table 2 The recall (R), false detection rate (F) and run time (t) of OPOD and NNOD algorithms

表3 OPOD和LOFOD算法的召回率、誤檢率和運(yùn)行時(shí)間Table 3 The recall (R), false detection rate (F) and run time (t) of OPOD and LOFOD algorithms

OPOD 算法取得良好異常點(diǎn)檢測(cè)表現(xiàn)的原因是，該算法通過觀測(cè)點(diǎn)將多維的原始數(shù)據(jù)轉(zhuǎn)化成一維的距離數(shù)據(jù)，在某種程度上可以將觀測(cè)點(diǎn)機(jī)制看作是一種特征提?。?1］機(jī)制，恰當(dāng)?shù)漠惓｜c(diǎn)選取能夠保證一維的距離分布正確反映出原始數(shù)據(jù)分布情況.之后在低維空間使用基于統(tǒng)計(jì)的異常點(diǎn)檢測(cè)算法比在高維空間構(gòu)建統(tǒng)計(jì)模型具有更低的計(jì)算復(fù)雜度，且比統(tǒng)計(jì)模型具有更好的適用性.

結(jié) 語

提出一種基于觀測(cè)點(diǎn)機(jī)制的異常點(diǎn)檢測(cè)算法OPOD，通過對(duì)不同維度、不同規(guī)模的仿真數(shù)據(jù)集進(jìn)行測(cè)試，獲得比基于近鄰和局部異常因子的異常點(diǎn)檢測(cè)算法更低的計(jì)算復(fù)雜度和更高的異常點(diǎn)檢測(cè)精度.OPOD 算法通過在原始數(shù)據(jù)空間中隨機(jī)放置觀測(cè)點(diǎn)，并將多維的原始數(shù)據(jù)轉(zhuǎn)換為一維的距離數(shù)據(jù)，再估計(jì)一維距離數(shù)據(jù)的概率密度函數(shù)，進(jìn)而計(jì)算距離值的概率值，從總觀測(cè)點(diǎn)的角度檢測(cè)出異常點(diǎn)數(shù)據(jù).下一步可結(jié)合生成模型理論對(duì)觀測(cè)點(diǎn)的選取機(jī)制進(jìn)行優(yōu)化，并考慮在隨機(jī)樣本劃分［22］框架下設(shè)計(jì)出用于大數(shù)據(jù)異常點(diǎn)檢測(cè)的OPOD 算法.同時(shí)，仍需進(jìn)一步對(duì)OPOD算法的收斂性、觀測(cè)點(diǎn)數(shù)量的選取，以及最優(yōu)觀測(cè)點(diǎn)的確定等方面進(jìn)行理論分析和驗(yàn)證.