鄧廷權，劉金艷，王寧

哈爾濱工程大學理學院，哈爾濱150001

高維數(shù)據(jù)離群點檢測的局部線性嵌入方法

鄧廷權，劉金艷，王寧

哈爾濱工程大學理學院，哈爾濱150001

CNKI網(wǎng)絡出版：2017-03-04,http://kns.cnki.net/kcms/detail/11.2127.TP.20170304.1727.006.html

1 引言

離群點或者異常值通常具有異乎尋常的信息。離群點[1]有時又被稱為異常點、野值點、例外點、噪聲點、偏離點、新穎點、異常物等，在這里統(tǒng)一稱作離群點。離群點是指可能由某種機制產生的偏離大多數(shù)樣本的點，信用卡欺詐檢測、網(wǎng)絡入侵檢測、自然災害預測和運動員的異常能力檢測等等通常能帶來許多重要的信息。因此離群點檢測引起了人們越來越多的關注。離群點產生的原因主要有三種：（1）實驗產生的誤差，可能是數(shù)據(jù)測量與收集產生的誤差，也可以稱為噪聲點，理論上應該去除。因為它們不僅不能提供有用的信息，還有可能降低數(shù)據(jù)的質量。（2）數(shù)據(jù)來自于不同的類，這種離群點是研究的重點，如信用卡欺詐就是盜竊信用卡的人與信用卡擁有者可能具有不同的用卡習慣，因此他們屬于不同的兩類，這種情況下的信息是非常重要的。（3）自然變異，這種情況可能是自然產生的，未必是變異的異常。

離群點檢測的經(jīng)典方法主要有基于距離的離群點檢測方法[2-3]，找出每個點的k-最近鄰距離，將求出的距離按降序進行排列，應用topn方法把距離大的點作為離群點。江峰[3]提出了一種新穎的基于距離與邊界的離群點檢測方法（BD）?；趉最近鄰（KNN）的離群點檢測方法是經(jīng)典的基于距離的方法，雖然基于KNN[4]聚類的離群點檢測方法容易實現(xiàn)，但是該算法值得進一步的研究。首先基于KNN的離群點檢測方法對參數(shù)k敏感，當近鄰點數(shù)k有一個小的變化時，可能引起離群因子和相應的離群點的變化，因此文獻[4]提出了基于最小生成樹的KNN啟發(fā)式方法來發(fā)現(xiàn)離群點，克服參數(shù)k的影響。其次，對于含有多個屬性的高維數(shù)據(jù)而言，尋找每個點的k-最近鄰是非常耗時的。最后，在高維空間，可能存在著維數(shù)災難問題，數(shù)據(jù)點之間的距離可能都是相等的。從而，在高維空間中，人們開始質疑基于距離的離群點檢測方法的合理性。還有基于密度的離群點檢測方法，如局部離群因子（LOF）方法[5-7]、基于統(tǒng)計的方法、基于深度的方法以及基于聚類的方法[8-10]。文獻[8]中提出了一種基于模糊粗糙C均值的半監(jiān)督離群點檢測方法（FRSSOD），通過利用標記樣本并結合模糊粗糙C均值聚類方法，達到較好的檢測離群點的效果。

隨著數(shù)據(jù)量的增大，數(shù)據(jù)的維數(shù)也在不斷增長，人們需要面對可能由此帶來的維數(shù)災難問題。對于高維數(shù)據(jù)集來說，許多傳統(tǒng)的離群點檢測方法并不能有效地檢測出離群點[11-13]，因為高維空間數(shù)據(jù)點分布比較稀疏，根據(jù)距離判斷k近鄰[14-15]、密度以及聚類都是不合理的。為了解決這個問題，一些方法嘗試將高維數(shù)據(jù)投影到低維子空間，在低維空間中通過距離、密度、聚類方法來檢測離群點。這些方法一般是將維度進行組合，對每一個可能的子空間進行投影，選出效果最好的子空間。但是隨著維數(shù)的增加，導致存在組合的子空間數(shù)量非常多，計算量非常大。Aggarwal提出了高維數(shù)據(jù)離群點檢測需要滿足以下條件：能夠有效地解決高維數(shù)據(jù)的稀疏問題；能夠對數(shù)據(jù)的異常進行解釋；能夠給出子空間的物理意義；計算高效性及要考慮數(shù)據(jù)點的局部結構。

