基于K近鄰和隨機森林的情感分類研究?

張月梅 劉媛華

（上海理工大學管理學院 上海 200093）

1 引言

隨著互聯(lián)網(wǎng)飛速發(fā)展，互聯(lián)網(wǎng)用戶開始大規(guī)模增加。根據(jù)最新的《中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告》，截至2018年6月，我國網(wǎng)民規(guī)模為8.02億，相較2017年年末增加3.8%，互聯(lián)網(wǎng)普及率達57.7%［1］。越來越多的用戶通過網(wǎng)絡發(fā)布動態(tài)和實時消息，但這些主觀性的文本數(shù)據(jù)的飛速增長也造成了管理和檢索上的困難，僅靠人工已經(jīng)難以應對和處理這些海量數(shù)據(jù)。因此，如何利用信息技術對大量文本數(shù)據(jù)進行價值提取，成為近幾年研究的熱點。文本情感分析技術就是解決這一問題的有效工具。

傳統(tǒng)的情感極性分類主要基于兩種研究范疇：情感詞匯語義特性和統(tǒng)計自然語言處理［2］。基于情感詞匯語義特征方法是利用詞匯的情感傾向來判斷評論文本的情感極性，這類方法主要是以自處理為基礎，目前自然語言領域還存在一些關鍵性技術需要突破，這限制了情感詞匯語義特征方法的進一步發(fā)展。所以研究者開始更多地關注基于統(tǒng)計自然語言方法?，F(xiàn)有的比較成熟的情感分類方法主要都是基于單個分類器模型，比如：隨機森林［3］、K 近鄰［4］、邏輯回歸［5］、支持向量機［6］、樸素貝葉斯［7］、決策樹［12］、最大熵等統(tǒng)計模型計算文本的情感傾向，但是不同的分類模型的分類任務的側(cè)重點不同，使得單個模型在復雜的分類情況下，并不能保證分類性能的優(yōu)良性，這就使得單一的分類方法有一定的局限性［6，11，13，15］。

K近鄰是一種無需參數(shù)的便捷型懶惰分類算法，當文本數(shù)據(jù)過于龐大時，分類效果會變差，耗時會過長。隨機森林則是由多個弱分類器通過多數(shù)投票方式構(gòu)成的集成學習算法，相比與單一的決策樹擁有不會過度擬合等的特點，但正是由于弱分類器較多，導致人們無法控制其內(nèi)部的操作，只能通過對參數(shù)和隨機種子來進行調(diào)優(yōu)，而且如果有許多相似的決策樹，則會遮蓋住真實的分類結(jié)果。所以對隨機森林的數(shù)據(jù)進行“本地化”顯得尤為重要。根據(jù)文獻，當兩種算法結(jié)合使用可以提高情感分類的精度和效率。Y.Lin，Y.Jeon兩位專家［8］對隨機森林和它的一些變異進行了一些理論性的研究，并且建立了隨機森林和自適應最近的相鄰學習者之間的聯(lián)系。H.Zhang等［9］專家提出了一種基于K近鄰和支持向量機的混合模型（KNN-SVM），該算法雖然對情感分類有一定的效果，但是對參數(shù)的要求較高（如：成本函數(shù)和核函數(shù)等）。為了解決以上困難，文章提出了一種基于最近鄰投影下的隨機森林的混合算法。利用無監(jiān)督、無參數(shù)、簡單容易實現(xiàn)的KNN算法“本地化”數(shù)據(jù)集，再通過法隨機森林進行分類，利用其多數(shù)投票機制綜合各個弱分類器的計算結(jié)果得出情感的極性，進一步提高分類準確率。

2 相關理論

2.1 隨機森林

隨機森林是基于bagging的集成方法，它由一大組不穩(wěn)定但各自獨立的分類器組成，最終的分類結(jié)果通過多數(shù)投票產(chǎn)生。隨機森林所用的基礎預測結(jié)構(gòu)就是決策樹，因此得名。

2.1.1 Bagging和隨機子空間的選擇

