基于粒子群聚類的KNN微博輿情分類研究

林 偉

（福建警察學(xué)院偵查系 福建 福州 350007）

基于粒子群聚類的KNN微博輿情分類研究

林 偉

（福建警察學(xué)院偵查系 福建 福州 350007）

基于數(shù)據(jù)挖掘的微博情感分類是網(wǎng)絡(luò)輿情監(jiān)控的重要方法，其中KNN算法具有簡單有效、無需估計(jì)參數(shù)等優(yōu)點(diǎn)，適用于微博輿情分類。微博輿情分類實(shí)質(zhì)上是對微博上的負(fù)面情感及時監(jiān)控，KNN會因在情感分類時處理大量的計(jì)算影響算法效率。因此，采用粒子群聚類算法在情感分類前裁剪微博訓(xùn)練樣本空間，以減少分類時的計(jì)算量。實(shí)驗(yàn)結(jié)果表明，基于粒子群聚類的KNN算法能夠有效提高微博情感分類的性能。

KNN 微博情感分類 特征選擇 粒子群聚類

隨著互聯(lián)網(wǎng)和通訊技術(shù)的發(fā)展，人們在網(wǎng)絡(luò)虛擬空間中呈現(xiàn)出的情感傾向、互動交流等往往是現(xiàn)實(shí)社會的延伸，涉及道德、民生、貪腐等民眾關(guān)注的熱點(diǎn)敏感話題信息極易被網(wǎng)絡(luò)催生和激化，將矛盾放大、以點(diǎn)概面、以偏概全形成各類攻擊，具有強(qiáng)大的蠱惑和煽動力，導(dǎo)致矛盾升級進(jìn)而影響社會穩(wěn)定[1]。據(jù)第38次《中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報告》顯示，截至2016年9月，我國微博用戶月活躍數(shù)3.906億，日活躍數(shù)1.05億，人均月使用次數(shù)52次，微博在追蹤熱點(diǎn)、發(fā)表熱點(diǎn)評論、關(guān)注興趣話題等方面都是用戶的首選平臺[2]。為此，通過數(shù)據(jù)挖掘算法對微博進(jìn)行情感分類及時監(jiān)控網(wǎng)絡(luò)上帶有煽動、攻擊等“負(fù)面”言論，進(jìn)而掌握輿論導(dǎo)向，具有重要的現(xiàn)實(shí)意義[3]。

在數(shù)據(jù)挖掘領(lǐng)域，常用的分類算法有：K最近鄰（KNN）、貝葉斯、支持向量機(jī)及神經(jīng)網(wǎng)絡(luò)等，其中KNN算法具有簡單有效、無需估計(jì)參數(shù)等優(yōu)點(diǎn)，適用于類似微博輿情這樣樣本容量比較大的類域的分類。然而，微博輿情分類實(shí)質(zhì)上是對微博上的“負(fù)面”情感及時監(jiān)控，KNN會因在情感分類時處理大量的計(jì)算影響算法效率。因此，本研究中將采用粒子群聚類算法在情感分類前裁剪微博訓(xùn)練樣本空間，以減少分類時的計(jì)算量。

1 相關(guān)工作

1.1 特征選擇

為降低特征空間維數(shù)及計(jì)算量、防止數(shù)據(jù)過份擬合，應(yīng)從微博訓(xùn)練集的原始特征空間中按照一定的評估函數(shù)篩選出對情感分類貢獻(xiàn)較大的前N個特征子集，即特征選擇。文獻(xiàn)[4]對文本分類領(lǐng)域常見的幾種特征選擇算法進(jìn)行了詳細(xì)比較，指出信息增益（IG）和卡方統(tǒng)計(jì)（CHI）表現(xiàn)最好，因此本研究用信息增益做為特征選擇的評估函數(shù)。

信息增益是通過計(jì)算某特征詞t出現(xiàn)前后的信息熵來衡量其對分類的貢獻(xiàn)，與特征詞的信息量成正比關(guān)系，在數(shù)據(jù)挖掘領(lǐng)域廣泛應(yīng)用，計(jì)算公式如下：

其中，P(ci)表示ci類在微博訓(xùn)練集中出現(xiàn)的

_概率；P(t)、P(t)分別表示微博訓(xùn)練集中包含或不包含特征詞t的微博樣本概率；P(ci|t)表示微博訓(xùn)練集

_中包含特征詞 并且屬于ci類的條件概率；P(ci|t)表示微博訓(xùn)練集中不包含特征詞t并且屬于ci類的條件概率。

