基于網(wǎng)格單元和P權(quán)值的離群數(shù)據(jù)挖掘方法

馮婷婷，張繼福

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

?

基于網(wǎng)格單元和P權(quán)值的離群數(shù)據(jù)挖掘方法

馮婷婷，張繼福

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

基于單元的離群數(shù)據(jù)挖掘是一類(lèi)典型的離群數(shù)據(jù)挖掘方法,盡管具有可以快速識(shí)別離群數(shù)據(jù)和修剪非離群數(shù)據(jù)等優(yōu)點(diǎn),但由于只從單元的角度修剪非離群數(shù)據(jù)，可能使一些單元無(wú)法準(zhǔn)確的確定離群數(shù)據(jù)。給出了一種基于網(wǎng)格單元和P權(quán)值的離群數(shù)據(jù)挖掘算法。該算法首先將數(shù)據(jù)集的每維均分，劃分網(wǎng)格單元，并在網(wǎng)格單元中，篩選出離群數(shù)據(jù)和正常數(shù)據(jù)網(wǎng)格單元；對(duì)既含有離群數(shù)據(jù)又有正常數(shù)據(jù)的網(wǎng)格單元，采用P權(quán)值的方法，來(lái)度量和確定離群數(shù)據(jù),從而進(jìn)一步提高了離群挖掘精度；最后，采用UCI數(shù)據(jù)集，實(shí)驗(yàn)驗(yàn)證了該算法的有效性和可行性。

數(shù)據(jù)挖掘；離群數(shù)據(jù);網(wǎng)格單元；P權(quán)值；距離

離群數(shù)據(jù)挖掘是數(shù)據(jù)挖掘的一個(gè)重要分支，離群數(shù)據(jù)就是一個(gè)數(shù)據(jù)對(duì)象，顯著不同于其他數(shù)據(jù)對(duì)象，好像是被不同的機(jī)制產(chǎn)生的一樣[1]，并已經(jīng)應(yīng)用在信用卡欺詐檢測(cè)[2]，網(wǎng)絡(luò)入侵檢測(cè)[3-4]，環(huán)境檢測(cè)[5]，醫(yī)療科學(xué)[6],天文光譜數(shù)據(jù)分析[7-8]等許多領(lǐng)域。目前，離群挖掘方法主要包括：基于統(tǒng)計(jì)的方法(又稱(chēng)為基于模型的方法)[9]，基于距離的方法[10]，基于密度的方法[11]，基于聚類(lèi)的方法[12]，基于網(wǎng)格單元的方法，基于角度的方法[13]等?；诰W(wǎng)格單元的離群數(shù)據(jù)挖掘具有把以單個(gè)對(duì)象為單位的檢測(cè)轉(zhuǎn)換為以單元為單位的檢測(cè)，能快速的修剪掉大部分非離群數(shù)據(jù)的特點(diǎn)，是一類(lèi)典型的離群數(shù)據(jù)挖掘方法，具有重要的應(yīng)用價(jià)值和應(yīng)用前景。

基于網(wǎng)格單元的離群數(shù)據(jù)挖掘方法[14]大都是首先將數(shù)據(jù)集按屬性維取值,均勻劃分成網(wǎng)格單元；然后分析每個(gè)網(wǎng)格單元中所包含數(shù)據(jù)的分布，并修剪其正常數(shù)據(jù)的網(wǎng)格單元；對(duì)于含有正常和離群數(shù)據(jù)的網(wǎng)格單元，采用子網(wǎng)格單元?jiǎng)澐?、近似密度?jì)算等方法，確定離群數(shù)據(jù)。典型研究工作主要有：Knorr等人首先提出了一種基于網(wǎng)格的離群數(shù)據(jù)挖掘方法，但該方法僅在小于4維數(shù)據(jù)下比較精確，并不適應(yīng)于高維數(shù)據(jù)集。在文獻(xiàn)[14]中，采用網(wǎng)格和密度結(jié)合的思想，提出了一種離群數(shù)據(jù)挖掘算法FOMAUC，有效提高了離群數(shù)據(jù)挖掘的效果和效率，但存在以下不足：

