張安安，鄭 萍，方 琳，彭嵩松

(1.江西省科學(xué)院能源研究所，330029，南昌；2.南昌師范學(xué)院，330032，南昌；2.江西警察學(xué)院刑事科學(xué)技術(shù)系，330100，南昌；4.井岡山大學(xué)電子與信息工程學(xué)院，343009，江西，吉安)

一種基于鄰域樣本密度的SVDD樣本剪輯方法及其應(yīng)用

張安安1，鄭 萍2，方 琳3，彭嵩松4

(1.江西省科學(xué)院能源研究所，330029，南昌；2.南昌師范學(xué)院，330032，南昌；2.江西警察學(xué)院刑事科學(xué)技術(shù)系，330100，南昌；4.井岡山大學(xué)電子與信息工程學(xué)院，343009，江西，吉安)

通常對于大數(shù)據(jù)的學(xué)習(xí)問題，需要選擇一個訓(xùn)練集的子集來進行學(xué)習(xí)，以降低問題本身的時間和空間復(fù)雜性。有很多學(xué)者從樣本的近鄰出發(fā)來選擇樣本，根據(jù)樣本的近鄰特點尋找位于靠近分類面的樣本。對于SVDD(Support Vector Data Description)算法而言，只有位于數(shù)據(jù)集邊緣區(qū)域的樣本對學(xué)習(xí)結(jié)果有影響。提出了通過估計樣本領(lǐng)域樣本概率的方式來判斷樣本在數(shù)據(jù)集里的位置，位于數(shù)據(jù)集邊緣區(qū)域的樣本概率要明顯小于位于數(shù)據(jù)集內(nèi)部樣本的概率，通過刪除位于數(shù)據(jù)集內(nèi)部的樣本可以大大降低數(shù)據(jù)集的規(guī)模，在不降低算法的性能時，降低訓(xùn)練模型的復(fù)雜度，提高識別速度和算法的學(xué)習(xí)速度。并在實時性要求比較高的電能擾動信號識別方面，得到了很好的應(yīng)用。

訓(xùn)練集；樣本；SVDD；樣本剪輯；電能質(zhì)量擾動信號識別

0 引言

與SVM(Support Vector Machine)類似，一分類SVDD(Support Vector Data Description)[1-2]根據(jù)結(jié)構(gòu)化風(fēng)險最小化原理，通過求一個包含盡可能少的奇異點數(shù)據(jù)，并且體積盡可能小的球體來描述樣本數(shù)據(jù)，即求滿足下式的R和a：

s.t.:‖xi-a‖≤R2+ξi,ξi≥0

(1)

將式(1)化為Wolf對偶形式：

s.t.:0≤αi≤C

(2)

對于測試數(shù)據(jù)z是否為奇異點根據(jù)式(3)判斷：

αj(xi,xj)≤R2

(3)

球半徑可以根據(jù)式(4)求出，其中xk∈SV

αk

(4)

求式(2)就是解一個二次規(guī)劃問題，因此SVDD也存在與求解SVM(Support Vector Machine)[3-4]問題相同的時間和內(nèi)存問題。SVDD求出的數(shù)據(jù)描述只與支持向量有關(guān)，而與數(shù)據(jù)分布內(nèi)部的樣本沒有關(guān)系。支持向量是靠近數(shù)據(jù)分布邊緣的少量樣本，而與占數(shù)據(jù)集大部分位于數(shù)據(jù)分布內(nèi)部的樣本無關(guān)。因此如果可以去除位于數(shù)據(jù)分布內(nèi)部的樣本就可以大大減少訓(xùn)練數(shù)據(jù)集的大小，而性能不會受太大影響。

圖1 ‘+’表示目標(biāo)數(shù)據(jù)，實線表示數(shù)據(jù)描述，實線外的是奇異數(shù)據(jù)(outlier)

對于已有的樣本剪輯方法[5-9]大多數(shù)都是針對二分類和多分類問題。本文通過樣本鄰域的概率密度判斷樣本在數(shù)據(jù)集里的位置。通常，數(shù)據(jù)集內(nèi)部樣本位于高密度區(qū)域，而數(shù)據(jù)集邊緣樣本位于低密度區(qū)域。在數(shù)據(jù)集內(nèi)部的樣本可以通過估計鄰域樣本密度在SVDD算法訓(xùn)練前去除，而不影響算法的性能。

1 基于鄰域樣本密度的樣本剪輯算法

