李橋，周瑩蓮，黃勝，馬翔

湖南涉外經(jīng)濟(jì)學(xué)院信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410205

對(duì)隨機(jī)投影算法的離群數(shù)據(jù)挖掘技術(shù)研究

李橋，周瑩蓮，黃勝，馬翔

湖南涉外經(jīng)濟(jì)學(xué)院信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410205

1 引言

離群數(shù)據(jù)挖掘技術(shù)廣泛應(yīng)用于信用卡欺詐檢測(cè)、網(wǎng)絡(luò)流量入侵檢測(cè)、視頻監(jiān)控異常行為檢測(cè)等領(lǐng)域，因而成為數(shù)據(jù)挖掘領(lǐng)域的一項(xiàng)重要課題得到人們的深入研究。離群數(shù)據(jù)檢測(cè)就是發(fā)現(xiàn)嚴(yán)重偏離數(shù)據(jù)總體分布范圍的離群數(shù)據(jù)。由于與數(shù)據(jù)總體分布情況不同，因此這些數(shù)據(jù)可以看成是可疑數(shù)據(jù)。例如，對(duì)于信用卡詐騙檢測(cè)問(wèn)題，數(shù)據(jù)集包括卡片主人的交易信息。交易記錄記載了每名用戶消費(fèi)行為的卡片使用情況。如果卡片被盜，用戶消費(fèi)行為往往會(huì)發(fā)生變化。如果交易記錄消費(fèi)額度高、消費(fèi)頻率高、消費(fèi)項(xiàng)目重復(fù)，則可認(rèn)定出現(xiàn)異常消費(fèi)模式。

離群數(shù)據(jù)挖掘技術(shù)多應(yīng)用于超高維數(shù)據(jù)領(lǐng)域[1]。例如，信用卡數(shù)據(jù)集交易記錄有100多個(gè)屬性。為了對(duì)視頻監(jiān)控進(jìn)行異常行為軌跡檢測(cè)，必須處理連續(xù)視頻幀的超高維像素特征。由于眾所周知的“維度災(zāi)難”問(wèn)題[2]，當(dāng)前大多數(shù)算法都或多或少地需要在全維空間對(duì)歐幾里德距離進(jìn)行考察，因此效果欠佳。傳統(tǒng)的基于距離[3]和基于密度[4]的離群數(shù)據(jù)檢測(cè)算法，需要進(jìn)行高維數(shù)據(jù)最近鄰搜索，因此計(jì)算復(fù)雜度較大。此外，數(shù)據(jù)維度越高，最近鄰和最遠(yuǎn)鄰數(shù)據(jù)就越難以區(qū)分。此時(shí)，如果還是根據(jù)高維空間距離和最近鄰概念來(lái)考察數(shù)據(jù)的相鄰點(diǎn)，就會(huì)出現(xiàn)大部分?jǐn)?shù)據(jù)都被判定為離群數(shù)據(jù)的情況[5]。

本文提出一種近線性時(shí)間算法，對(duì)各數(shù)據(jù)對(duì)象的角度方差進(jìn)行近似。對(duì)d維空間的n組數(shù)據(jù)，本文算法的計(jì)算時(shí)間為O(nlbn(d+lbn))，可輸出各數(shù)據(jù)對(duì)象角度方差非偏估計(jì)量。本文主要技術(shù)創(chuàng)新就是將隨機(jī)超平面投影[6]和乘積域AMS Sketch[7]結(jié)合在一起，使得可以將原方法的三次方時(shí)間復(fù)雜度降低到本文近似方法的近線性復(fù)雜度。本文算法另一個(gè)優(yōu)點(diǎn)就是支持并行處理。實(shí)際上，本文運(yùn)行時(shí)間并行加速比可以達(dá)到準(zhǔn)線性（根據(jù)使用的處理器數(shù)量而定）水平。還對(duì)近似方法進(jìn)行了理論分析，以保證本文估計(jì)算法的可靠性。基于實(shí)際數(shù)據(jù)和仿真數(shù)據(jù)的實(shí)驗(yàn)表明，本文方法應(yīng)用于超高維數(shù)據(jù)，效率高、可擴(kuò)展性強(qiáng)。

2 相關(guān)工作

對(duì)離群數(shù)據(jù)挖掘，一個(gè)良好的離群指標(biāo)是保證數(shù)據(jù)挖掘效果和效率的關(guān)鍵。人們提出了大量離群指標(biāo)，包括全局和局部離群模型。一般而言，全局離群模型對(duì)總體數(shù)據(jù)加以考慮，局部離群模型只考慮各數(shù)據(jù)對(duì)象周邊部分相鄰區(qū)域。

