基于Citation-KNN的語(yǔ)義隱含主題詞自動(dòng)抽取方法

1、基于Citation-KNN的語(yǔ)義隱含主題詞自動(dòng)抽取方法基于Citation-KNN的語(yǔ)義隱含主題詞自動(dòng)抽取方法 本研究受“十一五”國(guó)家科技支撐計(jì)劃重點(diǎn)項(xiàng)目(2006BAH03B02)、教育部人文社科項(xiàng)目(06JC870001)、南京理工大學(xué)青年科研扶持基金項(xiàng)目(JGQN0701)、南京理工大學(xué)科研啟動(dòng)基金項(xiàng)目(AB41123)資助。章成志1,2 劉耀1 王惠臨11. 中國(guó)科學(xué)技術(shù)信息研究所, 北京, 1000382. 南京理工大學(xué)信息管理系, 南京, 210094zhangchz, liuy, wanghl 摘 要：現(xiàn)有的關(guān)鍵詞抽取技術(shù)僅僅是抽取出現(xiàn)在正文中的詞匯，不能夠抽取語(yǔ)義上隱含的主題

2、。語(yǔ)義隱含主題的抽取是文本挖掘技術(shù)的難點(diǎn)。眾所周知，KNN方法作為機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)經(jīng)典的方法，在很多領(lǐng)域都有出色的表現(xiàn)。本文以KNN算法為基礎(chǔ)，提出基于Citation-KNN的語(yǔ)義隱含主題詞自動(dòng)抽取方法。實(shí)驗(yàn)結(jié)果表明該方法在進(jìn)行語(yǔ)義隱含主題詞抽取任務(wù)上的有效性。關(guān)鍵詞：關(guān)鍵詞抽?。浑[含語(yǔ)義主題詞；Citation-KNN；文本挖掘 1 引 言關(guān)鍵詞是最能反映文章主題或內(nèi)容的詞匯，是為了滿足文獻(xiàn)標(biāo)引或檢索工作的需要而從文章中萃取出的、表示全文主題內(nèi)容信息條目的單詞、詞組或術(shù)語(yǔ)。在文獻(xiàn)情報(bào)領(lǐng)域，關(guān)鍵詞抽取是一項(xiàng)困難的任務(wù)。首先，關(guān)鍵詞抽取是一項(xiàng)需要高度概括、分析和創(chuàng)造的活動(dòng)，需要標(biāo)引人員具有較

3、高的專業(yè)知識(shí)和標(biāo)引經(jīng)驗(yàn)。其次，為了準(zhǔn)確描述文本內(nèi)容，標(biāo)引人員通常會(huì)創(chuàng)造一些由多個(gè)詞按照一定規(guī)則連接起來(lái)的組合詞組。這些組合詞在文本中可能很少出現(xiàn)，甚至不出現(xiàn)。另外，由于經(jīng)驗(yàn)和知識(shí)背景不同，在標(biāo)引同一篇文本時(shí)，不同的標(biāo)引人員會(huì)給出不同的關(guān)鍵詞集合。這突出反映在作者給出的關(guān)鍵詞與專業(yè)標(biāo)引人員給出的關(guān)鍵詞通常存在很大差異。關(guān)鍵詞自動(dòng)抽取能夠解決上面的第三個(gè)問(wèn)題，但對(duì)于前面兩個(gè)問(wèn)題所起的作用很小。這是因?yàn)槟壳坝糜谧匀徽Z(yǔ)言處理的各種機(jī)器學(xué)習(xí)方法，還不能真正理解文本內(nèi)容，只能通過(guò)大量的詞或詞組出現(xiàn)的頻度、句法規(guī)則等信息進(jìn)行統(tǒng)計(jì)和學(xué)習(xí)。但是，在許多應(yīng)用領(lǐng)域，基于大規(guī)模數(shù)據(jù)集上的機(jī)器學(xué)習(xí)方法，特別是基于統(tǒng)計(jì)的

