基于網(wǎng)格劃分的高維大數(shù)據(jù)集離群點(diǎn)檢測(cè)算法研究

趙伯鑫

（河北軟件職業(yè)技術(shù)學(xué)院，河北保定071000）

1 引言

由于基于統(tǒng)計(jì)分析、密度以及偏差等所實(shí)施的離群點(diǎn)檢測(cè)方式，都存在著一定的不足，像對(duì)于用戶預(yù)先設(shè)置參數(shù)過于依賴或者檢測(cè)精準(zhǔn)度不高等，需要進(jìn)行改進(jìn)，對(duì)該種檢測(cè)算法發(fā)展與推廣形成了直接阻礙。在此種背景下，大數(shù)據(jù)和高維空間集中離群點(diǎn)檢測(cè)為離群點(diǎn)檢測(cè)開辟出了新的發(fā)展方向，對(duì)高維空間特性以及高維空間大數(shù)據(jù)集離群點(diǎn)高效檢測(cè)等內(nèi)容研究，已經(jīng)成為業(yè)界學(xué)者關(guān)注的主要課題，對(duì)于離群點(diǎn)檢測(cè)發(fā)展有著較為突出的現(xiàn)實(shí)意義。

2 網(wǎng)格劃分方式

網(wǎng)格單元?jiǎng)澐质谴朔N離群點(diǎn)檢測(cè)算法展開的關(guān)鍵，通常相關(guān)人員會(huì)按照高維空間維度，實(shí)施等距離單元格劃分。此種方式雖然具有一定優(yōu)勢(shì)，但也有著不可忽視的問題：第一，此種方式劃分所得到的網(wǎng)格單元數(shù)量，由于和數(shù)據(jù)集維度存在著指數(shù)級(jí)相關(guān)的聯(lián)系，所以其與高維大數(shù)據(jù)集空間劃分需求存在著一定出入；第二，因?yàn)榫S度距離數(shù)值是有關(guān)人員事先進(jìn)行設(shè)定的，且其與檢測(cè)算法開展有著直接關(guān)聯(lián)，所以如果數(shù)值發(fā)生相應(yīng)變化，很有可能就會(huì)對(duì)最終檢測(cè)計(jì)算結(jié)果產(chǎn)生不良影響[1]。其中，若距離數(shù)值設(shè)置過大，則可能會(huì)出現(xiàn)非邊界網(wǎng)格單元被忽略或被刪除的情況，會(huì)使離群點(diǎn)出現(xiàn)丟失的狀況；而如果數(shù)值設(shè)置過小，則會(huì)直接網(wǎng)格單元計(jì)算量，且可能會(huì)造成聚類點(diǎn)無法被完全檢測(cè)的情況。因此有學(xué)者提出，在不同維中實(shí)施不同間隔的劃分方式，此種方式會(huì)按照空間維實(shí)際情況，合理進(jìn)行間隔距離設(shè)置，可以有效解決等距離劃分所存在的各項(xiàng)問題，能夠有效提高算法落實(shí)效率，是目前較為認(rèn)可的一種網(wǎng)格劃分方式。

3 以網(wǎng)絡(luò)劃分為基礎(chǔ)的高維大數(shù)據(jù)集離群點(diǎn)檢測(cè)算法

3.1 算法流程和描述

3.1.1 算法流程

3.1.1.1 數(shù)據(jù)集預(yù)處理

在數(shù)據(jù)集預(yù)處理階段之中，主要分為過濾以及掃描兩部分內(nèi)容。此階段主要負(fù)責(zé)進(jìn)行數(shù)據(jù)集讀入和構(gòu)建動(dòng)態(tài)哈希表，會(huì)將數(shù)據(jù)集存儲(chǔ)到物理內(nèi)存之中。當(dāng)對(duì)讀入數(shù)據(jù)集實(shí)施掃描時(shí)，能夠完成所有數(shù)據(jù)點(diǎn)映射任務(wù)，每個(gè)維度的數(shù)據(jù)點(diǎn)都會(huì)映射到與之相對(duì)的網(wǎng)格單元之內(nèi)，且可以借助哈希表儲(chǔ)存結(jié)果，實(shí)現(xiàn)對(duì)輸入數(shù)據(jù)信息的動(dòng)態(tài)化讀入[2]。此種算法可以實(shí)現(xiàn)對(duì)所有網(wǎng)格單元數(shù)據(jù)點(diǎn)數(shù)的實(shí)時(shí)計(jì)算，且可以對(duì)數(shù)據(jù)計(jì)算準(zhǔn)確度進(jìn)行保證，相關(guān)人員會(huì)按照事先所設(shè)定的閥值完成對(duì)網(wǎng)格單元類型的判斷工作，可以在最短時(shí)間內(nèi)精準(zhǔn)判斷出網(wǎng)格單元的類型，并完成對(duì)稠密網(wǎng)格單元的處理，確保非稠密網(wǎng)格單元能夠出現(xiàn)在候選離群點(diǎn)之內(nèi)，以完成對(duì)剩余網(wǎng)格單元數(shù)量的計(jì)算，以保證算法有效性。

