基于大數(shù)據(jù)的高效分布式離群點(diǎn)檢測算法

劉建

摘要： 根據(jù)大數(shù)據(jù)的特征即數(shù)據(jù)量大、維數(shù)高，本文提出了基于大數(shù)據(jù)的高效分布式離群點(diǎn)檢測算法。該種算法就是在數(shù)據(jù)處理的初級階段，根據(jù)計算距離的方法將數(shù)據(jù)進(jìn)行精確的計算，并在計算的過程中建立查詢檢測模型，通過模型將數(shù)據(jù)進(jìn)行二次檢測;進(jìn)入離群點(diǎn)檢測的階段，通過大數(shù)據(jù)模型對其結(jié)果進(jìn)行批量的過濾。最后，就在基于距離的數(shù)據(jù)與局部數(shù)據(jù)集驗(yàn)證相結(jié)合的方式去檢驗(yàn)大數(shù)據(jù)的實(shí)效性與精確度。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有算法相對比，基于距離的算法在一定程度上大大提高了計算的精確率。

關(guān)鍵詞：大數(shù)據(jù);分布式;離群點(diǎn)檢測;算法;

中圖分類號：G642? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? 文章編號：1009-3044（2019）03-0014-02

離群點(diǎn)檢測主要就是為了挖掘數(shù)據(jù)，使得相關(guān)的工作更加有效，通常采用這種檢測方法會發(fā)現(xiàn)相關(guān)的特異行為數(shù)據(jù)，這就會提高相關(guān)的工作效率，減少不必要的探尋數(shù)據(jù)的時間。根據(jù)對離群點(diǎn)的具體定義表述為離群點(diǎn)就是對應(yīng)相應(yīng)的觀察點(diǎn)，如果離群點(diǎn)與其他觀測點(diǎn)的偏離較大，那就有理由懷疑是不是由于機(jī)制上的不同而產(chǎn)生的[1]。若是這些偏離的數(shù)據(jù)與不滿足的數(shù)據(jù)統(tǒng)一起來可以取一個名稱也就是離群點(diǎn)，離群點(diǎn)也可以稱為孤立點(diǎn)或者異常點(diǎn)。離群點(diǎn)挖掘也就是離群點(diǎn)檢測，這也是為什么要進(jìn)行數(shù)據(jù)挖掘的原因，一般來說數(shù)據(jù)挖掘是一個非常常見的概念，最近幾年使用的也非常廣泛，但是傳統(tǒng)的方法檢測出來的數(shù)據(jù)總是會產(chǎn)生這樣或者那樣的問題，就使得相關(guān)人員對這種檢測方式產(chǎn)生了質(zhì)疑的態(tài)度，但是這種算法又是必不可少，所以，就需要我們對其進(jìn)行探索，看是否能尋找到更加有效的方式方法。社會上近些年也出現(xiàn)了很多種不同的算法，大眾對其的真實(shí)效果褒貶不一。社會基本上給出了一個一般性的意義就是離群點(diǎn)以及離群點(diǎn)的挖掘方法?；诖髷?shù)據(jù)的高效分布式離群點(diǎn)檢測算法，挖掘點(diǎn)的比例相對來說會比較低。基于大數(shù)據(jù)的高效分布式離群點(diǎn)檢測算法的挖掘方法，雖然能夠解決一些問題，但是參數(shù)的敏感度等方面的東西卻有一些局限性。由于基于大數(shù)據(jù)的高效分布式離群點(diǎn)檢測算法在具體操作中時間的復(fù)雜度低以及聚類精度高，這樣就能將不同類型數(shù)據(jù)聚集在一起，最終目的就是挖掘簇[2]。

1高效分布式離群點(diǎn)檢測算法設(shè)計

1.1 基于距離的離群點(diǎn)計算

一般地，給定一個具有d維屬性的數(shù)據(jù)集P，數(shù)據(jù)集內(nèi)的數(shù)據(jù)點(diǎn)個數(shù)為|P|，對于P內(nèi)任一數(shù)據(jù)點(diǎn)p，p包括d個可度量的屬性值，記作p=<p[0]，P[1]，…，p[d-1]（為方便描述，后文中認(rèn)為數(shù)據(jù)點(diǎn)的各維屬性值均不小于0）[3]，那么點(diǎn)p1、p2之間的距離為

[distp1，p2=i∈0，d-1p2i-p1i2]? ? ? ? ? ? ? ? ?（1）

