基于深度信念網絡和線性單分類SVM的高維異常檢測

李昊奇，應娜，郭春生，王金華

?

基于深度信念網絡和線性單分類SVM的高維異常檢測

李昊奇，應娜，郭春生，王金華

（杭州電子科技大學，浙江 杭州 310018）

針對目前高維數據異常檢測存在的困難，提出一種基于深度信念網絡和線性單分類支持向量機的高維異常檢測算法。該算法首先利用深度信念網絡具有良好的特征提取功能，實現高維數據的降維，然后基于線性核函數的單分類支持向量機實現異常檢測。選取UCI機器學習庫中的高維數據集進行實驗，結果表明，該算法在檢測正確率和計算復雜度上均有明顯優勢。與PCA-SVDD算法相比，檢測正確率有4.65%的提升。與自動編碼器算法相比，其訓練和測試時間均有顯著下降。

異常檢測；高維數據；深度信念網絡；單分類支持向量機

1 引言

異常檢測是數據挖掘中的重要組成部分。異常數據是指在數據集中偏離大部分數據或者與數據集中其他大部分數據不服從相同統計模型的小部分數據[1]。而異常檢測就是要識別出異常數據從而消除不符合預期行為的模式問題。異常檢測在信用卡欺詐、網絡入侵、健康醫療監控等諸多生活領域中均有重要應用[2]。

在異常檢測中，單分類支持向量機（one-class support vector machine，OCSVM）是常用的有效手段[3]。OCSVM是對二分類支持向量機的一種細化，是在異常檢測領域中的重要經典算法。當確定合適的參數配置時，OCSVM對于異常數據的檢測可以提供良好的泛化能力。在OCSVM中，有兩種經典算法用于異常檢測，分別為基于超平面支持向量機（plane based support vector machine，PSVM）和基于超球面的支持向量描述（support vector data description，SVDD）法。相比較而言，利用超球面分類的SVDD算法性能優于基于PSVM算法。因此，通常采用SVDD算法進行異常檢測。

然而，隨著互聯網的快速發展和物聯網的逐漸普及，數據的收集更加容易。這導致數據庫的規模和數據的復雜性急劇增加，從而產生大量的高維數據。如證券交易數據、Web用戶數據、網絡多媒體數據等。維度的迅速增長，使得傳統的OCSVM方法對高維數據的異常檢測效率逐漸下降，從而導致高維數據的異常檢測成為數據挖掘的難點[4]。

高維數據存在的普遍性使得對高維數據挖掘的研究有著非常重要的意義。但“維度災難”問題導致對高維數據挖掘變得異常困難。即在分析高維數據時，所需的空間樣本數會隨維數的增加而呈指數倍增長。對于高維數據的處理，傳統的多元統計分析方法存在很多的局限性，同時高維數據空間中的稀疏性使得采用非參數方法的大樣本理論也并不適用。因此，采用數據降維是處理高維數據的最主要的高效手段。

在機器學習領域中，所謂降維就是指采用某種映射方法，將原高維空間中的點映射到新的低維空間中[5]。經典的數據降維方法如主成分分析[6]（principle component analysis，PCA）法、局部線性嵌入[7]（locally linear embedding，LLE）法和典型相關分析[8]（canonical correlation analysis，CCA）法等在特征提取和數據降維方面有著廣泛的應用。但這些降維方法均屬于線性降維，只能提取數據間的線性關系，從而導致在處理高維數據時存在著統計特性的漸進性難以實現、算法頑健性低等問題。盡管對PCA和CCA基于核函數改進后的核主成分分析（kernel principle component analysis，KPCA）法和核典型相關分析[9]（kernel canonical correlation analysis，KCCA）法可以解決非線性降維的問題，但算法的復雜度較高、效率較低。

對于解決高維的異常檢測問題，近幾年有多種經典的方法被提出。參考文獻[10]直接提出了OCSVM中的經典算法，即基于超球面的支持向量數據描述法。該算法雖然對當時的高維數據異常檢測起了很大的推動作用，但算法的正確率偏低。參考文獻[11]將PCA算法和OCSVM相結合，將數據利用經典的線性降維方法PCA進行降維，在OCSVM中采用非線性核函數進行異常檢測。由于線性降維的局限性，其結果并沒有很大的提升。參考文獻[12]利用改進后的KPCA算法和OCSVM進行異常檢測。檢測結果雖有所提升，但由于非線性核函數計算量大，對數據進行訓練和測試所需要的時間較長，導致該算法的效率不高。參考文獻[13]利用自動編碼器（autoencoder，AE），通過對比不同數據間的重構誤差進行異常檢測。其識別率雖有所提升，但測試效率依然不高。