圖2為Iris數(shù)據(jù)集不同位置的樣本密度情況。Iris數(shù)據(jù)總共有3類、4維。為了作圖方便，圖2只選取了樣本中的2維?！?’表示Versicolour類的樣本，‘*’表示Setosa或Virginica類中的樣本?！蟆硎尽?’的近鄰，‘o’表示‘*’的非近鄰。第1行是位于數(shù)據(jù)集邊緣；第2行是位于數(shù)據(jù)集內(nèi)部。顯然，位于數(shù)據(jù)集內(nèi)部的樣本密度要大于位于數(shù)據(jù)集邊緣的樣本密度。表1統(tǒng)計了圖2不同位置鄰域里的樣本數(shù)量。

圖2 Iris數(shù)據(jù)集不同位置樣本鄰域里近鄰數(shù)不同

表1 Iris數(shù)據(jù)集樣本鄰域近鄰數(shù)

用p(x)表示數(shù)據(jù)集D的概率分布函數(shù)，Si表示樣本xi表的鄰域。根據(jù)鄰域密度可以定義數(shù)據(jù)集邊緣的樣本如下：

算法：

輸入：D訓(xùn)練數(shù)據(jù)集；

輸出：D′剪輯后的訓(xùn)練集。

步驟：

1)選取一個固定大小的鄰域；

2)計算該鄰域里的樣本數(shù)；

3)選取一個合適的閾值(th)，如果鄰域里樣本數(shù)小于閾值保留；反之，丟棄；

4)由保留的樣本組成新的數(shù)據(jù)集D′；

5)在新的數(shù)據(jù)集D′訓(xùn)練分類器。

算法第3)步保留的鄰域內(nèi)樣本數(shù)小于閾值的樣本即為位于數(shù)據(jù)集邊緣的樣本。為了避免混淆，本文以下內(nèi)容將鄰域球里的樣本稱為鄰域里的近鄰。

在該算法里有2個參數(shù)需要確定：鄰域的大小和確定樣本是否被保留的閾值(th)。鄰域不能設(shè)置太大，否則無論樣本是位于數(shù)據(jù)集邊緣還是位于數(shù)據(jù)集內(nèi)部，鄰域內(nèi)都可能包含過多的樣本而無法區(qū)分樣本在數(shù)據(jù)集中的位置；反之，鄰域也不能太小，否則位于數(shù)據(jù)集內(nèi)部的樣本的鄰域也可能包含很少的樣本而無法區(qū)分。本文采用球形鄰域，鄰域球大小由球半徑?jīng)Q定，鄰域球半徑可以指定一個常數(shù)或者通過選取樣本集的一個較小的子集，用這個子集k近鄰半徑的平均值來表示鄰域球的半徑。閾值(th)決定被保留的子集的大小，閾值(th)越大，保留的樣本越多；反之，保留的樣本越少。本文根據(jù)需要保留的樣本數(shù)量來確定閾值。

圖3統(tǒng)計了2維Banana分布和2維高斯分布鄰域內(nèi)近鄰數(shù)量的直方分布圖。可以看到無論Banana分布還是高斯分布鄰域內(nèi)近鄰數(shù)量小于20都只有少部分。圖4根據(jù)鄰域內(nèi)近鄰數(shù)量直方分布圖找到的位于數(shù)據(jù)集邊緣的樣本?！?’對應(yīng)圖3中鄰域內(nèi)近鄰數(shù)量多于20的樣本；‘+’對于圖3中鄰域內(nèi)近鄰數(shù)量少于或等于20的樣本。

圖3 鄰域內(nèi)近鄰數(shù)量直方分布圖

圖4 根據(jù)鄰域內(nèi)近鄰數(shù)量找出的邊緣樣本

圖5表示僅保留圖4中位于數(shù)據(jù)分布邊緣的樣本后由SVDD算法學(xué)習(xí)得到的數(shù)據(jù)描述?？梢钥吹皆诒Ａ舻纳俨糠謽颖旧蠈W(xué)習(xí)得到的數(shù)據(jù)描述可以很好的描述原數(shù)據(jù)集。

圖5 由保留的邊緣樣本學(xué)習(xí)得到的數(shù)據(jù)描述

在不考慮其他優(yōu)化方式時，計算一個樣本的鄰域內(nèi)近鄰數(shù)量需要計算該樣本與其余樣本之間的兩兩距離，因此算法在最壞的情況下時間復(fù)雜度為O(n2)。