1.2 微博向量表示

微博的內(nèi)容是方便人類閱讀的自然語言，計(jì)算機(jī)無法理解與計(jì)算，因此要對微博以結(jié)構(gòu)化的特征向量形式存儲以便計(jì)算機(jī)處理，在文本分類領(lǐng)域一般用向量空間模型（VSM）來表示。一條微博（Micro-blog）經(jīng)切詞分詞算法預(yù)處理后，用向量空間模型描述為：m=＜w(t1),w(t2),w(t3)...,w(td)＞ ，其中n為向量空間的維數(shù)，w(ti)為特征詞ti在微博向量中的權(quán)重值，一般使用詞頻—逆文檔頻（TF-IDF）來計(jì)算，同時將各項(xiàng)特征詞ti權(quán)值規(guī)范在[0，1]之間，其計(jì)算公式為[5]：

其中，tfij為特征詞ti在微博樣本mj中的出現(xiàn)次數(shù)，N訓(xùn)練微博總數(shù)，dfi是特征詞ti在微博中的文檔頻率。

1.3 KNN分類算法

KNN算法是文本分類常用的算法之一，具有簡單有效、魯棒性、無需估計(jì)參數(shù)等優(yōu)點(diǎn)，應(yīng)用到微博輿情分類中其基本思想是[6]：計(jì)算待測微博樣本與已知訓(xùn)練微博樣本的情感相似度，找出與待測微博樣本相似度最大的K個最近鄰微博樣本，K個微博樣本中情感傾向較多的類別為該測試微博的情感類別，基本步驟如下：

（1）始初化K的值，K為最近鄰數(shù)。

（3）評估待試微博Mj與訓(xùn)練集中所有微博樣本Mi的情感相似度，我們使用歐式距離計(jì)算：

（4）根據(jù)公式（3）的計(jì)算結(jié)果進(jìn)行排序，選出計(jì)算值最大的K個微博，作為微博Mj情感最近鄰。

（5）計(jì)算待測試微博樣本與類別C的)情感相似度：

其中，Mj在類別 中出現(xiàn)(Mj,C)為1，否則為0，微博Mj的情感類別決策為：

2 KNN算法中微博訓(xùn)練集裁剪

雖然KNN算法簡單有效，但隨著微博訓(xùn)練集規(guī)模的增加，需要計(jì)算待測試微博樣本與訓(xùn)練集中所有微博樣本的情感相似度來找出K最近鄰，隨著大數(shù)據(jù)浪潮的到來，當(dāng)訓(xùn)練微博樣本集達(dá)到一定級別時，計(jì)算與每個微博情感相似耗時將劇增，KNN算法的效率問題凸顯。特別是在輿情監(jiān)控領(lǐng)域，應(yīng)及時監(jiān)控網(wǎng)絡(luò)上帶有煽動、攻擊等“負(fù)面”言論從而引導(dǎo)輿論導(dǎo)向，因而對情感分類算法的實(shí)時性要求高，下面討論用粒子群算法對微博訓(xùn)練集進(jìn)行裁剪，以提高KNN算法應(yīng)用在微博情感分類中的性能。

2.1 粒子群算法

粒子群算法基本思想是[7]：隨機(jī)初始化粒子群，粒子i的位置為：Xi=(x1,x2,...,xn)，飛行速度

為：Vi=(v1,v2,...,vn)，Xi和Vi為n維空間。粒子i通過由目標(biāo)函數(shù)決定的適應(yīng)值來不斷迭代找到最優(yōu)解，同時通過跟蹤自己目前的最好位置pbest和粒子群全局最優(yōu)位置gbest來更新自己。找到pbest和gbest后，通過公式（6）和（7）來分別更新自己的速度與位置。

其中，Vi為粒子的速度，rand()為隨機(jī)數(shù)，Xi為粒子的當(dāng)前位置，c1,c2是學(xué)習(xí)因子，ω為慣性因子。

2.2 聚類算法

聚類算法的基本思路就是按照一定的度量規(guī)則將數(shù)據(jù)進(jìn)行歸類或分組，使用組（也稱為簇）內(nèi)的數(shù)據(jù)具有較高的相似性，而組間的數(shù)據(jù)具有較大的差異性。應(yīng)用到微博訓(xùn)練樣本中其數(shù)學(xué)描述為：設(shè)有微博訓(xùn)練集M={M1,M2,M3,...,MN}，其中Mi是個d維的向量，N為訓(xùn)練集中微博總數(shù)。對于訓(xùn)練集M的聚類，就是通過一定算法劃分為{C1,C2,...,Cc}，通過求解訓(xùn)練集中的劃分滿足以下條件：樣本情感相似度用公式（3）計(jì)算[8]。

