林 偉
(福建警察學(xué)院偵查系 福建 福州 350007)
基于粒子群聚類的KNN微博輿情分類研究
林 偉
(福建警察學(xué)院偵查系 福建 福州 350007)
基于數(shù)據(jù)挖掘的微博情感分類是網(wǎng)絡(luò)輿情監(jiān)控的重要方法,其中KNN算法具有簡單有效、無需估計(jì)參數(shù)等優(yōu)點(diǎn),適用于微博輿情分類。微博輿情分類實(shí)質(zhì)上是對(duì)微博上的負(fù)面情感及時(shí)監(jiān)控,KNN會(huì)因在情感分類時(shí)處理大量的計(jì)算影響算法效率。因此,采用粒子群聚類算法在情感分類前裁剪微博訓(xùn)練樣本空間,以減少分類時(shí)的計(jì)算量。實(shí)驗(yàn)結(jié)果表明,基于粒子群聚類的KNN算法能夠有效提高微博情感分類的性能。
KNN 微博情感分類 特征選擇 粒子群聚類
隨著互聯(lián)網(wǎng)和通訊技術(shù)的發(fā)展,人們在網(wǎng)絡(luò)虛擬空間中呈現(xiàn)出的情感傾向、互動(dòng)交流等往往是現(xiàn)實(shí)社會(huì)的延伸,涉及道德、民生、貪腐等民眾關(guān)注的熱點(diǎn)敏感話題信息極易被網(wǎng)絡(luò)催生和激化,將矛盾放大、以點(diǎn)概面、以偏概全形成各類攻擊,具有強(qiáng)大的蠱惑和煽動(dòng)力,導(dǎo)致矛盾升級(jí)進(jìn)而影響社會(huì)穩(wěn)定[1]。據(jù)第38次《中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》顯示,截至2016年9月,我國微博用戶月活躍數(shù)3.906億,日活躍數(shù)1.05億,人均月使用次數(shù)52次,微博在追蹤熱點(diǎn)、發(fā)表熱點(diǎn)評(píng)論、關(guān)注興趣話題等方面都是用戶的首選平臺(tái)[2]。為此,通過數(shù)據(jù)挖掘算法對(duì)微博進(jìn)行情感分類及時(shí)監(jiān)控網(wǎng)絡(luò)上帶有煽動(dòng)、攻擊等“負(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ì)上是對(duì)微博上的“負(fù)面”情感及時(shí)監(jiān)控,KNN會(huì)因在情感分類時(shí)處理大量的計(jì)算影響算法效率。因此,本研究中將采用粒子群聚類算法在情感分類前裁剪微博訓(xùn)練樣本空間,以減少分類時(shí)的計(jì)算量。
為降低特征空間維數(shù)及計(jì)算量、防止數(shù)據(jù)過份擬合,應(yīng)從微博訓(xùn)練集的原始特征空間中按照一定的評(píng)估函數(shù)篩選出對(duì)情感分類貢獻(xiàn)較大的前N個(gè)特征子集,即特征選擇。文獻(xiàn)[4]對(duì)文本分類領(lǐng)域常見的幾種特征選擇算法進(jìn)行了詳細(xì)比較,指出信息增益(IG)和卡方統(tǒng)計(jì)(CHI)表現(xiàn)最好,因此本研究用信息增益做為特征選擇的評(píng)估函數(shù)。
信息增益是通過計(jì)算某特征詞t出現(xiàn)前后的信息熵來衡量其對(duì)分類的貢獻(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類的條件概率。
微博的內(nèi)容是方便人類閱讀的自然語言,計(jì)算機(jī)無法理解與計(jì)算,因此要對(duì)微博以結(jié)構(gòu)化的特征向量形式存儲(chǔ)以便計(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ì)算,同時(shí)將各項(xiàng)特征詞ti權(quán)值規(guī)范在[0,1]之間,其計(jì)算公式為[5]:
其中,tfij為特征詞ti在微博樣本mj中的出現(xiàn)次數(shù),N訓(xùn)練微博總數(shù),dfi是特征詞ti在微博中的文檔頻率。
KNN算法是文本分類常用的算法之一,具有簡單有效、魯棒性、無需估計(jì)參數(shù)等優(yōu)點(diǎn),應(yīng)用到微博輿情分類中其基本思想是[6]:計(jì)算待測微博樣本與已知訓(xùn)練微博樣本的情感相似度,找出與待測微博樣本相似度最大的K個(gè)最近鄰微博樣本,K個(gè)微博樣本中情感傾向較多的類別為該測試微博的情感類別,基本步驟如下:
(1)始初化K的值,K為最近鄰數(shù)。
(3)評(píng)估待試微博Mj與訓(xùn)練集中所有微博樣本Mi的情感相似度,我們使用歐式距離計(jì)算:
(4)根據(jù)公式(3)的計(jì)算結(jié)果進(jìn)行排序,選出計(jì)算值最大的K個(gè)微博,作為微博Mj情感最近鄰。
(5)計(jì)算待測試微博樣本與類別C的)情感相似度:
其中,Mj在類別 中出現(xiàn)(Mj,C)為1,否則為0,微博Mj的情感類別決策為:
雖然KNN算法簡單有效,但隨著微博訓(xùn)練集規(guī)模的增加,需要計(jì)算待測試微博樣本與訓(xùn)練集中所有微博樣本的情感相似度來找出K最近鄰,隨著大數(shù)據(jù)浪潮的到來,當(dāng)訓(xùn)練微博樣本集達(dá)到一定級(jí)別時(shí),計(jì)算與每個(gè)微博情感相似耗時(shí)將劇增,KNN算法的效率問題凸顯。特別是在輿情監(jiān)控領(lǐng)域,應(yīng)及時(shí)監(jiān)控網(wǎng)絡(luò)上帶有煽動(dòng)、攻擊等“負(fù)面”言論從而引導(dǎo)輿論導(dǎo)向,因而對(duì)情感分類算法的實(shí)時(shí)性要求高,下面討論用粒子群算法對(duì)微博訓(xùn)練集進(jìn)行裁剪,以提高KNN算法應(yīng)用在微博情感分類中的性能。
粒子群算法基本思想是[7]:隨機(jī)初始化粒子群,粒子i的位置為:Xi=(x1,x2,...,xn),飛行速度
為:Vi=(v1,v2,...,vn),Xi和Vi為n維空間。粒子i通過由目標(biāo)函數(shù)決定的適應(yīng)值來不斷迭代找到最優(yōu)解,同時(shí)通過跟蹤自己目前的最好位置pbest和粒子群全局最優(yōu)位置gbest來更新自己。找到pbest和gbest后,通過公式(6)和(7)來分別更新自己的速度與位置。
其中,Vi為粒子的速度,rand()為隨機(jī)數(shù),Xi為粒子的當(dāng)前位置,c1,c2是學(xué)習(xí)因子,ω為慣性因子。
聚類算法的基本思路就是按照一定的度量規(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是個(gè)d維的向量,N為訓(xùn)練集中微博總數(shù)。對(duì)于訓(xùn)練集M的聚類,就是通過一定算法劃分為{C1,C2,...,Cc},通過求解訓(xùn)練集中的劃分滿足以下條件:樣本情感相似度用公式(3)計(jì)算[8]。
為了發(fā)現(xiàn)c個(gè)簇的最優(yōu)劃分,聚類問題一般定義成一個(gè)性能函數(shù)的最優(yōu)(最?。﹩栴},使得類間總離散度和Jm達(dá)到最小,計(jì)算公式為:
其中,z1,z2,...,zc分 別為C1,C2,...,Cc的簇 中心。
||Mj?zi||為Mj到聚類中心zi的距離,滿足公式(9),Mj則 屬第i類。
編碼:本研究中的粒子編碼結(jié)構(gòu)如表1所示,其中z1,z2,...,zc分別是劃分為c類的每類簇中心(為d維向量,因此位置就是c×d維,每個(gè)粒子代表的是c個(gè)初始聚類中心的組合),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é)對(duì)微博進(jìn)行預(yù)處理工作,將所有樣本用向量空間模型(VSM)表示;
(2)初始化粒子群和相關(guān)參數(shù)(具體值見實(shí)驗(yàn)),從微博訓(xùn)練集中隨機(jī)選出幾個(gè)樣本為原始聚類中心,初始化P個(gè)粒子的位置編碼Xi,速度Vi=0;
(3)同時(shí)根據(jù)f(x)計(jì)算粒子的適應(yīng)度,產(chǎn)生pbest和gbest;
(4)根據(jù)公式(6)和(7)更新所有粒子的速度和位置;
(5)根據(jù)粒子聚類中心編碼,按最近鄰法則對(duì)微博樣本聚類分析及劃分,然后重新計(jì)算聚類中心并更新粒子的適應(yīng)度值;
(6)更新粒子的個(gè)最優(yōu)位置pbest和全局最位置gbest;
(7)重復(fù)步驟(4)至(6)直到達(dá)到最大迭代次數(shù)。
通過以上算法輸出以聚類中心的微博樣本調(diào)整后的裁剪訓(xùn)練集,然后采用KNN分類算法對(duì)微博進(jìn)行情感分類的處理,具體流程如圖1所示。
圖1 基于粒子群聚類的KNN微博情感分類流程
實(shí)驗(yàn)語料庫來源分別為新浪開放平臺(tái)公開的API抓取的中文微博樣本集和我們自己收集的部分私人微博,通過微博樣本的人工標(biāo)注,實(shí)驗(yàn)數(shù)據(jù)的樣本結(jié)構(gòu)如表2所示。
表2 微博樣本結(jié)構(gòu)
為了有效評(píng)價(jià)微博情感分類性能的好壞,我選取F值作為評(píng)判算法有效性的指標(biāo) ,其計(jì)算公式為:
本實(shí)驗(yàn)中切詞分詞工具選用中科院NLPIR漢語分詞系統(tǒng)(2013版),開發(fā)平臺(tái)為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版)對(duì)訓(xùn)練微博樣本集分別進(jìn)行去停用詞、切詞分詞等預(yù)處理工作得出微博的原始特征空間。再用信息增益算法計(jì)算排序,選出排名前N個(gè)特征子集構(gòu)成特征向量。在此基礎(chǔ)上對(duì)測試微博樣本用特征子集構(gòu)成向量空間模型并采用KNN分類算法進(jìn)行情感分類。文獻(xiàn)[9]對(duì)比了不同的K值得到的分類情況對(duì)比實(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在分類時(shí)的所需的計(jì)算工作量也減少了近1/3。從實(shí)驗(yàn)一可以看出,當(dāng)特征數(shù)為2500時(shí)輿情分類的F值達(dá)到峰值。因此我們?nèi)√卣鲾?shù)為2500,將傳統(tǒng)的KNN分類與訓(xùn)練集經(jīng)粒子群聚類裁剪后的KNN分類比對(duì)實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如表3所示。結(jié)果表明:使用粒子群聚類算法對(duì)微博訓(xùn)練集裁剪,減少輿情分類計(jì)算量的同時(shí)并不影響微博情感分類效果。
表3 基于粒子群聚類KNN與KNN對(duì)比
時(shí)間復(fù)雜度分析:由于在分類之前用粒子群聚類算法對(duì)微博訓(xùn)練集進(jìn)行裁剪,會(huì)有一定的時(shí)間開銷,但考慮微博輿情分類實(shí)質(zhì)上是對(duì)微博上帶有惡意、煽動(dòng)及攻擊性言論及時(shí)監(jiān)控,進(jìn)而掌握網(wǎng)絡(luò)輿情動(dòng)態(tài),更多的是強(qiáng)調(diào)情感分析的實(shí)時(shí)性,而且對(duì)微博訓(xùn)練集裁剪可以在離線的環(huán)境下完成,因此,對(duì)練樣本集裁剪并不會(huì)增加分類的時(shí)間損耗。
基于數(shù)據(jù)挖掘的微博情感分類是網(wǎng)絡(luò)輿情監(jiān)控的重要方法,KNN雖是一種有效的分類算法,但由于會(huì)受到訓(xùn)練集規(guī)模的影響導(dǎo)致分類計(jì)算量大。本文介紹基于粒子群聚類的KNN分類中訓(xùn)練集的裁剪算法。實(shí)驗(yàn)結(jié)果表明,通過對(duì)微博訓(xùn)練集的裁剪,能夠有效的降低輿情分類時(shí)的復(fù)雜度,而且還能適當(dāng)提高分類的準(zhǔn)確率。
[1]陶鵬.微時(shí)代背景下的虛擬社會(huì)治理[J].廣東行政學(xué)院學(xué)報(bào),2015(4):46-51.
[2]CNNIC.中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[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é)報(bào)[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)目;福建省教育廳基金(編號(hào):JAT160561)。
林偉(1983-),男,福建仙游人,福建警察學(xué)院偵查系講師,主要從事信息化偵查研究。
(責(zé)任編輯:于 萍)