覃鳳婷，楊有龍，仇海全，2

1.西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，西安710126

2.安徽科技學(xué)院 信息與網(wǎng)絡(luò)工程學(xué)院，安徽 鳳陽233100

1 引言

隨著信息科學(xué)技術(shù)的發(fā)展，越來越多的數(shù)據(jù)被收集和儲存在數(shù)據(jù)庫中。從海量的數(shù)據(jù)中挖掘一些新穎的、潛在有用的、最終可理解的知識是非常有意義的。大部分研究的重點是構(gòu)造一個對大多數(shù)數(shù)據(jù)（正常值）的通用模式映射，然而，從知識發(fā)現(xiàn)的角度來看，異常數(shù)據(jù)通常比正常的更有趣，因為它們包含異常行為背后的有用信息。因此，異常值檢測漸漸引起廣大研究者的關(guān)注，成為數(shù)據(jù)挖掘領(lǐng)域的重要組成部分。其主要任務(wù)是識別出與大多數(shù)據(jù)明顯不同的數(shù)據(jù)。異常值檢測（也稱離群點檢測）往往在網(wǎng)絡(luò)入侵檢測[1-2]、電話和信用卡欺詐檢測[3]、醫(yī)療診斷[4]等方面有著重要的研究價值。例如，在醫(yī)療診斷中，誤診的情況遠遠少于確診的情況，但是誤診付出的代價往往比確診要高很多。

現(xiàn)有的異常值檢測方法大部分側(cè)重于從全局角度識別異常值，但是隨著數(shù)據(jù)量和維度的爆炸性增長，全局異常值的挖掘變得很難實現(xiàn)。為了克服這個困難，局部異常值檢測技術(shù)逐漸引起研究者的重視。文獻[5]最早提出了局部異常值概念，該方法依據(jù)對象與其k 近鄰的差異定義對象的異常度，高于給定閾值的數(shù)據(jù)對象即為異常值，但該方法并不適用于大規(guī)模高維數(shù)據(jù)集。因為高維數(shù)據(jù)集中存在部分不相關(guān)的屬性，導(dǎo)致一些異常值在全維空間中可能無法檢測出來。而且這種不相關(guān)的維度會影響異常值檢測的效率，同時會減小異常值挖掘的準確性。換言之，如果數(shù)據(jù)點的異常度是從全維空間中得到的，則大多數(shù)現(xiàn)有的異常值檢測算法的效率會非常的低。

在高維數(shù)據(jù)集中，異常值通常包含在一些由部分維度構(gòu)成低維子空間中，并且不同的異常對象可能存在于由不同的部分屬性張成的不同子空間中[6]，因此，如何找到包含局部異常值的子空間是高維異常值挖掘的一個非常關(guān)鍵的問題。另外，在全維空間中一般無法體現(xiàn)異常數(shù)據(jù)與其他正常數(shù)據(jù)的偏差，這些偏差往往嵌入在一些低維的子空間中。即，局部異常值可以投影到低維的子空間中，因此目標可轉(zhuǎn)為搜索有利于表征異常值的子空間。但是，數(shù)據(jù)集中的維度和數(shù)據(jù)對象的指數(shù)型增長使得異常子空間檢測成為一個NP 難問題[7]。直接使用窮舉搜索一一列舉顯然是不可行的。

為克服高維數(shù)據(jù)異常值檢測的缺點，本文提出了一種基于稀疏子空間的局部異常值檢測技術(shù)（Sparse Subspace-based method for Local Outliers Detection，SSLOD）。該方法首先在每個維度上分析每個對象的局部異常程度，據(jù)此刪減高維數(shù)據(jù)集中與異常值不相關(guān)的維度以及冗余的數(shù)據(jù)，對初始的數(shù)據(jù)集進行一個初步的約簡。然后，給出了滿足稀疏子空間的判斷標準。最后，利用改進的粒子群優(yōu)化算法在約簡屬性和對象后的子空間中搜索稀疏子空間，從而挖掘出異常值。實驗結(jié)果表明，SSLOD算法具有良好的性能。

