4種分類算法參數(shù)選擇及分類特點研究

王正杰,楊偉麗,王 喆,侯玉珊,郭銀景

(山東科技大學電子通信與物理學院,山東 青島 266590)

0 引 言

分類算法是人工智能、模式識別和數(shù)據(jù)挖掘領(lǐng)域中重要的數(shù)據(jù)處理方法，其目的是通過樣本數(shù)據(jù)建立分類模型或函數(shù)，將實體屬性值分類到給定的數(shù)據(jù)類別中，常用的分類算法可以分為參數(shù)化模型和非參數(shù)化模型[1]。當使用參數(shù)化模型時，需要通過訓練數(shù)據(jù)估計參數(shù)，然后對數(shù)據(jù)進行分類操作，典型的包括感知機、邏輯斯諦回歸和線性支持向量機。非參數(shù)化模型無法通過一組固定參數(shù)進行表征，而且參數(shù)數(shù)量也會隨著訓練數(shù)據(jù)增加而遞增，典型的包括決策樹(含隨機森林)、采用核函數(shù)的支持向量機和K近鄰。進行數(shù)據(jù)分類時，數(shù)據(jù)特征空間維數(shù)、數(shù)據(jù)噪聲以及分類算法參數(shù)設(shè)置都會影響分類精度[2]。同時，算法的參數(shù)選擇在實際應用中也有很廣泛的需求[3-4],對算法參數(shù)尋優(yōu)是算法應用的重要基礎(chǔ)[5-6]。本文選擇2類模型中的代表算法，通過建立不同類型數(shù)據(jù)集并設(shè)置不同算法參數(shù)，分析多種算法分類效果，對了解不同算法分類精度及適用數(shù)據(jù)類型具有重要的指導意義。

1 算法基本原理

1.1 KNN

KNN是最近鄰法的推廣，KNN算法通過搜索模式空間，找出待分類樣本的k個鄰近數(shù)據(jù)。具體地說，對未知(待分類)樣本xt分類時，在訓練樣本集中尋找與待分類樣本xt距離最近的k個樣本，若這k個樣本大多數(shù)屬于某一類別，則判定該測試樣本屬于該類[7]。因此，KNN算法的2個重要因素是距離最近的樣本數(shù)k和“距離”度量公式。

假設(shè)有C個類別：w1,w2,…,wc，若k個近鄰樣本中屬于w1,w2,…,wc類的樣本數(shù)分別是k1,k2,…,kc，此時決策規(guī)則為：

則xt∈ωi，即未知樣本被分配到k個近鄰中樣本數(shù)最多的那一類中。

常用的距離度量公式如下[8]：

3)切比雪夫距離：max|xi-yi|(i=1,2,…,n)；

4)閔可夫斯基距離：

其中 s-1為樣本協(xié)方差矩陣的逆矩陣。

1.2 支持向量機

SVM是一種在線性可分條件下求最佳分類超平面基礎(chǔ)上發(fā)展而來的算法，其主要思想是將低維線性不可分問題通過核函數(shù)映射到高維特征空間，變成高維空間線性可分問題，在線性可分條件下求最優(yōu)分類面[9]。

設(shè)訓練樣本x1,x2,…,xn,x∈Rm，訓練樣本所屬類別(分類標簽集)為y∈{+1,-1}，傳遞函數(shù)(分類規(guī)則)定義為：

f(x)=sgn (wTx+b)

將求解最優(yōu)分類面問題表示為如下約束問題[10]：

(1)

st. yi(wTxi+b)≥1 (i=1,2,…,n)

(2)

考慮到存在噪聲引起的離群點，在最優(yōu)化目標中加入懲罰系數(shù)和松弛變量，即增加對應樣本xi允許偏離函數(shù)間隔。約束條件(2)式就變成：

yi(wTxi+b)≥1-ξi, i=1,2,…,n

(3)

優(yōu)化目標式(1)變成：

(4)

其中，C為懲罰因子，ξ為松弛變量，該值可自行設(shè)定。

通過拉格朗日乘子法，引入輔助變量λi，可以得到分類函數(shù)：

