基于TFIDF+LSA算法的新聞文本聚類與可視化

郝秀慧,方賢進,楊高明

(安徽理工大學 計算機科學與工程學院，安徽 淮南 232001)

0 引 言

在大數據時代，互聯網上有大量的數據有待挖掘，面對互聯網上大量的文本數據，主要有兩種數據挖掘的方法，一種是基于有監督的數據挖掘方法，這種方法一般需要提前對數據進行標注。另一種是基于無監督的數據挖掘方法，這種方法由于不需要提前對數據進行標注，能大大減少人工標注的成本。文本文檔聚類作為一種無監督數據挖掘方法，越來越成為數據挖掘領域備受關注的技術。文本聚類主要是將大量的文本集合劃分為幾個不同的小集合的過程,并使得同一集合內的樣本盡可能相似，不同集合內的樣本盡可能不相似。文本聚類首先要解決的問題就是文本的表示問題，即對文本數據進行建模。一般使用向量空間模型來表示文本，每個文本都表示為一個向量，向量的值根據不同的技術可有不同的表示方式。一般可以用詞頻tf或者詞頻反文檔頻率(tfidf)權重表示，在這種表示方式中，向量的每個維度為一個單詞。為了將無標注數據聚成不同的類別，需要用到聚類算法。聚類算法主要有基于劃分的聚類算法[1]、基于層次的聚類算法[2]和基于密度的聚類算法[3]等。其中kmeans作為聚類算法中經典的算法之一，通過劃分的方式對數據進行聚類，可應用在大量的數據上。但是kmeans算法也有自身的局限性,如需要事先選擇聚類數目K和對初始聚類中心的選擇比較敏感等。因此也出現了多種改進kmeans算法，如在文獻[1]中有學者根據肘點確定K值，用kmeans++算法來優化kmeans初始中心點的選擇[4]等。而面對聚類的一個重要事實是：沒有最好的聚類算法，每個聚類算法都是顯式或者隱式地對數據施加一個結構[5]。一般來說，評價一個聚類算法的好壞是根據不同的應用來決定，主要可以從三個方面來考慮：聚類的質量、聚類的效率和結果的可視化程度。該文采用不同的方式對數據進行kmeans聚類，用不同的指標來評估聚類的質量，并研究了基于不同聚類方式的算法的效率和結果的可視化程度。

1 文本預處理

1.1 TFIDF算法

TFIDF也叫做詞頻反文檔頻率[6]，結合了詞頻計算公式和反文檔頻率的計算公式。TFIDF的計算公式如下：

(1)

其中，fij代表詞j在文檔i中的出現頻率,即詞j在文檔i中出現的頻次與文檔i中總詞數的比，N代表總文檔數，nj代表出現詞j的文檔數。上述公式表示的是當一個詞在一篇文章中出現的頻次多且在其他文章中出現的次數少時,tfidfij的值是比較大的，也就是表示這個詞j對這篇文章i比較重要。解決的是當一個文檔中有相同詞頻的不同詞時，區分這些詞對文檔的重要性問題。例如，詞1與詞2在文檔i中有相同的詞頻，那這時僅僅用詞頻來計算詞的重要性是不能區分兩詞的重要性的。通過引入反文檔頻率，計算這兩個詞在整個文檔集中的反文檔頻率，若詞1在整個文檔集中出現的次數較少，而詞2在整個文檔集中出現的次數較多，那么就說明，詞1比詞2有更好的文檔區分能力。對文檔i來說，詞1的TFIDF的值就會比詞2的TFIDF的值大。

1.2 LSA算法

LSA也稱為潛在語義分析[7]，是一種無監督學習方法，主要用在文本的話題分析上，是通過對矩陣進行分解來發現文本與單詞之間的基于話題的語義關系。具體實現是將文本集合表示為單詞文本矩陣，根據確定的話題個數，對單詞文本矩陣進行截斷奇異值分解(TruncatedSVD)[8-9]，從而得到話題向量空間，以及文本在話題向量空間的表示。形式化表達分解公式如下：

單詞文本矩陣≈單詞話題矩陣×話題文本矩陣

潛在語義分析矩陣分解數學公式[8]如下：

Xm×n≈Um×kΣkVk×n

(2)

其中，m是單詞的維數，n是樣本的個數，k是話題的個數,且k?n?m。左奇異矩陣Um×k作為話題向量空間,列由X的前k個互相正交的左奇異向量組成；對角矩陣Σk和右奇異矩陣Vk×n的乘積作為文本在話題向量空間的表示，其中Σk為k階對角矩陣，對角元素為前k個最大奇異值，Vk×n的行由X的前k個互相正交的右奇異向量組成。

2 TFIDF+LSA算法

