K-means聚類與SVDD結合的新的分類算法

摘 要:為了提高支持向量數據描述(SVDD)的分類精度，引入局部疏密度提出了改進的SVDD算法。該算法提高了分類精度，但增加了計算復雜度。為此，先用K-means聚類將整個數據集劃分為k個簇，再用改進的SVDD算法并行訓練k個簇，最后再對獲得的k個局部支持向量集訓練，即得到最終的全局決策邊界。由于采用了分而治之并行計算的方法，提高了算法的效率。對合成數據(200個)和實際數據的實驗結果表明，所提算法較SVDD算法，訓練時間降低為原來的10%，分類錯誤率較原來的降低了近一半。因此，所提算法提高了分類精度和算法效率。

關鍵詞:單值分類; 支持向量數據描述; K-means聚類; 局部疏密度

中圖分類號:TP311 文獻標志碼:A

文章編號:1001-3695(2010)03-0883-04

doi:10.3969/j.issn.1001-3695.2010.03.020

New classification algorithm K-means clustering combined with SVDD

LIU Yan-hong， XUE An-rong， SHI Xi-yun

(School of Computer Science Telecommunications Engineering， Jiangsu University， Zhenjiang Jiangsu 212013， China)

Abstract:This paper proposed an improved SVDD algorithm by introducing a local density degree for each data point in order to improve the support vector data description(SVDD) classification accuracy. Proved to improve the classification accuracy， but the increase of computational complexity. To this end， first divided the whole data set into k clusters using K-means clustering algorithm. Then， trained the k clusters in parallel by improved SVDD. Finally， trained the k obtained local support vector sets and got the final overall decision border. As a result of divide and conquer method and parallel computing， improved the efficiency of the algorithm. Synthetic data and real data experimental results show that the proposed method than SVDD algorithm， training time is reduced to 10% and classification error rate lower than the original by almost half. Therefore， the proposed algorithm improves the classification accuracy and algorithm efficiency.

Key words:one-class classification; support vector data description; K-means clustering; local density degree

0 引言

單值分類技術在故障檢測、雷達目標檢測、股票市場控制、網絡入侵檢測等領域有著廣泛應用，已引起研究者的廣泛興趣[1]。支持向量數據描述(support vector data description，SVDD)算法是Tax[2]以支持向量分類器為基礎提出的單值分類算法。該算法試圖尋找包圍目標集最小的封閉超球面，而超球面的確定僅依靠目標集的訓練數據。該算法的核心是求解二次規劃問題，由于核函數的計算復雜導致該算法計算復雜度非常高。為了提高計算效率，很多研究者提出了改進算法，主要分為三類，即二次規劃算法、分解算法和并行學習算法。Lee等人[3]直接針對原始優化問題求解，將原始優化問題轉換為無約束的嚴格二次規劃，用牛頓法來求解。這種方法可以得到更可靠的解，并且學習速度至少提高一個數量級，但是采用這種方法僅僅存儲核矩陣就需要一個隨樣本大小二次增長的內存空間。為了解決這個問題，Keerthi等人[4]提出將二次規劃問題轉換為求解一系列小規模的二次規劃問題的分解算法，在不影響分類精度的同時提高了學習速度，減少了內存空間的需要，并提出SMO算法[4]，可解析每一子問題最優解，加快了算法的收斂速度，但是這種方法增加了優化計算量。為了進一步提高算法的學習速度，Collobert等人[5]提出了基于樣本集分割的并行學習算法，依據分治思想將學習樣本集分割成p個子集，提高了效率。但是由于p個子集是隨機劃分的，降低了分類準確率，并且增添額外的規則也增加了計算量。為此，本文首先通過引入樣本的疏密度來改進SVDD算法，使其超球球心落在高密度區域以提高分類精度，提出用K-means聚類算法解決數據集劃分問題，用改進的SVDD并行學習算法(即KmD-SVDD算法)求得各個子集上的局部支持向量，將所有的局部支持向量組成集合重新訓練得到全局最優解;最后用實驗驗證所提算法可提高算法效率和分類精度。

1 SVDD及其改進

1.1 支持向量數據描述(SVDD)

SVDD算法通過找到能包含一組數據的最小半徑的超球體實現對這組數據的描述，而異常點處在該球體的外面。為了減少異常點的影響，使用松弛變量ξi把該異常點排除在超球體的外面。即在約束條件下最小化:

