基于K-Means和Apriori算法的多層特征提取方法

錢慎一， 朱艷玲， 朱顥東

(鄭州輕工業(yè)學院 計算機與通信工程學院， 鄭州 450002)

?

基于K-Means和Apriori算法的多層特征提取方法

錢慎一， 朱艷玲， 朱顥東*

(鄭州輕工業(yè)學院 計算機與通信工程學院， 鄭州 450002)

根據(jù)科技文獻的結構特點，論文提出了一種四層挖掘模式，并結合K-means算法和Apriori算法，構建一個新的特征詞提取方法——MultiLM-FE方法.該方法首先依據(jù)科技文獻的結構將其分為4個層次，然后通過K-means聚類對前3層逐層實現(xiàn)特征詞提取，最后再使用Aprori算法找出第4層的最大頻繁項集，并作為第4層的特征詞集合.該方法能夠解決K-means算法不能自動確定最佳聚類初始點的問題，減少了聚類過程中信息損耗，這使得該方法能夠在文獻語料庫中更加準確地找到特征詞，較之以前的方法有很大提升，尤其是在科技文獻方面更為適用.實驗結果表明，該方法是可行有效的.

科技文獻； 特征提取；K-means算法； Apriori算法

隨著文獻檢索能力的提高，越來越多的用戶習慣于從中國知網(wǎng)和數(shù)字圖書館進行快速檢索，獲取所需文獻資料.但是在知識更新不斷加快的今天，新主題、新事物、新學科大量涌現(xiàn)，信息種類和數(shù)量激增，這使得科技文獻的數(shù)量每年近似指數(shù)的速度增長.如此海量的科技文獻，往往需要消耗讀者大量的時間.如何對其進行高效組織，滿足廣大讀者的需求，已經(jīng)成為該領域的一個研究熱點.目前，諸多檢索機構已將文獻資料進行分類處理，例如，在中國知網(wǎng)中輸入檢索詞“綠色網(wǎng)絡”，能夠檢索到74 050條數(shù)據(jù)記錄，其中，在宏觀經(jīng)濟管理與可持續(xù)發(fā)展學科領域有10 227條數(shù)據(jù)記錄，在工業(yè)經(jīng)濟領域有8 402條記錄，在建筑科學與工程領域有8 080條記錄，在農(nóng)業(yè)經(jīng)濟領域有7 217條記錄，在計算機軟件及計算機應用領域有2 419條記錄等等.但是，目前文獻的學科領域分類不夠精準，導致可能漏掉一些用戶所需的文獻資料，這無疑是對傳統(tǒng)檢索方式的一種極大挑戰(zhàn).

科技文獻主要以文本的形式存在，對科技文獻進行分類即是對文本進行分類處理.特征選擇是實現(xiàn)文本高效分類的前提，是文本自動分類的一個重要環(huán)節(jié)，特征選擇算法的性能將直接影響分類系統(tǒng)的最終效果.

目前，通常采用向量空間模型來描述文本向量，但是如果直接用分詞算法和詞頻統(tǒng)計方法得到的特征項來表示文本向量，那么這個向量的維度將會非常的大.這種未經(jīng)處理的文本矢量不僅會給后續(xù)工作帶來巨大的計算開銷，導致整個處理過程的效率非常低下，而且還會損害分類、聚類算法的精確性，以致使所得到的結果很難令人滿意.因此，需要對文本向量做進一步凈化處理，在保證原文含義的基礎之上，找出對文本特征類別最具有代表性的文本特征.目前關于特征詞的基本方法主要由以下幾種：互信息(Mutual Information))[1]，信息增益方法(Information Gain)[2]，χ-2統(tǒng)計量方法[3]，期望交叉熵(Expected Cross Entropy)[3]，文檔頻次方法(Document Frequency)[3].以上幾種方法，在英文特征提取方面都有各自的優(yōu)勢，但是由于中文和英文在語言表達形式上、句法分析和語義分析等方面都有較大差異，因此，將其用于中文文本分類并沒有很高的效率.

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

1 相關知識簡介

1.1 K-means算法

