羅旭，歐陽(yáng)純萍，劉志明（南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，衡陽(yáng)　421000）

?

基于聚類(lèi)的熱詞發(fā)現(xiàn)與關(guān)聯(lián)分析

羅旭，歐陽(yáng)純萍，劉志明
（南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，衡陽(yáng)421000）

摘要：

關(guān)鍵詞：

0　引言

隨著互聯(lián)網(wǎng)的日益普及，網(wǎng)絡(luò)往往成為有影響力事件發(fā)布的第一平臺(tái)，然而網(wǎng)絡(luò)上產(chǎn)生新聞的速度遠(yuǎn)遠(yuǎn)超過(guò)人所接受的程度，如果采用人工分檢的方法，肯定不能達(dá)到快速得知當(dāng)前互聯(lián)網(wǎng)的熱點(diǎn)信息。因此，對(duì)熱詞進(jìn)行快速識(shí)別，并對(duì)我們想要了解的熱詞加以關(guān)注，迅速分類(lèi)與這些熱詞相關(guān)的新聞，可以快速了解當(dāng)前輿情，及時(shí)對(duì)熱點(diǎn)信息作出處理。

在新聞話(huà)題的發(fā)現(xiàn)技術(shù)中，聚類(lèi)算法應(yīng)用較廣。習(xí)婷等[1]將兩種聚類(lèi)算法Single-Pass和K-means進(jìn)行了比較，認(rèn)為K-means雖然錯(cuò)檢率和漏檢率較低，但具有需要預(yù)先制定聚類(lèi)數(shù)目和隨機(jī)初始化的缺點(diǎn)。王偉等[2]通過(guò)對(duì)樣本網(wǎng)頁(yè)文本的特征提取，構(gòu)建文本向量空間模型，使用OPT ICS聚類(lèi)算法獲取網(wǎng)頁(yè)熱點(diǎn)簇，并且為了更加精確，還根據(jù)熱點(diǎn)簇特征向量對(duì)網(wǎng)頁(yè)進(jìn)行二次聚類(lèi)，從而獲取關(guān)于輿情的時(shí)間演變模式。袁方等[3]為了改善傳統(tǒng)K-means對(duì)初始聚類(lèi)中心敏感，計(jì)算每個(gè)數(shù)據(jù)對(duì)象所在區(qū)域的密度，選擇相互距離最遠(yuǎn)的k個(gè)處于高密度區(qū)域的點(diǎn)作為初始聚類(lèi)中心，得到較好的聚類(lèi)結(jié)果。

在如何得到熱詞關(guān)聯(lián)關(guān)系中，李渝勤等[4]采用命名實(shí)體識(shí)別技術(shù)和高頻串統(tǒng)計(jì)技術(shù)進(jìn)行短語(yǔ)串的劃分，再進(jìn)行熱度權(quán)值的計(jì)算，通過(guò)同現(xiàn)率的原則確定熱詞類(lèi)之間的關(guān)聯(lián)計(jì)算。

僅僅依靠同現(xiàn)率來(lái)確定熱詞類(lèi)之間的關(guān)聯(lián)度存在一定的局限性，熱詞的出現(xiàn)是成簇的出現(xiàn)的，因此本文將新聞話(huà)題與熱詞關(guān)聯(lián)結(jié)合起來(lái)，選擇K-means聚類(lèi)算法得到話(huà)題，由話(huà)題得到相應(yīng)的熱詞類(lèi)簇，再由熱詞類(lèi)簇計(jì)算熱詞關(guān)聯(lián)度。較為有效地展現(xiàn)當(dāng)前的熱詞類(lèi)的分布以及熱詞之間的關(guān)系。

1　熱詞發(fā)現(xiàn)系統(tǒng)功能及方案設(shè)計(jì)

以“南華大學(xué)”為新聞?shì)浨楸O(jiān)測(cè)目標(biāo)，具體提供熱詞統(tǒng)計(jì)，展示熱詞關(guān)聯(lián)關(guān)系等功能。我們圍繞這些功能，主要完成以下工作：第一，將新聞從數(shù)據(jù)庫(kù)中提取并進(jìn)行分詞，以及去除停用詞等預(yù)處理；第二，在熱詞發(fā)現(xiàn)模塊，進(jìn)行tf-idf計(jì)算以構(gòu)建VSM模型，然后使用K-means聚類(lèi)算法對(duì)新聞進(jìn)行聚類(lèi)，得到熱詞類(lèi)簇并進(jìn)行相應(yīng)處理；第三，計(jì)算熱詞關(guān)聯(lián)度，由聚類(lèi)得到的熱詞類(lèi)簇和新聞同現(xiàn)率等結(jié)合一塊得到熱詞關(guān)聯(lián)關(guān)系，最后進(jìn)行展示。具體步驟之間的聯(lián)系如圖1所示：