4、機(jī)器學(xué)習(xí)，通常比完全采用人工方法效果更好、更穩(wěn)定，例如文本分類、OCR識(shí)別、詞義排歧、信息檢索等。H. P. Luhn在20世紀(jì)50年代末首先開(kāi)展自動(dòng)標(biāo)引試驗(yàn) (Luhn 1957, Luhn 1958) ，而在1963年，美國(guó)Chemical Abstracts從第58卷起，就開(kāi)始采用電子計(jì)算機(jī)編制關(guān)鍵詞索引，提供快速檢索文獻(xiàn)資料主題的途徑。純粹的統(tǒng)計(jì)方法最早也最常被應(yīng)用于關(guān)鍵詞自動(dòng)抽取 (Edmundson & Oswald 1959, Edmundson 1969, Chien 1997)；20世紀(jì)70年代初，Lois L. Earl開(kāi)始采用句法分析等語(yǔ)言學(xué)方法 (Lois 19

5、70)；70年代中期，Salton等將機(jī)器學(xué)習(xí)技術(shù)引入關(guān)鍵詞自動(dòng)抽取中 (Salton, Wong & Yang 1975)；20世紀(jì)90年代末，Turney將遺傳算法 (Turney 1999, Turney 2000)、Frank將Bayes方法引入關(guān)鍵詞自動(dòng)抽取 (Frank, Paynter & Witten, et al 1999)。近年來(lái)關(guān)鍵詞自動(dòng)抽取的研究趨于活躍，2001年，Anjewierden與Kabel提出基于本體的自動(dòng)標(biāo)引方法 (Anjewierden & Kabel 2001)；2003年，Tomokiyo與Hurst提出了基于語(yǔ)言模型的關(guān)鍵詞

6、提取方法 (Tomokiyo & Hurst 2003)，Hulth利用Bagging算法進(jìn)行了基于集成學(xué)習(xí)的關(guān)鍵詞抽取 (Hulth 2003)；2004年，李素建提出基于最大熵模型的關(guān)鍵詞提取方法 (李素建, 王厚峰, 俞士汶等，2004)；2007年，Ercan G.與Cicekli I.提出基于詞匯鏈的自動(dòng)標(biāo)引方法 (Ercan & Cicekli 2007)。根據(jù)Turney的研究，人工標(biāo)注的詞匯，大約65%至90出現(xiàn)在正文中 (Turney 1997)。那些不出現(xiàn)在正文中的關(guān)鍵詞本文稱之為“隱含主題”。隱含主題的抽取是一項(xiàng)非常困難的工作，現(xiàn)有的關(guān)鍵詞自動(dòng)抽取算法，無(wú)

7、論是基于機(jī)器學(xué)習(xí)還是基于純粹的統(tǒng)計(jì)方法，都很難抽取這部分詞匯。通常的隱含主題詞自動(dòng)抽取方法是借助于外部資源，如敘詞表、本體等資源，將語(yǔ)義隱含主題詞自動(dòng)抽取過(guò)程轉(zhuǎn)換為主題詞的分類過(guò)程，或?qū)⑽谋镜年P(guān)鍵詞轉(zhuǎn)換為主題詞。本文嘗試使用Citation-KNN的語(yǔ)義隱含主題詞自動(dòng)抽取算法來(lái)抽取文章的隱含主題。實(shí)驗(yàn)證明，這一方法是切實(shí)有效的。2 基于Citation-KNN的語(yǔ)義隱含主題詞自動(dòng)抽取算法2.1 Citation-KNN算法描述（1） KNN算法概述K最近鄰方法（KNN）是一種基于統(tǒng)計(jì)的懶惰學(xué)習(xí)算法，是由Cover和Hart于1968年提出的 (Cover & Hart 1968)。KN

8、N方法在很多領(lǐng)域都有應(yīng)用，在文本自動(dòng)分類領(lǐng)域，K最近鄰方法被證明是效果最好的方法之一 (Yang & Liu 1999)。測(cè)試樣本根據(jù)最近鄰中的多數(shù)類進(jìn)行分類。yi=argmax （1）其中，v是類標(biāo)號(hào)，yi是一個(gè)最近鄰的類標(biāo)號(hào)，I(·)是指示函數(shù)，如果其參數(shù)為真，則返回“1”，否則返回“0”。由于每個(gè)近鄰對(duì)分類的影響可能不一樣，可以根據(jù)測(cè)試樣本與每個(gè)最近鄰xi的相似度對(duì)最近鄰進(jìn)行加權(quán) (Tan, Steinbach & Kumar, 2006)，越相似的近鄰，賦予越高的權(quán)重。如果直接以測(cè)試樣本與近鄰的相似度作為權(quán)重，則絕對(duì)權(quán)重公式、相對(duì)權(quán)重計(jì)算公式分別為式（2）、式

