基于逆k近鄰計(jì)數(shù)和權(quán)值剪枝的離群數(shù)據(jù)挖掘算法

朱云麗，張繼福

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

E-mail:onlylzhu@163.com

1 引言

離群數(shù)據(jù)挖掘是數(shù)據(jù)挖掘的主要任務(wù)之一，是指數(shù)據(jù)集中那些遠(yuǎn)離常規(guī)對(duì)象的數(shù)據(jù)，表現(xiàn)為與多數(shù)常規(guī)對(duì)象有明顯差異，以至于被懷疑可能是由另外一種完全不同的機(jī)制產(chǎn)生［1］，并廣泛地應(yīng)用在欺詐檢測(cè)［2］、網(wǎng)絡(luò)入侵檢測(cè)［3］、醫(yī)療診斷［4］、顧客關(guān)系管理［5］、天體光譜數(shù)據(jù)挖掘［6］等領(lǐng)域.大多數(shù)離群數(shù)據(jù)挖掘算法會(huì)受到“維度災(zāi)難”的影響，數(shù)據(jù)對(duì)象之間的相似性或距離變得難以區(qū)分或識(shí)別［7，8］，因而離群挖掘效果變差.k近鄰(KNN)搜索是許多離群數(shù)據(jù)挖掘算法中的一種重要操作步驟，應(yīng)用最為廣泛.

在高維數(shù)據(jù)空間中，KNN查詢會(huì)受到“維度災(zāi)難”的影響，無(wú)法識(shí)別出真正的離群點(diǎn)［9］.逆k近鄰(RKNN)查詢是與KNN相關(guān)的一個(gè)概念，是指查找以給定對(duì)象作為其k近鄰對(duì)象的集合［10］.具有低RKNN值的對(duì)象較少出現(xiàn)在其它對(duì)象的KNN中［11］，維度越高，RKNN值越能反映對(duì)象的離群程度，因而適用于高維數(shù)據(jù)空間中的離群數(shù)據(jù)挖掘［12，13］.本文針對(duì)高維數(shù)據(jù)集，利用RKNN給出一種基于RKNN計(jì)數(shù)和權(quán)值剪枝策略相結(jié)合的離群數(shù)據(jù)挖掘算法RKNNCWP.該算法利用參數(shù)k以及對(duì)象的RKNN計(jì)數(shù)作為區(qū)分度，重新定義了離群分?jǐn)?shù)計(jì)算公式，該公式減少了人為定義的區(qū)分度對(duì)離群數(shù)據(jù)挖掘精度的影響，避免了過(guò)多的算法參數(shù)設(shè)置;采用剪枝策略剔除非離群候選對(duì)象的離群分?jǐn)?shù)計(jì)算，避免計(jì)算數(shù)據(jù)集中全部對(duì)象的離群分?jǐn)?shù)，有效地提高了挖掘效率;采用人工數(shù)據(jù)集和UCI標(biāo)準(zhǔn)數(shù)據(jù)集，實(shí)驗(yàn)驗(yàn)證了該算法的有效性.

2 相關(guān)工作

傳統(tǒng)的離群數(shù)據(jù)挖掘算法大多基于距離［14］、基于密度［15］、基于統(tǒng)計(jì)［16］、基于子空間［17，18］等，在高維空間中會(huì)受到“維度災(zāi)難”的影響，離群挖掘效果變差，難以識(shí)別出真正的離群對(duì)象.k近鄰(KNN)查詢是離群數(shù)據(jù)挖掘算法中的一個(gè)重要步驟.

由KNN查詢所生成的KNN結(jié)果集有助于從全局的角度，了解數(shù)據(jù)對(duì)象在整個(gè)數(shù)據(jù)集中的分布情況，因此依據(jù)KNN結(jié)果集，可有效地實(shí)現(xiàn)離群數(shù)據(jù)挖掘任務(wù)［19，20］.典型研究成果:Ramaswamy等［21］將數(shù)據(jù)對(duì)象到其第k個(gè)最近鄰對(duì)象的距離看作是該數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，選取距離最大的若干個(gè)對(duì)象作為離群對(duì)象，但當(dāng)距離相等而對(duì)象周圍的密度明顯不同時(shí)，會(huì)將正常對(duì)象歸為離群對(duì)象;Angiulli等［22］將對(duì)象到其k個(gè)近鄰對(duì)象的距離和作為數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，距離和最大的前n個(gè)數(shù)據(jù)對(duì)象被認(rèn)為是離群對(duì)象，但當(dāng)該對(duì)象位于簇內(nèi)邊緣時(shí)，其k近鄰距離和較大，將被錯(cuò)誤地歸為離群對(duì)象;Breunig等［23］提出LOF算法，數(shù)據(jù)對(duì)象i的離群度被定義為對(duì)象i的密度與其KNN對(duì)象密度均值的比值，但當(dāng)數(shù)據(jù)集是由稠密程度不同的簇組成時(shí)，位于稀疏簇邊緣的對(duì)象將被錯(cuò)誤地歸為離群對(duì)象，因而不適用于復(fù)雜情形的數(shù)據(jù)集.