(1)在精選步驟2中，對(duì)各個(gè)數(shù)據(jù)對(duì)象的判別是獨(dú)立的，未利用先前的判斷信息，計(jì)算復(fù)雜性高，效率低；

(2)當(dāng)維數(shù)較高時(shí)，稀疏網(wǎng)格單元的個(gè)數(shù)較多，造成精選過(guò)程時(shí)間復(fù)雜度高，因此不適用于高維數(shù)據(jù)。文獻(xiàn)[15]為了解決文獻(xiàn)[14]存在的計(jì)算復(fù)雜性高和效率低的問(wèn)題，采用了微單元的概念。該算法通過(guò)增加微單元篩選過(guò)程，并采用改進(jìn)的微單元樹(shù)結(jié)構(gòu)，避免對(duì)非空單元的操作和進(jìn)行高效的鄰居查找,但存在如下不足：

(1)采用微單元致使計(jì)算單元網(wǎng)格的密度次數(shù)增多，而且在高維空間中，微單元增加了時(shí)間開(kāi)銷(xiāo)；

(2)采用微單元，對(duì)于處理單元過(guò)程中保留的密集單元及密集微單元，直接認(rèn)為是正常數(shù)據(jù)網(wǎng)格單元，直接刪除；對(duì)于稀疏的微單元及其鄰域微單元點(diǎn)數(shù)之和如果大于密度閾值，也判斷為正常網(wǎng)格單元，這樣容易遺漏離群數(shù)據(jù)。而且文獻(xiàn)[15]只是在基于單元的基礎(chǔ)上增加了微單元，在高維數(shù)據(jù)中，單元格密度較稀疏，造成幾乎所有數(shù)據(jù)對(duì)象都為離群數(shù)據(jù)，因此該方法不適用于高維數(shù)據(jù)。張凈等人提出了一種基于網(wǎng)格和密度的海量數(shù)據(jù)增量式離群點(diǎn)挖掘算法，該算法采用網(wǎng)格的七元組信息先對(duì)數(shù)據(jù)降維；然后利用增量更新減少內(nèi)存需求，并過(guò)濾掉部分非離群數(shù)據(jù)；最后采用近似密度計(jì)算的方法減少計(jì)算量，從而確定出離群數(shù)據(jù)。 文獻(xiàn)[16]給出一種基于P權(quán)值的離群數(shù)據(jù)挖掘算法，該算法首先采用三角不等式的剪枝技術(shù)修剪數(shù)據(jù)集，對(duì)剩余候選離群數(shù)據(jù)集用P權(quán)值的方法計(jì)算該數(shù)據(jù)對(duì)象與其k近鄰的距離和，和越大，離群的可能性越大，但在距離和相等的情況下無(wú)法判斷哪些數(shù)據(jù)對(duì)象更可能是離群數(shù)據(jù)。本論文的P權(quán)值方法是計(jì)算候選離群?jiǎn)卧袛?shù)據(jù)對(duì)象與其k近鄰的平均距離，由于候選離群?jiǎn)卧袑?duì)象數(shù)不同，其鄰域單元對(duì)象數(shù)也可能不同，因而每個(gè)對(duì)象的近鄰數(shù)k可能也不同，因此求平均距離，平均距離越大，離群可能性越高。

綜上所述，本文給出了一種基于網(wǎng)格單元和P權(quán)值的離群數(shù)據(jù)挖掘算法。該算法首先將數(shù)據(jù)集按維均勻劃分為網(wǎng)格單元，并根據(jù)其包含的數(shù)據(jù)對(duì)象密度，篩選出非離群和離群網(wǎng)格單元；對(duì)于剩余網(wǎng)格單元，采用P權(quán)值的方法，來(lái)度量和確定離群數(shù)據(jù)。該方法有效地避免了離群數(shù)據(jù)遺漏和誤檢現(xiàn)象，進(jìn)一步提高了挖掘精度。

1 單元網(wǎng)格、距離和離群數(shù)據(jù)

利用單元網(wǎng)格，可以快速識(shí)別離群數(shù)據(jù)和修剪正常數(shù)據(jù)，是一類(lèi)典型的離群數(shù)據(jù)挖掘方法。參照文獻(xiàn)[1,15,16]，相關(guān)概念定義如下：

