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

唐嘯虎 劉志鋒

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

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

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

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

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

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

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

1算法簡介

1.1k-means算法

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

1.3 k-means算法優(yōu)缺點

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

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

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

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

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已經(jīng)達到要求，則結(jié)束;否則轉(zhuǎn)到（2）。

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

2改進的k-means算法

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

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

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

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

（4）記錄具有相同標簽的兩個數(shù)據(jù)點的位置，創(chuàng)建共協(xié)矩陣：

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

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

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

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

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

3新聞數(shù)據(jù)聚類實驗與結(jié)果分析

3.1實驗數(shù)據(jù)集

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

3.2評價指標

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

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

3.3實驗分析

3.3.1實驗過程

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

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

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

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

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

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

3.3.2對比分析

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

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

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

4結(jié)論

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