基于和聲搜索機制的特征選擇與文本聚類分析

王永剛，李 靖，王文慧，曹傳劍，王曉燕

(1.青島黃海學院 通識教育學院，山東 青島 266427；2.青島黃海學院 大數據學院， 山東 青島 266427；3.青島黃海學院 教學工作部，山東 青島 266427； 4.青島黃海學院 智能制造學院，山東 青島 266427)

0 引 言

文本聚類的目標是將巨量文本信息劃分為若干文本群組的過程[1,2]，常應用于文本數據挖掘領域[3]。矢量空間模型VSM是最常用的文本特征表征模型，該模型以矢量權重的形式對文本特征進行表示，文本信息中的每個詞條均被描述為一維權重空間。因此，特征的高維度特性和稀疏特性，以及充斥在文本中的冗余特征成為影響文本聚類準確性的主要問題[4]。

文本特征一般由有用特征和無用特征組成。無用特征是具有噪聲、不相關性和冗余的特征，需要從文本中剔除。特征選擇的目標是搜索文檔中的有用特征最優子集，以此獲取更精確的文本聚類[5]。特征選擇主要解決如何準確獲取有用特征[6,7]和如何改善文本聚類性能兩個問題。文本聚類的目標是將文本集合劃分為若干群組，是非監督學習領域中的一種有效手段。文本聚類算法的最終目標是搜索最優解將集合進行劃分，且算法基于目標函數和適應度函數標準執行進行搜索。

針對以上分析，設計了一種基于和聲搜索機制的特征選擇算法。算法的主要目標是借助于和聲搜索的尋優機制降低文本初始特征維度，剔除無用特征，選擇有用特征最優子集，以此提升文本聚類準確度。

1 相關工作

文獻[8]為了改進傳統K均值法隨機性選擇初始質心的不足，引入了樣本局部密度指標，改善了聚類性能。文獻[9]利用語義K均值解決了特征詞條稀疏性問題，在質心選取上利用最大詞頻克服了初始質心敏感性。文獻[10]基于后綴樹思想設計了半監督自適應多密度聚類算法，利用K最近鄰傳播擴展簇標簽，適應于多密度不平衡文本數據。文獻[11]提出基于粒子群優化的特征選擇算法PSOTC，通過改進慣性權重提升粒子尋優性能，數據集測試結果表明新的特征選擇下的文本聚類在準確率和效率均有提升。文獻[12]設計了基于遺傳算法的特征選擇算法GAFSTC，以此改善聚類性能。算法首先通過遺傳算法生成新的特征子集，再將其輸入K均值算法，通過這種兩階段的優化方式收集最優信息性特征，實驗中的聚類準確率得到了有效提升。傳統卡方統計法在特征選擇上忽略了詞頻和詞條分布，對此，文獻[13]提出一種基于特征詞頻率分布函數的特征選擇算法。這種過濾特征選擇算法效率雖然有所提高，但特征子集求解精度低的問題依然沒有得到有效解決。

2 文本預處理

(1)詞語切分。詞語切分的目標是將文本流進行分割，生成符號、詞語、句子或其它有意義的元素(移除空格信息)。

(2)移除終止詞。文本文檔中的一些常規的、高頻率詞語，如but、and、be、in以及其它一些常用詞匯，通常會具有較小的權重及較高的出現頻率。該類詞語會影響文本聚類效果，因此需要在預處理過程中將其移除。該類終止詞總計有571個。

(3)提取詞干。主要目標是移除詞語的前后綴，使其擁有相同詞根。如：insect、section、subsect這3個詞，擁有相同詞根sect，在剔除前后綴后，即可得到一個詞根，可理解為詞條特征。常規詞干提取方式為Porter提詞器。

(4)詞條權重TF-IDF。文本數據挖掘領域中，詞條權重策略可用于為文檔中的詞條分配合適的權重值以改進詞條類型劃分(即辨別力)。詞條權重TF-IDF是一種常用的計算文檔詞條權重的計算與度量方法，根據詞條頻率TF和逆文檔頻率IDF計算，令di為一個文檔，表示為一個詞條權重矢量di=(wi,1,wi,2,…,wi,j,…,wi,t)。 以下公式用于計算詞條權重值

(1)

式中：n為文檔總量，tf(i,j) 為文檔i中詞條j的出現頻率，wi,j為i中詞條j的權重，idf(i,j) 為逆文檔頻率，df(j) 為含有特征j的文檔數。