min f(R，a，ξ)=R2+C∑ξi;i=1，2，…，n(1)

約束條件為

‖xi-a‖2≤R2+ξi;ξi≥0(2)

其中:C為某個指定的常數，起到控制對錯分樣本懲罰程度的作用，以實現在錯分樣本的比例與算法復雜程度之間的折中。這個優化問題的解是由拉格朗日(Lagrange)泛函的鞍點給出的，通過變換，求式(1)的最小值可變成求其對偶問題的最大值。

L=∑iαi(xi#8226;xi)-∑i，jαiαj(xi#8226;xj)

(3)

s.t. 0≤αi≤C ∑iαi=1(4)

其中:αi≥0為拉格朗日系數。最大化式(3)就可以求得α的最優值。對于0<αi

‖z-a‖2=(z#8226;z)-2∑iαi(z#8226;xi)+∑i，jαiαj(xi#8226;xj)≤R2(5)

成立，則z為目標樣本;否則z為非目標樣本。

上面的計算中用到了點積運算，用核函數K(x，y)來替代點積運算，實現由低維空間到高維空間的映射，從而使低維空間的非線性問題轉換為高維空間的線性問題。引入核函數后，原來的式(3)變成了如下形式:

L=∑iαiK(xi，xj)-∑i，jαiαjK(xi，xj)

(6)

判別函數式(5)變為

‖z-a‖2=K(z#8226;z)-2∑iαiK(z#8226;xi)+∑i，jαiαjK(xi#8226;xj)≤R2(7)

1.2 D-SVDD算法

傳統的SVDD沒有考慮目標數據的密度分布情況，在許多實際問題中，每個樣本點由于其所處區域的疏密度的不同其重要性也不同:在高密度區域的目標數據比在低密度區域的數據重要，因為在高密度區域的數據與低密度區域的數據相比更應包含在超球體的內部。所以，如果不考慮樣本的疏密度的不同，對所有樣本同等對待則求出的決策邊界不是最優的。

1.2.1 局部疏密度的計算

本文中采用最近鄰方法[6]來為每個目標樣本點計算局部疏密度。令樣本點xi的局部疏密度為ρi，用d(xi，xmi)表示樣本xi和它的第m個最近鄰居xmi的距離，為所有目標樣本與各自的第m個最近鄰居xmi的距離的平均距離，樣本xi的局部疏密度ρi定義為

ρi=exp{w×d(xi，xmi)};i=1，…，n(8)

其中:k=(1/n)∑ni=1d(xi，xmi);n是目標類樣本的個數;0≤w≤1是權重因子。顯然，具有高局部疏密度的樣本處于高密度區域內，較大的權重因子w可以得到較大的局部疏密度。為了把局部疏密度引入到SVDD來優化決策邊界，引入一個新的幾何距離度量。假設每個目標類樣本被表示成(xi，ρi)，定義當引入局部疏密度后，xi到超球(a，R)圓心的距離為δi={ρi(xi-a)#8226;(xi-a)}1/2。注意到，隨著ρi的增大δi會增大，超球體要想包圍這樣的樣本點，必須增大超球半徑，因此高密度區域的數據對最后求得的最優超球的大小有很大的影響。

1.2.2 改進的SVDD算法

引入局部疏密度后，求解最優超球體的二次規劃問題就表示為

min f(R，a，ξ)=R2+C∑ξi;i=1，2，…，n(9)

約束為

ρi(xi-a)#8226;(xi-a)≤R2+ξi(10)

求解該二次規劃問題的方法與SVDD求解方法一樣，通過變換需要求解式(9)的對偶問題:

L=∑iρiαiK(xi#8226;xi)-1T∑i，jαiαjρiρjK(xi#8226;xj) (11)

約束為

∑iαi=1;0≤αi≤C

T=∑iαiρi;i=1，…，n(12)

注意到，當ρi=1時，式(11)就與SVDD算法的式(3)相同，因此該算法是傳統SVDD的一般化推廣。對于測試樣本z，決策函數就變為

‖z-a‖2=K(z#8226;z)-2T∑iρiαiK(z#8226;xi)+

2T2∑i，jρiρjαiαjK(xi#8226;xj)≤R2(13)是否成立。

D-SVDD算法雖然能夠提高分類精度，但是由于SVDD算法本身的計算復雜度很高[7]，為O(n3)。其中n為目標樣本的個數，再加上D-SVDD算法中要計算每個樣本的疏密度，導致計算復雜度更高。為此，提出了將K-means聚類分別與SVDD算法和D-SVDD算法相結合的快速分類算法KmSVDD算法和KmD-SVDD算法。

2 KmSVDD和KmD-SVDD算法

KmSVDD算法和KmD-SVDD算法的思想是基于以下兩點考慮的:a)借鑒于已有改進算法的分治的策略;b)考慮到SVDD的分類邊界是由位于分類邊界上的支持向量決定的，即起決定作用的是那些少數支持向量對應的樣本，位于超球內部的數據樣本對決策邊界不起作用。為此，提出將大數據集劃分為若干子集，在各個子集上用SVDD算法求解，得到各局部支持向量集，然后提取出這些支持向量集，重新組成數據集用SVDD求解即得到全局最優解。已有的改進算法在采用分而治之策略時，“分”的方法大都是將整個目標數據集隨機地等分成n個互不相交的子集。在這種隨機劃分的子集上，用支持向量數據描述算法訓練會得到比較少的支持向量，這樣會導致目標樣本信息丟失過多。所以，文中提出采用聚類的方法將大規模的數據集劃分為各個簇，這樣簇內的數據樣本相互之間是相似的，各個簇上用SVDD算法訓練會得到比較準確的支持向量。這里采用K-means聚類算法劃分目標數據集，是因為K-means聚類方法在時間復雜度與樣本點個數線性相關的前提下有較好的性能。提出的該快速分類算法克服了先前的研究中需要添加額外規則得到全局最優解的局限。由于KmD-SVDD算法在求局部支持向量時把每個訓練樣本的局部疏密度考慮在內，這樣每個超球的球心落在高密度區域內，使得最終得到最優決策邊界，提高了分類準確率。

2.1 KmSVDD算法

該算法包含兩個階段，即訓練階段和測試階段。

1)訓練階段

輸入:目標樣本集O={o1，o2，…，on};聚類個數k;核寬度參數σ。

輸出:超球球心a、半徑R和支持向量集SV。

a)選擇k個點作為初始質心，用K-means聚類算法把目標樣本集O={o1，o2，…，on}劃分為k個子集S1，S2，…，Sk。

b)分別在S1，S2，…，Sk上根據高斯核函數公式計算K(xi，xi)和K(xi，xj)。其中i和j是子集中的樣本的下標。

c)在各個子集S1，S2，…，Sk上用SVDD算法訓練得到局部支持向量集SV1，SV2，…，SVk。

d)在{SV1，SV2，…，SVk}上用SVDD算法訓練得到最終球心a、半徑R和支持向量集SV。

