高 鑫 徐 建 胡建洪

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

根據(jù)2017年8月份中國互聯(lián)網(wǎng)絡(luò)信息中心（CNNIC）發(fā)布的《第40次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》［1］中的數(shù)據(jù)，截至2017年6月，我國網(wǎng)絡(luò)新聞?dòng)脩粢?guī)模為6.25億，半年增長率為1.7%，網(wǎng)民使用比例為83.1%。隨著網(wǎng)絡(luò)新聞的急劇增長，新聞信息逐漸變得龐大臃腫。這給人們從海量數(shù)據(jù)中獲取自己感興趣的信息帶來了極大的困難。新聞話題聚類在信息檢索、熱點(diǎn)話題發(fā)現(xiàn)、輿情監(jiān)督等多個(gè)領(lǐng)域都有著廣泛的應(yīng)用，有助于人們掌握社會(huì)最新動(dòng)態(tài)，及時(shí)把握社會(huì)輿論走向。

近年來，國內(nèi)外學(xué)者對(duì)新聞話題聚類做了大量的研究，并取得了卓有成效的結(jié)果。新聞話題聚類的研究主要集中于話題模型表示與聚類算法改進(jìn)。Spitters［2］首先基于語言模型表示新聞文本以及計(jì)算文本之間的相似度，但存在數(shù)據(jù)稀疏的問題。James Allan［4］最早采用向量空間模型來表示新聞文本，根據(jù)余弦相似度來計(jì)算新聞的相似度，但忽視了新聞報(bào)道之間語義的關(guān)系。李鳳嶺［6］等在基于微博的話題發(fā)現(xiàn)領(lǐng)域引入了LDA模型，增加了對(duì)文本語義相關(guān)方面的研究。但LDA模型話題數(shù)目需要預(yù)先指定且一直不變，并不能有效地抽取正確的話題。Bengio［7］等將分布式表示應(yīng)用于單詞，結(jié)合神經(jīng)網(wǎng)絡(luò)，訓(xùn)練語言模型，成功解決了傳統(tǒng)概率語言模型中的參數(shù)組合爆炸以及稀疏問題。在前人研究的基礎(chǔ)上，Mikolov［8］等在 2013 年提出了Word2Vec模型來計(jì)算詞向量。目前，將詞向量應(yīng)用于自然語言處理非常成功，已經(jīng)被廣泛應(yīng)用于中文分詞、情感分類、句法依存分析等。本文基于Word2Vec模型計(jì)算詞向量并利用詞向量來表示新聞文本的向量，然后通過改進(jìn)密度峰值聚類算法來進(jìn)行新聞話題聚類以提高聚類精度。

2 相關(guān)工作

2.1 詞語的分布式表示

Hinto［10］在 1986年提出概念的分布式表達(dá)開創(chuàng)了詞語的分布式表達(dá)的先河。與獨(dú)熱表示只使用向量的一個(gè)維度不同，分布式表示用稠密實(shí)數(shù)向量來表示一個(gè)詞語，能充分表達(dá)詞語之間的語義關(guān)聯(lián)，有效緩解數(shù)據(jù)稀疏問題。分布式表示自提出以來，已被廣泛應(yīng)用于單詞、短語、概念、句子、文檔和社會(huì)網(wǎng)絡(luò)等對(duì)象的表示學(xué)習(xí)中。其中，最經(jīng)典的是由Bengio提出的用一種三層的神經(jīng)網(wǎng)絡(luò)來構(gòu)建語言模型，在此基礎(chǔ)上研究者們又進(jìn)行了一系列的研究分析，其中較為出眾的要屬Word2Vec。Word2Vec的核心是神經(jīng)網(wǎng)絡(luò)的方法，采用CBOW和Skip-Gram兩種模型，將詞語映像到同一坐標(biāo)系，得出數(shù)值向量。CBOW的目標(biāo)是根據(jù)上下文來預(yù)測當(dāng)前詞語的概率。Skip-gram和CBOW剛好相反，其根據(jù)當(dāng)前詞語來預(yù)測上下文的概率。起初每個(gè)單詞都是一個(gè)隨機(jī)N維向量，之后利用CBOW或者Skip-gram模型就可以獲得每個(gè)單詞的最優(yōu)向量。