Knox和Ng等人[8]定義了一種簡(jiǎn)單直觀的基于距離的離群模型，該模型是數(shù)據(jù)庫(kù)背景下最早提出的全局離群模型。參數(shù)k和λ條件下的離群數(shù)據(jù)是指距離λ范圍內(nèi)近鄰數(shù)量少于k個(gè)的數(shù)據(jù)對(duì)象。文獻(xiàn)[3]提出了另一種基于距離的算法，該算法將數(shù)據(jù)對(duì)象相對(duì)其第kth個(gè)最近鄰數(shù)據(jù)的距離作為該對(duì)象的離群分值，然后將分值最高的m個(gè)對(duì)象作為離群程度最高的m個(gè)離群數(shù)據(jù)。為了避免嵌套循環(huán)最壞情況下的二次方計(jì)算復(fù)雜度問(wèn)題，該文獻(xiàn)提出了幾種關(guān)鍵的優(yōu)化方法。根據(jù)不同的修剪策略，這些優(yōu)化方法可以分為多種類別，比如說(shuō)近似最近鄰搜索[3]、數(shù)據(jù)分區(qū)策略[3]和數(shù)據(jù)分級(jí)策略[9]。雖然這些優(yōu)化方法可以帶來(lái)一定程度的性能提升，但是可拓展性較差，尤其是當(dāng)維度或數(shù)據(jù)規(guī)模變大或數(shù)據(jù)對(duì)象變得非常稀疏時(shí)，這些方法的效率將會(huì)顯著下降。

全局模型在基于相鄰數(shù)據(jù)點(diǎn)距離來(lái)檢測(cè)離群數(shù)據(jù)時(shí)，考慮了整個(gè)數(shù)據(jù)集，而基于密度的局部模型根據(jù)相鄰數(shù)據(jù)點(diǎn)密度來(lái)評(píng)估各數(shù)據(jù)對(duì)象的離群程度。在許多應(yīng)用中，局部離群模型有多個(gè)優(yōu)點(diǎn)，比如檢測(cè)到不同密度的全局和局部離群數(shù)據(jù)，確定正常數(shù)據(jù)和異常數(shù)據(jù)間的分界線。這種類型的方法根據(jù)k-最近鄰局部密度[10]或ε-近鄰多粒度偏差[4]為每個(gè)數(shù)據(jù)對(duì)象分配一個(gè)局部離群因子來(lái)描述該對(duì)象的離群程度。實(shí)際上，這些方法都需要為每個(gè)數(shù)據(jù)對(duì)象尋找最近鄰，經(jīng)常使用索引數(shù)據(jù)結(jié)構(gòu)來(lái)提升性能。因此，無(wú)法滿足高維離群數(shù)據(jù)挖掘要求。

因?yàn)榛诰嚯x或最近鄰數(shù)據(jù)的指標(biāo)在高維空間中可能沒(méi)有實(shí)質(zhì)性意義，最近人們利用子空間投影方法進(jìn)行離群分層[11]。換句話說(shuō)，這些方法只將數(shù)據(jù)對(duì)象的部分屬性作為子空間加以考慮。然而，這些方法要么難以選擇有意義的子空間，要么存在計(jì)算復(fù)雜度隨著數(shù)據(jù)維度呈指數(shù)增長(zhǎng)問(wèn)題。如上所述，Kriegel等人[5]為高維離群數(shù)據(jù)檢測(cè)提出一種健壯的基于角度的考察指標(biāo)。該方法根據(jù)數(shù)據(jù)對(duì)象與其他對(duì)象的角度差異來(lái)評(píng)估各數(shù)據(jù)對(duì)象的離群程度。數(shù)據(jù)對(duì)象與其他數(shù)據(jù)對(duì)象的角度差異越小，成為離群數(shù)據(jù)的概率越大。因?yàn)殡S著數(shù)據(jù)維度上升，數(shù)據(jù)對(duì)象間的角度頻譜比距離更加穩(wěn)定，因此該方法即使面對(duì)高維數(shù)據(jù)，性能也不會(huì)下降。然而，該方法的原型和近似方法的計(jì)算復(fù)雜度分別為三次方和二次方，均存在計(jì)算復(fù)雜度過(guò)高問(wèn)題。

3 本文方法

3.1 基于角度的離群數(shù)據(jù)檢測(cè)（ABOD）

如上所述，基于距離或近鄰理念的高維數(shù)據(jù)離群挖掘模式是不可行的。文獻(xiàn)[5]提出一種新的基于數(shù)據(jù)點(diǎn)角度差異的離群點(diǎn)檢測(cè)算法，以降低“維度災(zāi)難”影響。圖1顯示了三種數(shù)據(jù)點(diǎn)的角度差異，其中Outlier是離群點(diǎn)；border point是邊界點(diǎn)；inner point是內(nèi)部點(diǎn)?？梢钥吹?，該群數(shù)據(jù)點(diǎn)中，邊沿點(diǎn)和內(nèi)部點(diǎn)的角度差異較大，離群點(diǎn)的角度差異較小。換句話說(shuō)，一個(gè)點(diǎn)相對(duì)其他點(diǎn)的角度差異越小，該點(diǎn)為離群點(diǎn)的概率越大。這是因?yàn)槲挥谌簝?nèi)的點(diǎn)被位于其他方向上的其他點(diǎn)包圍，而群外的點(diǎn)只在部分方向上存在。因此，使用角度方差（VOA）作為離群因子來(lái)評(píng)估數(shù)據(jù)集中各點(diǎn)的離群程度。文獻(xiàn)[5]方法沒(méi)有直接提出角度方差，而是使用經(jīng)過(guò)數(shù)據(jù)點(diǎn)相應(yīng)距離加權(quán)的角度余弦方差代替。鑒于“維度災(zāi)難”影響，加權(quán)因子對(duì)高維數(shù)據(jù)的意義越來(lái)越低。希望對(duì)于高維數(shù)據(jù)，基于余弦譜方差的離群點(diǎn)分級(jí)（不論有沒(méi)有加權(quán)因子）和基于角度頻譜方差的離群點(diǎn)分級(jí)，能夠展現(xiàn)出一定的相似性。因此，利用角度方差，定義了基于角度的離群因子：

