自動(dòng)分類技術(shù)研究

摘要：自動(dòng)分類技術(shù)已成為文檔信息分類的主導(dǎo)關(guān)鍵技術(shù)，針對(duì)技術(shù)的發(fā)展現(xiàn)狀，歸納自動(dòng)分類技術(shù)的類型及歸類方法，以及對(duì)未來(lái)發(fā)展的展望。

關(guān)鍵詞：自動(dòng)分類；現(xiàn)狀；類型；文檔分類；方法

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2009)04-1020-02

自動(dòng)分類技術(shù)是利用計(jì)算機(jī)系統(tǒng)對(duì)文本集按照一定的分類體系或標(biāo)準(zhǔn)進(jìn)行自動(dòng)類別標(biāo)記，分類工具根據(jù)文檔的信息將其分配到已經(jīng)存在的類別中，也稱“主題”。

隨著網(wǎng)絡(luò)的迅猛發(fā)展，網(wǎng)頁(yè)、電子郵件、數(shù)據(jù)庫(kù)、聊天室和數(shù)字圖書(shū)館等電子文本成幾何級(jí)數(shù)不斷增長(zhǎng)，處理這些海量數(shù)據(jù)的一個(gè)重要方法就是將它們分類。當(dāng)我們?yōu)g覽一個(gè)網(wǎng)站查找信息時(shí)，如果網(wǎng)頁(yè)凌亂的堆積在一起沒(méi)有類別供我們查找，會(huì)使我們很難找到自己所需的信息。現(xiàn)在，大型網(wǎng)站都將網(wǎng)頁(yè)分類，以方便人們?yōu)g覽。比如，Yahoo就將網(wǎng)頁(yè)放在一個(gè)巨大的層次分類結(jié)構(gòu)中，通過(guò)組裝維護(hù)這些類別，可以幫助人們查找知識(shí)和信息。網(wǎng)頁(yè)自身并沒(méi)有類型區(qū)分，這就需要人工分類，將網(wǎng)頁(yè)、郵件等各種格式的文檔經(jīng)過(guò)文法分析都可以轉(zhuǎn)化為純文本，而自動(dòng)文本分類系統(tǒng)可以幫助人們檢查文本、判斷文本所屬類別。

1 自動(dòng)分類技術(shù)的現(xiàn)狀

到目前為止，國(guó)外已在自動(dòng)分類領(lǐng)域進(jìn)行了較為深入的研究。已經(jīng)從最初的可行性基礎(chǔ)研究經(jīng)歷了實(shí)驗(yàn)性研究進(jìn)入實(shí)用階段，并在郵件分類、電子會(huì)議、信息過(guò)濾等方面取得了較為廣泛的應(yīng)用[1]。

國(guó)內(nèi)對(duì)自動(dòng)分類技術(shù)的研究相對(duì)較晚。1986年，上海交通大學(xué)電腦應(yīng)用技術(shù)研究所開(kāi)發(fā)的中文科技文獻(xiàn)（計(jì)算機(jī)類）實(shí)驗(yàn)性分類系統(tǒng)。1995年，清華大學(xué)電子工程系研制的漢語(yǔ)語(yǔ)料自動(dòng)分類系統(tǒng)。1998年，東北大學(xué)計(jì)算機(jī)系的新聞?wù)Z料漢語(yǔ)文本自動(dòng)分類模型。1999年，由鄒濤等人開(kāi)發(fā)的中文技術(shù)文本分類系統(tǒng)CTDS。除此之外，國(guó)內(nèi)眾多學(xué)者對(duì)中文文本分類算法也進(jìn)行了深入研究，黃萱箐等提出的基于機(jī)器學(xué)習(xí)的、獨(dú)立于語(yǔ)種的文本分類模型[3]，周永庚等研究的隱含語(yǔ)義索引在中文文本處理中的應(yīng)用[4]，李榮陸等的最大熵模型[5]，張劍等提出的一種以WordNet語(yǔ)言本體庫(kù)為基礎(chǔ)，建立文本的概念向量空間模型作為文本特征向量的特征提取方法[6]，朱靖波等將領(lǐng)域知識(shí)引入文本分類，利用領(lǐng)域知識(shí)作為文本特征，提出一種基于知識(shí)的文本分類方法等[7]。

