基于改進的k-means算法的新聞聚類的研究

唐嘯虎 劉志鋒

摘要：針對k-means聚類算法對初始聚類中心敏感，容易陷入局部最優的情況，提出一種改進的基于k-means算法的新聞聚類方法。在用傳k-means算法對新聞數據集進行多次聚類的基礎上，使用證據累積算法對k-means算法的聚類結果進行融合，以平滑k-means算法的結果，減少波動。實驗結果表明提出的方法使聚類結果的準確率從53.33%提升至77.78%。

關鍵詞：k-means;新聞;聚類分析;融合;分級聚類

中圖分類號：TP391 文獻標識碼：A

文章編號：1009-3044（2020）10-0201-03

隨著互聯網的高速發展，人們已經邁向了一個信息化的時代，互聯網上的信息交流和獲取逐漸取代了傳統的電視、報紙、書信等傳統媒體。截至2019年6月，中國網民規模為8.54億人，互聯網普及率達61.2%，網站數量518萬個。人們每天通過瀏覽器或者新聞APP看新聞產生大量點擊記錄，對人們點擊的海量新聞進行分析，可以獲知特定時間和特定范圍內公眾最關心的熱門事件，進而可以在信息爆炸的互聯網時代幫助人們更快、更好、更有效地獲取有用的信息。如何快速、有效地在海量新聞瀏覽記錄中發現其中的趨勢和主題，不僅能夠幫助個人更準確地了解全社會關注的熱點事件，同時還能輔助國家及時發現網絡輿情事件、趨勢，在網絡輿情分析、重大網絡事件監測防御、信息網絡安全等領域具有極其重要的現實意義。

聚類分析旨在分析數據過程中發現數據對象之間的相互關系，將數據依據一定原理進行分組，各分組結果內的相似性越大，各分組之間的差別就越大，聚類效果越好。k均值（k-means）聚類算法具有快速、簡單的特點，對大數據集有較高的分析效率。

本文提出了一種結合k-means算法與分級聚類算法的方法，利用k-means算法對預處理過的新聞數據集進行多次聚類，然后用證據累積算法融合多次聚類得到的結果，減少波動。本文對搜狐新聞數據進行分析，考查本文方法的聚類效果，并與傳統k-means算法的聚類效果進行比較，體現本文方法的優勢。

1算法簡介

1.1k-means算法

k-means算法采用迭代更新的思想，該算法的目標是根據輸入的參數k將數據對象聚成k簇，其基本思想為：首先指定需要劃分的簇的個數k值，隨機地選擇k個初始數據對象作為初始聚類或簇的中心;然后計算其余的各個數據對象到這k個初始聚類中心的距離，并把數據對象劃分到距離它最近的那個中心所在的簇中，然后根據公式：

1.3 k-means算法優缺點

k-means算法是解決聚類問題的經典算法，這種算法簡單快速。當結構集是密集的，簇與簇之間區別明顯時，聚類的結果比較好。在處理大量數據時，該算法具有較高的可伸縮性和高效性。

但是，目前傳統的k-means算法也存在著許多缺點：

（1）k-means聚類算法需要用戶事先指定聚類的個數k值。在很多時候，在對數據集進行聚類的時候，用戶起初并不清楚數據集應該分為多少類合適，對k值難以估計。

（2）對初始聚類中心敏感，選擇不同的聚類中心會產生不同的聚類結果和不同的準確率。隨機選取初始聚類中心的做法會導致算法的不穩定性，有可能陷入局部最優的情況。

1.4分級聚類算法

分級聚類是一種自底向上的聚類方法。它的主要思想是：首先將每個樣本自定義為一類，然后逐步合并，直到最后聚為一類或者達到要求為止。

對于給定的n個樣本集合x={x1，x2，...xn}，分級聚類方法的具體步驟如下：

（1）x中每個樣本Xi均自成一類ci，這樣就構建了一個初始聚類C={c1，c2，...，cn};

（2）計算c中每對類（ci，ci）之間的相似度sim（ci，cj）;

（3）選擇最大相似度的類對Max（sim（ci，ci）），并將其合并為一個新類Ck-CiUci，構成一個新的聚類c={c1，c2，...，ck..，cn-1};

（4）如果C中只有一個類或C已經達到要求，則結束;否則轉到（2）。

分級聚類實際上將產生一棵樹，底部葉子結點代表n個樣本，根結點為最后聚為一類的情況，中間的某層代表其中的一種聚類。

2改進的k-means算法

傳統的k-means算法對初始聚類中心敏感，聚類結果隨不同的初始聚類中心而波動。針對k-means聚類算法中隨機選取初始聚類中心的缺陷，本文提出了一種改進的方法，步驟如下：

（1）準備好數據集D={d0，d1，d2，...，dn-1}，數據集中共有n條數據。