很顯然，VOA指標(biāo)不含參數(shù)，因此適宜無(wú)監(jiān)督離群檢測(cè)算法。ABOD原型算法計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的VOA，并返回VOA最小的m個(gè)點(diǎn)作為離群點(diǎn)。然而，原型算法的計(jì)算復(fù)雜度為O(dn3)。三次方的計(jì)算復(fù)雜度意味著超大規(guī)模數(shù)據(jù)集的離群點(diǎn)挖掘?qū)?huì)非常困難。

圖1 不同類型的點(diǎn)的角度差異

3.2 算法主要思路

本文算法的主要思路是，高效計(jì)算出各數(shù)據(jù)點(diǎn)的角度方差無(wú)偏估計(jì)值。換句話說(shuō)，估計(jì)的期望值等于角度方差，還將表明，角度方差圍繞期望值分布。于是，這些估計(jì)值可用于對(duì)點(diǎn)分級(jí)。角度方差最小的m個(gè)點(diǎn)判定為數(shù)據(jù)集離群度最大的離群點(diǎn)。

為了估計(jì)某點(diǎn)與其他所有點(diǎn)的角度方差，首先將數(shù)據(jù)集投影到與隨機(jī)向量（向量坐標(biāo)從標(biāo)準(zhǔn)正態(tài)分布N(0,1)中隨機(jī)選擇）正交的超平面上。根據(jù)投影之后的數(shù)據(jù)分區(qū)，能夠估計(jì)每個(gè)點(diǎn)的角度無(wú)偏期望值。然后，使用AMS Sketch估計(jì)二階矩，得出方差及投影到隨機(jī)超平面上數(shù)據(jù)點(diǎn)的頻率矩的總體情況。將隨機(jī)超平面投影和乘積域AMS Sketch結(jié)合在一起，可以將計(jì)算復(fù)雜度降低到O(nlbn(d+lbn))水平。接下來(lái)，將首先介紹隨機(jī)超平面投影和AMS Sketch的基本概念，然后給出數(shù)據(jù)集各點(diǎn)角度方差估計(jì)算法。

3.3 隨機(jī)超平面

依照文獻(xiàn)[6]，取隨機(jī)向量r1,r2,…,rt∈Rd，其中各向量坐標(biāo)從標(biāo)準(zhǔn)正態(tài)分布N(0,1)中獨(dú)立選取。

對(duì)向量ri，只有當(dāng)向量a-p和b-p位于與ri正交的超平面不同側(cè)時(shí)，才有=1，且(a-p)·r＜0。這種情況的概率與Θapb成正比，具體內(nèi)容可參考文獻(xiàn)[6]。更準(zhǔn)確地，有：

引理1對(duì)所有：

Alon在文獻(xiàn)[12]中描述并分析了一種稱為AMS Sketch的近似方法，以估計(jì)高維向量的二階頻率矩：

最近，Indyk和McGregor[7]及Braverman等人[13]考慮了帶有兩個(gè)不同4維獨(dú)立向量的AMS Sketch進(jìn)行外積計(jì)算。于是，可以把矩陣看成矩陣元素向量，有：

3.4 ABOD近似

為避免出現(xiàn)三次方計(jì)算復(fù)雜度，根據(jù)隨機(jī)超平面投影提出一種近線性時(shí)間算法，來(lái)估計(jì)各數(shù)據(jù)點(diǎn)角度方差。

3.4.1 一階矩估計(jì)

設(shè)有隨機(jī)向量r和點(diǎn)p∈S，估計(jì)MOA1(p)，有：

需要指出的是，該值是p點(diǎn)和其他點(diǎn)角度期望無(wú)偏估計(jì)。通過(guò)使用t個(gè)隨機(jī)投影來(lái)提高估計(jì)精度。于是，得到更精確的MOA1(p)無(wú)偏估計(jì)量：

3.4.2 二階矩估計(jì)

根據(jù)以上公式，可以估計(jì)MOA2(p)。

然而，無(wú)法在二次方時(shí)間內(nèi)準(zhǔn)確計(jì)算出Frobenius范式。于是，利用乘積域AMS Sketch來(lái)進(jìn)行估計(jì)。設(shè)向量ui和υi的AMS Sketch分別為AMS()和AMS()（使用不同的4維獨(dú)立隨機(jī)向量）。由于存在線性關(guān)系，分布的和的sketch等于分布的sketch的和，因此有：

3.4.3 算法

上文討論了如何計(jì)算點(diǎn)p的估計(jì)量MOA1(p)和MOA2(p)，現(xiàn)在討論近線性時(shí)間算法FastVOA，以估計(jì)數(shù)據(jù)集各點(diǎn)的角度方差。算法1偽代碼描述了FastVOA的內(nèi)容。