從20世紀(jì)90年代以來(lái)，基于機(jī)器學(xué)習(xí)的文本分類逐漸成為文本分類的主流技術(shù)。近年來(lái)文本分類技術(shù)取得了很大的進(jìn)展，提出了多種特征抽取方法和分類方法，如回歸模型、支持向量機(jī)、最大熵模型等，建立了OHSUMED，Reuters等開(kāi)放的分類語(yǔ)料庫(kù)。

2 自動(dòng)分類技術(shù)的類型

根據(jù)目的性，信息自動(dòng)分類包括自動(dòng)聚類和自動(dòng)歸類兩種類型。

2.1 自動(dòng)聚類

由計(jì)算機(jī)系統(tǒng)對(duì)待分類文本進(jìn)行分析并提取有關(guān)的特征，然后對(duì)提取的特征進(jìn)行比較，根據(jù)一定規(guī)則將具有相同或相近特征的對(duì)象定義為一類。自動(dòng)聚類的目的是在已有信息中定義符合實(shí)際情況的類。在網(wǎng)站的非主要分類體系中，也可以用自動(dòng)聚類的方法自動(dòng)生成欄目?jī)?nèi)的類別。

2.2 自動(dòng)歸類

計(jì)算機(jī)系統(tǒng)對(duì)分類文本提取有關(guān)特征，然后與既定分類系統(tǒng)中對(duì)象所具有的公共特征進(jìn)行相關(guān)性比較。將對(duì)象歸入其特征最相近的類中。自動(dòng)歸類的目的是把各種信息納入已建立的分類系統(tǒng)中，用于搜索引擎或網(wǎng)站導(dǎo)航系統(tǒng)的管理和數(shù)據(jù)更新。根據(jù)使用的技術(shù)，自動(dòng)歸類通常分為基于詞的自動(dòng)分類（詞典法）和基于專家系統(tǒng)的自動(dòng)分類（知識(shí)法）兩大類，也有人將界于兩種技術(shù)之間的稱為基于信息的自動(dòng)分類。

3 文檔分類關(guān)鍵技術(shù)分類及方法

現(xiàn)有的文本分類技術(shù)主要采用3 種方法:基于連接的方法、基于規(guī)則的方法和基于統(tǒng)計(jì)的方法。

3.1 基于連接的文本分類方法

基于連接的方法主要是利用人工神經(jīng)網(wǎng)絡(luò)來(lái)模擬人腦神經(jīng)網(wǎng)絡(luò)，并期望其能像大腦一樣地運(yùn)作，一樣地學(xué)習(xí)，從而產(chǎn)生智慧。這種方法可以實(shí)現(xiàn)信息的分布存取，運(yùn)算的全局并行，并且可在進(jìn)行非線性處理的同時(shí)具有高容錯(cuò)性等特點(diǎn)，適用于學(xué)習(xí)一個(gè)復(fù)雜的非線性映射。但是使用他學(xué)習(xí)所形成的知識(shí)結(jié)構(gòu)是人所難以理解的，系統(tǒng)本身也不具有良好的透明性。

3.2 基于規(guī)則的文本分類方法

基于規(guī)則的方法本質(zhì)上是一種確定性的演繹推理方法。其優(yōu)點(diǎn)在于他能根據(jù)上下文對(duì)確定性事件進(jìn)行定性描述，并且能充分利用現(xiàn)有的語(yǔ)言學(xué)成果。其成立的前提是有大量的知識(shí)，而這些知識(shí)必須是人類專家總結(jié)出來(lái)的。由于必須有人的參與，這種方法側(cè)重于知識(shí)的可理解性和可讀性，對(duì)于有些統(tǒng)計(jì)方法無(wú)法解決的問(wèn)題，利用基于規(guī)則的方法可以很容易地解決。但是，這種方法在不確定性事件的描述、規(guī)則之間的相容性等方面存在一些缺陷和限制。常用的基于規(guī)則的方法有決策樹(shù)、關(guān)聯(lián)規(guī)則等。

3.3 基于統(tǒng)計(jì)的文本分類方法