本文提出利用深度信念網絡（deep belief network，DBN）進行數據降維，再利用基于線性核函數的單分類支持向量機這種組合模型實現異常檢測。深度信念網絡本質上是一種概率生成模型，通過無監督的訓練方法由底層至頂層逐層訓練而成。與其他傳統的線性降維方法相比，深度信念網絡最大的特點就是利用其自身非線性的結構進行特征提取，將數據從高維空間映射至低維空間，從而降低數據的維度。這種非線性降維方法可以在最大程度上保留原始數據的高維特征，并且算法的復雜度較低，相比于其他算法可以更有效地解決高維數據的異常檢測問題。實驗結果表明，本文提出的混合算法模型，即將深度信念網絡和線性單分類支持向量機組合在一起解決高維數據的異常檢測問題，在檢測正確率和測試效率上都有很大提升。

2 算法設計

本文所提出的算法（DBN-OCSVM）模型如圖1所示，該模型由兩部分組成，即底層的DBN和頂層的OCSVM。DBN由2個限制玻爾茲曼機（restricted Boltzmann machine，RBM）堆疊而成。將原始數據首先輸入DBN的輸入層，經RBM1訓練后，輸入層數據被映射至隱藏層1。隱藏層1的輸出作為RBM2的輸入繼續訓練后得到隱藏層2。隱藏層2的數據即DBN的輸出，并將其輸入OCSVM中進行異常檢測。

圖1 DBN-OCSVM結構

圖2 OCSVM-SVDD算法示意

在OCSVM中，使用SVDD算法進行異常檢測。SVDD為無監督訓練算法，與有監督的二分類SVM相比，它并不是要尋找能夠區分數據的最優超平面，而是尋找能夠包含大多數正常數據的最優超球面。如圖2所示，當輸入空間的數據不可分時，構造一個映射函數，將輸入空間中的數據映射到特征空間中。在特征空間中，尋找支持向量構造一個將絕大多數點包圍在其中并具有最小半徑的最優超球面。由支持向量確定的超球面即正常數據類的描述模型，超球面外的點被判斷為離群類數據點，即異常數據。

在SVDD的核函數選取中，選擇線性函數代替傳統方法中的徑向基函數（radical basis function，RBF）。在SVM中，核函數的選擇對算法的性能起著重要的作用，利用核函數可以將線性不可分的輸入空間映射到更高維的特征空間，從而將正常數據和異常數據進行完全分離。通常，相比較線性核函數而言，RBF等非線性核函數可以將數據映射到更適于線性分類的特征空間，從而提高SVM的分類性能。但利用本文提出的模型，經DBN進行降維以及特征提取后的數據通過線性核函數依然可以進行優秀的分類，從而規避了線性核函數的缺點，反而突出了其優點。即降低了算法的時間復雜度和空間復雜度，提高了系統的運行速率。

3 算法原理

3.1 基于深度信念網絡的高度降維

DBN的實質是由一個高斯—伯努利型RBM作為底層，上層接有多個伯努利—伯努利型RBM，這樣將多個RBM堆疊起來便得到了所需要的生成模型DBN。將第一個RBM訓練后得到的輸出作為下一個RBM的輸入繼續訓練，如此往復，經過訓練后的各個RBM參數就是DBN的初始化參數。

其等價于：

根據該能量配置函數，設定可見層和隱藏層的聯合概率密度為：

在RBM中負對數似然度對于任意一個模型參數的導數為：

3.2 基于單分類支持向量機的異常檢測

則上述問題便可以轉化為：

4 實驗與分析

