基于關(guān)鍵句的K-means算法在熱點(diǎn)發(fā)現(xiàn)領(lǐng)域的研究與應(yīng)用

顧　俊

(貴州師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，貴州　貴陽(yáng)　550001)

?

基于關(guān)鍵句的K-means算法在熱點(diǎn)發(fā)現(xiàn)領(lǐng)域的研究與應(yīng)用

顧俊

(貴州師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，貴州貴陽(yáng)550001)

摘要：由于“互聯(lián)網(wǎng)+”提出的，網(wǎng)絡(luò)信息呈現(xiàn)爆炸的趨勢(shì)。面對(duì)海量數(shù)據(jù)如何準(zhǔn)確找到熱點(diǎn)事件成了網(wǎng)民關(guān)注的話(huà)題。文章從實(shí)際應(yīng)用出發(fā)，首先對(duì)每一篇文本選取5句話(huà)作為該文本關(guān)鍵句，然后用TF-IDF計(jì)算特征詞值，特征向量選擇時(shí)不考慮單個(gè)字的權(quán)重，再用K-means算法進(jìn)行聚類(lèi)。以新浪新聞為例，將環(huán)境、住房和違法三類(lèi)話(huà)題共322篇文本作為測(cè)試語(yǔ)料進(jìn)行聚類(lèi)，聚類(lèi)準(zhǔn)備率達(dá)到70 %以上，說(shuō)明選取關(guān)鍵句比將整個(gè)文本作為聚類(lèi)對(duì)象的聚類(lèi)效果好。

關(guān)鍵詞：文本挖掘，TF-IDF，聚類(lèi)，K-means

0引言

隨著互聯(lián)網(wǎng)+的出現(xiàn)，網(wǎng)絡(luò)數(shù)據(jù)迅速增長(zhǎng)，面對(duì)海量數(shù)據(jù)，如何快速有效地發(fā)現(xiàn)熱點(diǎn)信息成了人們?nèi)找骊P(guān)注的話(huà)題。網(wǎng)絡(luò)輿情[1][2]已經(jīng)對(duì)社會(huì)的穩(wěn)定和網(wǎng)民造成一定的影響。與一般輿情不同，網(wǎng)絡(luò)輿情具有傳播速度快、涉及范圍廣且不易被發(fā)現(xiàn)等特點(diǎn)，因此實(shí)現(xiàn)網(wǎng)絡(luò)輿情的實(shí)時(shí)監(jiān)控有一定的難度。本文利用k-means聚類(lèi)[3]算法，充分發(fā)揮文本中關(guān)鍵句的作用，從而達(dá)到熱點(diǎn)發(fā)現(xiàn)[4]的目的，為輿情監(jiān)控提供可能。

1相關(guān)研究

文本聚類(lèi)的研究方法比較多，但相對(duì)來(lái)講這些方法主要用于實(shí)驗(yàn)室研究階段，在實(shí)際商業(yè)應(yīng)用中還是一些簡(jiǎn)單大眾的方法。目前的聚類(lèi)方法分為是基于語(yǔ)義相似度[5]聚類(lèi)的研究和基于關(guān)系聚類(lèi)[6]的研究。

基于語(yǔ)義相似度聚類(lèi)[7]的研究方法主要有兩種：一種是利用語(yǔ)義詞典將相關(guān)詞放在一個(gè)樹(shù)形結(jié)構(gòu)中來(lái)計(jì)算其權(quán)重；另一種是綜合考慮文本上下文語(yǔ)境的信息，利用統(tǒng)計(jì)學(xué)的方法來(lái)計(jì)算詞的權(quán)重。前一種權(quán)重的計(jì)算方法相對(duì)來(lái)說(shuō)比較成熟，文獻(xiàn)[8]和[9]都是基于樹(shù)型結(jié)構(gòu)的語(yǔ)義網(wǎng)絡(luò)權(quán)重計(jì)算方法。上下文語(yǔ)境的統(tǒng)計(jì)方法是對(duì)基于語(yǔ)料庫(kù)的詞語(yǔ)相似度的計(jì)算方法，不同詞語(yǔ)語(yǔ)義相近當(dāng)且僅當(dāng)它們處在相似的上下文語(yǔ)境里，因此對(duì)語(yǔ)料庫(kù)具有較強(qiáng)地依賴(lài)性并伴有噪聲。