逆k近鄰(RKNN)查詢以數(shù)據(jù)集中對(duì)象的KNN集合作為前提條件，查找以數(shù)據(jù)對(duì)象i作為其KNN對(duì)象的集合，數(shù)據(jù)對(duì)象i出現(xiàn)在其它對(duì)象KNN中的次數(shù)，能有效地反映對(duì)象的離群程度［12］.典型研究成果:Hautamaki等［24］提出 ODIN算法，該算法把數(shù)據(jù)對(duì)象的入度數(shù)作為對(duì)象的離群分?jǐn)?shù)，入度數(shù)是指若數(shù)據(jù)集中其它對(duì)象的KNN中包含該對(duì)象，則該對(duì)象的入度數(shù)增加1，當(dāng)入度數(shù)滿足一定的閾值條件時(shí)，認(rèn)為該數(shù)據(jù)對(duì)象是離群對(duì)象，但需人為設(shè)置閾值參數(shù)，對(duì)離群數(shù)據(jù)挖掘的準(zhǔn)確率有較大影響;Jin等［25］提出INFLO算法，該算法在考慮數(shù)據(jù)對(duì)象的離群性時(shí)，將對(duì)象i的KNN對(duì)象以及RKNN對(duì)象組成一個(gè)影響集，對(duì)象i的離群度INFLO被定義為影響集中對(duì)象密度的均值與對(duì)象i的局部密度比值，INFLO值越高，該對(duì)象成為離群對(duì)象的可能性越大，但需計(jì)算所有對(duì)象的局部密度以及其近鄰、逆近鄰對(duì)象的密度，時(shí)間復(fù)雜度大，不適用于對(duì)數(shù)據(jù)量較大的數(shù)據(jù)集進(jìn)行離群挖掘;Radovanovic＇等［12］提出 AntiHub2算法，用于挖掘高維數(shù)據(jù)空間中的離群對(duì)象，該算法用區(qū)分度比例α，將查詢對(duì)象的RKNN計(jì)數(shù)及其KNN的RKNN計(jì)數(shù)結(jié)合起來(lái)，定義了離群分?jǐn)?shù)計(jì)算公式，但在無(wú)任何先驗(yàn)知識(shí)的情況下，需多次人為設(shè)置α參數(shù)，每次均需帶入離群分?jǐn)?shù)計(jì)算公式計(jì)算全部對(duì)象的離群分?jǐn)?shù)，才可得到滿意的離群結(jié)果集，時(shí)間復(fù)雜度較高，對(duì)離群挖掘準(zhǔn)確率有較大的影響.

綜上所述，在高維離群數(shù)據(jù)挖掘中，RKNN大多是采用數(shù)據(jù)對(duì)象及其KNN對(duì)象的RKNN計(jì)數(shù)作為數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，以衡量對(duì)象的離群程度，均需將人為設(shè)置的參數(shù)進(jìn)行迭代循環(huán)才能得到滿意的離群結(jié)果集，而參數(shù)的選擇無(wú)任何先驗(yàn)知識(shí)可借鑒，離群挖掘準(zhǔn)確率較低;此外，采用全部數(shù)據(jù)集，來(lái)計(jì)算數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，未將非離群候選對(duì)象剔除掉，因而時(shí)間復(fù)雜度較大.

3 逆k近鄰計(jì)數(shù)

