融入新的特征選擇機制的文本數據聚類算法

田夏利，熊 瑩

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

0 引 言

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

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

1 相關研究

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

2 算法詳細設計

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

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

圖1 文本預處理階段

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

圖2 特征選擇階段

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

圖3 文本聚類階段

2.1 文本預處理

(1)詞語切分

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

(2)終止詞移除

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

(3)詞干提取

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

(4)詞條權重計算

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

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

(1)

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

(2)

2.2 基于粒子群優化的特征選擇機制

(1)特征選擇模型

特征選擇問題可表示為尋找一個有用特征最優子集的最優化問題。給定文本特征集合F，表示為矢量Fi=(fi,1,fi,b,…,fi,j,…,fi,t)，t為所有唯一文本特征數量，i為文檔數量。令FS為新的有用特征子集，FSi=(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個位置給出第j個特征的位置。

表1 特征選擇的解表示

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

(3)適應度函數

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

(3)

(4)

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

2.3 粒子群優化算法PSO

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

算法1： PSO

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

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

(3)algorithm

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

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

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

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

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

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

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

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

(12)end while

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

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

(5)

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

xij=xij+vij

(6)

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

(7)

慣性權重處于[0,1]間，LBI為迭代I時當前的局部最優解，GBI為迭代I時當前的全局最優解，rand1和rand2為[0,1]間的隨機數，c1和c2為兩個常量學習因子。慣性權重計算方式如下

(8)

式中：wmax和wmin為最大和最小慣性權重。

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

(9)

(10)

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

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

表3 文檔被移除無用特征

表4 新的有用特征子集

2.4 文本聚類

(1)文本聚類模型

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

(2)聚類質心計算

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

(11)

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

(3)相似性度量

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

(12)

(4)K均值聚類算法

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

算法2：K均值文本聚類

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

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

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

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

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

(6)for alldinDdo

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

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

(9)end for

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

(11)end

3 性能評測

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

3.1 測試文本數據集

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

表5 測試文檔數據集

3.2 評估標準

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

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

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

(13)

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

(14)

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

(15)

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

(16)

準確率AC是用于計算文檔分配至聚類正確比例的常用度量指標，計算方法如下

(17)

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

3.3 結果對比

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

表6 各算法的性能指標情況

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

圖4 特征下降率

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

圖5 6種測試文本數據集的特征選擇收斂性

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

圖6 特征選擇計算時間

4 結束語

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