文本自動(dòng)分類中的動(dòng)態(tài)類別擴(kuò)展研究

摘要：提出基于粗糙集理論的動(dòng)態(tài)類別擴(kuò)展算法，可以根據(jù)新文獻(xiàn)與已有訓(xùn)練規(guī)則的匹配程度，有效地進(jìn)行新類別的自動(dòng)擴(kuò)展和新分類規(guī)則的自動(dòng)生成，從而屏蔽訓(xùn)練集和分類規(guī)則的更新等問題。

關(guān)鍵詞：文本自動(dòng)分類；粗糙集；動(dòng)態(tài)類別擴(kuò)展

中圖分類號(hào)：TP391．1文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2007)05－0074－03

文本自動(dòng)分類是指在給定的分類體系下，根據(jù)文獻(xiàn)的內(nèi)容自動(dòng)判別文獻(xiàn)類別的過程[1~3]。文本自動(dòng)分類采用分類思想組織文獻(xiàn)，不僅符合人們的思維習(xí)慣和應(yīng)用習(xí)慣，而且需求資源較少，操作簡(jiǎn)單，能夠適應(yīng)大規(guī)模文本處理的要求。20世紀(jì)90年代以來，機(jī)器學(xué)習(xí)方法已經(jīng)廣泛應(yīng)用于文本自動(dòng)分類研究。基于機(jī)器學(xué)習(xí)的文本自動(dòng)分類已成為當(dāng)前機(jī)器學(xué)習(xí)、信息檢索和自然語言處理領(lǐng)域最活躍的研究主題之一。

基于機(jī)器學(xué)習(xí)的文本自動(dòng)分類包括兩個(gè)基本過程，即分類知識(shí)訓(xùn)練和新文獻(xiàn)分類預(yù)測(cè)。分類知識(shí)訓(xùn)練是指應(yīng)用分類算法從一個(gè)包含一定數(shù)量的已經(jīng)進(jìn)行分類標(biāo)記的文獻(xiàn)集合（即訓(xùn)練集）中獲得分類知識(shí)；新文獻(xiàn)分類預(yù)測(cè)則是運(yùn)用訓(xùn)練得到的分類知識(shí)對(duì)訓(xùn)練集之外的文獻(xiàn)進(jìn)行分類預(yù)測(cè)。

在文本自動(dòng)分類中，訓(xùn)練集是相對(duì)固定的，一般不可能代表所有新文獻(xiàn)包含的主題。隨著系統(tǒng)中新文獻(xiàn)的不斷加入，原來訓(xùn)練得到的分類知識(shí)對(duì)新文獻(xiàn)的分類預(yù)測(cè)能力會(huì)變得越來越低。人們一般采取定期或不定期更新訓(xùn)練集，再重新訓(xùn)練分類器的方法來解決這一問題。但是，這種方法不僅會(huì)增加訓(xùn)練時(shí)間，而且會(huì)造成分類知識(shí)的不一致性，從而導(dǎo)致整個(gè)分類系統(tǒng)中文獻(xiàn)分類結(jié)果不一致，影響系統(tǒng)的檢索性能。

粗糙集理論產(chǎn)生于1982年，是一種處理知識(shí)模糊性和不確定性的數(shù)學(xué)工具。到目前為止，粗糙集理論已經(jīng)廣泛應(yīng)用于股票分析、地震預(yù)報(bào)、知識(shí)發(fā)現(xiàn)、醫(yī)療診斷、過程控制和圖像處理等領(lǐng)域。其基本思想是在保持分類能力不變的前提下，通過知識(shí)約簡(jiǎn)，導(dǎo)出分類規(guī)則。在分類任務(wù)中，粗糙集方法不需要先驗(yàn)知識(shí)，能夠以較低的計(jì)算時(shí)間推導(dǎo)出易于理解和驗(yàn)證的分類規(guī)則。粗糙集理論從知識(shí)分類的角度來研究對(duì)象之間和概念之間的關(guān)系，與文本自動(dòng)分類原理非常吻合。因此，近來年，基于粗糙集理論的文本自動(dòng)分類研究受到越來越多的關(guān)注。研究表明，基于粗糙集理論的文本自動(dòng)分類方法具有較好的發(fā)展前景，還有待進(jìn)一步的深入研究與推廣應(yīng)用[4~8]。