隨著維度的增加，“維災(zāi)現(xiàn)象”［26］表現(xiàn)的愈加明顯.Radovanovic＇等［12］提出 Hubness現(xiàn)象，是指隨著數(shù)據(jù)本征維度的增加，數(shù)據(jù)集中某些對(duì)象出現(xiàn)在其它對(duì)象KNN集合中的次數(shù)，所遵循的分布呈現(xiàn)右傾斜，導(dǎo)致一些數(shù)據(jù)對(duì)象(稱為hub)非常頻繁地出現(xiàn)在其它對(duì)象的KNN列表中，而另外一些數(shù)據(jù)對(duì)象(稱為antihub)則很少作為其它對(duì)象的最近鄰居.Hubness現(xiàn)象與“維災(zāi)現(xiàn)象”高度相關(guān).

給定數(shù)據(jù)集 D={D1，D2，…，Dn}，對(duì)象 Di的 RKNN 計(jì)數(shù)記為Nk(i).參照AntiHub2算法［12］，數(shù)據(jù)對(duì)象Di的antihub分?jǐn)?shù)公式定義為:

Antihub分?jǐn)?shù)刻畫(huà)了對(duì)象Di在數(shù)據(jù)集中的離群程度，當(dāng)對(duì)象Di很少或不出現(xiàn)在其它對(duì)象的KNN集合中時(shí)，該公式仍能有效地反映數(shù)據(jù)對(duì)象的離群程度.

為進(jìn)一步提高離群挖掘的準(zhǔn)確率，考慮數(shù)據(jù)對(duì)象Di的Nk(i)時(shí)，還考慮其KNN對(duì)象的Nk(i).對(duì)象Di的k近鄰antihub分?jǐn)?shù)和anni公式定義為:

其中NNdist(k，i)表示對(duì)象Di的KNN對(duì)象索引，aj表示KNN對(duì)象的antihub分?jǐn)?shù).數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)計(jì)算公式定義為:

其中α是離群區(qū)分度比例，取值范圍(0，step，2·step，…，1)，step是人為設(shè)置的參數(shù)，ai為數(shù)據(jù)對(duì)象Di的antihub分?jǐn)?shù)，anni為數(shù)據(jù)對(duì)象Di的k近鄰對(duì)象的antihub分?jǐn)?shù)和.

為獲得最滿意的α值，文獻(xiàn)［12］引入局部函數(shù)discScore(outlierScore1，p)，p是人為設(shè)置的參數(shù)，通過(guò)求最大離群區(qū)分度獲得滿意的α值.

AntiHub2算法的缺點(diǎn)有:

1)需人為設(shè)置參數(shù)α、step和p的值，而這三個(gè)參數(shù)的選擇沒(méi)有先驗(yàn)知識(shí)可以借鑒，對(duì)離群挖掘準(zhǔn)確率有較大影響;

2)迭代循環(huán)運(yùn)算時(shí)間較長(zhǎng)，為找到最滿意的α值，需將所有的可能值遍歷，α每取一個(gè)值，都需設(shè)置一個(gè)參數(shù)p，而p的取值對(duì)α的選擇又有影響，因而需較長(zhǎng)時(shí)間才能找到滿意的離群結(jié)果集;

3)利用該算法計(jì)算得到的離群分?jǐn)?shù)值較小，不能有效識(shí)別出離群對(duì)象.

4 權(quán)值剪枝與離群分?jǐn)?shù)

Knorr等［27］采用DB距離衡量數(shù)據(jù)對(duì)象的離群程度.借助于距離來(lái)衡量數(shù)據(jù)對(duì)象是否異常的方式，會(huì)將正常數(shù)據(jù)對(duì)象歸為離群數(shù)據(jù)，特別是在高維數(shù)據(jù)空間中，數(shù)據(jù)對(duì)象之間的距離難以區(qū)分.逆k近鄰(RKNN)計(jì)數(shù)以對(duì)象的KNN結(jié)果集為輸入，統(tǒng)計(jì)對(duì)象出現(xiàn)在其它對(duì)象KNN列表中的次數(shù).數(shù)據(jù)對(duì)象及其KNN對(duì)象的RKNN計(jì)數(shù)、數(shù)據(jù)對(duì)象與其KNN的距離均值，都從總體上反映了該數(shù)據(jù)對(duì)象的離群程度，因而將RKNN計(jì)數(shù)及KNN距離結(jié)合起來(lái)，可以提高離群挖掘效果.

給定數(shù)據(jù)集D={D1，D2，…，Dn}，每個(gè)對(duì)象的 k近鄰集合為 KNN={N1，N2，…，Nk}，Di與其 KNN 的距離均值為avg(Di，KNN)，數(shù)據(jù)集 D的 KNN距離均值為 avg(D，KNN)，參照文獻(xiàn)［28］，數(shù)據(jù)對(duì)象Di的KNN權(quán)值定義為:

