郭 峰，張繼福

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

1 引 言

離群數(shù)據(jù)是指明顯偏離其他數(shù)據(jù)，不滿(mǎn)足數(shù)據(jù)的一般模式或行為，與存在的其他數(shù)據(jù)不一致的數(shù)據(jù)，或者明顯偏離其它數(shù)據(jù)[1]，已經(jīng)廣泛應(yīng)用在天文光譜數(shù)據(jù)分析[2]、災(zāi)難天氣預(yù)報(bào)[3,4]、金融[5]、網(wǎng)絡(luò)入侵檢測(cè)[6]等領(lǐng)域.由于"維度災(zāi)難"的影響[7,8]，大多數(shù)在低維數(shù)據(jù)空間中表現(xiàn)良好的離群挖掘算法，在高維數(shù)據(jù)空間中效果變差，其主要原因是在高維數(shù)據(jù)空間中的數(shù)據(jù)變得稀疏，任意兩個(gè)數(shù)據(jù)對(duì)象之間的距離趨于一致，隱藏了真實(shí)離群數(shù)據(jù)，使每個(gè)數(shù)據(jù)對(duì)象都幾乎成為離群數(shù)據(jù)[9]，因而大多數(shù)離群數(shù)據(jù)挖掘方法無(wú)法適用于高維數(shù)據(jù)集.

k近鄰查詢(xún)?cè)陔x群數(shù)據(jù)挖掘中有著廣泛的應(yīng)用，樞紐現(xiàn)象(Hubness)是維度災(zāi)難中與k近鄰查詢(xún)相關(guān)的一個(gè)概念[10,11].樞紐現(xiàn)象是指在高維數(shù)據(jù)集中，任意數(shù)據(jù)對(duì)象i出現(xiàn)在其他數(shù)據(jù)對(duì)象k近鄰列表中的次數(shù)Nk(i)，其次數(shù)分布呈現(xiàn)明顯的右偏態(tài)，一些數(shù)據(jù)對(duì)象(antihubs，稱(chēng)為非樞紐點(diǎn))很少或者不出現(xiàn)在其他數(shù)據(jù)對(duì)象kNN列表中.隨著數(shù)據(jù)維度的增大，樞紐現(xiàn)象越來(lái)越明顯，且非樞紐點(diǎn)與高維數(shù)據(jù)集中的離群數(shù)據(jù)存在密切關(guān)聯(lián)關(guān)系[12].本文針對(duì)高維數(shù)據(jù)集，利用樞紐現(xiàn)象給出了一種基于樞紐現(xiàn)象和加權(quán)離群分?jǐn)?shù)的離群數(shù)據(jù)挖掘算法.該算法首先計(jì)算逆k近鄰，得到每個(gè)數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)；其次使用每個(gè)數(shù)據(jù)對(duì)象與其k近鄰點(diǎn)的距離，對(duì)其k近鄰點(diǎn)的離群分?jǐn)?shù)之和進(jìn)行加權(quán)，獲得加權(quán)k近鄰分?jǐn)?shù)和作為啟發(fā)性條件，并且多次隨機(jī)選擇區(qū)分度比例計(jì)算每個(gè)數(shù)據(jù)對(duì)象的區(qū)分度，將所得區(qū)分度平均值設(shè)為區(qū)分度閾值，大于區(qū)分度閾值則認(rèn)為所選取區(qū)分度比例是滿(mǎn)意值；然后將每個(gè)數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)與其加權(quán)k近鄰分?jǐn)?shù)和，按區(qū)分度比例滿(mǎn)意值求和，得到該對(duì)象的離群程度，選取離群程度最大的若干數(shù)據(jù)對(duì)象作為離群數(shù)據(jù).最后采用人工數(shù)據(jù)集和UCI 標(biāo)準(zhǔn)數(shù)據(jù)集，實(shí)驗(yàn)驗(yàn)證了該算法的有效性.

2 相關(guān)工作

傳統(tǒng)的離群數(shù)據(jù)挖掘方法，例如基于統(tǒng)計(jì)[13]、基于距離[14,15]、基于密度[16,17]、基于子空間[18,19]等，都會(huì)受到"維度災(zāi)難"的影響，在高維數(shù)據(jù)集中挖掘效果較差.k近鄰查詢(xún)是離群數(shù)據(jù)挖掘中的一種簡(jiǎn)單和基本步驟，影響著離群挖掘效果.

