基于改進K-medoids算法的科技文獻特征選擇方法

李俊州， 武 瑩

(1.開封大學 藝術設計學院， 河南 開封 475004; 2.開封大學 軟件職業技術學院， 河南 開封475004)

?

基于改進K-medoids算法的科技文獻特征選擇方法

李俊州1*， 武 瑩2

(1.開封大學 藝術設計學院， 河南 開封 475004; 2.開封大學 軟件職業技術學院， 河南 開封475004)

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

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

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

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

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

1 相關基礎知識

1.1 K-medoids算法

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

輸入：K為初始中心點個數，D為包含N個對象的數據集合.

輸出：K個結果簇.

Step1：從D中選出K個初始中心點；

Step2：將其余對象依據距離分配到與其最近的中心點；

Step3：隨機選擇一個非中心點Oi；

Step4：計算用Oi代替原中心點Oj所造成的絕對誤差；

Step5：計算Oi造成的絕對誤差與原中心點Oj造成的絕對誤差的差值，當新中心點的造成的絕對誤差小于原中心點時，Oi替換Oj，形成新的K個代表對象集合；

Step6：轉向step3，直至算法收斂；

Step7：結束，得到K個結果簇.

1.2 Apriori算法

Apriori算法是一種逐層迭代挖掘關聯規則的頻繁項集算法，其核心思想是通過候選集生成和情節的向下封閉檢測兩個階段來尋找數據項之間的關聯關系[6].Apriori算法使用如下性質來找到K維最大頻繁項集：

性質1XK是K維頻繁項集，若所有K-1維頻繁項集集合XK-1中包含XK的K-1維子項集的個數小于K，那么XK不可能為K維最大頻繁項集.

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

性質2若K維數據項集XK中有一K-1維子集不是頻繁項集，那么X不是頻繁項集.

算法描述：

Step1：掃描數據庫，產生頻繁的1-項集；

Step2：由頻繁1-項集經過兩兩結合生成頻繁的2-項集；

Step3：通過頻繁K-1-項集產生K-項集候選集；

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

Step4：從候選集中剔除非頻繁項集；

如果候選集中某個K-項集的子項集不在頻繁的K-1-項集中，將其刪除；

Step5：計算候選項集的支持度，將其與最小支持度比較，得到K維頻繁項集.直至生成最大項集，否則轉向Step3；

Step6：結束，獲取最大頻繁項集.

2 改進的K-medoids算法

K-medoids算法首先要任選K個數值點初始聚類的簇中心，在此基礎進行迭代計算.如果初始中心不同，相應的聚類結果就會有差異.在理論上，隨機選取初始點最理想情況是選取了K個簇的中心點，此種情況下的聚類效果為最佳，但是也有可能將一簇中的K個元素選為初始點，此時的聚類效果較差，為此，需對初始值的選取應該制定一個標準，使其盡可能地接近各個簇的中心.

設在訓練集中特征項ti的權重向量為：wi=(wi1，wi2，…，win)，任意兩個權重向量差值的模的最大值為：

vi=max|wis-wit|

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

(1)

其中，m為特征個數，n為文本數.

一般情況下，類屬性特征詞在其所屬類別文本中出現的頻率高而在其它類別文本中出現的概率較小，而非類屬性特征詞則不然，因此類屬性特征詞的vi值大于非類屬性特征詞的vi值，即vi值較大的特征項對文本類屬性的標引能力更強.

改進的K-medoids算法對數據集合進行聚類分析的步驟描述如下：

輸入：數據對象集A，聚類種子初始中心點個數K.

輸出：K個結果簇，使每個聚類中心點不再發生改變.

Step2：設定劃分區間的單位長度p，將區間d=[min{vi}，max{vi}]劃分為K個小區間，p值的計算公式[8]為：

(2)

其中,K為聚類的簇數；

Step3：判斷特征項ti的vi值是否滿足vi∈lr，如果滿足，則將ti劃分為相應的特征子集Sr，lr的計算公式為：

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

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