首先，將數(shù)據(jù)集投影到與隨機(jī)投影向量正交的超平面上（算法2）。函數(shù)Random Projection（）返回一個(gè)包含集合t次隨機(jī)投影后分區(qū)信息的數(shù)據(jù)結(jié)構(gòu)L。通過(guò)L，可以高效地確定點(diǎn)p和ri的對(duì)應(yīng)值||和||。

算法2RandomProjection(S,t)

在算法3中，使用L計(jì)算各點(diǎn)p的Frobenius范數(shù)||P||F。為了提高AMS Sketch的精度，必須重復(fù)計(jì)算Frobenius-Norm（）s1s2次，輸出F2作為s2個(gè)隨機(jī)變量Y1,Y2,…,Ys2的中位數(shù)，每個(gè)值均為s1個(gè)值的均值（第3～6行）。然后，第9～10行計(jì)算各點(diǎn)的二階矩估計(jì)值和方差。

算法3FrobeniusNorm(L,t,n)

3.4.4 計(jì)算復(fù)雜度和并行處理

很明顯，F(xiàn)astVOA的計(jì)算復(fù)雜度跟算法2、3有關(guān)。請(qǐng)注意，算法2在計(jì)算點(diǎn)積和對(duì)點(diǎn)分類時(shí)的計(jì)算復(fù)雜度為O(tn(d+lbn))，算法3復(fù)雜度為O(tn)。為了保證FastVOA的精度，特地使t=O(lbn)且s1s2足夠大，以提高估計(jì)的精度，具體分析見(jiàn)第4章。因此，計(jì)算時(shí)間主要由AMS Sketch的計(jì)算時(shí)間決定。這意味著，F(xiàn)astVOA的計(jì)算時(shí)間為O(s1s2nlbn)。需要指出的是，算法2、3使用涉及t個(gè)隨機(jī)向量的for循環(huán)，對(duì)每個(gè)隨機(jī)向量執(zhí)行相同的獨(dú)立操作。因此，可以并行計(jì)算這三個(gè)算法中的循環(huán)，獲得近線性加速效果（依使用的處理器數(shù)量而定）。

4 誤差分析

前面已經(jīng)論述，本文估計(jì)值是無(wú)偏的，可以獲得合適的一階和二階矩E[F1(p)]=MOA1(p)，E[F2(p)]=MOA2(p)。

本章對(duì)隨機(jī)投影進(jìn)行分析，并給出若要達(dá)到精度ε，需要的隨機(jī)投影和AMS Sketch數(shù)量范圍。角度方差估計(jì)時(shí)存在附加誤差O(ε)。對(duì)MOA1(p)，可以直接求得且概率較

一階估計(jì)值：考慮F1(p)偏離MOA1(p)程度超過(guò)ε的概率（選擇了向量r1,r2,…,rt）。將和值F1(p)t/π分成t項(xiàng)。于是，可以得出結(jié)論，偏離均值程度超過(guò)εt/π的概率最大為2e-2(εt/π)2/t。如果讓t＞ε-2π2ln(n)，則該概率最大為2/n2。因此，所有n個(gè)一階矩估計(jì)值達(dá)到最大誤差ε的概率為1-O(1/n)。大；對(duì)MOA2(p)，估計(jì)值F2(p)的基本成功概率只有3/4。然而，將二階矩估計(jì)步驟重復(fù)s2=O(lb(1/δ))次，為各點(diǎn)設(shè)置中位離群分值，成功概率可提高到1-δ，其中δ＞0，見(jiàn)文獻(xiàn)[12]。

根據(jù)文獻(xiàn)[14]，使用以下切爾諾夫限，有：

最后，應(yīng)該解釋一下在等式（3）求解最終估計(jì)值F2(p)使用AMS sketch時(shí)引入的誤差。估計(jì)值的方差最大為8MOA2(p)2。求取s1個(gè)sketch的均值，方差最大值被降低到8MOA2(p)2/s1。根據(jù)Chebychev不等式，F(xiàn)2(p)偏離期望值MOA2(p)程度達(dá)到MOA2(p)的概率最大為：

對(duì)s1＞32π4/ε2，該概率小于1/4?？梢宰C明，該偏離與F2(p)偏離2ε的情況相對(duì)應(yīng)。如上所述，通過(guò)將估計(jì)過(guò)程重復(fù)s2次，可以讓失效概率呈指數(shù)下降。

5 實(shí)驗(yàn)

所有算法用C++算法實(shí)現(xiàn)，利用合成和真實(shí)數(shù)據(jù)集，依托2.67 GHz core i7、3 GB RAM Windows平臺(tái)進(jìn)行。

5.1 數(shù)據(jù)集

為保證比較的公平性，使用與ABOD算法相同的合成數(shù)據(jù)生成方法[5]。生成的高斯數(shù)據(jù)包括5個(gè)平等加權(quán)的數(shù)據(jù)群，這些數(shù)據(jù)群正常點(diǎn)的均值和方差均隨機(jī)生成，利用全維空間均勻分布作為離群點(diǎn)。對(duì)每個(gè)合成數(shù)據(jù)集，均生成與高斯數(shù)據(jù)群相獨(dú)立的10個(gè)離群點(diǎn)，并利用不同規(guī)模和維度的合成數(shù)據(jù)集對(duì)各種算法進(jìn)行性能評(píng)估。