眾所周知，局部線性嵌入（LLE）[16-18]是一種非線性的維數(shù)約減方法，它將高維數(shù)據(jù)集降至低維空間的同時保持樣本間的局部線性結構，但它容易受到噪聲的影響。拉普拉斯映射（LE）[19-20]也是一種非線性的維數(shù)約減方法，它將高維數(shù)據(jù)降至低維空間的同時保持數(shù)據(jù)間的局部近鄰結構，同時它對噪聲不敏感?；谶@兩種方法的特點，本文應用流形學習的方法對高維數(shù)據(jù)進行降維，可以有效地避免組合的子空間數(shù)量非常多，計算量非常大的問題。由于離群點一般都在數(shù)據(jù)集的邊界上，本文通過建立一種有效的粗糙集模型，將數(shù)據(jù)集的下近似中的點保持局部線性結構，將所有樣本點保持局部近鄰結構，確保在降維的過程中使離群點遠離正常點，進而在低維空間中使用基于最小生成樹的KNN啟發(fā)式方法，能夠更簡單有效地檢測出異常值。本文提出的方法不僅能夠達到對高維數(shù)據(jù)集進行離群點檢測所需的5點要求，而且一系列實驗證明了它檢測離群點的有效性。

2 經(jīng)典LLE和LE降維方法

2.1 局部線性嵌入

Roweis和Saul在2000年提出了一種解決非線性維數(shù)約減的方法叫做局部線性嵌入（LLE）。由于該方法簡單，參數(shù)較少，容易實施，適用于非線性數(shù)據(jù)集以及最優(yōu)解不容易陷入局部最小等優(yōu)點，因此被廣泛應用。LLE通過保持數(shù)據(jù)的局部線性結構來恢復潛在流形。

得到。對于每一個點xi：

如果Gi=(Gjl)可逆，則可以得到：

其中第一個限制移除了旋轉平移自由度，第二個限制要求輸出變量在一定的范圍內。式（2）的等價表示如下：

其中M=(I-W)T(I-W)，所以求解優(yōu)化問題（3），轉化為求M最小的d+1特征值所對應的特征向量。由于最小的特征值為0，所以被舍掉。

2.2 拉普拉斯映射

拉普拉斯映射（LE）是由Belkin和Niyogi在2003年提出的一種經(jīng)典的非線性維數(shù)約減方法。LE方法將高維數(shù)據(jù)集映射到低維空間的同時保持數(shù)據(jù)點間的局部近鄰結構，且對噪聲不敏感。

整理優(yōu)化問題（4）并利用拉格朗日乘子法，優(yōu)化問題（4）可以轉化為求如下廣義特征值問題：

公式（5）的最小的d個正的特征值所對應的特征向量就是高維數(shù)據(jù)映射低維空間的映射結果。

3 局部線性嵌入的離群點檢測方法（OLLE）

由于高維數(shù)據(jù)集中不同屬性的范圍差異非常大，數(shù)值大的屬性計算距離時占很大的比重，導致可能忽略其他屬性的重要信息，因此需要對數(shù)據(jù)進行預處理。

利用如下方法對數(shù)據(jù)集進行歸一化處理：

為每一個點xi(i=1,2,…,n)尋找近鄰集時，首先計算樣本xi與數(shù)據(jù)集X中所有樣本的距離，找到第k個最小距離dik，根據(jù)閾值dik，構造樣本xi的近鄰集N(xi)：

根據(jù)每個樣本xi得到的近鄰集，可以計算出樣本點與所有近鄰點之間的平均值di：