基于統(tǒng)計(jì)的方法本質(zhì)上是一種非確定性的定量推理方法。基于統(tǒng)計(jì)的方法的優(yōu)勢(shì)在于他的全部知識(shí)是通過(guò)對(duì)大規(guī)模語(yǔ)料庫(kù)分析得到的，可以取得很好的一致性和非常高的覆蓋率，對(duì)語(yǔ)言處理提供了比較客觀的數(shù)據(jù)依據(jù)和可靠的質(zhì)量保證。但由于其是基于概率的一種方法，因此必然會(huì)對(duì)小類別文本即小概率事件造成忽視。常用的基于統(tǒng)計(jì)的方法有KNN、樸素貝葉斯、類中心向量、回歸模型、支持向量機(jī)、最大熵模型等。

3.4 經(jīng)典文本分類方法

3.4.1 KNN算法

KNN算法即k- Nearest Neighbor 分類方法，是一種穩(wěn)定而有效的文本分類方法。采用KNN 方法進(jìn)行文檔分類的過(guò)程如下：對(duì)于某一給定的測(cè)試文檔d，在訓(xùn)練集中，通過(guò)相似度找到與之最相似的k個(gè)訓(xùn)練文檔。在此基礎(chǔ)上，給每個(gè)文檔類打分，分值為k個(gè)訓(xùn)練文檔中屬于該類的文檔與測(cè)試文檔之間的相似度之和。也就是說(shuō)， 如果在這k個(gè)文檔中，有多個(gè)文檔屬于一個(gè)類，則該類的分值為這些文檔與測(cè)試文檔之間的相似度之和。對(duì)這k個(gè)文檔所屬類的分值統(tǒng)計(jì)完畢后，即按分值進(jìn)行排序。還應(yīng)當(dāng)選定一個(gè)閾值，只有分值超過(guò)閾值的類才予考慮。測(cè)試文檔屬于超過(guò)閾值的所有類。形式化表示為:

■（1）

其中，dj∈ci時(shí)y(dj，ci)=1；dj?埸c(diǎn)i時(shí)y(dj，ci) 。

bi為閾值，Sim(d，dj)為文檔d和dj的相似度，score(d，ci)為測(cè)試文檔d屬于ci類的分值。一般的，bi是一個(gè)有待優(yōu)化的值可以通過(guò)一個(gè)驗(yàn)證文檔集來(lái)進(jìn)行調(diào)整。驗(yàn)證文檔集是訓(xùn)練文檔集的一部分，根據(jù)公式(1)可確定測(cè)試文檔的類別。很顯然，對(duì)于每一個(gè)測(cè)試文檔，必須求解其和訓(xùn)練文檔庫(kù)中所有文檔的相似度。因此， KNN方法的時(shí)間復(fù)雜度為o(|D|ni)。其中，|D|和ni分別為訓(xùn)練文檔總數(shù)和測(cè)試文檔總數(shù)。

3.4.2 SVM

支持向量機(jī)（Support Vector Machine，SVM）是在統(tǒng)計(jì)學(xué)習(xí)理的基礎(chǔ)上發(fā)展而來(lái)的一種機(jī)器學(xué)習(xí)方法， 該模型是基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理的方法，把原始數(shù)據(jù)集合壓縮為支持向量集合，其基本思想是構(gòu)造出一個(gè)超平面作為決策平面，使正負(fù)模式之間的空白為最大化。在解決小樣本、非線性及高維模式識(shí)別問(wèn)題中SVM表現(xiàn)出了許多特有的優(yōu)勢(shì)， 并在很大領(lǐng)域得到了成功的應(yīng)用，如：人臉識(shí)別、手寫(xiě)字體識(shí)別、文本分類等。其中，SVM在文本分類方面的表現(xiàn)尤為突出。

SVM 的基本思想可用圖1的兩維情況進(jìn)行說(shuō)明。圖1中，圓形實(shí)心點(diǎn)和菱形實(shí)心點(diǎn)代表2類樣本，H為分類線，H1，H2分別為過(guò)各類中離分類線最近的樣本且平行于分類線的直線，他們之間的距離叫做分類間隔。所謂最優(yōu)分類線就是要求分類線不但能將兩類正確分開(kāi)(訓(xùn)練錯(cuò)誤率為0)，而且使分類間隔最大。分類線方程為：

