基于核函數(shù)的改進(jìn)k-means文本聚類

張國(guó)鋒 吳國(guó)文

(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 200050)

0 引 言

在計(jì)算機(jī)技術(shù)全面發(fā)展的當(dāng)代，人工智能在生活當(dāng)中的作用越來(lái)越重要，應(yīng)用的范圍也十分廣泛，各行各業(yè)都對(duì)人工智能進(jìn)行了大量的鉆研。人們都希望在有限的時(shí)間內(nèi)做足夠多的事，這其中就包括閱讀。就像在圖書(shū)館中閱讀一樣，人們?cè)谑謾C(jī)以及計(jì)算機(jī)上查閱資料或者閱讀文章時(shí)，希望能夠大大減少尋找同類型文章的時(shí)間，希望這些文章能夠存放在一起而不是錯(cuò)綜復(fù)雜的排列。但如果人工對(duì)文章進(jìn)行分類需要花費(fèi)大量的時(shí)間和精力，因此，讓計(jì)算機(jī)來(lái)為人們提供最便捷的服務(wù)是大勢(shì)所趨，機(jī)器學(xué)習(xí)中的聚類算法就得到了用武之地。

聚類算法屬于“無(wú)監(jiān)督學(xué)習(xí)”，而且是其中被人們研究、使用最多的算法。在聚類分析之前，每一個(gè)數(shù)據(jù)或樣本屬性的歸類是不確定的，屬性能被分成多少類一般也是需要預(yù)測(cè)的，只能依靠元數(shù)據(jù)進(jìn)行分析，不像分類算法可以參考相關(guān)類別的信息。聚類分析方法主要在探索研究方面應(yīng)用較多，最終的結(jié)果可能包含多種有價(jià)值的答案，如何進(jìn)行篩選要依靠研究人員的實(shí)際需求和具體分析。無(wú)論實(shí)際數(shù)據(jù)能否真地被分成不同種類，使用聚類分析都可以將數(shù)據(jù)劃分成特定數(shù)量的類別。聚類可以單獨(dú)使用來(lái)獲取數(shù)據(jù)的具體分布情況，通過(guò)研究聚類出的各個(gè)簇中數(shù)據(jù)的特征，找出特征顯著的簇進(jìn)行更加具體詳細(xì)的分析。

1 文本預(yù)處理

若要對(duì)文章進(jìn)行聚類，需要對(duì)文章進(jìn)行一定的處理，這些操作包括對(duì)文章進(jìn)行分詞、去除停用詞、使用TF-IDF找出每篇文章的關(guān)鍵詞以及使用Word2Vec將關(guān)鍵詞向量化。

1.1 分詞處理

首先使用jieba算法對(duì)文章進(jìn)行分詞。jieba分詞有三種模式：精確模式、全模式以及搜索引擎模式。這里使用精確模式，此模式的目的是把語(yǔ)句最精確地切分開(kāi)，適用于文本分析，分詞之后的文本存入txt文件中。

其次需要去除停用詞。分詞之后的文本現(xiàn)在以若干詞語(yǔ)集合的形式呈現(xiàn)。其中很多字詞并沒(méi)有實(shí)際的意義，例如“的”、“是”等，這些詞會(huì)影響之后提取關(guān)鍵字的準(zhǔn)確性，因此需要把這些沒(méi)有實(shí)際意義的字詞除去。由此構(gòu)造了一個(gè)停用詞字典，對(duì)詞語(yǔ)集合進(jìn)行篩選，若集合中的字詞出現(xiàn)在停用詞字典中，則刪除。

1.2 特征選取

本文使用TF-IDF算法找出文本中的關(guān)鍵詞，將權(quán)值最大的20個(gè)關(guān)鍵詞作為特征代表文本進(jìn)行聚類。TF-IDF的原理可以通俗易懂的解釋為：如果一個(gè)詞語(yǔ)或者短語(yǔ)在某篇文章中以很高的頻率出現(xiàn)，然而在其他的文章中幾乎沒(méi)有，那么就認(rèn)為這個(gè)詞語(yǔ)或者短語(yǔ)具有良好的代表性，適合用來(lái)做區(qū)分。具體計(jì)算公式如下：

(1)

式中：i代表文本中的詞語(yǔ)；Ti表示該詞語(yǔ)出現(xiàn)的次數(shù)；Nt表示文章的總詞數(shù)；Dn表示文本總數(shù)；Dt表示包含詞語(yǔ)i的文本數(shù)。