其中，xi為第i個樣本向量，x為未知向量，〈xi,x〉表示2向量的內(nèi)積。

從上式可以看出，若選擇不同的內(nèi)積計算方法，則可以得到不同的分類函數(shù)，常使用的核函數(shù)有如下形式[11-12]：

1)高斯核函數(shù)：

K(xi,x)=exp (-‖xi-x‖2/2σ2)

2)多項式核函數(shù)：

K(xi,x)=((xi·x)+1)d， d=1,2,…

3)感知器核函數(shù)：

K(xi,x)=tanh [β(xi,x)+b]

4)高斯徑向基核函數(shù)(RBF)：

K(xi,x)=exp (-γ‖xi-x‖2)

5)線性核函數(shù)：

K(xi,x)=〈xi,x〉

1.3 決策樹——CART算法

決策樹是基于訓練數(shù)據(jù)集的特征，通過一系列的問題來推斷樣本所屬類別的一種方法[13]。CART算法可對特征屬性進行二元分裂，分裂之后得到2個子樣本，則每個內(nèi)部結(jié)點都有2個分支。無論一個屬性有幾個取值，決策樹的每一步?jīng)Q策只能是“是”或“否”，即分支系數(shù)始終為2。

設(shè)x1,x2,…,xn代表單個樣本的n個樣本屬性，y代表所屬類別。CART算法通過多次分裂將n維空間分割成不重疊的矩形。

分裂步驟如下：

1)選取xi，再選取xi的一個值vi,n維空間被vi劃分為2部分。一部分滿足xi≤vi，另一部分都滿足xi≥vi；

2)對1)得到的2部分重新選擇屬性，按照1)繼續(xù)劃分，直到將整個n維空間被劃分完。

為使劃分效果更好，CART采用了一種稱為“節(jié)點不純度”的指標來度量進行二元分裂時的不純度。常用的幾種“不純度”測量函數(shù)是[14-15]：

1)Gini指標(隨機選中的樣本被誤分時的誤差率)。

假設(shè)有C種類別，則節(jié)點s的Gini不純度為：

其中，pi是節(jié)點s中屬于類別i的概率，Gini(s)=0時，所有樣本屬于同類。Gini指數(shù)越大，樣本包含的類別越多。

2)方差不純度：

I(s)=p(w1)p(w2)

該不純度適用于二分類問題。

3)“熵不純度”(Entropy Impurity):

2 主要參數(shù)及作用

2.1 KNN

對于KNN分類模型，需要對近鄰數(shù)k和距離度量公式這2個參數(shù)進行選擇。

1)k值的設(shè)定。值大小會影響KNN模型的復雜度。k值過小會降低分類的精度，增大模型復雜度，但過于復雜或過于簡單的模型的復雜度的測試準確率也比較低；k值過大且測試樣本屬于樣本數(shù)量較少的類，反而會增加數(shù)據(jù)的含噪度，降低分類精度。

2)距離度量的選擇。閔氏距離是常用的距離計算方法，當p=2時為歐氏距離，而馬氏距離由于能夠利用樣本協(xié)方差獲得統(tǒng)計特性，因此在計算樣本距離上有很大的優(yōu)越性，這里選擇這2種距離公式進行分析。

2.2 SVM

對于支持向量機核函數(shù)本文選擇線性核函數(shù)和徑向基核函數(shù)，即Linear SVM和RBF SVM，支持向量機的參數(shù)選擇和比較是該算法的重要研究內(nèi)容[16-17]。這里主要設(shè)定懲罰系數(shù)C和RBF核函數(shù)的系數(shù)γ這2個參數(shù)。

1)懲罰系數(shù)C，即松弛變量的系數(shù)。

主要作用：在優(yōu)化函數(shù)里平衡模型復雜度和訓練錯誤率這兩者之間的關(guān)系，控制著對誤分樣本的懲罰程度。若C取值比較小時，意味放棄離群點，即選擇少量樣本作為支持向量，支持向量和超平面的模型也會變得簡單，訓練誤差較大，導致“欠學習”。該值較大時，對經(jīng)驗誤差的懲罰大，代表保留距離較遠的離群點，即選擇較多樣本作為支持向量，則支持向量與超平面的模型變復雜，使“過擬合”出現(xiàn)的可能性增加。在Scikit-learn中，C默認值是1。

