K-means算法中文文獻(xiàn)聚類的Python實(shí)現(xiàn)

摘 ?要： 聚類是對(duì)文本信息進(jìn)行有效組織、摘要和導(dǎo)航的重要手段。K-means算法是非常典型的基于距離的聚類算法，將其用于中文文獻(xiàn)聚類，按照內(nèi)容相似性把一組文獻(xiàn)分成幾個(gè)類并發(fā)現(xiàn)其中的隱形知識(shí)。本文通過(guò)實(shí)例，總結(jié)了基于Python語(yǔ)言的K-means算法用于中文文獻(xiàn)聚類過(guò)程，通過(guò)CH指標(biāo)、輪廓系數(shù)指標(biāo)和SSE指標(biāo)這三個(gè)評(píng)價(jià)指標(biāo)選取K-means算法的初始聚類簇?cái)?shù)，即最優(yōu)k值的取值范圍，然后分別按照基于關(guān)鍵詞和基于摘要對(duì)文獻(xiàn)進(jìn)行聚類，并對(duì)聚類結(jié)果進(jìn)行比較分析，從而得出基于摘要對(duì)中文文獻(xiàn)進(jìn)行聚類可以得到更好結(jié)果的結(jié)論，同一類別中的文獻(xiàn)可以進(jìn)行關(guān)鍵詞聚類，從而進(jìn)一步挖掘其中的隱形知識(shí)。

關(guān)鍵詞： K-means算法;文獻(xiàn)聚類;評(píng)價(jià)指標(biāo)

中圖分類號(hào)： TP311.1. ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.08.021

本文著錄格式：趙謙益. K-means算法中文文獻(xiàn)聚類的Python實(shí)現(xiàn)[J]. 軟件，2019，40（8）：8994

【Abstract】： Clustering is an important means of effective organization， summarization and navigation of text information. The K-means algorithm is a very typical distance-based clustering algorithm. It is used for Chinese document clustering. According to the content similarity， a group of documents is divided into several categories and the invisible knowledge is found. In this paper， the K-means algorithm based on Python language is used to summarize the Chinese literature clustering process. The initial cluster cluster number of K-means algorithm is selected by three evaluation indexes： CH index， contour coefficient index and SSE index. The range of optimal k-values is then clustered according to keywords and based on abstracts， and the clustering results are compared and analyzed， so that the clustering of Chinese documents based on abstracts can get better results. In conclusion， the literature in the same category can be clustered by keywords to further explore the invisible knowledge.

【Key words】： K-means algorithm; Literature clustering; Evaluation index

0 ?引言

聚類算法是一種無(wú)監(jiān)督的知識(shí)發(fā)現(xiàn)算法。利用其對(duì)中文文獻(xiàn)進(jìn)行聚類，目的是發(fā)現(xiàn)其中的隱形知識(shí)。所謂文獻(xiàn)，文，指有關(guān)典章制度的文字資料，獻(xiàn)，指熟悉掌故的人。文獻(xiàn)是記錄、積累、傳播和繼承知識(shí)的最有效手段，是人類社會(huì)活動(dòng)中獲取情報(bào)的最基本、最主要的來(lái)源，也是交流傳播情報(bào)的最基本手段。文獻(xiàn)數(shù)據(jù)為非結(jié)構(gòu)化數(shù)據(jù)，能夠?qū)ζ溥M(jìn)行有效的數(shù)據(jù)分析，是文本數(shù)據(jù)挖掘重要的目標(biāo)。文獻(xiàn)聚類是按照內(nèi)容相似性把一組文獻(xiàn)分成幾個(gè)類的過(guò)程。當(dāng)前使用的文獻(xiàn)聚類技術(shù)可分為兩大類：層次聚類技術(shù)

和劃分聚類技術(shù)。層次聚類技術(shù)的代表是凝聚聚類技術(shù)，劃分聚類技術(shù)的代表是K-means聚類技術(shù)[1]。有效地對(duì)文獻(xiàn)進(jìn)行聚類，才可為后續(xù)文本數(shù)據(jù)分析做準(zhǔn)備。簡(jiǎn)而言之，聚類的結(jié)果是樣本數(shù)據(jù)對(duì)象構(gòu)成的多個(gè)類或簇（cluster），一個(gè)簇中的對(duì)象有較高的相似度（similarity），而不同簇中的對(duì)象差異較大，而這種相似度通常通過(guò)距離來(lái)度量[2-4]。

