楊晨 王婕婷 李飛江 錢宇華

摘 要：針對目前概率機器學習方法在解決概率問題時具有較高的復雜度，而傳統(tǒng)的支持向量數(shù)據(jù)描述（SVDD）作為一種核密度估計方法只能判斷測試樣本是否屬于該類等問題，提出一種基于概率的支持向量數(shù)據(jù)描述方法。首先，利用傳統(tǒng)的SVDD方法分別得到兩類數(shù)據(jù)的數(shù)據(jù)描述，計算測試樣本到超球體的距離;然后，構造一個將距離轉(zhuǎn)換為概率的函數(shù)，提出一種基于概率的SVDD方法;同時，使用Bagging算法進行集成，進一步提高數(shù)據(jù)描述的性能。借鑒分類場景，將所提方法與傳統(tǒng)的SVDD方法在Gunnar Raetsch的13種基準數(shù)據(jù)集上進行實驗，實驗結(jié)果表明，所提方法在準確率和F1值上優(yōu)于傳統(tǒng)的SVDD方法，并且其數(shù)據(jù)描述的性能有所提升。

關鍵詞：概率機器學習;支持向量數(shù)據(jù)描述;集成;不確定性;分類

中圖分類號：TP181

文獻標志碼：A

Support vector data description method based on probability

YANG Chen1，2，3， WANG Jieting1，2，3， LI Feijiang1，2，3， QIAN Yuhua1，2，3*

1.Research Institute of Big Data Science and Industry， Shanxi University， Taiyuan Shanxi 030006， China;

2.Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education（Shanxi University）， Taiyuan Shanxi 030006， China;

3.School of Computer and Information Technology， Shanxi University， Taiyuan Shanxi 030006， China

Abstract：

In view of the high complexity of current probabilistic machine learning methods in solving probability problems， and the fact that traditional Support Vector Data Description （SVDD）， as a kernel density estimation method， can only estimate whether the test samples belong to this class， a probabilitybased SVDD method was proposed. Firstly， the traditional SVDD method was used to obtain the data descriptions of two types of data， and the distance between the test sample and the hypersphere was calculated. Then， a function was constructed to convert the distance into probability， and an SVDD method based on probability was proposed. At the same time， Bagging algorithm was used for the integration to further improve the performance of data description. By referring to classification scenarios， the proposed method was compared with the traditional SVDD method on 13 kinds of benchmark datasets of Gunnar Raetsch. The experimental results show that the proposed method is better than the traditional SVDD method on accuracy and F1value， and its performance of data description is improved.

Key words：

probabilistic machine learning; Support Vector Data Description （SVDD）; ensemble; uncertainty; classification

0?引言

機器學習主要是計算機通過已知數(shù)據(jù)訓練模型，運用模型對未知數(shù)據(jù)進行預測。機器學習面臨的未來的數(shù)據(jù)和將來的行為引發(fā)的結(jié)果是不確定的， 而概率機器學習[1]針對這種不確定性提供了一個概率框架，對模型和預測的不確定性進行表示和控制，因此在很多領域發(fā)揮著重要的作用，比如語音識別[2]、圖像分類[3-4]、文本預測[5]等。Ghahramani[1]在2015年指出概率機器學習框架的主要思想是，學習可以被認為是通過推斷合理的模型來解釋預測數(shù)據(jù)，然后機器使用模型來預測未來的數(shù)據(jù)，并且根據(jù)這些預測作出合理的決策，不確定性在這一切中起著至關重要的作用，對于給定的數(shù)據(jù)而言，哪個模型是合適的尚不確定;同樣，對未來數(shù)據(jù)和未來行動結(jié)果的預測也是不確定的，因此使用概率論描述這種不確定性，概率論為不確定性建模提供了一個框架[1]。相對于二值輸出而言，以概率作為輸出的結(jié)果能夠提供更多的信息，預測結(jié)果更加準確。

