融入新的特征選擇機(jī)制的文本數(shù)據(jù)聚類算法

田夏利，熊 瑩

(武漢華夏理工學(xué)院 信息工程學(xué)院，湖北 武漢 430223)

0 引 言

文本聚類是將文本信息劃分為預(yù)定數(shù)量的文本群組的過程[1]，廣泛應(yīng)用于文本挖掘領(lǐng)域[2]。矢量空間模型是用于文本挖掘的標(biāo)準(zhǔn)模型，它將文本特征表示為權(quán)重矢量。模型中，每個詞條權(quán)重被描述為一維空間。因此，聚類效果主要受維度空間大小和無用特征量的影響[3]。文本文檔中包含有用特征和無用特征，無用特征屬于噪聲和冗余特征。非監(jiān)督特征選擇的任務(wù)是尋找文檔中新的有用特征最優(yōu)子集，該技術(shù)可增強(qiáng)聚類效果，且不依賴于文檔標(biāo)簽的先驗(yàn)知識。特征選擇需要重點(diǎn)解決：①如何改善文本聚類效果；②如何準(zhǔn)確獲取最多有用特征[4,5]。文本挖掘都得益于特征選擇，如文本聚類、基于聚類特征選擇的文本劃分、文本信息檢索等。文本聚類即將數(shù)字文本集合劃分為群組子集，是提供易于訪問的非監(jiān)督學(xué)習(xí)手段。而文本聚類的目標(biāo)是尋找最優(yōu)解將文本集合劃分。

本文設(shè)計了基于粒子群算法的特征選擇方法，可用于消除無用特征而選擇有用特征的最優(yōu)子集。在多個文本數(shù)據(jù)集的測試下，利用K均值文本聚類算法進(jìn)行算法性能評測。結(jié)果顯示，從快速聚類效果和特征維度降低效果上看，所提算法明顯優(yōu)于沒有使用任何特征選擇的K均值算法；而與另外兩種利用特征選擇的聚類方法相比，本文算法在各項(xiàng)性能指標(biāo)上也是占優(yōu)的。

1 相關(guān)研究

文獻(xiàn)[6]針對傳統(tǒng)K均值聚類在初始質(zhì)心選取上的隨機(jī)性，改進(jìn)了初始質(zhì)心的選擇方法，為樣本點(diǎn)引入了局部密度指標(biāo)，并根據(jù)局部密度分布，選擇密度峰值點(diǎn)作為初始質(zhì)心，得到了更高的文本聚類準(zhǔn)確度。文獻(xiàn)[7]針對特征詞的稀疏性，提出一種結(jié)合語義K均值文本聚類算法。算法以詞語集表示短文本，緩解了短文本特征詞的稀疏性問題；并通過挖掘文本集合的最大頻繁詞集得到聚類質(zhì)心，克服了算法對初始質(zhì)心的敏感度，得到較優(yōu)的文本聚類效果。文獻(xiàn)[8]提出一種基于增強(qiáng)蜂群優(yōu)化搜索與K均值相結(jié)合的文本聚類算法。算法首先引入公平與克隆操作提高全局搜索能力，提高樣本多樣性并增強(qiáng)蜂群搜索能力。同時，克隆操作增強(qiáng)了各代之間的信息交流，提高了文本聚類質(zhì)量。文獻(xiàn)[9]提出基于后綴樹文檔模型的半監(jiān)督自適應(yīng)多密度文本聚類算法，該算法基于后綴樹文檔模型表征文檔間的相似度，使用K最近鄰思想傳播擴(kuò)展簇標(biāo)簽，并在傳播擴(kuò)展過程中不斷更新擴(kuò)展閾值，以適應(yīng)多密度不平衡的文本數(shù)據(jù)集。文獻(xiàn)[10]為了改進(jìn)文本聚類性能，設(shè)計了基于遺傳算法的特征選擇機(jī)制。文獻(xiàn)[11]同樣提出了一種基于和聲搜索算法的特征選擇算法對文本聚類效果進(jìn)行改善。以上兩種算法在文本聚類時均采用了K均值聚類算法，以遺傳算法和和聲搜索機(jī)制得到的新的文本特征子集作為K均值聚類的輸入，更好地收集了最優(yōu)的信息性特征子集進(jìn)行文本聚類，在聚類準(zhǔn)確率和精確率上擁有更好的效果。

2 算法詳細(xì)設(shè)計

基于粒子群優(yōu)化的特征選擇可以尋找最優(yōu)的文本特征的最優(yōu)子集進(jìn)而改進(jìn)文本聚類性能，其算法過程分為3個階段：