基于關(guān)系聚類(lèi)[10][11]的研究，不同詞之間相似度的確定不僅要考慮詞的屬性還要考慮它們之間的相互聯(lián)系。2001年，Taskar等人提出了基于似然關(guān)系聚類(lèi)方法的模型；2003年，Neville等人又提出了基于圖形分解和數(shù)據(jù)聚類(lèi)相結(jié)合的關(guān)系聚類(lèi)模型；2006年，Bhattacharya等人將實(shí)體識(shí)別也歸為關(guān)系聚類(lèi)問(wèn)題，基于層次的聚類(lèi)算法[12]在聚類(lèi)過(guò)程中除了要計(jì)算屬性邊之外，還利用關(guān)系邊來(lái)表示不同實(shí)體間的關(guān)系。

2文本預(yù)處理

文本預(yù)處理是聚類(lèi)中重要環(huán)節(jié)之一，它的目的是盡可能的消除文本中的垃圾詞，提高文本的質(zhì)量，它是后期文本能否準(zhǔn)確聚類(lèi)的前提。

預(yù)處理的第一步是對(duì)文本進(jìn)行分詞。中文分詞與英文分詞不同，英文單詞之間有間隔可以以此為依據(jù)進(jìn)行分詞，而中文沒(méi)有這一特性因此中文分詞相對(duì)來(lái)說(shuō)比較麻煩。本文采用ansj分詞系統(tǒng)來(lái)對(duì)文本進(jìn)行分詞。

其次，去掉分詞后文本中的標(biāo)點(diǎn)符號(hào)。因?yàn)樵诰垲?lèi)過(guò)程中不考慮文本情感方面，故這些標(biāo)點(diǎn)符號(hào)在后面的處理過(guò)程中沒(méi)有實(shí)際作用。

最后，停用詞的去除。如：的、此外、啊、呀、以前、幾個(gè)……之類(lèi)的詞，這些虛詞在文本會(huì)多次出現(xiàn)而且對(duì)文章來(lái)說(shuō)沒(méi)有實(shí)際意義，如果不進(jìn)行處理，在后期特征選擇時(shí)不僅增加文本計(jì)算量，而且得到的特征不具有代表性，直接影響聚類(lèi)的效果。

3特征獲取

TF-IDF[13]是數(shù)據(jù)挖掘[14]中常用的加權(quán)技術(shù)，用來(lái)評(píng)估字詞在語(yǔ)料中的重要程度。字詞的重要性與它在文本中出現(xiàn)的次數(shù)成正比，與它在整個(gè)語(yǔ)料中出現(xiàn)的次數(shù)成反比。如果一個(gè)字詞在一篇文本中出現(xiàn)的頻率高并且在其它文檔中出現(xiàn)少，那么， 該字詞在聚類(lèi)算法中就是很好的特征詞。

為了提高聚類(lèi)的準(zhǔn)備性和特征詞效果，本文兩次應(yīng)用TF-IDF，先從每篇文本中選出權(quán)重最大的5個(gè)句子作為該文本的關(guān)鍵句，再?gòu)挠嘘P(guān)鍵句中選擇特征詞。在特征詞選擇方面，因?yàn)閱蝹€(gè)字的意義不大，因此即便算出來(lái)權(quán)重很大，本文也不將其作為特征詞。

4模型選擇

聚類(lèi)是一個(gè)無(wú)監(jiān)督的過(guò)程，因此并不需要訓(xùn)練數(shù)據(jù)，只要知道如何計(jì)算相似度將相似的東西聚到一起就可以了。K-means算法較成熟、易于實(shí)現(xiàn)且聚類(lèi)效果也較好，本文采用K-means模型聚類(lèi)。其中心思想是：首先隨機(jī)選取K個(gè)點(diǎn)作為中心點(diǎn)，依次計(jì)算其余各點(diǎn)到它們的距離，將所有的點(diǎn)分別歸到最靠近它們的中心點(diǎn)所在的類(lèi)；然后利用迭代的方法，計(jì)算出新的K個(gè)中心點(diǎn)，重新聚類(lèi)，直到收斂為止。

5實(shí)驗(yàn)過(guò)程

1)語(yǔ)料獲取。利用爬蟲(chóng)程序從新浪網(wǎng)獲取數(shù)據(jù)，然后人工進(jìn)行過(guò)濾、篩選，得到想要的理想數(shù)據(jù)。