K-means算法是一種基于樣本間相似性度量的間接聚類方法，也被稱為K-平均或K-均值算法.算法的主要思想是通過迭代的過程把數(shù)據(jù)集劃分為不同的類別，使得評價聚類性能的準則函數(shù)達到最優(yōu).算法描述：首先要確定K值.第二，使用歐氏距離計算數(shù)據(jù)樣本之間的距離.歐式距離公式如下：

(1)

式中，d(xi，xj)表示xi和xj之間的相似度，該值越小，說明樣本xi和xj越相似.xi=(xi1，xi2,…,xid)，其中xi1，xi2,…,xid為xi的具體取值，xj=(xj1，xj2，…，xjd)，其中xj1，xj2，…，xjd為xj的具體取值.第三，對各個數(shù)據(jù)對象按照其到聚類中心距離進行聚類，最后更新聚類中心點，這個過程不斷重復直到滿足某個準則函數(shù)且中心的的改變小于某個特定的值才停止.

1.2 關聯(lián)規(guī)則與Apriori算法

關聯(lián)規(guī)則是描述數(shù)據(jù)項之間存在的潛在關系的規(guī)則，其形式化描述如下：設A=(A1，A2,…，Am)為數(shù)據(jù)項的集合，D為數(shù)據(jù)庫事務的集合，其中每個事務C都是數(shù)據(jù)項的集合，即C?A.關聯(lián)規(guī)則是形如W≥Z的蘊涵式，其中W和Z是項目集，且W?A，Z?A，W∪Z=?.定義支持度為D中包含W∪Z的事務占全部事務的百分比，記作supprot(W?Z)=P(W∪Z)；置信度為D中包含W∪Z的事務數(shù)與包含X的事務數(shù)的比值，記作confidence(W?Z)=P(W|Z).多個項組成的集合成為項集.包含k個項的項集稱為k-項集.若某個項集的支持度不小于設定的最小支持度閾值min_sup.則稱這個項集為頻繁項集.所有的頻繁k-項集組成的集合成為最大頻繁項集.

Apriori算法是一種逐層迭代挖掘關聯(lián)規(guī)則的頻繁項集算法，其核心思想是通過候選集生成和情節(jié)的向下封閉檢測兩個階段來尋找數(shù)據(jù)項之間的關聯(lián)關系.首先找出頻繁1-項集的集合.通過頻繁1-項集來尋找頻繁2-項集，…，通過k-1項集尋找K項集合，直至找到最大頻繁項集合.Apriori算法使用如下性質(zhì)來找到K維最大頻繁項集：

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

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

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

2 基于K-means和Apriori算法的多層特征提取

科技文獻一般結構規(guī)范，特征清晰，易于對其進行線性化處理，從而進行聚類分析.本文根據(jù)科技文獻的結構特點提出一種4層挖掘模式，并將K-means聚類分析方法應用于該模式的前3層，將Apriori方法應用于第4層，從而實現(xiàn)逐層特征提取.特征提取流程如圖1所示.

圖1 科技文獻特征提取流程圖Fig.1 Feature extraction flow chart of scientific literatures

這種方法的基本思想是，首先將挖掘過程分為4層：標題與關鍵字、摘要、文獻引言與總結部分、正文的其他部分.逐層定位中心點，這就使得簇的數(shù)目K不必由用戶事先指定.然后將第1層的 K個一級特征詞作為第2層的初始中心點，使用歐氏距離公式計算第2層數(shù)據(jù)對象之間的距離，根據(jù)其與中心點的距離分配給最近的一個簇，其次計算每個簇的平均值，并用該平均值代表相應的簇.再次根據(jù)每個對象與各個簇中心的距離，分配給最近的簇.中心點若有改變，重新計算數(shù)據(jù)對象之間的距離，并計算每個簇的平均值，這個過程不斷重復直到滿足某個準則函數(shù)且中心的改變小于某個特定的值才停止.最后在每個簇中選擇一個或多個代表詞作為二級特征詞，并且指定這些二級特征詞作為第3層的初始中心點.步驟相同，待算法收斂時得到三級特征詞.正文部分屬于四層挖掘模式中的第4層，采用Apriori算法對正文部分進頻繁項集的挖掘.將提取出的頻繁項集和三級特征詞進行比較，消除重復詞，最終得出特征詞集.