由公式(4)，可定義KNN權(quán)值集合W={WD1，WD2，…，WDn}.對(duì)WDi＜1的數(shù)據(jù)對(duì)象，由于對(duì)象與其KNN的距離均值小于數(shù)據(jù)集的KNN距離均值，該數(shù)據(jù)對(duì)象位于數(shù)據(jù)集的中心對(duì)象附近，離群程度較小，因而可將該數(shù)據(jù)對(duì)象剪枝，得到剪枝后的 KNN 權(quán)值集合 Wpruning={WDa，WDb，WDc，…}以及剪枝后的對(duì)象集合 List={Da，Db，Dc，…}.計(jì)算 List集合中數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，可有效提高挖掘效率.

將WDm≥1的對(duì)象保存在離群候選集List中，對(duì)集合中數(shù)據(jù)對(duì)象Dm的annm進(jìn)行加權(quán)得到WPAnnm.對(duì)象與其KNN的距離越大，則該對(duì)象的權(quán)值WDm越大，離群對(duì)象的權(quán)值比非離群對(duì)象的權(quán)值大，從而離群對(duì)象的WPAnnm值大于非離群對(duì)象的WPAnnm值;WPAnnm值越大，離群對(duì)象與非離群對(duì)象的區(qū)分度越高，從而提高離群挖掘準(zhǔn)確率.WPAnnm的公式定義如下:

其中，annm表示List集合中對(duì)象Dm的k近鄰antihub分?jǐn)?shù)和，WDm表示對(duì)象Dm的k近鄰權(quán)值，WPAnnm表示List集合中對(duì)象的加權(quán)annm.

AntiHub2算法中，為計(jì)算數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，需人為設(shè)置α、step、p參數(shù)，且參數(shù)需帶入公式(3)進(jìn)行迭代循環(huán)才能得到滿意的離群結(jié)果集，離群挖掘準(zhǔn)確率低，時(shí)間復(fù)雜度高.采用近鄰數(shù)k及數(shù)據(jù)對(duì)象的RKNN計(jì)數(shù)作為區(qū)分度，可自適應(yīng)地調(diào)整ai及WPAnni在衡量對(duì)象的離群程度時(shí)的比例，避免了人為設(shè)置的參數(shù)對(duì)離群挖掘準(zhǔn)確率的影響.因而參照文獻(xiàn)［12，28］，將離群分?jǐn)?shù)的計(jì)算公式重新定義為:

公式(6)中，Dm為L(zhǎng)ist集合中的離群候選對(duì)象，count為對(duì)象Dm的逆k近鄰計(jì)數(shù)，k為近鄰個(gè)數(shù)，am為對(duì)象Dm的antihub分?jǐn)?shù)，WPAnnm為對(duì)象Dm的KNN加權(quán)antihub分?jǐn)?shù)和，avg(Dm，KNN)為對(duì)象Dm的KNN距離均值.

隨著數(shù)據(jù)維度的增大，Hubness現(xiàn)象(是指在高維數(shù)據(jù)空間中，數(shù)據(jù)對(duì)象的RKNN計(jì)數(shù)所服從的分布呈現(xiàn)明顯的右偏態(tài))使數(shù)據(jù)集產(chǎn)生更顯著的antihub對(duì)象(是指很少出現(xiàn)在數(shù)據(jù)集其它對(duì)象的KNN列表中的對(duì)象).維度越高，Hubness現(xiàn)象越顯著，進(jìn)而導(dǎo)致更明顯的antihub對(duì)象出現(xiàn)，而antihub對(duì)象與離群對(duì)象高度相關(guān)，可以作為離群候選對(duì)象［12］.公式(6)中，數(shù)據(jù)對(duì)象及其KNN對(duì)象的RKNN計(jì)數(shù)按照區(qū)分度比例求和，計(jì)算離群候選對(duì)象的離群分?jǐn)?shù);在高維數(shù)據(jù)空間中，對(duì)象的KNN距離均值從總體上衡量數(shù)據(jù)對(duì)象的離群程度，對(duì)數(shù)據(jù)對(duì)象的RKNN計(jì)數(shù)產(chǎn)生的影響較小，因而公式(6)適用于高維離群數(shù)據(jù)挖掘.

5 RKNNCWP算法描述

