多分類支持向量方法的本科招生生源質(zhì)量模型

邢 濤，廖 冉

(1.北京航空航天大學(xué)經(jīng)濟(jì)管理學(xué)院，北京100191，xt@buaa.edu.cn; 2.北京航空航天大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，北京100191)

近年來(lái)，高等教育已從“精英教育”快速向“大眾化教育”轉(zhuǎn)變，高校招生規(guī)模逐年擴(kuò)大，使得高校在生源上競(jìng)爭(zhēng)日趨激烈.怎樣從全國(guó)的高考生中錄取更多的優(yōu)質(zhì)生源，成為各高校招生工作者的一大難題.各高校招生工作部門一直在積極探索一套科學(xué)、有效、完善的招生管理和評(píng)價(jià)體系［1］.在現(xiàn)行招生制度下，高考成績(jī)?nèi)匀皇墙^對(duì)性指標(biāo).隨著高校招生改革的推進(jìn)，高考自行命題省份不斷增加，高考也從最初的全國(guó)統(tǒng)一標(biāo)準(zhǔn)變得更具區(qū)域性特色.因此，如何在兼顧教育公平的原則下，合理安排招生計(jì)劃，從而在全國(guó)眾多的報(bào)考學(xué)生中科學(xué)、公正、高效地挑選出有發(fā)展?jié)摿Φ膬?yōu)秀學(xué)生是提高生源質(zhì)量的關(guān)鍵問(wèn)題.以往的高校本科招生生源分析，并未充分挖掘高校歷年已錄取的學(xué)生信息.教育的發(fā)展具有持續(xù)性，一個(gè)地區(qū)以往的生源質(zhì)量往往能夠反映出該地區(qū)的教育水平，從而指導(dǎo)今后的招生工作，而高校本身?yè)碛械凝嫶蟮膶W(xué)生信息資源也恰好利于這一方法的實(shí)施.

統(tǒng)計(jì)學(xué)習(xí)理論是專門研究有限樣本情形下的機(jī)器學(xué)習(xí)規(guī)律的理論，在這一理論基礎(chǔ)上發(fā)展出了一種通用學(xué)習(xí)算法，相比起傳統(tǒng)統(tǒng)計(jì)方法所采用的經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原理，支持向量機(jī)算法采用了結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論并體現(xiàn)出了優(yōu)于傳統(tǒng)統(tǒng)計(jì)方法的一些性能［2］.多分類支持向量機(jī)算法是傳統(tǒng)支持向量機(jī)算法的推廣，該算法不僅繼承了支持向量機(jī)算法穩(wěn)健且計(jì)算精確等特點(diǎn)，而且克服了傳統(tǒng)支持向量機(jī)算法只能解決二分類問(wèn)題的局限.

本文利用多分類支持向量機(jī)算法，根據(jù)各地區(qū)學(xué)生在大學(xué)期間的學(xué)習(xí)成績(jī)，與學(xué)生入學(xué)前的信息特點(diǎn)，探討本科生源質(zhì)量預(yù)測(cè)體系，建立本科生源質(zhì)量分析模型，為高校制定招生計(jì)劃、提高生源質(zhì)量提供有效的參考信息.該模型可以對(duì)高校的招生工作給出初步的參考.

1 支持向量機(jī)

支持向量機(jī)算法是建立在統(tǒng)計(jì)學(xué)習(xí)理論的結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)上的，能較好地解決小樣本問(wèn)題，同時(shí)具有很好的泛化能力.算法由Vapnik等［3］在1995年左右提出.近些年來(lái)，該算法在實(shí)際應(yīng)用及理論推導(dǎo)中都有著長(zhǎng)足的進(jìn)步.韓媚和郭丹鳳［4］將支持向量機(jī)方法應(yīng)用到了高校就業(yè)情況的分析中.向小東和宋芳［5］利用基于核主成分分析的支持向量機(jī)算法對(duì)福建省的失業(yè)率進(jìn)行了有效的預(yù)測(cè)和分析.相比其他傳統(tǒng)的統(tǒng)計(jì)學(xué)分類方法或是帶有學(xué)習(xí)過(guò)程的人工智能算法，如神經(jīng)網(wǎng)絡(luò)方法，支持向量機(jī)算法能夠克服過(guò)學(xué)習(xí)問(wèn)題和維數(shù)災(zāi)難問(wèn)題，具有全局最優(yōu)的特點(diǎn)和很好的泛化能力［3］.該算法主要有以下兩個(gè)特點(diǎn)［6］:

(1)采用結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，所得到的學(xué)習(xí)機(jī)器有著很好的泛化能力，即由有限的訓(xùn)練樣本得到的小誤差能夠保證對(duì)獨(dú)立的測(cè)試集仍保持小的誤差.

(2)支持向量機(jī)算法最終將轉(zhuǎn)化為一個(gè)凸優(yōu)化問(wèn)題，局部最優(yōu)解一定是全局最優(yōu)解.

支持向量機(jī)算法的基本思想是在樣本空間或者特征空間，構(gòu)造出最優(yōu)超平面，盡可能將不同類的數(shù)據(jù)點(diǎn)分開，并使得超平面與不同類數(shù)據(jù)點(diǎn)之間的距離最大，從而達(dá)到最大的泛化能力.在線性可分情況下，如圖1所示，圓圈和方塊分別代表兩類樣本點(diǎn)，每類中處在邊界的點(diǎn)為支持向量，這些支持向量所形成的超平面H1和H2為能撐起不同類別樣本點(diǎn)的分類超平面，其之間的間隔為類與類之間的最大間隔，因此最佳的分類面H0介于這兩個(gè)分類超平面之間.

圖1 線性可分下的支持向量機(jī)模型

假設(shè)樣本集合為S={(xi，yi)∈Rn×{±1}，i=1，…，m}，其中x為輸入樣本，y為輸出樣本.用x∈A，y=1表示一類點(diǎn)，x∈B，y=-1表示另外一類點(diǎn).算法的目標(biāo)是利用訓(xùn)練樣本提供的信息來(lái)估計(jì)一個(gè)分類器，即函數(shù)f:Rn→{±1}.如果訓(xùn)練樣本是線性可分的，那么必然存在(w，b)∈Rn×R使得wTx+b=0為其線性邊界，且滿足wTx+b≥1(x∈A)和wTx+b≤-1(x∈B).該限制條件可被表示為:yi［(wT·xi)+b-1］≥0，得到?jīng)Q策函數(shù):fw，b(x)=sign(wTx+b)，其中w為權(quán)重向量，b為偏離值.最終該問(wèn)題可以轉(zhuǎn)化成為求解如下二次優(yōu)化問(wèn)題:

然而，在實(shí)際問(wèn)題中常常遇到線性不可分的情形，支持向量機(jī)算法的優(yōu)勢(shì)也體現(xiàn)在其能處理非線性復(fù)雜系統(tǒng)中的問(wèn)題，它能通過(guò)非線性變換將該非線性問(wèn)題轉(zhuǎn)化成為某個(gè)高維空間中的線性問(wèn)題，在高維空間中求取最優(yōu)分類面實(shí)現(xiàn)線性分類.這種非線性變換是通過(guò)定義適當(dāng)?shù)暮撕瘮?shù)實(shí)現(xiàn)的，在本文中特別應(yīng)用到了希爾伯特再生核空間HK

［7］中的兩種常用的核函數(shù)，其定義如下:

高斯核函數(shù):

多項(xiàng)式核函數(shù):

2 多分類支持向量機(jī)

支持向量機(jī)的產(chǎn)生最初是為了解決二分類問(wèn)題，但在實(shí)際應(yīng)用中，往往要求算法可以對(duì)多于兩類的分類問(wèn)題給出準(zhǔn)確的判斷.因此，隨著實(shí)際應(yīng)用的廣泛要求和理論研究的深入，多分類支持向量機(jī)算法就此產(chǎn)生.

多分類支持向量機(jī)算法在很多領(lǐng)域中都有著廣泛的應(yīng)用，Yoonkyung Lee等［8］應(yīng)用多分類支持向量方法對(duì)基因表達(dá)譜數(shù)據(jù)和衛(wèi)星放射數(shù)據(jù)進(jìn)行了分析.Dirong Chen等［9］對(duì)多分類支持向量機(jī)算法的收斂性給出了理論分析.竇智宙等［10］應(yīng)用該方法對(duì)彩色癌癥細(xì)胞的圖像進(jìn)行了分割.康文雄等［11］應(yīng)用小波分解和多分類支持向量機(jī)算法處理了臉譜識(shí)別問(wèn)題.