實驗中將DBN-SVDD算法與SVDD算法、PCA-SVDD算法和AE算法進行比較，從檢測正確率和訓練以及測試時間方面對比3種算法的性能。本實驗采用的數據集來自UCI機器學習庫，數據均采集于真實的生活。共選取4個高維數據集進行訓練和測試，其分別為：森林覆蓋集（forest covertype，FC）、基于傳感器檢測的氣體種類集（gas senor array drift，GAS）、日常活動集（daily and sport activity，DSA）和基于智能設備穿戴的人類活動集（human activity recognition using smartphone，HAR）。其維數分別為：54、128、315和561維。采用不同維度的數據集進行測試，從而更好地評估本文算法性能。

表1 3種算法在RBF核函數下的異常檢測正確率

表2 3種算法在線性核函數下的異常檢測正確率

在以下實驗中，用DBN后所加的數字表示DBN的層數。例如：DBN1和DBN3分別表示為具有1層和3層隱藏層的深度信念網絡。在實驗一和實驗二中，默認的DBN為具有2層隱藏層的深度信念網絡。對于DBN的每個隱藏層神經元個數，根據參考文獻[18]的方法在最優性能下確定。

（1）實驗一

將DBN-SVDD算法與SVDD、PCA-SVDD 兩種經典算法分別在線性（linear）核函數和徑向基函數（radical basis function，RBF）下進行實驗對比。通過對以上4個數據集進行異常檢測，其識別率見表1、表2（識別率保留百分號前小數點后兩位），并將表1、表2的數據繪制成圖3、圖4的折線。

圖3 RBF函數下3種算法對4個數據集的異常檢測正確率

圖4 DBN-SVDD算法下兩種核函數的異常檢測正確率對比

通過觀察表1、表2中的數據以及圖3、圖4，可以得出以下結論。

? ? 對于PCA方法降維，當使用線性核函數時，對于低維數據集如FC、GAS，異常檢測的正確率有一定提升；當數據維度較高時，如DSA、HAR，利用PCA降維相比于SVDD算法其測試結果幾乎沒有提升。

? ?對于SVDD和PCA-SVDD這兩種算法，無論使用線性核函數或者徑向基函數，隨著數據維度的增加，其異常檢測的正確率逐漸下降。而使用DBN-SVDD算法其異常檢測結果基本不受數據維度的影響，在各種維度的數據中，其檢測結果都要優于另外兩種算法。

? ?對于DBN-SVDD算法，當使用線性核函數和徑向基函數時，對實驗結果基本不產生影響。這說明利用DBN更好地提取了高維數據中的特征，即使用線性核函數也有很好的檢測結果。

（2）實驗二

將AE算法與DBN-SVDD算法分別在檢測正確率和檢測效率上進行比較。對于DBN-SVDD混合模型，訓練和測試的時間包括數據降維部分和降維后異常檢測兩部分的總和，訓練和測試的時間為SVDD平均迭代1 000次的時間值。

首先將DBN-SVDD分別在線性和RBF兩種核函數下的異常檢測率與AE算法進行比較，實驗結果見表3。

由表3可以看出，AE算法的平均異常檢測正確率為97.24%，與DBN-SVDD算法在RBF核下的97.63%以及線性核下的97.65%幾乎沒有差別。說明AE算法通過對比數據間的重構誤差，在異常檢測正確率上也可以達到很好的效果。再將兩種算法的訓練和測試時間進行對比，實驗結果分別見表4和表5。

表3 DBN-SVDD與AE算法的異常檢測正確率對比

表4 DBN-SVDD與AE算法的訓練時間對比（單位：s）

由表4可以看出，DBN-SVDD算法下兩種核函數分別進行訓練的時間基本一致，這也進一步表明DBN對高維數據進行特征提取的優良特性。對于AE算法，其訓練時間平均為0.772 1 s，分別為線性核DBN-SVDD的5.5倍和RBF核的4.4倍，進一步說明了DBN-SVDD算法的高效性。

由表5可以看出，AE算法的測試時間平均時間為3.993 0 ms，均大于線性核DBN-SVDD和RBF核SVDD算法。與AE算法相比，線性核函數的測試平均時間為0.281 3 ms，時間縮短了近13.2倍；RBF核函數的測試平均時間為0.473 1 ms，時間縮短了近7.4倍。對于DBN-SVDD算法，其采用線性核函數所測試的時間小于采用RBF核函數進行測試的時間。這是由于RBF核函數具有更高的計算復雜度，因此需要花費更多的時間。由于采用線性核函數和RBF核函數，異常檢測正確率幾乎一致，而采用線性核函數進行測試的平均時間為0.281 3 ms，相比于采用核函數的0.473 1 ms，時間降低了40.54%。因此，采用線性核函數在很大程度上縮短了進行數據測試的時間，提高異常檢測效率。