(1)文本文檔預(yù)處理階段。該階段包括詞語切分(令牌化)、終止詞移除、詞干提取以及詞條權(quán)重計算，如圖1所示。

圖1 文本預(yù)處理階段

(2)第二階段利用粒子群優(yōu)化算法通過消除無用文本特征解決特征選擇問題。圖2是所提算法的第二階段，粒子群算法用于尋找新的有用文本特征的子集，且算法運(yùn)行在每個文檔層次上，直到達(dá)到最大迭代數(shù)。在所有數(shù)據(jù)集中的文檔上過濾后，粒子群算法將聯(lián)合所有生成的文檔子集以生成擁有有用特征的新的數(shù)據(jù)集。

圖2 特征選擇階段

(3)第三階段利用K均值文本聚類方法將文檔劃分為不同聚類。圖3是文檔聚類的最后階段。

圖3 文本聚類階段

2.1 文本預(yù)處理

(1)詞語切分

詞語切分即是將文本文檔流分割為詞語或詞條的過程，并移除空格部分。每個詞語或符號從首字母至最后一個字母進(jìn)行掃描，而每個詞語則可視為一個令牌。

(2)終止詞移除

常規(guī)詞語，如an,that,be以及一些常用詞語通常擁有較小權(quán)重，但卻是高頻率詞語，文本聚類時可作為終止詞語。該類詞語需要從文檔中移除，由于會影響文本聚類的效果。

(3)詞干提取

詞干提取即是通過移除每個詞語的前綴和后綴將其轉(zhuǎn)換到相同的詞根上。例如：intersect，dissect，section均擁有相同的構(gòu)詞部分sect，可將其定義為特征。本文將利用Porter提詞器進(jìn)行詞干提取任務(wù)，該工具是目前文本挖掘領(lǐng)域中最為常用的詞干提取方法。

(4)詞條權(quán)重計算

詞條權(quán)重根據(jù)每個文檔中的詞條頻率分配至每個詞條或特征。若詞條頻率較高，且相同特征出現(xiàn)在多個文檔中，則該特征可用于區(qū)分文檔內(nèi)容。文檔i中特征j的詞條權(quán)重計算為

wi,j=tf(i,j)×idf(i,j)=tf(i,j)×logn/df(j)

(1)

式中：wi,j為文檔i中詞條j的權(quán)重，tf(i,j) 為文檔i中詞條j的出現(xiàn)，idf(i,j) 為倒數(shù)文檔頻率，n為數(shù)據(jù)集中的文檔數(shù)量，df(j) 為包括特征j的文檔數(shù)量。以下表達(dá)式表示利用矢量空間模型VSM表示的文檔標(biāo)準(zhǔn)格式

(2)

2.2 基于粒子群優(yōu)化的特征選擇機(jī)制

(1)特征選擇模型

特征選擇問題可表示為尋找一個有用特征最優(yōu)子集的最優(yōu)化問題。給定文本特征集合F，表示為矢量Fi=(fi,1,fi,b,…,fi,j,…,fi,t)，t為所有唯一文本特征數(shù)量，i為文檔數(shù)量。令FS為新的有用特征子集，F(xiàn)Si=(si,1,si,2,…,si,j,…,si,m)，通過特征選擇算法生成，m為新的特征長度，si,j∈{0,1},j=1,2,…,m。 若si,j=1，表明文檔i中的所選特征j為有用特征；否則，若si,j=0，則表明文檔i中的所選特征j為無用特征。

(2)解的表示

基于粒子群的特征選擇問題中，每個解(粒子)代表一個文檔特征的子集，見表1。PSO的種群包括一個粒子集合(位置)，表示一個二進(jìn)制矢量，每個粒子包括一些位置，即文檔特征。每個位置代表文檔的一個特征。粒子中的第j個位置給出第j個特征的位置。

表1 特征選擇的解表示

算法開始于隨機(jī)解，然后不斷改進(jìn)種群直到得到全局最優(yōu)解，最優(yōu)解即是一個新的文檔特征的子集。給定的數(shù)據(jù)集中的每個唯一特征考慮為一個搜索空間。如表1，若位置j等于1，則特征j選擇為有用特征；若位置j等于0，特征j不選擇為有用特征；若位置j為-1，則表明特征j不包括在初始文檔中。