2 相關(guān)工作

在數(shù)據(jù)集中，異常值往往是與大多數(shù)對象表現(xiàn)相對不一致的數(shù)據(jù)對象，以至于懷疑它是由其他機制產(chǎn)生的?，F(xiàn)存的異常值檢測方法可分為以下幾個類[8-9]：基于分布的、基于距離的、基于聚類的、基于密度的、基于角度的、基于子空間的。

基于分布的方法源自統(tǒng)計，它基于一些標準分布模型（正態(tài)、泊松等），如果一個數(shù)據(jù)點偏離標準分布的程度太大，則該數(shù)據(jù)點被認為是異常值[10]。例如，在正態(tài)分布中，異常值與數(shù)據(jù)期望的距離大于方差的3 倍[11]。但是在現(xiàn)實世界中，數(shù)據(jù)的分布函數(shù)的情況通常是未知的，尤其是對于高維數(shù)據(jù)集。由于在實際應(yīng)用中，數(shù)據(jù)并不能保證服從某一標準分布，從而無法從數(shù)據(jù)中找出異常值。

基于距離的方法不需要假設(shè)任何數(shù)據(jù)的分布情況，其基本思想是利用已有的距離度量方法（如曼哈頓距離、歐幾里得距離等）計算所有數(shù)據(jù)點之間的距離，根據(jù)距離關(guān)系識別異常值。文獻[12]將異常值定義為：當某個數(shù)據(jù)點與數(shù)據(jù)集中p%的數(shù)據(jù)點的距離超過d 時，該數(shù)據(jù)點被認為是異常值。該方法的難點是參數(shù)p 和d對異常值檢測結(jié)果影響大，且不易找到合適的值。同時，對于高維數(shù)據(jù)集在計算距離之前首先需要降維。

基于聚類的異常值檢測方法是由聚類算法優(yōu)化而來的[13]。在基于聚類的方法中，常見的異常值定義有兩種。一種是將聚類后的較小的簇視為異常值，但是不能判斷單獨的點是否是異常值；另一種是聚類后將不屬于任何簇的數(shù)據(jù)點視為異常值，但是聚類結(jié)果很影響異常值檢測的結(jié)果。

基于密度的方法的基本思想是通過數(shù)據(jù)點的局部密度檢測異常值，局部密度較低的數(shù)據(jù)點是異常值的可能性大。此類方法將異常值定義為局部密度與其鄰域內(nèi)的其他點明顯不同的數(shù)據(jù)點，換句話說就是正常點的局部密度與其鄰域點的密度非常相似。最早的基于局部密度的異常值檢測方法是LOF（Local Outlier Factor）[5]，該方法根據(jù)局部鄰域密度為每個數(shù)據(jù)點分配一個局部異常因子LOF，LOF值高的數(shù)據(jù)點視為異常值。隨后又出現(xiàn)了LOF模型的幾個擴展，例如，基于連接的異常值算法（Connection-based Outliers Factor，COF）[14]、不確定的局部離群因子（Uncertain Local Outlier Factor，ULOF）[15]、核密度估計異常分數(shù)（Kernel Density Estimates，Outiler Score，KDEOS）[16]、基于排序差的異常值檢測（Rank-difference based Outlier Detection，ROD）[17]、基于局部相對核密度的異常值檢測（Relative Density-based Outlier Score，RDOS）[18]等。這些方法在一定程度上提高了異常值檢測能力，但是，在測試階段的時間復(fù)雜度偏高。

基于角度的方法一般用于檢測高維數(shù)據(jù)集中的異常值。因為高維數(shù)據(jù)集一般分布在一個超球體的表面，此時歐式距離將隨著維度的增加漸漸失效?；诮嵌鹊漠惓Ｖ禉z測方法將對象與其k 個近鄰兩兩之間的夾角的方差作為判斷異常值的準則[19]。方差越小越說明該對象分布在整體數(shù)據(jù)的邊緣，越有可能是異常值。但是該方法無法將被幾個簇包圍的局部異常值檢測出來。另外，由于每次都需要計算對象與其近鄰兩兩之間的夾角，因此算法的復(fù)雜度非常高，導(dǎo)致算法的效率較低。