圖1　熱詞發(fā)現(xiàn)與關(guān)聯(lián)分析框圖

2　熱詞發(fā)現(xiàn)與關(guān)聯(lián)分析關(guān)鍵技術(shù)

2.1VSM模型構(gòu)建

在最開(kāi)始對(duì)新聞文本做分詞處理，采用開(kāi)源的Hanlp漢語(yǔ)言處理包中基于條件隨機(jī)場(chǎng)的分詞方法。在熱詞中，往往新詞出現(xiàn)的頻率較高，采用CRF分詞較為合理。

要得到一篇文本的向量空間模型，首先得計(jì)算文本中每一個(gè)詞匯的權(quán)重大小。本文采用以TF-IDF值作為詞匯的權(quán)重值，首先計(jì)算加權(quán)詞頻因子tf，以計(jì)算詞匯在文本出現(xiàn)的頻率作為tf值。

IDF逆向文件頻率是一個(gè)詞語(yǔ)普遍重要性的度量。某一特定詞語(yǔ)的IDF，可以由總文件數(shù)目除以包含該詞語(yǔ)的文件的數(shù)目，再將得到的商取對(duì)數(shù)得到：

在此之上，結(jié)合了出現(xiàn)在文檔中不同位置的詞的特性[5]，如meta中keyword、title和description等關(guān)鍵詞在文檔中的權(quán)重，因此tf值為

f（t，body）表示是詞匯在文本正文中出現(xiàn)，f（t，meta）則是在網(wǎng)頁(yè)的meta信息中出現(xiàn)，f函數(shù)對(duì)應(yīng)各自詞匯的tf-idf值，w1，w2，w3是相應(yīng)的權(quán)重系數(shù)。

在計(jì)算idf的過(guò)程，因?yàn)樾枰玫桨摦?dāng)前詞匯的文件的數(shù)目，需要多次遍歷計(jì)算，本系統(tǒng)因此做相應(yīng)的優(yōu)化，預(yù)處理各個(gè)詞匯的idf值，使得計(jì)算速度大大加快，算法復(fù)雜度由O（n2）降到O（nlogn）。

接下來(lái)進(jìn)行特征選取，如果抽取所有文本詞匯作為文本特征向量集合，因?yàn)榉衷~之后的詞匯量極大，因此有必要對(duì)文本特征向量集合做降維處理，根據(jù)詞權(quán)值篩選出部分詞匯作為全局文本特征向量。最后就是建立每一篇文本新聞的向量空間模型，對(duì)應(yīng)每一篇文本新聞，將其自身的文本特種向量投影到全局文本特征向量，由此可得到向量空間模型。對(duì)于每個(gè)新聞文本i，設(shè)Ti為其特征向量，k（i，j）是全局特征向量中的詞，w （i，j）是其在當(dāng)前文本i中詞匯j對(duì)應(yīng)的特征權(quán)值，m為全局特征詞向量中的總個(gè)數(shù)，文本可表示為T(mén)i=[（ki，1，wi，1），（ki，2，wi，2），（ki，3，wi，3），…，（ki，j，wi，j），…，（ki，m）]。

因?yàn)楦鱾€(gè)詞匯的特征權(quán)值因?yàn)樾侣勎谋镜牟町悾瑫?huì)導(dǎo)致某些值過(guò)于太大或太小以至于某一維或某幾維對(duì)數(shù)據(jù)影響過(guò)大，因此對(duì)向量進(jìn)行歸一化處理，對(duì)于在特征向量中的每一個(gè)詞

2.2話(huà)題聚類(lèi)

聚類(lèi)可以認(rèn)為是非監(jiān)督學(xué)習(xí)中最重要的問(wèn)題。K-means算法基于目標(biāo)的特征將目標(biāo)分為K類(lèi)，K為事先定義。基本思想就是定義K個(gè)中心，每一類(lèi)簇都有一個(gè)中心，類(lèi)簇里的物體是以計(jì)算相似度函數(shù)的大小為基準(zhǔn)相對(duì)靠近而聚集。