定義1設(shè)為Q鄰域，任意實(shí)數(shù)Q≥0，數(shù)據(jù)對象為P1的鄰域可以表示為Q（P2-P1 ），則定義為：

Q（P1，P2）={P<I}? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

定義2? Q（P1，P2）離群點(diǎn)。設(shè)定一個正整數(shù)i，如果數(shù)據(jù)點(diǎn)q的r鄰域基數(shù)小于k，則q是Q（P1，P2）離群點(diǎn)。

基于距離的離群點(diǎn)計算，根據(jù)以上的公式的具體論述可以計算出相對來說比較精準(zhǔn)的數(shù)據(jù)結(jié)果，在一定程度上可以提高工作的效率，減少重復(fù)驗(yàn)證結(jié)果的過程。本文采用真實(shí)數(shù)據(jù)進(jìn)行具體的運(yùn)算，以此來檢測新的算法與傳統(tǒng)算法相比是否更加真實(shí)有效，能夠在一定程度上保障檢驗(yàn)效果的合理性，增強(qiáng)其對民眾的說服力。

1.2實(shí)現(xiàn)分布式離群點(diǎn)檢測

如果數(shù)據(jù)集中至少有pct部分對象與對象o的距離大于DT，則對象o是一個基于距離的關(guān)于參數(shù)pct和 DT 的離群點(diǎn)，即DB（pct，DT）-Outlier[4]。這里的定義基本上是針對所以數(shù)據(jù)集的全局離群點(diǎn)。如果k作為用戶所期望的離群點(diǎn)的那個數(shù)相同的話，那么其偏離度就會是最大，假如k個對象作為離群點(diǎn)，檢測思路如下：首先確定k個簇，n個數(shù)據(jù)。然后描述s個離群點(diǎn)使outlierSet =K個相對的離群點(diǎn)集合則賦為空集，采用定義2輸出的簇集合為KCo;當(dāng)OKCo = KCo時可以存放包含著離群點(diǎn)的候選微聚類的集合，根據(jù)計算結(jié)果也就是聚類的信息熵;計算出偏離度也就是Doli最大的對象，或者采取按偏離度降序排列的方式將微聚類內(nèi)的對象表現(xiàn)出來。

然后就依次取出各個元素，要從第一個元素就開始計算，接下來就是計算剩余數(shù)據(jù)集中的信息也就是熵的值，接下來就是判斷信息熵的值是不是在閾值σ內(nèi)，如果算出來的值小于σ，那就說明結(jié)果不包含離群點(diǎn)，這樣就可以排除掉這類的聚類，要不然就可以對應(yīng)出相關(guān)的離群點(diǎn)然后保存在outlierSet內(nèi);

最后輸出在outlierSet 中的s個離群點(diǎn)，然后把可能出現(xiàn)在離群點(diǎn)的聚類中采用基于大數(shù)據(jù)的高效分布式離群點(diǎn)檢測算法，并將離群點(diǎn)放到入outlierSet中。

經(jīng)過對全局、局部離群點(diǎn)的分析，基于分布式離群點(diǎn)檢測算法數(shù)據(jù)實(shí)時反饋，結(jié)合取樣分析數(shù)據(jù)及時調(diào)整相關(guān)數(shù)據(jù)的輸入輸出，實(shí)現(xiàn)基于大數(shù)據(jù)的高效分布式離群點(diǎn)檢測算法的有效運(yùn)行[5]。

2實(shí)驗(yàn)數(shù)據(jù)分析

2.1精準(zhǔn)度檢測

為了檢測上述設(shè)計的基于距離離群點(diǎn)檢測算法是否真實(shí)有效，將其與已有的局部離群點(diǎn)檢測方法進(jìn)行數(shù)據(jù)對比。實(shí)驗(yàn)組選擇基于距離的方法，對比組選擇基于局部的方法，進(jìn)行對比實(shí)驗(yàn)。使用不同的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，先進(jìn)行基于距離方式的實(shí)驗(yàn)計算，將結(jié)果分別記錄，然后再根據(jù)傳統(tǒng)的計算方法進(jìn)行相關(guān)結(jié)果的計算，結(jié)果也需要分別記錄。最后也是最關(guān)鍵的一步就是把記錄下來的兩組數(shù)據(jù)制成表格，對其進(jìn)行對比，清晰的表示出不同方法所產(chǎn)生的不同結(jié)果，具體操作就如表1所示。