2.1 多分類問(wèn)題及貝葉斯決策

在多分類問(wèn)題中，考慮如下樣本(xi，yi)，i= 1，…，m.，其中，xi∈Rd為輸入樣本，yi∈{1，2，…，k}為輸出，代表了輸入樣本的分類情況.主要目標(biāo)是找到一種分類法則，使得分類法則φ(x)可以盡可能精準(zhǔn)的刻畫輸入xi和輸出yi之間的關(guān)系.假設(shè)樣本為獨(dú)立采樣且滿足分布P(x，y)，pj(x)=P(Y=j|X=x)表示樣本x被分到第j類的概率，當(dāng)各類別之間的錯(cuò)分誤差相等時(shí)，分類法則φ(x)的損失可由如下函數(shù)定義:

其中:I(·)為勢(shì)函數(shù)，若自變量為真，則取值為1，為假則取值為0.此時(shí)，最佳的分類法則為貝葉斯分類，即

當(dāng)錯(cuò)分誤差不一樣時(shí)，定義矩陣C，Cjl表示第j被錯(cuò)分到l的懲罰.顯然有Cjj=0，j=1，2，…，k，此時(shí)

通過(guò)最小化風(fēng)險(xiǎn)函數(shù)得到的最優(yōu)分類器為

但在實(shí)際問(wèn)題中，往往需要定義不同的錯(cuò)分懲罰，遇到這樣的情況可以通過(guò)調(diào)整矩陣C中的元素值來(lái)表示不同的錯(cuò)分誤差.

2.2 一對(duì)一(one against one)多分類支持向量機(jī)的數(shù)學(xué)模型

傳統(tǒng)的SVM算法是專門處理小樣本問(wèn)題的，因此在考慮多分類問(wèn)題時(shí)可以將問(wèn)題轉(zhuǎn)化成為多個(gè)二分類問(wèn)題，這樣的多分類支持向量機(jī)算法稱為一對(duì)一的多分類算法［12］.

一對(duì)一分類是在k類訓(xùn)練樣本中構(gòu)造所有可能的兩類分類器，每個(gè)分類器僅僅在k類中的兩類訓(xùn)練樣本上訓(xùn)練，結(jié)果共構(gòu)造k(k-1)/2個(gè)分類器，測(cè)試樣本經(jīng)過(guò)各個(gè)分類進(jìn)行分類，每次將樣本判為某一類，最終得到判入次數(shù)最多的類為樣本的最后結(jié)果.但這種算法的運(yùn)算量大，計(jì)算步驟很多，相應(yīng)的運(yùn)算時(shí)間也會(huì)長(zhǎng).

2.3 一對(duì)多(one against all)多分類支持向量機(jī)的數(shù)學(xué)模型

一對(duì)多方式的主要思想是構(gòu)造k個(gè)二分類器，每個(gè)二分類器應(yīng)用于所有樣本，第i個(gè)二分類器將樣本分為第i類和其他類，這k個(gè)二分類器組合起來(lái)就可以形成N分類的判決函數(shù).當(dāng)一個(gè)樣本數(shù)據(jù)輸入時(shí)，依次用這k個(gè)二分類器進(jìn)行判斷，如果第i個(gè)二分類器的輸出是屬于第i類，而其他的分類器都輸出為其他類，則判斷該樣本屬于第i類.

多分類支持向量機(jī)算法最終轉(zhuǎn)化為求解如下優(yōu)化問(wèn)題:

其中:向量vi∈Rk記錄分類結(jié)果，如果樣本xi屬于第j類，則向量vi第j個(gè)元素為1，其他元素為-(k-1)-1;且映射L(yi)第j個(gè)元素為0，其他元素為1的向量，滿足限定條件)=0.該問(wèn)題的最優(yōu)解的算法求解過(guò)程本文借助libsvm工具包［13］中SVMtrain函數(shù)完成.

3 高校生源質(zhì)量分析模型

基于多分類支持向量機(jī)的生源質(zhì)量分析模型由數(shù)據(jù)采集、數(shù)據(jù)預(yù)處理、特征指標(biāo)選取、數(shù)值歸一化和學(xué)習(xí)過(guò)程組成，如圖2所示.