2 實驗與仿真

與其他分類方法一樣，本文所有實驗分別比較了ROC(Receiver Operating Characteristic) 曲線[10]和AUC(Area Under the receiver operating Characteristic)值[11]，并作為評價算法的標(biāo)準(zhǔn)。所有實驗在Intel CoreTM2 Duo CPU E7200 @2.53 GHz,2 GB,windows XP機器上完成。為了驗證算法的有效性，本文分別采用了人工數(shù)據(jù)集、UCI數(shù)據(jù)集[12]以及電能擾動信號模擬數(shù)據(jù)集。

2.1人工數(shù)據(jù)集

本實驗采用Banana、Highleyman、Lithuanian、two difficult classes、5維高斯分布、10維高斯分布，這6個人工數(shù)據(jù)集。其中每個數(shù)據(jù)集訓(xùn)練樣本由2 000個目標(biāo)數(shù)據(jù)組成，測試集有目標(biāo)數(shù)據(jù)和奇異數(shù)據(jù)共4 000個組成。鄰域球半徑取為50個樣本的20個近鄰組成的鄰域球半徑的平均值。實驗比較了算法的時間、保留的數(shù)據(jù)集大小以及模型包含的支持向量數(shù)量。實驗結(jié)果如表2～表5所示。其中表2的百分比表示子集保留的樣本數(shù)占原數(shù)據(jù)集的百分比；表3比較了子集與原數(shù)據(jù)集的AUC值；表4比較了子集與數(shù)據(jù)集支持向量數(shù)量；表5子集算法時間包括算法預(yù)處理時間和子集訓(xùn)練時間。

表2 算法保留的樣本

表3 AUC值比較

表4 支持向量數(shù)比較

表5 算法時間比較

由實驗結(jié)果可以看到，在僅保留位于數(shù)據(jù)分布邊緣的樣本，算法的性能并沒有降低，而模型的復(fù)雜度和算法的時間都得到了顯著的提高。

2.2UCI數(shù)據(jù)集

為了進一步說明本文算法的有效性，本實驗采用了3個常用的UCI數(shù)據(jù)集：Blood Transfusion、Mush Version 1和Waveform，數(shù)據(jù)集信息如表6所示。為了使這些數(shù)據(jù)集可以用于一分類，本文將Blood Transfusion和Mush Version 1中包含較多樣本的類作為目標(biāo)數(shù)據(jù)，另一類作為奇異數(shù)據(jù)；Waveform包含3類，分別被轉(zhuǎn)換為3個一分類問題：1vs23,2vs13和3vs12，前一類作為目標(biāo)數(shù)據(jù)，后兩類作為奇異數(shù)據(jù)。算法分別比較了AUC值、ROC曲線。選擇的樣本僅占原數(shù)據(jù)集的10%左右。

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

表7 UCI數(shù)據(jù)集AUC值比較

圖6～圖10為UCI數(shù)據(jù)集的ROC曲線，點線表示子集的ROC曲線，實線表示原數(shù)據(jù)集的ROC曲線。

圖6 Blood Transfusion的ROC曲線

圖7 Mush Version1的ROC曲線

圖8 Waveform 1vs23的ROC曲線

圖9 Waveform 2vs13的ROC曲線

圖10 Waveform 3vs12的ROC曲線

由圖8～圖10可以看出Waveform 1vs23、Waveform 2vs13和Waveform 3vs12的ROC曲線非常吻合；Blood Transfusion和Mush Version 1的ROC曲線雖然存在較大差異，但是從表7可以看出AUC值相差不是很大。而這些數(shù)據(jù)集的平均AUC值非常接近。表8比較了算法的時間和需要的支持向量數(shù)。與人工數(shù)據(jù)集的實驗結(jié)果一樣，在僅保留位于數(shù)據(jù)集邊緣的樣本時，SVDD模型的復(fù)雜性和算法時間都得到了很大的改進。子集上的支持向量數(shù)大約僅為原來的1/10，所需的時間大約僅為原來的1/4。

表8 UCI數(shù)據(jù)集AUC值比較

2.3模擬電能質(zhì)量擾動信號集