算法步驟如下：預(yù)先定義K大小，隨機(jī)選擇K個(gè)文本向量作為中心，之后對(duì)于剩下的每一個(gè)文本，計(jì)算其到每一個(gè)類(lèi)簇中心的歐幾里得距離，并將其劃分到最近的類(lèi)簇中，遍歷分配完后，重新計(jì)算每個(gè)類(lèi)簇的中心，不斷循環(huán)直到1.聚類(lèi)中心不再移動(dòng)或者2.迭代次數(shù)達(dá)到指定次數(shù)。算法時(shí)間復(fù)雜度是O（K*N*T），k是中心個(gè)數(shù)，N數(shù)據(jù)集的大小，T是迭代次數(shù)。

在選取初始中心時(shí)，算法對(duì)初始聚類(lèi)中心敏感，從不同的初始聚類(lèi)中心出發(fā)，得到的聚類(lèi)結(jié)果也不一樣，并且一般不會(huì)得到全局最優(yōu)解。本系統(tǒng)則采用取相互距離最遠(yuǎn)的k個(gè)點(diǎn)作為初始中心，消除算法對(duì)初始聚類(lèi)中心的敏感性，并能得到較好的聚類(lèi)結(jié)果[3]。

對(duì)于文本相似度計(jì)算，采用了比較傳統(tǒng)的夾角余弦值計(jì)算各特征項(xiàng)之間的距離，并且同各個(gè)類(lèi)簇中心的值作比較，歸類(lèi)到一個(gè)和其相似度最大的類(lèi)簇。向量A與向量B的夾角余弦值如下計(jì)算：

2.3熱詞關(guān)聯(lián)分析

熱詞與熱詞之間是有聯(lián)系的，這一塊將之前話(huà)題聚類(lèi)得的話(huà)題進(jìn)一步處理，得到詞與詞之間，詞群與詞群之間的聯(lián)系。

具體步驟如下：取SVM向量模型中的全局文本特征向量作為展示熱詞。聯(lián)系的表現(xiàn)形式為矩陣，兩兩之間有相應(yīng)對(duì)應(yīng)關(guān)系，關(guān)系權(quán)值即為熱詞的關(guān)聯(lián)度。矩陣由三個(gè)部分構(gòu)成，新聞同現(xiàn)率矩陣，類(lèi)別距離矩陣，熱詞同現(xiàn)矩陣。三個(gè)矩陣賦予相應(yīng)的權(quán)重系數(shù)，進(jìn)行累加既可得到最終的熱詞關(guān)聯(lián)矩陣。

（1）新聞同現(xiàn)率矩陣定義為任意兩個(gè)熱詞代表的新聞集合中重疊的大小。在之前的聚類(lèi)模塊中，可以得到每個(gè)熱詞具有的新聞集合，遍歷兩者既可得到相應(yīng)的重疊率。

（2）類(lèi)別距離矩陣定義為由聚類(lèi)得到不同的詞群，詞群內(nèi)部的關(guān)聯(lián)度以及詞群與詞群的關(guān)聯(lián)度就是類(lèi)別距離矩陣。遍歷每一個(gè)類(lèi)簇中心，在這里稱(chēng)為詞群，得到中心權(quán)重向量，為不保證權(quán)重太大或太小，進(jìn)行歸一化處理。在這里，因?yàn)樵~與詞互相都有關(guān)聯(lián)，矩陣將兩步處理，第一步，在同一個(gè)詞群里的詞匯，以權(quán)重最大的詞為中心點(diǎn)，其他詞只與這個(gè)中心點(diǎn)形成關(guān)聯(lián)，這樣形成一個(gè)星狀的發(fā)散結(jié)構(gòu)，使得展示較為明晰。第二步，對(duì)于其它詞也就是其他詞群的詞，以較小權(quán)值向量作為關(guān)聯(lián)值。

（3）熱詞同現(xiàn)矩陣定義為兩個(gè)熱詞在同一文章中出現(xiàn)的幾率。因此遍歷所有新聞查看是否有同時(shí)出現(xiàn)即可。

