基于改進(jìn)K-medoids算法的科技文獻(xiàn)特征選擇方法

李俊州， 武 瑩

(1.開封大學(xué) 藝術(shù)設(shè)計(jì)學(xué)院， 河南 開封 475004; 2.開封大學(xué) 軟件職業(yè)技術(shù)學(xué)院， 河南 開封475004)

?

基于改進(jìn)K-medoids算法的科技文獻(xiàn)特征選擇方法

李俊州1*， 武 瑩2

(1.開封大學(xué) 藝術(shù)設(shè)計(jì)學(xué)院， 河南 開封 475004; 2.開封大學(xué) 軟件職業(yè)技術(shù)學(xué)院， 河南 開封475004)

根據(jù)科技文獻(xiàn)的結(jié)構(gòu)特點(diǎn)搭建了一個(gè)四層挖掘模式，并結(jié)合K-medoids算法提出了一個(gè)特征選擇方法.該選擇方法首先依據(jù)科技文獻(xiàn)的結(jié)構(gòu)將其分為4個(gè)層次，然后通過K-medoids算法聚類對(duì)前3層逐層實(shí)現(xiàn)特征詞提取，緊接著再使用Aprori算法找出第4層的最大頻繁項(xiàng)集，并作為第4層的特征詞集合.同時(shí)，由于K-medoids算法的精度受初始中心點(diǎn)影響較大，為了改善該算法在特征選擇中的效果，論文又對(duì)K-medoids算法的初始中心點(diǎn)選擇進(jìn)行優(yōu)化.實(shí)驗(yàn)結(jié)果表明，結(jié)合優(yōu)化K-medoids的四層挖掘模式在科技文獻(xiàn)分類方面有較高的準(zhǔn)確率.

文本分類； 特征選擇；K-medoids算法

隨著文獻(xiàn)檢索能力的提高，越來越多的用戶習(xí)慣于從中國(guó)知網(wǎng)和數(shù)字圖書館進(jìn)行快速檢索，獲取所需的文獻(xiàn)資料.但是在知識(shí)更新不斷加快的今天，新主題、新事物、新學(xué)科大量涌現(xiàn)，信息種類和數(shù)量激增.使得科技文獻(xiàn)的數(shù)量每年近似指數(shù)的速度增長(zhǎng)，如此海量的科技文獻(xiàn)，往往需要消耗讀者大量的時(shí)間，如何對(duì)其進(jìn)行高效組織，滿足廣大讀者的需求，已經(jīng)成為該領(lǐng)域的一個(gè)研究熱點(diǎn).

文本特征向量的高維性是文本分類的瓶頸，特征選擇是文本特征向量降維的一種方式，它是實(shí)現(xiàn)文本高效分類前提，是文本自動(dòng)分類的一個(gè)重要環(huán)節(jié)，特征選擇算法的性能將直接影響分類系統(tǒng)的最終效果.目前用于文本特征選擇的方法主要由以下幾種：互信息方法(Mutual Information)[1]，信息增益方法(Information Gain)[2]，x2統(tǒng)計(jì)量方法[3]，期望交叉熵方法(Expected Cross Entropy)[3]，文檔頻次方法(Document Frequency)[4].

科技文獻(xiàn)主要以文本的形式存在，由標(biāo)題、摘要，關(guān)鍵字，正文等組成，其中最能代表文章主題的是標(biāo)題和關(guān)鍵字，其次是摘要部分，再次是正文的引言和總結(jié)部分，最后是正文的其他部分.為了更加精準(zhǔn)的提取特征詞，本文組建四層挖掘模式，逐層對(duì)科技文獻(xiàn)進(jìn)行特征選擇.本文首先對(duì)K-medoids算法進(jìn)行改進(jìn)，然后結(jié)合改進(jìn)后的K-medoids算法和Apriori算法提出一種新的文本特征選擇方法，來對(duì)科技文獻(xiàn)進(jìn)行分類處理.

1 相關(guān)基礎(chǔ)知識(shí)

1.1 K-medoids算法

