一種自適應(yīng)的高維離群點識別方法

，，，

(江西中醫(yī)藥大學(xué)計算機學(xué)院，江西南昌330004)

高維數(shù)據(jù)中的離群點給數(shù)據(jù)分析工作帶來了不便，比如在中藥數(shù)據(jù)的藥性有效成分分析、量效關(guān)系分析等數(shù)據(jù)分析過程中，由于離群點的存在使得數(shù)據(jù)分析結(jié)果有偏差或錯誤。數(shù)據(jù)分析工作中的部分數(shù)據(jù)高達成千上萬維，隨著數(shù)據(jù)維度的增長，當(dāng)數(shù)據(jù)維度達到一定規(guī)模時，數(shù)據(jù)點的分布變得稀疏，就會出現(xiàn)“差距趨零”現(xiàn)象，將距離作為度量數(shù)據(jù)間差異的方式將會失效，這時傳統(tǒng)的基于距離的離群點識別方法將無法直接有效地應(yīng)用于高維數(shù)據(jù)中。常用的解決方法是先將高維數(shù)據(jù)映射到低維空間，再在低維空間應(yīng)用相關(guān)算法進行離群點識別。

文獻[1-4]提出使用PCA來提取數(shù)據(jù)樣本的特征，但PCA是線性降維，只能提取數(shù)據(jù)間的線性關(guān)系，從而導(dǎo)致在處理高維數(shù)據(jù)時存在著統(tǒng)計特性的漸近性難以實現(xiàn)等問題；文獻[5-10]采用了受限玻爾茲曼機(restricted Boltzmann machine，RBM)或高斯受限玻爾茲曼機(Gaussian restricted Boltzmann machine，GRBM)提取數(shù)據(jù)特征，其能夠有效地、非線性地提取出高維數(shù)據(jù)的特征，但參數(shù)難以設(shè)定為較優(yōu)值；文獻[11]提出通過遺傳算法優(yōu)化RBM的網(wǎng)絡(luò)權(quán)重等參數(shù)，但未對各層單元數(shù)進行具體優(yōu)化?；诰嚯x的離群點識別方法的算法思想簡單有效，被廣泛地研究和應(yīng)用[12-17]，其中文獻[12-13]提出了針對不確定性數(shù)據(jù)和流數(shù)據(jù)的離群點識別方法；文獻[15]提出了基于屬性距離和的識別方法，但此類方法的識別準(zhǔn)確率受用戶指定的參數(shù)影響；文獻[17]提出一種改進的、無需提供參數(shù)的基于距離和的識別方法。

基于此，本文提出一種自適應(yīng)的高維離群點識別方法，該方法利用經(jīng)遺傳算法優(yōu)化的GRBM對高維數(shù)據(jù)進行非線性特征提取，獲得高維數(shù)據(jù)的較優(yōu)低維表示，然后通過使用本文提出的自適應(yīng)離群點識別方法對較優(yōu)低維數(shù)據(jù)進行離群點識別。從理論上分析，該方法能有效地非線性提取出高維數(shù)據(jù)的特征，無需提供參數(shù)就可有效識別出高維數(shù)據(jù)中的離群點。

1 相關(guān)算法

1.1 GA-GRBM算法

受限玻爾茲曼機[18](RBM)是由可見層和隱藏層構(gòu)成的基于能量的雙層無向神經(jīng)網(wǎng)絡(luò)模型，層間相互連接，層內(nèi)無連接。RBM默認其可見層單元是二值的，本文所用的是可見層單元為實值的GRBM，網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。由于GRBM的輸入單元是實值的，不用對輸入數(shù)據(jù)二值化，因此不會造成數(shù)據(jù)信息的缺失，能更有效地提取出數(shù)據(jù)的特征。

圖1 GRBM網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 GRBM network architecture