k近鄰查詢(xún)是指根據(jù)相似性度量在數(shù)據(jù)集中尋找或查詢(xún)與給定對(duì)象最鄰近的k個(gè)數(shù)據(jù)對(duì)象[20]，并廣泛應(yīng)用在離群數(shù)據(jù)挖掘中，其典型研究成果為：Ramaswamy等人[14]首先提出基于k近鄰的離群數(shù)據(jù)檢測(cè)算法，計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象與其第k近鄰之間的歐氏距離，距離最大的n個(gè)數(shù)據(jù)對(duì)象是離群數(shù)據(jù)，其缺點(diǎn)是距離相同時(shí)的離群數(shù)據(jù)判斷；Angiulli等人[15]將離群數(shù)據(jù)認(rèn)為是與其k近鄰距離之和越大的n個(gè)數(shù)據(jù)對(duì)象，并提出HilOut算法，其主要思想是利用空間填充曲線(xiàn)計(jì)算近似k近鄰，找到候選離群數(shù)據(jù)準(zhǔn)確計(jì)算進(jìn)行篩選.?stermark[21]提出Fuzzy KNN算法，將模糊knn與遺傳算法結(jié)合，在時(shí)間序列中進(jìn)行離群數(shù)據(jù)挖掘.

逆k近鄰查詢(xún)是指給定一個(gè)查詢(xún)數(shù)據(jù)對(duì)象，根據(jù)相似性度量返回一個(gè)結(jié)果集，該結(jié)果集中每一個(gè)數(shù)據(jù)對(duì)象都將該查詢(xún)數(shù)據(jù)對(duì)象作為其k近鄰[22].在逆k近鄰查詢(xún)中，查詢(xún)數(shù)據(jù)對(duì)象與數(shù)據(jù)集中其他數(shù)據(jù)對(duì)象相似性相關(guān)，具有低逆k近鄰值的數(shù)據(jù)對(duì)象很少或者不出現(xiàn)在數(shù)據(jù)集其他數(shù)據(jù)對(duì)象的k近鄰列表中，與離群數(shù)據(jù)存在關(guān)聯(lián)關(guān)系[12].逆k近鄰查詢(xún)廣泛應(yīng)用在在離群數(shù)據(jù)挖掘中，典型研究成果為：Hautamaki等人[23]提出了ODIN算法，該算法將任意一個(gè)數(shù)據(jù)對(duì)象i出現(xiàn)在其他數(shù)據(jù)對(duì)象k近鄰列表中的次數(shù)Nk(i)分?jǐn)?shù)被認(rèn)為是該數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，并分析了為何Nk(i)分?jǐn)?shù)能夠構(gòu)成有意義的離群分?jǐn)?shù)的原因，其缺點(diǎn)是需要人為設(shè)定離群分?jǐn)?shù)閾值，不適應(yīng)于未知數(shù)據(jù)分布的離群數(shù)據(jù)挖掘；Lin等人[24]提出了一種ODIN算法的變體，遍歷數(shù)據(jù)集中所有數(shù)據(jù)對(duì)象，將離群數(shù)據(jù)認(rèn)為是Nk(i)=0的數(shù)據(jù)對(duì)象，其缺點(diǎn)是離群挖掘結(jié)果受數(shù)據(jù)分布影響，包含在小簇中的離群數(shù)據(jù)可能被隱藏.

樞紐現(xiàn)象是"維度災(zāi)難"與逆k近鄰查詢(xún)相關(guān)的一個(gè)概念，并隨著數(shù)據(jù)維度的增大，樞紐現(xiàn)象越來(lái)越明顯.Radovanovic等人[12]首先分析了樞紐現(xiàn)象，并表明在低維和高維數(shù)據(jù)中，非樞紐點(diǎn)和離群數(shù)據(jù)均存在關(guān)聯(lián)關(guān)系；隨著空間維度的增大，樞紐現(xiàn)象使數(shù)據(jù)集產(chǎn)生更顯著的樞紐點(diǎn)和非樞紐點(diǎn)，并據(jù)此提出了適用于高維離群檢測(cè)的AntiHub算法和AntiHub2算法.AntiHub算法計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象的Nk(i)值，根據(jù)Nk(i)值計(jì)算離群分?jǐn)?shù).AntiHub2算法在A(yíng)ntiHub算法的基礎(chǔ)上引入啟發(fā)性信息，在計(jì)算一個(gè)數(shù)據(jù)對(duì)象的離群程度時(shí)除了考慮該數(shù)據(jù)對(duì)象的Nk(i)分?jǐn)?shù)還考慮其k近鄰數(shù)據(jù)對(duì)象的Nk分?jǐn)?shù)和，設(shè)置step參數(shù)進(jìn)行遍歷，找到最大區(qū)分度比例α，將當(dāng)前數(shù)據(jù)對(duì)象的Nk(i)分?jǐn)?shù)與其k近鄰數(shù)據(jù)對(duì)象的Nk分?jǐn)?shù)和按最大區(qū)分度比例α求和，得到離群程度，選取離群程度最大的若干數(shù)據(jù)對(duì)象作為離群數(shù)據(jù).