圖2 多分類支持向量機(jī)模型

1)數(shù)據(jù)采集器.按用戶要求從數(shù)據(jù)庫(kù)中采集數(shù)據(jù);

2)數(shù)據(jù)預(yù)處理.剔除殘缺數(shù)據(jù)和奇異數(shù)據(jù)，如各省份特招生的樣本.由于各個(gè)省份的錄取標(biāo)準(zhǔn)不同，分?jǐn)?shù)之間的差距也很大，所以對(duì)高考成績(jī)進(jìn)行層次化處理，共分為11檔次，如表1所示.

表1 高考成績(jī)分層處理

3)特征指標(biāo)選取.從學(xué)生信息庫(kù)中依照數(shù)據(jù)的屬性和對(duì)問(wèn)題的貢獻(xiàn)選取了省份、高考成績(jī)、所在省份排名、畢業(yè)時(shí)所在專業(yè)排名情況這4個(gè)指標(biāo)組成了樣本的有效信息(見表2).

表2 有效樣本

4)數(shù)值歸一化處理.由于各個(gè)指標(biāo)之間數(shù)值的差別很大，所以對(duì)數(shù)值進(jìn)行歸一化處理，使得數(shù)值分布在［-1，1］之間:

5)訓(xùn)練及學(xué)習(xí)過(guò)程.對(duì)有標(biāo)號(hào)的樣本，根據(jù)其畢業(yè)時(shí)所在專業(yè)的排名進(jìn)行分類(見表3):

表3 帶標(biāo)號(hào)樣本的分類情況

4 測(cè)試實(shí)例與分析

數(shù)據(jù)來(lái)源主要是某大學(xué)某年級(jí)3 000余名本科學(xué)生的數(shù)據(jù).其中包括學(xué)生入學(xué)時(shí)的高考成績(jī)以及在高中時(shí)期的其他信息(包括是否是三好學(xué)生、優(yōu)秀學(xué)生干部，是否在學(xué)科競(jìng)賽中獲獎(jiǎng)等)，另外一部分信息如生源所在省，錄取時(shí)所在省份的排名情況以及高考成績(jī).研究的數(shù)據(jù)量足夠大，具有普遍性，使分析結(jié)果具有一定說(shuō)服力.

4.1 多分類支持向量機(jī)模型的分類情況

實(shí)驗(yàn)基于高斯核函數(shù)及多項(xiàng)式核函數(shù)展開，并選取了不同核寬及不同的階數(shù)進(jìn)行了對(duì)比，在表4中，MSVM表示多分類支持向量機(jī)模型，RBF-1表示核寬為1的高斯核，POLY-1表示階數(shù)為1的多項(xiàng)式核.在實(shí)驗(yàn)過(guò)程中，采用10倍交叉驗(yàn)證方法(10-fold cross validation)測(cè)試各個(gè)模型的分類結(jié)果，即將數(shù)據(jù)集分成10組，輪流將其中9組做訓(xùn)練，1組做測(cè)試，10次的結(jié)果的均值作為對(duì)算法精度的估計(jì)，結(jié)果分別呈現(xiàn)了均值和波動(dòng)值.

為比較多分類支持向量機(jī)的分類效果，采用多元統(tǒng)計(jì)中的判別分析作為對(duì)比試驗(yàn).判別分析是經(jīng)典的多元統(tǒng)計(jì)方法，其主要思想是在分類確定的條件下，根據(jù)某一研究對(duì)象的各種特征值判別其類型歸屬問(wèn)題的一種多變量統(tǒng)計(jì)分析方法.其基本原理是按照一定的判別準(zhǔn)則，建立一個(gè)或多個(gè)判別函數(shù)，用研究對(duì)象的大量資料確定判別函數(shù)中的待定系數(shù)，并計(jì)算判別指標(biāo).據(jù)此即可確定某一樣本屬于哪一類.實(shí)驗(yàn)結(jié)果見表4.

表4 實(shí)驗(yàn)結(jié)果(1)

通過(guò)實(shí)驗(yàn)可以看出，多分類支持向量機(jī)模型較傳統(tǒng)判別分析模型有著更好的分類能力.

4.2 模型的改進(jìn)