表5 DBN-SVDD與AE算法的測試時間對比（單位：ms）

表6 線性核函數下不同DBN隱藏層數對實驗結果的影響

（3）實驗三

在確定DBN-SVDD混合模型為最優算法的前提下，探究DBN隱藏層的層數對實驗結果的影響。由于過多的層數會增加模型的復雜性和算法計算量，因此只討論最多3層隱藏層對實驗結果的影響。在實驗1中，進行了具有2層隱藏層的DBN測試。接下再分別對DBN1和DBN3在線性核函數下進行實驗測試，實驗結果見表6。

將表5中的實驗結果繪制成圖5后可以看出，具有1層隱藏層的DBN1屬于“淺層模型”，導致其最終實驗測試結果除了在GAS數據集為97.02%，略高于其他兩種算法外，在其余數據集的測試結果均低于另外兩種“深層模型”。對于DBN3，其實驗結果與DBN2相比除了在FC數據集上有較大波動外（檢測率降低了0.90%），在其他數據集上的檢測結果相差甚微，只在0.18%~0.35%范圍波動，基本相同。而對于DBN3而言，其網絡模型的復雜度以及計算量均高于DBN2。因此，確定具有2層隱藏層的DBN2為最佳網絡模型。

5 結束語

本文通過將深度信念網絡和單分類支持向量機組合到一起，提出DBN-SVDD算法模型。通過數據降維的方式，該算法很好地解決了高維數據的異常檢測問題。利用DBN的非線性特性以及逐層遞進的特征提取方式來獲得高維數據中的低維特征，良好地解決了“維數災難”問題。通過實驗，確定了DBN2為最佳的降維網絡模型。采用線性核的DBN-SVDD算法在測試時間上相比RBF核可以降低34.9%。對比PCA-SVDD算法，其檢測正確率最高提升了4.65%；對比AE算法，其測試時間縮短到1/13。

圖5 不同DBN隱藏層數下的異常檢測正確率

[1] 王忠偉, 陳葉芳, 肖四友, 等. 一種高維大數據全近鄰查詢算法[J]. 電信科學, 2015, 31(7): 52-62.

WANG Z W, CHEN Y F, XIAO S Y, et al. An AkNN algorithm for high-dimensional big data[J]. Telecommunications Science, 2015, 31(7): 52-62.

[2] CHANDOLA V, BANERJEE A, KUMAR V. Anomaly detection:A survey[J]. ACM Computing Surveys, 2009, 41(3): 1-58.

[3] SHIN H J, EOM D H, KIM S S. One-class support vector machines—an application in machine fault detection and classification[J]. Computers & Industrial Engineering, 2005, 48(2): 395-408.

[4] 李昕, 錢旭, 王自強. 一種高效的高維異常數據挖掘算法[J]. 計算機工程, 2010, 36(21): 34-36.

LI X, QIAN X, WANG Z Q. Efficient data mining algorithm for high-dimensional outlier data[J]. Computer Engineering, 2010, 36(21): 34-36.

[5] TENENBAUM J B, DE S V, LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500): 2319.

[6] POMERANTSEV A L. Principal component analysis(PCA)[M]. New York: John Wiley & Sons, Inc., 2014: 4229-4233.

[7] ROWEIS S T, SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5500): 2323.

[8] GONZALEZ I, DéJEAN S, MARTIN P G P, et al. CCA: an R package to extend canonical correlation analysis[J]. Journal of Statistical Software, 2008, 23(12).

[9] CHENOURI S, LIANG J, SMALL C G. Robust dimension reduction[J]. Wiley Interdisciplinary Reviews Computational Statistics, 2015, 7(1): 63-69.

[10] 程輝, 方景龍, 王大全, 等. 超平面支持向量機簡化性能分析[J]. 電信科學, 2015, 31(8): 78-83.