綜上所述，現(xiàn)有的基于逆k近鄰(RkNN)的離群挖掘算法均使用Nk(i)值，對(duì)Nk(i)值操作得到離群分?jǐn)?shù).ODIN算法和AntiHub算法對(duì)離群數(shù)據(jù)和正常數(shù)據(jù)對(duì)象的區(qū)分度不高，主要原因是Nk(i)本質(zhì)上是離散的，較大的k值選擇提高區(qū)分度但運(yùn)算代價(jià)昂貴.AntiHub2算法能夠在較小的k值選擇下獲得較高的區(qū)分度，其缺點(diǎn)是計(jì)算過(guò)程中需要設(shè)置參數(shù)進(jìn)行遍歷，時(shí)間復(fù)雜度高，同時(shí)也都沒(méi)有考慮距離因素.

3 樞紐現(xiàn)在與相關(guān)概念

3.1 樞紐現(xiàn)象

樞紐現(xiàn)象(Hubness)是指高維數(shù)據(jù)空間中，任意數(shù)據(jù)對(duì)象i出現(xiàn)在其他數(shù)據(jù)對(duì)象k近鄰列表中的次數(shù)Nk(i)的分布呈現(xiàn)出明顯的右偏態(tài)，且右偏程度會(huì)隨著數(shù)據(jù)維度的增加而增大，導(dǎo)致少量的樞紐點(diǎn)(hubs)非常頻繁地出現(xiàn)在數(shù)據(jù)集其他數(shù)據(jù)對(duì)象的kNN列表中.而另外一些非樞紐點(diǎn)(antihubs)很少或者不出現(xiàn)在數(shù)據(jù)集其他數(shù)據(jù)對(duì)象的kNN列表中.參照文獻(xiàn)[10]右偏程度的計(jì)算公式定義如下；

(1)

其中：μN(yùn)k和δNk分別表示Nk(i)的均值和標(biāo)準(zhǔn)差.當(dāng)SNk>0 時(shí)，SNk值越大，Nk(i)的右偏程度就越高，數(shù)據(jù)集的樞紐現(xiàn)象就越明顯.

樞紐現(xiàn)象與"維度災(zāi)難"相關(guān).當(dāng)高維數(shù)據(jù)出現(xiàn)"維度災(zāi)難"時(shí)，任意兩個(gè)數(shù)據(jù)對(duì)象之間的距離趨于一致，反映相似性差異的各種距離指標(biāo)效果變差，大部分?jǐn)?shù)據(jù)對(duì)象將落在以數(shù)據(jù)質(zhì)心為中心的超球體表面上[10].該特征使得顯著低于超球體表面的數(shù)據(jù)對(duì)象更有可能出現(xiàn)在其他數(shù)據(jù)對(duì)象的kNN列表中，即這些數(shù)據(jù)對(duì)象具有更高的Nk(i)值，被稱(chēng)為樞紐點(diǎn).與此對(duì)應(yīng)，顯著遠(yuǎn)離超球體表面的數(shù)據(jù)對(duì)象很少或者不出現(xiàn)在其他數(shù)據(jù)對(duì)象的kNN列表中，具有較低的Nk(i)值，被稱(chēng)為非樞紐點(diǎn).超球體表面附近的數(shù)據(jù)對(duì)象,即"規(guī)則"數(shù)據(jù)對(duì)象，傾向于具有接近k的Nk(i)期望.若數(shù)據(jù)集來(lái)自多個(gè)分布，那么大部分?jǐn)?shù)據(jù)點(diǎn)將落在以相應(yīng)分布的質(zhì)心為中心的超球面上.