9、（3）。wi= Sim(xi, xj) （2）wi= （3）考慮到近鄰的權(quán)重后，分類決策函數(shù)為：yi= argmax （4）（2） Citation-KNN算法描述wc1C1C2R2CqR1RkAwcnwciwc2wr1wr2wrjwrm圖1 Citation-KNN中文本“引用”與“被引用”示意圖Citation-KNN最初由Jun Wang和Jean-Daniel Zucker提出，并用于解決多示例學(xué)習(xí)問(wèn)題（Wang & Zucker 2000）。Citation-KNN是對(duì)傳統(tǒng)KNN算法的一種改進(jìn)，主要思想是借助與文獻(xiàn)計(jì)量學(xué)中的引用與被引用這一思路，在對(duì)測(cè)試樣本xi進(jìn)行類別決策時(shí)

10、，除了考慮最近鄰的K個(gè)訓(xùn)練樣本的類別外（即測(cè)試樣本的“引文”），還考慮到訓(xùn)練樣本集中將xi作為其K個(gè)最近鄰之一的訓(xùn)練樣本（即測(cè)試樣本的“被引”樣本）的類別。圖1為Citation-KNN中文本“引用”與“被引用”示意圖。圖1中，R1、R2、Rk為被樣本A“引用”的K個(gè)文本，wr1、wr2、wrk為對(duì)應(yīng)的權(quán)重；C1、C2、Cq為樣本A的“被引”Q個(gè)文本，wC1、wC2、wCq為對(duì)應(yīng)的權(quán)重。在進(jìn)行分類決策時(shí)，綜合考慮“引用”與“被引”的最近鄰樣本的類標(biāo)號(hào)，并可以根據(jù)“引用”與“被引”對(duì)分類的影響賦予不同的權(quán)重，因此給出如下的分類決策函數(shù)：yi= argmax （5）其中，、分別為Citation-

11、KNN 中“引用”與“被引”的權(quán)重，且+=1，本文取=0.5。圖2給出了Citation-KNN算法的具體描述。算法：Citation-KNN算法描述輸入：測(cè)試集(x1,y1),(xn,yn), ,其中xiÎX, yiÎY, 訓(xùn)練集(x1,y1),(xm,ym),其中xjÎX, yjÎY輸出：測(cè)試集中每個(gè)xi對(duì)應(yīng)的類標(biāo)號(hào)yi步驟：設(shè)定最近鄰的數(shù)目K，設(shè)定=0.5；For i=1 to N 在訓(xùn)練集中選擇離xi最近的K個(gè)訓(xùn)練樣本構(gòu)成的集合x(chóng)1，并計(jì)算每個(gè)樣本的權(quán)重wri，1<i<K； 在訓(xùn)練集中選擇以xi作為其最近的K個(gè)最近鄰之一的訓(xùn)練樣本集合

12、x2；并計(jì)算每個(gè)樣本的權(quán)重wcj，1<j<Q；yi= argmax End For圖2 Citation-KNN算法描述2.2 Citation-KNN中的近鄰加權(quán)方法本文利用Citation-KNN進(jìn)行隱含主題詞自動(dòng)抽取中，根據(jù)不同近鄰的特征對(duì)決策函數(shù)進(jìn)行加權(quán)。主要用到的加權(quán)方法有：根據(jù)相似度大小進(jìn)行加權(quán)、根據(jù)樣本本身的特征（如PageRank值、引用頻次等）進(jìn)行加權(quán)。其中相似度加權(quán)公式如式（3）所示，相似度為文本向量夾角的余弦 （Baeza-Yates & Ribeiro-Neto, 1999）。樣本的PageRank值、引用頻次的定義與計(jì)算方法見(jiàn)文（Zhang, Su