1 ?K-means算法原理

K-means算法是一種非常典型的基于距離的聚類算法，采用距離作為相似性的評(píng)價(jià)指標(biāo)，即該算法認(rèn)為兩個(gè)對(duì)象的距離越近，其相似度就越大。最常用的樣本間距離度量方法歐式距離，其計(jì)算公式為：

其中D表示樣本之間的距離;1指的是樣本特征的維數(shù);d代表樣本的總維數(shù)，即樣本特征的總數(shù)量。[5]

該算法認(rèn)為簇是由距離靠近的對(duì)象組成的，因此把得到緊湊且獨(dú)立的簇作為聚類結(jié)果的最終目標(biāo)。

k個(gè)初始類聚類中心點(diǎn)的選取會(huì)對(duì)較大地影響聚類結(jié)果，因?yàn)樵谠撍惴ǖ谝徊街惺沁x取初始聚類的中心，即k值，指定k個(gè)對(duì)象作為初始聚類的中心，初始地代表一個(gè)簇。該算法在每次迭代中對(duì)數(shù)據(jù)集中剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離將每個(gè)對(duì)象重新賦給最近的簇。當(dāng)考察完所有數(shù)據(jù)對(duì)象后，一次迭代運(yùn)算完成，新的聚類中心被計(jì)算出來(lái)。

如下圖是一個(gè)K=4的聚類示意圖，每個(gè)點(diǎn)都是到自己所在的簇的均值點(diǎn)更近，而這個(gè)均值點(diǎn)可以是原始數(shù)據(jù)中的點(diǎn)，也可以是一個(gè)不存在的點(diǎn)，即不屬于原始數(shù)據(jù)集中的點(diǎn)[6]。

由于本文筆者將研究K-means算法用于中文文獻(xiàn)聚類的Python實(shí)現(xiàn)方法，而并非某類實(shí)證研究，所以筆者只選取了較少的文獻(xiàn)數(shù)據(jù)為例進(jìn)行說(shuō)明，選取中國(guó)知網(wǎng)中有關(guān)大數(shù)據(jù)方向的被引量前50名的文獻(xiàn)進(jìn)行聚類，從而淺談K-means算法用于中文文獻(xiàn)聚類。

2 ?文獻(xiàn)特征表示

聚類分析首先需要處理數(shù)據(jù)集的特征選擇或變換。實(shí)際上，特征選擇與特征變換是降維技術(shù)的兩大分類。特征選擇指的是從數(shù)據(jù)樣本集的所有特征（或稱屬性）中選擇更有利于達(dá)到某種目標(biāo)的若干屬性，即原始屬性集的一一個(gè)子集，同時(shí)也達(dá)到了降低維度的目的;而特征變換則是指通過(guò)某種變換將原始輸入空間的屬性映射到一個(gè)新的特征空間，然后在特征空間中根據(jù)規(guī)則選擇某些較為重要的變換后的特征[7-10]。

筆者使用Python語(yǔ)言中的Jieba分詞對(duì)50篇文獻(xiàn)進(jìn)行分詞。在文獻(xiàn)特征化表示的過(guò)程中，調(diào)用Python語(yǔ)言中count_vec.fit_transform方法，即可將文獻(xiàn)轉(zhuǎn)換為詞篇矩陣，在此過(guò)程中類似于“的”等單字和標(biāo)點(diǎn)符號(hào)會(huì)被自動(dòng)刪除，所以在此過(guò)程中并不需要利用停用詞表進(jìn)行預(yù)處理。以下分別按照關(guān)鍵詞和摘要對(duì)文獻(xiàn)進(jìn)行向量化表示，得到詞篇矩陣結(jié)果為：

其中將分詞后的每一個(gè)詞作為一個(gè)維度，原文獻(xiàn)中出現(xiàn)該詞語(yǔ)，對(duì)出現(xiàn)次數(shù)進(jìn)行計(jì)數(shù)。以所有詞語(yǔ)構(gòu)成的多維向量空間表示該文獻(xiàn)。同理可得到文獻(xiàn)摘要的詞篇矩陣。將文獻(xiàn)轉(zhuǎn)換為詞篇矩陣后，即完成了文獻(xiàn)特征表示。

