一種基于SVM的主動(dòng)多分類(lèi)方法

郭金玲

（山西大學(xué)商務(wù)學(xué)院 信息學(xué)院，山西 太原 030031）

0 引言

支撐向量機(jī)是一種以結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理為準(zhǔn)則的有效的機(jī)器學(xué)習(xí)方法，在數(shù)據(jù)分類(lèi)、預(yù)測(cè)等研究領(lǐng)域應(yīng)用較為廣泛[1-5]。近年來(lái)，伴隨大數(shù)據(jù)技術(shù)的發(fā)展，針對(duì)大規(guī)模數(shù)據(jù)的多分類(lèi)模型的建立成為數(shù)據(jù)挖掘技術(shù)的研究熱點(diǎn)[6-10]。許多學(xué)者在對(duì)SVM技術(shù)進(jìn)行深入研究后，提出了多種基于SVM的多分類(lèi)模型，如一對(duì)一、一對(duì)多、決策樹(shù)、有向無(wú)環(huán)圖等多分類(lèi)算法[11-15]。

“一對(duì)一”多分類(lèi)算法的主要思路是在每?jī)深?lèi)樣本之間構(gòu)造一個(gè)二分類(lèi)器，如果有k類(lèi)樣本，二分類(lèi)器的個(gè)數(shù)將達(dá)到，該方法構(gòu)造的分類(lèi)器個(gè)數(shù)過(guò)多，存在分類(lèi)器個(gè)數(shù)過(guò)多導(dǎo)致不可分區(qū)域出現(xiàn)的弊端?！耙粚?duì)多”多分類(lèi)算法的主要思路是鎖定某一類(lèi)數(shù)據(jù)，其余類(lèi)別的數(shù)據(jù)都?xì)w為另一類(lèi)，在兩者之間構(gòu)造一個(gè)分類(lèi)器，如果有k類(lèi)樣本，二分類(lèi)器的個(gè)數(shù)為k，該方法構(gòu)造的二分類(lèi)器個(gè)數(shù)較少，但是在訓(xùn)練分類(lèi)器的過(guò)程中，需要所有的訓(xùn)練樣本參與計(jì)算，計(jì)算量過(guò)大，訓(xùn)練時(shí)間過(guò)長(zhǎng)?！皼Q策樹(shù)”多分類(lèi)算法通過(guò)計(jì)算數(shù)據(jù)類(lèi)別的信息熵增益，首先分離出類(lèi)別屬性最易區(qū)分的數(shù)據(jù)，以此類(lèi)推，從而構(gòu)造出多分類(lèi)模型，由于每次分類(lèi)都需要計(jì)算信息熵增益，導(dǎo)致該模型的計(jì)算量過(guò)大?！坝邢驘o(wú)環(huán)圖”算法結(jié)合圖論和“一對(duì)一”算法的解決思路，將若干個(gè)二分類(lèi)器組合得到多分類(lèi)器，其缺點(diǎn)是分類(lèi)效果過(guò)度依賴(lài)于有向無(wú)環(huán)圖中有向節(jié)點(diǎn)的排列順序，算法過(guò)于冗余?？傮w來(lái)看，目前提出的比較成熟的多分類(lèi)模型可以解決數(shù)據(jù)挖掘中的多分類(lèi)問(wèn)題，但存在計(jì)算量大、訓(xùn)練時(shí)間長(zhǎng)、泛化性較低等問(wèn)題[16-19]。

針對(duì)傳統(tǒng)的多分類(lèi)模型構(gòu)造過(guò)程存在的上述問(wèn)題，本文提出一種基于SVM的主動(dòng)多分類(lèi)方法，該方法基于“一對(duì)多”SVM多分類(lèi)算法思路，通過(guò)引入就緒分類(lèi)器和阻塞分類(lèi)器的概念，將主動(dòng)學(xué)習(xí)的策略用于SVM多分類(lèi)器的構(gòu)造過(guò)程，不再是所有樣本參與訓(xùn)練，按照一定的規(guī)則，每次選取最有價(jià)值的樣本訓(xùn)練分類(lèi)器，實(shí)現(xiàn)高效、準(zhǔn)確構(gòu)造分類(lèi)器的過(guò)程，從而可降低計(jì)算復(fù)雜度，有效提高多分類(lèi)器的泛化性。

1 基于SVM的主動(dòng)多分類(lèi)方法