在高維離群數(shù)據(jù)挖掘中，若采用KNN方法，則需考察查詢對(duì)象與其KNN對(duì)象的聯(lián)系，已有的離群挖掘方法或只考慮數(shù)據(jù)對(duì)象i及其KNN對(duì)象的RKNN計(jì)數(shù)，或只考慮數(shù)據(jù)對(duì)象i與其KNN對(duì)象的距離，都沒(méi)有充分考慮對(duì)象與其KNN對(duì)象更多的聯(lián)系，故可將對(duì)象的RKNN計(jì)數(shù)及KNN距離結(jié)合起來(lái)，衡量數(shù)據(jù)對(duì)象的離群程度，該結(jié)合可提高正常數(shù)據(jù)對(duì)象與離群數(shù)據(jù)對(duì)象的區(qū)分度，有效地提高離群挖掘準(zhǔn)確率.利用權(quán)值剪枝策略將非離群對(duì)象剔除掉，得到離群對(duì)象候選集，計(jì)算候選集中對(duì)象的離群分?jǐn)?shù)，避免計(jì)算全部對(duì)象的離群分?jǐn)?shù)，從而提高離群挖掘效率.

利用RKNN計(jì)數(shù)與權(quán)值剪枝策略，計(jì)算數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)基本步驟:首先，查詢數(shù)據(jù)集中對(duì)象的RKNN，得到對(duì)象的RKNN計(jì)數(shù)，利用公式(1)計(jì)算對(duì)象i的antihub分?jǐn)?shù);其次，根據(jù)公式(4)得到數(shù)據(jù)集中對(duì)象的權(quán)值Wi，利用權(quán)值剪枝策略得到離群候選集List;再利用公式(5)，計(jì)算List集合中對(duì)象的加權(quán)antihub分?jǐn)?shù)和WPAnni;最后，根據(jù)公式(6)，得到離群候選對(duì)象的離群分?jǐn)?shù)，選擇離群分?jǐn)?shù)值較大的若干數(shù)據(jù)對(duì)象作為離群對(duì)象.

算法.RKNNCWP(Outlier Mining Based on Reverse KNN Counting and Weight Pruning)

輸入:數(shù)據(jù)集D中數(shù)據(jù)對(duì)象的KNN集合knnList，對(duì)象與其KNN的距離集合distList，數(shù)據(jù)集大小n，近鄰個(gè)數(shù)k

輸出:離群對(duì)象

RKNNCWP算法在計(jì)算數(shù)據(jù)對(duì)象的RKNN計(jì)數(shù)Nk(i)時(shí)，需找到對(duì)象的k個(gè)最近鄰居，因而需計(jì)算所有數(shù)據(jù)對(duì)象之間的距離，獲得Nk(i)的時(shí)間復(fù)雜度是O(n2)，其中n是數(shù)據(jù)集的大小.利用權(quán)值剪枝策略獲得離群候選集，并計(jì)算候選集中每個(gè)對(duì)象的離群分?jǐn)?shù)，因而整個(gè)算法的時(shí)間復(fù)雜度是O(n2).

6 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)環(huán)境:Intel(R)Core(TM)I5-3230M CPU 12GB內(nèi)存，Windows 7操作系統(tǒng)，Eclipse作為開(kāi)發(fā)平臺(tái)，采用Java語(yǔ)言作為開(kāi)發(fā)工具，實(shí)現(xiàn)了 RKNNCWP算法、WAntiHub算法［28］、AntiHub2算法［12］.實(shí)驗(yàn)數(shù)據(jù)包括人工數(shù)據(jù)集和 UCI標(biāo)準(zhǔn)數(shù)據(jù)集.

6.1 人工數(shù)據(jù)集

人工數(shù)據(jù)集是由隨機(jī)方法生成的標(biāo)準(zhǔn)正態(tài)數(shù)據(jù)，將數(shù)據(jù)集中與中心對(duì)象距離最遠(yuǎn)的1%對(duì)象乘以1.5，使這些對(duì)象距離中心對(duì)象更遠(yuǎn)，并作為人工數(shù)據(jù)集的離群對(duì)象.

6.1.1 數(shù)據(jù)量

