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

張月梅 劉媛華

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

1 引言

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

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

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

2 相關理論

2.1 隨機森林

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

2.1.1 Bagging和隨機子空間的選擇

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

2.1.2 袋外誤差估計（OOB）

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

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

2.2 K近鄰算法

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

KNN分類過程的數學描述如下。

定義判別函數：

分類的決策規則為

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

3 本文算法KNN-RF

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

算法1：RandomForesttrain(Dtrain)

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

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

2）抽取B組

3）for x inDB

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

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

2）在m個屬性中選擇最優的屬性（分裂節點）

3）將節點分裂成兩個子節點

輸出x′的類別

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

算法2：KNN-RF算法

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

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

（1）for x inDtrain

計算 distance（x，x′）

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

2）返回最優的前K個訓練樣本

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

4）KNNRF=RandomForst.train（DKNN）

輸出x′的類別

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

4 實驗及結果分析

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

4.1 數據準備

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

4.2 評價指標［11］

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

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

表1 分類準確率變量說明

4.3 實驗設置

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

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

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

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

由上文可知［7］，KNN-SVM是良好的文本分類器，這里作為我們對比的基線之一引入，分別將我們的數據集運用于兩中算法之中。可見圖2、圖3，KNN-RF與KNN-SVM算法隨著投影面積的增加，效果都表現顯著。可以發現，當K為900時兩者的精度都表現優異，最終，我們選用K為900進行下面的對比實驗。

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

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

4.4 實驗結果分析

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

表2 五種分類算法的分類結果

5 結語

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

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