2.1 科技文獻標題和關鍵字中一級特征詞的提取

對科技文獻標題、關鍵字用漢語分詞系統(tǒng)進行切分，經(jīng)去停用詞處理，得出一級特征詞，作為第2層正文的引言和總結部分聚類算法的中心點.例如文獻標題為：基于潛在語義分析的微博主題挖掘模型研究，關鍵字為：微博；短文本；主題挖掘；LDA模型；增量聚類，得到的切分效果如圖2所示.

圖2 漢語自動分詞系統(tǒng)Fig.2 Chinese auto-segmentation system

2.2 科技文獻摘要中二級特征詞的提取

對文獻的摘要部分用上文提到的漢語分詞系統(tǒng)進行分詞處理，經(jīng)過去停用詞處理得到得到文獻語料庫(一).特征提取過程如下：

Step1：依據(jù)一級特征詞的個數(shù)確定K-means算法的K值;

Step2：使用歐氏距離計算數(shù)據(jù)樣本之間的距離Li;

Step3：對各個數(shù)據(jù)對象按照其到聚類中心距離進行聚類;

Step4：計算每個簇的平均值，并用該平均值代表相應的簇;

Step5：根據(jù)每個對象與各個簇中心的距離，分配給最近的簇.中心點若有改變，重新計算數(shù)據(jù)對象之間的距離，這個過程不斷重復直到滿足某個準則函數(shù)且中心點的改變小于某個特定的;

Step6：輸出結果簇.

此時只需對每個簇選擇一個或多個代表詞作為二級特征詞，同時作為下一層聚類的初始中心點.

2.3 科技文獻引言和總結中三級級特征詞的提取

引言主要介紹該文獻主題的應用背景，目前所取得的一些成果，所處的一個階段及存在的不足之處，段尾是對該文獻的總結和展望.提取過程同二級特征詞提取的方法相似，用單詞切分器對段首和段尾文本進行切分，切分出的單詞經(jīng)過去停用詞處理后，形成文獻語料庫(二).

2.4 科技文獻正文的其他部分獲取四級特征詞

用相同的方法對正文部分數(shù)據(jù)處理得到文獻語料庫(三)，由于科技文獻的正文部分數(shù)據(jù)量較大，特征詞的密度相對較小.適合采用挖掘布爾關聯(lián)規(guī)則頻繁項集的方法進行頻繁項的抽取.

Step1：掃描文獻語料庫(三)中主題為“數(shù)據(jù)信息，產(chǎn)生頻繁的1-項集;

Stept2：由頻繁1-項集經(jīng)過兩兩結合生成頻繁的2-項集;

Step3：通過頻繁(k-1)-項集產(chǎn)生k-項集候選集.

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

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

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

Step5：掃描文獻語料庫(三)，計算候選項集的支持度，將其與最小支持度比較，從而得到k維頻繁項集.直至生成最大項集，否則轉(zhuǎn)向(3);

Step6：將挖掘出的頻繁項經(jīng)過頻率過濾和名詞剪枝，得到評價對象集，作為四級特征詞.

將提取出的頻繁項集和三級特征詞進行比較，消除重復詞，最終得出特征詞集.

3 仿真實驗

在知網(wǎng)上搜集1 320篇屬于計算機行業(yè)的科技文獻，作為實驗數(shù)據(jù)的訓練集，其中80篇主題為“離散化”的文獻，220篇主題為“綠色網(wǎng)絡”的文獻，360篇主題為“特征詞選擇”的文獻，其余660篇作為測試集，測試集的文獻數(shù)量訓練集數(shù)量相一致.本文選擇一篇題目為“文本分類中連續(xù)屬性離散化方法的研究”的文獻作為特征詞挖掘的實驗樣例，進行MultiLM-FE方法中提出的四層挖掘模式的前三層的聚類分析實驗.

3.1 從文獻標題和關鍵字中獲取一級特征詞