由于TFIDF+LSA算法是結合TFIDF算法和LSA算法得來，該文結合兩種算法的過程如圖1所示。

圖1 TFIDF+LSA算法的結合過程

3 聚類算法

3.1 kmeans算法

kmeans算法主要是將數據D={a1,a2,…,an}聚類為k個類別，class={class1,class2,…,classk},目標是最小化平方誤差和(SSE)[10]，公式如下：

(3)

其中，centeri是第i個類別的類中心。公式所要表達的含義是計算每類內數據到該類類中心的歐氏距離的和,描述的是每個類類內距離到該類中心的緊密程度,值越小,表示類內越緊密。

kmeans算法步驟如下：

步驟一：選擇k個初始中心點，該文采用kmeans++算法來選擇k個初始中心點。

步驟二：計算點到k個初始中心的歐氏距離[11]，并將點歸類為與初始中心最近的點的類別，依此計算其他點到k個中心的距離，并歸類。

步驟三：通過計算每類的均值，更新聚類中心。

步驟四：重復步驟二和步驟三，直至聚類達到收斂條件。

3.2 kmeans++算法

由于kmeans算法的聚類效果受初始中心點選取的影響比較大，因此有學者改進了kmeans算法，即kmeans++算法選擇初始中心點的方式是以較大的概率選擇離已經選取的聚類中心點最遠的點作為下一個初始中心點。算法步驟如下：

步驟一：隨機從輸入的數據集X中選取一個點作為第一個種子。

步驟二：計算其余點到已經選擇的種子中最近的種子的距離D(x)，并以距離的遠近為正比計算概率，將概率P最大的那個點作為新的聚類中心,計算公式如式(4)。

(4)

步驟三：重復步驟二直至獲得k個種子，即得到k個初始聚類中心。

4 實驗和性能分析

4.1 平臺與數據