K-medoids算法是聚類分析常用的一種方法，其基本思想[5]是：隨機(jī)選擇K個(gè)初始聚類中心點(diǎn)，其余數(shù)據(jù)點(diǎn)根據(jù)其與中心點(diǎn)的距離將其分配給最近的代表的簇，反復(fù)從聚類的非代表樣本中選取數(shù)據(jù)點(diǎn)來代替原質(zhì)點(diǎn)，如果某數(shù)據(jù)點(diǎn)成為質(zhì)點(diǎn)后，絕對(duì)誤差能小于原質(zhì)點(diǎn)所造成的絕對(duì)誤差，那么該數(shù)據(jù)點(diǎn)可取代原質(zhì)點(diǎn)，絕對(duì)誤差最小的數(shù)據(jù)樣本將成為簇中心點(diǎn).算法描述：

輸入：K為初始中心點(diǎn)個(gè)數(shù)，D為包含N個(gè)對(duì)象的數(shù)據(jù)集合.

輸出：K個(gè)結(jié)果簇.

Step1：從D中選出K個(gè)初始中心點(diǎn)；

Step2：將其余對(duì)象依據(jù)距離分配到與其最近的中心點(diǎn)；

Step3：隨機(jī)選擇一個(gè)非中心點(diǎn)Oi；

Step4：計(jì)算用Oi代替原中心點(diǎn)Oj所造成的絕對(duì)誤差；

Step5：計(jì)算Oi造成的絕對(duì)誤差與原中心點(diǎn)Oj造成的絕對(duì)誤差的差值，當(dāng)新中心點(diǎn)的造成的絕對(duì)誤差小于原中心點(diǎn)時(shí)，Oi替換Oj，形成新的K個(gè)代表對(duì)象集合；

Step6：轉(zhuǎn)向step3，直至算法收斂；

Step7：結(jié)束，得到K個(gè)結(jié)果簇.

1.2 Apriori算法

Apriori算法是一種逐層迭代挖掘關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集算法，其核心思想是通過候選集生成和情節(jié)的向下封閉檢測(cè)兩個(gè)階段來尋找數(shù)據(jù)項(xiàng)之間的關(guān)聯(lián)關(guān)系[6].Apriori算法使用如下性質(zhì)來找到K維最大頻繁項(xiàng)集：

性質(zhì)1XK是K維頻繁項(xiàng)集，若所有K-1維頻繁項(xiàng)集集合XK-1中包含XK的K-1維子項(xiàng)集的個(gè)數(shù)小于K，那么XK不可能為K維最大頻繁項(xiàng)集.

K的值每增加1就需要掃描一次數(shù)據(jù)庫(kù)，為了提高頻繁項(xiàng)集的搜索效率，Apriori算法使用下述性質(zhì)用于壓縮搜索空間：

性質(zhì)2若K維數(shù)據(jù)項(xiàng)集XK中有一K-1維子集不是頻繁項(xiàng)集，那么X不是頻繁項(xiàng)集.

算法描述：

Step1：掃描數(shù)據(jù)庫(kù)，產(chǎn)生頻繁的1-項(xiàng)集；

Step2：由頻繁1-項(xiàng)集經(jīng)過兩兩結(jié)合生成頻繁的2-項(xiàng)集；

Step3：通過頻繁K-1-項(xiàng)集產(chǎn)生K-項(xiàng)集候選集；

如果在兩個(gè)頻繁的K-1-項(xiàng)集只有最后一個(gè)元素不同，其他都相同，那么這兩個(gè)K-1-項(xiàng)集項(xiàng)集可以“連接”為一個(gè)K-項(xiàng)集.如果不能連接，將其舍棄；

Step4：從候選集中剔除非頻繁項(xiàng)集；

如果候選集中某個(gè)K-項(xiàng)集的子項(xiàng)集不在頻繁的K-1-項(xiàng)集中，將其刪除；

Step5：計(jì)算候選項(xiàng)集的支持度，將其與最小支持度比較，得到K維頻繁項(xiàng)集.直至生成最大項(xiàng)集，否則轉(zhuǎn)向Step3；

Step6：結(jié)束，獲取最大頻繁項(xiàng)集.