3 ?利用評(píng)價(jià)指標(biāo)確定最優(yōu)聚類簇?cái)?shù)

支持由于K-means算法需要事先人為指定算法聚類的簇?cái)?shù)，即指定k的取值，所以k值的選取對(duì)聚類結(jié)果具有較大的影響，在進(jìn)行最終聚類前，筆者將引用Calinski-Harabaz（CH）指標(biāo)，輪廓系數(shù)（silhouette coefficient）指標(biāo)和簇內(nèi)誤方差（SSE）指標(biāo)作為評(píng)價(jià)指標(biāo)，首先使用for循環(huán)對(duì)不同k值的聚類結(jié)果進(jìn)行評(píng)價(jià)匯總，并利用圖像進(jìn)行可視化表示，從而確定K-means算法最優(yōu)聚類簇?cái)?shù)，即k值。

3.1 ?Calinski-Harabaz（CH）指標(biāo)

CH指標(biāo)是通過(guò)計(jì)算每個(gè)類中各點(diǎn)與類中心點(diǎn)的距離平方和來(lái)度量聚類后各類內(nèi)的緊密程度，通過(guò)計(jì)算各類中心點(diǎn)與數(shù)據(jù)集中心點(diǎn)距離平方和來(lái)度量數(shù)據(jù)集的分離度，CH指標(biāo)由分離度與緊密度的比值得到。因此，CH越大代表著類自身越緊密，類與類之間越分散，即更優(yōu)的聚類結(jié)果。

其中，n表示聚類的數(shù)目，k表示當(dāng)前的類，trB（k）表示類間離差矩陣的跡，trW（k）表示類內(nèi)離差矩陣的跡。類別內(nèi)部數(shù)據(jù)的協(xié)方差越小越好，類別之間的協(xié)方差越大越好，這樣的Calinski-Harabasz分?jǐn)?shù)會(huì)高。Python語(yǔ)言中scikit-learn包中評(píng)價(jià)指標(biāo)Calinski-Harabasz Index對(duì)應(yīng)的方法是metrics. calinski_harabaz_score.通過(guò)圖形可以直觀的觀察到k對(duì)于聚類結(jié)果的影響。當(dāng)簇?cái)?shù)量為幾的時(shí)候出現(xiàn)了峰值，這說(shuō)明k取幾是一個(gè)不錯(cuò)的選擇。

3.2 ?輪廓系數(shù)（silhouette coefficient）指標(biāo)

輪廓分析（silhouette analysis），是使用圖形工具來(lái)度量簇中樣本的聚集程度。該評(píng)價(jià)算法通過(guò)三個(gè)步驟可以計(jì)算出當(dāng)個(gè)樣本的輪廓系數(shù)（silhouette coefficient）：第一步是將樣本x與簇內(nèi)的其他點(diǎn)之間的平均距離作為簇內(nèi)的內(nèi)聚度a。第二步是將樣本x與最近簇中所有點(diǎn)之間的平均距離看作是與最近簇的分離度b。第三步是將簇的分離度與簇內(nèi)聚度之差除以二者中比較大的數(shù)得到輪廓系數(shù)，其計(jì)算公式如下：

Python語(yǔ)言中scikit-learn包中該評(píng)價(jià)指標(biāo)對(duì)應(yīng)的方法是metrics.silhouette_score.輪廓系數(shù)的取值在–1到1之間。當(dāng)簇內(nèi)聚度與分度離相等時(shí)，輪廓系數(shù)為0。當(dāng)b>>a時(shí)，輪廓系數(shù)近似取到1，此時(shí)模型的性能最佳。通過(guò)圖形可以直觀的觀察到k對(duì)于聚類結(jié)果的影響。當(dāng)簇?cái)?shù)量為幾的時(shí)候出現(xiàn)了峰值，這說(shuō)明k取幾是一個(gè)不錯(cuò)的選擇。

3.3 ?簇內(nèi)誤方差（SSE）指標(biāo)