GRBM的可見單元個數(shù)是輸入數(shù)據(jù)的維度，隱藏單元的個數(shù)h、連接權(quán)重w和可見層偏置a，隱藏層偏置b的初始值可以通過文獻[18]方法給出，但隱藏層單元數(shù)h設(shè)置是否合理將會影響到特征提取的結(jié)果，且不同的偏置值和隱藏層單元數(shù)組合有不同的特征提取效果。此外，隨著數(shù)據(jù)維度增加，高斯受限玻爾茲曼機的參數(shù)也會增加，必然會導(dǎo)致算法的復(fù)雜度增加，因此本文應(yīng)用遺傳算法來尋找最優(yōu)的a初始值和h參數(shù)組合，從而加速高斯受限玻爾茲曼機的優(yōu)化參數(shù)速度，提出了遺傳算法優(yōu)化的GRBM方法(genetic algorithm-Gaussian restricted Boltzmann machine，GA-GRBM)。

GA-GRBM通過遺傳算法找到最優(yōu)的可見單元偏置初始值與隱藏單元數(shù)，相較于GRBM能夠在更少的訓(xùn)練次數(shù)下更有效地提取數(shù)據(jù)特征。如圖2所示，GA-GRBM的優(yōu)化過程主要分為兩個階段。第一階段是通過遺傳算法尋找最優(yōu)參數(shù)組合，首先將可見單元偏置a、隱藏層單元數(shù)h組合作為基因編碼來隨機初始化一個種群，將GRBM的重構(gòu)誤差作為適應(yīng)度函數(shù)，之后根據(jù)適應(yīng)度函數(shù)來選取、交叉、變異形成新的種群。以此種方式開始遺傳迭代，直到達到指定最大遺傳次數(shù)或適應(yīng)函數(shù)值變化趨于穩(wěn)定，獲得最優(yōu)的參數(shù)組合。在GA-GRBM的第二個階段中，將最優(yōu)的參數(shù)組合解碼作為GA-GRBM模型的隱藏層單元個數(shù)h和可見單元偏置a的參數(shù)初始值，其他參數(shù)初始值按照文獻[19]中的方式設(shè)置；然后采用對比散度方法來快速精調(diào)GRBM參數(shù)，獲得一個穩(wěn)定的GA-GRBM模型，最后利用此模型將高維數(shù)據(jù)非線性地映射到低維空間。

圖2 GA-GRBM流程圖Fig.2 GA-GRBM flow chart

值得注意的是，GA-GRBM是一種自編碼和解碼的非線性提取特征方法，能在盡量不損失原有特征信息的條件下，獲得更低維的強解釋的綜合特征。比如高維數(shù)據(jù)樣本o(o1,o2,…,on)經(jīng)過非線性提取特征后變成低維數(shù)據(jù)樣本p(p1,p2,…,pm)，樣本p是高維樣本o的低維表示，其中oi≠pj;i∈n,j∈m;m

1.2 自適應(yīng)的離群點識別算法

屬性距離和的離群點識別方法認為離群點是指與數(shù)據(jù)集中其他所有數(shù)據(jù)對象的距離之和最大的前n個數(shù)據(jù)對象，該方法思想簡單有效，但識別準(zhǔn)確率卻深受參數(shù)n的影響。為此，在屬性距離和的離群點識別方法的基礎(chǔ)上，提出了一種自適應(yīng)的離群點識別算法(adaptive outlier recognition method，AORM)，該方法無需人為設(shè)置參數(shù)就可以自適應(yīng)地輸出離群點。

AORM算法運用了盒圖[19]的思想，不需要提供任何參數(shù)就可以有效識別出離群點，解決了基于距離的離群點識別方法對參數(shù)敏感的問題。AORM首先計算每個數(shù)據(jù)對象與數(shù)據(jù)集中其他數(shù)據(jù)對象的距離，得到距離矩陣M；然后依次對矩陣的每一行求和，得到數(shù)據(jù)對象到其他數(shù)據(jù)對象的距離之和的集合S(s1，s2,…,si)，并將該集合升序排序；最后根據(jù)盒圖的原理自動輸出離群點。AORM方法的具體步驟如下。

輸入：數(shù)據(jù)集D。

輸出：離群點。

1)計算數(shù)據(jù)集合D中各個數(shù)據(jù)對象之間的屬性距離dij,得到距離矩陣M；

3)對步驟2)得到的距離之和的集合S(s1，s2,…,si)升序排序；

4)計算S的max值Smax，再將si與Smax比較，si值大于Smax的數(shù)據(jù)對象都被識別為離群點；

5)輸出離群點。