3.2 相關(guān)概念

在文獻(xiàn)[12]中，將給定數(shù)據(jù)對(duì)象i的Nk(i)值歸一化，并計(jì)算其離群分?jǐn)?shù)，計(jì)算公式定義如下：

(2)

其中：ai為數(shù)據(jù)對(duì)象i的離群分?jǐn)?shù).當(dāng)Nk(i)=0時(shí)，由公式(2)也可使得數(shù)據(jù)對(duì)象i獲得有意義的離群分?jǐn)?shù).計(jì)算每個(gè)數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，選取離群分?jǐn)?shù)最高的若干個(gè)數(shù)據(jù)對(duì)象，并將其視為離群數(shù)據(jù).

在文獻(xiàn)[12]中，引入啟發(fā)性信息，在計(jì)算數(shù)據(jù)對(duì)象i的離群程度時(shí)，除了考慮其N(xiāo)k(i)分?jǐn)?shù)還考慮其k近鄰數(shù)據(jù)對(duì)象的Nk分?jǐn)?shù)和.k近鄰Nk分?jǐn)?shù)和(anni)的計(jì)算公式定義如下：

anni=∑j∈NN(k,i)aj

(3)

其中：anni為數(shù)據(jù)對(duì)象i的k近鄰Nk分?jǐn)?shù)和，數(shù)據(jù)對(duì)象j為其k近鄰，aj為數(shù)據(jù)對(duì)象j的Nk(j)分?jǐn)?shù).數(shù)據(jù)對(duì)象i的離群程度計(jì)算公式定義如下：

cti=(1-α)·ai+α·anni

(4)

其中：cti為數(shù)據(jù)對(duì)象i的離群程度，ai為其N(xiāo)k(i)分?jǐn)?shù)，anni為其k近鄰Nk分?jǐn)?shù)和，α為最大區(qū)分度比例.計(jì)算每個(gè)數(shù)據(jù)對(duì)象的離群程度，選取離群程度最大的若干數(shù)據(jù)對(duì)象作為離群數(shù)據(jù).

4 距離信息加權(quán)與區(qū)分度滿(mǎn)意值

4.1 距離信息加權(quán)

指根據(jù)文獻(xiàn)[15]，離群數(shù)據(jù)是全體數(shù)據(jù)對(duì)象中與其k近鄰平均距離最大的n個(gè)數(shù)據(jù)對(duì)象.現(xiàn)有的基于逆k近鄰的離群挖掘算法都未考慮距離因素，因此引入距離信息作為權(quán)值，提高其準(zhǔn)確率.k近鄰距離定義為：給定數(shù)據(jù)對(duì)象與其k近鄰數(shù)據(jù)對(duì)象之間歐氏距離的平均值.k近鄰權(quán)值定義為：給定數(shù)據(jù)對(duì)象的k近鄰距離與數(shù)據(jù)集k近鄰距離平均值的比值，其計(jì)算公式定義如下：

(5)

其中：wi為數(shù)據(jù)對(duì)象i的k近鄰權(quán)值,averDisk(i)為其k近鄰距離，averDisk為數(shù)據(jù)集k近鄰距離平均值.

根據(jù)公式(2)(3)，計(jì)算數(shù)據(jù)對(duì)象i的歸一化Nk(i)分?jǐn)?shù)ai和其k近鄰Nk分?jǐn)?shù)和anni.ai值較高的數(shù)據(jù)對(duì)象Nk(i)值較低，較少或者不出現(xiàn)在數(shù)據(jù)集其他數(shù)據(jù)的k近鄰列表中，并與離群數(shù)據(jù)存在關(guān)聯(lián)關(guān)系，因此可以使用ai計(jì)算離群分?jǐn)?shù).因?yàn)閍i在本質(zhì)上離散，對(duì)離群數(shù)據(jù)與正常數(shù)據(jù)區(qū)分度低，引入anni作為啟發(fā)性條件能夠提高算法區(qū)分度.對(duì)于給定數(shù)據(jù)對(duì)象i，使用其k距離權(quán)值對(duì)其k近鄰Nk分?jǐn)?shù)和anni進(jìn)行加權(quán)，得到加權(quán)k近鄰Nk分?jǐn)?shù)和(Wanni)，其計(jì)算公式定義如下：

Wanni=anni·wi