為了發(fā)現(xiàn)c個簇的最優(yōu)劃分，聚類問題一般定義成一個性能函數(shù)的最優(yōu)（最?。﹩栴}，使得類間總離散度和Jm達(dá)到最小，計(jì)算公式為：

其中，z1,z2,...,zc分 別為C1,C2,...,Cc的簇 中心。

||Mj?zi||為Mj到聚類中心zi的距離，滿足公式（9），Mj則 屬第i類。

2.3 基于粒子群聚類的微博訓(xùn)練集裁剪

編碼：本研究中的粒子編碼結(jié)構(gòu)如表1所示，其中z1,z2,...,zc分別是劃分為c類的每類簇中心（為d維向量，因此位置就是c×d維，每個粒子代表的是c個初始聚類中心的組合），vi為粒子飛行的速度，f(x)是自適應(yīng)函數(shù)[7]如表1所示。

表1 粒子編碼

根據(jù)粒子群算法和聚類算法的基本思想，基于粒子群聚類的微博訓(xùn)練集裁剪算法思路：輸入初始微博訓(xùn)練集M，總數(shù)為N，加速常數(shù)c1,c2，慣性權(quán)重ω，需要聚的類數(shù)c。

（1）微博訓(xùn)練集M在切詞分詞的基礎(chǔ)上，按1.1節(jié)和1.2節(jié)對微博進(jìn)行預(yù)處理工作，將所有樣本用向量空間模型（VSM）表示；

（2）初始化粒子群和相關(guān)參數(shù)（具體值見實(shí)驗(yàn)），從微博訓(xùn)練集中隨機(jī)選出幾個樣本為原始聚類中心，初始化P個粒子的位置編碼Xi，速度Vi=0；

（3）同時根據(jù)f(x)計(jì)算粒子的適應(yīng)度，產(chǎn)生pbest和gbest；

（4）根據(jù)公式（6）和（7）更新所有粒子的速度和位置；

（5）根據(jù)粒子聚類中心編碼，按最近鄰法則對微博樣本聚類分析及劃分，然后重新計(jì)算聚類中心并更新粒子的適應(yīng)度值；

（6）更新粒子的個最優(yōu)位置pbest和全局最位置gbest；

（7）重復(fù)步驟（4）至（6）直到達(dá)到最大迭代次數(shù)。

通過以上算法輸出以聚類中心的微博樣本調(diào)整后的裁剪訓(xùn)練集，然后采用KNN分類算法對微博進(jìn)行情感分類的處理，具體流程如圖1所示。

圖1 基于粒子群聚類的KNN微博情感分類流程

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)語料庫來源分別為新浪開放平臺公開的API抓取的中文微博樣本集和我們自己收集的部分私人微博，通過微博樣本的人工標(biāo)注，實(shí)驗(yàn)數(shù)據(jù)的樣本結(jié)構(gòu)如表2所示。

表2 微博樣本結(jié)構(gòu)

3.2 評價指標(biāo)

為了有效評價微博情感分類性能的好壞，我選取F值作為評判算法有效性的指標(biāo) ，其計(jì)算公式為：

3.3 實(shí)驗(yàn)結(jié)果分析

本實(shí)驗(yàn)中切詞分詞工具選用中科院NLPIR漢語分詞系統(tǒng)（2013版），開發(fā)平臺為Visual Stdio.net 2015，在Windows環(huán)境下用C++語言實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果采取10次交叉驗(yàn)證方法，結(jié)果取平均值。從正面微博和負(fù)面微博中各取500條作為測試樣本，剩下的作為訓(xùn)練樣本。

實(shí)驗(yàn)1：統(tǒng)KNN分類。先用中科院NLPIR漢語分詞系統(tǒng)（2013版）對訓(xùn)練微博樣本集分別進(jìn)行去停用詞、切詞分詞等預(yù)處理工作得出微博的原始特征空間。再用信息增益算法計(jì)算排序，選出排名前N個特征子集構(gòu)成特征向量。在此基礎(chǔ)上對測試微博樣本用特征子集構(gòu)成向量空間模型并采用KNN分類算法進(jìn)行情感分類。文獻(xiàn)[9]對比了不同的K值得到的分類情況對比實(shí)驗(yàn)，指出K=18分類效果較佳。因此，本研究中取K=18，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 KNN輿情分類結(jié)果