選用3個(gè)實(shí)際數(shù)據(jù)集（Isolet，Multiple Features and Optical Digits），這3個(gè)實(shí)際數(shù)據(jù)集是UCI機(jī)器學(xué)習(xí)庫(kù)為分類和機(jī)器學(xué)習(xí)任務(wù)設(shè)計(jì)的[15]。Isolet包括字母表26個(gè)字母的發(fā)音數(shù)據(jù)，其他兩個(gè)數(shù)據(jù)集由手寫數(shù)字（0～9）數(shù)據(jù)組成。對(duì)每個(gè)數(shù)據(jù)集，選擇具有共同行為的某種類別的所有數(shù)據(jù)點(diǎn)作為正常點(diǎn)，從另一類選擇10個(gè)數(shù)據(jù)點(diǎn)作為離群點(diǎn)。例如，選擇Isolet數(shù)據(jù)集C，D，E類別都有“e”聲的點(diǎn)作為正常點(diǎn)，選擇Y類別10個(gè)點(diǎn)作為離群點(diǎn)。同樣地，由于形狀類似，選擇Multiple Features 6，9類及Optical Digits 3，9類數(shù)據(jù)作為正常點(diǎn)，0類的10個(gè)數(shù)據(jù)點(diǎn)作為離群點(diǎn)。需要指出的是，很有可能部分離群點(diǎn)位于內(nèi)點(diǎn)覆蓋區(qū)域。因此，無(wú)法準(zhǔn)確分離所有離群點(diǎn)。但是，希望本文算法能夠?qū)㈦x群點(diǎn)劃入頂級(jí)數(shù)據(jù)點(diǎn)范圍。

5.2 估計(jì)精度

圖25 個(gè)數(shù)據(jù)集基于隨機(jī)投影的估計(jì)值的偏離誤差

這一節(jié)討論精度實(shí)驗(yàn)，以評(píng)估本文算法的可靠性。如第4章所述，如果隨機(jī)投影次數(shù)t=O(lbn)和AMS Sketchs1s2足夠大，則數(shù)據(jù)集任意點(diǎn)p的估計(jì)值，偏離期望值程度超過(guò)ε的概率最大為δ。請(qǐng)注意，F(xiàn)2(p)是基于AMS Sketch的二階矩估計(jì)值，而F′2(p)只考慮了隨機(jī)投影。開(kāi)始時(shí)，通過(guò)實(shí)驗(yàn)來(lái)評(píng)估只基于隨機(jī)投影的估計(jì)值精度。在概率δ=0.1條件下考察了F1(p)和F′2(p)偏離期望值的程度ε。設(shè)t范圍[100，1 000]，選取含有1 000個(gè)點(diǎn)的合成數(shù)據(jù)集Syn50（50維）和Syn100（100維），及3個(gè)真實(shí)數(shù)據(jù)集（Isolet，Mfeat，Digit）進(jìn)行實(shí)驗(yàn)。圖2（a）和圖2（b）顯示了誤差概率δ=0.1條件下，估計(jì)值F1(p)和F′2(p)偏離期望值的程度(ε)。通過(guò)這兩個(gè)估計(jì)值，求得了方差估計(jì)值，并考察了在δ=0.1條件下與期望值的偏離程度，見(jiàn)圖2（c）。雖然理論分析表面，要讓?duì)疟容^小，隨機(jī)投影數(shù)量t必須要足夠大，對(duì)5個(gè)數(shù)據(jù)集的實(shí)驗(yàn)數(shù)據(jù)表面，如果t很小，可以準(zhǔn)確估計(jì)所有點(diǎn)的角度方差。在t=600時(shí)，5個(gè)數(shù)據(jù)集的90%的點(diǎn)，其一階矩、二階矩和方差估計(jì)值偏離期望值的最大誤差分別為0.035，0.08，0.015。當(dāng)t增加到1 000時(shí)，5個(gè)數(shù)據(jù)集的90%的點(diǎn)，其方差估計(jì)值偏離期望值的最大誤差為0.01。因此，如果數(shù)據(jù)集的離群點(diǎn)和邊界點(diǎn)的VOA差異較大，基于隨機(jī)投影的VOA估計(jì)方法也可以取得較好的離群點(diǎn)檢測(cè)效果。

為了對(duì)AMS Sketch帶來(lái)的誤差進(jìn)行定量分析，利用AMS Sketches，并將所有數(shù)據(jù)集的參數(shù)設(shè)置為t=1 000,s1=7 200,s2=50,e=0.1，然后考察方差估計(jì)值的誤差概率δ。具體來(lái)說(shuō)，計(jì)算出數(shù)據(jù)集p點(diǎn)數(shù)量，基于AMS Sketch的方差估計(jì)值偏離期望值VOA(p)的誤差將超過(guò)εVOA(p)。表1給出了5個(gè)數(shù)據(jù)集方差估計(jì)值的誤差概率。

表1 5個(gè)數(shù)據(jù)集基于AMS Sketch的方差估計(jì)值的誤差概率