為每個樣本xi的每一個近鄰點xj∈N(xi)，計算出與N(xi)中樣本之間的平均值dj，根據(jù)得到的||N(xi)個值，再計算出個值的平均值：

顯然，對于每一個點xi來說，如果滿足就說明xi點在下近似集合中，否則在邊界集合中。可以看出在下近似集合中的點與周圍點距離偏差不大，因此稀疏情況比較一致。然而在邊界中的點與周圍點距離偏差比較大，因此這些點是離群點的可能性就會相對大一些。

對下近似中的每一個樣本點xi，定義點xi的近鄰集

由于LLE對噪聲敏感，對所有樣本點保持局部線性結構是不合理的，因為邊界的點可能是離群點，影響降維的效果。所以在這里對下近似中的點保持局部線性嵌入。

考慮每個樣本點xi(i=1,2,…,n)與它的近鄰集(xi)，構造如下重構誤差：

構造如下優(yōu)化問題：

由此可以求解出重構的權矩陣：

為了避免噪聲的影響，將高維數(shù)據(jù)集降至低維空間時，又希望可以保持數(shù)據(jù)樣本之間的局部近鄰結構。因此，對整個數(shù)據(jù)集構造一個加權近鄰圖，利用熱核法為近鄰點之間賦權值：如果xi∈Nk(xj)或xj∈Nk(xi)

顯然，如果樣本點xi和xj是近鄰關系，且xi和xj之間距離越小，則權值w′ij越大。如果樣本點xi和xj不是近鄰關系，則權值w′ij為0。

目的是將高維數(shù)據(jù)降至低維空間后，可以有效地檢測出離群點，所以希望離群點在低維空間中離正常點越來越遠。故構造出如下一個權重w″ij：

其中ε1是一個給定的閾值，di表示樣本點xi與近鄰集N(xi)中所有樣本的距離平均值，dj表示樣本點xj與近鄰集N(xj)中所有樣本的距離平均值。如果di和dj偏差不大，說明xi與xj的稀疏情況比較一致，樣本xi與xj是離群點的可能性很小，因此賦予一個大的權值。相反，當di和dj偏差大于一定的閾值時，表明樣本xi與xj中可能有一個點為離群點，根據(jù)距離賦權值，因此權值w″ij較小。

由于將高維數(shù)據(jù)降至低維空間中，不僅試圖保持下近似集中的樣本之間的局部線性結構，而且也希望保持全部數(shù)據(jù)樣本之間的局部近鄰結構，同時確保離群點遠離正常點。因此構造如下優(yōu)化問題：

其中ρ是一個實參數(shù)，權衡第一項保下近似集中樣本之間局部線性結構與第二項保全部樣本的局部近鄰結構同時拉開離群點與正常點之間的距離對優(yōu)化問題的影響。在這里D?是一個對角陣，由于：

令H=M+ρL?，則H也是一個n×n矩陣，從而式（8）可轉化為：根據(jù)拉格朗日乘子法，將上述優(yōu)化問題轉化為解如下廣義特征值問題：

公式（9）的最小的d+1個特征值所對應的特征向量就是高維數(shù)據(jù)映射到低維空間的映射結果。因為最小的特征值是0，或者接近0，然而任何向量都可以作為0的特征向量，所以舍棄了第一個特征值來保證輸出變量的唯一性。

由于基于KNN聚類的離群點檢測方法容易實現(xiàn)，但受參數(shù)k的選擇影響很大。本文采用基于最小生成樹的KNN啟發(fā)式方法[4]（MST-KNN）來檢測離群點。

4 實驗與分析

所有的實驗都是在Windows 7機器上運行的，電腦具有以下配置Intel?Pentium?雙核，2 GB內存，并且所有方法都是在MATLAB R2009a上實現(xiàn)的。