電能質(zhì)量擾動信號識別需要對常見的6種信號(電壓閃變、電壓諧波、電壓中斷、電壓振蕩、電壓暫降和電壓暫升)進行識別分類。支持向量機解決多分類問題的方式一種是通過將其中一類作為正類，其他類作為負(fù)類，即一對多方式，這種方式需要p個二分類器(p表示多分類類別數(shù))。由于負(fù)類包含了p-1類的樣本，因此負(fù)類的樣本會遠多于正類樣本，這樣轉(zhuǎn)換二分類數(shù)據(jù)集就會引起數(shù)據(jù)集不平衡問題；另一種方式是將p類數(shù)據(jù)轉(zhuǎn)換為p(p-1)個二分類問題，即一對一方式，這樣需要p(p-1)個二分類分類器[13]。本文將多類問題轉(zhuǎn)換為多個一分類問題，即分別以電壓閃變、電壓諧波、電壓中斷、電壓振蕩、電壓暫降和電壓暫升做為一分類問題的目標(biāo)數(shù)據(jù)，其它類作為一分類問題的奇異數(shù)據(jù)，對這6類電能質(zhì)量擾動信號識別問題就轉(zhuǎn)換為6個一分類問題。本文首先對電能擾動信號數(shù)據(jù)進行剪輯，然后再將剪輯后的數(shù)據(jù)進行訓(xùn)練，剪輯后的數(shù)據(jù)約占原來數(shù)據(jù)集的10%左右。

電能質(zhì)量擾動信號由matlab模擬而成，波長為4個周期，每個周期0.02 s，電壓頻率為50 Hz，采樣頻率12.8 kHz，其中電壓閃變3 053個樣本，電壓諧波4 032個樣本，電壓中斷1 872個樣本，電壓振蕩3 096個樣本，電壓暫降2 614個樣本，電壓暫升2 517個樣本。對于模擬得到的時域數(shù)據(jù)，首先利用db4小波[14-16]進行6層分解得到1 062維小波變換后的小波系數(shù)和尺度系數(shù)。然后利用主成分分析方法[17]保留約90%的信息。每類電能擾動信號數(shù)據(jù)被分為相互獨立的10份，其中9份被作為訓(xùn)練數(shù)據(jù)，剩余的一份與其他5類數(shù)據(jù)作為測試數(shù)據(jù)，這樣重復(fù)10次。表9、表10分別比較了原數(shù)據(jù)集與剪輯后的數(shù)據(jù)集的AUC值、精度、時間和模型復(fù)雜性，其中模型復(fù)雜度主要比較了模型中的支持向量數(shù)。

表9 電能質(zhì)量擾動信號數(shù)據(jù)精度比較

由表9可以看出在剪輯后的數(shù)據(jù)集上無論是AUC值還是識別精度都與原數(shù)據(jù)集相差無幾。而在保留原來性能的情況下，由表10可以看到在剪輯后的數(shù)據(jù)集上需要保留的支持向量和算法所需要的時間都比原數(shù)據(jù)集有所改進。

3 結(jié)論

SVDD算法與SVM算法類似需要求解二次規(guī)劃問題，時間和空間復(fù)雜度都比較高。SVDD的結(jié)果僅有數(shù)據(jù)集中部分支持向量決定，而這樣的支持向量通常位于數(shù)據(jù)集的邊緣，因此僅保留數(shù)據(jù)集邊緣的樣本不會降低算法的性能。本文提出通過鄰域樣本密度來尋找位于數(shù)據(jù)集邊緣的樣本。人工數(shù)據(jù)集和UCI標(biāo)準(zhǔn)數(shù)據(jù)集的實驗結(jié)果表明經(jīng)過鄰域密度剪輯過的數(shù)據(jù)集性能與原數(shù)據(jù)集的性能相比沒有下降，算法的訓(xùn)練時間和模型的復(fù)雜性都得到了改善。在電能質(zhì)量擾動信號識別問題方面也得到了很好的應(yīng)用。

圖10電能質(zhì)量擾動信號數(shù)據(jù)時間、模型復(fù)雜度比較

數(shù)據(jù)集 支持向量數(shù) 時間/s 子集原數(shù)據(jù)集子集原數(shù)據(jù)集電壓閃變897310．0520．781電壓諧波717720．0570．915電壓中斷463810．0230．502電壓振蕩616200．0490．792電壓暫降555060．0340．624電壓暫升514890．0310．603平均62．2583．20．0410．703

[1] Tax D M J.One-class classification[D].Deflt:Delft University of Technology,2001.

[2]Tax D M J,Duin R P W.Support vector data description[J].Machine Learning,2004,54:45-66.