在對(duì)簇的劃分中，我們就使用了SSE作為目標(biāo)函數(shù)來(lái)劃分簇。當(dāng)KMeans算法訓(xùn)練完成后，我們可以通過(guò)使用inertia屬性來(lái)獲取簇內(nèi)的誤方差，不需要再次進(jìn)行計(jì)算。計(jì)算公式為：

Python語(yǔ)言中通過(guò)對(duì)應(yīng)kmeans.inertia_屬性來(lái)獲取簇內(nèi)的誤方差，同時(shí)可以使用圖形工具肘方法，根據(jù)簇的數(shù)量來(lái)可視化簇內(nèi)誤方差。通過(guò)圖形可以直觀的觀察到k對(duì)于簇內(nèi)誤方差的影響。當(dāng)簇?cái)?shù)量為幾的時(shí)候出現(xiàn)了肘型，這說(shuō)明k取幾是一個(gè)不錯(cuò)的選擇。

筆者選用以上三種評(píng)價(jià)指標(biāo)用于確定聚類的最優(yōu)簇?cái)?shù)，但需要注意的是不同的評(píng)價(jià)指標(biāo)對(duì)于不同的數(shù)據(jù)源，其敏感程度不同，所以筆者同時(shí)使用三種評(píng)價(jià)指標(biāo)，通過(guò)對(duì)比觀察得到最優(yōu)k值的取值范圍。

4 ?利用關(guān)鍵詞對(duì)文獻(xiàn)進(jìn)行聚類

實(shí)驗(yàn)利使用CountVectorizer方法將每篇文獻(xiàn)的關(guān)鍵詞轉(zhuǎn)換為詞篇矩陣后，利用Python語(yǔ)言中中對(duì)應(yīng)的KMeans（n_clusters=k， random_state=0）.fit（）方法對(duì)關(guān)鍵詞詞篇矩陣進(jìn)行聚類，并利用CH指標(biāo)，輪廓系數(shù)指標(biāo)和簇內(nèi)誤方差指標(biāo)（SSE）作為評(píng)價(jià)指標(biāo)，確定K-means算法的最優(yōu)k值，在Python語(yǔ)言中使用for循環(huán)進(jìn)行計(jì)算，并對(duì)結(jié)果使用matplotlib進(jìn)行繪圖展示，其結(jié)果見(jiàn)圖2，圖3，圖4。

對(duì)比以上三個(gè)評(píng)價(jià)指標(biāo)，由圖像可知CH指標(biāo)在k取值為13和26時(shí)出現(xiàn)波峰，但該波峰并不明顯。輪廓系數(shù)指標(biāo)在k取值為14和26時(shí)出現(xiàn)波峰，且相對(duì)明顯。而SSE指標(biāo)圖形在k取值為26以后變化較為穩(wěn)定。因此筆者將K-means算法的K值確定為14和26，使用Python語(yǔ)言對(duì)應(yīng)的KMeans（n_clusters=k， random_state=0）.fit（）方法，即將文獻(xiàn)按照關(guān)鍵詞聚為14類或26類時(shí)，分別得到聚類后的結(jié)果，再使用PCA（n_components=2）將多維結(jié)果降維到二維空間，使用matplotlib對(duì)結(jié)果進(jìn)行可視化繪圖，最終結(jié)果見(jiàn)圖5，圖6。

由上兩張圖觀察可得，利用三個(gè)評(píng)價(jià)指標(biāo)選出的最優(yōu)簇?cái)?shù)，無(wú)論是將文獻(xiàn)分為14簇還是26簇，代表文獻(xiàn)的圓點(diǎn)都有明顯地交叉，無(wú)法將文獻(xiàn)較好地進(jìn)行聚類。

5 ?利用摘要對(duì)文獻(xiàn)進(jìn)行聚類

使用CountVectorizer方法將每篇文獻(xiàn)的摘要轉(zhuǎn)換為詞篇矩陣后，同樣利用Python中對(duì)應(yīng)的KMeans（n_clusters=k， random_state=0）.fit（）方法，利用for循環(huán)多次計(jì)算各指標(biāo)結(jié)果，并使用matplotlib繪制CH指標(biāo)，輪廓系數(shù)指標(biāo)和簇內(nèi)誤方差指標(biāo)結(jié)果圖像作為評(píng)價(jià)指標(biāo)，確定K-means算法的最優(yōu)K值。其結(jié)果為：