采用8個數(shù)據(jù)集對本文提出的算法進行分析實驗。Iris、Cancer、Wine、Zoo和Wdbc等五個數(shù)據(jù)集取自于UCI數(shù)據(jù)庫。Iris數(shù)據(jù)集有三類，前兩類全部選取，在第三類中只選取4個點，并將這4個點看作離群點；Cancer數(shù)據(jù)集總共有兩類，從第一類中選取210個點，第二類選出2個點并看作離群點；在Wine數(shù)據(jù)集中，選取64個點做測試，其中59個點取自一類，5個點取自另一類，并將這5個點看作離群點；在Zoo數(shù)據(jù)集中，選取45個點，其中41個點取自一類，4個點取自另一類，將這4個點看作離群點；數(shù)據(jù)集Wdbc中358個點來自一個類，20個點來自另一類，把這20個點看成離群點；Optical handwritten和Mnist都是數(shù)字數(shù)據(jù)集。在Optical handwritten中選取409個點做測試，其中390個點來自一類，其他20個點來自另一類，并把這20個點看做離群點。數(shù)據(jù)集Mnist中前800個點都是數(shù)字1，后10個點來自數(shù)字2，并把這10個點看做離群點。PIE為人臉數(shù)據(jù)集，在PIE中選取216個點做測試，其中包括5個人的人臉圖像，前四個人每個人49張圖像，最后一個人的20張圖片被看做異常點。數(shù)據(jù)特征如表1所示。

表1 數(shù)據(jù)集描述

4.1 OLLE可視化圖形

由于高維數(shù)據(jù)點分布稀疏，使得高維空間中數(shù)據(jù)之間的距離尺度與區(qū)域密度不再具有直觀的意義。因此，在將數(shù)據(jù)集從高維降至低維空間的同時保持局部幾何結構，且讓離群點與大多數(shù)點遠離，進而在低維中來檢測離群點。

對UCI中的Wine、Cancer和Iris三個數(shù)據(jù)集進行二維可視化表示。Wine數(shù)據(jù)集中選取64個樣本點，其中包含5個離群點；Cancer數(shù)據(jù)集中選取212個樣本點，其中包含2個離群點。Iris數(shù)據(jù)集中選取104個樣本點，其中包含4個離群點。在這兩個實驗中設置參數(shù)ε=0.2，ε1=0.003,ρ=1，第三個實驗參數(shù)是ε=0.4，ε1=0.003，ρ=1，k分別為10、8、10。圖1～3分別為數(shù)據(jù)集Wine、Iris和Cancer的二維可視化結果。

圖1 Wine數(shù)據(jù)集的可視化

圖2 Iris數(shù)據(jù)集的可視化

圖3 Cancer數(shù)據(jù)集的可視化

其中圖1～3中的橫軸、縱軸分別表示高維空間中的圖像映射到低維空間所對應的橫、縱坐標。從圖中可以看出，數(shù)據(jù)集在降至二維空間中后離群點達到了遠離了大多數(shù)的點的效果。

4.2 與BD方法的對比實驗

江峰[3]提出了一種新穎的基于距離與邊界的離群點檢測方法（BD），對于一個給定的數(shù)據(jù)集U，X是U的子集。由于BD算法，需要針對每個屬性的X不同屬性值進行分析，且只檢測數(shù)據(jù)集的一個子集中的離群點，盡管如此，該算法計算量非常大，運行時間非常長。因此本文只對4個數(shù)據(jù)集進行分析。BD方法只檢測X數(shù)據(jù)集中的離群點，但本文提出的方法，仍然針對表1中前4個數(shù)據(jù)集，檢測其各自的離群點。在BD方法中，設X為表1數(shù)據(jù)集的前10個點，且離群點分別位于X的前4、5、2、4個位置。針對不同的數(shù)據(jù)集，設置不同的參數(shù)，Zoo數(shù)據(jù)集進行實驗時，OLLE中參數(shù)設置為：ε=0.2，ε1=0.003，ρ=1，k=10，Wine、Iris和Cancer數(shù)據(jù)集的參數(shù)設置同4.1節(jié)，實驗結果如表2，其中括號內為實驗運行的時間。