2.2 新聞話題聚類

新聞話題聚類是話題檢測與跟蹤的一項(xiàng)內(nèi)容，它利用文本聚類技術(shù)對(duì)大量的新聞文本聚類以發(fā)現(xiàn)相關(guān)話題。在以往的研究過程中，許多學(xué)者在新聞話題聚類方面做出了重大的貢獻(xiàn)。索紅光［11］等通過優(yōu)化局部搜索能力來改進(jìn)K-means算法，提高了文本聚類的精度。但隨機(jī)選擇初始聚類中心使得該算法對(duì)初始聚類中心選擇敏感，結(jié)果波動(dòng)性較大。HuangB［12］采用了LDA模型對(duì)微博中的短文本數(shù)據(jù)建立數(shù)學(xué)模型，并且采用單遍聚類算法對(duì)話題進(jìn)行聚類檢測。這種結(jié)合單遍聚類的聚類方法雖然方便，但是結(jié)果很容易受到文本輸入順序的影響。McCallum A［13］等提出兩層聚類方法，解決高維度大數(shù)據(jù)量問題。但劃分容易先形成規(guī)模大的Canopy，影響后面話題精確聚類的效率，而且初始種子選擇不當(dāng)會(huì)導(dǎo)致迭代次數(shù)和冗余度增加。Rodriguez A［14］等提出了一種快速搜索發(fā)現(xiàn)密度峰值的方法，可以方便快捷地確定類簇。但是在選取類簇中心時(shí)需要通過人工來選擇，存在一定的主觀性。經(jīng)過研究發(fā)現(xiàn)，基于密度的聚類算法能夠識(shí)別任何形狀的類簇，而且不需要提前給出聚類數(shù)目，還能比較好的識(shí)別出異常點(diǎn)，因此獲得了廣泛的使用。本文將通過改進(jìn)密度峰值聚類算法來對(duì)新聞文本進(jìn)行聚類，以達(dá)到發(fā)現(xiàn)新聞話題的目標(biāo)。

3 基于Word2Vec的話題聚類算法

3.1 新聞的分布式表示

一篇新聞?dòng)珊芏嗟脑~語組成，如何利用詞向量有效地表示新聞文本是話題聚類的關(guān)鍵。當(dāng)前常用的方法有對(duì)所有的詞求平均值［15］、對(duì)所有詞進(jìn)行TF-IDF加權(quán)求平均值［16］以及Doc2Vec模型［17］。本文提出一種基于Word2Vec選取核心詞（core words）來表示新聞文本的方法，也稱作CW-Word2Vec。

其中α為標(biāo)題的權(quán)重，β為正文的權(quán)重，tf(ttitle) 表示詞t在標(biāo)題中的詞頻，tf(tcontent)表示詞t在正文中的詞頻。

對(duì)每篇文章中的分詞利用詞向量計(jì)算這篇文章中距離此分詞最近的k個(gè)詞，以余弦距離作為兩個(gè)分詞間的“距離”。以詞t為例，將距離詞t最近的k個(gè)詞的距離分別乘以詞頻然后累加再乘以詞t的詞頻得到詞t的權(quán)重值。詞t的權(quán)重值計(jì)算公式如下：

其中di表示第個(gè)詞與詞t的距離，tf(i)表示第i個(gè)詞的詞頻。

計(jì)算出文章中每個(gè)詞的權(quán)重值以后，根據(jù)權(quán)重值進(jìn)行排序，取前n個(gè)詞表示文章的核心詞，用這些核心詞的向量均值表示文章的向量。文章i的向量計(jì)算公式如下：

其中，wt表示核心詞的詞向量。

3.2 改進(jìn)密度峰值聚類算法