2)RBF核函數(shù)的系數(shù)γ。

RBF核函數(shù)：

k(xi,x)=exp (-γ‖xi-x‖2)

其中γ指某個樣本對整個分類超平面的影響。

γ值的大小代表單個樣本對整個分類超平面的影響程度。當γ比較小時，影響比較大，易被選為支持向量；當γ比較大時，影響比較小，不易被選為支持向量。Scikit-learn中γ的默認值是1/樣本特征數(shù)。

當同時考慮C和γ時，若C比較大且γ比較小，則支持向量較多，模型會比較復雜，容易“過擬合”；若C比較小且γ比較大，則模型簡單，支持向量少。

2.3 決策樹

對于CART算法，需要設(shè)定的主要參數(shù)為決策樹的最大深度及“節(jié)點不純度”指標。決策樹最大深度當數(shù)據(jù)樣本少或者特征屬性比較少的時候該值可被忽略。若模型樣本數(shù)量和特征比較多的情況下，需要限制決策樹的深度，并根據(jù)數(shù)據(jù)的分布決定該取值。常用的可以取值10～100之間?！肮?jié)點不純度”指標使用Gini和Entropy不純度。

3 實驗仿真

本文選用Pycharm編程環(huán)境，使用Scikit-learn模塊進行實驗分析。首先分析不同參數(shù)下分類算法的最優(yōu)參數(shù)，根據(jù)所選最優(yōu)參數(shù)分析不同噪聲下分類算法的分類效果。

3.1 數(shù)據(jù)集

這里選擇2種數(shù)據(jù)集，用make_moons函數(shù)生成的數(shù)據(jù)集1和make_circles函數(shù)生成的數(shù)據(jù)集2。根據(jù)分類的效果，在討論最佳參數(shù)時，采用數(shù)據(jù)集1，在進行更詳細的討論時，使用2組數(shù)據(jù)集。首先使用數(shù)據(jù)集1的3組不同噪聲下的數(shù)據(jù)作為分類算法在不同參數(shù)下的精度數(shù)據(jù)，類別標記個數(shù)為2，加入的數(shù)據(jù)噪聲分別是0.1，0.3和0.5，將100個樣本分為40個訓練樣本和60個測試樣本。

3.2 參數(shù)分析

通過仿真得出分類算法主要參數(shù)下的分類精度結(jié)果見圖1～圖5。

1)對于KNN算法，通過分析圖1得出如下結(jié)論：

①2種距離度量具有相似特性，即當噪音取3種不同值時，分類精度曲線可以大致分成對應3組，這表明噪音對不同距離度量有相似影響。

②當同一噪聲下，選用閔可夫斯基距離得到分類精度較高于馬氏距離得到分類精度。

③選擇同一種度量距離時，數(shù)據(jù)噪聲變大，分類精度降低。

⑤k值過小或過大都會影響分類精度，因此在比較分類算法分類效果時，根據(jù)經(jīng)驗規(guī)則和上述參數(shù)分析結(jié)果，令KNN算法的近鄰值k=6。

圖1 不同噪聲及不同k值下KNN算法精確度

圖2 不同噪聲及最大深度下決策樹分類精確度

圖3 不同系數(shù)RBF核函數(shù)分類精確度(n=0.1)

圖4 不同系數(shù)RBF核函數(shù)分類精確度(n=0.3)

圖5 不同系數(shù)RBF核函數(shù)分類精確度(n=0.5)

2)對于決策樹算法，通過分析圖2得出如下結(jié)論：

①2種不純度指標具有相似特性，隨著深度變化，分類精度有所不同，但分類精度增加或者減少趨勢一致。

②當數(shù)據(jù)噪音為0.1和0.3時，2種指標的4條曲線可以分為一組，定位精度較高；當數(shù)據(jù)噪聲為0.5時，2種指標的曲線可以分為一組，該算法對數(shù)據(jù)分類效果急劇下降，因此該算法處理含有噪聲較大數(shù)據(jù)能力較弱。

