基于TFIDF+LSA算法的新聞文本聚類(lèi)與可視化

郝秀慧,方賢進(jìn),楊高明

(安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001)

0 引 言

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

1 文本預(yù)處理

1.1 TFIDF算法

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

(1)

其中，fij代表詞j在文檔i中的出現(xiàn)頻率,即詞j在文檔i中出現(xiàn)的頻次與文檔i中總詞數(shù)的比，N代表總文檔數(shù)，nj代表出現(xiàn)詞j的文檔數(shù)。上述公式表示的是當(dāng)一個(gè)詞在一篇文章中出現(xiàn)的頻次多且在其他文章中出現(xiàn)的次數(shù)少時(shí),tfidfij的值是比較大的，也就是表示這個(gè)詞j對(duì)這篇文章i比較重要。解決的是當(dāng)一個(gè)文檔中有相同詞頻的不同詞時(shí)，區(qū)分這些詞對(duì)文檔的重要性問(wèn)題。例如，詞1與詞2在文檔i中有相同的詞頻，那這時(shí)僅僅用詞頻來(lái)計(jì)算詞的重要性是不能區(qū)分兩詞的重要性的。通過(guò)引入反文檔頻率，計(jì)算這兩個(gè)詞在整個(gè)文檔集中的反文檔頻率，若詞1在整個(gè)文檔集中出現(xiàn)的次數(shù)較少，而詞2在整個(gè)文檔集中出現(xiàn)的次數(shù)較多，那么就說(shuō)明，詞1比詞2有更好的文檔區(qū)分能力。對(duì)文檔i來(lái)說(shuō)，詞1的TFIDF的值就會(huì)比詞2的TFIDF的值大。

1.2 LSA算法

LSA也稱(chēng)為潛在語(yǔ)義分析[7]，是一種無(wú)監(jiān)督學(xué)習(xí)方法，主要用在文本的話題分析上，是通過(guò)對(duì)矩陣進(jìn)行分解來(lái)發(fā)現(xiàn)文本與單詞之間的基于話題的語(yǔ)義關(guān)系。具體實(shí)現(xiàn)是將文本集合表示為單詞文本矩陣，根據(jù)確定的話題個(gè)數(shù)，對(duì)單詞文本矩陣進(jìn)行截?cái)嗥娈愔捣纸?TruncatedSVD)[8-9]，從而得到話題向量空間，以及文本在話題向量空間的表示。形式化表達(dá)分解公式如下：

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

潛在語(yǔ)義分析矩陣分解數(shù)學(xué)公式[8]如下：

Xm×n≈Um×kΣkVk×n

(2)

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

2 TFIDF+LSA算法

由于TFIDF+LSA算法是結(jié)合TFIDF算法和LSA算法得來(lái)，該文結(jié)合兩種算法的過(guò)程如圖1所示。

圖1 TFIDF+LSA算法的結(jié)合過(guò)程

3 聚類(lèi)算法

3.1 kmeans算法

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

(3)

其中，centeri是第i個(gè)類(lèi)別的類(lèi)中心。公式所要表達(dá)的含義是計(jì)算每類(lèi)內(nèi)數(shù)據(jù)到該類(lèi)類(lèi)中心的歐氏距離的和,描述的是每個(gè)類(lèi)類(lèi)內(nèi)距離到該類(lèi)中心的緊密程度,值越小,表示類(lèi)內(nèi)越緊密。

kmeans算法步驟如下：

步驟一：選擇k個(gè)初始中心點(diǎn)，該文采用kmeans++算法來(lái)選擇k個(gè)初始中心點(diǎn)。

步驟二：計(jì)算點(diǎn)到k個(gè)初始中心的歐氏距離[11]，并將點(diǎn)歸類(lèi)為與初始中心最近的點(diǎn)的類(lèi)別，依此計(jì)算其他點(diǎn)到k個(gè)中心的距離，并歸類(lèi)。

步驟三：通過(guò)計(jì)算每類(lèi)的均值，更新聚類(lèi)中心。

步驟四：重復(fù)步驟二和步驟三，直至聚類(lèi)達(dá)到收斂條件。

3.2 kmeans++算法

由于kmeans算法的聚類(lèi)效果受初始中心點(diǎn)選取的影響比較大，因此有學(xué)者改進(jìn)了kmeans算法，即kmeans++算法選擇初始中心點(diǎn)的方式是以較大的概率選擇離已經(jīng)選取的聚類(lèi)中心點(diǎn)最遠(yuǎn)的點(diǎn)作為下一個(gè)初始中心點(diǎn)。算法步驟如下：