從表1的實(shí)驗(yàn)結(jié)果可以看出，根據(jù)不同方式完成的實(shí)驗(yàn)，結(jié)果有明顯的差異，實(shí)驗(yàn)組對應(yīng)不同的數(shù)據(jù)，計算精準(zhǔn)度基本穩(wěn)定在80%到90%左右，而對比組的數(shù)據(jù)計算精準(zhǔn)度則基本穩(wěn)定在70%左右，可以看出實(shí)驗(yàn)組的精準(zhǔn)度相對于對比組提高了10%左右，這也就證明了實(shí)驗(yàn)組數(shù)據(jù)檢測的精準(zhǔn)度要遠(yuǎn)遠(yuǎn)高于對比組。

2.2離群點(diǎn)檢測結(jié)果查詢處理

在第一組實(shí)驗(yàn)的基礎(chǔ)上，為了更加清晰的說明實(shí)驗(yàn)組結(jié)果與對比組結(jié)果的差異，所以進(jìn)行第二組實(shí)驗(yàn)，在第一組精確度結(jié)果的基礎(chǔ)上，再次檢測。實(shí)驗(yàn)時一定要保證實(shí)驗(yàn)數(shù)據(jù)的精準(zhǔn)性，保證數(shù)據(jù)有證可尋，不能憑空捏造。與第一組實(shí)驗(yàn)步驟有類似之處，也需要將相對應(yīng)數(shù)據(jù)結(jié)果分別記錄下來，制成表格，填表格時一定要根據(jù)實(shí)驗(yàn)步驟一步一步填寫，保證數(shù)據(jù)的真實(shí)有效。表格制作完成之后，將實(shí)驗(yàn)組和對比組的內(nèi)容進(jìn)行查詢并二次驗(yàn)證，效果如表2所示。

根據(jù)表2數(shù)據(jù)可以看出，在實(shí)驗(yàn)一的結(jié)果上，進(jìn)行二次試驗(yàn)，結(jié)果顯示實(shí)驗(yàn)組查詢結(jié)果精準(zhǔn)度平均維持在90%以上，對比組則一般維持在75%左右，實(shí)驗(yàn)組相對于對比組而言查詢結(jié)果準(zhǔn)確率提高了15%左右，這一結(jié)果將更有利的說明實(shí)驗(yàn)組所采取的檢測方法，相對于對比組采取的傳統(tǒng)方法產(chǎn)生的實(shí)際效果更好，這就為之后檢測方法的具體改進(jìn)給予了一個科學(xué)性的論證。

3 結(jié)束語

本文通過對基于大數(shù)據(jù)的高效分布式離群點(diǎn)檢測算法的具體分析，對高效分布式離群點(diǎn)檢測算法在實(shí)際工作過程當(dāng)中的利用以及相關(guān)特點(diǎn)進(jìn)行詳細(xì)的論述和實(shí)驗(yàn)的操作，證明了基于大數(shù)據(jù)的高效分布式離群點(diǎn)檢測算法的必要性和實(shí)效性。希望本文的實(shí)驗(yàn)結(jié)果對基于大數(shù)據(jù)的高效分布式離群點(diǎn)檢測算法的進(jìn)一步發(fā)展提供理論上的支持，能夠?yàn)楦咝Х植际诫x群點(diǎn)檢測算法提供一種新的檢測方式，加強(qiáng)相關(guān)數(shù)據(jù)的精確度，減少檢測工作反復(fù)驗(yàn)證的過程。

參考文獻(xiàn)：

[1]? 呂軍暉，周剛，金毅.一種基于時間序列的自適應(yīng)網(wǎng)絡(luò)異常檢測算法[J].北京航空航天大學(xué)學(xué)報， 2009， 35（5）： 636-639.

[2] 魏小濤，黃厚寬，田盛豐.在線自適應(yīng)網(wǎng)絡(luò)異常檢測系統(tǒng)模型與算法[J].計算機(jī)研究與發(fā)展，2010， 47（3）： 485-492.

[3] 李如琦，周媛媛.自適應(yīng)變異粒子群算法及在輸電網(wǎng)規(guī)劃中的應(yīng)用[J].廣東電力， 2008， 21（12）： 18-22.

[4] 薛安榮，鞠時光，何偉華，等.局部離群點(diǎn)挖掘算法研究[J].計算機(jī)學(xué)報，2007，30（ 8）：1455-1463.

[5] 江峰，杜軍威，眭躍飛，等.基于邊界和距離的離群點(diǎn)檢測[J].電子學(xué)報，2010，38（ 3） ：700-705.

【通聯(lián)編輯：光文玲】