對(duì)比以上三個(gè)評(píng)價(jià)指標(biāo)，由圖像可知CH指標(biāo)在k取值為8時(shí)最先出現(xiàn)波峰。輪廓系數(shù)指標(biāo)在k取值為2、3和5時(shí)出現(xiàn)相對(duì)明顯波峰。而SSE指標(biāo)圖形在k取值為8以后變化較為穩(wěn)定。筆者將K-means算法的K值確定為2、3、5和8，即將文獻(xiàn)按照關(guān)鍵詞聚為2類、3類、5類或8類時(shí)，使用Python語(yǔ)言對(duì)應(yīng)的KMeans（n_clusters=k， random_state=0）.fit（）方法，分別得到聚類后的結(jié)果，再使用PCA（n_components=2）將多維結(jié)果降維到二維空間，使用matplotlib對(duì)結(jié)果進(jìn)行可視化繪圖，分別得到聚類后的結(jié)果為：

由上面三個(gè)圖對(duì)比觀察可得，當(dāng)k取值為2時(shí)，聚類效果較好，即利用摘要可以較好地將文獻(xiàn)分為2類文獻(xiàn)聚類結(jié)果如下：

文獻(xiàn)聚類后，人為觀察聚類后的兩類文獻(xiàn)，筆者發(fā)現(xiàn)第一組聚類結(jié)果主要涵蓋大數(shù)據(jù)系統(tǒng)、模型、算法等技術(shù)類研究文獻(xiàn)和數(shù)據(jù)與金融、教育、城市發(fā)展的主題結(jié)合的實(shí)用類研究文獻(xiàn)。第二類聚類結(jié)果則是涵蓋研究綜述，發(fā)展現(xiàn)狀與展望等理論性研究文獻(xiàn)。

為了更準(zhǔn)確地對(duì)聚類后的文獻(xiàn)進(jìn)行分析，筆者認(rèn)為可以計(jì)算聚類后的文獻(xiàn)關(guān)鍵詞的相關(guān)系數(shù)，進(jìn)一步對(duì)聚類后的文獻(xiàn)進(jìn)行分析。筆者在這里選用的是皮爾森相關(guān)系數(shù)（Pearson correlation coefficient），也稱皮爾森積矩相關(guān)系數(shù)（Pearson product-moment correlation coefficient），是一種線性相關(guān)系數(shù)。皮爾森相關(guān)系數(shù)是用來(lái)反映兩個(gè)變量線性相關(guān)程度的統(tǒng)計(jì)量。相關(guān)系數(shù)用r表示，其中n為樣本量，分別為兩個(gè)變量的觀測(cè)值和均值。r描述的是兩個(gè)變量間線性相關(guān)強(qiáng)弱的程度。r的絕對(duì)值越大表明相關(guān)性越強(qiáng)。計(jì)算公式為：

可以通過(guò)K-means算法對(duì)關(guān)鍵詞進(jìn)行聚類，可得到聚類后文獻(xiàn)中個(gè)關(guān)鍵詞之間的關(guān)系，首先是使用Python語(yǔ)言中的.corr（）方法對(duì)經(jīng)由CountVectorizer方法特征提取后的關(guān)鍵詞詞篇矩陣進(jìn)行相關(guān)系數(shù)計(jì)算，得到一個(gè)相關(guān)系數(shù)矩陣，然后KMeans（n_clusters=k， random_state=0）.fit（）方法對(duì)相關(guān)系數(shù)矩陣進(jìn)行聚類，再使用PCA（n_components=2）將多維結(jié)果降維到二維空間，最后使用matplotlib對(duì)結(jié)果進(jìn)行可視化繪圖，其結(jié)果為。

由圖14可以直觀看出，第一組中可將關(guān)鍵詞分為5類，即該組文獻(xiàn)中涵蓋以下幾個(gè)方面的內(nèi)容：第一類為深度、智能、機(jī)器學(xué)習(xí)等;第二類為數(shù)據(jù)分析、大數(shù)據(jù)等;第三類為數(shù)據(jù)管理、信息安全等;第四類為知識(shí)計(jì)算;第五類為互聯(lián)網(wǎng)金融。