密度峰值聚類算法（clustering by fast search and find of density peaks，DPC）由 Rodriguez等在2014年提出，該算法通過快速搜索發(fā)現(xiàn)密度峰值，然后選取密度峰值較大的樣本作為聚類中心，然后將剩余樣本指派到合適的聚類中心完成對(duì)數(shù)據(jù)集的聚類。DPC聚類算法通過引入樣本i的局部密度ρi和樣本i到局部距離比它大且距離它最近的樣本j的距離δi來確定聚類中心，局部密度 ρi和距離δi的定義分別如式（4）和式（5）所示：

其中，dij為對(duì)象i，j間的距離，dc為截?cái)嗑嚯x，當(dāng)x＜0時(shí)，χ(x)=1，否則 χ(x)=0。

對(duì)于局部密度 ρi最大的樣本i，其當(dāng)數(shù)據(jù)集較小時(shí)，可以通過高斯核函數(shù)來可靠地估計(jì)對(duì)象的局部密度，如式（6）所示。

當(dāng)通過式（4）和式（5）計(jì)算出所有樣本點(diǎn)的局部密度 ρi和距離 δi后，可以構(gòu)造點(diǎn)（ ρi，δi）在二維平面上的決策圖，然后通過可視化方式選取圖中ρi和δi都相對(duì)較大的點(diǎn)作為聚類中心。然而在有些情況下，由于數(shù)據(jù)的稀疏性導(dǎo)致聚類劃分的類簇個(gè)數(shù)不是很容易確定，很難確定聚類中心個(gè)數(shù)，因此Rodriguez等人給出了一種通過計(jì)算ρ和δ的乘積來選擇聚類中心數(shù)量的方法，如式（7）所示：

通過式（7）計(jì)算出所有樣本的γ值后，將每個(gè)樣本點(diǎn)的γ值按降序排序，γ值越大越有可能是聚類中心。通過判斷γ的第一次跳躍點(diǎn)可以找到各類簇的中心點(diǎn)，選取γ最大的k個(gè)樣本點(diǎn)為聚類中心。

DPC的主要優(yōu)點(diǎn)是計(jì)算過程簡單，無需迭代，易于理解，但存在的問題也比較明顯，主要存在的問題有截?cái)嗑嚯xdc設(shè)置困難、聚類中心選取困難、存在多米諾骨牌效應(yīng)、同一類簇多密度峰值問題等4個(gè)問題［18～20］。

局部密度作用是發(fā)現(xiàn)密度峰值較大的樣本，因此局部密度的計(jì)算方法應(yīng)該使得密度峰值大的樣本突出，同時(shí)平滑密度峰值小的樣本，因此本文使用高斯核函數(shù)來計(jì)算每個(gè)樣本點(diǎn)的局部密度。為避免截?cái)嗑嚯xdc取值困難問題，本文使用樣本點(diǎn)的K最近鄰來自適應(yīng)計(jì)算截?cái)嗑嚯xdc，計(jì)算方法如式（8）所示。

通過式（10）和式（5）計(jì)算出的樣本點(diǎn) ρ值和δ值可能處于不同的數(shù)量級(jí)，因此本文通過離差標(biāo)準(zhǔn)化將 ρ和δ歸一化到［0，1］區(qū)間，歸一化后的決策值的計(jì)算如式（11）所示。

其中，ρmax表示樣本局部密度的最大值，ρmin表示樣本局部密度的最小值，δmax表示樣本到高密度點(diǎn)距離中距離的最大值，δmin表示距離的最小值。

DPC算法在繪制決策圖后，通過肉眼觀察決策圖確定和選取聚類中心，然后對(duì)剩余樣本進(jìn)行指派完成聚類。然而通過肉眼觀察跳躍現(xiàn)象具有主觀性，不同的人可能選擇的聚類中心不同，不利于算法的自動(dòng)化。因此本文通過最小二乘法擬合直線的方法在決策圖中自動(dòng)確定最佳聚類中心集合。