在具體進(jìn)行處理過程中，①可以隨機(jī)對(duì)數(shù)據(jù)子空間中的未訪問點(diǎn)進(jìn)行挑選，并按照事先所設(shè)定的維度間隔距離，對(duì)該點(diǎn)所在網(wǎng)格單元類型進(jìn)行判斷；②完成哈希函數(shù)構(gòu)建，并確保所有網(wǎng)格單元信息能夠準(zhǔn)確、完整的體現(xiàn)在哈希表之中，并完成對(duì)網(wǎng)格單元中所有數(shù)據(jù)點(diǎn)數(shù)的計(jì)算，以便按照預(yù)先設(shè)定的數(shù)值，完成對(duì)網(wǎng)格單元類型評(píng)斷；③對(duì)哈希表中所有標(biāo)記為稠密型網(wǎng)格單元實(shí)施檢測(cè)，確定其周邊單元網(wǎng)格類型，并做好標(biāo)記、記錄；④要對(duì)上述步驟中標(biāo)記為稠密類型的網(wǎng)格單元進(jìn)行統(tǒng)一處理，并要對(duì)其中非邊界網(wǎng)格單元聚類點(diǎn)進(jìn)行刪除，且要將刪除之后剩余的單元網(wǎng)格歸入到離群點(diǎn)集之內(nèi)；⑤反復(fù)執(zhí)行上述步驟，直至所有數(shù)據(jù)集點(diǎn)都映射到哈希表之后，再展開對(duì)數(shù)據(jù)空間中所有非邊界網(wǎng)格聚類點(diǎn)與聚類區(qū)域的處理，以便在處理之后實(shí)施后期高效化計(jì)算。

3.1.1.2 離群點(diǎn)發(fā)現(xiàn)和檢測(cè)

在離群點(diǎn)發(fā)現(xiàn)和檢測(cè)階段，檢測(cè)算法需要重點(diǎn)負(fù)責(zé)對(duì)上一階段的數(shù)據(jù)進(jìn)行整理，并要對(duì)候選離群點(diǎn)集展開局部偏離因子的計(jì)算。同時(shí)要借助空間局部偏離因子算法，對(duì)此算法執(zhí)行過程進(jìn)行改進(jìn)與優(yōu)化，要展開對(duì)篩選后候選離群點(diǎn)集的計(jì)算，進(jìn)而找到最高值，并將其視作待挖掘的離群點(diǎn)目標(biāo)，以為后續(xù)工作開展奠定良好基礎(chǔ)。

3.1.2 算法描述

在執(zhí)行過程中，①輸入對(duì)象，像D=｛X1,X2,…,Xn｝以及區(qū)分網(wǎng)格單元類型參數(shù)值等；②輸出對(duì)象，即數(shù)據(jù)集中所存在的空間離群點(diǎn)集。在此過程中，首先需要對(duì)數(shù)據(jù)集進(jìn)行第一次描述，要在維中取出相應(yīng)的數(shù)據(jù)點(diǎn)數(shù)值，并會(huì)將其按照相應(yīng)維度實(shí)施排列，且會(huì)完成每一維度的等分間隔計(jì)算；其次會(huì)進(jìn)行第二次掃描，會(huì)對(duì)所有維度中的數(shù)據(jù)點(diǎn)所屬網(wǎng)格單元進(jìn)行計(jì)算，并構(gòu)建起哈希函數(shù)，以保證能夠?qū)⑺芯S度內(nèi)的網(wǎng)格單元映射到哈希表之內(nèi)；再次對(duì)哈希表進(jìn)行掃描，以完成對(duì)邊界單元網(wǎng)格的判斷，確保非邊界網(wǎng)格單元以及邊界單元所包圍的聚類點(diǎn)可以得到及時(shí)處理；最后要按照廣度優(yōu)先原則，對(duì)哈希表進(jìn)行掃描并完成對(duì)集合對(duì)象的計(jì)算，同時(shí)要按照所設(shè)定的參數(shù)，選出最終的輸出結(jié)果[3]。