目前已有的概率機器學習方法主要有貝葉斯學習、高斯過程和深度學習等，其中：神經(jīng)網(wǎng)絡是具有許多參數(shù)的可調(diào)非線性函數(shù)，深度學習的概念源于人工神經(jīng)網(wǎng)絡的研究，但是也有一些重要的改變，比如新的架構和算法創(chuàng)新、有更大的數(shù)據(jù)集、大規(guī)模的計算資源等。神經(jīng)網(wǎng)絡和深度學習系統(tǒng)在許多基本測試任務上都有很高的性能，但是也有一些局限性，比如需要大量的數(shù)據(jù)、需要大量的計算資源進行訓練等，因此這些方法在解決概率問題時具有較高的復雜度。

近年來，數(shù)據(jù)描述問題得到了大量的研究。在域描述領域中，數(shù)據(jù)描述的任務不是以“區(qū)分不同的類”為目標的分類問題，也不是以“對每一個樣本產(chǎn)生一個期望輸出”為目標的回歸問題，而是給出一個關于訓練樣本集的描述，同時檢測那些與訓練樣本集相似的新樣本。該描述應該覆蓋訓練樣本集的所有樣本，同時，在理想情況下，該描述應該能夠?qū)颖究臻g中其他所有可能的異常樣本排除在外。

20世紀末，Tax等[6]在支持向量機（Support Vector Machine， SVM）的基礎上提出了一種數(shù)據(jù)描述方法，即支持向量數(shù)據(jù)描述（Support Vector Data Description， SVDD）。SVDD方法是一種基于邊界數(shù)據(jù)（即支持向量）的描述方法，其思想是尋找一個幾乎包含所有目標樣本并且體積最小的超球體。SVDD方法相對于貝葉斯學習、高斯過程和深度學習等具有算法復雜性低、擴展性強、對數(shù)據(jù)規(guī)模需求低等優(yōu)點。Lee等[7]提出了一種改進的局部密度支持向量數(shù)據(jù)描述方法（Densityinduced Support Vector Data Description， DSVDD），結(jié)果表明，DSVDD的性能優(yōu)于SVDD和k近鄰數(shù)據(jù)描述方法。Kim等[8]針對SVDD在處理大數(shù)據(jù)集時存在一定的局限性提出了一種基于k均值聚類的快速SVDD算法，該方法與原始SVDD方法有相同的結(jié)果，并且降低了計算成本。Luo等[9]針對矩陣操作的空間復雜性，提出了一種基于分解和組合策略的快速SVDD算法，該算法在實現(xiàn)樣本描述方面優(yōu)于原SVDD算法，尤其是在大規(guī)模樣本數(shù)據(jù)集上。然而在現(xiàn)實生活中，目標數(shù)據(jù)集往往包含一類以上的對象，每一類對象都需要同時進行描述和區(qū)分，在這種情況下，傳統(tǒng)的SVDD只能給出一個描述目標數(shù)據(jù)集，不區(qū)分不同的目標類數(shù)據(jù)集，或者給目標數(shù)據(jù)集中每個類的對象一個描述，Huang等[10]提出了一種改進的支持向量數(shù)據(jù)描述方法——兩類支持向量數(shù)據(jù)描述（TwoClass Support Vector Data Description， TCSVDD）。

傳統(tǒng)的SVDD方法作為一種核密度估計方法，對未知數(shù)據(jù)進行預測主要是先對已知樣本進行數(shù)據(jù)描述，然后判斷測試樣本是否屬于該類，是二值輸出;相對于二值輸出而言，以概率作為輸出的結(jié)果能夠提供更多的信息，獲得更準確的數(shù)據(jù)描述。而傳統(tǒng)的SVDD方法判斷測試樣本是否屬于該類，主要是計算測試數(shù)據(jù)到超球體中心的距離，但是該距離無法得知測試數(shù)據(jù)所屬類別的概率。因此，本文提出了一個將距離轉(zhuǎn)換為概率的函數(shù)，在本文第2章詳細解釋。