根據(jù)表2的實驗結果可知：對Iris和Wine數(shù)據(jù)集，兩種方法都準確地檢測出離群點，但對于Cancer和Zoo這兩個數(shù)據(jù)集來說，OLLE方法檢測離群點的精度明顯高于BD方法，且應用OLLE方法實驗運行的時間少于BD方法實驗運行的時間。

表2 BD與OLLE對比實驗

4.3 與LOF和RFSSOD方法的對比實驗

LOF和RFSSOD兩種方法分別是基于密度和基于聚類的離群點檢測方法，它們都是依據(jù)近鄰點的距離來求密度和聚類的。RFSSOD方法結合了模糊集（FCM）、粗糙集（RCM）和半監(jiān)督異常知識發(fā)現(xiàn)（SSOD）方法進行離群點的挖掘，用到了一部分標記的正常點與離群點來獲得較好的聚類結果。RFSSOD主要討論邊界中的點是離群點的可能性，因此縮短了計算的時間。用LOF和RFSSOD兩個方法與OLLE進行比對。選取4個維數(shù)較高的數(shù)據(jù)集，其中Wdbc是UCI中的數(shù)據(jù)集，Optical handwritten和Mnist都是數(shù)字數(shù)據(jù)集，PIE為人臉數(shù)據(jù)集。在LOF中，8個數(shù)據(jù)集中的鄰域大小k分別為10、10、10、10、20、10、10、20。在RFSSOD中，有三個參數(shù)r1、r2、?，r1、r2是調節(jié)參數(shù)，調節(jié)FRCM、SSOD與標記樣本之間的關系。?為一個閾值，判斷樣本點屬于某一類的下近似，還是屬于多個類的上近似。在這里數(shù)據(jù)的標記信息如表3所示。

表3 數(shù)據(jù)集描述

在RFSSOD中，三個參數(shù)r1,r2,?在8個數(shù)據(jù)集的值分別為：

在OLLE中，前四個數(shù)據(jù)集參數(shù)同4.2節(jié)，后四個數(shù)據(jù)集參數(shù)設定：

實驗結果如表4所示。

根據(jù)表4的實驗結果可知，前四個數(shù)據(jù)集，維度相對較低，3種方法均能發(fā)現(xiàn)離群點。但對于Wdbc、Minst和PIE這3個數(shù)據(jù)集，維數(shù)相對較高，本文提出的方法的效果較好于其他兩種方法。LOF和RFSSOD兩種方法分別是基于密度與基于聚類的離群點檢測方法，它們都是計算近鄰點的距離來進行求密度，聚類的。然而在高維空間中，基于距離的方法不一定是準確的，因為高維數(shù)據(jù)集中的數(shù)據(jù)點非常稀疏，根據(jù)距離來判斷離群點不一定能達到理想的效果，而本文提出的方法是保證數(shù)據(jù)點的局部幾何結構不變，當映射到低維空間中，數(shù)據(jù)點比較緊湊，就可以在低維空間中進一步檢測離群點。因此對于大多數(shù)數(shù)據(jù)集，本文方法的效果都比較好，但對于Optical handwritten據(jù)集，RFSSOD方法檢測離群點的精度優(yōu)于OLLE方法，這是由于RFSSOD是一種半監(jiān)督聚類方法，利用一定的先驗知識，因此檢測出的離群點的個數(shù)較多。但是對數(shù)據(jù)集進行聚類時，離群點的個數(shù)較少時，幾乎很難將離群點都聚到一個類中，這是聚類方法常遇到的一個問題。應用三種方法對8個數(shù)據(jù)集進行實驗，其中，有兩個數(shù)據(jù)集OLLE運行的時間最少，有6個數(shù)據(jù)集RFSSOD算法運行的時間最少。運行時間的長短與數(shù)據(jù)集的樣本數(shù)，數(shù)據(jù)樣本的屬性個數(shù)有關，不同的數(shù)據(jù)集可能運行的時間不同。