2)測試階段

輸入:測試集T={t1，t2，…，tm};超球球心a;超球半徑R;支持向量集SV。

輸出:帶類標號的測試集(類標號為0代表目標樣本，類標號為1代表非目標樣本)。

a)從測試集T={t1，t2，…，tm}中讀取測試樣本z。

b)利用判別式(5)測試樣本z。若滿足，則該樣本的類標號標記為0，否則標記為1。

c)重復a)和b)，直到測試集T中的樣本讀取完畢。

該算法需要事先給出聚類個數k和核寬度參數σ，這兩個參數的設置問題將在3.2和3.3節討論。

2.2 KmD-SVDD算法

KmD-SVDD算法與KmSVDD算法過程類似，只是多了求目標集樣本疏密度的過程。

訓練階段:KmD-SVDD算法訓練階段在KmSVDD算法的步驟a)和b)之間添加以下步驟:利用式(8)計算各個子集S1，S2，…，Sk中的樣本的疏密度。其余步驟同KmSVDD算法，只是把用SVDD算法訓練改成用D-SVDD算法訓練即可。

測試階段:把KmSVDD算法中的判別函數改為式(13)即可，其余步驟同KmSVDD。

2.3 KmSVDD和KmD-SVDD算法復雜度分析

在上述KmSVDD算法中，訓練階段第一步用K-means算法聚類的時間復雜度為O(kN);用SVDD算法訓練k個子問題的總的時間復雜度為kO(N/k)3;第四步訓練所有支持向量的時間復雜度為O((αk)3)(其中α為在每個子集上求解得到的支持向量的平均個數)。故總的復雜度為O(kN)+kO((N/k)3)+O((αk)3)。在稀疏解的條件下，支持向量的個數αk比訓練集的總的數目N小得多，所以總的復雜度約等于kO((N/k)3)，相比SVDD算法的時間復雜度O(N3)來說，該算法的效率要比SVDD高，特別是當N足夠大時效果更明顯。