很顯然，合成數(shù)據(jù)集的誤差非常小，而真實(shí)數(shù)據(jù)集的誤差非常大，尤其是Isolet。這是因?yàn)槭褂肁MS Sketch會(huì)導(dǎo)致數(shù)據(jù)集所有點(diǎn)的方差被過(guò)高或過(guò)低估計(jì)。為了保證本文離群點(diǎn)檢測(cè)近似算法的可靠性，分析了SimpleVOA強(qiáng)力算法和FastVOA近似算法間的離群分級(jí)精度。離群分級(jí)精度被定義為|A∩B|/m，其中A和B分別是SimpleVOA和FastVOA算法返回的級(jí)別最高的m個(gè)點(diǎn)。圖3顯示了SimpleVOA和FastVOA算法的離群分級(jí)精度，其中m范圍為10～100，橫坐標(biāo)是指頂級(jí)數(shù)據(jù)點(diǎn)數(shù)目，縱坐標(biāo)是指分級(jí)精度。

圖3 SimpleVOA和FastVOA算法的離群分級(jí)精度

依據(jù)圖2的離群分級(jí)精度分析結(jié)果表明，F(xiàn)astVOA算法在所有數(shù)據(jù)集合情況下的精度都非常高。不管m范圍如何，2個(gè)合成數(shù)據(jù)集和Multiple Feature數(shù)據(jù)集的分級(jí)精度都比較高；而其他數(shù)據(jù)集當(dāng)m＜30時(shí)精度一般，當(dāng)m＞40時(shí)精度較高。雖然AMS Sketch會(huì)導(dǎo)致方差被過(guò)高或過(guò)低估計(jì)，F(xiàn)astVOA的數(shù)據(jù)點(diǎn)分級(jí)性能仍然出色。

5.3 有效性

很顯然，本文方法直接處理角度方差（VOA），而文獻(xiàn)[5]方法計(jì)算距離加權(quán)的角度余弦方差。本節(jié)實(shí)驗(yàn)將證明兩個(gè)離群數(shù)據(jù)檢測(cè)指標(biāo)的有效性。用該兩個(gè)指標(biāo)來(lái)評(píng)估強(qiáng)力算法（SimpleVOA和ABOD）和近似算法（FastVOA and FastABOD）的離群分級(jí)質(zhì)量。為了公平起見(jiàn)，使用精度檢索圖來(lái)評(píng)估各算法的最大似然離群點(diǎn)檢測(cè)性能。精度水平是指算法判定的數(shù)據(jù)集離群點(diǎn)中真實(shí)離群點(diǎn)的數(shù)量，在各精度水平，定義檢索率為算法判定的數(shù)據(jù)集離群點(diǎn)中真實(shí)離群點(diǎn)的百分比。

生成4個(gè)合成數(shù)據(jù)集，數(shù)據(jù)規(guī)模1 000和5 000點(diǎn)，維度50和100維。觀察到，當(dāng)合成數(shù)據(jù)的規(guī)模上升時(shí)，離群點(diǎn)和邊界點(diǎn)的VOA方差變大。因此，對(duì)5 000點(diǎn)合成數(shù)據(jù)集，更改了FastVOA的參數(shù)設(shè)置，以降低時(shí)間復(fù)雜度。尤其地，設(shè)置t=100,s1=1 600,s2=10。在5.2節(jié)其他數(shù)據(jù)集，也沿用相同的參數(shù)設(shè)置。FastABOD的樣本規(guī)模設(shè)為0.1n[5]。需要指出，ABOD和FastABOD在4個(gè)合成數(shù)據(jù)集上的表現(xiàn)非常完美。這意味著，所有10個(gè)離群點(diǎn)剛好都被評(píng)為10個(gè)頂級(jí)點(diǎn)。因此，沒(méi)有給出ABOD和FastABOD在合成數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果。圖4給出了合成數(shù)據(jù)集的精度檢索圖。圖4（a）顯示了強(qiáng)力算法（SimpleVOA1和SimpleVOA2）和近似算法（FastVOA1和FastVOA2）在2個(gè)數(shù)據(jù)集（50維，1 000和5 000個(gè)點(diǎn)）上的性能。在50維時(shí)，VOA對(duì)小規(guī)模數(shù)據(jù)效果不佳，但是在大數(shù)據(jù)規(guī)模時(shí)性能極佳，總共11個(gè)頂級(jí)點(diǎn)里包括了全部10個(gè)離群點(diǎn)。很顯然，SimpleVOA性能越高，F(xiàn)astVOA性能越高。圖4（b）給出了2個(gè)100維合成數(shù)據(jù)集實(shí)驗(yàn)結(jié)果。由于ABOF加權(quán)因子在高維數(shù)據(jù)中的作用有限，SimpleVOA和FastVOA的實(shí)驗(yàn)結(jié)果與ABOD、FastABOD相當(dāng)，性能也很顯著。

圖4 4個(gè)合成數(shù)據(jù)集的精度檢索圖

圖5 3個(gè)真實(shí)數(shù)據(jù)集的精度檢索圖