步驟一：隨機(jī)從輸入的數(shù)據(jù)集X中選取一個(gè)點(diǎn)作為第一個(gè)種子。

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

(4)

步驟三：重復(fù)步驟二直至獲得k個(gè)種子，即得到k個(gè)初始聚類(lèi)中心。

4 實(shí)驗(yàn)和性能分析

4.1 平臺(tái)與數(shù)據(jù)

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

表1 采集的部分?jǐn)?shù)據(jù)

當(dāng)采集到文本數(shù)據(jù)之后，經(jīng)過(guò)數(shù)據(jù)清洗，包括對(duì)文本去重、分詞、去停用詞等操作后才能進(jìn)行后續(xù)數(shù)據(jù)的預(yù)處理操作。其中，該實(shí)驗(yàn)是基于結(jié)巴分詞得到的分詞結(jié)果。去停用詞的操作主要是建立停用詞表，目前比較全的有哈工大的停用詞表。該實(shí)驗(yàn)使用的停用詞表包含有1 214個(gè)詞，包括特殊符號(hào)、不常用的詞以及無(wú)意義的詞等，當(dāng)然，也可以根據(jù)使用的不同語(yǔ)料庫(kù)和個(gè)人實(shí)驗(yàn)的需要，增加停用詞，建立適合實(shí)驗(yàn)需要的停用詞表，將分詞后不常用的詞或者是沒(méi)有意義的詞都可以加入到停用詞表中。根據(jù)停用詞表的不同類(lèi)別做出部分停用詞，如表2所示。

表2 部分停用詞表

根據(jù)TFIDF+LSA的方法得到的類(lèi)別劃分情況如表3所示。

表3 數(shù)據(jù)類(lèi)別劃分情況

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

4.2 聚類(lèi)評(píng)估指標(biāo)

4.2.1 輪廓系數(shù)

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

(5)

(6)

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

4.2.2 卡林斯基-原巴斯指數(shù)

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

(7)

(8)

(9)

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

4.2.3 戴維斯-堡丁指數(shù)

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

(10)

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

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

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

圖2 基于TFIDF的聚類(lèi)可視化

4.3.1 聚類(lèi)可視化結(jié)果

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

圖3 基于TFIDF+LSA的聚類(lèi)可視化

4.3.2 不同聚類(lèi)方式取不同k值的SSE

改變實(shí)驗(yàn)中的聚類(lèi)數(shù)目k值，k值依此從2取到20,根據(jù)不同的聚類(lèi)方式得到不同k值下的SSE值，如圖4所示。

圖4 基于TFIDF聚類(lèi)和TFIDF+LSA聚類(lèi)的SSE

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

4.3.3 不同聚類(lèi)方式的評(píng)估值對(duì)比

不同聚類(lèi)方式的評(píng)估指標(biāo)值對(duì)比如表4所示。

表4 不同聚類(lèi)方式的評(píng)估指標(biāo)值對(duì)比

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

4.3.4 不同聚類(lèi)方式時(shí)間對(duì)比

從圖5可以看出，基于TFIDF的聚類(lèi)方式所需的聚類(lèi)時(shí)間遠(yuǎn)遠(yuǎn)高于基于TFIDF+LSA的聚類(lèi)時(shí)間，表明基于TFIDF+LSA的聚類(lèi)方式的聚類(lèi)時(shí)間更短，速度更快。且基于TFIDF聚類(lèi)的時(shí)間約是基于TFIDF+LSA聚類(lèi)的55倍。

圖5 不同聚類(lèi)方式的聚類(lèi)時(shí)間

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

綜上，基于TFIDF+LSA的聚類(lèi)得到的聚類(lèi)結(jié)果比基于TFIDF的聚類(lèi)結(jié)果好，主要是因?yàn)榍罢呤褂昧藵撛谡Z(yǔ)義分析算法，將單詞文本矩陣分解為單詞話題矩陣和話題文本矩陣。也即前者在聚類(lèi)時(shí)使用到了話題文本矩陣進(jìn)行聚類(lèi)，而后者是使用單詞文本矩陣進(jìn)行聚類(lèi)。使用前者聚類(lèi)一方面可以將原始矩陣進(jìn)行了降維，提取了矩陣的話題信息，另一方面同一話題內(nèi)的詞的詞義更相近，有利于更好地聚類(lèi)。

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

5 結(jié)束語(yǔ)

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