2)預(yù)處理。利用分詞模塊和停用詞表對(duì)獲取的語(yǔ)料集進(jìn)行預(yù)處理，去掉預(yù)料中的噪聲。

3)文本表示。用向量空間模型(SVM)將文本以形式化的方式表示出來(lái)，以便計(jì)算機(jī)識(shí)別處理。

4)計(jì)算每篇文本中的句子權(quán)重，從每一篇文本中提取權(quán)重最大的五句話(huà)作為該篇文本的代表，以句號(hào)、感嘆號(hào)、問(wèn)號(hào)、省略號(hào)表示文本中一句話(huà)的結(jié)束，M表示該文本中的總句數(shù)。對(duì)預(yù)處理后的文本用局部TF-IDF計(jì)算每個(gè)詞的權(quán)重，文本中每一句話(huà)中的每個(gè)詞的權(quán)重相加后再除以詞的數(shù)量為該句權(quán)重的計(jì)算的一部分，即

W(第i句中單詞)=(w1+w2+……+wn)/n

(1)

其中，tf(i)表示詞i在整個(gè)文本中出現(xiàn)的詞數(shù)，df(i)表示出現(xiàn)詞i的文本數(shù)，D表示文本總數(shù)，n表示該句中出現(xiàn)的詞數(shù)；同時(shí)考慮句子在文本中出現(xiàn)的位置，一般說(shuō)來(lái)文本開(kāi)頭和結(jié)尾的句子比較重要賦予權(quán)重為1，首尾依次遞減1 /M。即

(2)

5)特征選擇。根據(jù)步驟4可以得到的每篇文本權(quán)重最大的五個(gè)句子，再?gòu)娜挚紤]用TF-IDF計(jì)算單詞權(quán)重，從而選出特征詞。

(3)

其中N表示句中的總詞數(shù)，nt表示詞t出現(xiàn)的次數(shù)，D表示文本總數(shù)，dt表示出現(xiàn)詞t的文本數(shù)。

6)利用K-means聚類(lèi)。文本集合為{X1，X2，…… ，Xn}，其中Xi代表一個(gè)d維向量的文本。類(lèi)別質(zhì)心的計(jì)算方法是根據(jù)歐式距離對(duì)給定的聚類(lèi)數(shù)K通過(guò)不斷迭代直到質(zhì)心不變，即將文本分為K類(lèi)S={S1，S2，……，Sk}需要滿(mǎn)足的終止條件是：

(4)

其中ui表示Si的平均值。

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

6.1評(píng)價(jià)指標(biāo)

本文主要通過(guò)以下四種方法來(lái)評(píng)估[15]聚類(lèi)性能的好壞：準(zhǔn)確率(Precision)、召回率(Recall)、Rand Index和F1值。

準(zhǔn)確率反映的是聚類(lèi)模型能正確發(fā)現(xiàn)熱點(diǎn)的能力，召回率反映的是聚類(lèi)模型發(fā)現(xiàn)熱點(diǎn)的文本數(shù)與文本庫(kù)中所有相關(guān)熱點(diǎn)文本數(shù)的比例。

(5)

RI利用排列組合的原理對(duì)聚類(lèi)算法性能進(jìn)行評(píng)價(jià)。公式如下：

(6)

其中TP指同類(lèi)文本正確地聚在一起；TN指不相同類(lèi)文本正確地聚成了不同的類(lèi)；FP指不相同類(lèi)文本被錯(cuò)誤地聚在一起；FN指同類(lèi)文本錯(cuò)誤地聚成了不相同類(lèi)。與F1值不同，RI將準(zhǔn)確率和召回率看的同等重要。

F1值也稱(chēng)調(diào)和均值，是準(zhǔn)確率和召回率的平均值。公式如下：

(7)

6.2結(jié)果分析

本實(shí)驗(yàn)使用的文本是爬蟲(chóng)程序從新浪網(wǎng)上獲取的有關(guān)環(huán)境、住房和違法三類(lèi)新聞事件，然后經(jīng)過(guò)人工過(guò)濾篩選出的322個(gè)文本作為本實(shí)驗(yàn)的測(cè)試數(shù)據(jù)，并做文本關(guān)鍵句提取前、后實(shí)驗(yàn)對(duì)比。

表1為直接對(duì)這322篇文章所有內(nèi)容在不同特征維數(shù)上聚類(lèi)的結(jié)果。從表中可以看出雖特征維數(shù)為100時(shí)，聚類(lèi)效果最好，但F1值也只60 %。由于文本中包含許多噪聲句從而導(dǎo)致聚類(lèi)結(jié)果不是很理想。