(3)適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評估算法產(chǎn)生的候選解。每一代需要計算所有候選解的適應(yīng)度。若解的質(zhì)量得到改善，則該解可用于替換當(dāng)前解，反之亦然。本文使用平均絕對差MAD作為基于標(biāo)準(zhǔn)權(quán)重策略TF-IDF特征選擇的適應(yīng)度函數(shù)。該策略用于評估特征解或粒子位置的目標(biāo)函數(shù)。MAD是用于特征選擇領(lǐng)域中的常用度量方式，可通過計算均值之差為每個文本特征分配一個相關(guān)分值(權(quán)重)，然后計算均值與xi,j的中值之差為

(3)

(4)

MAD(Xi)為解i的適應(yīng)度函數(shù)，xi,j為文檔i中特征j的值，由詞頻逆文本頻率指數(shù)TF-IDF計算得到，ai為文檔i中所選文本特征的數(shù)量，t為所有文本特征的數(shù)量，x′i為矢量i的均值。

2.3 粒子群優(yōu)化算法PSO

粒子群模擬了種群的社會行為，是通過對鳥群捕食行為的研究抽象出的迭代優(yōu)化算法[12]，算法首先隨機(jī)初始化一個包含若干數(shù)量的種群粒子，每個粒子代表問題的一個可行解，算法的目標(biāo)就是通過粒子在空間中的移動尋找目標(biāo)問題的全局最優(yōu)解。算法過程如算法1。

算法1： PSO

(1)input:generate the initial particles randomly//輸入初始粒子

(2)output:optimal particle and its fitness value//輸出最優(yōu)粒子和適應(yīng)度值

(3)algorithm

(4)initialize swarm and parameters of the particle swarm optimizationc1,c2andetc//種群及粒子相關(guān)參數(shù)初始化

(5)evaluate all particles using the fitness function by Eq.(3)//以適應(yīng)度函數(shù)評估每個種群粒子

(6)while termination criteria do//迭代終止條件

(7) update the velocity//更新粒子速率

(8) update each position//更新粒子位置

(9) evaluate the fitness function//評估粒子適應(yīng)度

(10) replaces the worst particle with best particle//以最優(yōu)粒子替換最差粒子

(11) updateLBandGB//更新局部最優(yōu)粒子和全局最優(yōu)粒子

(12)end while

(13)return a new subset of informative featureD1//返回有用特征最優(yōu)子集合

每個粒子所代表的候選解通過式(3)定義的適應(yīng)度函數(shù)評估。PSO中，解包含一些單個實(shí)體(特征)，算法在特征選擇問題的搜索空間中運(yùn)行，并對粒子所處的當(dāng)前位置依據(jù)適應(yīng)度函數(shù)進(jìn)行評估。每個解通過根據(jù)當(dāng)前和最優(yōu)的適應(yīng)度決定其移動的方向，直到達(dá)到代表問題最優(yōu)解的粒子位置為止。PSO算法利用一個粒子群優(yōu)化存儲PSOM對解進(jìn)行存儲，表示如下

(5)

粒子位置更新如式(6)，粒子移動速率更新如式(7)

xij=xij+vij

(6)

vij=w×vij+c1×rand1×(LBI-xij)+c2×rand2×(GBI-xij)

(7)

慣性權(quán)重處于[0,1]間，LBI為迭代I時當(dāng)前的局部最優(yōu)解，GBI為迭代I時當(dāng)前的全局最優(yōu)解，rand1和rand2為[0,1]間的隨機(jī)數(shù)，c1和c2為兩個常量學(xué)習(xí)因子。慣性權(quán)重計算方式如下

(8)

式中：wmax和wmin為最大和最小慣性權(quán)重。

由于算法需要處理二進(jìn)制優(yōu)化問題，本文通過每個維度上的離散值方式更新解的位置。式(9)表示用于決定位置i的概率的單峰函數(shù)，式(10)用于更新粒子的新位置

(9)

(10)

表2～表4給出了一種特征選擇示例。表2是文檔D中初始特征的詞條頻率，其中選擇為無用特征的地方以黑體顯示。應(yīng)用特征選擇機(jī)制后，無用特征將在表3中被移除。最后，若該特征不出現(xiàn)在任一文檔中(即特征9未出現(xiàn)在任一文檔中)，維度大小將降低，進(jìn)而得到特征移除后的表4結(jié)果。因此，一個新的有用特征子集D1將可以用于改進(jìn)文本聚類的性能。

表2 文檔初始特征的詞條頻率

表3 文檔被移除無用特征

表4 新的有用特征子集

2.4 文本聚類

(1)文本聚類模型