2 改進(jìn)的K-medoids算法

K-medoids算法首先要任選K個(gè)數(shù)值點(diǎn)初始聚類的簇中心，在此基礎(chǔ)進(jìn)行迭代計(jì)算.如果初始中心不同，相應(yīng)的聚類結(jié)果就會(huì)有差異.在理論上，隨機(jī)選取初始點(diǎn)最理想情況是選取了K個(gè)簇的中心點(diǎn)，此種情況下的聚類效果為最佳，但是也有可能將一簇中的K個(gè)元素選為初始點(diǎn)，此時(shí)的聚類效果較差，為此，需對(duì)初始值的選取應(yīng)該制定一個(gè)標(biāo)準(zhǔn)，使其盡可能地接近各個(gè)簇的中心.

設(shè)在訓(xùn)練集中特征項(xiàng)ti的權(quán)重向量為：wi=(wi1，wi2，…，win)，任意兩個(gè)權(quán)重向量差值的模的最大值為：

vi=max|wis-wit|

(s，t=1，2，…，n;s≠t;i=1，2，…，m),

(1)

其中，m為特征個(gè)數(shù)，n為文本數(shù).

一般情況下，類屬性特征詞在其所屬類別文本中出現(xiàn)的頻率高而在其它類別文本中出現(xiàn)的概率較小，而非類屬性特征詞則不然，因此類屬性特征詞的vi值大于非類屬性特征詞的vi值，即vi值較大的特征項(xiàng)對(duì)文本類屬性的標(biāo)引能力更強(qiáng).

改進(jìn)的K-medoids算法對(duì)數(shù)據(jù)集合進(jìn)行聚類分析的步驟描述如下：

輸入：數(shù)據(jù)對(duì)象集A，聚類種子初始中心點(diǎn)個(gè)數(shù)K.

輸出：K個(gè)結(jié)果簇，使每個(gè)聚類中心點(diǎn)不再發(fā)生改變.

Step2：設(shè)定劃分區(qū)間的單位長(zhǎng)度p，將區(qū)間d=[min{vi}，max{vi}]劃分為K個(gè)小區(qū)間，p值的計(jì)算公式[8]為：

(2)

其中,K為聚類的簇?cái)?shù)；

Step3：判斷特征項(xiàng)ti的vi值是否滿足vi∈lr，如果滿足，則將ti劃分為相應(yīng)的特征子集Sr，lr的計(jì)算公式為：

lr=[min{vi}+(r-1)p，min{vi}+rp]

(r=1，2，…，K)；

(3)

(4)

則將特征項(xiàng)to作為第o簇的初始值;

Step5：將其余對(duì)象依據(jù)距離分配到與其最近的中心點(diǎn)；

Step6：隨機(jī)選擇一個(gè)非中心點(diǎn)Oi；

Step7：計(jì)算用Oi代替原中心點(diǎn)Oj所造成的絕對(duì)誤差，公式為[9]：

(5)

其中，p為空間中的數(shù)據(jù)點(diǎn)，Oj為簇Cj的中心點(diǎn)；

Step8：計(jì)算Oi造成的絕對(duì)誤差與原中心點(diǎn)Oj造成的絕對(duì)誤差的差值，計(jì)算公式為：

e=Ei-Ej,

(6)

當(dāng)e<0時(shí)，Oi替換Oj，形成新的K個(gè)代表對(duì)象集合；

Step9：轉(zhuǎn)向Step6，直到所有類簇的中心點(diǎn)不再發(fā)生變化；

Step10：算法結(jié)束，得到K結(jié)果簇.

此種作為選擇聚類初始值的條件具有以下優(yōu)點(diǎn)：

1)初始值的選取基本上位于或接近位于各個(gè)聚類簇的幾何中心，這更符合聚類要求；

2)由于本文研究的是文本特征選擇，因此這種以vi值的大小為標(biāo)準(zhǔn)的簇初始值選擇模式通過聚類得到的位于各個(gè)簇的“核心區(qū)域”內(nèi)的那些特征項(xiàng)更具有文本的類別標(biāo)引能力.