[3]蔣莎,張曉龍.一種用于非平衡數(shù)據(jù)的SVM學(xué)習(xí)算法[J].計算機工程,2008,34(20):198-199.

[4]Nello Cristianimi,John Shawe-Taylor.An Introduction to Support Vector Machines and Other Kernel-based Learning Methods[M].Beijing:China Machine Press,2005.

[5]Shin H,Cho S.Neighborhood property-based pattern selection for support vector machines[J].NeuralComput,2007,19(3):816-855.

[6]Chang E Y.Concept boundary detection for speeding up svms[C].ICML06: Proceedings of the 23rd International Conference on Machine Learning,2006:681-688.

[7]Almeida M B,Braga A,Braga J P.SVM-KM:speeding SVMs learning with a priori cluster selection and k-means[C].Proceedings of the 6th Brazilian Symposium on Neural Networks,2000:162-167.

[8]Zheng S F,Lu X F,Zheng N N,etal.Unsupervised clustering based reduced support vector machines[C].

Proceedings of IEEE International Conference on Acoustics,Speech,and Signal Processing (ICASSP) 2,2003:821-824.

[9]Koggalage R,Halgamuge S.Reducing the number of training samples for fast support vector machine classification[J].Neural Inf Process,2004,2(3):57-65.

[10]方景龍,王萬良,何偉成.用于不平衡數(shù)據(jù)分類的FE-SVDD算法[J].計算機工程,2011(6):157-159.

[11]Bradley A.The use of the area under the ROC curve in the evaluation of machine learning algorithms[J].Pattern Recognition,1997,30(7):1145-1159.

[12]Blake C,Keogh E,Merz C.UCI repository of machine learning databases[EB/OL].http://www.ics.uci.edu/mlearn/MLRepository.html,University of California,Irvine,Dept.of Information and Computer Sciences,1998.

[13]Kressel U.Pairwise classification and Support Vector Machines,Cambridge[M].Massachusetts:MIT Press,1999:255- 268.

[14]陳珍萍,歐陽名三,劉淮霞.小波能量差分布和SVM結(jié)合的PQD識別[J].計算機工程與應(yīng)用,2011(20):241-244.

[15]王成山,王繼東.基于小波包分解的電能質(zhì)量擾動分類方法[J].電網(wǎng)技術(shù),2004,28(15):78-82.

[16]趙俊,楊洪耕,李偉.利用S變換與變尺度模板標(biāo)準(zhǔn)化的短時電能質(zhì)量擾動分類[J].南方電網(wǎng)技術(shù),2010,4(3):72-76.

[17]何朝暉.基于小波變換和人工神經(jīng)網(wǎng)絡(luò)的電能質(zhì)量擾動分類[D].長沙:湖南大學(xué),2009.

ASampleReductionMethodforSVDDandItsApplication

ZHANG Anan1,ZHENG Ping2,FANG Lin3,PENG Songsong4

(1.Energy Research Institute,Jiangxi Academy of Sciences,330029,Nanchang,PRC;2.Nanchang Normal University,330032,Nanchang,PRC;2.Department of Criminal Science and Technology,Jiangxi Police College,330100,Nanchang,PRC;2.School of Electronic and Information Engineering,Jinggangshan University,343009,Ji′an,Jiangxi,PRC)

Usually for large data learning problems,we need to select a subset of training set to study,in order to reduce the time and space complexity of the problem itself.Many scholars proposed to find useful samples,which locate near the boundary of the data distribution,based on K-nearest neighbors.The SVDD (Support Vector Data Description) algorithms,only in the edge region of the sample Data sets,have an effect on learning results. In this paper,a novel method to identify whether a sample locates near the boundary region by estimating the probability density of a neighborhood area.The probability density of a sample locating boundary region is much larger than the probability density of the sample locating in the internal of the data distribution.Removing the samples locating in the internal of the data distribution,the scale of training set can reduced heavily,the speed of training can be fast and the performance will not deteriorate.For power disturbance signal recognition problem,which is a real-time problem,this algorithm had a good application.

training det;dample;dupport vector data description;sample reduction;power disturbance signal recognition

2014-09-04;

2014-10-08

張安安(1979-)，女，江西吉安人，本科，副研究員，研究方向：計算機軟件工程。

10.13990/j.issn1001-3679.2014.06.031

TP181

A

1001-3679(2014)06-0884-07