(6)

其中：Wanni為數(shù)據(jù)對(duì)象i加權(quán)k近鄰Nk分?jǐn)?shù)和，anni為其k近鄰Nk分?jǐn)?shù)和，wi為其k近鄰權(quán)值.參照文獻(xiàn)[12],離群程度計(jì)算公式可重新定義為：

cti=(1-α′)·ai+α′·Wanni

(7)

其中：cti為數(shù)據(jù)對(duì)象i的離群程度，ai為其N(xiāo)k(i)分?jǐn)?shù)，Wanni為其加權(quán)k近鄰Nk分?jǐn)?shù)和，α′為區(qū)分度比例滿(mǎn)意值.

當(dāng)數(shù)據(jù)對(duì)象i為離群數(shù)據(jù)時(shí)，數(shù)據(jù)對(duì)象i的k近鄰距離大于數(shù)據(jù)集k近鄰距離平均值，其k近鄰權(quán)值wi>1，所對(duì)應(yīng)加權(quán)k近鄰Nk分?jǐn)?shù)和Wanni大于k近鄰Nk分?jǐn)?shù)和anni.根據(jù)公式(4)(7)，對(duì)于離群數(shù)據(jù)，使用加權(quán)k近鄰Nk分?jǐn)?shù)和可獲得比文獻(xiàn)[12]高的離群分?jǐn)?shù)，提高正常數(shù)據(jù)對(duì)象和離群數(shù)據(jù)的區(qū)分度.利用信息作對(duì)離群分?jǐn)?shù)進(jìn)行加權(quán)還具有以下優(yōu)點(diǎn)：當(dāng)數(shù)據(jù)集不滿(mǎn)足任何特定分布模型時(shí)，距離信息仍能有效地發(fā)現(xiàn)離群數(shù)據(jù)；k近鄰查詢(xún)，可獲得所有數(shù)據(jù)對(duì)象的k近鄰距離，不需要進(jìn)行額外計(jì)算.

4.2 區(qū)分度滿(mǎn)意值

使用區(qū)分度閾值分支判斷可以有效減少循環(huán)次數(shù)，提高算法效率.為適用于數(shù)據(jù)分布未知的數(shù)據(jù)集，自動(dòng)生成區(qū)分度閾，根據(jù)區(qū)分度閾值判斷區(qū)分度比例滿(mǎn)意值，并根據(jù)公式(7)使用區(qū)分度比例滿(mǎn)意值計(jì)算離群程度.自動(dòng)生成區(qū)分度閾值用于分支判斷，使用區(qū)分度比例滿(mǎn)意解α′計(jì)算離群程度的步驟如下：

從α′∈(0,step,2·step，…，1)中多次隨機(jī)選取α′，每個(gè)α^′值調(diào)用局部函數(shù)discScore(y,ρ)計(jì)算對(duì)應(yīng)區(qū)分度，多次實(shí)驗(yàn)所獲得區(qū)分度平均值設(shè)為區(qū)分度閾值Threshold；繼續(xù)從α′∈(0,step,2·step，…，1) 中多次隨機(jī)選取α′，如果所選取α′對(duì)應(yīng)區(qū)分度大于區(qū)分度閾值，則認(rèn)為所選取α′為一個(gè)區(qū)分度比例滿(mǎn)意值；使用區(qū)分度比例滿(mǎn)意值α′計(jì)算離群程度.

計(jì)算區(qū)分度滿(mǎn)意值α′的過(guò)程是在所有α取值中隨機(jī)選取有限個(gè)α′，根據(jù)區(qū)分度閾值判斷是否為區(qū)分度比例滿(mǎn)意值α′.當(dāng)搜索參數(shù)step設(shè)置較小時(shí)，使用區(qū)分度滿(mǎn)意值α′可以減少算法循環(huán)次數(shù).在計(jì)算區(qū)分度比例滿(mǎn)意值α′的過(guò)程中，采用隨機(jī)抽樣，計(jì)算得到的區(qū)分度比例滿(mǎn)意值α′具有隨機(jī)性，因此m次隨機(jī)選擇α′，計(jì)算區(qū)分度比例直到獲得n個(gè)區(qū)分度比例滿(mǎn)意值.

5 離群數(shù)據(jù)挖掘算法描述