返回的結(jié)果是一個(gè)列表和一個(gè)矩陣。列表中存放的是所有文本的詞語(yǔ)匯總，每個(gè)詞語(yǔ)只存儲(chǔ)一次。矩陣每行存儲(chǔ)的是每個(gè)詞語(yǔ)在一個(gè)文本中的權(quán)值數(shù)據(jù)，排列順序與列表中詞語(yǔ)的排列順序一致，若某個(gè)詞并未出現(xiàn)在某個(gè)文本中，則權(quán)值為0。

1.3 文本向量化

最后的處理工作是把文本向量化。把分詞后的所有文本當(dāng)作語(yǔ)料庫(kù)，使用Word2Vec模型進(jìn)行詞向量化。Word2Vec根據(jù)詞義把詞語(yǔ)映射到距離接近的空間中，詞向量能夠表達(dá)出一定的語(yǔ)義信息。此次選擇CBOW訓(xùn)練模式，這種模式通過(guò)前后文預(yù)測(cè)目標(biāo)詞。屬性windows意思是目標(biāo)詞與預(yù)測(cè)詞的距離，此次大小設(shè)為5，通過(guò)目標(biāo)詞前后文共10個(gè)詞得到當(dāng)前詞的向量，維度size設(shè)定為20。在得到的向量庫(kù)中匹配出各個(gè)特征的向量Vi，將特征向量相加得到最終的文本向量Vd：

(2)

這樣就可以使用向量Vd來(lái)進(jìn)行聚類工作。

2 相似度定義

本文使用高斯核函數(shù)計(jì)算文本之間的相似度。高斯核函數(shù)的公式如下：

(3)

一種等價(jià)且更為簡(jiǎn)單的定義公式為：

(4)

式中：γ=1/2σ2。

高斯核函數(shù)對(duì)于數(shù)據(jù)中的噪音有著很不錯(cuò)的抗干擾能力，函數(shù)中的σ參數(shù)決定了函數(shù)的有效區(qū)域，超過(guò)了此范圍，數(shù)據(jù)的影響就會(huì)基本忽略。由于噪音對(duì)k-means算法的影響很大，所以使用高斯核函數(shù)來(lái)降低噪音的影響。此外，高斯核函數(shù)能夠利用高維空間向量之間的內(nèi)積得出兩個(gè)點(diǎn)之間的距離，降低了計(jì)算難度。

高斯核函數(shù)對(duì)自身的參數(shù)σ比較敏感，本次實(shí)驗(yàn)通過(guò)交叉驗(yàn)證法確定參數(shù)σ。使用距離協(xié)方差作為參數(shù)，因?yàn)閰f(xié)方差能很好地反映各維數(shù)據(jù)的離散狀況，很符合核函數(shù)參數(shù)的性質(zhì)。協(xié)方差公式如下：

(5)

其中:n代表數(shù)據(jù)的總數(shù)；xi為第i個(gè)具體的數(shù)據(jù)。

從原始數(shù)據(jù)中隨機(jī)選擇400個(gè)數(shù)據(jù)，平均分為4組，其中三組記為A、B、C，當(dāng)作訓(xùn)練集，最后一組記為D，作為最終的驗(yàn)證集，用驗(yàn)證集來(lái)選出最合適的一個(gè)當(dāng)作參數(shù)。

具體做法是：使用傳統(tǒng)k-means算法對(duì)三個(gè)訓(xùn)練集進(jìn)行聚類，使用歐氏距離作為距離公式，k值定為3。每組聚類后會(huì)有3個(gè)簇，把各簇誤差的協(xié)方差(精確到小數(shù)點(diǎn)后五位)分別記為s1、s2、s3，把它們的平均值記作S，這里的誤差是指當(dāng)前點(diǎn)到簇質(zhì)心的距離。隨后將它們分別代入高斯核函數(shù)中，使用測(cè)試集D的數(shù)據(jù)進(jìn)行聚類。測(cè)試集使用誤差平方和(SSE)來(lái)評(píng)估聚類效果，SSE的值越小，表示數(shù)據(jù)點(diǎn)離它們的質(zhì)心越近，聚類效果也就越好。測(cè)試集每個(gè)簇的誤差平方和分別用d1、d2、d3表示，從中選出平均誤差平方和最小的一組，將S值作為σ。訓(xùn)練集具體數(shù)據(jù)如表1所示。

表1 訓(xùn)練集數(shù)據(jù)