表4 離群點檢測結果

4.4 與基于最小生成樹的KNN（MST-KNN）方法的對比實驗

OLLE是在保持局部幾何結構的前提下，將數(shù)據(jù)集從高維空間降至低維空間，同時讓離群點與大多數(shù)點遠離，并在低維空間中用基于最小生成樹的KNN啟發(fā)式方法（MST-KNN）來進行離群點檢測，應用topn1方法，把離群程度最大的幾個點判定為離群點。在高維空間中利用MST-KNN檢測離群點的精度與OLLE檢測離群點的精度進行對比實驗。最后都是通過選取離群程度最高的前n1個樣本作為候選離群點。在MST-KNN中，對8個數(shù)據(jù)集，參數(shù)k分別設置為10、10、10、10、20、20、10、10。OLLE方法的參數(shù)設置同4.3節(jié)。實驗結果如表5所示。

根據(jù)表5的實驗結果可知，對Iris、Cancer、Zoo數(shù)據(jù)集，兩個方法均能檢測出離群點。但是對其他數(shù)據(jù)集，用OLLE將數(shù)據(jù)降維，并在低維中使用MST-KNN方法檢測離群點的精度明顯多于高維中使用MST-KNN算法來檢測離群點的精度。實驗證明了OLLE通過降維來發(fā)現(xiàn)離群點的方法是合理的。在這幾個實驗中，OLLE算法運行的時間多于MST-KNN方法運行的時間，這是因為OLLE是將數(shù)據(jù)降維，然后應用MST-KNN，因此計算時間比MST-KNN稍長。

表5 離群點檢測結果

5 參數(shù)分析

5.1 k的分析

如果k選取太小，離群點的k近鄰個數(shù)比較少，檢測不到離群點。如果k選取太大，不能凸顯數(shù)據(jù)的局部幾何結構。如圖4，只選取3個有代表的數(shù)據(jù)集Wine、Wdbc和Mnist進行實驗，觀察參數(shù)k對實驗結果的影響，其他幾個數(shù)據(jù)集也有類似的結果。

圖4 OLLE對不同的數(shù)據(jù)集，不同的近鄰k的分析結果

根據(jù)圖4可以看出，Wine數(shù)據(jù)集對k是不敏感的，因為離群點的離群程度比較高，雖然k發(fā)生變化，但是都能準確發(fā)現(xiàn)離群點。然而對于后兩個數(shù)據(jù)集而言，隨著k的變化，發(fā)現(xiàn)離群點的精度也在變化?？梢钥闯龃薕LLE方法發(fā)現(xiàn)離群點的精度同樣受k的影響，然而，當k在一個小范圍內變化時，檢測離群點的精度可能是不變的。可以說明OLLE在一定范圍內，對k不是非常敏感的。產生這一結果的原因是因為采用了求N(xi)的方法，當k在一定范圍變化時，近鄰集N(xi)可能是不變的。因此本文提出的方法在一定范圍內對參數(shù)k是不敏感的。

5.2 d的分析

只選取3個有代表的數(shù)據(jù)集Mnist、optical handwritten和PIE進行實驗，觀察參數(shù)d對實驗結果的影響，其他幾個數(shù)據(jù)集也有類似的結果。在OLLE方法中3個數(shù)據(jù)集的參數(shù)設置同4.3節(jié)。

根據(jù)圖5的實驗結果可知：不同的數(shù)據(jù)集，當映射到不同維數(shù)的低維空間時，檢測離群點的準確程度也是不同的。d的選取應該與數(shù)據(jù)集的本征維數(shù)有一定的關系，所以在d取不同值時，得到的離群點的準確程度也不同。圖5中Wine數(shù)據(jù)集不受d的影響。但optical handwritten和PIE受d的影響很大，當d在變化時，檢測離群點的準確程度也在變化，且均在d=30時，檢測離群點的準確程度最高。

