KNN算法在輿情領(lǐng)域中的應(yīng)用研究

鄭偉 王若怡 馬林 李明 王喆

[摘 要]KNN算法是模式識別領(lǐng)域中的一種常用算法，具有簡單有效、無須估計參數(shù)等優(yōu)點。本文針對訓(xùn)練樣本的不規(guī)則性，分析了相似度權(quán)重的KNN算法，并將該算法應(yīng)用于網(wǎng)絡(luò)輿情的識別實驗中，旨在為研究KNN算法提供借鑒。實驗結(jié)果表明：KNN算法用相似度作為權(quán)重能夠有效提高輿情識別質(zhì)量。

[關(guān)鍵詞]輿情;KNN算法;準(zhǔn)確率

doi：10.3969/j.issn.1673 - 0194.2019.06.074

[中圖分類號]TP391[文獻(xiàn)標(biāo)識碼]A[文章編號]1673-0194（2019）06-0-02

0? ? ?引 言

現(xiàn)實生活中的熱點、焦點問題會引發(fā)廣大網(wǎng)民關(guān)注，同時民眾會通過網(wǎng)絡(luò)媒體轉(zhuǎn)發(fā)并發(fā)表相關(guān)意見。輿情就是大量民眾集中的意見表述與訴求，網(wǎng)絡(luò)輿情識別與預(yù)警對于輿情工作尤為重要，如有關(guān)部門提前發(fā)現(xiàn)輿情的源頭或預(yù)測可能產(chǎn)生的現(xiàn)實危機，可以提早判斷輿論走向，可以通過多部門聯(lián)動做好輿論引導(dǎo)和應(yīng)對突發(fā)事件的準(zhǔn)備。輿情預(yù)警是否及時決定了后續(xù)輿情處理效果的好壞，如何有效地從海量的互聯(lián)網(wǎng)言論中及時發(fā)現(xiàn)一些潛在的存在危機的輿論導(dǎo)向?qū)S護(hù)社會安定尤為重要。目前，輿情識別技術(shù)除日常監(jiān)測外還有以下技術(shù)，如主題提取、情感分析、話題聚類和話題跟蹤等。

近年來，一些研究者做了一些與輿情識別新技術(shù)有關(guān)的研究。例如：王珍從社會網(wǎng)絡(luò)的角度詳細(xì)分析了輿情的監(jiān)測和預(yù)警方法;田殷姿提出了一種挖掘搜索引擎日志內(nèi)容的輿情監(jiān)測方法，并通過實踐獲得了較好的預(yù)警效果;劉勘 等提出一種基于支持向量的真假輿情識別方法;趙靜嫻針對輿情的識別問題，提出一種基于組合優(yōu)化決策樹的偽輿情識別方法。本文主要研究了KNN算法下的網(wǎng)絡(luò)輿情識別及分類，并嘗試在KNN中采用相似度作為權(quán)重參與計算。

1? ? ?經(jīng)典KNN算法

經(jīng)典KNN（K-Nearest Neighbor）是一種基于統(tǒng)計的分類算法，原理簡單、編程易理解，在各個領(lǐng)域應(yīng)用廣泛。很多研究者對其進(jìn)行了不同程度的改進(jìn)，在分類、推薦與模式識別方向取得了較好的效果。KNN算法的思想在分類時采用投票原則，即少數(shù)服從多數(shù)原則;通過某種測量手段測量未知樣本的K個近鄰數(shù)，統(tǒng)計K個近鄰大多數(shù)屬于的類別，算法如下。

（1）已知訓(xùn)練樣本集合K={K1，K2，…，Km}，訓(xùn)練集合中樣本的數(shù)目，m、n為類別數(shù)目。

（2）設(shè)定待測樣本的最近鄰數(shù)目值k。

（3）樣本間的相似程度采用余弦相似度進(jìn)行測量，測度值用s表示。