本文采用“一對(duì)多”的思想構(gòu)造SVM多分類(lèi)模型，假設(shè)訓(xùn)練數(shù)據(jù)集包含l個(gè)樣本、c個(gè)類(lèi)別，表示為其中，xi∈Rd，Y為類(lèi)別標(biāo)簽且yi∈{1，2，···，c}，通過(guò)“一對(duì)多”多分類(lèi)方法得到的多分類(lèi)器集合包含c個(gè)二類(lèi)分類(lèi)器，表示為F={f1，f2，···，fc}。

1.1 就緒分類(lèi)器與阻塞分類(lèi)器

假設(shè)第i類(lèi)樣本與其他類(lèi)樣本之間構(gòu)造的分類(lèi)器表示為fi，訓(xùn)練樣本集X中的任意樣本xj(j=1，···，l）與分類(lèi)器fi之間的距離表示為|fi(xj)|。

就緒分類(lèi)器fi是指對(duì)于訓(xùn)練數(shù)據(jù)集存在樣本xj位于fi的分類(lèi)間隔內(nèi)，即|fi(xj)|＜1成立；阻塞分類(lèi)器fi是指訓(xùn)練數(shù)據(jù)集中所有的樣本位于fi的分類(lèi)間隔外，即對(duì)于任意樣本xj，均為|fi(xj)|≥1。

根據(jù)SVM分類(lèi)器構(gòu)造原理分析，可以得到以下結(jié)論：

（1）如果分類(lèi)器fi處于阻塞狀態(tài)，即所有訓(xùn)練樣本位于fi的分類(lèi)間隔外，則這個(gè)超平面進(jìn)行硬間隔的主動(dòng)學(xué)習(xí)沒(méi)有意義。

（2）如果分類(lèi)器fi處于就緒狀態(tài)，采用SVM分類(lèi)算法進(jìn)行訓(xùn)練，一定可以獲得更新的分類(lèi)器集合。

（3）如果存在多個(gè)就緒狀態(tài)的分類(lèi)器f1、f2、…，即存在多個(gè)|fi(xj)|＜1，選擇和分類(lèi)超平面距離最小的|fi(xj)|min對(duì)應(yīng)的樣本xj，xj將被選為最有價(jià)值的樣本投入本輪主動(dòng)分類(lèi)模型的訓(xùn)練中。

以上結(jié)論應(yīng)用于基于SVM的主動(dòng)多分類(lèi)模型構(gòu)造過(guò)程中，每次訓(xùn)練只選取處于就緒狀態(tài)的分類(lèi)器，可有效減少每輪需要訓(xùn)練的分類(lèi)器數(shù)目。另外，結(jié)論（3）為如何選取最有價(jià)值樣本提供了選取策略，保證了主動(dòng)多分類(lèi)器高效、準(zhǔn)確地進(jìn)行更新和構(gòu)造。

1.2 基于SVM的主動(dòng)多分類(lèi)算法

基于SVM的主動(dòng)多分類(lèi)算法首先采用k-均值聚類(lèi)方法，以各個(gè)類(lèi)的中心樣本訓(xùn)練得到初始分類(lèi)器集合，并劃分為就緒分類(lèi)器集合與阻塞分類(lèi)器集合；然后選擇最有價(jià)值的樣本對(duì)就緒分類(lèi)器進(jìn)行訓(xùn)練；訓(xùn)練過(guò)程中，由于訓(xùn)練樣本的不斷加入，就緒分類(lèi)器集合與阻塞分類(lèi)器集合不斷更新，該過(guò)程迭代進(jìn)行，直到所有分類(lèi)器停止更新。該主動(dòng)多分類(lèi)方法一方面減少了需要訓(xùn)練的分類(lèi)器的數(shù)量；另一方面可有效選取最有價(jià)值的樣本，從分類(lèi)器和樣本數(shù)量?jī)煞矫孢M(jìn)行了優(yōu)化，降低了分類(lèi)模型構(gòu)造的復(fù)雜度，提高了分類(lèi)器的效率。

假設(shè)測(cè)試數(shù)據(jù)集包含t個(gè)樣本，表示為基于SVM的主動(dòng)多分類(lèi)算法主要包含以下步驟：

Step 1： 對(duì)訓(xùn)練數(shù)據(jù)集采用k-均值聚類(lèi)方法，以各個(gè)類(lèi)的中心樣本訓(xùn)練得到初始分類(lèi)器集合F0。

Step 2： 根據(jù)就緒分類(lèi)器與阻塞分類(lèi)器的劃分規(guī)則，將初始分類(lèi)器集合F0分為就緒分類(lèi)器集合F0-m與阻塞分類(lèi)器集合F0-n。

