李 煜，馮 翱，鄒書蓉

(成都信息工程大學計算機學院，四川 成都 610225)

0 引 言

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

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

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

1 基本算法介紹

1.1 直推式支持向量機算法

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

(1)

(2)

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

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

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

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

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

1.2 k-近鄰算法

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

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

2)對于樣本Ci(i=1,2,…,n)，采取某種距離函數(shù)計算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)計集合C*樣本類別出現(xiàn)次數(shù)，出現(xiàn)次數(shù)最多的類別wi(i=1,2,…,m)即為測試樣本的類別。

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

1.3 k-均值聚類算法

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

(4)

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

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

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

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

dji=‖xj-μi‖

(5)

Step4確定xj的簇標記，將樣本xj加入對應的簇Cλj=Cλj∪{xj}。

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

(6)

Step5重新計算k個中心點。

(7)

Step6計算目標函數(shù)E，若滿足式(8)，算法結束，否則，返回Step3。

|En-En-1|<ε

(8)

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

2 算法設計

2.1 原理分析

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

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

2.2 算法主要步驟

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

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

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

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

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

(9)

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

(10)

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

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

3 實驗結果

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

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

項目數(shù)據(jù)集SVM-LightSVMlin數(shù)據(jù)集內容文本數(shù)據(jù)文本數(shù)據(jù)樣本維數(shù)99477279有標簽樣本數(shù)1050有標簽正樣本數(shù)525有標簽負樣本數(shù)525訓練集無標簽樣本數(shù)5981410測試集樣本數(shù)600486測試集中正樣本數(shù)300242測試集中負樣本數(shù)300244

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

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

項目算法名稱TSVMknn-TSVMk2TSVM有標簽樣本數(shù)101010無標簽樣本數(shù)598392376訓練時間/s0.088770.0754290.065478準確率/%93.59393.3333

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

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

項目算法名稱TSVMknn-TSVMk2TSVM有標簽樣本數(shù)505050無標簽樣本數(shù)1410825699訓練時間/s0.3016250.2389250.124125準確率/%92.798491.975392.3868

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

4 結束語

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

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

參考文獻：

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

[2] 謝麗星,周明,孫茂松. 基于層次結構的多策略中文微博情感分析和特征抽取[J]. 中文信息學報, 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]. 軟件學報, 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] 周志華. 機器學習[M]. 北京:清華大學出版社, 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]. 計算機工程與應用, 2013,49(14):144-146.

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