（4）每個待測樣本用Z表示。①計算m個測度值并使用排序算法對其進(jìn)行排序，排序后為：s1，s2，…，sk，sK+1，…，sm。②取出其相似度最高的K個樣本，然后遵守投票規(guī)則進(jìn)行待測樣本Z的類別值判定，Z類別值為得票數(shù)最多的那個類別。

2? ? ?加權(quán)重KNN算法

針對K值的不易確定性、訓(xùn)練樣本的不均勻性，KNN算法采用一種相似度加權(quán)的KNN算法，該算法在分類時可以有效體現(xiàn)類別代表樣本的重要性，修改后的算法流程如下。

（1）已知訓(xùn)練樣本集合K={K1，K2，…，Km}，m為訓(xùn)練樣本數(shù)目，n為類別數(shù)。（2）樣本間的相似程度采用余弦相似度進(jìn)行測量，測度值用s表示。

（3）每個待測樣本Z的計算如下：①依次計算樣本X與訓(xùn)練樣本的余弦相似度si，其中i∈[1，n];②計算X的K個最近鄰的相似值{s1，s2，…，sk};③使用式（1）判別樣本X的類別，其中wk=sk，y?取最大值時所對應(yīng)的類別為樣本最終對應(yīng)的分類類別。

3? ? ?文本特征提取方法

向量空間模型常用文本向量表示，文本中的代表特征提取也稱特征選擇，通過構(gòu)造一個評估算法，對待評估的文本特征進(jìn)行打分，通過預(yù)設(shè)的閾值篩選出合適的詞條作為文本樣本的特征。目前，常用的特征評估函數(shù)有下列幾種形式：信息增益（IG）、互信息（MI）、χ2統(tǒng)計（CHI）、文本證據(jù)權(quán)（WET）、期望交叉熵（CE）等。周茜對上述常用的特征選擇方法進(jìn)行了研究，研究發(fā)現(xiàn)IG、χ2、WET法的效果較佳。

3.1? ? 信息增益（IG）

信息增益是信息論的一種信息計算公式，可以衡量特征出現(xiàn)時類別的貢獻(xiàn)度，n個類別的信息增益值需要累加。IG的定義如下。

其中，t與t分別表示特征的出現(xiàn)與不出現(xiàn)，ci表示第i個類別。

3.2? ?文本證據(jù)權(quán)（Weight of Evid Txt）

一個類別出現(xiàn)的概率與某個特征出現(xiàn)的概率關(guān)系可以通過條件概率之間的差別進(jìn)行表示，定義如下。

3.3? ?χ2估計（CHI）

CHI可以有效衡量特征詞t與類c之間的依存關(guān)系，特征t的CHI計算值為零，表示特征t與類別c之間相互獨立。對于類別c，特征t的CHI估計定義如下。

4? ? ?基于KNN算法的輿情分類實驗

表1顯示的是使用經(jīng)典KNN分類算法取不同K值時的分類結(jié)果。在京東網(wǎng)上商城下載關(guān)于某型號數(shù)碼相機的網(wǎng)絡(luò)商品評論數(shù)據(jù)，共360條作為語料進(jìn)行分類實驗，其中評論情感數(shù)據(jù)分為好評與差評兩類。實驗時選擇其中270條評論作為訓(xùn)練數(shù)據(jù)，余下90條作為測試數(shù)據(jù)，實驗數(shù)據(jù)使用2組交叉語料進(jìn)行實驗，特征選擇算法使用信息增益方法，特征維數(shù)取經(jīng)驗值500維。實驗采用的評估指標(biāo)為準(zhǔn)確率，其具體計算公式如下。

從表1可以看到，當(dāng)K值增大時，2組測試樣本所對應(yīng)的分類準(zhǔn)確率均在K值等于10時取最大值，隨后呈現(xiàn)波動趨勢，可見K值在10以后增加時，近鄰樣本中不斷引入各類別“雜”樣本。但是，加權(quán)重KNN算法與經(jīng)典KNN分類準(zhǔn)確率不同，表2顯示的是采用加權(quán)重KNN算法用于分類的結(jié)果。