x·w+b=0

在此可以對(duì)他進(jìn)行歸一化，使得對(duì)線性可分的樣本集：

(xi，yi)，i=1，…，n，x∈R4，y∈{+1，-1}

滿足：yi[(w.xi)+b]-1≥0 i=1，2，…n

此時(shí)分類間隔等于2/‖w‖， 使間隔最大等價(jià)于使‖w‖2最小。滿足式且使間距為‖w‖/2的分類面就叫做最優(yōu)分類面， H1 ， H2上的訓(xùn)練樣本點(diǎn)就稱作支持向量。

基本的SVM是針對(duì)兩類分類問(wèn)題的，為了實(shí)現(xiàn)對(duì)多個(gè)類別的識(shí)別，需要對(duì)SVM進(jìn)行擴(kuò)展。常用的SVM多類分類方法有One-vs-Res， One-vs-One，ECOC( Error Correcting Output Coding)、DAGSVM和二叉樹(shù)等方法。實(shí)驗(yàn)結(jié)果表明DAGSVM 方法要優(yōu)于其他2 種方法。Weston和Watkins[2]對(duì)SVM的理論進(jìn)行了擴(kuò)充，使其一次就可以完成多類分類，但是實(shí)驗(yàn)結(jié)果顯示其分類查準(zhǔn)率要低于One-vs-Rest 和One-vs-One方法。

4 技術(shù)的發(fā)展趨勢(shì)與展望

本文介紹了文本分類的研究背景，國(guó)內(nèi)外關(guān)于文本分類技術(shù)研究的最新動(dòng)態(tài)，總結(jié)了近年來(lái)文本分類研究的關(guān)鍵技術(shù)。文本分類技術(shù)有著廣泛的應(yīng)用，逐漸趨于實(shí)用。

但隨著自動(dòng)分類技術(shù)相關(guān)應(yīng)用的發(fā)展，及對(duì)其需求的不斷提升，文本分類技術(shù)仍有非常多的問(wèn)題值得研究：可靠、有效及快速的在線分類；基于語(yǔ)義度量的數(shù)據(jù)模型和分類方法；緩解樣本標(biāo)注瓶頸以及樣本數(shù)據(jù)分布帶來(lái)的影響等。隨著數(shù)據(jù)挖掘領(lǐng)域和機(jī)器學(xué)習(xí)理論、技術(shù)研究的不斷深入， 針對(duì)解決不同實(shí)際應(yīng)用和數(shù)據(jù)特征的問(wèn)題將成為文本分類相關(guān)研究，及其應(yīng)用的主要突破方向和攻克難點(diǎn)。

參考文獻(xiàn)：

[1] 李榮陸.文本分類及相關(guān)技術(shù)研究[D].上海:復(fù)旦大學(xué)，2005.

[2] 李應(yīng)紅.慰詢楷. 劉建勛.支持向量機(jī)的工程應(yīng)用[M].北京:兵器工業(yè)出版社，2004.

[3] 黃萱菁，吳立德，石崎洋之，等. 獨(dú)立于語(yǔ)種的文本分類方法[J].中文信息學(xué)報(bào)，2000，14(6):1-7.

[4] 周水庚，關(guān)佶紅，胡運(yùn)發(fā). 隱含語(yǔ)義索引及其在中文文本處理中的應(yīng)用研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2001，22(2):239-244.

[5] 李榮陸，王建會(huì)，陳曉云，胡運(yùn)發(fā)等. 使用最大熵模型進(jìn)行中文文本分類[J].計(jì)算機(jī)研究與發(fā)展.2005，42(1):94-101.

[6] 張劍，李春平. 基于WordNet概念空間模型的文本分類[J].計(jì)算機(jī)工程與應(yīng)用.2006(4):174-178.

[7] 朱靖波，陳文亮. 基于領(lǐng)域知識(shí)的文本分類[J].東北大學(xué)學(xué)報(bào)，2005，26(8):733-736.

畢靜，女，陜西漢中人，助理講師，工作于漢中市農(nóng)業(yè)干部學(xué)校，主要從事于計(jì)算機(jī)科學(xué)應(yīng)用的研究。