3 結(jié)合改進(jìn)K-medoids和Apriori算法的四層挖掘模式

本文根據(jù)科技文獻(xiàn)的結(jié)構(gòu)特點(diǎn)提出4層挖掘模式，將K-medoids聚類分析方法應(yīng)用于該模式的前3層，將Apriori方法應(yīng)用于第4層，逐層實(shí)現(xiàn)特征選擇.其基本思想：首先將挖掘過程分為如下4層，標(biāo)題與關(guān)鍵字為第1層，摘要為第2層，文獻(xiàn)引言與總結(jié)部分為第3層，正文的其他部分為第四層；然后將第1層的一級(jí)特征詞的個(gè)數(shù)來確定K值，依據(jù)特征項(xiàng)對(duì)文本類屬性的標(biāo)引能力選出初始中心點(diǎn)，將樣本集中的樣本按照歐式距離原則分配到最鄰近的簇中，反復(fù)從聚類的非代表樣本中選取數(shù)據(jù)點(diǎn)來代替原質(zhì)點(diǎn)，如果某數(shù)據(jù)點(diǎn)成為質(zhì)點(diǎn)后，絕對(duì)誤差能小于原質(zhì)點(diǎn)所造成的絕對(duì)誤差，新數(shù)據(jù)點(diǎn)可取代原質(zhì)點(diǎn)，絕對(duì)誤差最小的數(shù)據(jù)樣本將成為簇中心點(diǎn)，直到算法收斂，得到K個(gè)結(jié)果簇；在每個(gè)簇中選擇一個(gè)或多個(gè)代表詞作為二級(jí)特征詞，并根據(jù)二級(jí)特征詞的數(shù)量來確定第3層K值.步驟相同，待算法收斂時(shí)得到三級(jí)特征詞.正文部分屬于四層挖掘模式中的第4層，由于該部分?jǐn)?shù)據(jù)量大，且所含有效信息量較少，本文采用Apriori算法對(duì)其進(jìn)頻繁項(xiàng)集的挖掘.將提取出的頻繁項(xiàng)集和三級(jí)特征詞進(jìn)行比較，消除重復(fù)詞，最終得出特征詞集.

對(duì)科技文獻(xiàn)標(biāo)題、關(guān)鍵字用漢語(yǔ)分詞系統(tǒng)進(jìn)行切分，經(jīng)去停用詞處理，得出一級(jí)特征詞，獲取K值.對(duì)文獻(xiàn)的摘要部分用漢語(yǔ)分詞系統(tǒng)進(jìn)行分詞處理，經(jīng)過去停用詞處理得到文獻(xiàn)語(yǔ)料庫(kù)(一).采用本文提出的改進(jìn)的K-medoids算法對(duì)其進(jìn)行特征選擇，然后對(duì)每個(gè)簇選擇一個(gè)或多個(gè)代表詞作為二級(jí)特征詞，獲取下一次聚類的K值.同樣的方法對(duì)科技文獻(xiàn)的引言和總結(jié)部分進(jìn)行處理，形成文獻(xiàn)語(yǔ)料庫(kù)(二).選擇過程同二級(jí)特征詞選擇的方法類似.用相同的方法對(duì)正文部分?jǐn)?shù)據(jù)處理得到文獻(xiàn)語(yǔ)料庫(kù)(三)，由于科技文獻(xiàn)的正文部分?jǐn)?shù)據(jù)量較大，特征詞的密度相對(duì)較小.適合采用挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的方法進(jìn)行頻繁項(xiàng)的挖掘.最后將選擇出的頻繁項(xiàng)集和三級(jí)特征詞進(jìn)行比較，消除重復(fù)詞，最終得出特征詞集.

下面以二級(jí)特征詞的選擇為例，對(duì)其過程進(jìn)行描述：

Step1：根據(jù)一級(jí)特征詞的數(shù)量確定獲取二級(jí)特征詞聚類的K值;

Step2：使用文本分類中常用的tf-idf因子對(duì)第i個(gè)特征項(xiàng)ti進(jìn)行賦權(quán).tf-idf的計(jì)算公式為：