13、 & Zhou 2008）。2.3 基于Citation-KNN的語(yǔ)義隱含主題詞自動(dòng)抽取算法本文將隱含主題詞自動(dòng)抽取轉(zhuǎn)化為分類學(xué)習(xí)問(wèn)題，根據(jù)圖2所示的Citation-KNN算法，得到待抽取文檔的K個(gè)相似近鄰的樣本文檔集合與將待抽取文檔作為其最近的K個(gè)最近鄰之一的訓(xùn)練樣本文檔集合，結(jié)合每個(gè)樣本文檔的權(quán)重，進(jìn)行投票，最終得到待抽取文檔的隱含主題詞自動(dòng)抽取結(jié)果。3 實(shí)驗(yàn)結(jié)果分析與討論3.1 試驗(yàn)數(shù)據(jù)與評(píng)價(jià)方法（1）試驗(yàn)數(shù)據(jù)實(shí)驗(yàn)使用的數(shù)據(jù)集是中國(guó)學(xué)術(shù)期刊全文數(shù)據(jù)庫(kù) 中國(guó)期刊全文數(shù)據(jù)庫(kù). . Accessed: 2007.10.10.。從中國(guó)學(xué)術(shù)期刊全文數(shù)據(jù)庫(kù)經(jīng)濟(jì)類數(shù)據(jù)中選出由作者給出了關(guān)鍵詞

14、的文獻(xiàn)作為K最近鄰關(guān)鍵詞抽取的訓(xùn)練集，共10萬(wàn)余篇，從中國(guó)學(xué)術(shù)期刊全文數(shù)據(jù)庫(kù)2005年數(shù)據(jù)中隨機(jī)選出作者標(biāo)注關(guān)鍵詞的600篇文獻(xiàn)作為測(cè)試集。（2）評(píng)價(jià)方法實(shí)驗(yàn)結(jié)果的評(píng)價(jià)采用Turney提出的方案，使用準(zhǔn)確率（Precision）和召回率（Recall）以及F1衡量算法的性能。在Turney的方案中，機(jī)器抽取的關(guān)鍵詞和人工標(biāo)注的關(guān)鍵詞完全一致才算匹配 (Turney 1997)。定義：Precision= （6）Recall= （7）F1=(2×Precision×Recall) / (Precision +Recall) （8）其中，是機(jī)器抽取的關(guān)鍵詞和人工標(biāo)注的關(guān)鍵詞完全

15、匹配的數(shù)目，是機(jī)器自動(dòng)標(biāo)注的關(guān)鍵詞數(shù)目，是人工標(biāo)注的關(guān)鍵詞數(shù)目。3.2 試驗(yàn)結(jié)果與分析本文進(jìn)行基于KNN方法與基于Citation-KNN的隱含主題詞自動(dòng)抽取的對(duì)照研究。依據(jù)文本向量夾角的余弦作為文本間的相似度。表1為其中一篇篇名為“現(xiàn)代網(wǎng)絡(luò)銀行發(fā)展中的金融監(jiān)管思考”的文章的相似文獻(xiàn)集合前10篇最相似的文獻(xiàn)信息。篇名中文關(guān)鍵詞引用頻次PageRank值網(wǎng)絡(luò)銀行發(fā)展中的問(wèn)題及其對(duì)策網(wǎng)絡(luò)銀行，金融電子化，金融監(jiān)管10.575000網(wǎng)絡(luò)銀行理論及其在我國(guó)的實(shí)踐網(wǎng)絡(luò)銀行，理論依據(jù)10.377679全球網(wǎng)絡(luò)銀行的發(fā)展與中國(guó)網(wǎng)絡(luò)銀行發(fā)展戰(zhàn)略網(wǎng)絡(luò)銀行，生成機(jī)理，制約因素，發(fā)展戰(zhàn)略10.510606對(duì)我國(guó)網(wǎng)絡(luò)

