許愛琴，王夢潔，劉永堅(jiān)，王衛(wèi)華

（1.武漢理工大學(xué)理學(xué)院，湖北 武漢 430070；2.武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430070）

自動(dòng)標(biāo)引是一種利用計(jì)算機(jī)自動(dòng)給出信息主題詞或關(guān)鍵詞的技術(shù)。這一技術(shù)涉及到如何從信息中提取有實(shí)意的詞匯，并從這些詞匯中分析能夠代表一段信息或一篇文章主題意義的詞匯［1］。關(guān)鍵詞是表達(dá)文件主題意義的最小單位，它可以提高信息檢索的準(zhǔn)確性，幫助讀者快速查找相關(guān)內(nèi)容所需的文獻(xiàn)信息。但由于傳統(tǒng)的人工標(biāo)引關(guān)鍵詞費(fèi)時(shí)費(fèi)力且主觀性較強(qiáng)，不利于下一步的檢索，因此，對(duì)關(guān)鍵詞提取技術(shù)的研究是一項(xiàng)具有重要意義的工作。

在西文文獻(xiàn)的自動(dòng)標(biāo)引中，相比于單個(gè)的單詞，單詞序列即詞組有語法結(jié)構(gòu)，對(duì)于表達(dá)信息的主題有較強(qiáng)的代表能力。西文關(guān)鍵詞的提取主要包括3個(gè)步驟:①候選關(guān)鍵詞集的自動(dòng)識(shí)別；②引入一系列特征來計(jì)算候選集里關(guān)鍵詞的權(quán)重并按權(quán)值排列；③用一個(gè)監(jiān)督模型從具有相應(yīng)權(quán)值的候選集中選取出最終的關(guān)鍵詞匯［2］。筆者主要討論候選關(guān)鍵詞集的自動(dòng)識(shí)別。目前，最常用的識(shí)別方法有兩種:基于NGram 法［3］和基于詞性序列法（又稱 POS 法）［4］。由于每個(gè)候選集權(quán)值必須在步驟②中計(jì)算，而這一步占據(jù)了系統(tǒng)運(yùn)行的大部分時(shí)間，因此，大量的候選集必然會(huì)導(dǎo)致系統(tǒng)效率低下［5］。筆者在N-Gram基礎(chǔ)上提出了關(guān)鍵單詞拓展樹算法，由此產(chǎn)生候選關(guān)鍵詞集，并將其與N-Gram法產(chǎn)生的候選集大小進(jìn)行比較。

1 關(guān)鍵單詞集

1.1 關(guān)鍵單詞與關(guān)鍵詞的關(guān)系

關(guān)鍵單詞是指文本中重要的單個(gè)的單詞，在文本中出現(xiàn)的頻率較高，而關(guān)鍵詞是指由一個(gè)或幾個(gè)單詞組成的具有一定的表達(dá)文本主題的單詞串。通常直觀地認(rèn)為關(guān)鍵詞一定包含關(guān)鍵單詞，而筆者認(rèn)為在一特定領(lǐng)域的文章標(biāo)引中，關(guān)鍵單詞可以作為發(fā)現(xiàn)關(guān)鍵詞的基礎(chǔ)，這里主要針對(duì)科技文獻(xiàn)這一領(lǐng)域?；陉P(guān)鍵單詞發(fā)現(xiàn)關(guān)鍵詞的方法可以在一些現(xiàn)存的相關(guān)作品中發(fā)現(xiàn)，如TURNEY的作品［6］。筆者通過一個(gè)統(tǒng)計(jì)研究實(shí)驗(yàn)來驗(yàn)證這一思想。

通過輸入2～10個(gè)關(guān)鍵詞自動(dòng)抽取出400篇科技相關(guān)論文，實(shí)驗(yàn)前一般要對(duì)輸入計(jì)算機(jī)的文本進(jìn)行預(yù)處理。設(shè)k為關(guān)鍵單詞的個(gè)數(shù)，a為以關(guān)鍵單詞開頭或結(jié)尾的關(guān)鍵詞在所有已知關(guān)鍵詞中的比例，b為所有關(guān)鍵單詞的頻數(shù)在預(yù)處理后文本中占據(jù)的比例。通過改變k的值，計(jì)算分析a和b值的變化情況。其分析結(jié)果如圖1所示。

