中圖分類號：TP301.6 文獻標識碼：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 引言

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

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

1 支持向量機

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

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

w^Tx+b=0

其中 x 表示輸入向量， w 表示可調權向量， b 表示偏置。于是相應的線性分類判別可表述為：

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

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

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

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

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

問題：給定訓練集 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）可知，樣本線性可分時總是可以重新調整參數(shù) w₀ 和 b₀ 得到式（3）。

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

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

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

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

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

基本特征如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

約束條件為：

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

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

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

1.4支持向量案例分析

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

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

表1初始訓練樣本的獲取

1.4.2 支持向量

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

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

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

1.4.3 超平面

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

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

于是得到：

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

1. 4.4 試驗解析

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

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

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

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

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

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

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

a=（0.0039-0.517013.2119）

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

表3訓練樣本與訓練時間的關系

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

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

2.1 K均值聚類

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

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

算法過程如下：

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

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

3）重新計算已獲得的各類的質心。

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

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

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

，

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

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

M₁=（0.3533，0.4213） ，

，

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

3）訓練樣本數(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迭代訓練算法

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

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

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

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

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

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

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

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

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

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

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

3 實驗及結果分析

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

使用傳統(tǒng)支持向量機迭代訓練算法與K均值聚類的SVM迭代訓練算法進行比較，傳統(tǒng)SVM訓練算法運算采用矩陣計算，其計算量通常很大。訓練時，所有支持向量機都選取高斯核函數(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均值聚類的支持向量機迭代算法訓練的模型，其訓練效率與傳統(tǒng)支持向量機迭代算法相比，可能會得到顯著提升，如表4所示。

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

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

圖8K均值聚類的SVM迭代訓練算法

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

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

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

3.2 拓展實驗

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

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

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

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

圖10SVM訓練算法

圖11K均值聚類的SVM訓練迭代算法

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

4結論

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

參考文獻：

[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].天津：天津

大學，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]王秀菲.基于特征加權支持向量機的復合材料粘接缺

陷量化識別研究[D].呼和浩特：內蒙古大學，2011.

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

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

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

合肥：中國科學技術大學，2005.

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

東師范大學，2006.

[10]孔銳.基于核的學習方法及其在人臉識別中的應用研

究[D].合肥：中國科學技術大學，2004.

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

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

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

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

[13]DUDARO，HARTPE，STORKDG.Pattern

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

2001.

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