其中Smax=Q3+1.5IQR，IQR=Q3-Q1，Q3和Q1是集合S的上四分位數(shù)和下四分位數(shù)。

2 自適應(yīng)的高維離群點識別方法

隨著數(shù)據(jù)維度的增長，當(dāng)數(shù)據(jù)維度達到一定規(guī)模時，數(shù)據(jù)點的分布變得稀疏，若使用常用的距離測度(比如歐氏距離)，數(shù)據(jù)點之間的距離將趨于相等，這就是“差距趨零”現(xiàn)象；這時傳統(tǒng)的基于距離的離群點識別方法將無法直接有效地應(yīng)用于高維數(shù)據(jù)集?；诖耍疚膶A-GRBM算法和AORM算法組合優(yōu)化，提出了一種自適應(yīng)的高維離群點識別方法(adaptive high-dimensional outlier recognition method, AHORM)。

AHORM模型的結(jié)構(gòu)如圖3所示，AHORM的思想是利用GA-GRBM算法將高維數(shù)據(jù)映射到低維空間，之后在低維空間中使用基于距離的自適應(yīng)的離群點識別方法輸出離群點。模型的具體構(gòu)建過程如下：

1)遺傳算法優(yōu)化GRBM。

(a)隨機初始化種群，種群中的每個個體都是可見層偏置a和隱藏層單元數(shù)h組成的基因編碼片段；

(b)將GRBM的重構(gòu)誤差作為適應(yīng)度函數(shù)，對種群進行選擇、交叉和變異，得到新種群；

(c)循環(huán)步驟(b)，直到達到收斂條件停止遺傳，得到最優(yōu)參數(shù)組合。

2)GA-GRBM提取數(shù)據(jù)特征。

(a)將最優(yōu)基因片段解碼作為GA-GRBM可見層偏置初始值和隱藏層單元數(shù)，再利用對比散度方法訓(xùn)練模型、精調(diào)參數(shù)，構(gòu)建一個穩(wěn)定GA-GRBM特征提取模塊；

(b)利用GA-GRBM將高維數(shù)據(jù)非線性地映射到低維數(shù)據(jù)空間，得到高維數(shù)據(jù)的最優(yōu)低維表示。

3)AORM自適應(yīng)識別離群點。

(a)計算低維數(shù)據(jù)各自之間的距離得到距離矩陣，對矩陣的每一行求和并升序排列；

(b)根據(jù)盒圖原理找出屬性距離和異常的數(shù)據(jù)對象，輸出離群點。

圖3 AHORM模型結(jié)構(gòu)Fig.3 AHORM model structure

AHORM模型的優(yōu)勢在于可以有效地應(yīng)用于高維數(shù)據(jù)，通過將高維數(shù)據(jù)映射到低維空間，避免“差距趨零”現(xiàn)象的發(fā)生；這時基于距離的離群點識別方法不再失效，可以通過AHORM模型中的AORM算法模塊自適應(yīng)地輸出數(shù)據(jù)中離群點。

3 實驗與分析

本節(jié)對GA-GRBM算法、AORM算法和AHORM算法分別做了對比驗證實驗，所有的實驗環(huán)境均為Windows10(64位)操作系統(tǒng)，Intel Core i5-3470 CPU@3.2GHz，8GiB內(nèi)存，Pycharm Python3.5編程平臺。