（2）對簇的數目k取2到19，對于每一次聚類結果，計算慣性權重，畫出k值一慣性權重折線圖，根據肘點法，選擇最合適的簇的數目k1。

（3）使用k-means聚類算法對數據集進行多次聚類，每次聚類，k從區間[k1-m，k1+j]隨機取值（m>0，j>0且m+j<8），每一次聚類完成后，遍歷所有數據點所在簇的標簽，簇標簽集合為{0，1，2，3…，k-1}。

（4）記錄具有相同標簽的兩個數據點的位置，創建共協矩陣：

（5）多次運行k-means算法，把每一次迭代得到的共協矩陣相加，矩陣中的數值表示兩個數據點被分到同一簇的次數。

（6）使用分級聚類對第一步得到的共協矩陣進行聚類分析。構造共協矩陣的最小生成樹。

生成樹中的節點對應數據集中的個體，邊的權重對應兩個節點被分到同一簇的次數，也就是共協矩陣所記錄的值。

（7）遍歷最小生成樹矩陣中的每一條邊，刪除低于閾值的邊。

（8）最后，找到所有連通分支，也就是尋找移除低權重邊以后仍然連接在一起的節點。連通分支的數量就是簇的數量，連通分支中的節點就是被分到同一簇的數據。

3新聞數據聚類實驗與結果分析

3.1實驗數據集

本文的實驗數據集來源于網絡搜狐新聞，數據集包含了9個類別的新聞：娛樂、財經、房地產、旅游、科技、體育、健康、教育、汽車，共4500條。新聞類別名與數量如下表所示。

3.2評價指標

本文的主要工作是提升新聞聚類的準確率，對于聚類產生的k個簇的新聞，采用準確率A來評價算法的正確性，準確率A的計算方法如下：

公式（3）中，Ca表示新聞數據集中所有新聞類別的集合，CK表示使用k-means算法聚類后得到的類別集合。

3.3實驗分析

3.3.1實驗過程

首先對數據集進行分詞、去除停用詞處理。本文采用了iieba分詞工具對數據集進行分詞，采用哈工大停用詞表去除數據集中的停用詞。

對經過分詞、去除停用詞預處理之后的4500條數據進行聚類，k依次取區間（2，20）內的值，每次運行算法都計算慣性權重。

圖3中，橫軸是k的值，縱軸是慣性權重。由折線圖可知，隨著簇數量的增加，質心點和其他數據點位置的調整逐漸減少，慣性權重逐漸降低。簇數量為9時，慣性權重進行了最后一次大的調整。

使用k-means算法對新聞數據集進行聚類，運行12次，每次k值在區間[6，12]上隨機取值，將聚類結果保存到共協矩陣中。然后，將12次運行得到的共協矩陣相加，使用分級聚類算法對共協矩陣進行聚類分析，構造最小生成樹，刪除低于閾值的邊后，連通分支就是聚類得到的各個簇。

對聚類結果中的每個簇，對該簇中的詞語按權重由大到小排序，選取權重最大的10個詞作為該簇關鍵詞，聚類結果如下表所示。

對聚類結果進行分析，可以得出結論：本文所提出的基于k-means的聚類方法能夠準確、有效地對新聞進行分類，獲取的聚類中心附近的高頻關鍵詞可以較好地反映該簇所包含新聞的內容、主題、類別。

3.3.2對比分析

在同等條件下，用傳統的k-means聚類算法對本文所使用的新聞數據集進行聚類分析。為保證結果的客觀性，用傳統k-means算法進行了5次聚類，取平均值作為最終結果，實驗結果的對比如表4所示。

k-means算法對初始聚類中心敏感，選擇不同的聚類中心會產生不同的聚類結果和不同的準確率。隨機選取初始聚類中心的做法會導致算法的不穩定性，有可能陷入局部最優的情況。實驗表明，與傳統k-means聚類算法相比，本文使用證據累積算法對多次運行k-means算法得到的結果進行融合，能夠平滑算法多次運行所得到的不同結果，可以減少波動。

綜上所述，本文的方法在一定程度上降低了傳統k-means算法對初始值的依賴，降低了算法的不穩定性，有效提高了算法聚類結果的準確率。

4結論

k-means聚類算法作為基于劃分聚類算法的一個典型算法，在數據挖掘中被廣泛應用，經常被用來作為預處理步驟。本文使用基于k-means算法的方法對新聞數據集進行聚類分析，以找到數據集中包含的新聞類別與主題。對新聞數據集進行分詞、去除停用詞預處理后，先使用k-means算法對新聞數據集進行多次聚類，然后使用分級聚類算法對運行k-means算法得到的多個結果進行融合，克服k-means算法因初始聚類中心的選擇而導致的局部最優。實驗證明本文的方法對聚類結果的準確率有較大提高。