綜上所述，引入距離信息對(duì)離群分?jǐn)?shù)加權(quán)提高離群數(shù)據(jù)與正常數(shù)據(jù)的區(qū)分度,提高離群數(shù)據(jù)挖掘效果；使用區(qū)分度滿(mǎn)意值分支判斷減少循環(huán)次數(shù)，提高了離群數(shù)據(jù)挖掘效率.利用距離信息和區(qū)分度比例滿(mǎn)意值，計(jì)算離群程度的基本步驟：首先對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)對(duì)象進(jìn)行逆k近鄰查詢(xún)，得到每個(gè)數(shù)據(jù)對(duì)象出現(xiàn)在其他數(shù)據(jù)對(duì)象k近鄰列表中的次數(shù)Nk，根據(jù)公式(2)、(3)計(jì)算數(shù)據(jù)對(duì)象i的Nk(i)分?jǐn)?shù)與其k近鄰Nk分?jǐn)?shù)和；其次使用每個(gè)數(shù)據(jù)對(duì)象的k近鄰權(quán)值對(duì)其k近鄰Nk分?jǐn)?shù)和加權(quán)，得到加權(quán)k近鄰Nk分?jǐn)?shù)和；然后多次隨機(jī)選擇α′值計(jì)算其區(qū)分度，將所得區(qū)分度平均值設(shè)為區(qū)分度閾值，大于區(qū)分度閾值則認(rèn)為所選取α′是滿(mǎn)意值；最后使用公式(7)計(jì)算每個(gè)數(shù)據(jù)對(duì)象的離群程度，選取離群程度最高的若干個(gè)數(shù)據(jù)對(duì)象，并將其視為離群數(shù)據(jù).其算法描述如下：

算法：WAntiHub(Weighted Anti-Hubness for Unsupervised Distance-Based Outlier Detection)

輸入：數(shù)據(jù)集D中每個(gè)數(shù)據(jù)的k近鄰；采樣比例ρ∈(0,1]；搜索參數(shù)step∈(0,1]

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

1)n=數(shù)據(jù)集D的數(shù)據(jù)個(gè)數(shù)；

2)for(i=0;i

3) 根據(jù)公式(2)計(jì)算數(shù)據(jù)對(duì)象i的歸一化Nk(i)分?jǐn)?shù)ai；

4) 使用ai，根據(jù)公式(3)計(jì)算數(shù)據(jù)對(duì)象i的k近鄰Nk分?jǐn)?shù)和anni；

5) 根據(jù)公式(5)計(jì)算數(shù)據(jù)對(duì)象i的k近鄰權(quán)值wi；

6) 使用wi和anni，根據(jù)公式(6)計(jì)算數(shù)據(jù)對(duì)象i的加權(quán)加權(quán)k近鄰Nk分?jǐn)?shù)和Wanni；

7)end for；

8)α從(0,step,2·step，…，1)中隨機(jī)取值，得到α1…αm；

9)for(j=0;j

10) for(i=0;i

11) 根據(jù)公式(7)，使用α1…αm計(jì)算數(shù)據(jù)對(duì)象i的離群程度cti；

12) end for；

13) cdiscj=discScore(cti, ρ)；//調(diào)用局部函數(shù)計(jì)算α1…αm對(duì)應(yīng)區(qū)分度

14)end for；

15)Threshold=(∑1jcdiscj)/m ； //計(jì)算區(qū)分度閾值Threshold

16)α′從(0,step,2·step，…，1)中隨機(jī)取值，得到α1′…αq′；

17)for(j=0;j

18) for(i=0;i

19) 根據(jù)公式(7)使用α′計(jì)算數(shù)據(jù)對(duì)象i的離群程度cti；

20) end for；

21) cdisc=discScore(cti, ρ)；//調(diào)用局部函數(shù)計(jì)算α′對(duì)應(yīng)區(qū)分度

22) if cdisc> Threshold；//根據(jù)閾值判斷區(qū)分度比例滿(mǎn)意值α′

23) 記錄所對(duì)應(yīng)的區(qū)分度比例滿(mǎn)意值α′；

24) if 已經(jīng)保存了s個(gè)α′；

25) end if；

26)end for；

28)for(i=0;i

29) 根據(jù)公式(7)使用區(qū)分度比例滿(mǎn)意值α^′計(jì)算離群程度

30)end for；

31)End WAntiHub

算法步驟說(shuō)明：