基于子空間的方法被設(shè)計為通過搜索子空間來檢測異常值。由于高維空間中的數(shù)據(jù)對象是稀疏的，異常值是根據(jù)部分維度而不是整個空間來確定的。因此一般是將數(shù)據(jù)集映射到子空間，在子空間中搜索異常數(shù)據(jù)。根據(jù)子空間的度量方法不同，基于子空間的異常值檢測方法又可以分為兩類：相關(guān)子空間投影方法和稀疏子空間投影方法。

相關(guān)子空間投影方法是在數(shù)據(jù)集中選出對異常值有意義的屬性構(gòu)建子空間來進行異常值檢測，投影方法一般有兩種：基于線性相關(guān)的[20]和基于統(tǒng)計模型的[21]。前者使用局部參考集之間的線性相關(guān)性創(chuàng)建子空間，而后者通過在局部參考集上應(yīng)用統(tǒng)計模型構(gòu)建子空間。例如，文獻[19]提出了一種在高維空間的軸平行子空間中檢測異常值的方法，該方法主要是在子空間中描述數(shù)據(jù)對象的異常度。文獻[22]用統(tǒng)計方法選擇相關(guān)子空間，然后在該子空間中根據(jù)數(shù)據(jù)的偏差程度確定了異常值排名算法，數(shù)據(jù)集中每個對象均對應(yīng)一個相關(guān)子空間。文獻[21]提出了一種子空間搜索方法來建立高對比度子空間，確定了基于密度的異常值排序。

稀疏子空間由密度明顯低于平均值的數(shù)據(jù)點構(gòu)成的，密度可以根據(jù)稀疏系數(shù)來測量。根據(jù)稀疏系數(shù)閾值，可以將高維數(shù)據(jù)集投影到稀疏子空間中，該稀疏子空間的點可設(shè)想為異常值。文獻[23]提出了一種高維異常值檢測算法，其主要思想是將高維數(shù)據(jù)投影到低維子空間，利用遺傳算法來確定異常值。該算法雖然提高了異常值檢測的效率，但是異常值的完整性和準確性并不能得到保證。為了解決這個問題，文獻[24]利用異常值的概念和改進的遺傳算法搜索子空間。文獻[25]利用網(wǎng)格概念來表示子空間，并研究了一種通過引入密度系數(shù)來提取稀疏子空間的方法，該方法提高了異常值檢測的準確性和完整性，但是由于構(gòu)造概念格的復(fù)雜性導(dǎo)致其檢測效率較低。文獻[26]為提出了一種基于屬性相關(guān)性的局部異常值檢測算法，該算法不同于上面方法的是使用粒子群算法搜索子空間，大大提高了異常數(shù)據(jù)的挖掘效率。

3 約簡數(shù)據(jù)集

在高維數(shù)據(jù)集中實現(xiàn)異常值檢測的高精度和高效率是一個挑戰(zhàn)。本章提出了一種新的數(shù)據(jù)集約簡方法，其作用是進行異常值檢測算法之前減少數(shù)據(jù)對象和維數(shù)。該方法通過每個維度上分析數(shù)據(jù)對象的異常度，將與異常值無關(guān)的維度與異常值相關(guān)的維度分來，將與異常值無關(guān)的冗余數(shù)據(jù)識別出來。

假設(shè)D 是N×d 維的空間，A={A1,A2,…,Ad}表示屬性集，X={X1,X2,…,XN}表示N 個數(shù)據(jù)點，其中Xi={xi1,xi2,…,xid}。對象Xi在屬性Aj上所對應(yīng)的值表示為xij(i=1,2,…,N;j=1,2,…,d)。通過檢測每個維度上數(shù)據(jù)點的密度，識別與異常值不相關(guān)的屬性和數(shù)據(jù)對象。密度較大的數(shù)據(jù)點一般聚集在密集區(qū)域，而密集區(qū)域的數(shù)據(jù)點是由一些相似特征構(gòu)成的，這些特征對于檢測異常值往往作用不大。因此，在每個維度上分析對象的密度可以更好地區(qū)分與異常值不相關(guān)的維度和相關(guān)的維度。這里利用對象在每個屬性上的k 最近鄰估計其在該屬性上的密度。