圖5 OLLE對不同的數(shù)據(jù)集，不同的維數(shù)d的分析結果

5.3 ε參數(shù)分析

ε的選取主要作用是區(qū)分下近似與邊界。如果ε的值較大，可能導致一部分異常點被分到下近似中，這樣，就達不到使異常值遠離正常點的效果，進而達不到在降維的過程中區(qū)分離群點的效果。如果ε的值較小，所有樣本點都在上近似中，下近似中沒有點，也就達不到下近似中的點保持局部線性結構的效果，進而也達不到很好的降維效果。因此ε的取值，會影響在低維中檢測離群點的精確度。

5.4 時間復雜度分析

6 結束語

針對高維空間中數(shù)據(jù)集存在維數(shù)高、數(shù)據(jù)點稀疏、計算量大和不容易檢測異常值這些問題，本文提出了一種基于LLE的高維數(shù)據(jù)離群點檢測方法。OLLE方法是將數(shù)據(jù)集從高維空間降至低維空間的過程中保持數(shù)據(jù)的局部幾何結構，同時讓離群點與大多數(shù)點遠離，進而在低維空間用基于最小生成樹的KNN啟發(fā)式方法可以較好地檢測離群點。且OLLE方法滿足高維數(shù)據(jù)檢測離群點的5點要求。本文對8個數(shù)據(jù)集進行了測試，并選取4個已有方法進行了比對實驗，實驗結果證明了本文的方法可以有效地檢測離群點，并且改進的方法在一定的范圍內對k不敏感。參數(shù)的選取將是接下來考慮的問題。

[1] Maciá-Pérez F，Berna-Martinez J V，Oliva A F，et al.Algorithm for the detection of outliers based on the theory of rough sets[J].Decision Support Systems，2015，75：63-75.

[2] 江峰，杜軍威，眭躍飛，等.基于邊界和距離的離群點檢測[J].電子學報，2010，38（3）：700-705.

[3] Jiang Feng，Sui Yuefei，Cao Cungen.A hybrid approach to outlier detection based on boundary region[J].Pattern Recognition Letters，2011，32（14）：1860-1870.

[4] Wang Xiaochun，Wang Xiali，Ma Yongqiang，et al.A fast MST-inspired kNN-based outlier detection method[J].Information Systems，2015，48：89-112.

[5] 王敬華，趙新想，張國燕，等.NLOF：一種新的基于密度的局部離群點檢測算法[J].計算機科學，2013，40（8）：181-185.

[6] Bai Mei，Wang Xite，Xin Junchang，et al.An efficient algorithm for distributed density-based outlier detection on big data[J].Neurocomputing，2016，181：19-28.

[7] Ha J，Seok S，Lee J S.A precise ranking method for outlier detection[J].Information Sciences，2015，324：88-107.

[8] Xue Zhenxia，Shang Youlin，F(xiàn)eng Aifen.Semi-supervised outlier detection based on fuzzy rough C-means clustering[J].Mathematics and Computers in Simulation，2010，80（9）：1911-1921.

[9] Daneshgar A，Javadi R，Razavi S B S.Clustering and outlier detection using isoperimetric number of trees[J].Pattern Recognition，2013，46（12）：3371-3382.

[10] Jiang Feng，Liu Guozhu，Du Junwei，et al.Initialization of K-modes clustering using outlier detection techniques[J].Information Sciences，2016，332：167-183.

[11] 張小燕，胡昊，蘇勇.高維空間中針對離群點檢測的特征抽取[J].計算機工程與應用，2012，48（22）：189-194.

[12] 張凈，孫志揮，宋余慶，等.基于信息論的高維海量數(shù)據(jù)離群點挖掘[J].計算機科學，2011，38（7）：148-151.

[13] Ye Mao，Li Xue，Orlowska M E.Projected outlier detection in high-dimensional mixed-attributes data set[J].Expert Systems with Applications，2009，36：7104-7113.