16、銀行發(fā)展與監(jiān)管問(wèn)題的研究網(wǎng)絡(luò)銀行，監(jiān)管33.219107網(wǎng)絡(luò)銀行的競(jìng)爭(zhēng)優(yōu)勢(shì)探析網(wǎng)絡(luò)銀行，競(jìng)爭(zhēng)優(yōu)勢(shì)，阻礙因素，政策建議10.510606網(wǎng)絡(luò)銀行的安全性分析網(wǎng)絡(luò)銀行，安全性10.320000國(guó)外網(wǎng)絡(luò)銀行發(fā)展模式的啟示網(wǎng)絡(luò)銀行，網(wǎng)絡(luò)安全，發(fā)展模式，啟示10.362500西方網(wǎng)絡(luò)銀行的發(fā)展戰(zhàn)略及啟示網(wǎng)絡(luò)銀行，發(fā)展戰(zhàn)略，啟示10.227273我國(guó)網(wǎng)絡(luò)銀行集約化經(jīng)營(yíng)之策略網(wǎng)絡(luò)銀行，集約化經(jīng)營(yíng)，網(wǎng)上支付，便利服務(wù)，網(wǎng)絡(luò)顧客10.362500我國(guó)發(fā)展網(wǎng)絡(luò)銀行所面臨的問(wèn)題與對(duì)策網(wǎng)絡(luò)銀行，創(chuàng)新，對(duì)策10.433333表1 相似文檔(Top-10)樣例本文對(duì)隱含主題詞自動(dòng)抽取的測(cè)評(píng)方法為計(jì)算標(biāo)引結(jié)果的查準(zhǔn)率、召回

17、率以及F1值。在實(shí)驗(yàn)中必須事先從原文關(guān)鍵詞中抽取出原文中沒(méi)有出現(xiàn)的詞語(yǔ)，將這些詞語(yǔ)作為隱含主題詞自動(dòng)抽取性能的評(píng)價(jià)依據(jù)。表2給出了兩種隱含主題詞自動(dòng)抽取方法的結(jié)果。通過(guò)表2可以看出，基于KNN或Citation-KNN的隱含主題詞自動(dòng)抽取方法具有一定效果。其中基于Citation-KNN的隱含主題詞自動(dòng)抽取的查準(zhǔn)率高于基于KNN的抽取方法，這表明基于Citation-KNN算法在分類決策任務(wù)中的可靠性要高于KNN算法。同時(shí)，通過(guò)表2還可以看出，兩種隱含主題詞自動(dòng)抽取的查準(zhǔn)率和召回率都低于50%。因此我們的下一步工作為尋找提高基于KNN或Citation-KNN的隱含主題詞自動(dòng)抽取方法質(zhì)量的方法

18、。標(biāo)引模型PRF1KNN0.25860.48040.3362Citation-KNN0.35770.47950.4097表2 隱含主題詞自動(dòng)抽取結(jié)果4 小 結(jié)本文以KNN算法為基礎(chǔ)，提出基于Citation-KNN的隱含主題詞自動(dòng)抽取方法?；贑itation-KNN的隱含主題詞自動(dòng)抽取方法是一種懶惰學(xué)習(xí)算法（Lazy Learning），它利用文本集中與待標(biāo)引記錄相似的文檔的關(guān)鍵詞，作為待標(biāo)引記錄隱含主題詞自動(dòng)抽取的依據(jù)。根據(jù)相似文檔本身的特征可以進(jìn)行基于加權(quán)方式的Citation-KNN的隱含主題詞自動(dòng)抽取。實(shí)驗(yàn)結(jié)果表明該方法在進(jìn)行隱含主題詞自動(dòng)抽取這一任務(wù)時(shí)的有效性?；贑itation

19、-KNN的隱含主題詞自動(dòng)抽取方法存在的問(wèn)題是，隱含主題詞自動(dòng)抽取的效果強(qiáng)烈依賴于數(shù)據(jù)集的規(guī)模。只有當(dāng)數(shù)據(jù)集規(guī)模達(dá)足夠大的情況下，才能充分挖掘出與待標(biāo)記錄內(nèi)容相似的記錄，這樣可以保證隱含主題詞自動(dòng)抽取的可靠性。另外，文本間的相似度計(jì)算也是一個(gè)關(guān)鍵問(wèn)題，相似度計(jì)算的質(zhì)量對(duì)隱含主題詞自動(dòng)抽取的效果有重要影響。下一步的工作主要包括：獲取大量帶有關(guān)鍵詞的數(shù)據(jù)集，提高基于Citation-KNN的隱含主題詞自動(dòng)抽取方法的可靠性；提出可加可靠的隱含主題詞自動(dòng)抽取的評(píng)價(jià)方法；探索計(jì)算文本間相似度更加可靠的方法。參 考 文 獻(xiàn)Anjewierden A, Kabel S. 2001. Automatic Ind