3 基于和聲搜索機制的特征選擇

文本特征選擇的目標是尋找最優的文本特征子集，以改進文本聚類結果。整個過程如下：首先，按第2節中的方法，對文本進行預處理，即先將文本文檔集合形式化為文本數據集，然后經過文本中的詞語切分、終止詞移除、提取詞干、計算詞條權重值，并通過矢量空間模型基于詞條權重值將原始文本表示為標準文檔模式。該過程如圖1所示。

圖1 預處理

其次，利用和聲搜索機制過濾無用文本特征，生成最優特征子集，即特征選擇優化。圖2是該階段的示例圖，和聲搜索機制用于搜索信息性文本特征子集，在每個文本文檔上均運行和聲搜索過程。最終和聲搜索將結合所有搜索文本生成信息化特征集合。

圖2 特征選擇

最后，利用K均值聚類方法進行聚類劃分，如圖3所示。

圖3 聚類

3.1 特征選擇模型

特征選擇即生成最優特征子集的優化問題。令初始特征集合fi={fi1,fi2,…,fit}， 其中，t為唯一特征量，i為文檔序號。令sfi表示新的特征子集，sfi={si1,si2,…,sij,…,sim}， 其中，m表示數據集中所有特征的新數量，如果sij=1，表明文檔i選擇特征j為重要特征；如果sij=0，則為非重要特征。

3.2 解的表達

利用和聲搜索機制進行文本特征選擇，首先需要隨機生成初始解，然后以和聲搜索迭代改進直到得到全局最優解。文檔中每個唯一詞條可理解為搜索空間中一個維度。表1為一種特征選擇解。

表1所示特征選擇解的具體含義是：X表示特征選擇的一個解。若位置j=1，則特征j包含在特征子集中；若位置j=0，則特征j不在最優特征子集內；若位置j=-1，則特征j不是初始文檔中的特征詞條。

表1 特征選擇的解表示

3.3 適應度函數

適應度函數用于評估和聲搜索解的質量。每次迭代中需要計算和聲搜索解的適應度值，擁有最高適應度值的解作為最終的特征選擇最優解。利用平均絕對差MAD作為算法的適應度函數。MAD可以通過計算特征權重的均值差為特征分配權重值，然后計算xi,j的均值與中值之差，具體為

(2)

(3)

式中：xi,j為文檔i中特征j的權值，根據式(1)計算，ai為文檔i的所選特征量，t為特征總量，x′i為矢量i的均值。

3.4 和聲搜索過程

和聲搜索算法可以隨機生成若干和聲記憶庫解，并不斷改進和聲記憶庫以獲取最優解，即最優的信息化特征子集。每一位音樂家，即可視為一個文本詞條，可作為搜索空間中的一個維度。和聲搜索解可以通過式(2)的適應度函數進行評估，以便得到最優和聲，即全局最優解。利用和聲搜索機制進行特征選擇的具體過程如下所示：

步驟1 對問題進行初始化，并初始化和聲搜索相關參數。文本特征選擇問題可定義為一個最優化問題，并通過最大化適應度函數值f(x)得到最優解，其中，xi表示表1所示特征選擇解中第i個位置上的值。基于和聲搜索的特征選擇的相關參數設置如下：生成的和聲記憶庫解的總數量HMS=50，HMCR=0.9，表示是否從記憶庫或隨機方式決定決策變量的選擇概率，PARmin=0.45，表示音高調整率的最小值，PARmax=0.9，表示音高調整率的最大值，bwmin=0.1，表示最小帶寬，bwmax=1，表示最大帶寬，NI表示最大迭代次數。

步驟2 初始化和聲記憶庫。算法包括和聲記憶庫HM矩陣方式的解的存儲，以隨機生成和聲記憶庫解HMS填充，表示為

(4)

(5)

和聲記憶庫由式(4)所示的矩陣創建，其中，LBi表示下限值，UBi表示上限值。

步驟3 創建新解。根據以下3個規則生成新解：記憶考慮、縱向傾角調整和隨機選擇。具體過程如算法1所示

X′=(x′1,x′2,…,x′t)

(6)

算法1：創建新解

(1)input: Harmony memoryHMsolutions

(2)output: a new solution as vector represented in Equ.(6)

(3)for eachj∈[1,t] do

(4) ifrand(0,1)≤HMCRthen

(5)x′j=HM[i][j] wherei～U(1,2,…,HMS)

