搜索引擎中的文本分類方法研究

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

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

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

1評估方法

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

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

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

2文本分類過程

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

3 常用分類算法

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

D= ｛｝表示將要被分類的文本的特征向量；

c1，...ck表示這些文本可能的類別；

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

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

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

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

3.1中心向量法

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

然后，用Cos（D，VCi）來計算它們之間的相似度。

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

Na ve Bayes（簡稱NB）理論的基本觀點是：假設(shè)在給定的文本類語境下，文本屬性是相互獨立的。

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

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

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

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

3.4支持向量機（SVM）

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

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

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

3.6遺傳算法( Genetic Algorithms ， GA)

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

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

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

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

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

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

參考文獻(xiàn)

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

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

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