定義1 單元U.對(duì)于給定的m維數(shù)據(jù)集,將其構(gòu)成m維空間S中的每一維均分，第i維被劃分成Si段，那么，該空間就被劃分為S1×S2×S3…×Sm個(gè)區(qū)域，這樣的區(qū)域稱(chēng)為單元，記為U=(u1,u2,…um),1≤Ui≤Si.

定義2 單元密度D.在m維空間S中有數(shù)據(jù)對(duì)象d=(d1,d2,…,dm)，若點(diǎn)d屬于單元U=(p1,p2,…,pm)，當(dāng)且僅當(dāng)(pi-1)×L≤di

定義3 若一單元U中的密度D超過(guò)某一給定的閾值Minpts, 即D≥Minpts時(shí), 則單元U稱(chēng)之為密集單元, 記為UD, 反之單元U稱(chēng)之為稀疏單元, 記為US.

定義4 鄰居單元。若單元U1=(p11,p12,…,p1m)和U2=(p21,p22,…,p2m)滿(mǎn)足下式：

其中i=1,2，…m，則稱(chēng)U1，U2互為鄰居單元。

對(duì)于密集單元，若其鄰居單元也都為密集單元，則將該單元中的點(diǎn)全部標(biāo)記為正常數(shù)據(jù)，否則將其標(biāo)記為候選離群?jiǎn)卧?duì)于稀疏單元，若其鄰居單元也都為稀疏單元，則將該單元中的數(shù)據(jù)對(duì)象標(biāo)記為離群數(shù)據(jù)，否則將其標(biāo)記為候選離群?jiǎn)卧?/p>

定義5 距離 令i=(xi1,xi2,...,xip)和j=(xj1,xj2,...,xjp)是兩個(gè)p維數(shù)據(jù)對(duì)象。對(duì)象i和j之間的歐幾里得距離定義為：

歐幾里得距離有效地度量和刻畫(huà)了兩個(gè)數(shù)據(jù)對(duì)象之間的相似性,距離d(i,j)越大，二者越相異，越小越相似。

利用P權(quán)值可以有效地度量數(shù)據(jù)對(duì)象的稀疏程度，權(quán)值越大，對(duì)象p距離其鄰域?qū)ο笤竭h(yuǎn)，也表明對(duì)象p的鄰居對(duì)象越稀疏。

2 基于單元和P權(quán)值的離群數(shù)據(jù)挖掘算法

2.1 基本思想

在基于網(wǎng)格單元的離群數(shù)據(jù)檢測(cè)方法中，對(duì)于候選離群?jiǎn)卧械臄?shù)據(jù)，很難判別是否為離群數(shù)據(jù),容易遺漏,而且在高維數(shù)據(jù)集中，網(wǎng)格單元密度較稀疏，無(wú)法有效地度量離群數(shù)據(jù)。P權(quán)值是一種度量數(shù)據(jù)對(duì)象稀疏程度的有效方法,采用P權(quán)值來(lái)度量候選離群?jiǎn)卧械臄?shù)據(jù)對(duì)象,可以有效地區(qū)分和識(shí)別出每個(gè)數(shù)據(jù)對(duì)象的稀疏程度,從而有效地度量其網(wǎng)格單元中,所包含的離群數(shù)據(jù)?；舅枷肴缦拢?/p>

(1)對(duì)于任意m維數(shù)據(jù)集DB，根據(jù)定義1，將其構(gòu)成m維空間數(shù)據(jù)S中的每一維均分，即將m維數(shù)據(jù)空間劃分為多個(gè)網(wǎng)格單元U.(2)根據(jù)定義2，統(tǒng)計(jì)每個(gè)單元的密度D.(3)根據(jù)定義3，4劃分密集單元和稀疏單元，若該單元為密集單元，且其鄰居單元也都為密集單元時(shí)，可以確定該單元中所有的數(shù)據(jù)都為正常數(shù)據(jù)，否則將其標(biāo)記為候選離群?jiǎn)卧Ｈ粼搯卧獮橄∈鑶卧?，若其周?chē)従訂卧紴橄∈鑶卧瑒t可判定該單元所有數(shù)據(jù)都為離群數(shù)據(jù)，否則將其標(biāo)記為候選離群?jiǎn)卧?4)對(duì)標(biāo)記為候選離群?jiǎn)卧械臄?shù)據(jù)對(duì)象，根據(jù)定義5，6計(jì)算其P權(quán)值，確定前TOP-N個(gè)P權(quán)值最大的數(shù)據(jù)對(duì)象即為最需要的離群數(shù)據(jù)。(5)綜上，標(biāo)記為離群數(shù)據(jù)單元的對(duì)象和前TOP-N個(gè)P權(quán)值最大的數(shù)據(jù)對(duì)象即為最終查找的離群數(shù)據(jù)。