假 設(shè) 決 策 圖 中 有 點(diǎn) 集 DP={(xi，fi)，(xi+1，fi+1)，…，(xn，fn)} ，點(diǎn) 集 DP 的 最 佳 擬 合 直 線 為f=a0+a1x，則通過最小二乘法計(jì)算直線 f的誤差平方和S的方法，如式（12）所示：

為了得到S的最小值，可以對(duì)S求偏導(dǎo)數(shù)，令這兩

等價(jià)變換為

通過求解方程組即可得到參數(shù)a0和a1的值，分別如式（17）和如式（18）所示：

將式（17）和式（18）求出的 a0和 a1，代入式（12）即可求出擬合直線的誤差平方和S。

設(shè)決策圖中所有點(diǎn)的集合為D={(x1，f1) ，，現(xiàn)在把集合 D分為左點(diǎn)集 Dl和右點(diǎn)集 Dr兩個(gè)部分，其中 Dl和 Dr分別如式（19）和式（20）所示，Dl為聚類中心的集合。

因此，為求出最佳聚類中心集合，首先分別求出集合Dl和Dr的擬合直線的誤差平方和Sl和Sr，然后通過式（21）求出總的均方根誤差平方和RMSEP。

通過改變劃分點(diǎn) p的值，求最小的均方根誤差平方和RMSEmin對(duì)應(yīng)的左點(diǎn)集Dl，即為最佳聚類中心集合。

當(dāng)數(shù)據(jù)集較大時(shí)，選擇初始聚類中心將非常耗時(shí)，需要做相應(yīng)的優(yōu)化?？紤]到聚類中心為γ值最大k個(gè)點(diǎn)，通常聚類個(gè)數(shù)k也不會(huì)很大，因此可以選擇γ值最高的m個(gè)點(diǎn)參與選擇初始聚類中心即可，本文根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)通過式（22）確定m的值。

因此，本文通過最小二乘法線性擬合選擇最佳聚類中心集合的具體過程如算法1所示。

算法1初始聚類中心選擇算法

輸入：降序排序后的γ值集合D及其大小m

輸出：初始聚類中心集合C

算法步驟：

1.初始化聚類中心集合C為空；

2.初始化最小均方根誤差平方和RMSEmin為無窮大；

3.forp←2 to m-1

4. 根據(jù)劃分點(diǎn) p將集合D劃分為左點(diǎn)集Dl和右點(diǎn)集Dr兩部分；

5. 使用式（12）分別求出集合Dl和Dr的擬合直線的誤差平方和Sl和Sr；

6.使用式（21）根據(jù)Sl和Sr求出總的均方根誤差平方和RMSEP；

7.ifRMSEP＜RMSEmin

8. RMSEmin=RMSEP；

9. C=Dl；

10.end if

11.end for

12.返回初始聚類中心集合C

為了避免離群點(diǎn)對(duì)樣本歸類結(jié)果的影響，導(dǎo)致將兩個(gè)類簇合并為一個(gè)類簇的現(xiàn)象出現(xiàn)，在將樣本歸類到相應(yīng)類簇前，先進(jìn)行離群點(diǎn)剔除。本文通過樣本i與其K近鄰的最大距離和閾值dt來識(shí)別離群點(diǎn)，當(dāng)樣本i的大于閾值dt時(shí)，則樣本i為離群點(diǎn)。和dt的計(jì)算方法分別如式（23）和式（24）所示。

其中，N為數(shù)據(jù)集樣本總數(shù)，KNNi是樣本i的K個(gè)近鄰集合。

本文首先對(duì)非離群點(diǎn)樣本進(jìn)行分配，然后分配離群點(diǎn)樣本，具體算法過程如算法2所示：

算法2剩余樣本分配到聚類中心的過程

輸入：聚類中心集合CI

非離群點(diǎn)樣本集合S

離群點(diǎn)樣本集合O

輸出：初始聚類結(jié)果C

算法步驟：

1.初始化隊(duì)列Vq為空；

2.for each樣本i inCI