文本聚類可定義為：給定文本文檔集合D，D=(d1,d2,…,dj,…,dn)，n為文檔數(shù)量，d1標(biāo)記文檔序號1。聚類目標(biāo)是將文本劃分為若干子集，滿足文檔i與聚類質(zhì)心j間的余弦相似度達(dá)到最大化，余弦相似度即為聚類的目標(biāo)函數(shù)，是文本聚類中常用的評估標(biāo)準(zhǔn)，可以有效評估聚類方法的有效性。

(2)聚類質(zhì)心計算

為將文本文檔集合劃分為聚類子集，每個聚類具有一個聚類質(zhì)心，在每次迭代中通過式(11)更新。每個文檔基于與聚類質(zhì)心的相似性分配至相似的聚類中。令Ck為聚類k的質(zhì)心，表示為矢量Ck=(ck1,ck2,…,ckj,…,ckt)，ckj為聚類j的質(zhì)心，t為聚類質(zhì)心的長度。以下公式用于計算聚類質(zhì)心

(11)

式中：di為屬于聚類質(zhì)心i中的文檔i，akj為屬于聚類j中的所有文本文檔數(shù)量，ri為聚類i中文本文檔的數(shù)量。

(3)相似性度量

余弦相似度是文本聚類中用于計算兩個矢量(即文檔與聚類質(zhì)心)間的相似度的標(biāo)準(zhǔn)度量方式。若d1為文檔1，d2為聚類質(zhì)心，則余弦相似度計算為

(12)

(4)K均值聚類算法

K均值聚類算法可用于將文本文檔集合D=(d1,d2,…,dn) 劃分為K個聚類，通過式(12)分配每個文檔至最為相似的聚類質(zhì)心，即相似性最大的聚類中。算法利用X作為數(shù)據(jù)矩陣n×K，n為所有文檔的數(shù)量，K為聚類數(shù)量。每個文本文檔顯示為權(quán)重矢量di=(wi1,wi2,…,wij,…,wit)，t為文檔D中所有文本特征的數(shù)量。算法過程如算法2所示。

算法2：K均值文本聚類

(1)Input:a set of text documentDandKis the number of all clusters//輸入文本文檔集合和聚類數(shù)量

(2)Output:allocateDtoK//將文本文檔分配至聚類中

(3)termination criteria//算法迭代終止條件

(4)randomly choosingKdocuments as clusters centroidC=(c1,c2,…,cK)//隨機(jī)選擇K個文檔作為初始聚類質(zhì)心

(5)initialize matrixXas zeros//初始化分配矩陣

(6)for alldinDdo

(7)j=argmaxk∈{1 to K},based onCos(di,ck)//尋找余弦相似度最大的目標(biāo)聚類質(zhì)心

(8) assigndito the clusterj,A[i][j]=1//分配文檔至聚類并更新分配矩陣元素

(9)end for

(10)update the clusters centroid using Eq.(11)//更新聚類質(zhì)心

(11)end

3 性能評測

本節(jié)利用Matlab實(shí)現(xiàn)基于粒子群優(yōu)化的文本特征選擇算法，尋找擁有更多有用文本特征的新的最優(yōu)子集，然后利用K均值算法對文本進(jìn)行聚類，觀察在給定測試文本數(shù)據(jù)集合中融入了粒子群優(yōu)化機(jī)制的文本特征選擇后聚類結(jié)果的性能變化。

3.1 測試文本數(shù)據(jù)集

表5給出了6種標(biāo)準(zhǔn)的文本數(shù)據(jù)集合，用于測試基于粒子群優(yōu)化的特征選擇算法的性能，該測試數(shù)據(jù)集是計算智能實(shí)驗(yàn)機(jī)制LABIC提供的文本聚類標(biāo)準(zhǔn)數(shù)據(jù)集，數(shù)據(jù)集包括文檔數(shù)量、文檔特征數(shù)量和聚類數(shù)量。對比算法選擇基于遺傳算法的特征選擇機(jī)制下的文本聚類算法GAFSTC[10]和基于和聲搜索算法的特征選擇機(jī)制下的文本聚類算法HSFSTC[11]，以及未使用任何特征選擇機(jī)制的K均值文本聚類算法。

表5 測試文檔數(shù)據(jù)集

3.2 評估標(biāo)準(zhǔn)

除相似性度量標(biāo)準(zhǔn)外，另外引入4種評估標(biāo)準(zhǔn)，包括：準(zhǔn)確率Accuracy(Ac)、精確率Precision(P)、召回率Recall(R) 和F-measure(F)，這些均是評估聚類準(zhǔn)確度的標(biāo)準(zhǔn)評估方式。

