張國鋒 吳國文

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

0 引 言

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

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

1 文本預(yù)處理

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

1.1 分詞處理

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

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

1.2 特征選取

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

(1)

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

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

1.3 文本向量化

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

(2)

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

2 相似度定義

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

(3)

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

(4)

式中：γ=1/2σ2。

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

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

(5)

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

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

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

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

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

表2 測試集結(jié)果

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

3 k-means算法改進

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

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

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

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

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

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

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

具體步驟為：

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

(6)

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

k′=k′+a

(7)

Δk=k′/2

(8)

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

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

k′=k′-Δk

(9)

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

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

4 結(jié)果分析

4.1 實驗一

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

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

(10)

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

表3 實驗一結(jié)果對比

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

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

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

4.2 實驗二

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

precision=Nt/NT

(11)

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

recall=Nt/Nm

(12)

F值計算公式為：

(13)

實驗結(jié)果如表4所示。

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

5 結(jié) 語

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