支持向量機的大樣本迭代訓(xùn)練算法

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：2096-4706（2025）12-0085-07

Large Sample Iterative Training Algorithm for Support Vector Machine

CHEN Jimao

（Sanya Instituteof Technology， Sanya 572022， China）

Abstract： Aiming at the large sample training problem for Support Vector Machine （SVM），a new iterative training algorithmis proposed.Tobuildan initial training sample set，theK-meansclustering algorith is used tocompressthe training sample set，with each cluster centroid serving as the initial training sample set，reducing redundant information between samples toenhance trainingspeed.Toensure thetraining acuracy，theresultingcentroidistakenasthe initialsampleset， andthe boundarysamplesand misclasifiedsamples areaddedtothe initial sample setwithclassification.Anditis usedas trainingsamplesforiterativetraining until the numberof misclasifiedsamples is stable.Here，the K-means clustering SVM iterative training algorithmcanreduce thecomputational complexity while maintaining the training accuracyand improve the classification and training speed by optimization.

Keywords： Support Vector Machine; K-means clustering algorithm; iterative algorithm; Machine Learning

0 引言

支持向量機是最基本的模式識別與機器學(xué)習(xí)方法，應(yīng)用相當(dāng)廣泛，其基本原理是用線性分類器將兩類不同的信號特征數(shù)據(jù)顯著分離。支持向量機的學(xué)習(xí)訓(xùn)練過程可轉(zhuǎn)化為二次規(guī)劃問題，傳統(tǒng)優(yōu)化解法需要全體訓(xùn)練樣本同時參與運算，需耗費大量運算時間和機器內(nèi)存，這對于海量訓(xùn)練數(shù)據(jù)顯然是不能接受的。為此，大樣本集學(xué)習(xí)速度的改進(jìn)算法[近些年來出現(xiàn)兩類：一類是將SVM中QP問題分解為一系列的QP問題的代數(shù)方法，如序貫最小優(yōu)化算法；另一類是將SVM中最小化問題轉(zhuǎn)化為求解兩個凸包問題的幾何方法，如循環(huán)最近點算法[3]。針對當(dāng)支持向量的數(shù)量比較龐大時分類速度就會下降這一問題，Scholkopf的簡約集方法[5]降低了分類時的計算量，提高了分類速度。

但遇到大樣本集[時計算耗時顯著增加。且在大樣本集中存在冗余情況，和考慮到支持向量機分類效率和準(zhǔn)確率僅與支持向量有關(guān)[7，因此提出了支持向量機的大樣本迭代訓(xùn)練算法。此算法對大樣本集采用K均值聚類算法壓縮作為初始訓(xùn)練樣本集，在迭代的過程中加入邊界樣本和錯分樣本更新訓(xùn)練樣本集[8]。借助歷年溫度、相對濕度和降雨關(guān)系表分析，結(jié)果不難看出支持向量機的大樣本迭代訓(xùn)練算法能夠在保持訓(xùn)練精度的前提下，大幅提高訓(xùn)練和分類的速度。

1 支持向量機

1.1 線性可分的最優(yōu)超平面

假設(shè)訓(xùn)練數(shù)據(jù)樣本為 {（x_i，d_i）}_i=1^N ，其中 x_i 表示第 i 個樣本的輸入變量。 d_i 表示對應(yīng)的輸出變量。設(shè)子集d_i=+1 模式和子集 d_i=-1 模式都是線性可分的。其分離超平面方程為：

w^Tx+b=0

其中 x 表示輸入向量， w 表示可調(diào)權(quán)向量， b 表示偏置。于是相應(yīng)的線性分類判別可表述為：

d_i=+1?w^Tx_i+bgt;0

d_i=-1?w^Tx_i+blt;0

對于給定的權(quán)向量 w 和偏置 b ，由式（1）表示的分類超平面兩側(cè)附近數(shù)據(jù)點所確定的兩個超平面稱為分離邊界。分類超平面的選取應(yīng)使得兩分離邊界盡可能相互遠(yuǎn)離。一個二維輸入空間的最優(yōu)超平面的幾何構(gòu)造如圖1所示。

圖1二維線性可分模式最優(yōu)超平面

其中落在線上的符號點表示的數(shù)據(jù)點為支持向量。用 w₀ 和 b₀ 分別表示權(quán)向量和偏差的最優(yōu)值，原點到最優(yōu)分類超平面的距離為 b₀/w₀ ，當(dāng) b₀gt;0 時，原點處于最優(yōu)超平面的正側(cè)； b₀lt;0 時在負(fù)側(cè)； b₀=0 時最優(yōu)超平面通過原點。

問題：給定訓(xùn)練集 T=（x_i，d_i）_i=1^N ，尋找最優(yōu)超平面參數(shù) w₀ 和 b₀ 。根據(jù)以上所描述，看到這對 必須滿足以下約束條件為：

w₀^Tx_i+b₀?0，d_i=+1

w₀^Tx_i+b₀?0，d_i=-1

由式（2）可知，樣本線性可分時總是可以重新調(diào)整參數(shù) w₀ 和 b₀ 得到式（3）。

支持向量在機器學(xué)習(xí)運行中起著突出的作用。從概念上講，支持向量是最接近最優(yōu)超平面的數(shù)據(jù)點，因此最難分類。所以，它們直接關(guān)系到?jīng)Q策面的最佳位置。

1.2 尋找最優(yōu)超平面的二次優(yōu)化

首先注意訓(xùn)練樣本是 T={x_i，d_i}_i=1^N ，由式（3）的雙線約束，把這兩條線合并成單線得到：

有了這種形式的約束，現(xiàn)在就可以給定訓(xùn)練樣本{（x_i，d_i）}_i=1^N 求權(quán)向量 w 和偏置 b 的最佳值，使之滿足式（4）的約束條件。權(quán)向量 w 最小化了代價函數(shù)為：

為了方便演示，將約束優(yōu)化問題置為原始問題。

基本特征如下：

1）將成本函數(shù) 當(dāng)作是 w 凸函數(shù)。

2）約束在 w 中的成本函數(shù)是線性的。

所以，可以利用拉格朗日乘數(shù)方法去求解約束優(yōu)化問題。首先構(gòu)造拉格朗日函數(shù)并展開式子可得：

其中， a_i 表示拉格朗日乘子。約束優(yōu)化問題的解是由拉格朗日函數(shù) 決定的。 關(guān)于w 和偏置 b 求偏導(dǎo)，并將結(jié)果等于零，得到兩個最優(yōu)性條件并整理后可得：

因此，令 可以重新定義式（6）設(shè)置目標(biāo)函數(shù)為：

1.3不可分的模式最優(yōu)超平面

為了解決在訓(xùn)練數(shù)據(jù)大樣本時遇到錯誤分類，如果數(shù)據(jù)點 違反下列條件（見式（4））：

這種違反可以通過以下兩種方式之一產(chǎn)生：

1）數(shù)據(jù)點 落在分離區(qū)，但在決定正確的側(cè)表面。

2）數(shù)據(jù)點 是在決策表的錯誤的一邊。

在第一種情況下，有正確的分類。但在第二種錯誤分類，為不可分的數(shù)據(jù)點集的形式處理階段，設(shè)置了非負(fù)的標(biāo)量變量 ，在分離超平面的定義（即決策面），如下所示：

d_i（w^Tx_i+b）?1-ε_i，i=1，2，…，N

其中， ε_i 表示松弛變量；它們測量數(shù)據(jù)點偏離理想模式可分性條件[。當(dāng) 0lt;ε_i?1 數(shù)據(jù)點落在分離區(qū)，但在決定正確的側(cè)表面。當(dāng) ε_igt;1 它落在分類超平面的錯誤的一邊。支持向量的那些特定的數(shù)據(jù)點滿足式（8）的精確 ε_igt;0 。此外，還可以滿足條件的支持向量 ε_i=0 。請注意，如果 ε_igt;0 離開了訓(xùn)練樣本，決定表面將發(fā)生變化。

在訓(xùn)練大樣本中，如果找到一個分離超平面，平均誤差被最小化 ，然而，最小化 與 w 是一個非凸優(yōu)化問題，是NP完全問題，于是給定訓(xùn)練大樣本 {（x_i，d_i）}_i=1^N 求權(quán)向量 w 和偏置 b 的最佳值，使之滿足約束條件：

1） d_i（w^Tx_i+b）?1-ε_i，i=1，2，…，N

2） ε_i?0，i=R （20

加權(quán)向量 w 和松弛變量 ε 最小化成本泛函數(shù)為：

其中， C 表示指定的正參數(shù)，在上面描述的利用Lagrangemultipliers和訴訟法在類似的方式，制定了對偶問題的不可分模式。

在訓(xùn)練大樣本 {（x_i，d_i）}_i=1^N 找到乘子 {α_i}_i=1^N 最大化目標(biāo)函數(shù)：

約束條件為：

其中 c 表示指定的正參數(shù)。對于非線性情況，如果核函數(shù) 滿足Mercer條件，用 代替式（10）中的內(nèi)積運算，得到目標(biāo)泛函數(shù)為：

同樣要滿足上述約束條件，得到的分類器函數(shù)為：

其中， a_i 表示支持向量且不等于 0 。由式 （11）可知式（12）是收斂到最優(yōu)解的。

1.4支持向量案例分析

1.4.1 數(shù)據(jù)獲取

給定兩個分布各產(chǎn)生 N=250 個訓(xùn)練樣本如表1所示。

表1初始訓(xùn)練樣本的獲取

1.4.2 支持向量

由于訓(xùn)練樣本分布呈正態(tài)分布情況，根據(jù)前面相關(guān)理論首先設(shè)置一高斯核函數(shù)為：

向量機訓(xùn)練數(shù)據(jù)樣本時，取徑向基函數(shù)為e^-σ|u-ν|2 核函數(shù)，參數(shù) σ=0.5 。目的是在給定訓(xùn)練樣本{（x_i，d_i）}_i=1^N 中找到拉格朗日乘子 {α_i}_i=1^N 式（10）最大化目標(biāo)函數(shù)為，其中選取參數(shù) C=10 。

當(dāng)目標(biāo)函數(shù)最大時就可以找到相應(yīng)的乘子{α_i}_i=1^N ，且 {α_i}_i=1^N≠0 是對應(yīng)訓(xùn)練樣本的支持向量。在MATLAB應(yīng)用軟件中運用quadprog函數(shù)求解這樣的二次規(guī)劃問題，求解得到的支持向量 X_s 分布情況如圖2所示。

1.4.3 超平面

綜合上面相關(guān)的理論知識，運用最大化目標(biāo)函數(shù)時的 {α_i}_i=1^N ，以及此時產(chǎn)生的支持向量，設(shè)置可調(diào)的權(quán)向量： （20

計算偏置： 分類器方程為：

于是得到：

在給定的權(quán)向量 w 和偏置 b ，在數(shù)據(jù)點之間定義分離的超平面的稱為分離邊界，運用MATLAB中的contour畫出高斯核函數(shù)下的超平面的SVM分類如圖3所示。

1. 4.4 試驗解析

以上是選取初始訓(xùn)練樣本 N=250 時所得結(jié)果，可以看出SVM效果尚可，為了充分檢測SVM分類狀態(tài)，接下來討論分析SVM的訓(xùn)練時間 T ，為了了解支持向量數(shù) X_s 以及錯分樣本數(shù) X_e 的情況，選取初始訓(xùn)練樣本各為 N=10 ，30，60，90，120，150，180，200，220， 250^…… 時分析其性能，通過實驗確定他們之間的關(guān)系，結(jié)果如表2所示。

表2不同樣本數(shù)結(jié)果

從表中可以看出隨著初始訓(xùn)練樣本數(shù)量增多，訓(xùn)練時間變化比較大，訓(xùn)練速度（N/T）大幅度減小；第1類和第2類的支持向量與錯分樣本數(shù)量也增多，幾乎成正比例變化，這點也可以從平均錯分率看出來，在同樣的一個正態(tài)分布類型樣本，保持在同一個相關(guān)函數(shù)情況下的平均錯分率幾乎不會有改變。

可以看出，訓(xùn)練樣本數(shù)量增加的同時時間也相應(yīng)變大，它們之間會存在什么樣的函數(shù)關(guān)系，接下來分析訓(xùn)練樣本數(shù)量跟訓(xùn)練時間的關(guān)系。

利用多項式函數(shù)擬合得：

T=a₁N²+a₂N+a₃

數(shù)據(jù)代入原式解得：

a=（0.0039-0.517013.2119）

根據(jù)上面的關(guān)系，試者把初始訓(xùn)練樣本 N 增多這時的訓(xùn)練時間 T 的變化情況如表3所示。

表3訓(xùn)練樣本與訓(xùn)練時間的關(guān)系

看得出來支持向量機在大樣本情況下的訓(xùn)練速度較慢，因為它的訓(xùn)練需要龐大矩陣計算[1]，在實際問題當(dāng)中不利于工作的進(jìn)行。所以現(xiàn)在針對大規(guī)模數(shù)據(jù)的支持向量機，應(yīng)減少訓(xùn)練時間以達(dá)提高速度。

2K均值聚類的SVM迭代算法

2.1 K均值聚類

K均值聚類算法是典型的基于距離的聚類算法[12]。采取它們之間的間距作為相似性的評價指標(biāo)，即兩個對象的間距越近，說明它們之間相似度越大。根據(jù)每次迭代的結(jié)果得到間距并設(shè)為簇，當(dāng)完成一次迭代后也就得到新的聚類質(zhì)心[13]。若在完成第一次迭代的前后，樣本對象 i 的值沒有產(chǎn)生變化，則說明運算已經(jīng)收斂，即：

其中， K 表示類別數(shù)目， （n₁ ， n₂ ，…， n_k） 表示各類的樣本數(shù)目， （m₁ ， m₂ ，…， m_k） 表示聚類的質(zhì)心。

算法過程如下：

1）從 N 個數(shù)據(jù)樣本中任意選取 k 個數(shù)據(jù)樣本對象作為質(zhì)心。

2）對剩下的全部數(shù)據(jù)樣本計算出它們各到每一個質(zhì)心的間距，并添加到最近質(zhì)心的類。

3）重新計算已獲得的各類的質(zhì)心。

4）返回第2）～3）步直到新質(zhì)心與原質(zhì)心相等或者小于自定義的閾值，算法結(jié)束。

針對不同樣本集， K 值的選擇也會有所差異，以下是三種不同樣本的K均值聚類結(jié)果展示：

1）訓(xùn)練樣本數(shù)量 N=100 ， K=2 均值聚類，如圖4所示。聚類質(zhì)心坐標(biāo)為：

，

聚類時間為 T=0.239 144 ，迭代次數(shù)為9。

2）訓(xùn)練樣本數(shù)量 N=200 ， K=4 均值聚類，如圖5所示。聚類質(zhì)心坐標(biāo)為：

M₁=（0.3533，0.4213） ，

，

聚類時間 T=0.345760 ，迭代次數(shù)為6。

3）訓(xùn)練樣本數(shù)量 N=500 分布，選取 K=40 均值聚類中心分布如圖6所示。

圖4 K=2 的K均值聚類

圖5 K=4 時K均值聚類

圖6 N=500 ， K=40 時K均值聚類

圖7K均值聚類的SVM分類

2.2K均值聚類的SVM迭代訓(xùn)練算法

從2.1節(jié)可以采用K均值聚類的聚類質(zhì)心作為初始樣本集有效地提高訓(xùn)練效率。然而，抽取樣本減少訓(xùn)練數(shù)據(jù)集會影響分類器的性能，因為分類邊界是由支持向量控制的，所以應(yīng)該隨時更新訓(xùn)練集，讓所有支持向量集中在訓(xùn)練集中，提高支持向量機的精度。

采用歐式距離來度量向量之間的相似性為：

d²（x_i，x_j）=|x_i-x_j|²i，j=1，…，n

由式（12）函數(shù)去掉符號可以得到分類器的距離函數(shù)為：

兩類分類時，將分類期望響應(yīng)標(biāo)簽設(shè)為 d∈[1，-1] 當(dāng) x_i 在超平面正側(cè)方向面時，由式（17）計算得到大于0的值，乘上此時的期望響應(yīng)1仍然為本身，可以看作離超平面的距離；當(dāng) x_i 在超平面反側(cè)面方向時，由式（20）計算得到小于0的值，乘上此時的期望響應(yīng)-1仍然是正值，仍然可以看作離超平面的距離。

K均值聚類支持向量機的大樣本迭代訓(xùn)練算法如下：

1）選擇聚類數(shù)量 K=n_i/k ， n_i 表示第 i 類的樣本數(shù)量，得到聚類質(zhì)心 M 作為初始訓(xùn)練樣本集。

2）求得分類器函數(shù)。

3）由分類器對全部樣本進(jìn)行計算出超平面的間距，然后比較這些間距，按照準(zhǔn)則獲得邊界樣本和錯分樣本。

4）返回步驟2）和步驟3），當(dāng)錯分樣本穩(wěn)定（或變化很?。r，結(jié)束迭代，輸出結(jié)果。

基于MATLAB軟件采取K均值聚類的支持向量機迭代訓(xùn)練算法分類后的結(jié)果。其初始訓(xùn)練樣本數(shù)量為 N=250 （兩類樣本數(shù)量各250），壓縮比 k=20 如圖7所示。

3 實驗及結(jié)果分析

3.1 模擬數(shù)據(jù)實驗

使用傳統(tǒng)支持向量機迭代訓(xùn)練算法與K均值聚類的SVM迭代訓(xùn)練算法進(jìn)行比較，傳統(tǒng)SVM訓(xùn)練算法運算采用矩陣計算，其計算量通常很大。訓(xùn)練時，所有支持向量機都選取高斯核函數(shù)，參數(shù) σ=0.5 。模擬的兩組數(shù)據(jù)均服從正態(tài)分布：

分布參數(shù)分別是 m₁=[0， 0]^T ， s₁-[2，1]^T ， m₂=[0 5]^T ， s₂-[1， 2]^T 兩個分布各產(chǎn)生250個樣本，利用基于K均值聚類的支持向量機迭代算法訓(xùn)練的模型，其訓(xùn)練效率與傳統(tǒng)支持向量機迭代算法相比，可能會得到顯著提升，如表4所示。

表4傳統(tǒng)訓(xùn)練算法與K均值聚類的SVM選代訓(xùn)練算法比較結(jié)果

其中，壓縮比 K=4 下的K均值聚類的SVM迭代訓(xùn)練算法得到的兩類支持向量（圓圈圈住）與用傳統(tǒng)支持向量機迭代算法直接訓(xùn)練得到的支持向量（圓圈圈?。┍容^如圖8和圖9所示。

圖8K均值聚類的SVM迭代訓(xùn)練算法

圖9傳統(tǒng)支持向量機迭代算法

傳統(tǒng)的SVM訓(xùn)練算法所獲得高斯線為兩類超平面方程， K=4 時用K均值聚類的SVM迭代訓(xùn)練算法有兩條高斯線，其中一條是樣本K均值聚類后的聚類中心 M（m₁ ， m₂ ，…， m_k） 作為其初始訓(xùn)練樣本集所得的分界面；另一條是邊界樣本和錯分樣本加入初始訓(xùn)練集 M 中采用傳統(tǒng)的支持向量機訓(xùn)練所得到的超平面。

從以上兩圖可以著出，此處提出的支持向量機的訓(xùn)練集的重構(gòu)在分類訓(xùn)練精度和傳統(tǒng)支持向量機分類訓(xùn)練精度幾乎一樣，兩圖的支持向量大部分是重合的，說明此算法在減少訓(xùn)練時間的同時保證了支持向量機的訓(xùn)練精度。例如，不難看出當(dāng) K=2 和 K=4 時，在訓(xùn)練時間減少的同時提高了精度，訓(xùn)練速度比傳統(tǒng)算法有所提高。

3.2 拓展實驗

為了實驗的價值性預(yù)測未來某天下雨情況，收集了2012年1月1日到2015年1月16日樣本數(shù)量為N=1 112 的氣候數(shù)據(jù)變化情況，以訓(xùn)練樣本 X 表示當(dāng)天的平均溫度 C 和相對濕度 R ，即 X=（C，R） ， d 表示當(dāng)天是否下雨的期望響應(yīng)，其中第1類 d=1 表示當(dāng)天不下雨樣本數(shù)量為649天，第2類 d=-1 表示當(dāng)天下雨的樣本數(shù)量為463天，兩類的數(shù)據(jù)服均從正態(tài)分布高斯核函數(shù)：

選取核函數(shù)參數(shù) σ=5 。為了易于分析，在下雨天（期望響應(yīng) d=-1 ）時讓濕度值均增加30，‘ +^，，， 表示不下雨即第1類分布，“。”表示下雨即第2類。算法程序在MATLAB軟件上編程后得到的結(jié)果如表5和圖10以及圖11所示。

表5傳統(tǒng)訓(xùn)練算法與K均值聚類的SVM迭代訓(xùn)練算法比較結(jié)果

150（24號 + 不降雨類降雨類○支持向量0 分類超平面00100 O 。 Q O 。8 8 C 。 O票灰 R10 由 00 0 蒸 1 +50 子+++ 華 .田 . 果% 5 10 15 20 25 30 35平均濕度

圖10SVM訓(xùn)練算法

圖11K均值聚類的SVM訓(xùn)練迭代算法

從以上表和圖可以看出，K均值聚類的SVM迭代訓(xùn)練算法與傳統(tǒng)支持向量機訓(xùn)練算法相比，K均值聚類的SVM大樣本迭代訓(xùn)練算法比傳統(tǒng)支持向量機訓(xùn)練算法訓(xùn)練時間減少很多，平均錯分率也降低了。

4結(jié)論

針對大樣本集下支持向量機的迭代訓(xùn)練算法，在大規(guī)模分類訓(xùn)練中迭代訓(xùn)練速度慢的問題，提出了支持向量機的大樣本迭代訓(xùn)練算法。在該算法中，利用K均值類的操縱達(dá)成初始訓(xùn)練樣本的壓縮，通過傳統(tǒng)支持向量機訓(xùn)練算法得到分類器，將全部樣本計算到超平面的距離，并采取通過加入邊界和錯分樣本的策略更新訓(xùn)練樣本集。MATLAB軟件運行嘗試實驗結(jié)果表明，該算法在分類訓(xùn)練精度保持不變的情況下既減少了樣本訓(xùn)練的時間，又提高了分類器分類訓(xùn)練的速度。

參考文獻(xiàn)：

[1]LIJM，ZHANGB，LINFZ.TrainingAlgorithms for

Support Vector Machines [J].Journal of Tsinghua University，

2003，43（1）：120-124.

[2] PLATTJC.Fast Training of Support Vector Machines

Using Sequential Minimal Optimization[C]//Advances in Kernel

Methods-Support Vector Learning.Cambridge：MIT Press，

1999：185-208.

[3]KEERTHISS，SHEVADE SK，BHATTACHARYYA

C，et al.A Fast Iterative Nearest Point Algorithm for Support

Vector Machine Classifier Design [J].IEEE Transactions on Neural

Networks，2000，11（1）：124-136.

[4]安金龍.支持向量機若干問題的研究[D].天津：天津

大學(xué)，2004.

[5] SCHOLKOPFB，MIKA S，BURGES CJC，et al.

Input Space versus Feature Space in Kernel-Based Methods [J].

IEEETransactions on Neural Networks，1999，10（5）：1000-

1017.

[6]王秀菲.基于特征加權(quán)支持向量機的復(fù)合材料粘接缺

陷量化識別研究[D].呼和浩特：內(nèi)蒙古大學(xué)，2011.

[7]李飛，李紅蓮.支持向量機大規(guī)模樣本快速訓(xùn)練算法[J].

北京信息科技大學(xué)學(xué)報：自然科學(xué)版，2012，27（2）：83-87.

[8]劉莉.支持向量機及其在遙感圖像處理中的應(yīng)用 [D].

合肥：中國科學(xué)技術(shù)大學(xué)，2005.

[9]孟媛媛.模糊支持向量機的研究與應(yīng)用[D].濟南：山

東師范大學(xué)，2006.

[10]孔銳.基于核的學(xué)習(xí)方法及其在人臉識別中的應(yīng)用研

究[D].合肥：中國科學(xué)技術(shù)大學(xué)，2004.

[11]田新梅，吳秀清，劉莉.大樣本情況下的一種新的

SVM迭代算法[J].計算機工程，2007（8）：205-207.

[12]郭振凱，宋召青，毛劍琴.基于改進(jìn)的SVMR的混

沌時間序列預(yù)測[J].控制工程，2008（4）：385-388.

[13]DUDARO，HARTPE，STORKDG.Pattern

Classification： 2nd ed[M].New York：John Wileyamp; Sons，

2001.

作者簡介：陳積茂（1995—），男，漢族，海南樂東人，講師，本科，研究方向：數(shù)學(xué)、算法和程序設(shè)計。