實驗采用Windows10系統，Compute Core: 4C+4G, 1.8 GHz,RAM:4 GB.Jupyter notebook,python 3.7.8。數據來源于從校園新聞中采集到的數據，總共11 456條校園綜合新聞(新聞網址是：http://news.aust.edu.cn/zhxw.htm)。由于校園新聞主要是對校園活動的記錄，每條新聞字數在400字到700字不等。從內容上，主要通過人工的方式，將這11 456條新聞大致分為7個類別，分別為教育教學類、畢業就業類、比賽活動類、思想政治類、交流會議類、學習培訓類、管理服務類。采集到的數據集為csv格式，數據情況如表1所示。

表1 采集的部分數據

當采集到文本數據之后，經過數據清洗，包括對文本去重、分詞、去停用詞等操作后才能進行后續數據的預處理操作。其中，該實驗是基于結巴分詞得到的分詞結果。去停用詞的操作主要是建立停用詞表，目前比較全的有哈工大的停用詞表。該實驗使用的停用詞表包含有1 214個詞，包括特殊符號、不常用的詞以及無意義的詞等，當然，也可以根據使用的不同語料庫和個人實驗的需要，增加停用詞，建立適合實驗需要的停用詞表，將分詞后不常用的詞或者是沒有意義的詞都可以加入到停用詞表中。根據停用詞表的不同類別做出部分停用詞，如表2所示。

表2 部分停用詞表

根據TFIDF+LSA的方法得到的類別劃分情況如表3所示。

表3 數據類別劃分情況

從表3可以看出，校園綜合新聞的數據組成每個類別是不均衡的，最多的有2 418條新聞，最少的有876條新聞。

4.2 聚類評估指標

4.2.1 輪廓系數

輪廓系數(SC)[12]的計算公式如下：

(5)

(6)

公式(5)中，ai表示同一類中樣本與其他樣本之間的平均距離，bi表示樣本與最近的類別內所有樣本之間的平均距離。公式(6)中的S(k)是每一類樣本輪廓系數的平均值,nk表示第k類聚類的樣本數。輪廓系數S(k)的取值在[-1,1]之間，值越接近于1，表示類間分離得越遠，聚類效果越好。

4.2.2 卡林斯基-原巴斯指數

卡林斯基-原巴斯指數(CHI)[13]的計算公式如下：

(7)

(8)

(9)

公式(8)中的Bk為類間離差矩陣的跡，公式(9)中的Wk為類內離差矩陣的跡，nE表示數據集E的大小。cq表示類q的中心,cE表示數據E的中心,nq表示q類內的樣本數量。CHI的值越大，表示類間數據的分離程度越大，聚類效果越好。

4.2.3 戴維斯-堡丁指數

戴維斯-堡丁指數(DBI)[14]的計算公式如下：

(10)

其中，si表示類i中每一個點到類i中心的平均距離，dij表示類i和類j兩個類中心之間的歐氏距離。DBI取值越接近于零，聚類效果越好。

4.3 實驗結果與分析

實驗采用t-SNE技術[15]對聚類的結果進行可視化展示，這種技術主要是將高維數據映射到低維空間，是一種將高維空間數據看作高斯分布，將低維空間數據看作t分布，將高維映射到低維空間的同時,盡量保證兩者分布概率不變的方法?；赥FIDF得到的聚類結果如圖2所示，基于TFIDF+LSA得到的聚類結果如圖3所示。

圖2 基于TFIDF的聚類可視化

4.3.1 聚類可視化結果

從圖2和圖3可以看出，比起基于TFIDF的聚類結果，基于TFIDF+LSA的聚類結果中，每一類類內更加緊湊，類間可以很好地分離出來。

圖3 基于TFIDF+LSA的聚類可視化

4.3.2 不同聚類方式取不同k值的SSE

改變實驗中的聚類數目k值，k值依此從2取到20,根據不同的聚類方式得到不同k值下的SSE值，如圖4所示。

圖4 基于TFIDF聚類和TFIDF+LSA聚類的SSE

從圖4可以看出，在相同的k值下，基于TFIDF+LSA的聚類得到的平方誤差和SSE更小。整體上，基于TFIDF聚類得到的平方誤差和SSE在11 000到10 000之間，基于TFIDF+LSA的聚類得到的平方誤差和SSE在6 200到1 000左右。SSE越小，表明聚類的效果越好。

4.3.3 不同聚類方式的評估值對比

不同聚類方式的評估指標值對比如表4所示。

表4 不同聚類方式的評估指標值對比

從表4可以看出，基于TFIDF的聚類和基于TFIDF+LSA的聚類得到的聚類評估指標值相差很大。并且，基于后者聚類得到的SC、CHI和DBI都比前者好，其中基于TFIDF+LSA聚類得到的SC的值約是基于TFIDF聚類得到的值的23倍，CHI的值約是基于TFIDF聚類得到的值的35倍，而DBI的值約是基于TFIDF的值的0.16倍。即基于TFIDF+LSA的聚類得到的聚類結果比基于TFIDF的聚類結果好。

4.3.4 不同聚類方式時間對比

從圖5可以看出，基于TFIDF的聚類方式所需的聚類時間遠遠高于基于TFIDF+LSA的聚類時間，表明基于TFIDF+LSA的聚類方式的聚類時間更短，速度更快。且基于TFIDF聚類的時間約是基于TFIDF+LSA聚類的55倍。

圖5 不同聚類方式的聚類時間

4.3.5 實驗結果分析

綜上，基于TFIDF+LSA的聚類得到的聚類結果比基于TFIDF的聚類結果好，主要是因為前者使用了潛在語義分析算法，將單詞文本矩陣分解為單詞話題矩陣和話題文本矩陣。也即前者在聚類時使用到了話題文本矩陣進行聚類，而后者是使用單詞文本矩陣進行聚類。使用前者聚類一方面可以將原始矩陣進行了降維，提取了矩陣的話題信息，另一方面同一話題內的詞的詞義更相近，有利于更好地聚類。

而且，由于kmeans算法聚類的時間復雜度為O(mnkt),其中m是樣本的維數，n是樣本的個數，k是聚類個數，t是迭代次數。而基于TFIDF+LSA的聚類方式的時間復雜度為O(knkt)，即將m維降到了k維，也就降低了聚類整體的時間復雜度，提高了聚類速度，降低了聚類時間。同時從空間復雜度上分析，基于TFIDF的聚類方式所需要的空間為O(mn),基于TFIDF+LSA的聚類方式所需的空間復雜度為O(kn)，其中k是遠遠小于m的。因此，與基于TFIDF的聚類方式相比，基于TFIDF+LSA的聚類算法也減少了空間復雜度。

5 結束語

將TFIDF算法和LSA算法相結合，提出基于TFIDF+LSA聚類方式，通過計算TFIDF值來得到詞在文本中的權重，然后將得到的TFIDF權重矩陣運用潛在語義分析LSA算法來得到文本的話題表示，最后，用kmeans算法對話題文本矩陣進行聚類而不是用單詞文本矩陣對數據進行聚類。該文將這種方法應用到了實際的新聞文本數據聚類上，實驗結果表明，該方法大大提高了中文文本聚類的速度和可視化效果，可以對大規模的文本數據產生實際的應用價值。另一方面，在研究過程中也存在一些比較難以處理的問題，比如說，人工根據文本的內容將新聞文本分為某一類，實際上，一篇文章有可能是關于多個話題的，即可能是屬于多個類的，在這種情況下，若后續對文本進行分類處理，研究其準確率等分類指標的時候，對于這種情況，只要這篇文章屬于正確話題中的某一個，那么就算是分類正確的。