直觀上講，ρ(xij)的值越大，就意味著xij是在該維度上是正常值的可能性越大，因此其在密集區(qū)域的可能性就越大；反之，表示xij在該維度上是異常值的可能性越大，即其在稀疏區(qū)域的可能性較大。

由于密集區(qū)域往往由具有相似特征的數(shù)據(jù)點構(gòu)成。為了找到密集的區(qū)域，用γij=1/ρ(xij)表示一維對象xij的異常因子。顯然，λij的值越大，xij在屬性Aj上越可能是異常的，說明xij越可能在稀疏區(qū)域，反之亦然。

接下來用K(N×d）表示原始數(shù)據(jù)集所對應(yīng)的稀疏密度矩陣，Kij(i=1,2,…,N;j=1,2,…,d)表示矩陣K 中的元素。給定異常因子閾值 τ ，若 γij＜τ ，將Kij設(shè)置為1，表示xij是在屬性Aj上是正常值，包含在密集區(qū)域；若 γij＞τ ，將Kij設(shè)置為0，表示xij在屬性Aj上是異常值，在一個稀疏區(qū)域。在形成稀疏密度矩陣K 的過程中涉及到參數(shù)k 的選取問題。k 值表示在一維屬性上對象的近鄰數(shù)，取值較小時，異常因子γij幾乎沒有意義。顯而易見，k 值應(yīng)該小于N（數(shù)據(jù)集中對象的數(shù)量）。參考其他屬性約簡方法PCKA[27]，將k 值設(shè)置為。當然，在實際應(yīng)用中，參數(shù)k 也可以由用戶根據(jù)相關(guān)領(lǐng)域的知識自行設(shè)定并且調(diào)優(yōu)。

下面用一個簡單的例子說明生成稀疏密度矩陣的過程。表1 是由一個病例信息組成的數(shù)據(jù)集，包括7 個屬性和12個數(shù)據(jù)對象。屬性A1表示性別，0表示女性，1表示男性；屬性A2表示年齡；屬性A3和A4分別表示鼻塞程度和頭疼程度，其值范圍從0到5，表示癥狀從輕微到嚴重。屬性A5的值為0時表示喉嚨不痛，1時表示喉嚨痛；屬性A6代表患者的體溫；屬性A7的值從0 取到3，分別表示感冒程度是由輕微到嚴重。根據(jù)以上參數(shù)k 的取值方法，k=3，計算每一個屬性下的一維數(shù)據(jù)點的異常因子γij，設(shè)定異常因子閾值τ 的取值為0.7，進一步得到該數(shù)據(jù)集對應(yīng)的稀疏密度矩陣，如表2所示。

表1 病例信息數(shù)據(jù)

表2 病例信息數(shù)據(jù)的稀疏密度矩陣

在表2中，屬性A1和A5在稀疏密度矩陣中的值都是1，說明這兩個屬性上的對象均是正常值，處在一個相對密集的區(qū)域，這些屬性顯然對異常值檢測沒有作用，這表明了屬性A1和A5是與異常值不相關(guān)的屬性。因此，在檢測異常值之前，就可以先將這兩個屬性修剪掉。同理，第9 條數(shù)據(jù)在各個維度上的Kij值均為1，說明其在各個維度上均為正常值，為冗余數(shù)據(jù)，應(yīng)修剪掉。當然，在不影響挖掘結(jié)果的正確性的前提下，對這些屬性和對象進行初步約簡可以顯著地提高異常值挖掘的效率，數(shù)據(jù)集初步約簡方法總結(jié)見算法1和算法2。

算法1稀疏密度矩陣的形成

4 基于初步約簡的稀疏子空間

4.1 稀疏子空間

局部異常值是在部分維空間中與其他數(shù)據(jù)點表現(xiàn)明顯不一致的數(shù)據(jù)對象。本文利用搜索數(shù)據(jù)空間中稀疏子空間的方法檢測局部異常值。稀疏子空間是指數(shù)據(jù)的密度明顯低于平均值的數(shù)據(jù)點構(gòu)成的子空間，其中的數(shù)據(jù)對象即為異常值[23]。下面介紹稀疏子空間的相關(guān)知識。

給定一個N×d高維數(shù)據(jù)集D，將每個屬性上的數(shù)據(jù)劃分為φ個離散區(qū)間。這些離散區(qū)間是在等深的基礎(chǔ)上劃分的，因此每個區(qū)間上都包含g=1φ的對象。這里使用等深劃分而不是等頻劃分的原因是不同位置的數(shù)據(jù)可能具有不同的密度。在d維屬性上選擇t個屬性構(gòu)成一個t維的數(shù)據(jù)集，記為D1。如果屬性在統(tǒng)計上是獨立的，根據(jù)伯努利概率，N個對象在t維屬性上隨機分布的概率是gt，對應(yīng)的數(shù)學(xué)期望可以表示為N?gt，標準差是在選擇出的t個屬性上分別取一個區(qū)間，構(gòu)成另一個t維數(shù)據(jù)集，記為D2。由于真實數(shù)據(jù)集在統(tǒng)計上并不一定是獨立的，因此t維數(shù)據(jù)集D2中對象的實際分布與原數(shù)據(jù)集D1的期望值存在著顯著地差異。那些低于平均值的異常偏差通常是由異常數(shù)據(jù)造成的，因此更有利于異常值檢測。

假設(shè)數(shù)據(jù)是均勻分布的，t維數(shù)據(jù)集D2中的對象總個數(shù)可以近似為正態(tài)分布。設(shè)n(D2)是t維數(shù)據(jù)集D2中對象的個數(shù)，為了度量子空間中數(shù)據(jù)的偏離程度，D2的稀疏系數(shù)[23]定義為：

從（2）式中可以得到，若D2是稀疏子空間，那么D2中的數(shù)據(jù)點個數(shù)會小于平均值，n(D2)＜N?gt。此時，S(D2)的值定是一個負數(shù)。然而，異常值往往分布在比較稀疏的區(qū)域，即包含在某個稀疏子空間中。

因此，稀疏子空間即為：當S(D2)小于某一個閾值θ(θ ＜0)時，D2就是一個稀疏子空間，其中的數(shù)據(jù)對象就是異常值，n(D2)即為異常值的個數(shù)。

要找到準確稀疏子空間的一個重要問題是如何選擇參數(shù)t和φ。在d維屬性中選擇t個屬性形成N×t的子空間，每個子空間含有期望數(shù)是N?(1/φ)t的數(shù)據(jù)對象。因此，當t很大時，N?(1/φ)t的值會很小，而稀疏因子閾值θ是一個負數(shù)，導(dǎo)致n(D2)很小，從而無法檢測出異常值。例如，若φ=10，t=5，t維子空間中數(shù)據(jù)對象的個數(shù)須大于105，否則數(shù)據(jù)對象的期望值將會比1小，即t維子空間中包含小于1 個點數(shù)據(jù)點，這意味著不可能找到有著高稀疏系數(shù)且至少包含一個數(shù)據(jù)點的稀疏子空間。因此，參數(shù)t和φ的值應(yīng)該設(shè)置的足夠小，使得恰好包含一個數(shù)據(jù)點的子空間的稀疏系數(shù)是一個合理的負值。同時φ應(yīng)該設(shè)置的夠大，使得每個維度上有足夠數(shù)量的區(qū)間對應(yīng)一個合理的局部性概念。一旦給定了參數(shù)φ，參數(shù)t的范圍將由極端情況導(dǎo)出。假設(shè)t維子空間是一個空子空間，有n(D2)=0，計算該空子空間的稀疏系數(shù)，可得：

本文的算法均選取參數(shù)t的上界。對于參數(shù)θ的取值，θ=-3 是決定參數(shù)t的一個很好的參考值[23]。在具體應(yīng)用中，用戶也可以根據(jù)實際情況設(shè)定不同的θ值，以確定適當?shù)膖值。