KmD-SVDD算法復雜度比KmSVDD算法多了一步求各個子集中樣本疏密度的計算，求解各個子集中的樣本疏密度總的時間復雜度為kO((N/k)2)。這樣總的復雜度為O(kN)+kO((N/k)2)+kO((N/k)3)+O((αk)3)，與KmSVDD類似，在稀疏解的條件下總的時間復雜度約等于kO((N/k)3)，該算法同樣比SVDD效率高。

3 實驗

3.1 KmSVDD算法可視化過程(以k=5為例)

在人工生成的200個香蕉形狀的數據集上應用KmSVDD算法訓練，這里聚類個數取值為5。該算法的可視化過程如圖1所示。

3.2 高斯核函數參數的調節

文獻[8]指出在支持向量數據描述算法中使用較多的是高斯核函數，這是因為:a)高斯核具有一般核函數的各種特性;b)高斯核獨立于數據與原點之間的相對位置關系，而僅僅與數據之間的距離有關;c)使用高斯核函數時，模型邊界的緊致性較好。所以本文采用高斯核函數，分兩種情況討論高斯核函數中參數σ2:

(a)當σ2→0時，exp (-‖x-y‖2/2σ2)=δij，i=j時δij=1;i≠j時，δij=0。

這樣，當αi=1/N時式(6)達到最大，這時意味著每個訓練樣本都是支持向量，會發生嚴重的過學習現象，對測試樣本不具有任何推廣能力。

(b)當σ2→∞，高斯核函數的泰勒展開式為

exp(‖x-y‖22σ2)=1-‖x-y‖2σ2+o(‖x-y‖2σ2)=1-‖x‖2σ2-‖y‖2σ2+xTyσ2+o(‖x-y‖2σ2)

由上式可以看出，當σ2趨向于無窮大時，核函數的值約等于1，這樣當其中N-1個樣本對應的α均等于0，而其中一個樣本對應的α=1時式(6)達到最大，這就意味著幾乎不存在支持向量，會發生嚴重的欠學習現象，測試樣本會全部劃分為目標類樣本。

通過以上兩點的分析，核寬度參數σ2可以調節支持向量的個數，當增加σ時所包圍的區域的體積會變大，支持向量的個數會減少;反之，當減小σ時所包圍的區域的體積會減小，支持向量的個數會增大。所以在實驗中，根據支持向量的個數來調節σ的大小。

從核函數exp(-‖x-y‖2/2σ2)可以看出，σ2的大小完全是針對‖x-y‖2而言的，因此，在實際應用中，只要σ2的取值比訓練樣本之間的最小距離小得多時就能達到σ2→0的效果，當σ2比訓練樣本之間的最大距離大得多時就可以達到σ2→∞的效果。基于這一考慮，實驗中采用訓練樣本之間的最小距離和最大距離的平均值作為σ的初始值，若訓練結果中支持向量個數超過總體訓練樣本的30%，則減小高斯參數重新訓練，反之，如果支持向量個數低于總體訓練個數的10%，則增加高斯參數重新訓練，直到找到合適的σ的值為止。

3.3 聚類個數k的選擇方法

3.3.1 聚類個數k對訓練時間的影響

為了研究聚類個數k對訓練時間的影響，在人工生成的香蕉形狀的數據集(200個)上分別用SVDD、KmSVDD和KmD-SVDD算法實驗，所用的訓練時間和聚類個數k的關系如圖2所示。

從圖2得知，KmSVDD和KmD-SVDD算法相比SVDD算法所用的訓練時間可以由原來的10 s以上降低到1 s以下，降低為原來的10%。聚類個數k并不是任意設定的，隨著k的增大訓練時間先減少后增加，在增大到某種程度后就會比只采用SVDD算法的訓練時間長。所以，如何選擇合適的k值是十分關鍵的。

3.3.2 聚類個數k的選擇

聚類個數k的選擇沒有現有的理論依據，為了尋找合適的k值，在不同規模的數據集上用KmSVDD算法訓練，尋求當訓練時間取最小值時的k值與數據集的規模的關系，并以此作為依據在實際應用中快速得到合適的k值。實驗采用的數據集樣本大小分別為200、400、600、1 000的人工生成的香蕉形狀數據集。聚類個數k的選擇與訓練時間的關系如圖3所示。

