基于稀疏子空間的局部異常值檢測(cè)算法

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

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

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

1 引言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

接下來用K(N×d）表示原始數(shù)據(jù)集所對(duì)應(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上是異常值，在一個(gè)稀疏區(qū)域。在形成稀疏密度矩陣K 的過程中涉及到參數(shù)k 的選取問題。k 值表示在一維屬性上對(duì)象的近鄰數(shù)，取值較小時(shí)，異常因子γij幾乎沒有意義。顯而易見，k 值應(yīng)該小于N（數(shù)據(jù)集中對(duì)象的數(shù)量）。參考其他屬性約簡方法PCKA[27]，將k 值設(shè)置為。當(dāng)然，在實(shí)際應(yīng)用中，參數(shù)k 也可以由用戶根據(jù)相關(guān)領(lǐng)域的知識(shí)自行設(shè)定并且調(diào)優(yōu)。

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

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

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

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

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

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

4.1 稀疏子空間

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

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

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

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

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

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

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

4.2 改進(jìn)的粒子群算法搜索稀疏子空間

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

4.2.1 標(biāo)準(zhǔn)粒子群算法

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

4.2.2 改進(jìn)的粒子群算法

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

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

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

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

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

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

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

算法3 用改進(jìn)的粒子群算法搜索稀疏子空間

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

輸出：異常值集合O。

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

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

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

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

表4 約簡對(duì)象及屬性的比例%

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

表5 混淆矩陣

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

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

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

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

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

表7 3種算法精度比較%

圖3 3種方法的效率比較

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

6 結(jié)束語

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