1粗糙集基本理論

根據(jù)粗糙集理論及其屬性約簡(jiǎn)算法，可以有效地推導(dǎo)出用于文本自動(dòng)分類的分類規(guī)則。但是，在分類規(guī)則應(yīng)用于新文獻(xiàn)的分類預(yù)測(cè)過程中，隨著新文獻(xiàn)的不斷加入，分類規(guī)則與新文獻(xiàn)主題的不匹配矛盾會(huì)變得越來越突出。近似分類規(guī)則和匹配方法的改進(jìn)不能從根本上解決這個(gè)問題。另外，它們會(huì)導(dǎo)致分類的準(zhǔn)確率降低，以及分類準(zhǔn)確性不可預(yù)測(cè)性提高。例如下面兩種情況：①如果新文獻(xiàn)在分類規(guī)則中能夠找到至少一條的匹配規(guī)則，但是匹配相關(guān)值較小，那么分類預(yù)測(cè)結(jié)果的正確率就會(huì)受到較大的影響；②如果新文獻(xiàn)在分類規(guī)則中根本找不到匹配規(guī)則，那么文獻(xiàn)類別就變得不可預(yù)測(cè)。最常用的辦法是將其歸為出現(xiàn)頻率較高的類別。很顯然，這種方法不能保證預(yù)測(cè)的準(zhǔn)確性。需要指出的是，本文不討論基于粗糙集理論的分類規(guī)則推導(dǎo)算法，具體研究是在假設(shè)分類規(guī)則已經(jīng)推導(dǎo)出的情況下。有關(guān)基于粗糙集理論的規(guī)則推導(dǎo)算法請(qǐng)參考文獻(xiàn)[10]。

2動(dòng)態(tài)類別擴(kuò)展算法

與平面分類法相比，層次體系結(jié)構(gòu)分類法的類別自動(dòng)擴(kuò)展相對(duì)比較復(fù)雜。事實(shí)上，平面分類法可以看做是層次體系結(jié)構(gòu)分類法的一種特例。因此，重點(diǎn)討論層次體系結(jié)構(gòu)分類法的類別自動(dòng)擴(kuò)展問題。

層次體系分類法的類別分布呈樹狀結(jié)構(gòu)。其中每個(gè)類別都可以看做是樹上的一個(gè)節(jié)點(diǎn)，每個(gè)類別的上位類是其代表節(jié)點(diǎn)的父節(jié)點(diǎn)，下位類是其代表節(jié)點(diǎn)的子節(jié)點(diǎn)，同位類是指代表節(jié)點(diǎn)的兄弟節(jié)點(diǎn)。

實(shí)驗(yàn)數(shù)據(jù)集（CWT）由北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室提供，包括15 605個(gè)網(wǎng)頁文本。該數(shù)據(jù)集主要用于測(cè)試網(wǎng)頁自動(dòng)分類方法的性能。表1描述了該數(shù)據(jù)集的訓(xùn)練集和測(cè)試集的劃分情況。圖1描述了CWT數(shù)據(jù)集的層次體系結(jié)構(gòu)。

對(duì)于層次體系分類法，類別自動(dòng)擴(kuò)展算法主要解決兩個(gè)問題：①建立創(chuàng)建新類別的標(biāo)準(zhǔn)，即判斷在分類系統(tǒng)應(yīng)用過程中，什么狀態(tài)下可以創(chuàng)建新類別；②如何確定新類別的位置。