[14] Bhattacharya G，Ghosh K，Chowdhury A S.Outlier detection using neighborhood rank difference[J].Pattern Recognition Letters，2015，60-61：24-31.

[15] Huang Jinlong，Zhu Qingsheng，Yang Lijun，et al.A nonparameter outlier detection algorithm based on natural neighbor[J].Knowledge-Based Systems，2016，92：71-77.

[16] Liu Feng，Zhang Weijie，Gu Suicheng.Local linear laplacian eigenmaps：A direct extension of LLE[J].Pattern Recognition Letters，2016，75：30-35.

[17] Niu Ben，Gu Hongbin，Sun Jin.Weighted kernel locally linear embedding for dimensionality reduction[J].Journal of Information&Computational Science，2014，11（7）：2109-2116.

[18] 吳曉婷，閆德勤.改進的非線性數(shù)據(jù)降維方法及其應用[J].計算機工程與應用，2011，47（2）：156-159.

[19] Malik Z K，Hussain A，Wu J.An online generalized eigenvalue version of Laplacian Eigenmaps for visual big data[J].Neurocomputing，2016，173：127-136.

[20] 向婷婷，羅運綸，王學松.流形學習及維數(shù)約簡在數(shù)據(jù)隱私保護中的應用[J].計算機工程與應用，2011，47（8）：79-82.

DENG Tingquan,LIU Jinyan,WANG Ning.Locally linear embedding method for high dimensional data outlier detection.Computer Engineering andApplications,2018,54（6）：115-122.

DENG Tingquan,LIU Jinyan,WANG Ning

College of Science,Harbin Engineering University,Harbin 150001,China

Due to the fact that data distribution is sparse in the high dimensional space,it can’t achieve desired effect in the high dimensional space by using the conventional methods.This paper proposes an Outlier detection method based on Locally Linear Embedding（OLLE）.In the proposed OLLE method,it establishes an effective rough set model which aims to retain the local lineal structure of samples in the lower approximation.Meanwhile,it constructs two weights to keep the local neighbor structure of all points and guarantee outliers away from normal points when high dimensional points are mapped into a low dimensional space.At last,this paper uses a minimum spanning tree-inspired k-nearest neighbors method to detect the outliers in the low dimensional space.A series of simulation experiments show that the OLLE can better keep the local geometric structure,and outliers are detected effectively in the low dimensional space.

locally linear embedding;dimensionality reduction;high dimensional data;outlier;k-nearest neighbors

由于高維空間中數(shù)據(jù)點比較稀疏，用傳統(tǒng)方法來檢測高維空間中的離群點不能達到預期效果。提出了一種基于局部線性嵌入的離群點檢測方法（OLLE）。在OLLE降維方法中，建立了一種有效的粗糙集模型，使數(shù)據(jù)集的下近似中的點保持局部線性結構。同時構造兩個權重，使所有樣本點保持局部近鄰結構，且保證在降維的過程中使離群點遠離正常點。最后，在低維空間中，采用基于最小生成樹的k-最近鄰啟發(fā)式方法來檢測離群點。通過一系列的模擬實驗，證明OLLE方法能達到很好的降維效果，并且在低維空間中可以有效地檢測出離群點。

局部線性嵌入；維數(shù)約減；高維數(shù)據(jù)；離群點；k-最近鄰

2016-10-24

2016-12-14

1002-8331（2018）06-0115-08

A

TP301

10.3778/j.issn.1002-8331.1610-0261

國家自然科學基金（No.11471001）。

鄧廷權（1965—），男，博士，教授，研究領域為圖像處理、計算機視覺、模式識別、人工智能、數(shù)據(jù)挖掘；劉金艷（1991—），女，碩士，研究方向為數(shù)據(jù)挖掘，E-mail：13019003609@163.com；王寧（1992—），女，碩士，研究領域為數(shù)據(jù)挖掘。