文獻的標題為：“文本分類中連續(xù)屬性離散化方法的研究”，關鍵字為：機器學習；文本分類；信息增益；連續(xù)屬性離散化；Boosting算法.采用中國科學院計算技術研究所的切分器切分，結果為：文本/n分類/v中/f連續(xù)/a屬性/n離散/v化/v方法/n的/u研究/v機器/n學習/v；/w文本/n分類/v；/w信息/n增益/v；/w連續(xù)/a屬性/n離散/v化/v Boosting/n 算法/n.經(jīng)停用詞處理之后得出一級特征詞.如表1所示.

表1 一級特征詞

3.2 從摘要中獲取二級特征詞

首先對摘要進行分詞切分：針對/p_機器/n_學習/v_領域/n_的/u_一些/m_分類/v_算法/n_不能/v_處理/v_連續(xù)/a_屬性/n_的/u問題/n ……將/d_問題/n_轉(zhuǎn)換/v_成二/m_值/a_表示/v_方式/n_，/w_以/p_使得/v_這些/r_分類/v_算法/n_適用/v_于/p_連續(xù)/a_屬性/n_值/v_./w，由于數(shù)據(jù)使用不同的尺度度量，在使用歐氏距離之前先進行歸一化處理，屬性值歸一化定義為：

(2)

其中，ai是指某個對象的屬性i，vi是屬性i的真實值，最大屬性值maxvi和最小屬性值minvi是從訓練集實例中獲得的.選擇表1中的13個一級特征詞作為此步聚類的初始中心點，即K-means算法中K=13.算法收斂時得到13個結果簇，不同的結果簇會有不同的屬性詞，同時屬性詞的個數(shù)也不同.在個數(shù)較少的簇選擇一個詞作為此簇的代表，在個數(shù)較多的簇中可以選擇2個及2個以上的代表詞，目的是為了保證選出的代表詞能夠很好地反映出第二層即引言部分的特征屬性，將這些代表詞作為二級特征詞.結果如表2所示.

表2 二級特征詞

3.3 從文獻引言和總結部分獲取三級特征詞

使用分詞器對科技文獻的引言和總結部分進行單詞切分處理，然后經(jīng)去除停用詞處理和聚類對象的歸一化處理，再用Multi-Tap-FE算法進行聚類分析，初始中心點為表3的36個二級特征詞，即K-means算法中K=36，進行迭代計算，直至算法收斂，得到184個三級特征詞如表3所示.

表3 三級特征詞

對80篇關于“離散化”文獻均采用以上的方法對其進行特征提取.其中一級特征詞有948個，消除重復詞后有386個(以下均為消除停用詞后的數(shù)量).二級特征詞有1 954個，三級特征詞有7 285個.220篇關于“綠色網(wǎng)絡”的文獻的一級特征詞有1 023個，二級特征詞有4 563個，三級特征詞有18 956個，360篇關于“特征詞選擇”的文獻中一級特征詞有1 320個，二級特征詞有6 451，三級特征詞有10 034個.

3.4 從文獻正文中獲取頻繁項集獲得四級特征詞

本文采用C#語言，Visual Studio 2010開發(fā)環(huán)境編寫程序，分別對660篇訓練集的部分正文信息進行提取，將提取的信息進行分詞處理和去除停用詞處理，為了減少數(shù)據(jù)量剔除詞頻小于3的詞，按主題分類存入數(shù)據(jù)庫，形成評價語料庫，將660篇文獻當做是660個事務，用Apriori算法挖掘頻繁項集，本文以80篇主題為“離散化”的科技文獻作為Apriori算法的實驗數(shù)據(jù).文獻語料庫如表4所示，設最小支持度為40%，用Java語言實現(xiàn)Apriori算法，A_Algorithm類實現(xiàn)頻繁項集和頻繁關聯(lián)規(guī)則的挖掘過程，A_SubsetCombination類用于計算某頻繁項集的真子集.

表4 文獻語料庫

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

4 實驗結果與對比

4.1 對660篇測試集進行特征詞選擇

實驗結果如表5所示.

表5 本文特征詞提取方法特征詞提取結果

4.2 MultiLM-FE方法與IACA方法[1]比較