從圖1中可以分析出絕大多數(shù)的關(guān)鍵詞是以關(guān)鍵單詞集中的單詞開頭或結(jié)尾的。當(dāng)k增大時(shí)，a和b都在增長，當(dāng) k增大到40時(shí)，a高達(dá)90%以上，雖然b不到40%，通過比較a與b，可以得出關(guān)鍵單詞對(duì)待測關(guān)鍵詞有較大的覆蓋能力，因此可以通過先抽取關(guān)鍵單詞集，再由關(guān)鍵單詞前后拓展得到待測關(guān)鍵詞，找出每個(gè)關(guān)鍵單詞在文本中的位置。

圖1 關(guān)鍵詞數(shù)目與其對(duì)關(guān)鍵詞抽取的覆蓋能力比較

1.2 關(guān)鍵單詞集的獲取

關(guān)鍵單詞集的獲?。?］必須在已經(jīng)預(yù)處理過的文本中選取，通過計(jì)算該文本中的所有非停用單詞的頻率，將其按從大到小的順序排列，并記錄它們每次出現(xiàn)時(shí)對(duì)應(yīng)文本中的位置，當(dāng)k的大小確定了，就取頻率大小排在前k的非停用單詞，同時(shí)將它們的位置記錄一起取出。這樣關(guān)鍵單詞集就確定了，這里不妨記其為Mkw={（Wi，Pi），i=1，2，…，k}，其中 Wi為單個(gè)關(guān)鍵單詞，Pi為 Wi出現(xiàn)的位置矩陣。根據(jù)圖1分析可知，當(dāng)k取40時(shí)，關(guān)鍵單詞對(duì)關(guān)鍵詞的覆蓋率達(dá)到90%以上，因此，建議將關(guān)鍵單詞的個(gè)數(shù)設(shè)置為40。

2 關(guān)鍵詞的形成算法

根據(jù)Porter莖算法［8］中在相同莖下的單詞進(jìn)行組配成詞的思想，先描述基于關(guān)鍵單詞集產(chǎn)生候選集的前拓展算法，所謂前拓展就是以關(guān)鍵單詞開頭的關(guān)鍵詞。統(tǒng)計(jì)表明，包含4個(gè)單詞的關(guān)鍵詞是相當(dāng)少的，把一個(gè)關(guān)鍵詞的最大長度設(shè)置為4是合理的［9］。同現(xiàn)存的很多抽取系統(tǒng)一樣，筆者設(shè)置一個(gè)臨界值來過濾掉低頻數(shù)的單詞組合，在這里可設(shè)置為3［10］，即在文本中出現(xiàn)次數(shù)小于3的詞待測集將自動(dòng)過濾，其具體算法過程如下:

（1）輸入已預(yù)處理過的文件及其關(guān)鍵單詞集Mkw；

（2）賦值每次抽取Mkw中的一個(gè)關(guān)鍵單詞Wi和它的位置矩陣Pi，并用＊標(biāo)記它為非葉節(jié)點(diǎn)；

（3）根據(jù)Porter莖算法，將Wi作為根節(jié)點(diǎn)開始建立拓展樹；

（4）當(dāng)在建的拓展樹中含有未拓展的非葉節(jié)點(diǎn)時(shí)，分別取出每個(gè)非葉節(jié)點(diǎn)和它的位置矩陣，做如下處理，轉(zhuǎn)入步驟（5），否則轉(zhuǎn)入步驟（10）；

（5）將非葉節(jié)點(diǎn)的深度（即由根節(jié)點(diǎn)開頭到該節(jié)點(diǎn)的單詞序列的長度）記為L，若L＜4，則將該非葉節(jié)點(diǎn)的位置矩陣中每個(gè)元素的下個(gè)位置所對(duì)應(yīng)文本中的單詞放入一個(gè)子集合中，不妨記為Mi，轉(zhuǎn)入步驟（6）；若 L≥4，則轉(zhuǎn)入步驟（9）；