(6) ifrand(0,1)≤PARthen

(7)x′j=x′j±rand×bw,wherer～U(0,1) andbwis distance bandwidth

(8) elsex′i=LBj+rand×(UBj-LBj)

(9) end if

(10) end if

(11)end for

和聲搜索解根據PAR(I)和bw(I)兩個參數動態的決定收斂狀態，如果[0,1]間生成的隨機生成數小于或等于PAR的概率，則新的決策變量x的決策方式為

(7)

(8)

式中：PAR(I)為一個新解的縱向傾角調整率，I表示當前迭代數，Imax為最大迭代數，bwmin為最小調整率，bwmax表示最大調整率。

步驟4 更新記憶庫。如果生成的新解擁有更高的適應度，將取代較差的和聲解。

步驟5 檢查終止條件。當和聲搜索達到最大迭代次數時將終止，和聲搜索中的HMCR和PAR兩個參數有助于搜索全局解和局部解。

4 文本聚類

利用和聲搜索機制得到特征最優子集后，進一步設計基于K-mean算法的文本聚類算法，更新聚類質心并做相似性度量。

4.1 文本聚類模型

給定一個文本文檔集合D，D=(d1,d2,…,dj,…,dn)， 其中，n為集合D的文檔總量。聚類目標是以文檔i與質心j間的余弦相似度達到最大的同時，將文本劃分為若干子集。將余弦相似度定義目標函數，評估算法的可行性和效率。

4.2 計算聚類質心

利用K均值進行文本聚類過程中，每一次迭代過程中需要更新聚類質心，以實現全局搜索。令ck為聚類中心，ck=(ck1,ck2,…,ckj,…,ckK)， 其中，ckj表示聚類j的質心。聚類質心更新如下

(9)

式中：akj表示聚類j的文檔總量，di表示聚類質心cj的第i個文檔，ri表示聚類i中的文檔總量。

4.3 相似性度量

余弦相似度是文本文檔聚類問題中常用的相似性度量方法，可以用于計算代表文檔和聚類質心這兩個矢量間的相似性。文檔d1與質心d2兩者間的余弦相似度為

(10)

4.4 融入特征選擇的K-mean文本聚類算法

K均值聚類算法的目標是將集合D=(d1,d2,…,dn) 劃分為K個聚類，同時需要滿足將每個文檔分配至最為相似的質心，而文檔與質心間的相似性則由余弦相似度式(10)進行衡量。具體地，算法利用規模為n×K的X作為初始文檔聚類矩陣，n為文檔總數，K為聚類量。文檔以權重矢量形式表示為di=(wi1,wi2,…,wij,…,wit)，t為文本特征總數，算法搜索空間為n×K。

融入特征選擇的K-mean文本聚類算法過程如下：

步驟1 將每個文檔表達為詞條權重矢量；

步驟2 基于特征選擇解X，隨機初始化生成聚類質心；

步驟3 計算每個文檔與所有聚類質心的相似度，將文檔分配至相似度最高的聚類質心；

步驟4 根據式(9)更新聚類質心；

步驟5 重復執行多目標K-mean文本聚類過程，直到達到終止條件或最大迭代次數。

具體過程的偽代碼如下：

算法2：K-mean文本聚類

輸入：文本文檔集合D和聚類數K

輸出：集合D與聚類間的分配關系

(1)迭代終止條件

(2)隨機選取K個文檔作為初始的聚類質心， 表示為C=(c1,c2,…,cK)

(3)將矩陣X的所有元素初始化為0

(4)for eachdinD

(5)j=argminkbased onCos(di,ck)

(6)end for

(7)更新新的聚類質心

(8)結束

5 性能評測

利用Matlab對基于和聲搜索機制的特征選擇及K-mean文本聚類算法進行仿真測試。以下分別對測試數據集的特征、性能評估標準以及實驗結果和分析討論做出描述。表2是4種標準文本數據集的特征，包括數據集名稱、包含的文檔數量、文檔中包含的詞條數目以及聚類數量。文本數據集可用于分析和比較利用和聲搜索機制后的K-mean文本聚類算法和未使用特征選擇的文本聚類算法間的性能。

表2 數據集特征

5.1 評估指標

利用一個內在評估指標：相似性度量指標，以及兩個外在評估指標：準確率AC和F度量(F-measure)進行算法性能評測。