Step 3： 選擇就緒分類(lèi)器集合F0-m中距離每個(gè)分類(lèi)器間隔超平面最近的樣本，并計(jì)算出各個(gè)距離值|fi(xj)|，選擇|fi(xj)|min對(duì)應(yīng)的樣本xj參與本輪分類(lèi)模型的訓(xùn)練。

Step 4： 動(dòng)態(tài)更新就緒分類(lèi)器集合F0-m與阻塞分類(lèi)器集合F0-n，采用測(cè)試數(shù)據(jù)集TE測(cè)試分類(lèi)器精度。

Step 5： 循環(huán)執(zhí)行步驟3-步驟4，直到分類(lèi)器集合F停止更新，基于SVM的主動(dòng)多分類(lèi)模型構(gòu)造完成，算法結(jié)束。

K-均值聚類(lèi)方法的初始化方式包括三種：（1）將訓(xùn)練樣本隨機(jī)劃分為k個(gè)部分；（2）隨機(jī)選擇與訓(xùn)練樣本一致的樣本空間中的三個(gè)點(diǎn)作為初始聚類(lèi)中心；（3）從訓(xùn)練樣本中隨機(jī)選擇k個(gè)樣本作為初始聚類(lèi)中心。本文采用第三種方式進(jìn)行選擇。

雖然初始聚類(lèi)中心的選取對(duì)聚類(lèi)結(jié)果的影響不大，但對(duì)于聚類(lèi)的收斂速度有較大影響。本文首先從訓(xùn)練樣本中隨機(jī)選擇一個(gè)樣本點(diǎn)作為初始聚類(lèi)中心的第一個(gè)樣本，然后選擇距離該樣本點(diǎn)最遠(yuǎn)的樣本作為第二個(gè)樣本點(diǎn)，之后再選擇聚類(lèi)這兩個(gè)樣本平均距離最遠(yuǎn)的樣本作為第三個(gè)樣本點(diǎn)，如此循環(huán)往復(fù)，直到選擇的樣本點(diǎn)數(shù)達(dá)到k個(gè)，由于采用該種方法選擇的聚類(lèi)中心距離相差較大，而K均值聚類(lèi)的目標(biāo)就是將相似度較大的樣本聚為一類(lèi)，把不相似的樣本通過(guò)聚類(lèi)過(guò)程分離，因此，此種初始化方式可以使得算法快速收斂。

本文提出的主動(dòng)多分類(lèi)方法首先采用K-均值聚類(lèi)，其復(fù)雜度為O(kdl)，其中l(wèi)為樣本規(guī)模，k為聚類(lèi)個(gè)數(shù)，d為迭代次數(shù)，且k＜＜l和d＜＜l成立。在此基礎(chǔ)上，采用聚類(lèi)中心得到初始分類(lèi)器，并反復(fù)選擇就緒分類(lèi)器中距離分類(lèi)面最近的樣本加入訓(xùn)練，并進(jìn)行超平面的更新，直到算法收斂。假設(shè)分類(lèi)器更新次數(shù)為n，結(jié)合SVM訓(xùn)練的時(shí)間復(fù)雜度可知，更新過(guò)程的時(shí)間復(fù)雜度為O(k3n)，由于在分類(lèi)器更新過(guò)程中，選擇距離就緒分類(lèi)器最近的樣本進(jìn)行超平面更新，可使得超平面快速收斂，因此分類(lèi)器更新次數(shù)為n很小。反之，如果直接用標(biāo)準(zhǔn)SVM進(jìn)行主動(dòng)學(xué)習(xí)的話，一方面需要的專(zhuān)家標(biāo)記代價(jià)很大，因?yàn)樗袇⑴c訓(xùn)練的樣本都需要進(jìn)行專(zhuān)家標(biāo)記；另一方面，其時(shí)間復(fù)雜度為O(l3)，由于n＜＜l，因此本文提出的基于SVM的主動(dòng)多分類(lèi)方法具有較低的時(shí)間復(fù)雜度，可有效提高具有少量標(biāo)記的弱監(jiān)督多分類(lèi)問(wèn)題的學(xué)習(xí)效率。

2 實(shí)驗(yàn)結(jié)果與分析

為了測(cè)試基于SVM的主動(dòng)多分類(lèi)算法的性能，驗(yàn)證其有效性，基于UCI標(biāo)準(zhǔn)數(shù)據(jù)集，采用文中方法和一對(duì)一多分類(lèi)方法、一對(duì)多多分類(lèi)方法、決策樹(shù)多分類(lèi)方法、有向無(wú)環(huán)圖多分類(lèi)方法四種多分類(lèi)方法進(jìn)行了實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)采用SVM作為基準(zhǔn)分類(lèi)器，核函數(shù)選擇高斯核，核函數(shù)參數(shù)σ取1.0。