圖1展示了數(shù)據(jù)維度為100維，近鄰數(shù)k為100時(shí)，數(shù)據(jù)量變化對(duì)算法性能的影響.圖1(a)表明隨著數(shù)據(jù)量的增大，RKNNCWP算法的準(zhǔn)確率遠(yuǎn)高于WAntiHub、AntiHub2算法，且準(zhǔn)確率波動(dòng)范圍較小，驗(yàn)證了算法的有效性.其主要原因是，數(shù)據(jù)量的增大，使得離群對(duì)象出現(xiàn)在其它對(duì)象KNN列表中的次數(shù)減少，antihub分?jǐn)?shù)較高，離群對(duì)象的權(quán)值變大，離群對(duì)象與正常數(shù)據(jù)對(duì)象的區(qū)分度更明顯，從而離群候選集List中存儲(chǔ)的離群對(duì)象較多，RKNNCWP算法的準(zhǔn)確率較高且波動(dòng)幅度較小.

圖1 數(shù)據(jù)量對(duì)算法準(zhǔn)確率和效率的影響Fig.1 Accuracy and efficiency impact of data amount

圖1 (b)表明隨著數(shù)據(jù)量的增大，RKNNCWP算法的執(zhí)行時(shí)間上升但效率高于WAntiHub、AntiHub2算法.其主要原因是數(shù)據(jù)量的增大，使得計(jì)算對(duì)象的Nk(i)時(shí)間變長(zhǎng)，算法的運(yùn)行時(shí)間呈上升趨勢(shì);權(quán)值剪枝策略將權(quán)值小于1的非離群候選對(duì)象剪枝掉，避免了計(jì)算全部對(duì)象的離群分?jǐn)?shù)，因而時(shí)間較WAntiHub、AntiHub2算法少.

6.1.2 維度

圖2展示了數(shù)據(jù)量為10000條，近鄰數(shù)k為100時(shí)，維度變化對(duì)算法性能的影響.圖2(a)表明在維度為50時(shí)，準(zhǔn)確率較低，并隨著維度的增加，RKNNCWP算法的準(zhǔn)確率呈上升趨勢(shì)且遠(yuǎn)高于WAntiHub、AntiHub2算法.其主要原因是隨著數(shù)據(jù)維度的增加，Hubness現(xiàn)象更加明顯，使得antihub對(duì)象較少出現(xiàn)在其它對(duì)象的KNN列表中，而antihub對(duì)象與離群對(duì)象高度相關(guān)，離群對(duì)象的antihub分?jǐn)?shù)比正常對(duì)象的高，正常對(duì)象與離群對(duì)象的區(qū)分度更明顯，因而算法的準(zhǔn)確率隨著維度的增加而更精確.正常對(duì)象的區(qū)分度，離群分?jǐn)?shù)公式以近鄰數(shù)k、Nk(i)作為區(qū)分度比例，因而RKNNCWP算法的準(zhǔn)確率更高且變化幅度較小.

圖2 維度對(duì)算法準(zhǔn)確率和效率的影響Fig.2 Accuracy and efficiency impact of dimension

圖3 k值對(duì)算法準(zhǔn)確率和效率的影響Fig.3 Accuracy and efficiency impact of k

圖3 (b)表明隨著k值的增大，RKNNCWP算法的執(zhí)行時(shí)間呈線性增長(zhǎng)，但仍比WAntiHub、AntiHub2算法效率高.其主要原因是在計(jì)算離群分?jǐn)?shù)之前，需計(jì)算每個(gè)對(duì)象的Nk(i)，而k值的增大，增加了RKNN對(duì)象的查詢時(shí)間，因而時(shí)間呈線性增長(zhǎng);RKNNCWP算法中的權(quán)值剪枝策略受k值的變化影響小，可剔除掉非離群對(duì)象，只需計(jì)算離群候選集中對(duì)象的離群分?jǐn)?shù)，從而離群挖掘的效率較高.

6.2 UCI數(shù)據(jù)集

使用 UCI數(shù)據(jù)集 HTRU2、Fertility、Statlog(Heart)、BreastCancerWisconsin(Diagnostic)、Seismic、Epileptic、Seizure、Ionosphere，比較 RKNNCWP 與 WAntiHub、AntiHub2算法在準(zhǔn)確率和效率方面的性能差異.為方便標(biāo)記，將數(shù)據(jù)集Statlog(Heart)、BreastCancerWisconsin(Diagnostic)、Epileptic Seizure 簡(jiǎn)記為 Statlog、Breast、EpilSei，所有 UCI數(shù)據(jù)集都進(jìn)行歸一化，選取各數(shù)據(jù)集中類別最少的一類數(shù)據(jù)對(duì)象作為離群對(duì)象.表1是各數(shù)據(jù)集的組成，參數(shù)k=(n為數(shù)據(jù)量).