③同一種噪聲下，決策樹分類精度隨著最大深度(2～20)增大而變化；當噪聲較小時，分類精度隨著深度增加而增加，當噪聲較大時，分類精度降低。

④對于2種“節(jié)點不純度”指標，數(shù)據(jù)噪聲相同時，選用“Gini”指標時精確度高于選用“Entropy”指標時精確度。

⑤在比較不同分類算法分類效果時，令決策樹節(jié)點度量指標為“Gini”。為使在不同噪聲情況下分類精度都可以取到較高的分類精度，選取最大深度值為6。

3)對圖3～圖5分析，同一種噪聲數(shù)據(jù)下，懲罰系數(shù)C和RBF核函數(shù)系數(shù)改變都對精確度有著不可忽略的影響。RBF系數(shù)γ的取值一般為1/樣本特征數(shù)，因選用樣本特征數(shù)為2，此處γ=0.5。為研究參數(shù)對分類精度的影響，令RBF系數(shù)取值范圍為0.1～1.0。懲罰系數(shù)C取值范圍為0.5～1.5。

對RBF SVM算法，通過分析圖3～圖5得出如下結(jié)論：

①隨著噪聲增大，分類精度逐漸降低。

②當噪聲為0.1時，分類精度隨著γ的增大而增大；當噪音為0.3時，分類精度基本不隨著γ變化而保持穩(wěn)定；當噪聲達到0.5時，分類精度隨著γ的增大而減小。

③當噪音較小時，γ可以適當設(shè)置為較大值；當噪音適中時，γ只要不是較小值即可獲得較好精度；當噪音較大時，γ應該取較小值。

④當γ=0.5±0.2時，不同種噪聲下，都取得良好精度。

⑤當懲罰系數(shù)C較大γ較小時或者C較小γ較大時，分類精度都降低。

對于支持向量機核函數(shù)為線性核函數(shù)時，其主要參數(shù)為懲罰系數(shù)C，這里根據(jù)圖3～圖5的結(jié)果來選擇參數(shù)大小。

表1 各算法重要參數(shù)設(shè)置

主要參數(shù)選擇實驗取值KNN(K近鄰法)k、距離度量公式k=7、閔可夫斯基距離SVM(支持向量機)C核函數(shù)=“l(fā)inear”C=1核函數(shù)=“RBF”系數(shù)γγ=0．6，C=1決策樹最大深度、不純度指標max＿depth=6，Gini

為了區(qū)分不同算法對數(shù)據(jù)邊界分類能力，這里選擇各種算法性能最好參數(shù)來進行各種算法的綜合分析，所選主要參數(shù)見表1。

3.3 分類效果分析

根據(jù)所選參數(shù)，仿真得出算法對2種數(shù)據(jù)集在不同噪聲下分類結(jié)果，如圖6和圖7所示。總體來講，大部分分類算法的分類精確度都隨著噪聲增大而降低。2種數(shù)據(jù)集除了數(shù)據(jù)集2的RBF SVM算法在噪音為0.1時有最好分類效果外，數(shù)據(jù)集1在不同噪音條件下，所有算法都有更好分類精度，這說明通常情況下，不同類型數(shù)據(jù)集在大部分算法上比其它數(shù)據(jù)集會有更好的分類效果，或者說能否有效分類主要由數(shù)據(jù)集本身決定。

圖6 分類算法對make_moons函數(shù)產(chǎn)生數(shù)據(jù)分類結(jié)果

圖7 分類算法對make_circles函數(shù)產(chǎn)生數(shù)據(jù)分類結(jié)果

在數(shù)據(jù)集1條件下，Linear SVM分類精度隨著噪音增加，分類精度反而增加，因為噪音越低，節(jié)點分布越密，更不容易獲得分類平面。其它算法隨著噪音增加分類精度降低，但是不同算法之間變化程度不同，當噪音為0.1和0.3時，3種算法都有95%分類精度，當噪音增加到0.5時，KNN和RBF SVM擁有85%以上分類精度，而決策樹由于只能設(shè)置直線分類邊界導致其精度下降為60%。當噪音較小時，Linear SVM分類精度比其他3種方法都低，當噪音達到0.5時，該方法分類精度反而超過其他3種方法，這表明，不同的算法對噪音的適應能力不同，在給定數(shù)據(jù)集的情況下，若已知噪音程度，可以選擇有效分類方法提高分類精度。在本數(shù)據(jù)集情況下，RBF SVM基本上擁有最好分類能力。

