基于改進(jìn)k-近鄰的直推式支持向量機(jī)學(xué)習(xí)算法

李 煜，馮 翱，鄒書蓉

(成都信息工程大學(xué)計(jì)算機(jī)學(xué)院，四川 成都 610225)

0 引 言

情感分析(Sentiment Analysis)指的是分析人們對諸如產(chǎn)品、服務(wù)、組織、事件、問題、主題等實(shí)體及其屬性的觀點(diǎn)、情感、評價、態(tài)度的研究領(lǐng)域[1]。隨著互聯(lián)網(wǎng)的普及，人們比過去更愿意和他人分享自己的生活、觀點(diǎn)、經(jīng)歷和想法，這促使網(wǎng)絡(luò)尤其是社交網(wǎng)絡(luò)中涌現(xiàn)出大量主觀文本數(shù)據(jù)，如何從大量文本數(shù)據(jù)中分析用戶態(tài)度成為個人、商家和政府迫切需要解決的問題之一[2]。通常情況下，所能獲得的文本數(shù)據(jù)往往是無標(biāo)簽的，若對其全部進(jìn)行標(biāo)注需要花費(fèi)大量人力物力。因此，如何利用少量的標(biāo)注數(shù)據(jù)對大量的無標(biāo)簽數(shù)據(jù)進(jìn)行分類識別成為該領(lǐng)域主要難題之一。

統(tǒng)計(jì)學(xué)習(xí)理論是由Vapnik等人提出的針對小樣本問題的機(jī)器學(xué)習(xí)理論[3-4]。支持向量機(jī)(Support Vector Machine, SVM)[5]是建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上，以結(jié)構(gòu)風(fēng)險最小化為原則的一種學(xué)習(xí)算法。由于其良好的分類性能，該算法在圖像和文本處理等眾多領(lǐng)域得到了廣泛的應(yīng)用。

傳統(tǒng)支持向量機(jī)根據(jù)學(xué)習(xí)樣本進(jìn)行訓(xùn)練得到分類超平面，并對測試樣本進(jìn)行預(yù)測。SVM具有良好的分類性能，但它要求每個學(xué)習(xí)樣本標(biāo)簽已知。但在實(shí)際問題中，得到所有學(xué)習(xí)樣本的標(biāo)簽需要花費(fèi)較大代價。針對傳統(tǒng)支持向量機(jī)的不足，Joachims等人提出直推式支持向量機(jī)模型(Transductive Support Vector Machine, TSVM)[6]。該模型可以利用少量有標(biāo)簽樣本對無標(biāo)簽樣本進(jìn)行預(yù)測，可以在保證準(zhǔn)確率的同時，較大幅度地減少對有標(biāo)簽樣本的依賴。但當(dāng)數(shù)據(jù)量較大時，TSVM模型構(gòu)建需要花費(fèi)大量時間。在保證算法準(zhǔn)確率能滿足實(shí)際應(yīng)用要求的前提下，如何減少該算法的運(yùn)行時間成為主要研究方向之一。

1 基本算法介紹

1.1 直推式支持向量機(jī)算法

文獻(xiàn)[6-7]中提出一種直推式支持向量機(jī)學(xué)習(xí)算法，與傳統(tǒng)SVM一樣，TSVM也是針對二分類問題的學(xué)習(xí)方法。TSVM試圖對未標(biāo)記樣本賦予不同的標(biāo)簽并找到在所有樣本上間隔最大的分類超平面。下面對TSVM的基本原理進(jìn)行簡單介紹[8-9]。

(1)

(2)

Step1用戶指定影響因子C和C*，并使用傳統(tǒng)支持向量機(jī)方法對有標(biāo)簽數(shù)據(jù)進(jìn)行訓(xùn)練，得到一個初始分類器。

Step2用初始分類器對無標(biāo)簽數(shù)據(jù)進(jìn)行分類，并按照分類結(jié)果給無標(biāo)簽數(shù)據(jù)賦予臨時標(biāo)簽。