2.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)采用的數(shù)據(jù)集包括UCI數(shù)據(jù)庫(kù)中的Balance_scale、Glass、Iris等7個(gè)數(shù)據(jù)集，這些數(shù)據(jù)集均為多類(lèi)別數(shù)據(jù)集，且包括訓(xùn)練集和測(cè)試集兩部分，數(shù)據(jù)集的基本信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息表Table 1 Datasets for the experiments

為了避免特征分量量綱不同對(duì)分類(lèi)實(shí)驗(yàn)造成的影響，首先對(duì)數(shù)據(jù)集進(jìn)行歸一化處理[20]，計(jì)算過(guò)程如下：

2.2 測(cè)試結(jié)果與分析

采用文中方法和一對(duì)一、一對(duì)多、決策樹(shù)、有向無(wú)環(huán)圖四種多分類(lèi)方法，分別對(duì)UCI數(shù)據(jù)庫(kù)中7個(gè)數(shù)據(jù)集進(jìn)行了分類(lèi)對(duì)比實(shí)驗(yàn)，表2記錄了不同方法在各個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)的分類(lèi)精度，其中，帶下劃線的值代表了文中方法的分類(lèi)精度高于其余方法的情況，從表2可以看出，文中方法在Balance_scale、Glass、Wine、Vehicle、Iris 5 個(gè)實(shí)驗(yàn)數(shù)據(jù)集上的測(cè)試精度都高于其他方法，在Page_block、Segment兩個(gè)數(shù)據(jù)集上和其余方法的測(cè)試精度比較接近，區(qū)分度不大。文中提出的主動(dòng)多分類(lèi)方法主要通過(guò)歐式距離的計(jì)算來(lái)獲取最佳訓(xùn)練樣本，考慮到樣本分布的復(fù)雜性，Page_block、Segment兩個(gè)數(shù)據(jù)集采用文中方法進(jìn)行分類(lèi)，沒(méi)有明顯提高分類(lèi)精度。

表2 不同方法的分類(lèi)結(jié)果比較（%）Table 2 Comparison among testing results（%）

實(shí)驗(yàn)時(shí)間是衡量分類(lèi)算法優(yōu)劣的一個(gè)重要指標(biāo)，表3給出了不同方法在各個(gè)數(shù)據(jù)集上的訓(xùn)練時(shí)間對(duì)比。從表3可以看出，在不同數(shù)據(jù)集的分類(lèi)實(shí)驗(yàn)過(guò)程中，文中提出的方法較其余方法實(shí)驗(yàn)時(shí)間較短，有效提高了分類(lèi)器訓(xùn)練的速度。

表3 不同方法的訓(xùn)練時(shí)間對(duì)比（s）Table 3 Comparison among training time（s）

綜合以上實(shí)驗(yàn)結(jié)果，結(jié)合表2和表3記錄的實(shí)驗(yàn)數(shù)據(jù)分析，本文提出的基于SVM的主動(dòng)多分類(lèi)方法，從分類(lèi)器數(shù)量和訓(xùn)練樣本兩方面進(jìn)行優(yōu)化，通過(guò)動(dòng)態(tài)控制分類(lèi)器的有效參與，選取最有價(jià)值的樣本參與訓(xùn)練，從而提高了分類(lèi)器的精度，降低了訓(xùn)練的時(shí)間，提高了學(xué)習(xí)效率。

3 結(jié)論

針對(duì)傳統(tǒng)的多分類(lèi)模型構(gòu)造過(guò)程存在的計(jì)算量大、效率低等問(wèn)題，本文提出一種基于SVM的主動(dòng)多分類(lèi)方法，該方法基于“一對(duì)多”SVM多分類(lèi)算法思路，通過(guò)引入就緒分類(lèi)器和阻塞分類(lèi)器的概念，將主動(dòng)學(xué)習(xí)的策略用于SVM多分類(lèi)器的構(gòu)造過(guò)程，從分類(lèi)器數(shù)量和訓(xùn)練樣本兩方面進(jìn)行優(yōu)化，降低了計(jì)算復(fù)雜度，有效提高了多分類(lèi)器的泛化性?？紤]到大數(shù)據(jù)領(lǐng)域數(shù)據(jù)集分布的多樣性、復(fù)雜性，如何結(jié)合不同數(shù)據(jù)集的特征選取最有價(jià)值的訓(xùn)練樣本，并設(shè)計(jì)對(duì)應(yīng)的算法，值得進(jìn)一步的探討與研究。