Bagging是并行式集成學習方法中最著名的代表，是一種基于自主采樣（bootstrap sampling）的機器學習方法。隨機森林是通過一個bootstrapped訓練集來保證預測器之間的獨立性，即從原始數(shù)據(jù)集中有放回的抽取N個樣本，其中原始數(shù)據(jù)集的樣本數(shù)也是N。為了減少預測器之間的相關性，我們通過對P個屬性隨機挑選m個，找出這m個中最優(yōu)的屬性進行劃分來增加隨機性。隨機選擇一組屬性也有利于減少隨機森林對維度災難的敏感性，即在考慮很少的屬性時，隨機森林處理在高緯度數(shù)據(jù)集中的噪音屬性的魯棒性更好。

2.1.2 袋外誤差估計（OOB）

當我們用自主采樣boostrapping數(shù)據(jù)作為每棵樹的原始數(shù)據(jù)時，樣本在B次抽樣中始終沒有被抽到的概率為，當B無窮大時，概率約等于0.3679，即自主采樣數(shù)據(jù)集中會包含的原始數(shù)據(jù)，因為隨機森林的這個性質(zhì)，我們可以不用留出法來進行泛化估計，而是用（OOB）袋外誤差來進行泛化估計。

專家指出［3］，在使用隨機特性時，使用袋外估計可以增加準確率；袋外估計用于估計組合數(shù)目的泛化性、強度和相關性，這些估計都是在袋外進行的。

2.2 K近鄰算法

KNN是一種無需參數(shù)的便捷型懶惰分類算法。該方法通過計算特定樣本與訓練集里樣本之間的距離，一般為歐幾里得距離，找到離它最近的k個數(shù)據(jù)樣本。若k個最近鄰樣本原本屬于A類，那么新的測試數(shù)據(jù)的樣本也劃入到A類。

KNN分類過程的數(shù)學描述如下。

定義判別函數(shù)：

分類的決策規(guī)則為

x∈LLi，其中x為分類文本，m為總的類別，k（k＞1）為訓練集樣本數(shù)據(jù)中與x距離最近的文本數(shù)，Li為訓練集中的某個類別，ki為Li類文本的數(shù)目。

3 本文算法KNN-RF

KNN-RF是一種基于K近鄰和隨機森林的混合算法。通過懶惰算法KNN將原始數(shù)據(jù)集中的數(shù)據(jù)進行投影過濾，即將距離測試點的最近的K個文本向量投影到新的數(shù)據(jù)子集中，進行第一步的數(shù)據(jù)過濾，過濾掉一些不相關的噪音數(shù)據(jù)，凈化下一步隨機森林分類器中的數(shù)據(jù)子集。具體見算法1與算法2。

算法1：RandomForesttrain(Dtrain)

輸入：有N個樣本的訓練集Dtrain和測試樣本x′

1）從Dtrain中有放回的隨機抽取N個樣本

2）抽取B組

3）for x inDB

通過遞歸地對樹的每一個根節(jié)點重復以下步驟，直到達到最小的節(jié)點。

1）在P個屬性中隨機選出m個

2）在m個屬性中選擇最優(yōu)的屬性（分裂節(jié)點）

3）將節(jié)點分裂成兩個子節(jié)點

輸出x′的類別

算法1詳細介紹了隨機森林算法的工作原理，通過有放回的隨機抽樣生成bootsrrapped訓練子集以及隨機子空間的選擇，能有效增加分類器的獨立性，減小相關性對分類效果的影響。算法1將作為改進算法中的一個重要函數(shù)。

算法2：KNN-RF算法

輸入：有n1個樣本的訓練集Dtrain和測試樣本x′輸出：測試集類別

1）function：獲得K個近鄰（Dtrain，x′，k）

（1）for x inDtrain

計算 distance（x，x′）

（2）將距離排序得出最優(yōu)的前K個訓練樣本，

2）返回最優(yōu)的前K個訓練樣本

3）DKNN=function：獲得K個近鄰（Dtrain，x′，k）

4）KNNRF=RandomForst.train（DKNN）

輸出x′的類別

算法2作為混合算法中的主程序加入了KNN算法，將“本地化”后的數(shù)據(jù)子集分別帶入了隨機森林分類器進行分類任務，最終輸出x′類別

4 實驗及結(jié)果分析