(7)

Step3：用本文提出的改進(jìn)的K-medoids算法獲取相應(yīng)的類簇C1，C2，…，Ck;

Step4：計(jì)算類簇C1，C2，…，Ck的簇內(nèi)向量的算術(shù)平均向量(類別中心向量)X1，X2，…，XK；

Step5：計(jì)算簇內(nèi)各特征與類別中心向量的相似度，相似度計(jì)算公式：

(8)

其中，w1i，w2i代表兩個(gè)不同的向量，n為向量?jī)?nèi)的參數(shù)個(gè)數(shù).按從大到小的順序分別取前f個(gè)特征值對(duì)應(yīng)的特征，將這f×K個(gè)特征項(xiàng)構(gòu)成特征集S的子集用于文本表示[11].

4 仿真實(shí)驗(yàn)與結(jié)果

4.1 仿真實(shí)驗(yàn)

在中國(guó)知網(wǎng)上搜集1 320篇屬于計(jì)算機(jī)行業(yè)的科技文獻(xiàn)，660篇作為實(shí)驗(yàn)數(shù)據(jù)的訓(xùn)練集，其余作為測(cè)試集.其中160篇主題為“離散化”的文獻(xiàn)，440篇主題為“綠色網(wǎng)絡(luò)”的文獻(xiàn)，720篇主題為“特征選擇”的文獻(xiàn)，對(duì)660篇訓(xùn)練集均采用以上的方法對(duì)其進(jìn)行特征選擇.前三級(jí)特征詞的數(shù)量如表1所示.

表1 前三級(jí)特征詞數(shù)量Tab.1 The Number of Before Three-Level Feature Words

本文以80篇主題為“離散化”的科技文獻(xiàn)作為Apriori算法的實(shí)驗(yàn)數(shù)據(jù).設(shè)最小支持度為40%，文獻(xiàn)語(yǔ)料庫(kù)如表2所示.

表2 文獻(xiàn)語(yǔ)料庫(kù)Tab.2 Literature Corpus

80篇主題為“離散化”的文獻(xiàn)，經(jīng)過Apriori算法處理，最終得到39450維最大頻繁項(xiàng)集52組，將52組數(shù)據(jù)全部組合得到39608個(gè)特征詞.

4.2 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)采用空間向量模型(VSM)[15]進(jìn)行文本表示，經(jīng)過KNN(這里取K=30)文本分類算法的訓(xùn)練，形成文本分類器，以此作為實(shí)驗(yàn)測(cè)試的工具.

分類評(píng)估的效果使用查全率、查準(zhǔn)率和F-score值進(jìn)行刻劃：

Recall=正確分類的文本數(shù)/應(yīng)有文本數(shù)；

Precision=正確分類的文本數(shù)/實(shí)際分類的文本數(shù)；

F-score=(2*recall*precision)/(recall+precision).

實(shí)驗(yàn)中，把本文特征提取方法與文獻(xiàn)[1]中的IACA方法作比較，其實(shí)驗(yàn)對(duì)比結(jié)果如表3所示.

表3 各特征提取方法實(shí)驗(yàn)對(duì)比結(jié)果Tab.3 Experiment Comparison Results of Feature Extraction Methods %

通過以上的比較，可以看出本文所提出方法的查全率、查準(zhǔn)率都優(yōu)于IACA方法，說明本文提出的特征選擇方法在科技文獻(xiàn)特征選擇方面有著較好的挖掘性能.

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

特征選擇是特征降維的一種方式，是文本信息處理的核心步驟，本文針對(duì)科技文獻(xiàn)分類提出一種基于改進(jìn)K-medoids方法，該方法與四層挖掘模式相結(jié)合，不僅解決了K-medoids聚類算法不能自動(dòng)確定K值的問題，而且避免了初始聚類中心點(diǎn)對(duì)算法聚類的影響，使得特征選擇的精度有了較為明顯的提升.但該方法也受到一定因素的影響，如K-medoids算法對(duì)孤立點(diǎn)數(shù)據(jù)很敏感，孤立點(diǎn)會(huì)使聚類中心偏離從而影響聚類結(jié)果；由于Apriori算法在計(jì)算項(xiàng)集支持度時(shí)，需對(duì)文獻(xiàn)語(yǔ)料庫(kù)中的數(shù)據(jù)進(jìn)行掃描，隨著文獻(xiàn)語(yǔ)料庫(kù)記錄的增加，這種掃描將使計(jì)算機(jī)系統(tǒng)的I/O開銷呈現(xiàn)出幾何級(jí)數(shù)增加.這些都是進(jìn)一步研究應(yīng)該考慮的問題.