圖5顯示了3個(gè)真實(shí)數(shù)據(jù)集的精度檢索圖。對(duì)Isolet數(shù)據(jù)集，SimpleVOA和ABOD的性能表現(xiàn)幾近完美，10個(gè)和16個(gè)頂級(jí)數(shù)據(jù)點(diǎn)剛好包含了全部10個(gè)離群點(diǎn)。FastABOD的離群分級(jí)性能優(yōu)于FastVOA，10個(gè)頂級(jí)數(shù)據(jù)點(diǎn)包含了7個(gè)離群點(diǎn)。然而，F(xiàn)astABOD和FastVOA兩個(gè)算法在精度水平較高時(shí)性能欠佳。對(duì)Multiple Features數(shù)據(jù)集，SimpleVOA和FastVOA的性能表現(xiàn)非常出色，16個(gè)頂級(jí)數(shù)據(jù)點(diǎn)剛好包含了全部10個(gè)離群點(diǎn)，而ABOD和FastABOD算法性能欠佳。所有方法對(duì)Optical Digits數(shù)據(jù)集，離群點(diǎn)檢測(cè)性能均不佳。盡管如此，基于VOA的方法性能明顯優(yōu)于基于ABOF的算法。

5.4效率

本節(jié)將對(duì)FastVOA，LB ABOD和FastABOD三種算法在超大維數(shù)據(jù)集上的運(yùn)行時(shí)間進(jìn)行比較。事實(shí)上，大部分高維數(shù)據(jù)集的離群點(diǎn)難以事先準(zhǔn)確判定。因此，決定將這三個(gè)算法在合成數(shù)據(jù)集上運(yùn)行。數(shù)據(jù)集規(guī)模10 000～100 000個(gè)點(diǎn)，維度100～1 000維，各算法運(yùn)行時(shí)測(cè)量CPU運(yùn)行時(shí)間。

很顯然，LB ABOD和FastABOD的運(yùn)行時(shí)間為O(dn2)，F(xiàn)astVOA的計(jì)算時(shí)間主要依賴于參數(shù)t,s1,s2。如5.3節(jié)所示，對(duì)超高維合成數(shù)據(jù)集使用FastVOA算法時(shí)，即使將參數(shù)設(shè)置得非常小，也不會(huì)影響精度。因此，設(shè)置FastVOA算法的參數(shù)為t=100,s1=1 600,s2=10，F(xiàn)astABOF的樣本規(guī)模設(shè)為0.1n。需要指出的是，0.1n的值當(dāng)數(shù)據(jù)集規(guī)模增大時(shí)也會(huì)變得非常大。相反，F(xiàn)astVOA只需要很少量的隨機(jī)投影和AMS Sketch規(guī)模。如3.4.4節(jié)分析，F(xiàn)astVOA的總體運(yùn)行時(shí)間為O(tn(d+lbn+s1s2))。按照以上所述參數(shù)設(shè)置，F(xiàn)astVOA的總體運(yùn)行時(shí)間主要由AMS Sketch計(jì)算時(shí)間(O(ts1s2n))決定。

圖6（a）顯示了100維10 000～100 000點(diǎn)數(shù)據(jù)集時(shí)Fast-VOA，LB ABOD和FastABOD算法的CPU時(shí)間（ms），圖6（b）顯示了100～1 000維20 000點(diǎn)數(shù)據(jù)集時(shí)的CPU時(shí)間。很顯然，F(xiàn)astVOA的運(yùn)行時(shí)間隨著數(shù)據(jù)集的規(guī)模呈線性增長(zhǎng)，與維數(shù)無(wú)關(guān)。相反，LB ABOD和FastABOD計(jì)算時(shí)間與數(shù)據(jù)規(guī)模呈二次方關(guān)系，與維數(shù)成線性關(guān)系。

圖6 FastVOA，LB ABOD和FastABOD算法的CPU時(shí)間比較

最后，從FastVOA適宜并行處理角度來(lái)討論其高效性。利用支持多平臺(tái)內(nèi)存共享和多處理器C++編程的Open Multi-Processing API（OpenMP）來(lái)并行處理3.4.3節(jié)算法2、3的隨機(jī)投影向量for循環(huán)。在4核Core i7機(jī)上運(yùn)行并衡量了并行加速效果。表2給出了100維10 000點(diǎn)合成數(shù)據(jù)集時(shí)FastVOA算法的近線性并行加速效果。

表2 FastVOA并行加速效果

6 結(jié)論

本文提出了一種基于隨機(jī)投影的數(shù)據(jù)點(diǎn)角度方差估計(jì)算法，同時(shí)提出一種可靠的離群評(píng)分來(lái)檢測(cè)高維離群現(xiàn)象。通過(guò)將隨機(jī)投影與乘積域AMS Sketch相結(jié)合，本文近似算法的計(jì)算時(shí)間與數(shù)據(jù)集規(guī)模呈近線性關(guān)系，且適宜并行處理。本文還對(duì)近似質(zhì)量作了理論分析，以保證近似算法的可靠性?；诤铣蓴?shù)據(jù)和真實(shí)數(shù)據(jù)的實(shí)驗(yàn)表明，本文在對(duì)超高維數(shù)據(jù)集進(jìn)行離群點(diǎn)檢測(cè)時(shí)具有可拓展性強(qiáng)、效果好、效率高等特點(diǎn)。