為了驗證模型的有效性，將在中文評論數(shù)據(jù)集上進行對比實驗。本文選用了譚松波博士整理的酒店評論2000作為數(shù)據(jù)集。算法使用Python語言實現(xiàn)，中文分詞選用的是Jieba分詞工具庫，分類器模型選擇的是Scikit-Learn機器學習庫中的函數(shù)，硬件環(huán)境為 DELL，處理器為 Intel（R）Core（TM）i5-7200U，CPU@2.5Hz 2.7GHz，內(nèi)存為8GB。

4.1 數(shù)據(jù)準備

本文選用了包括1000條正面評論和1000條負面評論的譚松波博士酒店評論語料作為數(shù)據(jù)來源。針對數(shù)據(jù)中存在的酒店反饋，顧客的補充說明以及評論的長短等進行了數(shù)據(jù)的預處理，本文在處理過程中將評論的最小長度設置為50。最終選擇了524條負面評論，462條正面評論最為數(shù)據(jù)集。

4.2 評價指標［11］

文本分類效果的評價主要從以下幾個方面進行：

A，B，C，D的含義見表1。

表1 分類準確率變量說明

4.3 實驗設置

本文利用Python中的Jieba工具包進行精確分詞，IG進行特征降維，TF-IDF計算每個詞的權(quán)重并形成詞向量維度為300的向量空間模型。

完成向量空間模型的構(gòu)造后，我們需要對隨機的森林模型的參數(shù)進行定義，包括森林中樹的數(shù)量、每棵樹的停止標準、隨機選擇的特征數(shù)量和分割準則。這些參數(shù)通常是估計的。本文選擇讓樹無限制的生，隨機子集的大小固定為p，p是所有屬性的總數(shù)［3］。需要估算的是樹木的生長數(shù)量。根據(jù)經(jīng)驗，生長的樹越多，得到的泛化性能就越好，但是過多的樹木會浪費資源。

圖1中顯示了隨著數(shù)目棵樹增加，OOB估計的變化趨勢，為了獲得最合理的隨機森林的數(shù)目棵樹，本文需要找到使OOB估計平穩(wěn)的最小一點，看見當樹的棵數(shù)為24時，袋外估計趨于平穩(wěn)。故參數(shù)n_estimate=24。

圖1 森林中不同樹木數(shù)量下的OOB估計

由上文可知［7］，KNN-SVM是良好的文本分類器，這里作為我們對比的基線之一引入，分別將我們的數(shù)據(jù)集運用于兩中算法之中?？梢妶D2、圖3，KNN-RF與KNN-SVM算法隨著投影面積的增加，效果都表現(xiàn)顯著?？梢园l(fā)現(xiàn)，當K為900時兩者的精度都表現(xiàn)優(yōu)異，最終，我們選用K為900進行下面的對比實驗。

圖2 八種K投影下的KNN-RF分類結(jié)果

圖3 八種K投影下的KNN-SVM分類結(jié)果

4.4 實驗結(jié)果分析

由表2可知，相比與單一的分類器，兩個混合算法的分類精度較好，可以認為混合的分類器比單一的分類器效果更優(yōu)。從宏觀上來說，本文算法在四個指標中精度排名第一，另外三個的精度也以較小的精度次于第一名。從更微觀的角度來看，本文提出的KNN-RF的算法在F-measure上占優(yōu)，分別為79%與85%；在總體的分類精度上KNN-RF以82.2%的精度優(yōu)勢強于其他四個分類器，認為本文提出的分類算法在分類效果上具有一定的有效性和可行性。

表2 五種分類算法的分類結(jié)果

5 結(jié)語

本文通過“本地化”原始數(shù)據(jù)集，對文本進行差異性過濾后再進行分類做法使混合算法在與單一性分類器進行比較時具有明顯優(yōu)勢，具有良好實用性和發(fā)展前景。

對于今后的研究方向：本文只考慮了將兩種方法相結(jié)合，未來可以考慮將多種單一分類器融合的方法，進一步提高文本的情感分類精度；文中隨機森林所使用的投票機制，只是簡單的多數(shù)投票方法，未來可考慮改用加權(quán)投票機制，使每個子分類器的權(quán)重更具有自身特點；最后，文中給出的特征詞指向性不足等問題日后都需要深入研究。