集成學習算法[11]是通過集成多個學習器共同決策的機器學習技術，通過不同的樣本集訓練有差異的個體學習器，然后使用某種規(guī)則把個體學習器的結(jié)果進行集成，得到的集成分類器可以有效提高單個分類器的學習效果。根據(jù)個體學習器的生成方式，目前的集成學習方法大致分為兩大類，即個體學習器間存在強依賴關系、必須串行生成的序列化方法，以及個體學習器間不存在強依賴關系、可同時生成的并行化方法。前者的代表是Boosting[12]，后者的代表是Bagging[13]和隨機森林（Random Forest）[14-15]。借鑒分類場景，本文主要使用Bagging集成算法來提高傳統(tǒng)SVDD方法的數(shù)據(jù)描述能力。

為了解決目前深度學習等概率機器學習在解決概率問題時具有較高的復雜度，而且傳統(tǒng)的SVDD方法只能判斷測試樣本是否屬于該類等問題，本文首先介紹了SVDD方法和Bagging集成算法的相關知識;然后構造了一個將距離轉(zhuǎn)換為概率的函數(shù)，提出了一種基于概率的支持向量數(shù)據(jù)描述方法（SVDD method based on Probability， PSVDD）;最后，實驗驗證了PSVDD方法的有效性。

1?相關工作

本文算法是基于概率的支持向量數(shù)據(jù)描述方法，因此在本章簡要回顧了SVDD方法和Bagging集成算法的相關知識。

1.1?SVDD相關理論

支持向量數(shù)據(jù)描述（SVDD）是一種對目標數(shù)據(jù)集進行球形描述并用于離群點檢測或分類的數(shù)據(jù)描述方法。它的基本思想是通過利用核函數(shù)將樣本從低維空間映射到高維特征空間，并尋求一個超球體，盡可能在使超球體的半徑小的情況下把所有訓練樣本包圍起來，并以最小超球體的邊界對數(shù)據(jù)進行描述和分類。在測試階段，判斷測試樣本與所構造的超球體的球心之間的距離是否小于半徑：如果小于超球體半徑則認為是目標點;若大于超球體的半徑則被認為是異常點。SVDD示意圖如圖1所示。

設X={xi，i=1，2，…，n}為Rd空間中的訓練數(shù)據(jù)集，a和R分別表示球面的中心和半徑。該目標被表述為一個二次規(guī)劃問題：

minR，a，ξi（R，a，ξi）=R2+C∑iξi（1）

s.t.‖xi-a‖2≤R2+ξi， ξi≥0， i=1，2，…，n

其中ξi是一個松弛變量，允許訓練數(shù)據(jù)集中出現(xiàn)異常值的可能性; C為誤差懲罰系數(shù)，用來平衡錯分誤差和球體體積。為了該二次規(guī)劃問題進行求解，引入拉格朗日乘子αi，γi構造拉格朗日函數(shù)：

L（R，a，ξi，αi，γi）=R2+C∑iξi-

∑iαi[R2+ξi-（xi-a）2]-∑iγiξi（2）

其中拉格朗日乘子αi≥0，γi≥0。將R，a，ξi偏導數(shù)設為零得到約束條件：

[2]HINTON G， DENG L， YU D， et al. Deep neural networks for acoustic modeling in speech recognition： the shared views of four research groups[J]. IEEE Signal Processing Magazine， 2012， 29（6）： 82-97.

[3]KRIZHEVSKY A， SUTSKEVER I， HINTON G E， et al. ImageNet classification with deep convolutional neural networks[J]. Communications of the ACM， 2017， 60（6）： 84-90.

[4]黃凱奇， 任偉強， 譚鐵牛. 圖像物體分類與檢測算法綜述[J]. 計算機學報， 2014， 36（6）：1-18.（HUANG K Q， REN W Q， TAN T N. A review on image object classification and detection[J]. Chinese Journal of Computers， 2014， 36（6）： 1-18.）

[5]KANDOLA E J， HOFMANN T， POGGIO T， et al. A neural probabilistic language model[J]. Journal of Machine Learning Research， 2006， 194： 137-186.

[6]TAX D M J， DUIN R P W. Support vector data description[J]. Machine Learning， 2004， 54（1）： 45-66.