本文定義，當(dāng)一篇新文獻(xiàn)在進(jìn)行分類預(yù)測(cè)時(shí)，它與所有類別的匹配度均小于系統(tǒng)規(guī)定閾值時(shí)，新類別就應(yīng)該自動(dòng)產(chǎn)生。類別擴(kuò)展可以分為橫向擴(kuò)展和縱向擴(kuò)展兩種類型。橫向擴(kuò)展是指增加某個(gè)類別的兄弟節(jié)點(diǎn)，縱向擴(kuò)展是指增加某個(gè)類別的子節(jié)點(diǎn)。

理論上，新類別的增加，容易引起子父節(jié)點(diǎn)之間隸屬關(guān)系的不一致性。增加新類別時(shí)要盡可能地減少子父節(jié)點(diǎn)之間的差異，而且不能影響同級(jí)路徑上其他節(jié)點(diǎn)與子父節(jié)點(diǎn)之間的關(guān)系。在提出具體的類別擴(kuò)展算法之前，先定義上近似邊界、下近似邊界和同位近似邊界三個(gè)概念。

輸入：新文獻(xiàn)及其關(guān)鍵詞

輸出：新類別和分類規(guī)則

計(jì)算新文獻(xiàn)與各類區(qū)別的匹配度 

搜索與新文獻(xiàn)匹配度最大的類別，即定位節(jié)點(diǎn)M

If搜索不到，則在一級(jí)類別中增加新類別//橫向擴(kuò)展

Else搜索與之匹配度最大的類別，其相似值定義為MATCH(M)

If MATCH(M)大于該類別的規(guī)定閾值，則該文獻(xiàn)歸至該類

Else計(jì)算MATCH(PM)，AVG(MATCH(CM)），AVG(MATCH(SM)），BND(D)，BND(D)和BND(D)

If BND(D)＞=BND(D)and BND(D)＞=BND(D)

增加一個(gè)M節(jié)點(diǎn)的子節(jié)點(diǎn)//縱向擴(kuò)展

Else

增加一個(gè)M節(jié)點(diǎn)的兄弟節(jié)點(diǎn)//橫向擴(kuò)展

Endif

Endif

Endif

Return新節(jié)點(diǎn)及其相對(duì)應(yīng)新分類規(guī)則

從上述算法可以看出，當(dāng)一篇文獻(xiàn)輸入后，根據(jù)判定條件，決定是否產(chǎn)生新類別。如果需要?jiǎng)?chuàng)建新類別，則必須同時(shí)為該類別生成分類規(guī)則。當(dāng)一篇文獻(xiàn)加入時(shí)，產(chǎn)生了新的類別，此時(shí)將該文獻(xiàn)的關(guān)鍵詞作為分類規(guī)則的條件屬性，而將該類別作為決策屬性，生成一條新的分類規(guī)則。之后，如果有新文獻(xiàn)加入該類別，需要根據(jù)每個(gè)新文獻(xiàn)的特征項(xiàng)，生成相應(yīng)的分類規(guī)則。

舉例：假設(shè)某篇新文獻(xiàn)D與類別0408的匹配度最大值為0.32，小于規(guī)定閾值0.41。在這種情況下，需要新增類別。其用于動(dòng)態(tài)類別擴(kuò)展算法幾種參數(shù)的計(jì)算過程和結(jié)果如表2所示。根據(jù)動(dòng)態(tài)類別擴(kuò)展算法，可以生成新類別節(jié)點(diǎn)，即一個(gè)0408的同位節(jié)點(diǎn)。

3實(shí)驗(yàn)性能評(píng)估

如何評(píng)估類別自動(dòng)擴(kuò)展算法的性能，目前可參考的相關(guān)文獻(xiàn)還較少。類別自動(dòng)擴(kuò)展算法的性能評(píng)估，主要包括兩個(gè)方面的工作：