最后，新聞同現(xiàn)率和熱詞同現(xiàn)矩陣都要進(jìn)行矩陣歸一化處理，要保證矩陣最后均要大于零，

同時(shí)考慮到矩陣中大部分關(guān)聯(lián)值為零，歸一化反而使得這些值不為零，所以特殊化處理，不考慮這些零值。三者矩陣加權(quán)累加即可得到關(guān)聯(lián)矩陣。

3　系統(tǒng)實(shí)現(xiàn)

本系統(tǒng)以南華大學(xué)相關(guān)新聞為輿情監(jiān)測(cè)目標(biāo)，因此采集的新聞也以南華大學(xué)新聞為主，選擇2015-08-28到2015-10-04之間新浪、騰訊、紅網(wǎng)、鳳凰等有關(guān)南華大學(xué)的298篇新聞。因?yàn)樾侣剚?lái)源廣泛，內(nèi)容復(fù)雜隨機(jī)，可能會(huì)引入不相干的數(shù)據(jù)。因此，在分詞階段還要進(jìn)行相應(yīng)的過(guò)濾，去除與南華大學(xué)不相關(guān)的“香港《南華早報(bào)》”新聞，“臺(tái)灣南華大學(xué)”等，以及去除相應(yīng)的停留詞。

得到所有新聞分詞后的詞匯后，對(duì)這些進(jìn)行tf-idf值計(jì)算，根據(jù)各個(gè)詞的tf-idf值進(jìn)行排序，篩選出10％的詞匯，去重，作為全局文本特征向量。其次建立VSM模型，例如隨機(jī)抽取一篇來(lái)自新浪的新聞“南華大學(xué)分專(zhuān)業(yè)靠抓鬮招生后細(xì)化專(zhuān)業(yè)如何分流？”，其部分特征向量權(quán)重值如表1所示。

通過(guò)K-means獲得K個(gè)類(lèi)簇中心，這里預(yù)先指定k=5，從而聚類(lèi)獲得5個(gè)新聞熱點(diǎn)類(lèi)簇。具體如表二所示：

表2　新聞熱點(diǎn)類(lèi)簇

可以看到雖然新聞的熱點(diǎn)信息多樣化，但是聚類(lèi)還是能夠取得一個(gè)比較明顯的熱點(diǎn)區(qū)分。但是在各個(gè)熱點(diǎn)類(lèi)簇下還存在著很多與此熱點(diǎn)不相干的新聞，精度還需要有所提高。

表1　新聞VSM模型

在得到熱點(diǎn)類(lèi)簇后，要對(duì)熱詞進(jìn)行處理，添加熱詞的情感的褒貶程度以及敏感程度，進(jìn)而得到每個(gè)熱詞的熱度，并且根據(jù)類(lèi)簇添加與之相關(guān)的新聞。因在展示時(shí)，熱詞不能太多，將全局特征詞按照熱詞熱度權(quán)值進(jìn)行過(guò)濾，只獲取1.5％的熱詞。由熱詞關(guān)聯(lián)度模塊得到關(guān)聯(lián)矩陣。進(jìn)行展示如圖2所示：

圖2　熱詞關(guān)聯(lián)展示

圖中關(guān)于“專(zhuān)業(yè)靠抓鬮”以及“海軍先進(jìn)事跡報(bào)告”的新聞熱詞較為集中，清晰地展現(xiàn)了兩個(gè)事件具有很高的熱度。根據(jù)圖中節(jié)點(diǎn)的大小來(lái)展示不同的熱度值，熱度越高的詞所在的節(jié)點(diǎn)面積將越大。例如，“專(zhuān)業(yè)”在這些新聞里具有極高熱度因此也是最為明顯的。但是不少的雜詞的混入以及詞匯的相對(duì)松散，導(dǎo)致其余熱詞事件不夠明顯。

4　結(jié)語(yǔ)