[7]LEE K Y， KIM D W， LEE D， et al. Improving support vector data description using local density degree[J]. Pattern Recognition， 2005， 38（10）：1768-1771.

[8]KIM P J， CHANG H J， SONG D S， et al. Fast support vector data description usingkmeans clustering[C]// Proceedings of the 4th International Symposium on Neural Networks. Berlin： Springer， 2007： 506-514.

[9]LUO J， LI B， WU C， et al. A fast SVDD algorithm based on decomposition and combination for fault detection[C]// Proceedings of the 2010 International Conference on Control and Automation. Piscataway： IEEE， 2010： 1924-1928.

[10]HUANG G， CHEN H， ZHOU Z， et al. Twoclass support vector data description[J]. Pattern Recognition， 2011， 44（2）： 320-329.

[11]李勇， 劉戰(zhàn)東， 張海軍. 不平衡數(shù)據(jù)的集成分類算法綜述[J]. 計算機應用研究， 2014， 31（5）： 1287-1291.（LI Y， LIU Z D， ZHANG H J. Summary of integrated classification algorithm for unbalanced data[J]. Application Research of Computers， 2014， 31（5）： 1287-1291.）

[12]FREUND Y， SCHAPIRE R E. A decisiontheoretic generalization of online learning and an application to boosting[J]. Journal of Computer and System Sciences， 1997， 55（1）： 119-139.

[13]BREIMAN L. Bagging predictors[J]. Machine Learning， 1996， 24（2）： 123-140.

[14]BREIMAN L. Random forests[J]. Machine Learning， 2001， 45（1）： 5-32.

[15]周志華. 機器學習[M]. 北京：清華大學出版社， 2016： 171-189.（ZHOU Z H. Mechine Learning[M]. Beijing： Tsinghua University Press， 2016： 171-189.）

[16]QIAN Y， LI F， LIANG J， et al. Space structure and clustering of categorical data[J]. IEEE Transactions on Neural Networks & Learning Systems， 2016， 27（10）：2047-2059.

[17]ZHOU Z. Ensemble Methods： Foundations and Algorithms[M]. Boca Raton， FL： Taylor & Francis Group， 2012： 1-22.

[18]QIAN Y， LI F， LIANG J， et al. Fusing monotonic decision trees[J]. IEEE Transactions on Knowledge and Data Engineering， 2015， 27（10）： 2717-2728.

[19]EFRON B. Bootstrap methods： another look at the jackknife[J]. Breakthroughs in Statistics， 1979， 7（1）： 569-593.

[20]CAWLEY G， TALBOT N. Gunnar Raetschs benchmark datasets [DB/OL].[2018-11-20]. http：//theoval.cmp.uea.ac.uk/～gcc/matlab/default.html#benchmarks.

[21]NAGANJANEYULU S， KUPPA M R. A novel framework for class imbalance learning using intelligent undersampling[J]. Progress in Artificial Intelligence， 2013， 2（1）： 73-84.

[22]ZHANG X， SONG Q， WANG G， et al. A dissimilaritybased imbalance data classification algorithm[J]. Applied Intelligence， 2015， 42（3）： 544-565.

[23]JIANG K， LU J， XIA K. A novel algorithm for imbalance data classification based on genetic algorithm improved SMOTE[J]. Arabian Journal for Science and Engineering， 2016， 41（8）： 3255-3266.

This work is partially supported by the National Natural Science Foundation of China （61672332）， the Program for the Outstanding Innovative Teams of Higher Learning Institutions of Shanxi， the Program for the San Jin Young Scholars of Shanxi， the Overseas Returnee Research Program of Shanxi Province （2017023）.

YANG Chen， born in 1996， M. S. candidate. Her research interests include statistical machine learning theory.

WANG Jieting， born in 1991， Ph. D. candidate. Her research interests include statistical machine learning theory， reinforcement learning.

LI Feijiang， born in 1990， Ph. D. candidate. His research interests include group learning， unsupervised learning.

QIAN Yuhua， born in 1976， Ph. D.， professor. His research interests include machine learning， complex network， rough set theory， granular computing.