3. 將樣本i作為一個(gè)新類簇的聚類中心，標(biāo)記樣本i已訪問，同時(shí)將樣本i的K近鄰集合KNN（i）中每個(gè)樣本并入樣本i所在的類簇，并將KNN（i）的每個(gè)樣本加入隊(duì)列Vq；

4. whileVq不為空

5. 取出隊(duì)列Vq的樣本j，對(duì)于集合KNN（j）中每一個(gè)樣本r，若樣本r沒有被訪問，且不是離群點(diǎn)，則將樣本r并入樣本j所在類簇，標(biāo)記樣本r已訪問，并將樣本r放入隊(duì)列Vq；

6. end while

7.end for

8.for each樣本i in離群點(diǎn)樣本集合O

9. 計(jì)算樣本i的K近鄰歸屬最多的類簇Cu，將樣本i并入類簇Cu

10.end for

11.return初始聚類結(jié)果C

本文針對(duì)密度峰值算法存在的問題，提出了一種基于KNN改進(jìn)的密度峰值聚類算法。該算法首先使用樣本的K近鄰集合自適應(yīng)計(jì)算出截?cái)嗑嚯xdc，然后計(jì)算出每個(gè)樣本的 ρi和δi，并作歸一化處理，計(jì)算每個(gè)樣本的γ值并降序排列；然后通過最小二乘法線性擬合選取初始聚類中心，并使用算法2將剩余樣本歸類到合適的聚類中心形成聚類結(jié)果。具體過程如算法3所示：

算法3基于KNN改進(jìn)的密度峰值聚類算法

輸入：數(shù)據(jù)集D

對(duì)象的K近鄰K

輸出：聚類結(jié)果C

算法步驟：

1.預(yù)處理數(shù)據(jù)集，如歸一化或降維處理；

2.根據(jù)距離度量公式計(jì)算樣本間的距離，并通過式（8）計(jì)算截?cái)嗑嚯xdc；

3.分別使用式（10）和式（5）計(jì)算每個(gè)樣本的 ρi和 δi，計(jì)算每個(gè)樣本的γ值并降序排列；

4.使用算法1選取初始聚類中心；

5.使用算法2將除聚類中心外的剩余樣本分配到合適的聚類中心，生成聚類結(jié)果；

6.返回聚類結(jié)果C

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

4.1 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

本文使用純度、F1值、調(diào)整蘭德系數(shù)（ARI）作為實(shí)驗(yàn)評(píng)價(jià)指標(biāo)，相關(guān)定義如下。

1）純度。純度是對(duì)某個(gè)聚類結(jié)果Ci，其中數(shù)量最多的類在聚類結(jié)果中比例。單個(gè)類簇的純度的定義如式（25）所示：

其中，Ci表示一個(gè)聚類結(jié)果，ni表示Ci的元素總數(shù)，nij表示Ci中，元素屬于j類的個(gè)數(shù)?？傮w的聚類純度可以通過單個(gè)聚類純度的加權(quán)平均得到，計(jì)算方法如式（26）所示。

2）F1值。F1值是準(zhǔn)確率P和召回率R的調(diào)和均值。對(duì)于給定的聚類i和類別j，F(xiàn)1值的計(jì)算方法如式（27）所示。

其中，Nij表示在聚類i中類別j的元素個(gè)數(shù)，Ni表示聚類i的元素個(gè)數(shù)，Nj表示類別j的元素個(gè)數(shù)。整體的F1值可以通過類間F1值的加權(quán)平均求得，計(jì)算方法如式（28）所示。

3）調(diào)整蘭德系數(shù)ARI。調(diào)整蘭德系數(shù)根據(jù)樣本的真實(shí)標(biāo)簽和聚類算法得到的標(biāo)簽，計(jì)算這兩種標(biāo)簽分布的相似性。設(shè)和分別表示數(shù)據(jù)集的真實(shí)劃分和聚類結(jié)果。則ARI的定義如式（29）所示。