3.2 算法性能分析

此種離群點(diǎn)檢測(cè)方式，會(huì)先借助網(wǎng)格劃分方式，完成對(duì)離群點(diǎn)網(wǎng)格的過濾與劃分，會(huì)有效減少后續(xù)檢測(cè)以及篩選工作量，更加便于對(duì)候選離群點(diǎn)集實(shí)施檢測(cè)，可以選取出更多與相應(yīng)條件相滿足的待挖掘離群點(diǎn)，離群點(diǎn)挖掘與計(jì)算效率較高，可以在規(guī)定時(shí)間內(nèi)完成各項(xiàng)計(jì)算工作。同時(shí)為了保證網(wǎng)格單元性質(zhì)判斷速度，迅速確定網(wǎng)格單元屬于稠密型還是邊界型，以便迅速找到聚類網(wǎng)格單元并對(duì)其進(jìn)行處理，此種算法會(huì)運(yùn)用哈希表對(duì)網(wǎng)格單元信息進(jìn)行存儲(chǔ)，并完成上述一系列操作，與初始數(shù)據(jù)集點(diǎn)數(shù)量相比，在處理之后所需要進(jìn)行計(jì)算的集點(diǎn)數(shù)量極少，不僅聚類區(qū)域查找與處理較為迅速，且可以有效規(guī)避網(wǎng)格單元個(gè)數(shù)增加的問題，如果將其運(yùn)用到大規(guī)數(shù)據(jù)離群點(diǎn)檢測(cè)計(jì)算之中，會(huì)得到較為理想的執(zhí)行效率，算法優(yōu)勢(shì)較為明顯。

3.3 算法實(shí)驗(yàn)驗(yàn)證

為對(duì)算法可行性與效率展開分析，筆者設(shè)置了相應(yīng)算法驗(yàn)證實(shí)驗(yàn)。本次實(shí)驗(yàn)的空間鄰居數(shù)維度距離數(shù)值為50，而網(wǎng)格之間的距離為5，離群點(diǎn)數(shù)為80，且稠密網(wǎng)格單元數(shù)據(jù)點(diǎn)的閥值為25[4]。

經(jīng)過實(shí)驗(yàn)表明，與其他檢測(cè)算法相比，此種算法執(zhí)行效率優(yōu)勢(shì)較為突出，且執(zhí)行時(shí)間可以被控制在合理范圍之內(nèi)，能夠在完成網(wǎng)格劃分之后，實(shí)現(xiàn)對(duì)聚類區(qū)域的有效篩選和過濾，所需要實(shí)施離群點(diǎn)檢測(cè)的對(duì)象能夠得到有所壓縮，可以省去不必要的計(jì)算工作時(shí)間與工作量，所以此種算法不但可行，且執(zhí)行效率較為理想，值得進(jìn)行推廣與進(jìn)一步研究。

4 結(jié)語(yǔ)

通過分析可以發(fā)現(xiàn)，以網(wǎng)格劃分為基礎(chǔ)的高維離群點(diǎn)檢測(cè)方式，是一項(xiàng)較為高效的離群點(diǎn)挖掘技術(shù)，該方式會(huì)通過對(duì)數(shù)據(jù)空間維進(jìn)行同等距離劃分的方式，完成對(duì)數(shù)據(jù)空間的劃分，進(jìn)而形成多個(gè)沒有交集的網(wǎng)格單元，以實(shí)現(xiàn)對(duì)所有檢測(cè)對(duì)象的逐一檢測(cè)與處理，整體檢測(cè)效率與精準(zhǔn)度更加理想，更加適合大數(shù)據(jù)時(shí)代離群點(diǎn)挖掘需要，因此該項(xiàng)檢測(cè)算法將成為今后離群點(diǎn)研究領(lǐng)域重點(diǎn)研究課題，還需要業(yè)界同仁的不斷努力。