一種新的生成候選關鍵詞集的方法

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

（1.武漢理工大學理學院，湖北 武漢 430070；2.武漢理工大學計算機科學與技術學院，湖北 武漢 430070）

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

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

1 關鍵單詞集

1.1 關鍵單詞與關鍵詞的關系

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

通過輸入2～10個關鍵詞自動抽取出400篇科技相關論文，實驗前一般要對輸入計算機的文本進行預處理。設k為關鍵單詞的個數，a為以關鍵單詞開頭或結尾的關鍵詞在所有已知關鍵詞中的比例，b為所有關鍵單詞的頻數在預處理后文本中占據的比例。通過改變k的值，計算分析a和b值的變化情況。其分析結果如圖1所示。

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

圖1 關鍵詞數目與其對關鍵詞抽取的覆蓋能力比較

1.2 關鍵單詞集的獲取

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

2 關鍵詞的形成算法

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

（1）輸入已預處理過的文件及其關鍵單詞集Mkw；

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

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

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

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

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

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

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

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

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

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

（12）輸出具有頻數和位置信息的候選關鍵詞集。

筆者用一個簡單例子解釋其具體運算，隨意抽取一篇西文科技文獻的一個關鍵單詞candidate在文章中每次出現的位置，具體每次出現的片段是:①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］。由于一個關鍵單詞的每次出現都會伴隨著一個以它開頭的單詞序列，根據上述算法的相關設置，可知這個單詞序列的最大長度為4，因此只需要從該關鍵單詞開始向后依次再取出3個單詞，即candidate phrase indentification or、candidate phrase indentification methods、candidate phrase by considering 和candidates from weak ones。

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

圖2 預處理后簡化圖

圖3 關鍵單詞candidate的前拓展樹

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

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

隨后筆者再次通過輸入2～6個關鍵詞自動選取了100篇科技類文章，隨機抽取每篇文章中的2個關鍵單詞進行前后拓展樹算法，并畫出拓展樹圖，記錄對應產生的潛在候選關鍵詞。實驗結果表明，關鍵單詞的每次出現仍然都最多可產生兩個潛在候選關鍵詞，前后拓展樹分別產生一個。這里所說潛在候選關鍵詞是因為有些單詞序列組合可能無意義，形成后還要再次進行篩選。

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

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

表1 由關鍵單詞產生的潛在候選關鍵詞

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

4 結論

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

［1］蘇新寧.信息檢索理論與技術［M］.北京:科學技術文獻出版社，2004:208－210.

［2］劉華.關鍵詞自動標引系統(tǒng)實現［J］.現代圖書情報技術，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，FARKAS 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.