1)局部函數(shù)：discScore(y,ρ)：對(duì)于y∈Rn和ρ∈(0,1]，根據(jù)采樣比例找到y(tǒng)中值最小的「nρ?個(gè)值，進(jìn)行去重操作，將非重元素個(gè)數(shù)除以「nρ?作為輸出.

2)在上述算法中2)-7)計(jì)算數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象Nk(i)歸一化分?jǐn)?shù)ai，使用k近鄰權(quán)值對(duì)其k近鄰Nk分?jǐn)?shù)和進(jìn)行加權(quán)，得到加權(quán)k近鄰分?jǐn)?shù)和Wanni.8)-15)多次隨機(jī)選擇α值計(jì)算區(qū)分度閾值Threshold.16)-27)多次隨機(jī)選擇α′，使用區(qū)分度閾值判斷，獲得區(qū)分度比例滿(mǎn)意值α′.28)-30)使用區(qū)分度比例滿(mǎn)意值α′計(jì)算每個(gè)數(shù)據(jù)對(duì)象的離群程度，選取離群程度最高的若干個(gè)數(shù)據(jù)對(duì)象，并將其視為離群數(shù)據(jù).

算法復(fù)雜性分析：

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

實(shí)驗(yàn)環(huán)境：Inter Core(TM) i7-6700HQ CPU 16GB內(nèi)存，windows 10操作系統(tǒng)，eclipse作為開(kāi)發(fā)平臺(tái)，采用Java語(yǔ)言實(shí)現(xiàn)了WAntiHub算法和AntiHub2算法[12].實(shí)驗(yàn)數(shù)據(jù)包括人工數(shù)據(jù)集和UCI數(shù)據(jù)集.

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

人工數(shù)據(jù)采用隨機(jī)生成正態(tài)數(shù)據(jù)，并將數(shù)據(jù)集中的1%元素乘以1.5倍作為離群數(shù)據(jù).

1)近鄰數(shù)k

圖1 近鄰數(shù)k對(duì)算法的影響Fig.1 Influence of the neighbor number k on the algorithm

由圖1(b)表明隨著k值的增大，WAntiHub算法耗時(shí)呈現(xiàn)線(xiàn)性增長(zhǎng).主要原因是Wantihub算法和Antihub2算法都使用(加權(quán))k近鄰Nk分?jǐn)?shù)和，k值越大，計(jì)算(加權(quán))k近鄰Nk分?jǐn)?shù)和的數(shù)據(jù)也隨之增多.對(duì)所有的k值，WantiHub算法的效率高于A(yíng)ntiHub2算法，主要原因是WAntiHub算法使用區(qū)分度比例滿(mǎn)意值α′代替最大區(qū)分度比例α用于計(jì)算離群程度，分支判斷減少了循環(huán)次數(shù).

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

圖2是采用100維數(shù)據(jù)的實(shí)驗(yàn)結(jié)果，由圖2(a)表明隨著數(shù)據(jù)量的增大，WAntiHub算法的準(zhǔn)確度基本不變，AntiHub2算法的準(zhǔn)確度有緩慢的提高.主要原因是數(shù)據(jù)量的增加使數(shù)據(jù)更加聚集，樞紐現(xiàn)象程度加深，非樞紐點(diǎn)更加顯著.對(duì)所有數(shù)據(jù)量，WAntiHub算法的準(zhǔn)確度高于A(yíng)ntiHub2算法.

圖2 數(shù)據(jù)量對(duì)算法的影響Fig.2 Influence of the amount on the algorithm

由圖2(b)表明隨著數(shù)據(jù)量的增大，WantiHub算法耗時(shí)呈指數(shù)型增長(zhǎng).主要原因是WantiHub算法的時(shí)間復(fù)雜度為O(n2·t).對(duì)所有的數(shù)據(jù)量，WAntiHub算法的效率高于A(yíng)ntiHub2算法.

3)屬性維度

圖3是采用10000條數(shù)據(jù)，k=100的實(shí)驗(yàn)結(jié)果.由圖3(a)表明隨著屬性維度的增大，WAntiHub2算法和AntiHub2算法的準(zhǔn)確率提升.主要原因是數(shù)據(jù)屬性維度增大使樞紐現(xiàn)象程度加深，非樞紐點(diǎn)更加顯著.AntiHub2算法對(duì)準(zhǔn)確率的提升高于WAntiHub算法，其主要原因是屬性維度增大使數(shù)據(jù)集中任意兩個(gè)數(shù)據(jù)對(duì)象之間的距離趨于一致，使基于距離信息加權(quán)的效果變差.對(duì)所有的屬性維度，WantiHub算法的準(zhǔn)確率高于A(yíng)ntiHub2算法.

