搜索引擎中的文本分類(lèi)方法研究

摘要:文本分類(lèi)技術(shù)在搜索引擎中有很重要的用途，本文簡(jiǎn)要分析了文本分類(lèi)的評(píng)估方法，應(yīng)用于搜索引擎的分類(lèi)過(guò)程，重點(diǎn)介紹了現(xiàn)行的文本自動(dòng)分類(lèi)方法，包括經(jīng)典算法和新算法以及未來(lái)的發(fā)展趨勢(shì)。

關(guān)鍵詞：文本分類(lèi)；分類(lèi)器；準(zhǔn)確率

互聯(lián)網(wǎng)的出現(xiàn)，使得人類(lèi)全部的信息資源以前所未有的方式和程度在全球內(nèi)互聯(lián)互通，現(xiàn)在網(wǎng)上的信息紛繁蕪雜，還沒(méi)有一個(gè)統(tǒng)一的組織標(biāo)準(zhǔn)。在信息量如此豐富的網(wǎng)上查找自己感興趣的信息是當(dāng)務(wù)之急，搜索引擎就應(yīng)運(yùn)而生。即便如此搜索引擎搜索到的信息也是雜亂無(wú)章的，如果我們對(duì)網(wǎng)頁(yè)進(jìn)行分類(lèi)就會(huì)為我們提供很多方便。如果人工進(jìn)行分類(lèi)幾乎是不可 能的，如果能夠?qū)嵤┚W(wǎng)頁(yè)的自動(dòng)分類(lèi)，就可以實(shí)現(xiàn)網(wǎng)頁(yè)標(biāo)引和檢索的分類(lèi)主題一體化，搜索引擎就能夠兼有分類(lèi)瀏覽、檢索和關(guān)鍵詞檢索的優(yōu)點(diǎn);能夠深入到網(wǎng)頁(yè)層次，幫助用戶迅速的判斷返回的結(jié)果是否符合自己的檢索要求。

1評(píng)估方法

因?yàn)槲谋痉诸?lèi)從根本上說(shuō)是一個(gè)映射過(guò)程，所以評(píng)估文本分類(lèi)系統(tǒng)的標(biāo)志是映射的準(zhǔn)確程度和映射的速度。映射的速度取決于映射規(guī)則的復(fù)雜程度，而評(píng)估映射準(zhǔn)確程度的參照物是通過(guò)專(zhuān)家思考判斷后對(duì)文本的分類(lèi)結(jié)果(這里假設(shè)人工分類(lèi)完全正確并且排除個(gè)人思維差異的因素)，與人工分類(lèi)結(jié)果越相近，分類(lèi)的準(zhǔn)確程度就越高，這里隱含了評(píng)估文本分類(lèi)系統(tǒng)的兩個(gè)指標(biāo):準(zhǔn)確率和查全率，準(zhǔn)確率是所有判斷的文本中與人工分類(lèi)結(jié)果吻合的文本所占的比率。其數(shù)學(xué)公式表示如下：

查全率是人工分類(lèi)結(jié)果應(yīng)有的文本中分類(lèi)系統(tǒng)吻合的文本所占的比率，其數(shù)學(xué)公式表示如下:

準(zhǔn)確率和查全率反映了分類(lèi)質(zhì)量的兩個(gè)不同方面，兩者必須綜合考慮，不可偏廢，因此，存在一種新的評(píng)估指標(biāo)，F(xiàn)I測(cè)試值，其數(shù)學(xué)公式如下:

2文本分類(lèi)過(guò)程

從圖1可以看出，構(gòu)建一個(gè)分類(lèi)器的關(guān)鍵因素包括：預(yù)處理、訓(xùn)練集、特征選取算法、分類(lèi)算法和截尾算法等。

3 常用分類(lèi)算法

到目前為止產(chǎn)生了許多的文本自動(dòng)分類(lèi)方法，如中心向量法、樸素貝葉斯方法等等。在討論各種分類(lèi)方法之前，我們首先說(shuō)明本章用到的一些常用符號(hào)。

D= ｛｝表示將要被分類(lèi)的文本的特征向量；

c1，...ck表示這些文本可能的類(lèi)別；

T={d1，...dn}表示包含N個(gè)文本的訓(xùn)練集；

y1，...yn，表示這N個(gè)訓(xùn)練文本的類(lèi)別；