首先將GA-GRBM與傳統(tǒng)的GRBM做了對比驗證實驗。實驗數(shù)據(jù)采用了UCI數(shù)據(jù)集(http://archive.ics.uci.edu/ml)中的Communities and Crime數(shù)據(jù)集，該數(shù)據(jù)經(jīng)處理后包含了1 000個數(shù)據(jù)樣本，每個樣本各有112個屬性。傳統(tǒng)GRBM的可見層單元數(shù)為樣本屬性個數(shù)112，各層偏置和權(quán)重初始值、隱藏層單元數(shù)根據(jù)文獻[18]中的方法設(shè)定，權(quán)重w的初始值由正態(tài)分布(0,0.01)生成，各層偏置初始值為零，隱藏層單元數(shù)根據(jù)數(shù)據(jù)信息估算給出。GA-GRBM的可見層偏置初始值和隱藏層單元數(shù)由遺傳算法確定，其他參數(shù)設(shè)定同傳統(tǒng)GRBM一樣。遺傳算法的種群個數(shù)100，父代個數(shù)和子代個數(shù)均為50，當(dāng)遺傳代數(shù)達到100時停止遺傳。

如圖4，實驗記錄了在不同訓(xùn)練次數(shù)(epoch)的情況下兩種GRBM的重構(gòu)誤差(reconstruction error)變化情況，其中重構(gòu)誤差是在同一個epoch值下，各實驗5次取的平均值。從圖4可以看出，隨著epoch值的增加，兩種GRBM的重構(gòu)誤差呈現(xiàn)出先減小后震蕩增加的趨勢，這是訓(xùn)練從欠擬合到剛好擬合再到過擬合的過程。

GRBM的重構(gòu)誤差變化較劇烈，在epoch值為80的時候劇烈下降，然后epoch值為500時降到最小值0.384。相較與GRBM，GA-GRBM的曲線變化比較平緩，在epoch值為150的時候達到最小值0.365，之后隨著epoch值的增加而增加。

圖4 重構(gòu)誤差隨epoch值變化圖Fig.4 Reconstruction error versus epoch value

以上分析說明了兩點：

1)GA-GRBM和GRBM分別在epoch為150、500時，重構(gòu)誤差達到了最小值，這表示GA-GRBM相對GRBM能夠用更少的訓(xùn)練次數(shù)快速學(xué)習(xí)到數(shù)據(jù)的特征；

2)GA-GRBM具有比GRBM更小的重構(gòu)誤差，表明GA-GRBM比GRBM能夠更好地擬合原數(shù)據(jù)。

為了驗證AORM的有效性，將AORM算法與屬性距離和算法做對比實驗。實驗數(shù)據(jù)取自UCI數(shù)據(jù)庫的BTSC數(shù)據(jù)集(blood transfusion service center data set)、CMC數(shù)據(jù)集(contraceptive method choice data set)、AD數(shù)據(jù)集(audit data set)、BCW數(shù)據(jù)集(breast cancer Wisconsin data set)和WI數(shù)據(jù)集(wine data set)，屬性維度分別為4、9、13、18、30維，每個數(shù)據(jù)集都含有5%的離群數(shù)據(jù)，離群數(shù)據(jù)的每一維由均勻分布隨機生成[20]。屬性距離和算法的參數(shù)n的取值為數(shù)據(jù)集樣本個數(shù)的5%取整，AORM無需設(shè)置參數(shù)。用運行時間(T)、精確率和召回率的調(diào)和均值(F1值)作為實驗效果評價指標(biāo)，對比實驗評價指標(biāo)結(jié)果見表1。

表1 GA-GRBM對比實驗結(jié)果

從運行時間T來看：屬性距離和算法與AORM算法的運行時間相差無幾，兩者都能較快速地識別出低維數(shù)據(jù)中的離群點。從調(diào)和均值F1值來看，在對實驗數(shù)據(jù)有所了解的情況下，AORM的F1值要略高于屬性距離和方法。倘若在對數(shù)據(jù)的分布不夠了解的情況下，通過人為給定離群點個數(shù)的方式相對于AORM的自適應(yīng)識別方式會有更差的識別率。

綜上所述，屬性距離和算法與AORM的對比實驗結(jié)果證明了AORM方法是能夠有效地、自適應(yīng)地識別出低維數(shù)據(jù)中的離群點。

表2 AHORM對比實驗結(jié)果

為了驗證AHORM方法的有效性，本文選取了UCI機器學(xué)習(xí)數(shù)據(jù)集的4組數(shù)據(jù)做了對比驗證實驗。并用江西中醫(yī)藥大學(xué)現(xiàn)代中藥制劑教育部重點實驗室的兩組中藥數(shù)據(jù)驗證AHORM方法對高維中藥數(shù)據(jù)離群點識別的有效性。