測(cè)試集數(shù)據(jù)如表2所示。

表2 測(cè)試集結(jié)果

由測(cè)試集數(shù)據(jù)可了解到，當(dāng)S為0.002 17的時(shí)候，效果最好，這表明，可以確定σ取值為0.002 17。

3 k-means算法改進(jìn)

3.1 傳統(tǒng)k-means算法

k-means是劃分方法中較經(jīng)典的聚類算法之一。由于該算法的效率高，所以普遍應(yīng)用于對(duì)大規(guī)模數(shù)據(jù)進(jìn)行聚類。目前，許多算法均圍繞著該算法進(jìn)行擴(kuò)展和改進(jìn)。

k-means算法的邏輯如下：確定聚類的個(gè)數(shù)k，隨機(jī)確定初始質(zhì)心的坐標(biāo)，選擇合適的距離公式計(jì)算每個(gè)數(shù)據(jù)與每個(gè)質(zhì)心的距離，并將其聚類到距離最近的簇中。在所有數(shù)據(jù)完成聚類后，更新每個(gè)簇的質(zhì)心坐標(biāo)并重新計(jì)算每個(gè)點(diǎn)與質(zhì)心的距離，將數(shù)據(jù)點(diǎn)重新聚類到距離最近的簇中。重復(fù)以上步驟直到質(zhì)心不再變化，聚類完成。

k-means算法的優(yōu)點(diǎn)是簡(jiǎn)單、快速，當(dāng)數(shù)據(jù)很密集時(shí)，效果較好。缺點(diǎn)是要事先確定準(zhǔn)備生成的簇的數(shù)目k，對(duì)于初始質(zhì)心坐標(biāo)和噪聲很敏感，不同的初始值結(jié)果可能會(huì)不一樣，當(dāng)k值預(yù)估過(guò)大時(shí)，可能出現(xiàn)空簇。

3.2 使用改進(jìn)的k-means算法聚類

由于初始質(zhì)心的隨機(jī)性對(duì)k-means的結(jié)果影響很大，數(shù)據(jù)很可能收斂到局部最小值，并且會(huì)產(chǎn)生空簇，所以此次實(shí)驗(yàn)對(duì)傳統(tǒng)k-means做出了改進(jìn)。

用k′表示距離指定k值的差，Δk表示當(dāng)前將要增加的質(zhì)心數(shù)。改進(jìn)后的算法先隨機(jī)生成k/2個(gè)初始質(zhì)心，初始k′=k-k/2。將所有數(shù)據(jù)聚類到k/2個(gè)簇中，如果有a個(gè)簇中沒(méi)有數(shù)據(jù)，則直接刪除這些質(zhì)心并更新k′=k′+a。每次增加Δk=k′/2個(gè)質(zhì)心，利用誤差平方和來(lái)判斷聚類過(guò)程中的效果，找出聚類過(guò)程中SSE值最大的Δk個(gè)簇分別進(jìn)行k為2的局部聚類，將原先的簇劃分成兩個(gè)，再重新計(jì)算每個(gè)簇的SSE，重復(fù)以上步驟，直到簇的數(shù)目達(dá)到k為止。

具體步驟為：

(1) 初始化k/2個(gè)質(zhì)心，質(zhì)心坐標(biāo)隨機(jī)確定：

(6)

(2) 將所有的數(shù)據(jù)聚類到這些簇中，判斷是否有空簇并記錄個(gè)數(shù)a，若有即刻刪除，并更新k′和Δk：

k′=k′+a

(7)

Δk=k′/2

(8)

(3) 比較每個(gè)簇的SSE值,找出值最大的Δk個(gè)簇，進(jìn)行局部二分聚類。

(4) 更新k′以及Δk的值并重復(fù)第3步的操作：

k′=k′-Δk

(9)

(5) 當(dāng)簇的數(shù)量達(dá)到k即k′為0時(shí)，聚類結(jié)束。

經(jīng)過(guò)這一改進(jìn)后，可以有效降低SSE的值，使數(shù)據(jù)最大化地收斂到全局最小值，還可以避免出現(xiàn)空簇，改善了有效簇未達(dá)到期望值的缺陷。

4 結(jié)果分析

4.1 實(shí)驗(yàn)一

為了對(duì)比，分別使用傳統(tǒng)k-means算法和改進(jìn)后的k-means算法做了兩組聚類對(duì)比實(shí)驗(yàn)。選取的文本字?jǐn)?shù)在500到1 500字之間，具有普遍性和一般性。數(shù)據(jù)文本共選取2 000篇，分為三組，第一組300篇，第二組700篇，第三組1 000篇。

