鄭偉 王若怡 馬林 李明 王喆

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

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

doi：10.3969/j.issn.1673 - 0194.2019.06.074

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

0? ? ?引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1? ? 信息增益（IG）

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

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

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

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

3.3? ?χ2估計(jì)（CHI）

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

4? ? ?基于KNN算法的輿情分類(lèi)實(shí)驗(yàn)

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

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