表1　基于全文的聚類(lèi)結(jié)果

表2 為對(duì)這322篇文本提取文本關(guān)鍵句后，不同特征維數(shù)上的聚類(lèi)結(jié)果。從表中可以看出：提取文本關(guān)鍵句后再聚類(lèi)，特征向量維數(shù)明顯降低，提高了計(jì)算速度；當(dāng)特征向量取50維時(shí)，聚類(lèi)準(zhǔn)確率高達(dá)80.53 %，F(xiàn)1值也明顯高于前者達(dá)77.9 %，聚類(lèi)的性能和穩(wěn)定性得到了提升。

表2　基于關(guān)鍵句的聚類(lèi)結(jié)果

通過(guò)以上兩個(gè)實(shí)驗(yàn)可以知道：在熱點(diǎn)發(fā)現(xiàn)方面，先提取文本的關(guān)鍵句后再聚類(lèi)比直接對(duì)文本進(jìn)行聚類(lèi)的效果要好，并且隨著特征向量維數(shù)的增加聚類(lèi)準(zhǔn)確率也隨之增加；但是當(dāng)特征向量維數(shù)增加到一定數(shù)量的時(shí)候，聚類(lèi)的準(zhǔn)確率不僅沒(méi)有增長(zhǎng)，反而下降。

6.3誤差分析

主要從文本和關(guān)鍵句兩個(gè)方面分析誤差：

1)訓(xùn)練文本分布不均勻。三個(gè)類(lèi)別的文本數(shù)不相等，而且這些數(shù)據(jù)是人工進(jìn)行標(biāo)注的，難以避免主觀(guān)思想的左右，導(dǎo)致標(biāo)類(lèi)時(shí)就不準(zhǔn)確。

2)文章關(guān)鍵句選擇上的誤差。在提取文本關(guān)鍵句時(shí)選出的句子并不是很理想，包含噪聲而且每篇文本的長(zhǎng)短不一，具體取多少句子能恰到好處地表示文本，這些方面有待進(jìn)一步深度思考。

以上就是為什么本文聚類(lèi)的準(zhǔn)確率只有70 %左右的原因之一。

7總結(jié)

本文從新浪網(wǎng)獲取的環(huán)境、住房和違法三類(lèi)數(shù)據(jù)出發(fā)，分析聚類(lèi)在熱點(diǎn)發(fā)現(xiàn)領(lǐng)域中的應(yīng)用。以文本的關(guān)鍵句作為核心數(shù)據(jù)分析K-means聚類(lèi)的準(zhǔn)確性。從結(jié)果可以看出用文本的關(guān)鍵句進(jìn)行聚類(lèi)比直接用全部文本內(nèi)容進(jìn)行聚類(lèi)的效果要好。在未來(lái)的工作中，將從以下幾個(gè)方面來(lái)改進(jìn)：第一，在數(shù)據(jù)獲取方面，盡量獲取比較純的文本而且文本類(lèi)別分類(lèi)很清楚，不存在類(lèi)別模棱兩可的文本。第二，對(duì)于每一篇文本，怎樣才能取到合適的句子準(zhǔn)確的表達(dá)該篇文本的內(nèi)容？第三，在特征選擇方面，如何降低噪聲詞的影響，使用更低維特征向量就能把表示不相同類(lèi)的文本信息。

參考文獻(xiàn)【REFERENCES】

[1]王偉，許鑫.基于聚類(lèi)的網(wǎng)絡(luò)輿情熱點(diǎn)發(fā)現(xiàn)及分析[J].現(xiàn)代圖書(shū)情報(bào)技術(shù)，2009(03)74-79.

WANG W，XU X.Online public Opinion hotspot detection and analysis based on document clustering[J].New Technology of Library and Information Service，2009(03)74-79.

[2]鄭軍.網(wǎng)絡(luò)輿情監(jiān)控的熱點(diǎn)發(fā)現(xiàn)算法研究[D].哈爾濱工程大學(xué)，2007.

[3]王千，王成，馮振元，等.K-means聚類(lèi)算法研究綜述[J].電子設(shè)計(jì)工程，2012(07)21-24.

WANG Q，WANG C，F(xiàn)ENG Z Y，et al.Review of K-means clustering algorithm[J].Electronic Design Engineering，2012(07)21-24.