CHENG H, FANG J L, WANG D Q, et al. Performance analysis of simplification of hyperplane support vector machine[J]. Telecommunications Science, 2015, 31(8): 78-83.

[11] GEORGE A. Anomaly detection based on machine learning dimensionality reduction using PCA and classification using SVM[J]. International Journal of Computer Applications, 2012, 47(21): 5-8.

[12] BAO S, ZHANG L, YANG G. Trajectory outlier detection method based on kernel principal component analysis[J]. Journal of Computer Applications, 2014, 34(7): 2107-2110.

[13] SAKURADA M, YAIRI T. Anomaly detection using autoencoders with nonlinear dimensionality reduction[C]//Mlsda Workshop on Machine Learning for Sensory Data Analysis, December 2, 2014, Gold Coast, Australia QLD, Australia. New York: ACM Press, 2014: 4-11.

[14] HINTON G E. Training products of experts by minimizing contrastive divergence[J]. Neural Computation, 2002, 14(8): 1771-1800.

[15] SUBRAMANIAM S, PALPANAS T, PAPADOPOULOS D, et al. Online outlier detection in sensor data using non-parametric models[C]//International Conference on Very Large Data Bases, September 12-15, 2006, Seoul, Korea. New York: ACM Press, 2006: 187-198.

[16] MOORE B. Principal component analysis in linear systems: controllability, observability, and model reduction[J]. IEEE Transactions on Automatic Control, 2003, 26(1): 17-32.

[17] HU C, HOU X, LU Y. Improving the architecture of an autoencoder for dimension reduction[C]//Ubiquitous Intelligence and omputing, 2014 IEEE, Intl Conf on and IEEE, Intl Conf on and Autonomic and Trusted Computing, and IEEE, Intl Conf on Scalable Computing and Communications and ITS Associated Workshops, Dec 9-12, 2014, Bali, Indonesia. Piscataway: IEEE Press, 2014: 855-858.

[18] HINTON G E. A practical guide to training restricted Boltzmann machines[M]. Berlin: Springer Berlin Heidelberg, 2012: 599-619.

[19] YANG J, DENG T, SUI R. An adaptive weighted one-class svm for robust outlier detection[M]. Berlin: Springer Berlin Heidelberg, 2016.

[20] LIN C J. A practical guide to support vector classification[EB/OL]. (2003-01-31)[2017-06-21]. http://www.researchgate.net/publication/ 200085999_A_Practical_Guide_to_Support_Vector_Classication.

High-dimensional outlier detection based on deepbelief network and linear one-class SVM

LI Haoqi, YING Na, GUO Chunsheng, WANG Jinhua

Hangzhou Dianzi University, Hangzhou 310018, China

Aiming at the difficulties in high-dimensional outlier detection at present, an algorithm of high-dimensional outlier detection based on deep belief network and linear one-class SVM was proposed. The algorithm firstly used the deep belief network which had a good performance in the feature extraction to realize the dimensionality reduction of high-dimensional data, and then the outlier detection was achieved based on a one-class SVM with the linear kernel function. High-dimensional data sets in UCI machine learning repository were selected to experiment, result shows that the algorithm has obvious advantages in detection accuracy and computational complexity. Compared with the PCA-SVDD algorithm, the detection accuracy is improved by 4.65%. Compared with the automatic encoder algorithm, its training time and testing time decrease significantly.

outlier detection, high-dimensional data, deep belief network, one-class SVM

TP183

A

10.11959/j.issn.1000?0801.2018006

2017?06?21；

2017?09?26

國家自然科學基金資助項目（No.61372157）；“電子科學與技術”浙江省一流學科A類基金資助項目（No.GK178800207001）

The National Natural Science Foundation of China(No.61372157), Zhejiang Provincial First Class Disciplines: Class A-Electronic Science and Technology (No.GK178800207001)

李昊奇（1992?），男，杭州電子科技大學碩士生，主要研究方向為深度學習與數據挖掘。

應娜（1978?），女，博士，杭州電子科技大學副教授、碩士生導師，主要研究方向為信號處理與人工智能。

郭春生（1971?），男，博士，杭州電子科技大學副教授、碩士生導師，主要研究方向為模式識別與人工智能。

王金華（1992?），女，杭州電子科技大學碩士生，主要研究方向為深度學習與自然語言處理。