考慮對(duì)多分類支持向量機(jī)模型進(jìn)行改進(jìn)，在如上的實(shí)驗(yàn)中均假設(shè)對(duì)錯(cuò)誤分類的懲罰是一致的，但在實(shí)際情況中并不是如此.例如一種誤差是將一名一等的學(xué)生錯(cuò)分為二等，即優(yōu)秀的被判別成良好.另一種誤差是將一等學(xué)生錯(cuò)分到五等，即將優(yōu)秀的學(xué)生判別成差下.這兩種錯(cuò)誤的程度顯然不一樣，第二種錯(cuò)誤較第一種錯(cuò)誤要嚴(yán)重些，因此，可以調(diào)整懲罰矩陣Cjl，在本問(wèn)題中最終用到的懲罰矩陣為

含義為將第i類學(xué)生錯(cuò)分到第j的懲罰為|i-j|.

基于此調(diào)整，訓(xùn)練得到新的分類器，實(shí)驗(yàn)結(jié)果如表5所示.

表5 改進(jìn)后的實(shí)驗(yàn)結(jié)果

由模型的實(shí)驗(yàn)結(jié)果可以看出，分類結(jié)果精度較調(diào)整前有了較大的提高.

5 結(jié)論

1)本文基于多分類支持向量機(jī)算法建立了生源質(zhì)量分析模型，該模型可以通過(guò)生源所在地、高考成績(jī)，以及該成績(jī)所在省的排名等信息，預(yù)測(cè)出該生源在大學(xué)畢業(yè)時(shí)學(xué)習(xí)情況的所處類別，因此可以對(duì)生源的質(zhì)量?jī)?yōu)劣進(jìn)行初步的分析和評(píng)價(jià)，對(duì)招生工作及相關(guān)政策的制定有一定的指導(dǎo)和幫助.

2)通過(guò)對(duì)懲罰矩陣進(jìn)行合理的調(diào)整，模型的結(jié)果和可靠性都得到顯著的提高.

［1］姚金琢.高等教育大眾化與依法試行自主招生問(wèn)題探析［J］.中國(guó)高教研究，2006(11)，90-91.

［2］于春梅，楊勝波，陳馨，等.SVM和基于PCA、PLS的 SVM在非線性辨識(shí)中的比較研究［J］.計(jì)算機(jī)應(yīng)用研究，2004，24(6):85-90.

［3］VAPNIK V.The nature of statistical learning theory［M］.［S.l.］:Springer Verlag，1995.

［4］韓媚，郭丹鳳.SVM的特征選擇方法在高校就業(yè)預(yù)測(cè)中的應(yīng)用研究［J］.杭州師范大學(xué)學(xué)報(bào):自然科學(xué)版，2009，8(5):358-362.

［5］向小東，宋芳.基于核主成分與加權(quán)支持向量機(jī)的福建省城鎮(zhèn)登記失業(yè)率預(yù)測(cè)［J］.系統(tǒng)工程理論與實(shí)踐，2009，29(1):73-80.

［6］祁享年.支持向量機(jī)及其應(yīng)用研究綜述［J］.計(jì)算機(jī)工程，2004，30(10):6-9.

［7］SCH?LKOPF，SMOLA A.Learning with Kernels［M］. Cambridge:MIT Press，2002.

［8］LEE Y K，LIN Y，WAHBA G.Multicategory support vector machines，theory，and application to the classification of microarray data and satellite radiance data［J］. Journal of the American statistical Association，2004，99 (465):67-381.

［9］CHEN D R，XIANG D H.The consistency of multicategory support vector machines［J］.Adv Comput Math，2006，24(1-4):155-169.

［10］竇智宙，平子良，馮文兵，等.多分類支持向量機(jī)分割彩色癌細(xì)胞圖像［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45 (20)，236-239.

［11］康文雄，謝紀(jì)美，鄧飛其，等.基于小波分解和多分類支持向量機(jī)的臉譜識(shí)別［J］.計(jì)算機(jī)測(cè)量與控制，2005，13(12):1390-1422.

［12］HSU C W，LIN C J.A Comparison of Methods for Multiclass Support Vector Machines［J］.IEEE Trans Neural Networks，2002，13(2):415-425.

［13］CHANG C C，LIN C J.LIBSVM:a library for support vector machines［EB/OL］.［2008-07-25］.http:// www.csie.ntu.edu.tw/～cjlin/libsvm.