（6）對(duì)Mi全體元素利用Porter莖算法分別對(duì)其莖進(jìn)行拓展，其中Mi中的每個(gè)不同莖（即Mi中的一個(gè)元素）記為wj，轉(zhuǎn)入步驟（7）；

（7）賦值wj和其在文本中其父節(jié)點(diǎn)這個(gè)單詞之后出現(xiàn)的位置矩陣，若其位置矩陣的元素個(gè)數(shù)小于3，或wj是一個(gè)詞邊界，則用#標(biāo)記其為葉節(jié)點(diǎn)，反之則用＊標(biāo)記為非葉節(jié)點(diǎn)，轉(zhuǎn)入步驟（8）；

（8）再從Mi中取出與步驟（7）中不同的莖，同樣對(duì)其進(jìn)行步驟（7）的操作，直至取完Mi中的元素，轉(zhuǎn)入步驟（4）；

（9）建立一個(gè)空的葉節(jié)點(diǎn)集作為非葉節(jié)點(diǎn)的子節(jié)點(diǎn)，則對(duì)該非葉節(jié)點(diǎn)的處理結(jié)束，轉(zhuǎn)入步驟（4）；

（10）取拓展樹的一個(gè)葉節(jié)點(diǎn)，對(duì)樹的這個(gè)葉節(jié)點(diǎn)進(jìn)行向根節(jié)點(diǎn)方向回溯，直到遇到第一個(gè)非停用詞節(jié)點(diǎn)時(shí)停止，則從根節(jié)點(diǎn)開頭到這個(gè)非停用詞節(jié)點(diǎn)結(jié)尾的單詞組合稱為一個(gè)待測關(guān)鍵詞，轉(zhuǎn)入步驟（11）；

（11）取拓展樹的一個(gè)其他不同于步驟（10）中的葉節(jié)點(diǎn)，重復(fù)步驟（10）的操作直至所有葉節(jié)點(diǎn)都被處理完，則轉(zhuǎn)入步驟（12）；

（12）輸出具有頻數(shù)和位置信息的候選關(guān)鍵詞集。

筆者用一個(gè)簡單例子解釋其具體運(yùn)算，隨意抽取一篇西文科技文獻(xiàn)的一個(gè)關(guān)鍵單詞candidate在文章中每次出現(xiàn)的位置，具體每次出現(xiàn)的片段是:①The first step is called candidate phrase identification or its generation；②Some candidate phrase identification methods were proposed in previous works；③Unsupervised approaches usually involve assigning a saliency score to each candidate phrase by considering various features；④We argue that distinguishing strong candidates from weak ones should not only rely on feature engineering［11］。由于一個(gè)關(guān)鍵單詞的每次出現(xiàn)都會(huì)伴隨著一個(gè)以它開頭的單詞序列，根據(jù)上述算法的相關(guān)設(shè)置，可知這個(gè)單詞序列的最大長度為4，因此只需要從該關(guān)鍵單詞開始向后依次再取出3個(gè)單詞，即candidate phrase indentification or、candidate phrase indentification methods、candidate phrase by considering 和candidates from weak ones。

為了簡化書寫和便于理解，用不同字母和符號(hào)代替不同單詞及其在文本中的位置，用‖代表詞邊界，則預(yù)處理后的簡化形式和拓展樹如圖2和圖3所示。

圖2 預(yù)處理后簡化圖

圖3 關(guān)鍵單詞candidate的前拓展樹