20、exing of Documents with Ontologies. In: Proceedings of the 13th Belgian/Dutch Conference on Artificial Intelligence (BNAIC-01), Amsterdam, Neteherlands. 2330.Baeza-Yates R, Ribeiro-Neto B. 1999. Modern Information Retrieval. New York: Association for Computing Machine (ACM) Press, 27-30.Chien LF. 19

21、97. PAT-tree-based Keyword Extraction for Chinese Information Retrieval. In: Proceedings of the ACM SIGIR International Conference on Information Retrieval, Philadelphia, USA: ACM Press, 5059Cover TM, Hart PE. 1968. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, IT

22、-13 : 2127Edmundson H P, Oswald V A. 1959. Automatic Indexing and Abstracting of the Contents of Documents. Planning Research Corp, Document PRC R-126, ASTIA AD No. 231606, Los Angeles. 1142.Edmundson H P. 1969. New Methods in Automatic Abstracting Extracting. Journal of the Association for Computin

23、g Machinery.16(2): 264285.Ercan G, Cicekli I. 2007. Using Lexical Chains for Keyword Extraction. Information Processing and Management, 43(6): 17051714.Frank E, Paynter GW, Witten IH, et al. 1999. Domain-specific keyphrase extraction. In: Proceedings of the Sixteenth International Joint Conference o

24、n Artificial Intelligence (IJCAI-99), California: Morgan Kaufmann, 668673Hulth A. 2003. Improved Automatic Keyword Extraction Given More Linguistic Knowledge. In: Proceedings of the 2003 Conference on Emprical Methods in Natural Language Processing, Sapporo, Japan, 216223.Lois L E. 1970. Experiments

25、 in Automatic Indexing and Extracting. Information Storage and Retrieval, 6: 313334.Luhn H P. 1957. A Statistical Approach to Mechanized Encoding and Searching of Literary Information. IBM Journal of Research and Development, 1(4): 309317Luhn H P. 1958. The Automatic Creation of Literature Abstracts

26、. IBM Journal of Research and Development. 2(2): 159165.Salton G, Wong A, Yang C S. 1975. A Vector Space Model for Automatic Indexing. Communications of ACM, 18(11): 613620.Tan P, Steinbach M, Kumar V. 2006. Introduction to Data Mining. Boston: Addison-Wesley, 225.Tomokiyo T, Hurst M. 2003. A langua

27、ge Model Approach to Keyphrase Extraction. In: Proceedings of the ACL Workshop on Multiword Expressions: Analysis, Acquisition & Treatment, Sapporo, Japan, 3340.Turney P D. 1999. Learning to Extract Keyphrases from Text. NRC Technical Report ERB-1057, National Research Council, Canada. 143.Turne

28、y PD. 1997. Extraction of Keyphrase from Text: Evaluation of Four Algorithms. Techial Repor ERB-1051, National Research Council, Institute for Information Technology.Turney PD. 2000. Learning algorithms for keyphrase extraction. Information Retrieval. 2:303336Wang J, Zucker J D. 2000. Solving the Mu

29、ltiple-instance Problem: A Lazy Learning Approach. In: Proceedings of 17th International Conference on Machine Learning (ICML2000). San Francisco: Morgan Kaufmann Publishers, 1119-1125.Yang Y, Liu X. 1999. A Re-examination of Text Categorization Methods. In: Proceedings of 22nd Annual International

30、ACMSIGIR Conference on Research and Development in Information Retrieval (SIGIR99), Berkeley, CA, USA, 4249. Zhang CZ, Su XN, Zhou DM. 2008. Document Clustering Using Sample Weighting. In: He YX, Xiao GZ, Sun MS eds. Recent Advance of Chinese Computing Technologies Singapore: Chinese and Oriental Languages Information Processing Society, 3: 260-265. 李素建 王厚峰 俞士汶 辛乘勝，2004，關(guān)鍵詞自動(dòng)標(biāo)引的最大熵模型應(yīng)用研究，計(jì)算機(jī)學(xué)報(bào)，27(9):11921197。Automatic Implicit Semantic Subject Extraction Based on Citation-KNN