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

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

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

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

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

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

1 引言

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

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

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

2 相關工作

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

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

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

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

3 本文方法

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

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

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

圖1 不同類型的點的角度差異

3.2 算法主要思路

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

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

3.3 隨機超平面

依照文獻[6]，取隨機向量r1,r2,…,rt∈Rd，其中各向量坐標從標準正態(tài)分布N(0,1)中獨立選取。

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

引理1對所有：

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

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

3.4 ABOD近似

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

3.4.1 一階矩估計

設有隨機向量r和點p∈S，估計MOA1(p)，有：

需要指出的是，該值是p點和其他點角度期望無偏估計。通過使用t個隨機投影來提高估計精度。于是，得到更精確的MOA1(p)無偏估計量：

3.4.2 二階矩估計

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

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

3.4.3 算法

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

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

算法2RandomProjection(S,t)

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

算法3FrobeniusNorm(L,t,n)

3.4.4 計算復雜度和并行處理

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

4 誤差分析

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

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

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

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

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

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

5 實驗

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

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

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

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

5.2 估計精度

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

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

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

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

很顯然，合成數(shù)據(jù)集的誤差非常小，而真實數(shù)據(jù)集的誤差非常大，尤其是Isolet。這是因為使用AMS Sketch會導致數(shù)據(jù)集所有點的方差被過高或過低估計。為了保證本文離群點檢測近似算法的可靠性，分析了SimpleVOA強力算法和FastVOA近似算法間的離群分級精度。離群分級精度被定義為|A∩B|/m，其中A和B分別是SimpleVOA和FastVOA算法返回的級別最高的m個點。圖3顯示了SimpleVOA和FastVOA算法的離群分級精度，其中m范圍為10～100，橫坐標是指頂級數(shù)據(jù)點數(shù)目，縱坐標是指分級精度。

圖3 SimpleVOA和FastVOA算法的離群分級精度

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

5.3 有效性

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

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

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

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

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

5.4效率

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

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

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

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

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

表2 FastVOA并行加速效果

6 結論

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

[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].計算機工程與應用，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維點集離群數(shù)據(jù)挖掘技術是目前數(shù)據(jù)挖掘領域的研究熱點之一。當前基于距離或最近鄰概念進行離群數(shù)據(jù)挖掘時，在高維數(shù)據(jù)情況下的挖掘效果不佳，鑒于此，將基于角度的離群因子應用到高維離群數(shù)據(jù)挖掘中，提出一種新的基于隨機投影算法的離群數(shù)據(jù)挖掘方案，它只需要用接近線性時間的方法就能預測所有數(shù)據(jù)點的基于角度的離群因子。該方法可以用于并行環(huán)境進行并行加速。對近似質量進行了理論分析，以保證算法的可靠性。合成和真實數(shù)據(jù)集實驗結果表明，對超高維數(shù)據(jù)集，該方法效率高、可伸縮性強。

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

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年湖南省教育廳科學研究項目（No.11C0784）。

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

2013-05-31

2013-08-07

1002-8331（2013）24-0122-08