F-measure：F-measure是一種用于文本聚類領域的常用度量指標，用于表示求解的聚類結果中與原始分類匹配的百分比。主要由聚類精確率P和聚類召回率R兩個要素決定，兩個因素的計算方法分別為

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

(11)

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

(12)

式中：ni,j為聚類j中分類i的成員數量，nj為聚類j的成員數量，ni為分類i的成員數量。對于聚類j和分類i的F-measure 為

(13)

因此，文本中的所有聚類的F-measure可計算為

(14)

準確率AC。準確率AC用于計算文檔分配至相應聚類正確比例，計算方法為

(15)

式中：n對應每個聚類的文檔數量，K為聚類總數。

5.2 結果對比討論

對兩種類型的K-mean文本聚類算法進行仿真測試，一種是沒有利用特征選擇的K-mean文本聚類算法，命名為KMTC，另一種是利用了和聲搜索機制特征選擇策略的K-mean文本聚類算法，即本文設計的算法，命名為FSHSTC。對于數據集DS1和DS2而言，FSHSTC算法在所有度量指標上均優于未使用特征選擇策略的文本聚類算法KMTC，在DS4數據集中則FSHSTC算法在F-measure指標上有所改進。為了進行公平的比較，實驗結果均是30次仿真實驗得到的均值結果。和聲搜索機制是一種全局搜索算法，每一次運行均需要進行500次迭代。實驗中500次迭代足以使得和聲搜索的全局搜索過程發生收斂。K-mean是一種局部搜索算法，因此，100次迭代也足以使該算法在文本聚類中進行局部搜索的收斂。表3對比了聚類算法的聚類質量表現。所提出的基于和聲搜索機制的特征選擇在4種基準的文本數據集測試下均有性能指標上有所改善。信息化特征最優子集的選擇是文本聚類的關鍵步驟，它需要處理大量文本特征并尋找近似的最優聚類結果。所提出的FSHSTC算法在使用了特征選擇后在文本聚類上明顯表現更好，降低了特征數量，具體地，在DS1數據集中將特征數量從1725降低至1225，在DS2數據集中將特征數量從5773降低至351。總體來看，FSHSTC算法在DS1、DS2和DS43個數據集上均克服了K-mean算法在文本聚類上固有的不足。

表3 聚類質量對比

圖4觀察采用不同的特征選擇算法后，最優特征子集比較原始文本特征集合的下降百分比。除KMTC算法以外，再引入GAFSTC[13]做進一步的性能比較。從4種文本數據集的測試結果來看，本文設計的FSHSTC算法在不同數據集中的特征子集選擇規模上，降維比例是最高的，說明該算法可以盡可能地減少無用非信息化特征的在最優特征子集中的出現比例，降低特征維度，建立有用特征為新的子集。以此最優特征子集作為基礎的文本聚類，會生成更好的聚類結果。

圖5觀察在4個測試數據集中算法進行特征選擇時的適應度變化，驗證算法收斂性。收斂適應度即為算法得到的最優特征子集的最優適應度。從實驗結果觀察，本文設計的基于和聲搜索機制的特征選擇FSHSTC算法具備最好的收斂性能，處于收斂處的適應度值是所有算法中最高的，適應度比GAFSTC算法和KMTC算法分別高于8.65%和13.17%，驗證本文設計的和聲搜索優化特征選擇的思路是有效可行的。

圖4 特征下降率

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

圖6觀察3種算法在所有4個測試數據集中求解特征選擇解的計算時間。計算時間少，表明算法求解最優解的迭代數越少，收斂速度更快。根據圖6的結果，本文的FSHSTC算法在測試數據集中都得到了最小計算時間，計算效率最高，說明基于和聲搜索機制的特征選擇算法比較基于遺傳算法的特征選擇算法GAFSTC和未使用特征選擇優化的KMTC算法均是更優的。

圖6 特征選擇計算時間

6 結束語

本文提出一種基于和聲搜索機制的文本特征選擇算法，算法以詞頻逆文本頻率指數評估特征詞條，然后通過和聲搜索的記憶考慮、縱向傾角調整和隨機選擇3種特征選擇新解更新規則，迭代搜索最優特征子集；最后以最優特征子集為基礎，以K均值進行文本聚類。實驗結果表明，算法可以有效降低特征維度，并提升聚類準確率。進一步的研究可以嘗試對和聲搜索過程的相關參數進行尋優，得到最優的參數取值范圍，在提升和聲搜索機制的性能的前提下，使特征選擇求解性能得到進一步提高。