[4]盛宇.基于微博的學(xué)科熱點(diǎn)發(fā)現(xiàn)、追蹤與分析——以數(shù)據(jù)挖掘領(lǐng)域?yàn)槔齕J].圖書(shū)情報(bào)工作，2012(08)32-37.

SHENG Y.Subject hotspots discovery，tracking and analysis based on microblog-take the field of data mining as an example[J].Library and Information Service，2012(08)32-37.

[5]劉宏哲.文本語(yǔ)義相似度計(jì)算方法研究[D].北京交通大學(xué)，2012.

LIU H Z.Research on semantic similarity measurement for text[D].Beijing Jiaotong University，2012.

[6]高瀅.多關(guān)系聚類(lèi)分析方法研究[D].吉林大學(xué)，2008.

GAO Y.Research on Multi-relational clustering analysis approaches[D].Changchun：Jilin University，2008.

[7]焦芬芬.基于概念和語(yǔ)義相似度的文本聚類(lèi)算法[J].計(jì)算機(jī)工程與應(yīng)用，2012(18)136-141.

JIAO F F.Clustering method based on concept and semantic similarity[J].Computer Engineering and Applications，2012(18)136-141.

[8]馮永，李華，吳中福，等.基于擴(kuò)展語(yǔ)義網(wǎng)的知識(shí)資源組織技術(shù)研究[J].計(jì)算機(jī)科學(xué)，2008(03)139-141+185.

FENG Y，LI H，WU Z F，et al.Knowledge resources organization technology research based on expended semantic web[J].Computer Science，2008(03)139-141+185.

[9]姜洪強(qiáng).基于語(yǔ)義Web文檔的索引技術(shù)研究[D].北京工業(yè)大學(xué)，2010.

[10]WANG J D，ZENG H J，CHEN Z，et al.ReCoM：reinforcement clustering of multi-type interrelated data objects[C] // Proceeding of the 26th annual international ACM SIGIR conference on Research and development in information retrieval.New York：ACM Publisher，2003：274-281.

[11]LONG B，ZHANG M，WU X，et al.Spectral clustering for multi-type relational data[C] // Proceedings of the 23rd International Conference on Machine Learning.New York：ACM Publisher，2006：585-592.

[12]段明秀.層次聚類(lèi)算法的研究及應(yīng)用[D].中南大學(xué)，2009.

[13]韓敏，唐常杰，段磊，等.基于TF-IDF相似度的標(biāo)簽聚類(lèi)方法[J].計(jì)算機(jī)科學(xué)與探索，2010(03)240-246.

HAN M，TANG C J，DUAN L，et al.TI-IDF similarity based method for tag clustering[J].Journal of Forntiers of computer science & Technology，2010(03)240-246.

[14]申彥.大規(guī)模數(shù)據(jù)集高效數(shù)據(jù)挖掘算法研究[D].江蘇大學(xué)，2013.

SHEN Y.The research of high effcient data mining algorithms for massive data sets[D].Xhenjiang：Jiangsu University，2013.

[15]李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京：清華大學(xué)出版社，2012.

收稿日期：2016-03-31；修回日期：2016-04-13

作者簡(jiǎn)介：顧俊(1989-)，男(漢族)，安徽馬鞍山人，貴州師范大學(xué)，研究生，主要從事自然語(yǔ)言處理研究。

中圖分類(lèi)號(hào)：TP391.1；N37

文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1003-6563(2016)03-0093-04

The research and application of K - Means algorithm based on key sentence in the field of hot spots

GU Jun

(GuiZhouNormalUniversity，MathematicsandComputerScience，Guiyang550001，China)

Abstract：Due to the proposing of Internet +，network information shows the tendency of explosion.How to accurately find a hot issue in the face of massive data has become a concern of Internet users.This paper starts from the practical application，firstly five sentences are selected from every text as the key sentences；then TF-IDF is used to calculate the weight of characteristic words and the weight of a word wouldn’t be taken into account when selecting feature vectors；Lastly it utilizes K-means algorithm for clustering.Taking Sina News as an example，three kinds of topics including Environment，Housing and Illegitimacy contain 322 texts totally，which are clustered as test corpus，and clustering preparation rate reaches more than 70 %.The result shows that the key sentence extraction is better than that of the whole text as hot spot of clustering object.

Keywords：text mining，TF-IDF，cluster，K-Means