[1]Wheeler R，Aitken S.Multiple algorithms for fraud detection[J]. Knowledge-Based Systems，2000，13（2）：93-99.

[2]賀玲，蔡益朝，楊征.高維數(shù)據(jù)空間的一種網(wǎng)格劃分方法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（5）：152-153.

[3]Angiulli F，Pizzuti C.Outlier mining in large high-dimensional data sets[J].IEEE Transactions on Knowledge and Data Engineering，2005，17（2）：203-215.

[4]Papadimitriou S，Kitagawa H，Gibbons P B，et al.Loci：fast outlier detection using the local correlation integral[C]//Proceedings 19th International Conference on Data Engineering，2003：315-326.

[5]Kriegel H P，Zimek A.Angle-based outlier detection in highdimensional data[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2008：444-452.

[6]Charikar M S.Similarity estimation techniques from rounding algorithms[C]//Annual ACM Symposium on Theory of Computing，2002：380-388.

[7]Indyk P，McGregor A.Declaring independence via the sketchingofsketches[C]//ProceedingsoftheNineteenth Annual ACM-SIAM Symposium on Discrete Algorithms，2008：737-745.

[8]Knox E M，Ng R T.Algorithms for mining distance-based outliers in large datasets[C]//Proceedings of the International Conference on Very Large Data Bases，1998：392-403.

[9]Wang Y，Parthasarathy S，Tatikonda S.Locality sensitive outlier detection：a ranking driven approach[C]//IEEE 27th International Conference on Data Engineering（ICDE），2011：410-421.

[10]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.

[11]Muller E，Schiffer M，Seidl T.Statistical selection of relevant subspace projections for outlier ranking[C]//IEEE 27th International Conference on Data Engineering（ICDE），2011：434-445.

[12]Alon N，Matias Y，Szegedy M.The space complexity of approximating the frequency moments[C]//Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing，1996：20-29.

[13]Braverman V，Chung K M，Liu Z，et al.AMS without 4-wise independence on product domains[C]//Proceedings of STACS’10，2008：119-130.

[14]Dubhashi D，Panconesi A.Concentration of measure for the analysis of randomized algorithms[M].Cambridge：Cambridge University Press，2009.

[15]Frank A，Asuncion A.UCI machine learning repository[EB/OL]. [2013-03-30].http：//archive.ics.uci.edu/ml.

LI Qiao,ZHOU Yinglian,HUANG Sheng,MA Xiang

School of Information Science and Engineering,Hunan International Economics University,Changsha 410205,China

Outlier mining ind-dimensional point sets is currently one of the hot areas of data mining.The current outlier mining approaches based on the distance or the nearest neighbor result in the poor mining results.To solve this problem,this paper investigates the use of angle-based outlier factor in mining high dimensional outliers.It proposes a novel random projection-based technique that is able to estimate the angle-based outlier factor for all data points in time near-linear in the size of the data.Also,the approach is suitable to be performed in parallel environment to achieve a parallel speedup.It introduces a theoretical analysis of the quality of approximation to guarantee the reliability of the algorithm.The empirical experiments on synthetic and real world data sets demonstrate that the approach is efficient and scalable to very large high-dimensional data sets.

outlier data mining;angle;random projection algorithm;near-linear time;reliability;efficiency

d維點(diǎn)集離群數(shù)據(jù)挖掘技術(shù)是目前數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一。當(dāng)前基于距離或最近鄰概念進(jìn)行離群數(shù)據(jù)挖掘時(shí)，在高維數(shù)據(jù)情況下的挖掘效果不佳，鑒于此，將基于角度的離群因子應(yīng)用到高維離群數(shù)據(jù)挖掘中，提出一種新的基于隨機(jī)投影算法的離群數(shù)據(jù)挖掘方案，它只需要用接近線性時(shí)間的方法就能預(yù)測(cè)所有數(shù)據(jù)點(diǎn)的基于角度的離群因子。該方法可以用于并行環(huán)境進(jìn)行并行加速。對(duì)近似質(zhì)量進(jìn)行了理論分析，以保證算法的可靠性。合成和真實(shí)數(shù)據(jù)集實(shí)驗(yàn)結(jié)果表明，對(duì)超高維數(shù)據(jù)集，該方法效率高、可伸縮性強(qiáng)。

離群數(shù)據(jù)挖掘；角度；隨機(jī)投影算法；接近線性時(shí)間；可靠性；效率

A

TP391

10.3778/j.issn.1002-8331.1305-0442

LI Qiao,ZHOU Yinglian,HUANG Sheng,et al.Random projection algorithm for outlier mining technology research. Computer Engineering and Applications,2013,49（24）：122-129.

2011年湖南省教育廳科學(xué)研究項(xiàng)目（No.11C0784）。

李橋（1979—），講師，主要研究方向：數(shù)據(jù)挖掘，嵌入式及應(yīng)用；周瑩蓮（1974—），女，碩士，主要研究方向：社會(huì)網(wǎng)絡(luò)，數(shù)據(jù)挖掘。

2013-05-31

2013-08-07

1002-8331（2013）24-0122-08