(1)試驗(yàn)數(shù)據(jù)集的獲取。本文認(rèn)為，類別自動(dòng)擴(kuò)展方法的性能評(píng)估可以在用來文本自動(dòng)分類的數(shù)據(jù)集中進(jìn)行。具體實(shí)驗(yàn)方法如下：任意抽取其中一個(gè)類別作為測(cè)試對(duì)象。如果某個(gè)類別為非葉節(jié)點(diǎn)，則將該類別及其所有子孫節(jié)點(diǎn)的訓(xùn)練文獻(xiàn)和測(cè)試文獻(xiàn)分別進(jìn)行合并，產(chǎn)生新的訓(xùn)練文獻(xiàn)集合和測(cè)試文獻(xiàn)集合（圖1）。

本文共抽取了CWT中十個(gè)類別進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如表3所示。

從表3中可以看出，動(dòng)態(tài)類別擴(kuò)展算法是相當(dāng)有效的。從總體上看，級(jí)別越低的類別，擴(kuò)展位置出錯(cuò)的可能性越高，比較容易擴(kuò)展至上位類。這種可能性在很大程度上取決于實(shí)驗(yàn)數(shù)據(jù)集中上下類別文獻(xiàn)的相關(guān)性。例如，類別122205所有的測(cè)試文獻(xiàn)與其上位類1222都有較高的匹配度，因此根據(jù)本文制定的規(guī)則沒有產(chǎn)生新的擴(kuò)展類別。

4結(jié)束語

動(dòng)態(tài)類別擴(kuò)展方法旨在解決基于機(jī)器學(xué)習(xí)的文本自動(dòng)分類系統(tǒng)中訓(xùn)練集相對(duì)固定，而新主題文獻(xiàn)無法進(jìn)行正確分類預(yù)測(cè)的問題。隨著文本自動(dòng)分類技術(shù)的普及應(yīng)用，動(dòng)態(tài)類別擴(kuò)展將逐步發(fā)展成為解決這一難題的可行性技術(shù)。但是，到目前為止，該主題研究還沒有引起廣泛的關(guān)注。本文試圖作一些初步的探討，并提出一種基于粗糙集理論的動(dòng)態(tài)類別擴(kuò)展算法。實(shí)驗(yàn)表明，該算法不僅可以有效地自動(dòng)擴(kuò)展新類別，而且可以同時(shí)生成相應(yīng)的分類規(guī)則。但是，隨著大量新文獻(xiàn)加入新增的類別，分類規(guī)則也會(huì)急劇增加，分類規(guī)則會(huì)存在大量的冗余，從而導(dǎo)致分類速度和分類準(zhǔn)確性的降低。因此，下一步的研究工作將主要側(cè)重于分類規(guī)則的動(dòng)態(tài)優(yōu)化等問題。

參考文獻(xiàn)：

［1］

AAS K， EIKVIL L.Text categorization: a survey[R]. Norwegian: Norwegian Computer Center，1999.

[2]RUIZ M E R. Combining machine learning and hierarchical structures for text categorization[R]. Iowa:University of Iowa， 2001.

[3]SEBASTIANI F.A tutorial on automated text categorization:procee－dings of the 1st Argentinean Symposium on Artificial Intelligence[C].Varese:[s.n.]，1999.

[4]DAS G P.Rough sets and information retrieval:proceedings of the 11th ACM SIGIR International Conference on Research and Development in Information Retrieval[C].[S.l.]:[s.n.]，1988.

[5]SRINIVASAN P.Exploring the UMLs:A rough sets based theoretical framework:proceedings of the American Medical Informatics Association[C].[S.l.]:[s.n.]，1999.

[6]SRINIVASAN P， RUIZ M E， KRAFT D H，et al.Vocabulary mining for information retrieval: rough sets and fuzzy sets[J].Information Processing Management，2001，37(1):15－38.

[7]CHOUCHOULAS A. A rough set approach to text classification[D].[S.l.]:University of Edinburgh，1999.

[8]CHOUCHOULAS A.Incremental feature selection based on rough set theory[D].[S.l.]:University of Edinburgh，2001.

[9]張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法[M].北京：科學(xué)出版社，2001.

[10]PAWLAK Z.Rough sets:theoretical aspects of reasoning about data[M]. Boston: Kluwer Academic Publishers，1999.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”