Step3使用支持向量機(jī)方法對全部樣本進(jìn)行訓(xùn)練，得到新的分類器。按照一定規(guī)則交換數(shù)據(jù)的臨時標(biāo)簽，使得目標(biāo)函數(shù)值最大程度地減小。

Step4逐漸增大C*，并返回Step3，直到C和C*相等為止。

Step1中用戶指定C*應(yīng)小于C，使算法執(zhí)行初期有標(biāo)記樣本在算法中發(fā)揮更大作用。Step3中數(shù)據(jù)臨時標(biāo)簽的交換是最小化目標(biāo)函數(shù)的關(guān)鍵。Step4中C*的逐漸增大目的是增加無標(biāo)記樣本對算法的影響，使目標(biāo)函數(shù)進(jìn)一步最小化。

1.2 k-近鄰算法

k-近鄰算法(k-nearest neighbor, kNN)是一種常用的分類算法[10]，它是惰性學(xué)習(xí)[11]的顯著代表，即沒有明顯的訓(xùn)練過程。訓(xùn)練階段只將樣本保存起來，當(dāng)測試樣本輸入，算法開始執(zhí)行。它的原理為找出每個樣本最近的k個樣本，k個樣本中出現(xiàn)次數(shù)最多的類別即為該樣本的類別，主要過程如下[12]：

1)給定訓(xùn)練樣本集C={C1,C2,…,Cn}，樣本類別集合w={w1,w2,…,wm}，設(shè)置k值。

2)對于樣本Ci(i=1,2,…,n)，采取某種距離函數(shù)計(jì)算Ci與Cj(j=1,2,…,n,i≠j)的距離為dij，存入距離集合D。

D={dij|i=1,2,…,k; j=1,2,…,k; i≠j}

(3)

4)統(tǒng)計(jì)集合C*樣本類別出現(xiàn)次數(shù)，出現(xiàn)次數(shù)最多的類別wi(i=1,2,…,m)即為測試樣本的類別。

在k-近鄰算法中，測試樣本的k個近鄰在一定程度上反映出測試樣本的空間位置。若k個樣本類別基本一致，則測試樣本有很大概率屬于該類別。若k個樣本存在2個類別對應(yīng)樣本數(shù)目大致相同，則說明該樣本位于這2個類的交界處。

1.3 k-均值聚類算法

k-均值聚類算法[13]是一種典型的無監(jiān)督學(xué)習(xí)方法。它將數(shù)據(jù)集樣本分為k個簇，使得簇內(nèi)樣本相似，簇間樣本相異。聚類性能的衡量是由目標(biāo)函數(shù)決定的，k-均值聚類算法的目標(biāo)函數(shù)即最小化平方誤差[14]：

(4)

其中μi是每個簇的均值向量，即每簇的中心，Ci是聚類完成后產(chǎn)生的簇劃分，k為劃分簇的個數(shù)，x為數(shù)據(jù)集中的樣本。直觀上看，該目標(biāo)函數(shù)刻畫簇內(nèi)樣本的緊密程度，即E值越小，簇內(nèi)樣本越緊密，相似度越高，算法主要過程如下[15]：

Step1輸入樣本集D={x1,x2,…,xm}，聚類簇數(shù)k和精度ε。

Step2從D中隨機(jī)選擇k個樣本作為初始的中心點(diǎn)集μ={μ1,μ2,…,μk}。

Step3令Ci=Φ(1ik)，遍歷數(shù)據(jù)集，計(jì)算樣本xj和各中心點(diǎn)μi(1ik)的距離。

dji=‖xj-μi‖

(5)

Step4確定xj的簇標(biāo)記，將樣本xj加入對應(yīng)的簇Cλj=Cλj∪{xj}。

λj=arg mini∈{1,2,…,k}dji

(6)

Step5重新計(jì)算k個中心點(diǎn)。

(7)

Step6計(jì)算目標(biāo)函數(shù)E，若滿足式(8)，算法結(jié)束，否則，返回Step3。

|En-En-1|<ε

(8)