通過分析在不同規模數據集上聚類個數與訓練時間的關系可以看出:數據集大小N=200時，在k=7處訓練時間t取最小值;N=400時，k=11處t取最小值;N=600時，k=17處t取最小值;N=1 000時，k=30處t取最小值。從這幾組數據上可以得出這樣的規律，經過聚類后得到的簇的平均樣本個數均在25～40，即k的最小值應在k1=N/40和k2=N/25之間取得。因此，可以此為依據，當給定樣本個數為N的數據集時，用k2作為k的上限值，用k1作為k的下限值。從k1和k2分別以步長向中間靠攏，并分別計算每個k值對應的時間t，直到找到一個k值，使得該k值對應的時間t均小于k-Δk和k+Δk對應的時間;然后縮小在k-Δk與k+Δk之間的步長。重復以上過程，直到max(tn-1-tn，tn+1-tn)<δ。其中δ是用戶設定的閾值。如果數據量不是太大，δ可以設定小一點的值(如0.5);如果數據量很大，δ可以設定比較大的值(如3.0)。

3.4 在實際數據集上測試各算法的分類準確率

在真實數據集UCI的機器學習庫中Iris數據集上[9]訓練并測試來比較SVDD、KmSVDD和KmD-SVDD三種算法的檢測精度。用10-折交叉驗證法得到各自的平均錯誤率，聚類個數k=5，核寬度參數σ2=5。測試結果如表1所示。

表1 三種算法的10-折交叉驗證平均分類錯誤率 %

Class noSVDDKmSVDDKmD-SVDD

03.474.32 0.42

1 7.739.565.36

29.3311.278.23

total 6.848.38 3.71

Iris數據集總共有150個樣本，分三類，每類50個樣本，在表1中第一列表示每次作為目標樣本的類標號，其余兩類作為異常類。從表1中可以看到，SVDD、KmSVDD、KmD-SVDD三種算法的平均分類錯誤率分別為6.84%、8.38%、3.71%。KmSVDD算法的平均錯誤率高于SVDD算法，而KmD-SVDD算法的平均錯誤率低于SVDD算法，在3.3.1節實驗中已經驗證KmD-SVDD算法的效率比SVDD有很大提高，現在在實際數據集上證明KmD-SVDD算法的分類準確率也高于SVDD算法。因而，KmD-SVDD算法不僅提高了算法的運算效率，而且分類準確率也有所提高。

4 結束語

針對支持向量數據描述算法復雜度高的問題，本文提出了將K-means聚類與改進的SVDD算法D-SVDD相結合的快速分類算法KmD-SVDD。基于分而治之的策略，采用并行學習算法的同時引入樣本的局部疏密度求解局部決策邊界，以提高分類準確率，最后只提取出支持向量訓練，從而降低了算法復雜度。文中分別在人工數據集和實際數據集上的實驗結果表明，該算法不僅在降低算法復雜度上具有明顯優勢，而且分類錯誤率降低為原來的一半。因此，所提算法提高了分類準確率和算法效率。

參考文獻:

[1]JUSZCZAK P， ADAMS N M， HAND D J， et al. Off-the-peg and bespoke classifiers for fraud detection[J]. Computation Statistics and Data Analysis， 2008，52(9):4521-4532.

[2]TAX D M J. Support vector data description[J]. Machine Lear-ning， 2004，54(1):45-46.

[3]LEE Y J， MANGASARIAN O L. A smooth support vector machine for classification[J].Computational Optimization and Applications， 2001，20(1):5-22.

[4]KEERTHI S S， GILBERT E G. Convergence of a generalized SMO algorithm for SVM classifier design[J]. Machine Learning， 2002，46(1):351-360.

[5]COLLOBERT R， BENGIO S， BENGIO Y. A parallel mixture of SVMs for very large scale problems[J]. Neural Computation， 2002，14(5):143-160.

[6]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.

[7]GUO S M， CHEN L C， TSAI J S H. A boundary method for outlier detection based on support vector domain description[J]. Pattern Recognition， 2009，42(1):77-83.

[8]趙峰，張軍英，劉敬.一種改善支撐向量域描述性能的核優化算法[J].自動化學報， 2008，34(9):1121-1127.

[9]NEWMAN D J， HETTICH S， BLAKE C L， et al. UCI repository of machine learning databases[EB/OL].(1998). http://www.ics.uci.edu/~mlearn/MLRepository.html.