表1 UCI數(shù)據(jù)集信息Table 1 UCI data sets

圖4展示了 RKNNCWP、WAntiHub、AntiHub2算法在不同數(shù)據(jù)集上的準(zhǔn)確率變化趨勢(shì).表明在低維數(shù)據(jù)集Fertility、Statlog和中維數(shù)據(jù)集Breast、Ionosphere上，RKNNCWP算法的準(zhǔn)確率遠(yuǎn)高于WAntiHub、AntiHub2算法.其主要原因是數(shù)據(jù)集的數(shù)據(jù)量較小，維度較低，數(shù)據(jù)對(duì)象與其KNN的距離易識(shí)別，離群對(duì)象的權(quán)值較大，離群數(shù)據(jù)候選集中存儲(chǔ)著真正的離群對(duì)象，因而離群挖掘準(zhǔn)確率較高.在低維數(shù)據(jù)集HTRU2、中維數(shù)據(jù)集Seismic上，RKNNCWP與WAntiHub算法的準(zhǔn)確率大體相同，但均高于AntiHub2算法，在高維數(shù)據(jù)集EpilSei上，RKNNCWP與AntiHub2算法的準(zhǔn)確率大致相同，其主要原因是數(shù)據(jù)集的數(shù)據(jù)量、屬性維度的增大，使用對(duì)象的KNN距離均值作為部分衡量對(duì)象離群程度的效果變差.

圖4 UCI數(shù)據(jù)集對(duì)算法準(zhǔn)確率的影響Fig.4 Accuracy impact of UCI data sets

圖5 展示了 RKNNCWP、WAntiHub、AntiHub2算法在不同數(shù)據(jù)集上的效率變化趨勢(shì).圖5(a)表明在中低維數(shù)據(jù)集Fertility、Statlog、Breast、Ionosphere 上，RKNNCWP 算法效率遠(yuǎn)高于WAntiHub、AntiHub2算法.其主要原因是數(shù)據(jù)集的數(shù)據(jù)量較小，計(jì)算對(duì)象的Nk(i)用時(shí)較少，權(quán)值剪枝策略剔除掉非離群對(duì)象，因而計(jì)算數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)時(shí)間減少.

圖5 UCI數(shù)據(jù)集對(duì)算法效率的影響Fig.5 Efficiency impact of UCI data sets

圖5 (b)表明RKNNCWP算法在數(shù)據(jù)集EpilSei、HTRU2、Seismic上的效率性能提升幅度較小，但仍高于WAntiHub、AntiHub2算法.其主要原因是數(shù)據(jù)集的數(shù)據(jù)量較大，計(jì)算對(duì)象的Nk(i)用時(shí)占據(jù)離群挖掘的大部分運(yùn)算時(shí)間，權(quán)值剪枝策略將非離群對(duì)象剔除掉，減少了數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)計(jì)算時(shí)間，而WAntiHub、AntiHub2算法需計(jì)算數(shù)據(jù)集中全部對(duì)象的離群分?jǐn)?shù)，所以RKNNCWP算法的離群挖掘效率較高.

7 結(jié)束語(yǔ)

本文針對(duì)高維數(shù)據(jù)空間中，由于“維度災(zāi)難”導(dǎo)致的離群挖掘效果變差，給出一種RKNN計(jì)數(shù)與k近鄰距離均值相結(jié)合的無(wú)監(jiān)督離群數(shù)據(jù)挖掘算法RKNNCWP.該算法使用權(quán)值剪枝策略剔除掉非離群對(duì)象，離群候選集中保存剪枝后的對(duì)象;利用RKNN計(jì)數(shù)與KNN距離均值，重新定義了離群分?jǐn)?shù)計(jì)算公式，并可有效地衡量離群候選集中數(shù)據(jù)對(duì)象的離群程度，其主要優(yōu)點(diǎn)是避免了設(shè)置WAntiHub和AntiHub2算法中的α、step和p參數(shù);最后使用人工數(shù)據(jù)集和UCI標(biāo)準(zhǔn)數(shù)據(jù)集，實(shí)驗(yàn)驗(yàn)證了該算法的正確性和有效性.為適應(yīng)海量數(shù)據(jù)的需求，RKNNCWP算法的并行化將是下一步的研究工作.