熱詞發(fā)現(xiàn)及關(guān)聯(lián)分析已經(jīng)被廣泛應(yīng)用，能夠較為清晰地反映當(dāng)前發(fā)生的新聞事件。本文提出把K-means聚類(lèi)算法得到的話(huà)題運(yùn)用到計(jì)算熱詞關(guān)聯(lián)度上，能夠有效地提供熱詞統(tǒng)計(jì)，展示熱詞關(guān)聯(lián)關(guān)系。然而K-means聚類(lèi)算法具有必須預(yù)先指定K數(shù)目，才能進(jìn)行聚類(lèi)的缺陷。但在實(shí)際中，熱點(diǎn)數(shù)目往往是未知的，具有不確定性，因此可以考慮采用改進(jìn)的Single-Pass增量聚類(lèi)等算法替代K-means算法。另外，在熱詞選擇中，熱詞隨時(shí)間推移會(huì)出現(xiàn)突然的變化，即時(shí)間因子對(duì)于熱詞具有非常明顯的印象，因此下一步可以將時(shí)間因素考慮進(jìn)去。

參考文獻(xiàn)：

[1]Ting，X.and L.Jufang，A Comparative Study between Single-Pass Algorithm and K-means Algorithm in Web Topic Detection.Atlantis Press，2014.

[2]Wei，W.，X.Xin.基于聚類(lèi)的網(wǎng)絡(luò)輿情熱點(diǎn)發(fā)現(xiàn)及分析*.現(xiàn)代圖書(shū)情報(bào)技術(shù)，2009，3（3）：74-79.

[3]袁方，周志勇，宋鑫，初始聚類(lèi)中心優(yōu)化的K-means算法[J].計(jì)算機(jī)工程，2007，33（3）：65-66.

[4]李渝勤，孫麗華，面向互聯(lián)網(wǎng)輿情的熱詞分析技術(shù).中文信息學(xué)報(bào)，2011，25（1）：48-53.

[5]GESANG，D.，et al..基于Single-Pass的網(wǎng)絡(luò)輿情熱點(diǎn)發(fā)現(xiàn)算法.電子科技大學(xué)學(xué)報(bào)，2015（4）.

Hot-Word Detection and Relations Analysis Based on Document Clustering

LUO Xu，OUYANG Chun-ping，LIU Zhi-ming
（School of Computer Science and Technology，University of South China，Hengyang 421000）

Abstract：

Proposes a method to discover hot-word relations based on topic clustering.For word discovering，vector space mode is built by extracting document features from news text，and the hot -spot cluster is achieved by K-means algorithm with ameliorated initial center.Up to the hot-word association，hot words relations are analyzed according to the weighted sum of three factors，which include the word category distance computed by the hot -spot cluster，the news co -occurrence rate and the hot words co-occurrence rate.This approach has been successfully applied to Public Opinion Monitoring System of University of South China and it obtains good results in practical operation.

Keywords：

提出一種將話(huà)題聚類(lèi)算法應(yīng)用到計(jì)算熱詞關(guān)聯(lián)度上的方法。在熱詞發(fā)現(xiàn)階段，通過(guò)對(duì)新聞文本的特征提取，構(gòu)建向量空間模型，采用初始聚類(lèi)中心優(yōu)化的K-means算法，獲取熱點(diǎn)簇；在關(guān)聯(lián)分析階段，先通過(guò)熱點(diǎn)簇計(jì)算詞類(lèi)別距離，再和新聞同現(xiàn)率，熱詞同現(xiàn)率加權(quán)累加，得到熱詞關(guān)聯(lián)度。該方法已成功應(yīng)用到南華大學(xué)輿情監(jiān)測(cè)系統(tǒng)中，并在實(shí)際運(yùn)行中獲得較好的效果。

K-means；SVM；熱詞；詞群關(guān)系

基金項(xiàng)目：

湖南省哲學(xué)社會(huì)科學(xué)基金（No.14YBA335）

文章編號(hào)：1007-1423（2016）14-0056-05

DOI：10.3969/j.issn.1007-1423.2016.14.012

作者簡(jiǎn)介：

羅旭（1993-），男，江蘇泰興人，本科，研究方向?yàn)樽匀徽Z(yǔ)言處理、數(shù)據(jù)挖掘

歐陽(yáng)純萍（1979-），女，湖南衡陽(yáng)人，副教授，碩士生導(dǎo)師，研究方向?yàn)樽匀徽Z(yǔ)言處理、語(yǔ)義網(wǎng)

劉志明（1972-），男，湖南瀏陽(yáng)人，教授，碩士生導(dǎo)師，研究方向?yàn)榇髷?shù)據(jù)分析、知識(shí)工程

收稿日期：2016-03-25修稿日期：2016-04-30

K-means Algorithm；SVM；Hot Words；Words Relationship