基于Word2Vec的改進密度峰值新聞話題聚類*

高 鑫 徐 建 胡建洪

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

根據2017年8月份中國互聯網絡信息中心（CNNIC）發布的《第40次中國互聯網絡發展狀況統計報告》［1］中的數據，截至2017年6月，我國網絡新聞用戶規模為6.25億，半年增長率為1.7%，網民使用比例為83.1%。隨著網絡新聞的急劇增長，新聞信息逐漸變得龐大臃腫。這給人們從海量數據中獲取自己感興趣的信息帶來了極大的困難。新聞話題聚類在信息檢索、熱點話題發現、輿情監督等多個領域都有著廣泛的應用，有助于人們掌握社會最新動態，及時把握社會輿論走向。

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

2 相關工作

2.1 詞語的分布式表示

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

2.2 新聞話題聚類

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

3 基于Word2Vec的話題聚類算法

3.1 新聞的分布式表示

一篇新聞由很多的詞語組成，如何利用詞向量有效地表示新聞文本是話題聚類的關鍵。當前常用的方法有對所有的詞求平均值［15］、對所有詞進行TF-IDF加權求平均值［16］以及Doc2Vec模型［17］。本文提出一種基于Word2Vec選取核心詞（core words）來表示新聞文本的方法，也稱作CW-Word2Vec。

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

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

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

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

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

3.2 改進密度峰值聚類算法

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

其中，dij為對象i，j間的距離，dc為截斷距離，當x＜0時，χ(x)=1，否則 χ(x)=0。

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

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

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

DPC的主要優點是計算過程簡單，無需迭代，易于理解，但存在的問題也比較明顯，主要存在的問題有截斷距離dc設置困難、聚類中心選取困難、存在多米諾骨牌效應、同一類簇多密度峰值問題等4個問題［18～20］。

局部密度作用是發現密度峰值較大的樣本，因此局部密度的計算方法應該使得密度峰值大的樣本突出，同時平滑密度峰值小的樣本，因此本文使用高斯核函數來計算每個樣本點的局部密度。為避免截斷距離dc取值困難問題，本文使用樣本點的K最近鄰來自適應計算截斷距離dc，計算方法如式（8）所示。

通過式（10）和式（5）計算出的樣本點 ρ值和δ值可能處于不同的數量級，因此本文通過離差標準化將 ρ和δ歸一化到［0，1］區間，歸一化后的決策值的計算如式（11）所示。

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

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

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

為了得到S的最小值，可以對S求偏導數，令這兩

等價變換為

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

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

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

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

通過改變劃分點 p的值，求最小的均方根誤差平方和RMSEmin對應的左點集Dl，即為最佳聚類中心集合。

當數據集較大時，選擇初始聚類中心將非常耗時，需要做相應的優化。考慮到聚類中心為γ值最大k個點，通常聚類個數k也不會很大，因此可以選擇γ值最高的m個點參與選擇初始聚類中心即可，本文根據實驗經驗通過式（22）確定m的值。

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

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

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

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

算法步驟：

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

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

3.forp←2 to m-1

4. 根據劃分點 p將集合D劃分為左點集Dl和右點集Dr兩部分；

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

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

7.ifRMSEP＜RMSEmin

8. RMSEmin=RMSEP；

9. C=Dl；

10.end if

11.end for

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

為了避免離群點對樣本歸類結果的影響，導致將兩個類簇合并為一個類簇的現象出現，在將樣本歸類到相應類簇前，先進行離群點剔除。本文通過樣本i與其K近鄰的最大距離和閾值dt來識別離群點，當樣本i的大于閾值dt時，則樣本i為離群點。和dt的計算方法分別如式（23）和式（24）所示。

其中，N為數據集樣本總數，KNNi是樣本i的K個近鄰集合。

本文首先對非離群點樣本進行分配，然后分配離群點樣本，具體算法過程如算法2所示：

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

輸入：聚類中心集合CI

非離群點樣本集合S

離群點樣本集合O

輸出：初始聚類結果C

算法步驟：

1.初始化隊列Vq為空；

2.for each樣本i inCI

3. 將樣本i作為一個新類簇的聚類中心，標記樣本i已訪問，同時將樣本i的K近鄰集合KNN（i）中每個樣本并入樣本i所在的類簇，并將KNN（i）的每個樣本加入隊列Vq；

4. whileVq不為空

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

6. end while

7.end for

8.for each樣本i in離群點樣本集合O

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

10.end for

11.return初始聚類結果C

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

算法3基于KNN改進的密度峰值聚類算法

輸入：數據集D

對象的K近鄰K

輸出：聚類結果C

算法步驟：

1.預處理數據集，如歸一化或降維處理；

2.根據距離度量公式計算樣本間的距離，并通過式（8）計算截斷距離dc；

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

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

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

6.返回聚類結果C

4 實驗及結果分析

4.1 實驗評價指標

本文使用純度、F1值、調整蘭德系數（ARI）作為實驗評價指標，相關定義如下。

1）純度。純度是對某個聚類結果Ci，其中數量最多的類在聚類結果中比例。單個類簇的純度的定義如式（25）所示：

其中，Ci表示一個聚類結果，ni表示Ci的元素總數，nij表示Ci中，元素屬于j類的個數。總體的聚類純度可以通過單個聚類純度的加權平均得到，計算方法如式（26）所示。

2）F1值。F1值是準確率P和召回率R的調和均值。對于給定的聚類i和類別j，F1值的計算方法如式（27）所示。

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

3）調整蘭德系數ARI。調整蘭德系數根據樣本的真實標簽和聚類算法得到的標簽，計算這兩種標簽分布的相似性。設和分別表示數據集的真實劃分和聚類結果。則ARI的定義如式（29）所示。

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

4.2 實驗環境和數據集

本文的實驗環境為Windows 7，64位操作系統，內存 8GB，硬盤 500GB，CPU 為 Inter（R）Core（TM）2 Duo CPU E7500@2.93GHz，Java版本1.7。

本文選擇搜狗實驗室中2012年6月到7月的搜狐新聞數據集作為實驗數據集，并進行聚類實驗和實驗結果分析。對于搜狐新聞數據集，本文隨機選取其中IT、財經、房產、教育、軍事、汽車、文化、體育等8個類別下各1000篇新聞文本構成總量為8000篇新聞數據集，然后使用開源中文切詞軟件Ansj對新聞文本進行切詞，并去除常規停用詞。

4.3 實驗結果及分析

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

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

表1 搜狐新聞數據集聚類實驗結果

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

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

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

5 結語

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