圖3 屬性維度對(duì)算法的影響Fig.3 Influence of the dimension on the algorithm

由圖3(b)表明對(duì)所有的屬性維度，WatiHub算法運(yùn)算時(shí)間基本一致.主要原因是WantiHub算法使用k近鄰查詢(xún)結(jié)果作為輸入數(shù)據(jù)，對(duì)屬性維度不同的數(shù)據(jù)集，其k近鄰查詢(xún)結(jié)果所包含的數(shù)據(jù)量基本一致.對(duì)所有的維度，WAntiHub算法的效率高于A(yíng)ntiHub2算法.

4)采樣比例ρ

圖4是采用10000條100維數(shù)據(jù),k=100的實(shí)驗(yàn)結(jié)果.由圖4(a)表明采樣比例ρ對(duì)WAntiHub算法精確度影響較小.且對(duì)所有的ρ值，WAntiHub算法的準(zhǔn)確率高于A(yíng)ntiHub2算法.

圖4 采樣比例ρ對(duì)算法的影響Fig.4 Influence of the sampling ratio on the algorithm

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

使用UCI數(shù)據(jù)集Yeast，HTRU2，Ionosphere，ESRDS驗(yàn)證算法準(zhǔn)確率和效率，所有UCI數(shù)據(jù)都轉(zhuǎn)化為標(biāo)準(zhǔn)分?jǐn)?shù).

表1 UCI數(shù)據(jù)集信息Table 1 UCI dataset information

圖5 UCI數(shù)據(jù)集對(duì)算準(zhǔn)確率的影響Fig.5 Influence of algorithm accuracy on the UCI dataset

由圖5表明在所有UCI數(shù)據(jù)集上，WAntiHub算法的準(zhǔn)確率高于A(yíng)ntiHub2算法，WAntiHub算法對(duì)低維數(shù)據(jù)集Yeast、HTRU_2和中維數(shù)據(jù)集HTRU_2準(zhǔn)確率提高較多，對(duì)高維數(shù)據(jù)集ESRDS準(zhǔn)確度提升較小.主要原因是隨著屬性維度的增大，使用距離信息加權(quán)的效果變差.

由圖6(a)表明，WantiHub算法對(duì)Yeast和Ionosphere數(shù)據(jù)集效率提升較大，主要原因是Yeast和Ionosphere數(shù)據(jù)集數(shù)據(jù)量較小，遍歷找到最大區(qū)分度比例α占總運(yùn)算時(shí)間比例大，使用區(qū)分度閾值分支判斷有效減少循環(huán)次數(shù).圖6(b)顯示對(duì)HTRU_2和ESRDS數(shù)據(jù)集，效率提升較小.主要原因是數(shù)據(jù)集數(shù)據(jù)量較大，計(jì)算每個(gè)數(shù)據(jù)對(duì)象的Nk(i)值占總運(yùn)算時(shí)間比例大.在所有UCI數(shù)據(jù)集上，WAntiHub算法效率提高.

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

針對(duì)高維數(shù)據(jù)中維度災(zāi)難導(dǎo)致離群數(shù)據(jù)挖掘效果變差，利用逆k近鄰中出現(xiàn)的樞紐現(xiàn)象，給出了一種基于樞紐現(xiàn)象和加權(quán)離群分?jǐn)?shù)的離群數(shù)據(jù)挖掘算法WAntiHub.該算法引入距離信息對(duì)離群分?jǐn)?shù)加權(quán)，提高離群數(shù)據(jù)挖掘效果；使用區(qū)分度滿(mǎn)意值分支判斷減少循環(huán)次數(shù)，提高了離群數(shù)據(jù)挖掘效率.使用人工數(shù)據(jù)和 UCI 數(shù)據(jù)集，實(shí)驗(yàn)驗(yàn)證了該算法的有效性.為適應(yīng)海量數(shù)據(jù)的需求，WAntiHub算法的并行化將是下一步的研究工作.

圖6 UCI數(shù)據(jù)集對(duì)算法效率的影響Fig.6 Influence of algorithm efficiency on the UCI dataset