事實(shí)上，最小化式(4)需要考察樣本集D所有可能的簇劃分，這是一個NP問題。k-均值聚類算法采用了貪心算法的思想，通過迭代優(yōu)化找出近似解，但初始中心點(diǎn)和k值的選取會影響算法的執(zhí)行結(jié)果。

2 算法設(shè)計(jì)

2.1 原理分析

TSVM成功將直推式學(xué)習(xí)思想引入算法中，利用無標(biāo)簽數(shù)據(jù)和少量的有標(biāo)簽數(shù)據(jù)構(gòu)建分類器。相對于傳統(tǒng)的支持向量機(jī)，該算法結(jié)合無標(biāo)簽數(shù)據(jù)隱藏的分布信息，在分類性能上有一定提高。但是，TSVM求解過程需要遍歷所有無標(biāo)簽樣本，當(dāng)數(shù)據(jù)量較大時，算法執(zhí)行時間較長。文獻(xiàn)[16-17]中提出了2種解決方式，但都存在一定缺陷。為了在保證準(zhǔn)確率的前提下進(jìn)一步提高TSVM模型的運(yùn)行速度，本文提出一種基于改進(jìn)k-近鄰的直推式支持向量機(jī)學(xué)習(xí)算法(k2TSVM)。

該算法思想如下：若僅使用k-均值算法將無標(biāo)簽樣本分為k簇，每簇樣本賦予相同標(biāo)簽，然后對無標(biāo)簽樣本集所有2k種分類結(jié)果進(jìn)行訓(xùn)練和學(xué)習(xí)，選擇分類效果最好的作為最終分類器，算法雖然在一定程度上對數(shù)據(jù)集進(jìn)行壓縮，但是學(xué)習(xí)所有分類可能仍需花費(fèi)較長時間。由支持向量機(jī)可知，算法目標(biāo)是最大化支持向量到分類超平面的幾何間隔，支持向量機(jī)分類超平面僅僅取決于少數(shù)支持向量，即位于2類交界處的樣本對分類器起決定作用。利用這點(diǎn)刪除遠(yuǎn)離分類面樣本，在一定程度上可以加快算法執(zhí)行速度，但依然需要遍歷無標(biāo)簽樣本。由聚類算法特性可知，簇內(nèi)樣本相似，簇間樣本相異，因此一種新思路是在進(jìn)行k-近鄰算法前先對無標(biāo)簽樣本進(jìn)行k-均值聚類，分為若干簇。由于簇內(nèi)樣本相似，使用每簇中心點(diǎn)作為簇的代表進(jìn)行k-近鄰算法，若該中心點(diǎn)的k個近鄰類別大致相同，則認(rèn)為該類樣本遠(yuǎn)離2類交界面，可將該簇樣本刪除。這種方法可以減少k-近鄰算法的測試樣本數(shù)，進(jìn)一步提高算法的執(zhí)行速度。

2.2 算法主要步驟

k2TSVM算法解決二分類問題的主要步驟如下：

Step1輸入有標(biāo)簽樣本集合Dl={Dl1,Dl2,…,Dlm}和無標(biāo)簽樣本集合Du={Du1,Du2,…,Dun}。

Step2根據(jù)無標(biāo)簽樣本總數(shù)n的大小估計(jì)簇數(shù)k1，使用k-均值算法將無標(biāo)記數(shù)據(jù)進(jìn)行聚類，將其分為k1簇，記錄其均值向量集合μ={μ1,μ2,…,μk1}。

Step3根據(jù)有標(biāo)簽樣本總數(shù)m的大小估計(jì)近鄰數(shù)k2，設(shè)置閾值θ,i=1。

Step4采用某種距離函數(shù)計(jì)算中心點(diǎn)μi和有標(biāo)簽樣本Dlj(1jm)的距離，此處選取余弦相似度，則中心點(diǎn)μi和有標(biāo)簽樣本Dlj的相似度可定義為：

(9)

Step5統(tǒng)計(jì)中心點(diǎn)μi的k2個近鄰樣本屬于正類個數(shù)為numpos，屬于負(fù)類個數(shù)為numneg，若滿足式(10)，則表明該均值向量所屬簇遠(yuǎn)離2類交界處，將該簇?zé)o標(biāo)記樣本從Du中刪除。