根據(jù)圖3的前拓展樹及其算法過程的步驟（10）可知，由candidate產(chǎn)生的候選關(guān)鍵詞為cd和d，即還原為 candidate phrase和 candidate。再來分析前拓展樹，由關(guān)鍵單詞開頭的每個(gè)單詞序列相當(dāng)于拓展樹的一個(gè)枝干，用數(shù)學(xué)語言更準(zhǔn)確地說，如果用集合P代表關(guān)鍵單詞每次出現(xiàn)的位置，集合S代表所有不同的以關(guān)鍵單詞開頭的所有單詞序列，集合B代表樹的所有枝干，則函數(shù)f:P→S為滿射，函數(shù)g:S→B為雙射。結(jié)合算法可得出樹的每條枝干最多形成一個(gè)候選關(guān)鍵詞，換句話說就是關(guān)鍵單詞的每次出現(xiàn)最多產(chǎn)生一個(gè)候選關(guān)鍵詞。再回到該例子，candidate的第一次、第二次和第三次出現(xiàn)都產(chǎn)生了candidate phrase，第四次出現(xiàn)產(chǎn)生了candidate，也完全符合以上的分析，對(duì)于第一次、第二次和第三次產(chǎn)生的候選關(guān)鍵詞只取一次就行了。

后拓展樹算法與上述算法十分相似，只需稍做改變，首先將步驟（5）中的下一個(gè)位置改為上一個(gè)位置，再對(duì)步驟（10）中的操作進(jìn)行反序操作，即從非停用詞節(jié)點(diǎn)到根節(jié)點(diǎn)取候選關(guān)鍵詞。其實(shí)驗(yàn)結(jié)論與前拓展樹是一樣的。

隨后筆者再次通過輸入2～6個(gè)關(guān)鍵詞自動(dòng)選取了100篇科技類文章，隨機(jī)抽取每篇文章中的2個(gè)關(guān)鍵單詞進(jìn)行前后拓展樹算法，并畫出拓展樹圖，記錄對(duì)應(yīng)產(chǎn)生的潛在候選關(guān)鍵詞。實(shí)驗(yàn)結(jié)果表明，關(guān)鍵單詞的每次出現(xiàn)仍然都最多可產(chǎn)生兩個(gè)潛在候選關(guān)鍵詞，前后拓展樹分別產(chǎn)生一個(gè)。這里所說潛在候選關(guān)鍵詞是因?yàn)橛行﹩卧~序列組合可能無意義，形成后還要再次進(jìn)行篩選。

3 前后拓展樹算法與N-Gram法的比較

傳統(tǒng)的基于N-Gram法形成潛在候選關(guān)鍵詞的方法在先前的許多研究中都被采用了［12］，其過程簡單描述如下:首先，根據(jù)詞邊界將輸入文本分解；其次，將長度在一定范圍內(nèi)的詞序列和其子序列抽取出來當(dāng)做初步的候選關(guān)鍵詞集；最后，設(shè)置一些法則來過濾掉無意義的詞序，例如候選關(guān)鍵詞不能以停用詞開頭或結(jié)尾。在后來的標(biāo)引系統(tǒng)中N-Gram法得到更進(jìn)一步的改善和提高［13－14］，如將候選關(guān)鍵詞的最大長度設(shè)置為4，則所有小于或等于4的N-Gram都可能稱為候選關(guān)鍵詞。具體到某個(gè)關(guān)鍵單詞，不妨記為Wp，其中p為在文本中出現(xiàn)的位置，則所有的候選詞將出現(xiàn)在單詞序列 Wp－3Wp－2Wp－1WpWp+1Wp+2Wp+3中，其包含關(guān)鍵單詞Wp本身，以及所有的2-Gram、3-Gram和4-Gram，再排除不含關(guān)鍵單詞或包含在內(nèi)部的詞序列，這樣就可將基于N-Gram法產(chǎn)生的所有候選關(guān)鍵詞列于表1中。

表1 由關(guān)鍵單詞產(chǎn)生的潛在候選關(guān)鍵詞