在數(shù)據(jù)集2條件下，Linear SVM分類精度沒有隨著噪音增加而發(fā)生變化，其他3種算法分類精度都隨著噪音增加急劇下降。當噪音較小時，3種算法都有很高分類精度，當噪音增加時，KNN和RBF SVM分類精度從100%降至75%，決策樹降為65%，而KNN在噪音為0.5時，分類精度僅為45%，這表明在給定數(shù)據(jù)集情況下，不同算法分類精度有很大差別。在本數(shù)據(jù)集情況下，RBF SVM擁有最好分類能力。

對于2種數(shù)據(jù)集，KNN和RBF SVM在不同噪音下都有類似的分類精度，這主要由于兩者都使用距離來判斷節(jié)點類別，并且可以形成曲線邊界，因此兩者在所給數(shù)據(jù)集和不同噪音參數(shù)下，分類精度大部分情況下比較接近，都有比較好的分類能力。而線性支持向量機和決策樹都只能采用直線作為分類邊界，當噪聲變大時，分類效果明顯變差，因此，曲線分類邊界明顯比直線邊界擁有更好的分類能力。在數(shù)據(jù)集1的情況下，數(shù)據(jù)有明顯界限，雖然當噪音增加時，邊界不太清晰，但是3種算法除了決策樹，都能達到85%準確率。在數(shù)據(jù)集2情況下，數(shù)據(jù)點沒有線性邊界，因此，當噪音增加至0.5時，數(shù)據(jù)點之間邊界已經(jīng)非常模糊，除了RBF SVM可以繪制任意曲線邊界的分類方法能達到65%分類精度，其他分類方法分類精度已經(jīng)降至50%及以下?？傮w上來說，基于RBF SVM在各種條件下，擁有較好的分類精度。

3.4 分類精度及時間消耗分析

計算時間運行環(huán)境為：Windows10專業(yè)版64位、Intel i5-6500CPU(3.2 GHz)、8 G DDR4內(nèi)存、固態(tài)硬盤。本文以n=0.3為例，分析當節(jié)點數(shù)為100、1000、5000、1萬和10萬時的分類精度和運行50次的平均時間消耗對算法性能做分析。因為當節(jié)點數(shù)少于1000時，分類算法在時間上沒有明顯的區(qū)別，這里以節(jié)點數(shù)為1000的運行時間作為基準，如表2所示進行分析。

從表2可以看出，KNN所需時間最少，決策樹次之，支持向量機花費時間最多。從圖8和圖9可以看出，2種數(shù)據(jù)集都表現(xiàn)出如下相同的規(guī)律，當節(jié)點數(shù)在1萬以內(nèi)，單位節(jié)點消耗時間迅速增加，當節(jié)點數(shù)量繼續(xù)變多時，消耗時間減少。線性支持向量機在各個節(jié)點數(shù)量條件下，都消耗最多時間，特別是在數(shù)據(jù)集2的條件下，實際上數(shù)據(jù)已經(jīng)線性不可分。在各種節(jié)點數(shù)情況下，K近鄰一直消耗最少時間，決策樹次之，支持向量機花費的時間最久，采用RBF的SVM需要運算核函數(shù)，花費時間更多，而線性支持向量機由于數(shù)據(jù)線性不可分，耗費時間最久。

表2 1000個節(jié)點時不同算法的運行時間 /ms

KNNLinearSVMRBFSVMDecisionTree數(shù)據(jù)集154022863429802數(shù)據(jù)集253146775375801

圖8 數(shù)據(jù)集1不同點數(shù)所花費時間比

圖9 數(shù)據(jù)集2不同點數(shù)所花費時間比

下面分析不同節(jié)點數(shù)在各種算法下分類精度，圖10展示了在數(shù)據(jù)集1時的分類精度，從圖中可以看出，分類精度差別不是很大，其中以線性支持向量機精度最低。