2.2 算法描述

算法:CWOP(Cell-basedandPweightoutlierdetection)

輸入：數(shù)據(jù)集GDB，密度閾值Minpts，近鄰數(shù)k

輸出：離群數(shù)據(jù)集合O

1.double[][]data=GDB；

2.doublelen；

2.createNetGrid(double[][]data,doublelen)；//根據(jù)數(shù)據(jù)集和單元格邊長(zhǎng)創(chuàng)建網(wǎng)格

3.showPointsSum(ArrayListresult,Stringname)；//統(tǒng)計(jì)每個(gè)單元格的對(duì)象數(shù)

4.statisticNeighourCellUnit(ArrayListresult)；//統(tǒng)計(jì)鄰域單元的對(duì)象數(shù)

5.foreachnon-emptyCkinD//對(duì)于每個(gè)非空單元

6.ifCountk>MinptsandCountk鄰域>Minpts

7.Ckisnormaldata,skiptoanotherCk.//標(biāo)記此Ck為正常單元，跳轉(zhuǎn)到下一個(gè)單元

8.elseifCountk

9.Ckisoutlierdata，addCktooutlierCell,skiptoanotherCk.

10.endif

11.foreachnon-emptyCkinG//對(duì)于剩余網(wǎng)格單元 ，計(jì)算每個(gè)對(duì)象的P權(quán)值

12.foreachOiinCk

14.fori=1tom

15.ArrayListgetAllOutPoints(ArrayListcolorcells,ArrayListobletepoints,intm)，addtooutlierCell.

16.returnoutlierCell.//輸出離群數(shù)據(jù)集合中的點(diǎn)

2.3 單元格邊長(zhǎng)L的確定

單元格邊長(zhǎng)對(duì)離群數(shù)據(jù)的判定有一定的影響，而一個(gè)特定的網(wǎng)格單元邊長(zhǎng)L無(wú)法適合于所有數(shù)據(jù)集D.單元格邊長(zhǎng)越小,網(wǎng)格單元的數(shù)目越多，統(tǒng)計(jì)單元格內(nèi)的對(duì)象數(shù)執(zhí)行時(shí)間就越長(zhǎng)；單元格邊長(zhǎng)越大，雖然統(tǒng)計(jì)單元格內(nèi)對(duì)象數(shù)時(shí)間縮短，但也降低了修剪概率。因此需要多次試驗(yàn)找出一個(gè)合適的單元格邊長(zhǎng)。

3 算法分析

在上述CWOP算法中，首先使用基于網(wǎng)格的方法將數(shù)據(jù)劃分網(wǎng)格單元，再利用網(wǎng)格的密度特征，有效地確定數(shù)據(jù)集中一部分非離群?jiǎn)卧碗x群?jiǎn)卧?。?duì)于候選單元中的點(diǎn)用P權(quán)值的方法可以確定對(duì)象分布的稀疏程度，權(quán)值越大，該對(duì)象周?chē)较∈?，說(shuō)明該對(duì)象距離其鄰域?qū)ο笤竭h(yuǎn)，即越可能是離群數(shù)據(jù)，從而檢測(cè)出這些網(wǎng)格單元中的離群數(shù)據(jù)。對(duì)于檢測(cè)高維數(shù)據(jù)中稀疏網(wǎng)格單元，確定前n個(gè)權(quán)值最大的數(shù)據(jù)為離群數(shù)據(jù)，也不會(huì)造成所有數(shù)據(jù)都檢測(cè)為離群數(shù)據(jù)這一現(xiàn)象。假設(shè)已統(tǒng)計(jì)好數(shù)據(jù)集中數(shù)據(jù)量為N，稀疏單元的個(gè)數(shù)為s，稀疏單元鄰居個(gè)數(shù)為k，密集單元內(nèi)數(shù)據(jù)對(duì)象的個(gè)數(shù)為c，掃描剩余候選集，判斷該數(shù)據(jù)對(duì)象是否為離群數(shù)據(jù)，需要調(diào)用m次，因此算法總的時(shí)間復(fù)雜度為T(mén)=O(N+2*s*k+(N-c)*m).

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