2012年復旦大學的劉海燕提出一種基于條件互信息的特征選擇改進算法(IACA方法).該算法采用K-means 的基本思想聚類特征，并從中選出類相關度最大的特征，從而去除不相關和冗余特征.該算法比較適合處理高維數(shù)據(jù)集，能夠較好地降維，并且達到不錯的效果.在此，本文所提出的方法MultiLM-FE方法與之在查全率、查準率和F值3方面做比較， F-score值為：

對文獻特征詞挖掘結果對比，如表6所示.

表6 各特征詞提取方法實驗對比結果

通過以上的比較，可以看出本文所提出MultiLM-FE方法的查全率、查準率都優(yōu)于普通的K-means與Apriori方法，在特征詞選擇算法的研究中有一定的有效性，表明Multi-Tap-FE方法在科技文獻抽取特征詞方面有著較好性能.

5 結束語

本文提出的Multi-Tap-FE方法，解決了K-means聚類算法不能自動確定最佳聚類初始點的問題，減少了聚類過程中信息損耗，能夠在文獻語料庫中更加準確的找到特征詞，較之以前的方法有很大提升，但該方法也受到一定因素的影響，如k-means算法對孤立點數(shù)據(jù)很敏感，孤立點會使聚類中心偏離從而影響聚類結果；Apriori算法在每次計算項集的支持度時，都對文獻語料庫中的所有數(shù)據(jù)進行掃描比較，若是一個大型的文獻語料庫，這種掃描比較會使得計算機系統(tǒng)的I/O開銷大大增加.而這種代價是隨著文獻語料庫記錄的增加呈現(xiàn)出幾何級數(shù)的增加.這些都是我們今后做研究應該考慮的方向.

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

[2] 毛國君， 段麗娟， 王 實，等. 數(shù)據(jù)挖掘原理與算法[M].北京：清華大學出版社， 2007．

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

[4] Yang C C， Tobun D N. Analyzing and visualizing Web opinion development and social interactions with density-based clustering[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part A :Systems and Humans， 2011， 41(6): 1144-1155．

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

[6] Sina T. An unsupervised feature selection algorithm based on ant colony optimization[J]. Engineering Applications of Artificial intelligence， 2014， 32(1): 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. Data Mining: Concepts and Techniques[M]. 北京: 機械工程出版社，2001．

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

[11] 郭亞維， 劉曉霞. 文本分類中信息增益特征選擇方法的研究[J]. 計算機工程與應用， 2012， 48(27): 119-127．

[12] 周麗紅， 劉 勘. 基于關聯(lián)規(guī)則的科技文獻分類研究[J]. 圖書情報工作， 2012， 56(4): 12-16．

Multi-level feature extraction method based onK-means and Apriori

QIAN Shenyi， ZHU Yanling, ZHU Haodong

(School of Computer and Communication Engineering， Zhengzhou University of Light Industry， Zhengzhou 450002)

This article proposed a four-mining model based on the structural characteristics of scientific literature， and combinedK-means algorithm and Apriori algorithm to construct an new feature extraction method-MultiLM-FE Method. Firstly， scientific literature was divided into four layers according to its structure. And then， it selected features progressively for the former three layers byK-means clustering. Finally， it found out the maximum frequent itemsets of fourth layer by Aprori algorithm to act as a collection of features fourth layer. This method can solve the problem that theK-means clustering algorithm can’t determine the most appropriate clustering starting point automatically， and reduces the loss of information in the clustering process， so it is possible to find features more accurately in the literature corpus. Experimental results showed that this method was feasible and effective and had greatly improved especially in terms of the scientific literature when compared with the previous method．

scientificl iterature; feature extraction;K-means; Apriori

2014-11-24.

國家自然科學基金項目(61201447); 河南省科技攻關項目(122102210024、122300410287); 河南省高等學校青年骨干教師資助計劃項目(2014GGJS-084)； 河南省教育廳科學技術研究重點項目(13A520367)； 鄭州市科技計劃項目(121PPTG362-12，131PPTGG411-8)； 鄭州輕工業(yè)學院校級青年骨干教師培養(yǎng)對象資助計劃項目(XGGJS02)．

1000-1190(2015)03-0357-06

TP311

A

*通訊聯(lián)系人. E-mail: zhuhaodong80@163.com．