郝秀慧,方賢進,楊高明

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

0 引 言

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

1 文本預(yù)處理

1.1 TFIDF算法

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

(1)

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

1.2 LSA算法

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

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

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

Xm×n≈Um×kΣkVk×n

(2)

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

2 TFIDF+LSA算法

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

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

3 聚類算法

3.1 kmeans算法

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

(3)

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

kmeans算法步驟如下：

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

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

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

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

3.2 kmeans++算法

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

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

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

(4)

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

4 實驗和性能分析

4.1 平臺與數(shù)據(jù)

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

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

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

表2 部分停用詞表

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

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

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

4.2 聚類評估指標(biāo)

4.2.1 輪廓系數(shù)

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

(5)

(6)

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

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

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

(7)

(8)

(9)

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

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

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

(10)

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

4.3 實驗結(jié)果與分析

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

圖2 基于TFIDF的聚類可視化

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

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

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

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

改變實驗中的聚類數(shù)目k值，k值依此從2取到20,根據(jù)不同的聚類方式得到不同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 不同聚類方式的評估值對比

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

表4 不同聚類方式的評估指標(biāo)值對比

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

4.3.4 不同聚類方式時間對比

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

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

4.3.5 實驗結(jié)果分析

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

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

5 結(jié)束語

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