基于核函數的改進k-means文本聚類

張國鋒 吳國文

(東華大學計算機科學與技術學院 上海 200050)

0 引 言

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

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

1 文本預處理

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

1.1 分詞處理

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

其次需要去除停用詞。分詞之后的文本現在以若干詞語集合的形式呈現。其中很多字詞并沒有實際的意義，例如“的”、“是”等，這些詞會影響之后提取關鍵字的準確性，因此需要把這些沒有實際意義的字詞除去。由此構造了一個停用詞字典，對詞語集合進行篩選，若集合中的字詞出現在停用詞字典中，則刪除。

1.2 特征選取

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

(1)

式中：i代表文本中的詞語；Ti表示該詞語出現的次數；Nt表示文章的總詞數；Dn表示文本總數；Dt表示包含詞語i的文本數。

返回的結果是一個列表和一個矩陣。列表中存放的是所有文本的詞語匯總，每個詞語只存儲一次。矩陣每行存儲的是每個詞語在一個文本中的權值數據，排列順序與列表中詞語的排列順序一致，若某個詞并未出現在某個文本中，則權值為0。

1.3 文本向量化

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

(2)

這樣就可以使用向量Vd來進行聚類工作。

2 相似度定義

本文使用高斯核函數計算文本之間的相似度。高斯核函數的公式如下：

(3)

一種等價且更為簡單的定義公式為：

(4)

式中：γ=1/2σ2。

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

高斯核函數對自身的參數σ比較敏感，本次實驗通過交叉驗證法確定參數σ。使用距離協方差作為參數，因為協方差能很好地反映各維數據的離散狀況，很符合核函數參數的性質。協方差公式如下：

(5)

其中:n代表數據的總數；xi為第i個具體的數據。

從原始數據中隨機選擇400個數據，平均分為4組，其中三組記為A、B、C，當作訓練集，最后一組記為D，作為最終的驗證集，用驗證集來選出最合適的一個當作參數。

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

表1 訓練集數據

測試集數據如表2所示。

表2 測試集結果

由測試集數據可了解到，當S為0.002 17的時候，效果最好，這表明，可以確定σ取值為0.002 17。

3 k-means算法改進

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

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

k-means算法的邏輯如下：確定聚類的個數k，隨機確定初始質心的坐標，選擇合適的距離公式計算每個數據與每個質心的距離，并將其聚類到距離最近的簇中。在所有數據完成聚類后，更新每個簇的質心坐標并重新計算每個點與質心的距離，將數據點重新聚類到距離最近的簇中。重復以上步驟直到質心不再變化，聚類完成。

k-means算法的優(yōu)點是簡單、快速，當數據很密集時，效果較好。缺點是要事先確定準備生成的簇的數目k，對于初始質心坐標和噪聲很敏感，不同的初始值結果可能會不一樣，當k值預估過大時，可能出現空簇。

3.2 使用改進的k-means算法聚類

由于初始質心的隨機性對k-means的結果影響很大，數據很可能收斂到局部最小值，并且會產生空簇，所以此次實驗對傳統(tǒng)k-means做出了改進。

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

具體步驟為：

(1) 初始化k/2個質心，質心坐標隨機確定：

(6)

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

k′=k′+a

(7)

Δk=k′/2

(8)

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

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

k′=k′-Δk

(9)

(5) 當簇的數量達到k即k′為0時，聚類結束。

經過這一改進后，可以有效降低SSE的值，使數據最大化地收斂到全局最小值，還可以避免出現空簇，改善了有效簇未達到期望值的缺陷。

4 結果分析

4.1 實驗一

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

由于計算距離公式不同，所以使用平均誤差平方和(AvgSSE)與最大誤差平方和(MaxSSE)的比值(pSSE)作為評估標準之一，計算公式如下：

(10)

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

表3 實驗一結果對比

由最后結果對比可知，在迭代次數上，改進后的算法較傳統(tǒng)算法所用次數明顯減少。原因有兩點：第一是初始的質心只為k值的一半，基礎的迭代次數必然減少；第二是因為算法后期的局部聚類相當于二分聚類，每次增長的幅度相對較小。

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

此外，較大數據量的兩組分別聚類了兩次進行對比?？梢钥吹礁倪M后的算法并沒有出現空簇，而傳統(tǒng)算法雖數據量沒有變，但是由于初始的質心發(fā)生變化，導致出現的空簇數量不定，或多或少，隨著文本的增多，出現空簇的可能性也增大。改進后的算法徹底修正了傳統(tǒng)算法的這個缺陷，保證了聚類結果能達到數量上的基本要求。

4.2 實驗二

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

precision=Nt/NT

(11)

召回率是指Nt占相對應類型文本Nm的比值：

recall=Nt/Nm

(12)

F值計算公式為：

(13)

實驗結果如表4所示。

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

5 結 語

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