Nj表示訓(xùn)練集中類(lèi) 的樣本個(gè)數(shù)；

m表示訓(xùn)練集特征個(gè)數(shù)；

3.1中心向量法

中心向量算法比較簡(jiǎn)單，它利用向量空間模型，對(duì)各個(gè)訓(xùn)練類(lèi)別分別計(jì)算平均向量，進(jìn)行標(biāo)準(zhǔn)化處理，再計(jì)算相似度。設(shè)T={d1，...dn}={，...，}，表示文檔dj的向量，Wi，j表示特征i在文檔.j中的權(quán)重，對(duì)于類(lèi)別Ci其中心向量VCi={VW1，i，...VWm，i}其中:

然后，用Cos（D，VCi）來(lái)計(jì)算它們之間的相似度。

3.2樸素貝葉斯方法（Na ve Bayes）

Na ve Bayes（簡(jiǎn)稱(chēng)NB）理論的基本觀點(diǎn)是：假設(shè)在給定的文本類(lèi)語(yǔ)境下，文本屬性是相互獨(dú)立的。

貝葉斯分類(lèi)方法以貝葉斯定理為理論基礎(chǔ)，是一種在已知先驗(yàn)概率與條件概率的情況下的模式識(shí)別方法。 貝葉斯分類(lèi)方法分兩種：一種將問(wèn)題簡(jiǎn)化，假設(shè)一個(gè)屬性對(duì)給定類(lèi)的影響?yīng)毩⒂谄渌麑傩裕刺卣鳘?dú)立性假設(shè)。當(dāng)假設(shè)成立時(shí)，與其他分類(lèi)算法相比，樸素貝葉斯分類(lèi)器是最精確的。但是實(shí)際問(wèn)題中文本屬性之間的依賴關(guān)系是可能存在的。 這就要求考慮屬性之間的依賴程度，顯然其計(jì)算復(fù)雜度比前一種高得多，當(dāng)然也更能反映真實(shí)文本的情況。但是實(shí)現(xiàn)十分復(fù)雜，目前還停留在理論的研究階段。大量的理論和實(shí)驗(yàn)表明貝葉斯算法繁雜，且效果不顯著。 但是我們可以借鑒其項(xiàng)無(wú)關(guān)性的基本概念。

3.3 k-近鄰算法（K-NN）

KNN方法是一種基于實(shí)例的文本分類(lèi)方法.首先，對(duì)于一個(gè)測(cè)試文本，計(jì)算它與訓(xùn)練樣本集中每個(gè)文本的文本相似度，依文本相似度找出k個(gè)最相似的訓(xùn)練文本。然后在此基礎(chǔ)上給每一個(gè)文本類(lèi)打分，分值是k個(gè)訓(xùn)練文檔中屬于該類(lèi)的文本與測(cè)試文本之間的文檔相似度之和。對(duì)這k個(gè)文本所屬類(lèi)的分值統(tǒng)計(jì)完畢之后，即按分值進(jìn)行排序。為了分類(lèi)合理，應(yīng)當(dāng)選定一個(gè)閾值，可以認(rèn)為測(cè)試文本屬于越過(guò)閾值的所有類(lèi)。

knndoc 是指在訓(xùn)練集中依文本相似度找出與文本dx，最相似的k個(gè)訓(xùn)練文本所組成的訓(xùn)練文本子集；當(dāng)訓(xùn)練文本dx屬于c，類(lèi)時(shí)g(di，cj)取1，否則取0.一般可以通過(guò)另外的測(cè)試文本集進(jìn)行調(diào)整。

3.4支持向量機(jī)（SVM）

支持向量機(jī)（SVM）建立在計(jì)算學(xué)習(xí)理論的結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則之上，其主要思想是針對(duì)兩類(lèi)分類(lèi)問(wèn)題在高維空間中尋找一個(gè)超平面作為兩類(lèi)的分割。以保證最小的分類(lèi)錯(cuò)誤率。用（SVM）實(shí)現(xiàn)分類(lèi)，首先要從原始空間中抽取特征，將原始空間中的樣本映射為高維特征空間中的一個(gè)向量。包含這個(gè)向量的文本稱(chēng)為正例，所有不包含這個(gè)向量的文本稱(chēng)為反例?？瞻妆欢x為在線形關(guān)系里，距正例和反例最近的超平面中的實(shí)例。一個(gè)支持向量機(jī)是從最大空白中分離反例的正例集合構(gòu)成的超平面。