由于計(jì)算距離公式不同，所以使用平均誤差平方和(AvgSSE)與最大誤差平方和(MaxSSE)的比值(pSSE)作為評(píng)估標(biāo)準(zhǔn)之一，計(jì)算公式如下：

(10)

比值保留到小數(shù)點(diǎn)后5位。結(jié)果分別從聚類的迭代次數(shù)(t)、pSSE以及空簇的數(shù)量(Ne)進(jìn)行對(duì)比。結(jié)果如表3所示。

表3 實(shí)驗(yàn)一結(jié)果對(duì)比

由最后結(jié)果對(duì)比可知，在迭代次數(shù)上，改進(jìn)后的算法較傳統(tǒng)算法所用次數(shù)明顯減少。原因有兩點(diǎn)：第一是初始的質(zhì)心只為k值的一半，基礎(chǔ)的迭代次數(shù)必然減少；第二是因?yàn)樗惴ê笃诘木植烤垲愊喈?dāng)于二分聚類，每次增長(zhǎng)的幅度相對(duì)較小。

在pSSE方面，改進(jìn)后的算法要大于傳統(tǒng)算法。pSSE較小說(shuō)明最大的誤差平方和相對(duì)較大，傳統(tǒng)的聚類方法得出的簇很可能出現(xiàn)某一簇的范圍很大而其他簇的位置很集中，這就說(shuō)明聚類效果不是很好。而改進(jìn)后的算法聚類出的每個(gè)簇的數(shù)據(jù)更集中，平均每個(gè)數(shù)據(jù)距離質(zhì)心更近,從而說(shuō)明改進(jìn)后的算法聚類效果要優(yōu)于傳統(tǒng)算法。

此外，較大數(shù)據(jù)量的兩組分別聚類了兩次進(jìn)行對(duì)比。可以看到改進(jìn)后的算法并沒(méi)有出現(xiàn)空簇，而傳統(tǒng)算法雖數(shù)據(jù)量沒(méi)有變，但是由于初始的質(zhì)心發(fā)生變化，導(dǎo)致出現(xiàn)的空簇?cái)?shù)量不定，或多或少，隨著文本的增多，出現(xiàn)空簇的可能性也增大。改進(jìn)后的算法徹底修正了傳統(tǒng)算法的這個(gè)缺陷，保證了聚類結(jié)果能達(dá)到數(shù)量上的基本要求。

4.2 實(shí)驗(yàn)二

實(shí)驗(yàn)二選取了金融類、汽車類、體育類、天氣類以及食品類文本各100篇混合成源數(shù)據(jù)進(jìn)行聚類。分別從準(zhǔn)確率(precision)、召回率(recall)以及F值進(jìn)行對(duì)比。準(zhǔn)確率是指聚類后，各類文本數(shù)量Nt與該簇全部文本數(shù)量NT的比值。公式為：

precision=Nt/NT

(11)

召回率是指Nt占相對(duì)應(yīng)類型文本Nm的比值：

recall=Nt/Nm

(12)

F值計(jì)算公式為：

(13)

實(shí)驗(yàn)結(jié)果如表4所示。

由實(shí)驗(yàn)二數(shù)據(jù)可以看出，改進(jìn)后的算法整體在準(zhǔn)確率和召回率上都有了明顯提升，F(xiàn)值也因此提高。只有食品類準(zhǔn)確率少許降低，原因可能是食品類文本中的詞語(yǔ)與其他類重復(fù)得過(guò)多，但召回率的提高使得F值并沒(méi)有降低。由此從整體上來(lái)看，改進(jìn)后算法的聚類效果比傳統(tǒng)算法的聚類效果要好。

5 結(jié) 語(yǔ)

本文結(jié)合TF-IDF與Word2Vec對(duì)文本實(shí)現(xiàn)向量化，并針對(duì)傳統(tǒng)k-means算法易收斂到局部最小值，對(duì)噪聲敏感等不足之處做出改進(jìn)，以高斯核函數(shù)作為距離公式，并在聚類過(guò)程中降低誤差平方和，提升聚類效果，對(duì)文本進(jìn)行了高效聚類。實(shí)驗(yàn)結(jié)果表明，本文算法在效果上優(yōu)于傳統(tǒng)k-means聚類，并消除了聚類結(jié)果出現(xiàn)空簇的可能性。