通過(guò)實(shí)驗(yàn)對(duì)本文CWOP算法和改進(jìn)的微單元(MCA)算法[15]的檢測(cè)精度、執(zhí)行效率和冗余度進(jìn)行對(duì)比。

精確度=(挖掘出的離群個(gè)數(shù)/實(shí)際離群個(gè)數(shù))*100%

冗余度=(已挖掘的離群點(diǎn)數(shù)-正確挖掘的離群點(diǎn)數(shù))/已挖掘的離群點(diǎn)數(shù)

實(shí)驗(yàn)環(huán)境：Intel(R)Core(TM)i5-4570，3.20GHzCPU，2GB內(nèi)存，操作系統(tǒng)為Windows7，用junoeclipse作為開(kāi)發(fā)平臺(tái)，并用java語(yǔ)言實(shí)現(xiàn)了MCA算法[15]和本文CWOP算法。

測(cè)試數(shù)據(jù)集如下:

表1 試驗(yàn)測(cè)試數(shù)據(jù)集

對(duì)于低維數(shù)據(jù)，圖1表明算法的精度隨著L的增大呈現(xiàn)先降低后升高的狀態(tài)，在邊長(zhǎng)為0.3至0.5和1.3時(shí)達(dá)到最佳為77.8%，隨著邊長(zhǎng)L的增大，劃分的單元格數(shù)量減少，每個(gè)單元格內(nèi)的對(duì)象數(shù)增多，選定合適的密度閾值，刪除的非離群點(diǎn)數(shù)增多，因此精度提高。說(shuō)明單元格邊長(zhǎng)對(duì)該算法挖掘精度影響很大。特殊情況，當(dāng)邊長(zhǎng)L=1時(shí)，所有對(duì)象都在一個(gè)單元格內(nèi)，此時(shí)CWOP算法判定所有對(duì)象為候選離群點(diǎn)，以做進(jìn)一步判斷，而MCA算法判定該單元為密集單元，這樣造成所有對(duì)象都為非離群數(shù)據(jù)的極端情況，相當(dāng)于沒(méi)有檢測(cè)到離群數(shù)據(jù)對(duì)象，即造成離群數(shù)據(jù)判斷不精確。

對(duì)于高維數(shù)據(jù)，從圖1直觀來(lái)看，二者的挖掘精度都達(dá)到100%，但二者的冗余度卻不同，具體看下面的實(shí)驗(yàn)對(duì)比。

圖1 挖掘精度比較(Minpts=15)

圖2 挖掘精度比較(L= 0.5)

圖2為在L固定的時(shí)候，改變密度閾值來(lái)比較兩個(gè)算法的挖掘精度，隨著密度閾值的增加，MCA算法和CWOP算法精度都呈現(xiàn)升高的趨勢(shì)。在Minpts=5和25的時(shí)候達(dá)到最高峰。在找到合適的邊長(zhǎng)之后，調(diào)整Minpts的大小，在Minpts=1至5時(shí)，CWOP算法挖掘精度稍高于MCA算法，在Minpts=10至25時(shí)，二者都達(dá)到最高精度77.8%.總體來(lái)說(shuō)，在數(shù)據(jù)集維數(shù)比較低時(shí)，CWOP算法挖掘精度比MCA算法略高。