4.2 改進的粒子群算法搜索稀疏子空間

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法一種基于群體的智能全局搜索優(yōu)化算法[28]。由于概念簡單，參數(shù)少，收斂速度快，PSO算法漸漸被應(yīng)用到各類算法中。本文將使用改進的粒子群算法搜索稀疏子空間。

4.2.1 標準粒子群算法

PSO算法首先初始化一群粒子，即優(yōu)化問題的候選解。每個粒子都有一個位置向量和一個決定方向和步長的速度向量，并且都有一個由優(yōu)化函數(shù)給出的適應(yīng)值。然后粒子在解空間中跟隨最優(yōu)的粒子進行搜索并且更新自身的位置和速度。同時粒子自身的最優(yōu)位置（稱為Pbest）和整個種群的最優(yōu)位置（稱為Gbest）也在算法的每次迭代中不斷地更新直到達到終止條件，最后得到的全局最優(yōu)位置就是優(yōu)化問題的最優(yōu)解。粒子的速度和位置可表示為：

4.2.2 改進的粒子群算法

隨機慣性權(quán)重在PSO算法中，慣性權(quán)重控制粒子的歷史因素對其當前狀態(tài)的影響程度。為了平衡算法的全局搜索能力以及它的局部搜索能力，可以對慣性權(quán)重進行調(diào)整。在大多數(shù)改進的PSO 算法中，權(quán)重ω一般使用線性遞減的方法進行更新。這種更新方法在搜索算法的前期時，ω有利于取到全局搜索的最優(yōu)值但是搜索效率比較低；在后期時ω雖然有利于加快算法的收斂速度，但是很容易導(dǎo)致算法陷入局部最優(yōu)。