由圖15可以看出，第二組中可將關(guān)鍵詞分為3類，即該組文獻(xiàn)中涵蓋以下幾個(gè)方面的內(nèi)容：第一類為信息、電網(wǎng)等;第二類為文計(jì)算、數(shù)據(jù)處理技術(shù)等;第三類為數(shù)據(jù)挖掘、數(shù)據(jù)分析等。

6 ?總結(jié)

作為一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法， 聚類因其不需要訓(xùn)練過(guò)程、不需要預(yù)先對(duì)文檔手工標(biāo)注類別， 故具有較高的靈活性和自動(dòng)化處理能力，為對(duì)文本信息進(jìn)行有效組織、摘要和導(dǎo)航的重要手段[11-12]。筆者認(rèn)為利用K-means算法對(duì)中文文獻(xiàn)進(jìn)行聚類時(shí)，應(yīng)該使用文獻(xiàn)摘要進(jìn)行聚類，首先利用Python語(yǔ)言對(duì)文獻(xiàn)摘要進(jìn)行特征表示，即將中文文獻(xiàn)轉(zhuǎn)換為詞篇矩陣，再利用Calinski-Harabaz（CH）指標(biāo)，輪廓系數(shù)（silhouette coefficient）指標(biāo)和簇內(nèi)誤方差（SSE）標(biāo)作為評(píng)價(jià)指標(biāo)，從而確定K-means算法最優(yōu)聚類簇?cái)?shù)，即k值。可以選出多組K值在進(jìn)行繪圖比較，從而確定最優(yōu)聚類簇?cái)?shù)得到最后聚類結(jié)果。關(guān)鍵詞不能較好地對(duì)文獻(xiàn)進(jìn)行聚類，但筆者認(rèn)為可以計(jì)算聚類后同類別文獻(xiàn)關(guān)鍵詞的相關(guān)系數(shù)，從而得出各關(guān)鍵詞之間的聯(lián)系，達(dá)到進(jìn)一步對(duì)文獻(xiàn)進(jìn)行分析的目的。

參考文獻(xiàn)

[1] 李慧， 劉東蘇， 任志純. 文獻(xiàn)聚類技術(shù)及其評(píng)價(jià)函數(shù)[J]. 情報(bào)技術(shù)， 2004， 20（7）： 17-18.

[2] 陳磊磊. 不同距離測(cè)度的K-Means 文本聚類研究[J]. 軟件， 2015， 36（1）： 56-61.

[3] 申超波， 王志海， 孫艷歌. 基于標(biāo)簽聚類的多標(biāo)簽分類算法[J]. 軟件， 2014， 35（8）： 16-21.

[4] 唐波. 改進(jìn)的K?means聚類算法及應(yīng)用[J]. 軟件， 2012， 33（3）： 100-104.

[5] DUDARO， HARTPE， TORKDG. Pattern classification （2nd Edition）[M]. New York： John Wiley & Sons， 2001： 47-56.

[6] iphilo.k-mwans算法原理及numpy實(shí)現(xiàn)[EB/OL]. https：//blog. csdn.net/iphilo/article/details/80735944， 2018-06-19/2019-04-16.

[7] 章永來(lái)， 周耀鑒. 聚類算法綜述. 計(jì)算機(jī)應(yīng)用， 2019. doi： 101177/j..issn.1001-9081.2019010174.

[8] 田瑞， 閆丹鳳. 針對(duì)特定主題的短文本向量化[J]. 軟件， 2012， 33（11）： 202-205.

[9] 袁愛(ài)領(lǐng)， 齊偉， 錢旭. 基于流形正則化的支持向量機(jī)文本分類[J]. 軟件， 2013， 34（2）： 65-68.

[10] 姚清耘， 劉功申， 李翔. 基于向量空間模型的文本聚類算法[J]. 計(jì)算機(jī)工程， 2008， 34（18）： 39-41中的應(yīng)用[J]. 軟件， 2013， 34（1）： 158-159.

[11] 鄭世卓， 崔曉燕. 基于半監(jiān)督LDA的文本分類應(yīng)用研究[J]. 軟件， 2014， 35（1）： 46-48.

[12] 張彬. 探討人工智能在計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)中的應(yīng)用[J]. 軟件， 2012， 33（11）： 265-266.