對(duì)于高維數(shù)據(jù)，從圖1和圖2可以看出兩種算法的精度都達(dá)到100%，但是從圖3可以看出CWOP算法的冗余度為0，而MCA算法的冗余度為97%.MCA算法在檢測(cè)過(guò)程中雖然刪除了一部分非離群點(diǎn)，但是仍舊把很大一部分當(dāng)成離群點(diǎn)，而真正的離群點(diǎn)數(shù)是少數(shù)的，這就造成離群點(diǎn)檢測(cè)的冗余度較高，這是離群點(diǎn)的誤檢，說(shuō)明MCA算法不適合檢測(cè)高維數(shù)據(jù)。而CWOP算法采用P權(quán)值有效地度量數(shù)據(jù)對(duì)象的稀疏程度，可以正確的檢測(cè)出離群點(diǎn)并且冗余度為0.

圖4和圖5表明隨著L的增大或Minpts的增大，刪除的非離群點(diǎn)數(shù)越來(lái)越多，主要原因是，隨著單元格邊長(zhǎng)的增大，劃分單元格的數(shù)目減少，在Minpts固定時(shí)，邊長(zhǎng)大的單元格中對(duì)象數(shù)較多，刪除的非離群點(diǎn)數(shù)較多，因此執(zhí)行時(shí)間減少，效率提高。在L固定時(shí)，隨著Minpts的增大，單元格中大于Minpts的單元數(shù)減少，刪除的單元格數(shù)減少，因此執(zhí)行時(shí)間減少，效率提高。從圖4和圖5可以看出，在低維情況下，CWOP算法的效率略高于MCA算法，而在高維情況下，CWOP算法的效率明顯高于MCA算法。而且在高維和海量數(shù)據(jù)情況下，MCA算法的冗余度達(dá)到100%，說(shuō)明MCA算法不適合檢測(cè)高維數(shù)據(jù)。

圖3 冗余度比較

圖5 效率比較(L=0.5)

圖6 不同數(shù)據(jù)集大小下用的時(shí)間比較

圖6為在選定合適的Minpts和邊長(zhǎng)的情況下，在不同數(shù)據(jù)集大小下所用時(shí)間的比較，CWOP算法由于數(shù)據(jù)量的增加，計(jì)算每個(gè)對(duì)象的P 權(quán)值所用時(shí)間增加，因此效率降低。而MCA算法隨著數(shù)據(jù)量的增加，劃分微單元并統(tǒng)計(jì)微單元內(nèi)的對(duì)象數(shù)增加了計(jì)算量，效率也隨之降低。可以看出CWOP算法和MCA算法都隨著數(shù)據(jù)集數(shù)目的增多所用時(shí)間增大，而且都成指數(shù)增長(zhǎng)，而CWOP算法所用時(shí)間略低于MCA算法，說(shuō)明CWOP算法的效率略高。將該算法與OMAW算法[17]進(jìn)行比較，該算法在數(shù)據(jù)集達(dá)到3 000時(shí)明顯優(yōu)于OMAW 算法，說(shuō)明數(shù)據(jù)量增大時(shí)，本文算法的效率相對(duì)較高。

5 結(jié) 論

采用基于網(wǎng)格單元的離群數(shù)據(jù)挖掘方法修剪網(wǎng)格單元，對(duì)剩余的網(wǎng)格單元用P權(quán)值的方法確定離群數(shù)據(jù)，即計(jì)算候選點(diǎn)O的k近鄰的平均距離，并按P權(quán)值大小排序，確定前TOP-N個(gè)P權(quán)值最大的點(diǎn)即為離群點(diǎn)，具有既可以檢測(cè)出既有正常數(shù)據(jù)又有離群數(shù)據(jù)網(wǎng)格單元中的離群數(shù)據(jù)的優(yōu)點(diǎn)，也可以避免在高維數(shù)據(jù)中把所有稀疏單元都檢測(cè)為離群數(shù)據(jù)這一極端現(xiàn)象。利用UCI數(shù)據(jù)集，實(shí)驗(yàn)驗(yàn)證了該算法的可行性和有效性。

[1] JIAWEI H,MICHELINE K. FAN M. Data mining concepts and techniques[M].Beijing:China Machine Press,2012.7

[2] KNORR E M, Ng R T. Algorithms for Mining Distance-Based Outliers in Large Datasets[C]// Proceedings of the 24rd International Conference on Very Large Data BasesMorgan Kaufmann Publishers Inc., 1998:392-403.

[3] SEQUEIRA K, ZAKI M. ADMIT: anomaly-based data mining for intrusions[C]//Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2002: 386-395.