為了克服這個缺點，可以將慣性權(quán)重設(shè)置為隨機變量。慣性權(quán)重的隨機性可以使粒子在前期和后期都有可能取到較大或較小的權(quán)值，有利于算法跳出局部最優(yōu)，同時可以提高算法的全局搜索能力。因此，提出以下慣性權(quán)重的公式：

其中，μmin表示隨機慣性權(quán)重的最小值，μmax表示其最大值，rand( )是[0,1]之間的隨機數(shù)。μmin和μmax的初始值分別設(shè)定為0.5和0.95。

異步學(xué)習(xí)因子在PSO 中，若學(xué)習(xí)因子c1和c2在優(yōu)化問題過程中有著不同的變化方式，那這兩個學(xué)習(xí)因子就是異步變化的。異步學(xué)習(xí)因子表示為：

其中，c1start和c2start分別是c1和c2的初始值，c1final和c2final分別表示其迭代后的終值。t是當前迭代次數(shù)，Tmax是最大迭代次數(shù)。

若在前期階段取較大的c1和較小的c2，會使得粒子更多地向自身最優(yōu)學(xué)習(xí)而較少地向全局最優(yōu)學(xué)習(xí)，可以使粒子的全局搜索能力得到提升。在后期取較小的c1和較大的c2，會使得粒子更多地向全局最優(yōu)學(xué)習(xí)而較少地向自身最優(yōu)學(xué)習(xí)，有利于算法快速收斂到全局最優(yōu)解。因此，改進PSO 算法的初始參數(shù)設(shè)定如下：c1start=2，c1final=0.5，c2start=0.5，c2final=2。