F-measure可用于度量分類模型的優(yōu)劣，表示的是聚類匹配百分比，取決于兩個要素：精確率P和召回率R。兩個要素的計算方法為

P(i,j)=ni,j/nj

(13)

R(i,j)=ni,j/ni

(14)

其中，ni,j為聚類j中分類i的成員數(shù)量，nj為聚類j的成員數(shù)量，ni為分類i的成員數(shù)量

(15)

式中：P(i,j) 為聚類j中分類i的成員精確率，R(i,j) 為聚類j中分類i的成員召回率。所有聚類的F-measure計算為

(16)

準(zhǔn)確率AC是用于計算文檔分配至聚類正確比例的常用度量指標(biāo)，計算方法如下

(17)

式中：P(i,j) 為聚類j中分類i的精確率值，n為每個聚類中的文檔數(shù)量，K為聚類數(shù)量。

3.3 結(jié)果對比

利用K均值算法檢測特征選擇對文本聚類的影響，特征選擇可以通過生成的新的包括有用特征的子集改進(jìn)文本聚類效果，并以此作為K均值算法的輸入。表6是利用基于粒子群的特征選擇機(jī)制后的K均值文本聚類結(jié)果。根據(jù)結(jié)果，本文算法在所有給定的數(shù)據(jù)集中均生成了有效的文本聚類結(jié)果(由評估指標(biāo)決定)。在AC方面，本文算法在6個數(shù)據(jù)集中4個獲得了最優(yōu)的結(jié)果，即DS3-DS6。在PE方面，本文算法在所有6個數(shù)據(jù)集文檔中均得到了最優(yōu)的結(jié)果。在F-measure方面，該指標(biāo)是最為常用的文本聚類領(lǐng)域中的重要指標(biāo)，本文算法在所有6個數(shù)據(jù)集中均效果更佳。

表6 各算法的性能指標(biāo)情況

圖4是不同特征選擇機(jī)制下得到的特征下降率情況。綜合不同類型的數(shù)據(jù)集文檔看，本文算法基本可以實(shí)現(xiàn)最大的特征下降率，這表明算法在文本聚類前的特征選擇上可以更大量地降低無用特征的出現(xiàn)比例，降低文本數(shù)據(jù)的維度空間，建立有用特征為新的子集，并以此為標(biāo)準(zhǔn)進(jìn)行文本聚類，生成更好的聚類結(jié)果。

圖4 特征下降率

圖5通過計算在不同數(shù)據(jù)集文檔中算法進(jìn)行特征選擇的適應(yīng)度函數(shù)值評估算法的收斂性能。算法收斂值即為通過若干次迭代得到的最優(yōu)適應(yīng)度值。明顯地，本文基于粒子群優(yōu)化的特征選擇機(jī)制具有最好的收斂性能，特征選擇迭代完成后，其得到的特征選擇結(jié)果也具有最高的適應(yīng)度值，說明粒子群優(yōu)化的特征選擇結(jié)果是有效可行的。

圖5 6種測試文本數(shù)據(jù)集的特征選擇收斂性

圖6是不同算法進(jìn)行特征選擇的計算時間。計算時間越小，說明算法在得到最優(yōu)特征子集的求解時間越少，也進(jìn)一步表明算法的收斂速度越快。從結(jié)果可以看到，本文算法在大部分測試數(shù)據(jù)集文檔中均得到了最小的計算時間，說明基于粒子群優(yōu)化的特征選擇機(jī)制比較基于遺傳算法的特征選擇和基于和聲搜索算法的特征選擇機(jī)制均是更好的。

圖6 特征選擇計算時間

4 結(jié)束語

提出了一種基于粒子群優(yōu)化的文本特征選擇算法，算法利用詞頻逆文本頻率指數(shù)為目標(biāo)函數(shù)評估每個文檔層次上的文本特征，并從初始的文檔數(shù)據(jù)集中求解新的有用特征最優(yōu)子集。然后以該最優(yōu)有用特征子集作為K均值文本聚類算法的輸入進(jìn)行文本聚類，得到最優(yōu)的文本聚類結(jié)果。結(jié)果表明，利用了基于粒子群優(yōu)化的特征選擇機(jī)制后的文本聚類算法，在多項(xiàng)評估指標(biāo)上均比對比算法表現(xiàn)得更加優(yōu)秀，可以更好地實(shí)現(xiàn)相似度更高的文本聚類，且在特征選擇規(guī)模上也降低了初始文檔特征規(guī)模。