由表1可知，通過N-Gram法對(duì)于關(guān)鍵單詞的每次出現(xiàn)產(chǎn)生潛在候選關(guān)鍵詞的最大數(shù)目為7個(gè)，然而這7個(gè)中的一些潛在關(guān)鍵詞有可能是無意義的，一些系統(tǒng)都有相應(yīng)的過濾操作將其過濾，但是由這種方法產(chǎn)生的候選關(guān)鍵詞集仍然較大。而采用上述關(guān)鍵單詞前后拓展樹算法，關(guān)鍵單詞的每次出現(xiàn)最多產(chǎn)生兩個(gè)候選關(guān)鍵詞，因此可推算該算法將通常的N-Gram法產(chǎn)生的候選關(guān)鍵詞減少1/2以上。

4 結(jié)論

所提出的方法只需要將每個(gè)關(guān)鍵單詞前后拓展，其中拓展樹的深度設(shè)置為4，過濾臨界值設(shè)置為3，這樣就可得到一個(gè)相對(duì)較小的候選關(guān)鍵詞集以便于后面的操作。但是還要考慮該算法的時(shí)間復(fù)雜性，由于拓展樹的時(shí)間復(fù)雜性等同于深度優(yōu)先策略（即O（n））的復(fù)雜性，而深度優(yōu)先策略與其他抽取系統(tǒng)的復(fù)雜性是相似的。由此可以表明，該算法是在沒有增加計(jì)算難度的同時(shí)達(dá)到了減小候選關(guān)鍵詞集的效果。

［1］蘇新寧.信息檢索理論與技術(shù)［M］.北京:科學(xué)技術(shù)文獻(xiàn)出版社，2004:208－210.

［2］劉華.關(guān)鍵詞自動(dòng)標(biāo)引系統(tǒng)實(shí)現(xiàn)［J］.現(xiàn)代圖書情報(bào)技術(shù)，2006（2）:88－90.

［3］KUMAR N，SRINATHAN K.Automatic keyphrase extraction from scientific documents using N-gram filtration technique［C］∥Proceedings of the 8th ACM Symposium on Document Engineering.Sao Paulo:［s.n.］，2008:199－208.

［4］HULTH A.Improved automatic keyword extraction given more linguistic knowledge［C］∥Proceedings of the 2003 Conference on Emprical Methods in Natural Language Processing.Sapporo:［s.n.］，2003:216 －223.

［5］BEREND G，F(xiàn)ARKAS R.SZTERGAK:feature engineering for keyphrase extraction［C］∥Proceeding of the 5th International Workshop on Semantic Evaluation.Uppsala:［s.n.］，2010:186 －189.

［6］TURNEY P D.Coherent keyphrase extraction via web mining［C］∥ Proceedings of the 20th International Joint Conference on Artificial Intelligence.Acapulco:［s.n.］，2003:434 －439.

［7］HULTH A，MEGYESI B.A study on automatically extracted keywords in text categorization［C］∥Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics.Sydney:［s.n.］，2006:124－154.

［8］PORTER M F.An algorithm for suffix stipping［J］.Program，1980，14（3）:130 －137.

［9］FRANK E，PAYNTER G W，WITTEN I H.Domainspecific keyphrase extraction［C］∥Proceedings of the 16th International Joint Conference on Aritifical Intelliegence.Stockholm:Morgan Kaufmann，1999:668 －673.

［10］EL－BELTAGY S R，RAFEA A.KP-miner:a key phrase extraction system for english and arabic documents［J］.Inf Syst，2009，34（1）:132 － 144.

［11］WEI Y，DOMINIQUE F，JEAN-PAUL B.An automatic key phrase extraction system for scientific documents［J］.Knowl Inf Syst，2013（34）:691 － 724.

［12］TURNEY P D.Learning algorithms for key phrase extraction［J］.Inf Retrieval，2000，2（4）:303 －336.

［13］HUANG C，TIAN Y，ZHOU Z，et al.Key phrase extraction using semantic networks structure analysis［C］∥Proceedings of the 6th International Conference on Data Mining.Hong Kong:［s.n.］，2006:275 －284.

［14］WAN C H，ZHANG M，RU L Y，et al.An automatic online news topic key phrase extraction system［C］∥Proceedings of 2008 IEEE/WIC/ACM International Conference on Web Intelligence.Sydney:［s.n.］，2008:214－219.