(10)

Step6i=i+1；如果ik1，返回Step4。

Step7將有標(biāo)簽數(shù)據(jù)集合Dl和剩余無標(biāo)簽數(shù)據(jù)集合Du作為訓(xùn)練集輸入TSVM算法中進(jìn)行分類器構(gòu)建。

3 實(shí)驗(yàn)結(jié)果

根據(jù)上面提出的算法，采用SVM-Light工具箱的路透社文章數(shù)據(jù)集和SVMlin工具箱的路透社文章數(shù)據(jù)集對算法進(jìn)行實(shí)驗(yàn)，該算法在SVMlin代碼基礎(chǔ)上使用C++語言實(shí)現(xiàn)。實(shí)驗(yàn)軟件環(huán)境：Ubuntu-16.04，硬件環(huán)境：Intel i5-4590s處理器，3.00 GHz主頻，8 GB內(nèi)存的PC機(jī)。2個數(shù)據(jù)集具體情況如表1所示。

表1 2個數(shù)據(jù)集情況介紹

項(xiàng)目數(shù)據(jù)集SVM-LightSVMlin數(shù)據(jù)集內(nèi)容文本數(shù)據(jù)文本數(shù)據(jù)樣本維數(shù)99477279有標(biāo)簽樣本數(shù)1050有標(biāo)簽正樣本數(shù)525有標(biāo)簽負(fù)樣本數(shù)525訓(xùn)練集無標(biāo)簽樣本數(shù)5981410測試集樣本數(shù)600486測試集中正樣本數(shù)300242測試集中負(fù)樣本數(shù)300244

為了驗(yàn)證k2TSVM算法的有效性，采用文獻(xiàn)[11]中的k-近鄰法作為實(shí)驗(yàn)的對照算法，記為knn-TSVM。使用上述2個數(shù)據(jù)集，對原始TSVM, knn-TSVM和k2TSVM算法進(jìn)行分類實(shí)驗(yàn)比較，結(jié)果分別如表2和表3所示。

表2 3種算法使用第1個數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果對比

項(xiàng)目算法名稱TSVMknn-TSVMk2TSVM有標(biāo)簽樣本數(shù)101010無標(biāo)簽樣本數(shù)598392376訓(xùn)練時間/s0.088770.0754290.065478準(zhǔn)確率/%93.59393.3333

從表2實(shí)驗(yàn)結(jié)果可得：1)knn-TSVM算法和k2TSVM算法對數(shù)據(jù)集均有一定刪減，樣本數(shù)分別減少34.4%和37.1%。2)2種改進(jìn)算法訓(xùn)練時間與原始算法相比都有下降，分別下降15%和26%。3)在準(zhǔn)確率方面，由于數(shù)據(jù)量的減少，2種改進(jìn)算法準(zhǔn)確率分別下降0.5%和0.167%，雖然準(zhǔn)確率均略微下降但能夠滿足實(shí)際應(yīng)用要求。由實(shí)驗(yàn)結(jié)果可知，k2TSVM算法在減少樣本數(shù)量，降低訓(xùn)練時間的幅度和準(zhǔn)確率3個方面表現(xiàn)均優(yōu)于knn-TSVM算法。

表3 3種算法使用第2個數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果對比

項(xiàng)目算法名稱TSVMknn-TSVMk2TSVM有標(biāo)簽樣本數(shù)505050無標(biāo)簽樣本數(shù)1410825699訓(xùn)練時間/s0.3016250.2389250.124125準(zhǔn)確率/%92.798491.975392.3868