(3)

(4)

則將特征項to作為第o簇的初始值;

Step5：將其余對象依據距離分配到與其最近的中心點；

Step6：隨機選擇一個非中心點Oi；

Step7：計算用Oi代替原中心點Oj所造成的絕對誤差，公式為[9]：

(5)

其中，p為空間中的數據點，Oj為簇Cj的中心點；

Step8：計算Oi造成的絕對誤差與原中心點Oj造成的絕對誤差的差值，計算公式為：

e=Ei-Ej,

(6)

當e<0時，Oi替換Oj，形成新的K個代表對象集合；

Step9：轉向Step6，直到所有類簇的中心點不再發生變化；

Step10：算法結束，得到K結果簇.

此種作為選擇聚類初始值的條件具有以下優點：

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

2)由于本文研究的是文本特征選擇，因此這種以vi值的大小為標準的簇初始值選擇模式通過聚類得到的位于各個簇的“核心區域”內的那些特征項更具有文本的類別標引能力.

3 結合改進K-medoids和Apriori算法的四層挖掘模式

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

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

下面以二級特征詞的選擇為例，對其過程進行描述：

Step1：根據一級特征詞的數量確定獲取二級特征詞聚類的K值;

Step2：使用文本分類中常用的tf-idf因子對第i個特征項ti進行賦權.tf-idf的計算公式為：

(7)

Step3：用本文提出的改進的K-medoids算法獲取相應的類簇C1，C2，…，Ck;

Step4：計算類簇C1，C2，…，Ck的簇內向量的算術平均向量(類別中心向量)X1，X2，…，XK；

Step5：計算簇內各特征與類別中心向量的相似度，相似度計算公式：

(8)

其中，w1i，w2i代表兩個不同的向量，n為向量內的參數個數.按從大到小的順序分別取前f個特征值對應的特征，將這f×K個特征項構成特征集S的子集用于文本表示[11].

4 仿真實驗與結果

4.1 仿真實驗

在中國知網上搜集1 320篇屬于計算機行業的科技文獻，660篇作為實驗數據的訓練集，其余作為測試集.其中160篇主題為“離散化”的文獻，440篇主題為“綠色網絡”的文獻，720篇主題為“特征選擇”的文獻，對660篇訓練集均采用以上的方法對其進行特征選擇.前三級特征詞的數量如表1所示.

表1 前三級特征詞數量Tab.1 The Number of Before Three-Level Feature Words

本文以80篇主題為“離散化”的科技文獻作為Apriori算法的實驗數據.設最小支持度為40%，文獻語料庫如表2所示.

表2 文獻語料庫Tab.2 Literature Corpus

80篇主題為“離散化”的文獻，經過Apriori算法處理，最終得到39450維最大頻繁項集52組，將52組數據全部組合得到39608個特征詞.

4.2 實驗結果

本實驗采用空間向量模型(VSM)[15]進行文本表示，經過KNN(這里取K=30)文本分類算法的訓練，形成文本分類器，以此作為實驗測試的工具.

分類評估的效果使用查全率、查準率和F-score值進行刻劃：

Recall=正確分類的文本數/應有文本數；

Precision=正確分類的文本數/實際分類的文本數；

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

實驗中，把本文特征提取方法與文獻[1]中的IACA方法作比較，其實驗對比結果如表3所示.

表3 各特征提取方法實驗對比結果Tab.3 Experiment Comparison Results of Feature Extraction Methods %

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

5 結束語

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

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

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

[3] 劉海峰， 蘇 展， 劉守生. 一種基于詞頻信息的改進CHI文本特征選擇[J].計算機工程與應用， 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]. 北京:機械工程出版社，2001．

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

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

[12] 劉海峰， 劉守生，張學仁. 聚類模式下一種優化的K-means文本特征選擇[J]. 計算機科學， 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">文獻標識碼： A

A

*E-mail: lijunzhou0724@163.com.