[1] 劉海燕， 王 超， 牛軍鈺. 基于條件互信息的特征選擇改進(jìn)算法[J].計(jì)算機(jī)工程， 2012， 14(38): 36-42．

[2] 潘 果. 基于正則化互信息改進(jìn)輸入特征選擇的分類算法[J].計(jì)算機(jī)工程與應(yīng)用， 2014， 50(15): 25-29．

[3] 劉海峰， 蘇 展， 劉守生. 一種基于詞頻信息的改進(jìn)CHI文本特征選擇[J].計(jì)算機(jī)工程與應(yīng)用， 2013， 49(22): 110-114．

[4] Orakoglu F E， Ekinci C E. Optimization of constitutive parameters of foundation soilsK-means clustering analysis[J]. Sciences in Cold and Arid Regions， 2013， 5(5) :0626-0636．

[5] Dernoncourt D. Analysis of feature selection stability on high dimension and small sample data[J]. Computational Statistics and Data Analysis， 2014， 71(3):681-693．

[6] SinaT， Parham M， Fardin A. An unsupervised feature selection algorithm based on ant colony optimization[J].Engineering Applications of Artificial intelligence， 2014， 32(6): 112-123．

[7] Salwani A. An exponential Monte-Carlo algorithm for feature selection problems[J]. Computers and Industrial Engineering， 2014， 67(1): 160-167．

[8] Wu X. Online feature selection with streaming features[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2013， 35(5): 1178-1192．

[9] Han J， Kamber M. Date Mining: Comcepts and Techniques[M]. 北京:機(jī)械工程出版社，2001．

[10] 朱顥東， 吳懷廣. 基于論域劃分的無監(jiān)督文本特征選擇方法[J].科學(xué)技術(shù)與工程， 2013， 13(7): 1836-1839．

[11] 傅德勝， 周 辰. 基于密度的改進(jìn)K均值算法及實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用， 2011， 31(2): 432-434．

[12] 劉海峰， 劉守生，張學(xué)仁. 聚類模式下一種優(yōu)化的K-means文本特征選擇[J]. 計(jì)算機(jī)科學(xué)， 2011， 38(1):195-197．

Feature selection method of scientific literatures based on optimizedK-medoids algorithm

LI Junzhou1， WU Ying2

(1.College of Art and Design， Kaifeng University， Kaifeng， Henan 475004;2.College of Software Technology， Kaifeng University， Kaifeng， Henan 475004)

According to the structural characteristics of the scientific literature， the paper set up a four-level mining mode， and combinedK-medoids algorithm to propose a feature selection method of scientific literatures．The proposed feature selection method firstly divided scientific literature into four layers according to its structure， and then selected features progressively for the former three layers byK-medoids algorithm， finally found out the maximum frequent itemsets of fourth layer by Aprori algorithm to act as a collection of Features fourth layer. Meanwhile， because the clustering accuracy ofK-medoids algorithm is influenced by the initial centers， in order to improve the effect of feature selection， the paper also optimizedK-medoids algorithm which it firstly used information entropy empower the clustering objects to correct the distance function， and then employed empowerment function value to select the optimal initial clustering center. Experimental results show that the four-level mining mode combined optimizedK-medoids has higher accuracy in scientific literature classification.

text classification; feature selection;K-medoids algorithm

2015-01-17.

1000-1190(2015)04-0541-05

TP392< class="emphasis_bold">文獻(xiàn)標(biāo)識(shí)碼： A

A

*E-mail: lijunzhou0724@163.com.