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

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

0 引 言

文本聚類(lèi)的目標(biāo)是將巨量文本信息劃分為若干文本群組的過(guò)程[1,2]，常應(yīng)用于文本數(shù)據(jù)挖掘領(lǐng)域[3]。矢量空間模型VSM是最常用的文本特征表征模型，該模型以矢量權(quán)重的形式對(duì)文本特征進(jìn)行表示，文本信息中的每個(gè)詞條均被描述為一維權(quán)重空間。因此，特征的高維度特性和稀疏特性，以及充斥在文本中的冗余特征成為影響文本聚類(lèi)準(zhǔn)確性的主要問(wèn)題[4]。

文本特征一般由有用特征和無(wú)用特征組成。無(wú)用特征是具有噪聲、不相關(guān)性和冗余的特征，需要從文本中剔除。特征選擇的目標(biāo)是搜索文檔中的有用特征最優(yōu)子集，以此獲取更精確的文本聚類(lèi)[5]。特征選擇主要解決如何準(zhǔn)確獲取有用特征[6,7]和如何改善文本聚類(lèi)性能兩個(gè)問(wèn)題。文本聚類(lèi)的目標(biāo)是將文本集合劃分為若干群組，是非監(jiān)督學(xué)習(xí)領(lǐng)域中的一種有效手段。文本聚類(lèi)算法的最終目標(biāo)是搜索最優(yōu)解將集合進(jìn)行劃分，且算法基于目標(biāo)函數(shù)和適應(yīng)度函數(shù)標(biāo)準(zhǔn)執(zhí)行進(jìn)行搜索。

針對(duì)以上分析，設(shè)計(jì)了一種基于和聲搜索機(jī)制的特征選擇算法。算法的主要目標(biāo)是借助于和聲搜索的尋優(yōu)機(jī)制降低文本初始特征維度，剔除無(wú)用特征，選擇有用特征最優(yōu)子集，以此提升文本聚類(lèi)準(zhǔn)確度。

1 相關(guān)工作

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

2 文本預(yù)處理

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

(2)移除終止詞。文本文檔中的一些常規(guī)的、高頻率詞語(yǔ)，如but、and、be、in以及其它一些常用詞匯，通常會(huì)具有較小的權(quán)重及較高的出現(xiàn)頻率。該類(lèi)詞語(yǔ)會(huì)影響文本聚類(lèi)效果，因此需要在預(yù)處理過(guò)程中將其移除。該類(lèi)終止詞總計(jì)有571個(gè)。

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

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

(1)

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

3 基于和聲搜索機(jī)制的特征選擇

文本特征選擇的目標(biāo)是尋找最優(yōu)的文本特征子集，以改進(jìn)文本聚類(lèi)結(jié)果。整個(gè)過(guò)程如下：首先，按第2節(jié)中的方法，對(duì)文本進(jìn)行預(yù)處理，即先將文本文檔集合形式化為文本數(shù)據(jù)集，然后經(jīng)過(guò)文本中的詞語(yǔ)切分、終止詞移除、提取詞干、計(jì)算詞條權(quán)重值，并通過(guò)矢量空間模型基于詞條權(quán)重值將原始文本表示為標(biāo)準(zhǔn)文檔模式。該過(guò)程如圖1所示。

圖1 預(yù)處理

其次，利用和聲搜索機(jī)制過(guò)濾無(wú)用文本特征，生成最優(yōu)特征子集，即特征選擇優(yōu)化。圖2是該階段的示例圖，和聲搜索機(jī)制用于搜索信息性文本特征子集，在每個(gè)文本文檔上均運(yùn)行和聲搜索過(guò)程。最終和聲搜索將結(jié)合所有搜索文本生成信息化特征集合。

圖2 特征選擇

最后，利用K均值聚類(lèi)方法進(jìn)行聚類(lèi)劃分，如圖3所示。

圖3 聚類(lèi)

3.1 特征選擇模型

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