實(shí)驗(yàn)2：基于粒子群聚類的微博訓(xùn)練集裁剪的KNN分類。算法參數(shù)初始化為：最大迭代次數(shù)60次，c1=c2=2，rand()為（0，1）間取隨機(jī)數(shù)，慣性權(quán)重 在迭代過程中線性下降。在實(shí)驗(yàn)過程中通過粒子群聚類將訓(xùn)練集數(shù)目從9000裁剪至6135，KNN在分類時的所需的計(jì)算工作量也減少了近1/3。從實(shí)驗(yàn)一可以看出，當(dāng)特征數(shù)為2500時輿情分類的F值達(dá)到峰值。因此我們?nèi)√卣鲾?shù)為2500，將傳統(tǒng)的KNN分類與訓(xùn)練集經(jīng)粒子群聚類裁剪后的KNN分類比對實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3所示。結(jié)果表明：使用粒子群聚類算法對微博訓(xùn)練集裁剪，減少輿情分類計(jì)算量的同時并不影響微博情感分類效果。

表3 基于粒子群聚類KNN與KNN對比

時間復(fù)雜度分析：由于在分類之前用粒子群聚類算法對微博訓(xùn)練集進(jìn)行裁剪，會有一定的時間開銷，但考慮微博輿情分類實(shí)質(zhì)上是對微博上帶有惡意、煽動及攻擊性言論及時監(jiān)控，進(jìn)而掌握網(wǎng)絡(luò)輿情動態(tài)，更多的是強(qiáng)調(diào)情感分析的實(shí)時性，而且對微博訓(xùn)練集裁剪可以在離線的環(huán)境下完成，因此，對練樣本集裁剪并不會增加分類的時間損耗。

4 結(jié)語

基于數(shù)據(jù)挖掘的微博情感分類是網(wǎng)絡(luò)輿情監(jiān)控的重要方法，KNN雖是一種有效的分類算法，但由于會受到訓(xùn)練集規(guī)模的影響導(dǎo)致分類計(jì)算量大。本文介紹基于粒子群聚類的KNN分類中訓(xùn)練集的裁剪算法。實(shí)驗(yàn)結(jié)果表明，通過對微博訓(xùn)練集的裁剪，能夠有效的降低輿情分類時的復(fù)雜度，而且還能適當(dāng)提高分類的準(zhǔn)確率。

[1]陶鵬.微時代背景下的虛擬社會治理[J].廣東行政學(xué)院學(xué)報,2015(4):46-51．

[2]CNNIC.中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報告[EB/OL].(2016-10-12)[2016-12-12].http://www.idcps.com/news/20161012/92421.html.

[3]單月光.基于微博的網(wǎng)絡(luò)輿情關(guān)鍵技術(shù)的研究與實(shí)現(xiàn)[D].成都:電子科技大學(xué),2013:1-5．

[4]Yiming Yang.A Comparative Study on Feature Selection in Text Categorization[J].The ICML97,Nashville,1997.

[5]張霞,尹怡欣,于海燕,趙海成.基于模糊粒度計(jì)算的文本聚類研究[J].計(jì)算工程與應(yīng)用,2010(13):53-55．

[6]于蘋蘋,倪建成,姚彬修,李淋淋,曹博.基于Spark框架的高效KNN中文文本分類算法[J].計(jì)算機(jī)應(yīng)用,2016(12):3292-3297.

[7]王縱虎.聚類分析優(yōu)化關(guān)鍵技術(shù)研究[D].西安:西安電子科技大學(xué),2012:66-88．

[8]彭宏,蔣洋,王軍.一種帶混合進(jìn)化機(jī)制的膜聚類算法.軟件學(xué)報[J].2015(5):1001-1012．

[9]周慶平,譚長庚,王宏君,湛淼湘.基于聚類改進(jìn)的KNN文本分類算法[J].2016(11):3374-3377．

TP-391

A

2095-7939（2017）05-0121-04

10.14060/j.issn.2095-7939.2017.05.025

2017-04-16

2017年福建省高校杰出青年科研人才培育計(jì)劃資助項(xiàng)目；福建省教育廳基金（編號：JAT160561）。

林偉（1983-），男，福建仙游人，福建警察學(xué)院偵查系講師，主要從事信息化偵查研究。

（責(zé)任編輯：于 萍）