來自UCI機器學(xué)習(xí)數(shù)據(jù)集的4組數(shù)據(jù)分別是：PD數(shù)據(jù)集(Parkinson’s disease)、SCADI數(shù)據(jù)集、Musk數(shù)據(jù)集、DG數(shù)據(jù)集(Dota2Games result)，其維度分別為756、206、166、116維。來自江西中醫(yī)藥大學(xué)現(xiàn)代中藥制劑教育部重點實驗室的兩組中藥數(shù)據(jù)分別是：CHD寒熱藥數(shù)據(jù)，數(shù)據(jù)特征有249個；中藥光譜數(shù)據(jù)NIR中藥數(shù)據(jù)集，屬性是波長，屬性的取值為中藥成分在該波長下的吸收率，有1 557個屬性。采用不同維度的數(shù)據(jù)集進行試驗，可更好地評估算法性能。對于每個數(shù)據(jù)集，分別將其中的70%用作訓(xùn)練集，30%用作測試集。訓(xùn)練集中混有20%的離群數(shù)據(jù)，測試集中混有5%的離群數(shù)據(jù)，離群數(shù)據(jù)的每一維由均勻分布隨機生成[20]。

對比實驗將基于PCA及屬性距離和的離群點檢測算法和PCA-SVM[21]兩個方法作為參照算法。按照通常的做法，本文將PCA的貢獻比率閾值都定義為98%，SVM中的核函數(shù)采用徑向基核函數(shù) RBF；為模擬現(xiàn)實中參數(shù)n的取值情況，將基于PCA及屬性距離和算法的參數(shù)n設(shè)置為數(shù)據(jù)樣本容量的5%～10%的隨機數(shù)取整。AHORM中的遺傳最大次數(shù)為100，種群個數(shù)為100，父代個數(shù)和子代個數(shù)均為50；權(quán)重w的初始值由正態(tài)分布(0,0.01)生成，隱藏層偏置初始值為零，可見層單元數(shù)為樣本數(shù)據(jù)維度，學(xué)習(xí)率為0.1，當(dāng)epoch超過300次停止訓(xùn)練。用P值、R值、F1值作為實驗效果的評價指標(biāo)，實驗結(jié)果見表2。圖7、圖8分別是3種算法在UCI數(shù)據(jù)上和在中藥數(shù)據(jù)上的對比實驗結(jié)果圖。

從表2和圖7、圖8可以看出：

1)在UCI數(shù)據(jù)上，AHORM的P值相較于PCA-SVM平均提高了8.3個百分點；調(diào)和均值F1值平均提高了4.6個百分點；在兩組中藥數(shù)據(jù)的對比實驗中，AHORM的F1值比PCA-SVM算法平均高了5.2個百分點。

2)相對于PCA及屬性距離和算法，從精確率P值來看，AHORM在兩種數(shù)據(jù)集上的P值都高于PCA及屬性距離和的P值，最高相差0.230，最低相差0.016。差值波動大是n的取值隨機造成的，說明了n的取值好壞對實驗結(jié)果影響很大。從調(diào)和均值F1值來看，AHORM在5組數(shù)據(jù)的F1值比PCA及屬性距離和算法平均提高了5.9個百分點。

以上分析說明，本文提出的AHORM算法可以有效地應(yīng)用于高維數(shù)據(jù)的離群點識別當(dāng)中。

圖7 UCI數(shù)據(jù)實驗結(jié)果Fig.7 UCI dataexperimental results

圖8 中藥數(shù)據(jù)實驗結(jié)果Fig.8 Traditional Chinese medicine data experimental results

4 結(jié)束語

針對傳統(tǒng)的基于距離的離群點識別方法難以直接有效地應(yīng)用于高維數(shù)據(jù)且識別效果受參數(shù)影響的問題，本文提出了一種自適應(yīng)的高維離群點識別方法(AHORM)，充分利用了經(jīng)遺傳算法優(yōu)化后的高斯受限玻爾茲曼機的強大非線性特征提取能力，以及基于距離的自適應(yīng)離群點識別方法(AORM)簡單有效的優(yōu)勢。在UCI高維數(shù)據(jù)和中藥高維數(shù)據(jù)上的對比實驗中，AHORM算法相對于兩種對比算法，各項評價指標(biāo)均有所提升，其中F1值平均提高了5.6個百分點，證明了AHORM方法具有更好的識別效果，是一種能有效地應(yīng)用于高維數(shù)據(jù)的離群點識別方法。