其中，a表示在U和V均在同一類簇的樣本對(duì)數(shù)目，b表示在U中在同一類簇，但在V中不在同一類簇的樣本對(duì)數(shù)目，c表示在U中不在同一類簇，但在V中同一類簇的樣本對(duì)數(shù)目，d表示在U中和V中均不在同一類簇的樣本對(duì)數(shù)目。

4.2 實(shí)驗(yàn)環(huán)境和數(shù)據(jù)集

本文的實(shí)驗(yàn)環(huán)境為Windows 7，64位操作系統(tǒng)，內(nèi)存 8GB，硬盤 500GB，CPU 為 Inter（R）Core（TM）2 Duo CPU E7500@2.93GHz，Java版本1.7。

本文選擇搜狗實(shí)驗(yàn)室中2012年6月到7月的搜狐新聞數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，并進(jìn)行聚類實(shí)驗(yàn)和實(shí)驗(yàn)結(jié)果分析。對(duì)于搜狐新聞數(shù)據(jù)集，本文隨機(jī)選取其中IT、財(cái)經(jīng)、房產(chǎn)、教育、軍事、汽車、文化、體育等8個(gè)類別下各1000篇新聞文本構(gòu)成總量為8000篇新聞數(shù)據(jù)集，然后使用開源中文切詞軟件Ansj對(duì)新聞文本進(jìn)行切詞，并去除常規(guī)停用詞。

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

為驗(yàn)證不同文本表示模型對(duì)聚類結(jié)果的影響，本文分別使用基于TF-IDF的向量空間模型、LDA主題模型以及本文的CW-Word2Vec模型對(duì)新聞文本進(jìn)行特征提取。對(duì)于CW-Word2Vec模型，本文采用CBOW模型，模型設(shè)置的訓(xùn)練參數(shù)為，詞向量維度為100，初始學(xué)習(xí)率為0.025，文本窗口大小為5，標(biāo)題權(quán)重α為0.6，正文權(quán)重 β為0.4，n取8。本文使用KMeans++和DPC作為文本聚類的基準(zhǔn)方法，來驗(yàn)證本文改進(jìn)的KNN-DPC聚類算法的可行性和有效性，實(shí)驗(yàn)結(jié)果如表1、圖1、圖2以及圖3所示。

由實(shí)驗(yàn)數(shù)據(jù)可知，不同的文本表示方法對(duì)聚類結(jié)果的影響比較大，整體上來說基于CW-Word2Vec模型的聚類結(jié)果最好，基于主題模型LDA的聚類結(jié)果次之，基于TF-IDF向量空間模型的聚類結(jié)果最差。在TF-IDF空間模型和CW-Word2Vec模型上，DPC算法實(shí)驗(yàn)結(jié)果比KMeans++和KNN-DPC的實(shí)驗(yàn)結(jié)果要差。在LDA主題模型上，三種聚類算法的實(shí)驗(yàn)結(jié)果差距較小。通過對(duì)比在三種文本表示模型上聚類的各項(xiàng)指標(biāo)，可以發(fā)現(xiàn)KNN-DPC的實(shí)驗(yàn)結(jié)果整體上要優(yōu)于KMeans++和DPC，從而驗(yàn)證了KNN-DPC在高維文本數(shù)據(jù)集上聚類具有更好的效果。

表1 搜狐新聞數(shù)據(jù)集聚類實(shí)驗(yàn)結(jié)果

圖1 TF-IDF模型下不同聚類算法聚類結(jié)果

圖2 LDA主題模型下不同聚類算法聚類結(jié)果

圖3 CW-Word2Vec模型下不同聚類算法聚類結(jié)果

5 結(jié)語

本文首先基于Word2Vec提出一種選取核心詞來表示新聞文本向量的方法。然后介紹了密度峰值聚類算法的主要思想和存在的問題并針對(duì)密度峰值聚類算法存在的問題提出了基于KNN改進(jìn)的密度峰值聚類算法。在搜狐新聞數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明本文改進(jìn)后的聚類算法的可行性以及有效性。后續(xù)工作將研究如何更好地改進(jìn)算法質(zhì)量降低復(fù)雜度。