假設(shè)約簡后的數(shù)據(jù)集D1的維度是d1。本文利用該改進的粒子群算法在約簡的數(shù)據(jù)集中搜索稀疏子空間。在d1中選擇t個屬性，而每個屬性被劃分為φ份，此時將會有φt種子空間，每一種子空間即為粒子群算法的一個候選解。粒子群算法從p個隨機解開始，隨后根據(jù)局部最優(yōu)Pgest和全局最優(yōu)Gbest對隨機解的位置和速度進行迭代和更新，并且對可能的子空間進行隨機搜索。每一個可能的子空間D2都有一個稀疏系數(shù)S(D2)，稀疏系數(shù)S(D2)即為粒子群優(yōu)化算法對應(yīng)的適應(yīng)度函數(shù)。迭代中Pgest和Gbest都是通過適應(yīng)度函數(shù)得到的。這個過程一直持續(xù)到達到最大迭代次數(shù)為止。在算法的每一個階段都是在追隨最佳的t個屬性（即具有最小的稀疏系數(shù)），在算法的最后階段，這t個屬性為數(shù)據(jù)集中與異常值最相關(guān)的特征集。粒子群搜索算法的總體過程見算法3。

算法3 用改進的粒子群算法搜索稀疏子空間

輸入：約簡后的數(shù)據(jù)集D1，稀疏因子閾值θ，原始數(shù)據(jù)集數(shù)據(jù)對象的總數(shù)N=||D。

輸出：異常值集合O。

5 實驗結(jié)果分析

為了說明SSLOD算法的有效性和異常因子閾值以及稀疏因子閾值方法的準確性，在仿真數(shù)據(jù)集上和UCI數(shù)據(jù)庫真實數(shù)據(jù)集上進行了測試。

仿真數(shù)據(jù)集：用文獻[26]的產(chǎn)生數(shù)據(jù)方法生成了3個仿真數(shù)據(jù)集。假設(shè)數(shù)據(jù)服從正態(tài)分布，首先生成均值是0，方差是1的數(shù)據(jù)集；其次向數(shù)據(jù)集額外增加0.1%的點作為異常值，加入的數(shù)據(jù)服從0到1的均勻分布；最后不斷復(fù)制第一步生成的數(shù)據(jù)集擴充數(shù)據(jù)量。基本信息見表3。首先說明在算法過程中的屬性初步約簡的性能，表4列出了約簡的數(shù)據(jù)屬性和對象隨著異常因子閾值τ的變化趨勢?？梢园l(fā)現(xiàn)，異常因子閾值τ的增大，屬性和對象個數(shù)顯著減少。例如，當τ=0.005 時，仿真數(shù)據(jù)集Data1、Data2、Data3減少的屬性所占比例分別是16%、17%、20.7%，減少的數(shù)據(jù)對象所占的比例分別是13.31%、18.45%、14.29%。將一個N×d高維數(shù)據(jù)集D每個屬性上的數(shù)據(jù)劃分為φ個離散區(qū)間，在d維屬性中選擇t個，那么這t維屬性就可以構(gòu)成φt種子空間。所以減少屬性和數(shù)據(jù)對象，以減少需要搜索的子空間的個數(shù)，有利于提高算法的效率。

表3 仿真數(shù)據(jù)集信息

表4 約簡對象及屬性的比例%

分析了異常因子閾值τ和稀疏系數(shù)閾值θ對算法精度（Accuracy）的影響。為表示精度，先給出混淆矩陣，見表5?；煜仃囈话銘?yīng)用在二分類中，這里將異常值認為是正類。精度[29]的計算公式如下：

表5 混淆矩陣

如圖1 給出了算法精度隨異常因子閾值τ變化情況，可以看出，當異常因子閾值τ逐漸增大時，算法的精度會略下降。這是因為τ越大，被減少的屬性和對象就越多，使得產(chǎn)生的稀疏子空間可能會丟失一些有用的信息，導(dǎo)致算法的精度出現(xiàn)下降的趨勢，由圖2 的信息可以看出隨著稀疏系數(shù)閾值θ的增大，算法的精度在漸漸地上升，但是在后期上升的速度要緩慢一些。這說明在后期算法的精度前后相差不大，這種現(xiàn)象可以給在實際試驗中如何取θ值做一個較佳的參考。

圖1 異常因子閾值τ 對算法精度的影響

圖2 稀疏系數(shù)閾值θ 對算法精度的影響