從表3實(shí)驗(yàn)結(jié)果可得：1)knn-TSVM算法和k2TSVM算法樣本數(shù)分別減少41.5%和50.4%。2)2種改進(jìn)算法訓(xùn)練時間與原始算法相比都有下降，分別下降20.8%和58.9%。3)在準(zhǔn)確率方面，2種改進(jìn)算法準(zhǔn)確率分別下降0.82%和0.41%。由實(shí)驗(yàn)結(jié)果可知，隨著數(shù)據(jù)集樣本數(shù)量的增加，k2TSVM算法在減少樣本數(shù)量，降低訓(xùn)練時間的幅度2個方面表現(xiàn)均優(yōu)于knn-TSVM算法且領(lǐng)先幅度比表2明顯。在準(zhǔn)確率方面，k2TSVM算法準(zhǔn)確率稍優(yōu)于knn-TSVM算法，雖與原算法相比略有下降，但能夠滿足實(shí)際應(yīng)用需求。

4 結(jié)束語

本文提出了一種基于改進(jìn)k-近鄰的直推式支持向量機(jī)學(xué)習(xí)算法——k2TSVM，該算法在保證算法準(zhǔn)確率能滿足實(shí)際應(yīng)用需求的前提下有效降低了TSVM模型計(jì)算復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，該算法在運(yùn)行時間和準(zhǔn)確率方面均優(yōu)于基于k-近鄰的直推式支持向量機(jī)學(xué)習(xí)算法。

該算法的不足之處是算法性能很大程度上取決于k-均值聚類算法執(zhí)行結(jié)果，但k-均值聚類對于離群點(diǎn)和孤立點(diǎn)敏感。一種改進(jìn)的方法是在進(jìn)行k-均值聚類前先將離群點(diǎn)刪除，減少離群點(diǎn)對算法的影響。

參考文獻(xiàn)：

[1] Liu Bing. Sentiment Analysis and Opinion Mining[M]. Morgan & Claypool Publishers, 2012.

[2] 謝麗星,周明,孫茂松. 基于層次結(jié)構(gòu)的多策略中文微博情感分析和特征抽取[J]. 中文信息學(xué)報, 2012,26(1):73-83.

[3] Vapnik V. The Nature of Statistical Learning Theory[M]. New York: Springer-Verlag, 1995.

[4] Vapnik V. Statistical Learning Theory[M]. New York: John Wiley and Sons, 1998.

[5] Cortes C, Vapnik V. Support-vector networks[J]. Machine Learning, 1995,20(3):273-297.

[6] Joachims T. Transductive inference for text classification using support vector machines[C]// Proceedings of the 16th International Conference on Machine Learning. 1999:200-209.

[7] Joachims T. Transductive support vector machines[M]// Semi-Supervised Learning. MIT Press, 2006:105-118.

[8] Joachims T. Learning to Classify Text Using Support Vector Machines: Methods, Theory and Algorithms[M]. Kluwer Academic Publishers, 2002.

[9] 陳毅松,汪國平,董士海. 基于支持向量機(jī)的漸進(jìn)直推式分類學(xué)習(xí)算法[J]. 軟件學(xué)報, 2003,14(3):451-460.

[10] Cover T M, Hart P E. Nearest neighbor pattern classification[J]. IEEE Transactions on Information Theory, 1967,13(1):21-27.

[11] Aha D W. Lazy learning[J]. Artificial Intelligence Reviews, 1997,11(1-5):7-10.

[12] Keller J M, Gray M R, Givens J A. A fuzzy k-nearest neighbor algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1985,15(4):580-585.

[13] Kanungo T, Mount D M, Netanyahu N S, et al. An efficient k-means clustering algorithm: Analysis and implementation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(7):881-892.

[14] 周志華. 機(jī)器學(xué)習(xí)[M]. 北京:清華大學(xué)出版社, 2016.

[15] Likas A, Vlassis N, Verbeek J J. The global k-means clustering algorithm[J]. Pattern Recognition, 2003,36(2):451-461.

[16] 王立梅,李金鳳,岳琪. 基于k-均值聚類的直推式支持向量機(jī)學(xué)習(xí)算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013,49(14):144-146.

[17] 廖東平,王書宏,黎湘. 一種結(jié)合k-近鄰法的改進(jìn)的漸進(jìn)直推式支持向量機(jī)學(xué)習(xí)算法[J]. 電光與控制, 2010,17(10):6-9.