圖10 數(shù)據(jù)集1不同點數(shù)分類精度比較

圖11展示了在數(shù)據(jù)集2時分類精度，對于此類數(shù)據(jù)集，線性支持向量機分類效果明顯很差，大部分情況下分類精度小于0.5。從圖10和圖11可以知道，節(jié)點數(shù)量對分類算法的影響比較小，數(shù)據(jù)集的結(jié)構(gòu)對算法的分類精度有較大影響。

圖11 數(shù)據(jù)集2不同點數(shù)分類精度比較

4 結(jié)束語

本文分析4種基本分類算法參數(shù)作用，通過設(shè)置其主要參數(shù)，比較算法參數(shù)和節(jié)點數(shù)量對算法精度影響。通過設(shè)置最佳參數(shù)和使用生成數(shù)據(jù)集，分析不同噪音參數(shù)時分類算法的分類精度及運行所需時間，討論算法分類結(jié)果的基本特點。通過仿真實驗表明：對于二維數(shù)據(jù)的處理，KNN在這4種分類算法上擁有最好分類能力并且消耗了最少的運行時間。根據(jù)工作原理推斷在高維數(shù)據(jù)大量數(shù)據(jù)情況下，KNN和RBF SVM應該具有很好的分類能力，為處理高維數(shù)據(jù)提供了可靠的依據(jù)。

[1] 塞巴斯蒂安·拉施卡. Python機器學習[M]. 北京:機械工業(yè)出版社, 2017:55-56.

[2] 宋暉,薛云,張良均. 基于SVM分類問題的核函數(shù)選擇仿真研究[J]. 計算機與現(xiàn)代化, 2011(8):133-136.

[3] 肖永良,朱韶平,劉文彬,等. 基于優(yōu)化支持向量機的高校教師績效評價研究[J]. 赤峰學院學報(自然科學版), 2014(24):25-27.

[4] 尚丹. 基于參數(shù)優(yōu)化的SVM分類器在肺癌早期診斷中的應用[D]. 鄭州:鄭州大學, 2014.

[5] 崔君榮,苑薇薇. 利用智能算法優(yōu)化支持向量機參數(shù)[J]. 河北科技師范學院學報, 2017,31(1):34-38.

[6] 徐曉明. SVM參數(shù)尋優(yōu)及其在分類中的應用[D]. 大連:大連海事大學, 2014.

[7] Hastie T, Tibshirani R, Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction[M]. 2nd ed. Springer New York, 2009:463-468.

[8] 曾勇. 廣義近鄰模式分類研究[D]. 上海:上海交通大學, 2009.

[9] Boyd S, Vandenberghe L. 凸優(yōu)化[M]. 王書寧,許鋆,黃曉霖譯. 北京:清華大學出版社， 2013:42-46.

[10] 周志華. 機器學習[M]. 北京:清華大學出版社, 2016:123-124．

[11] 奉國和. SVM分類核函數(shù)及參數(shù)選擇比較[J]. 計算機工程與應用, 2011,47(3):123-124.

[12] 梁禮明,鐘震,陳召陽. 支持向量機核函數(shù)選擇研究與仿真[J]． 計算機工程與科學, 2015,37(6):1135-1141．

[13] 陳輝林,夏道勛. 基于CART決策樹數(shù)據(jù)挖掘算法的應用研究[J]. 煤炭技術(shù), 2011,30(10):164-166.

[14] 齊樂,岳彩榮. 基于CART決策樹方法的遙感影像分類[J]. 林業(yè)調(diào)查規(guī)劃, 2011,36(2):62-66.

[15] 張亮,寧芊. CART決策樹的兩種改進及應用[J]. 計算機工程與設(shè)計, 2015(5):1209-1213.

[16] 馮新剛． 支持向量機核函數(shù)選擇方法探討[D]. 贛州:江西理工大學, 2012．

[17] 魏峻． 一種有效的支持向量機參數(shù)優(yōu)化算法[J]. 計算機技術(shù)與發(fā)展, 2015,25(12):97-100．