UCI數(shù)據(jù)集：在3個真實的數(shù)據(jù)集上實現(xiàn)SSLOD算法，這些數(shù)據(jù)集是高度類不平衡的，一般應(yīng)用在數(shù)據(jù)分類和其他機器學(xué)習(xí)算法中，數(shù)據(jù)集中的少數(shù)類認為是異常值，多數(shù)類是正常值。另外，在實驗之前還對數(shù)據(jù)進行了清洗以便處理分類屬性和缺失數(shù)據(jù)。表6 給出了UCI真實數(shù)據(jù)集的基本信息。對于這3個不同的數(shù)據(jù)集均將參數(shù)φ設(shè)置為7，稀疏系數(shù)閾值θ可根據(jù)仿真數(shù)據(jù)集的分析結(jié)果選擇，建議在[-1.5，-0.5]之間選擇，其余參數(shù)的設(shè)定已在相關(guān)章節(jié)給出。將算法SSLOD的精度和效率與遺傳算法和標準粒子群算法進行了對比。觀察表7，在相同的數(shù)據(jù)集下，提出的算法SSLOD 算法的精度均高于其余兩種算法，特別是對于數(shù)據(jù)集Internet Usage Data，SSLOD 的精度比遺傳算法的精度提高了13.07%。由圖3中可以看出，SSLOD的效率在不同的數(shù)據(jù)集上均高于其余兩種算法。這是因為SSLOD算法在搜索稀疏子空間之前先用算法1和2約簡了原始數(shù)據(jù)集維度和對象，然后用算法3對標準粒子群算法慣性權(quán)重隨機化，對其學(xué)習(xí)因子異步化，使搜索算法不易陷入局部最優(yōu)，同時又可以快速收斂到全局最優(yōu)。與標準粒子群算法相比，進一步提高了算法效率。與遺傳算法相比，不需要進行交叉變異等遺傳操作，降低了計算復(fù)雜度，提高了算法效率。

表6 UCI數(shù)據(jù)集信息

表7 3種算法精度比較%

圖3 3種方法的效率比較

算法1 的復(fù)雜度主要體現(xiàn)在第3 步到第5 步，若采用蠻力法構(gòu)造KNN 圖，N個對象的計算復(fù)雜度為O(N2)，而使用R*-tree索引結(jié)構(gòu)可以將搜索k近鄰的復(fù)雜度減少到O(N?lgN)，第6步到第11步以及算法2復(fù)雜度均為線性階，因此算法1 和算法2 的復(fù)雜度即為O(N?lgN)。算法3 的計算量主要體現(xiàn)在更新速度、位置和計算適應(yīng)度函數(shù)。設(shè)粒子規(guī)模是p，最大迭代次數(shù)是T，約簡后數(shù)據(jù)集的大小是N，待搜索的空間被劃分為φ×t份。速度和位置更新的復(fù)雜度為O(T?p?2N)，計算適應(yīng)度函數(shù)的復(fù)雜度是O(T?p?φ?t)。因此，SSLOD算法總時間復(fù)雜度為O(N?lgN)+O(T?p?2N)+O(T?p?φ?t)。

6 結(jié)束語

在高維數(shù)據(jù)集中，異常數(shù)據(jù)往往在部分維度構(gòu)成的子空間中能被識別，而在高維空間中表現(xiàn)并不異常，這使得高維空間中直接檢測異常值變得困難。此外，不同的異常值可能存在于由不同屬性張成的不同子空間中，因此需要搜索有利于表征異常值的子空間。本文針對上述問題，在檢測異常值之前先對屬性和數(shù)據(jù)對象進行約簡，并用改進的粒子群搜索算法在約簡后的數(shù)據(jù)集中搜索稀疏的子空間，進一步將局部異常值挖掘出來。在仿真數(shù)據(jù)集上充分分析了SSLOD 算法的有效性，并將該算法與遺傳算法和標準粒子群算法在真實數(shù)據(jù)集上作比較。綜合實驗結(jié)果表明，本文所提出的基于稀疏子空間局部異常值算法具有良好的性能和較高的效率。