3.5基于投票的方法(Voting Method)

基于投票方法比較典型的有Bagging 法和Boosting 法。a.Bagging 法。訓(xùn)練R個(gè)分類(lèi)器f i ，分類(lèi)器之間其他相同就是參數(shù)不同。其中f i 是通過(guò)從訓(xùn)練集合中( N 篇文檔) 隨機(jī)取(取后放回) N 次文檔構(gòu)成的訓(xùn)練集合訓(xùn)練得到的。對(duì)于新文檔d ，用這R 個(gè)分類(lèi)器去分類(lèi)， 得到的最多的那個(gè)類(lèi)別作為d 的最終類(lèi)別。b.Boosting 法。類(lèi)似Bagging 方法，但是訓(xùn)練是串行進(jìn)行的，第k 個(gè)分類(lèi)器訓(xùn)練時(shí)關(guān)注對(duì)前k - 1 分類(lèi)器中錯(cuò)分的文檔，即不是隨機(jī)取，而是加大取這些文檔的概率。

3.6遺傳算法( Genetic Algorithms ， GA)

遺傳算法是一種基于生物進(jìn)化過(guò)程的組合優(yōu)化方法。其基本思想是:隨著時(shí)間的更替，只有最適合的物種才得以進(jìn)化。將這種思想用于文本挖掘就是根據(jù)遺傳算法獲得最適合的模型，并據(jù)此對(duì)模型進(jìn)行優(yōu)化。遺傳算法能夠解決其他技術(shù)難以解決的問(wèn)題，然而它也是一種最難理解和最開(kāi)放的方法。遺傳算法常與神經(jīng)網(wǎng)絡(luò)結(jié)合起來(lái)使用，以在較高的層次上提高模型的可理解性。它有三個(gè)基本算子:遺傳、交叉、變異，其基本步驟為:a. 隨機(jī)產(chǎn)生初始種群; b. 構(gòu)造評(píng)價(jià)函數(shù);c. 選擇高適應(yīng)值的個(gè)體進(jìn)入下一代;d. 通過(guò)遺傳、變異算子產(chǎn)生新的個(gè)體;e.重復(fù)b～d 過(guò)程，直到產(chǎn)生最優(yōu)化個(gè)體，問(wèn)題解決。

3.7神經(jīng)網(wǎng)絡(luò)

神經(jīng)網(wǎng)絡(luò)的基本特點(diǎn):大量簡(jiǎn)單節(jié)點(diǎn)的復(fù)雜連接;高度并行處理;分布式存儲(chǔ)，信息存在整個(gè)網(wǎng)中，用權(quán)值體現(xiàn)出來(lái)，有聯(lián)想能力，可以從一個(gè)不完整的信息恢復(fù)出完整信息;自組織、自學(xué)習(xí)。圖2 是一個(gè)多層的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖。

神經(jīng)網(wǎng)絡(luò)的最大優(yōu)點(diǎn)是他能精確地對(duì)復(fù)雜問(wèn)題進(jìn)行預(yù)測(cè)。

以上列出了七種分類(lèi)方法但是這些分類(lèi)方法也還遠(yuǎn)沒(méi)有達(dá)到滿足用戶的需求。 伴隨著計(jì)算機(jī)技術(shù)的不斷進(jìn)步，人們也在不斷的研究新的分類(lèi)方法。

4 小結(jié)：此文章對(duì)于深入研究文本信息加工、信息服務(wù)有重要的指導(dǎo)意義。雖然文本分類(lèi)技術(shù)取得了長(zhǎng)足發(fā)展，不斷涌現(xiàn)新的算法，但是對(duì)于一般用戶的感覺(jué)還是不能夠隨心所欲的快捷方便的找到自己所需要的信息，所以在文本自動(dòng)分類(lèi)領(lǐng)域還有很大的發(fā)展空間。

參考文獻(xiàn)

[1]奉國(guó)和.基于聚類(lèi)的大樣本支持向量機(jī)研究.計(jì)算機(jī)科學(xué) ，2006(4) .

[2]王義麟.一種基于決策樹(shù)的分類(lèi)算法J . 軟件學(xué)報(bào) ，2004 ，15(1) :1 - 4.

[3]和亞麗 ，陳立潮. Web 文本挖掘中的特征選取方法研究 J . 計(jì)算機(jī)工程 ，2005(5).