[4] LAZAREVIC A, ERTOZ L, KUMAR V, et al. A Comparative Study Of Anomaly Detection Schemes In Network Intrusion Detection[C]// In Proceedings of the Third SIAM International Conference on Data Mining2003.

[5] LIU H, SHAH S, JIANG W. On-line outlier detection and data cleaning[J]. Computers & Chemical Engineering, 2004, 28(9):1635-1647.

[6] KNORR E M, NG R T, TUCAKOV V. Distance-based outliers: algorithms and applications[J]. The VLDB Journal—The International Journal on Very Large Data Bases, 2000, 8(3-4): 237-253.

[7] 張繼福, 蔣義勇, 胡立華,等. 基于概念格的天體光譜離群數(shù)據(jù)識(shí)別方法[J]. 自動(dòng)化學(xué)報(bào), 2008(9):1060-1066.

[8] 張繼福, 李永紅, 秦嘯,等. 基于MapReduce與相關(guān)子空間的局部離群數(shù)據(jù)挖掘算法[J]. 軟件學(xué)報(bào), 2015 (5)：131-135.

[9] FREEMAN J. Outliers in Statistical Data (3rd edition)[J]. Journal of the Operational Research Society, 1995, 46(8)：68-71.

[10] 石巖,劉愛(ài)琴,張繼福.一種基于基尼指標(biāo)的高維數(shù)據(jù)離群挖掘算法[J].太原科技大學(xué)學(xué)報(bào), 2013, 34(3):161-165.

[11] BREUNIG M M, KRIEGEL H P, Ng R T, et al. LOF: Identifying Density-Based Local Outliers.[J]. Acm Sigmod Record, 2000,29(2):93-104.

[12] LIANG B M. A Hierarchical Clustering Based Global Outlier Detection Method[C]// Bio-Inspired Computing: Theories and Applications (BIC-TA), 2010 IEEE Fifth International Conference2010:1213 - 1215.

[13] KRIEGEL H P, S HUBERT M, ZIMEK A. Angle-Based Outlier Detection in High-dimensional Data[J]. Dbs.ifi.lmu.de, 2008(6):444-452.

[14] 崔貫勛，李梁，王勇，等. 快速的基于單元格的離群數(shù)據(jù)挖掘算法[J]. 計(jì)算機(jī)應(yīng)用, 2009, 29(12): 3300-3302.

[15] 唐成龍, 邢長(zhǎng)征. 基于數(shù)據(jù)分區(qū)和網(wǎng)格的離群點(diǎn)挖掘算法[J]. 計(jì)算機(jī)應(yīng)用, 2012, 32(8): 2193-2197.

[16] 張凈, 孫志揮, 楊明, 等. 基于網(wǎng)格和密度的海量數(shù)據(jù)增量式離群點(diǎn)挖掘算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2011, 48(5): 823-830.

[17] LOU S J, ZHANG J F, LIU A Q. A Outlier Mining Algorithm Based on P Weights[J]. Journal of Chinese Computer Systems, 2014，12(6)：63-68.

AnOutlier Data Mining Method of Grid Cell-Based and P weights

FENG Ting-ting，ZHANG Ji-fu

(School of Computer Science and Technology, Taiyuan University of Science and Technology, Taiyuan 030024, China)

Cell-based outlier data mining is a kind of typical outlier data mining method, although it has the advantage of quick identification of outlier data and trimming the data from the group, only from the unit part perspective of pruning the non-outlier data is likely to make some cells not be determined accurately. This paper presents a cell-based and P weight of outlier data mining algorithm. The algorithm firstly divides each dimension of the data set and divides the grid cell, then in the grid cell, screens out the outlier data and the normal data grid cell; both contain outlier and the normal data of grid cell by using the method of p weights to measure and determine the outlier data from the group, so as to further improve the accuracy of outlier data mining; finally, the experiment proves the algorithm of the feasibility and effectiveness by using the UCI data sets.

data mining, outlier data, grid cell, P weight, distance

2015-11-05

馮婷婷(1988-)女，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘。

1673-2057(2016)05-0359-06

TP39

A

10.3969/j.issn.1673-2057.2016.04.005