3.2 解的表達(dá)

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

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

表1 特征選擇的解表示

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

適應(yīng)度函數(shù)用于評(píng)估和聲搜索解的質(zhì)量。每次迭代中需要計(jì)算和聲搜索解的適應(yīng)度值，擁有最高適應(yīng)度值的解作為最終的特征選擇最優(yōu)解。利用平均絕對(duì)差MAD作為算法的適應(yīng)度函數(shù)。MAD可以通過(guò)計(jì)算特征權(quán)重的均值差為特征分配權(quán)重值，然后計(jì)算xi,j的均值與中值之差，具體為

(2)

(3)

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

3.4 和聲搜索過(guò)程

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

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

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

(4)

(5)

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

步驟3 創(chuàng)建新解。根據(jù)以下3個(gè)規(guī)則生成新解：記憶考慮、縱向傾角調(diào)整和隨機(jī)選擇。具體過(guò)程如算法1所示

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

(6)

算法1：創(chuàng)建新解

(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

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

(7)

(8)

式中：PAR(I)為一個(gè)新解的縱向傾角調(diào)整率，I表示當(dāng)前迭代數(shù)，Imax為最大迭代數(shù)，bwmin為最小調(diào)整率，bwmax表示最大調(diào)整率。

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

步驟5 檢查終止條件。當(dāng)和聲搜索達(dá)到最大迭代次數(shù)時(shí)將終止，和聲搜索中的HMCR和PAR兩個(gè)參數(shù)有助于搜索全局解和局部解。

4 文本聚類(lèi)

利用和聲搜索機(jī)制得到特征最優(yōu)子集后，進(jìn)一步設(shè)計(jì)基于K-mean算法的文本聚類(lèi)算法，更新聚類(lèi)質(zhì)心并做相似性度量。

4.1 文本聚類(lèi)模型

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

4.2 計(jì)算聚類(lèi)質(zhì)心

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

(9)

式中：akj表示聚類(lèi)j的文檔總量，di表示聚類(lèi)質(zhì)心cj的第i個(gè)文檔，ri表示聚類(lèi)i中的文檔總量。

4.3 相似性度量

余弦相似度是文本文檔聚類(lèi)問(wèn)題中常用的相似性度量方法，可以用于計(jì)算代表文檔和聚類(lèi)質(zhì)心這兩個(gè)矢量間的相似性。文檔d1與質(zhì)心d2兩者間的余弦相似度為

(10)

4.4 融入特征選擇的K-mean文本聚類(lèi)算法

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

融入特征選擇的K-mean文本聚類(lèi)算法過(guò)程如下：

步驟1 將每個(gè)文檔表達(dá)為詞條權(quán)重矢量；

步驟2 基于特征選擇解X，隨機(jī)初始化生成聚類(lèi)質(zhì)心；

步驟3 計(jì)算每個(gè)文檔與所有聚類(lèi)質(zhì)心的相似度，將文檔分配至相似度最高的聚類(lèi)質(zhì)心；

步驟4 根據(jù)式(9)更新聚類(lèi)質(zhì)心；

步驟5 重復(fù)執(zhí)行多目標(biāo)K-mean文本聚類(lèi)過(guò)程，直到達(dá)到終止條件或最大迭代次數(shù)。

具體過(guò)程的偽代碼如下：

算法2：K-mean文本聚類(lèi)

輸入：文本文檔集合D和聚類(lèi)數(shù)K

輸出：集合D與聚類(lèi)間的分配關(guān)系

(1)迭代終止條件

(2)隨機(jī)選取K個(gè)文檔作為初始的聚類(lèi)質(zhì)心， 表示為C=(c1,c2,…,cK)

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

(4)for eachdinD

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

(6)end for

(7)更新新的聚類(lèi)質(zhì)心

(8)結(jié)束

5 性能評(píng)測(cè)

利用Matlab對(duì)基于和聲搜索機(jī)制的特征選擇及K-mean文本聚類(lèi)算法進(jìn)行仿真測(cè)試。以下分別對(duì)測(cè)試數(shù)據(jù)集的特征、性能評(píng)估標(biāo)準(zhǔn)以及實(shí)驗(yàn)結(jié)果和分析討論做出描述。表2是4種標(biāo)準(zhǔn)文本數(shù)據(jù)集的特征，包括數(shù)據(jù)集名稱(chēng)、包含的文檔數(shù)量、文檔中包含的詞條數(shù)目以及聚類(lèi)數(shù)量。文本數(shù)據(jù)集可用于分析和比較利用和聲搜索機(jī)制后的K-mean文本聚類(lèi)算法和未使用特征選擇的文本聚類(lèi)算法間的性能。

表2 數(shù)據(jù)集特征

5.1 評(píng)估指標(biāo)

利用一個(gè)內(nèi)在評(píng)估指標(biāo)：相似性度量指標(biāo)，以及兩個(gè)外在評(píng)估指標(biāo)：準(zhǔn)確率AC和F度量(F-measure)進(jìn)行算法性能評(píng)測(cè)。

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

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

(11)

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

(12)

式中：ni,j為聚類(lèi)j中分類(lèi)i的成員數(shù)量，nj為聚類(lèi)j的成員數(shù)量，ni為分類(lèi)i的成員數(shù)量。對(duì)于聚類(lèi)j和分類(lèi)i的F-measure 為

(13)

因此，文本中的所有聚類(lèi)的F-measure可計(jì)算為

(14)

準(zhǔn)確率AC。準(zhǔn)確率AC用于計(jì)算文檔分配至相應(yīng)聚類(lèi)正確比例，計(jì)算方法為

(15)

式中：n對(duì)應(yīng)每個(gè)聚類(lèi)的文檔數(shù)量，K為聚類(lèi)總數(shù)。

5.2 結(jié)果對(duì)比討論

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

表3 聚類(lèi)質(zhì)量對(duì)比

圖4觀察采用不同的特征選擇算法后，最優(yōu)特征子集比較原始文本特征集合的下降百分比。除KMTC算法以外，再引入GAFSTC[13]做進(jìn)一步的性能比較。從4種文本數(shù)據(jù)集的測(cè)試結(jié)果來(lái)看，本文設(shè)計(jì)的FSHSTC算法在不同數(shù)據(jù)集中的特征子集選擇規(guī)模上，降維比例是最高的，說(shuō)明該算法可以盡可能地減少無(wú)用非信息化特征的在最優(yōu)特征子集中的出現(xiàn)比例，降低特征維度，建立有用特征為新的子集。以此最優(yōu)特征子集作為基礎(chǔ)的文本聚類(lèi)，會(huì)生成更好的聚類(lèi)結(jié)果。

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

圖4 特征下降率

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

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

圖6 特征選擇計(jì)算時(shí)間

6 結(jié)束語(yǔ)

本文提出一種基于和聲搜索機(jī)制的文本特征選擇算法，算法以詞頻逆文本頻率指數(shù)評(píng)估特征詞條，然后通過(guò)和聲搜索的記憶考慮、縱向傾角調(diào)整和隨機(jī)選擇3種特征選擇新解更新規(guī)則，迭代搜索最優(yōu)特征子集；最后以最優(yōu)特征子集為基礎(chǔ)，以K均值進(jìn)行文本聚類(lèi)。實(shí)驗(yàn)結(jié)果表明，算法可以有效降低特征維度，并提升聚類(lèi)準(zhǔn)確率。進(jìn)一步的研究可以嘗試對(duì)和聲搜索過(guò)程的相關(guān)參數(shù)進(jìn)行尋優(yōu)，得到最優(yōu)的參數(shù)取值范圍，在提升和聲搜索機(jī)制的性能的前提下，使特征選擇求解性能得到進(jìn)一步提高。