基于優(yōu)化類中心分類算法的文本分類研究

王 斌，邵華清，劉 振

1.佳木斯大學(xué)信息電子技術(shù)學(xué)院，黑龍江佳木斯 154007

2.佳木斯大學(xué)經(jīng)濟(jì)管理學(xué)院，黑龍江佳木斯 154007

3.桂林理工大學(xué)，廣西桂林 541004

0 引言

當(dāng)前，隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展，各類電子郵件和電子文檔以前所未有速度的迅速增長，用戶如何能從海量文本中快速準(zhǔn)確的獲取有效的信息，是人們普遍關(guān)注的問題。文本形式是互聯(lián)網(wǎng)上大部分信息的載體，文本的識(shí)別的速度決定了是否能高效獲取信息的速度。文本分類識(shí)別技術(shù)可以把海量但缺乏結(jié)構(gòu)的文本數(shù)據(jù)組織成規(guī)范的文本數(shù)據(jù)，以達(dá)到提高檢索信息和利用信息的效率的目的。文本分類已經(jīng)成為組織和管理文本數(shù)據(jù)的重要形式。傳統(tǒng)的人工分類已經(jīng)不能滿足如今的需要，它耗費(fèi)大量的人力、物力和精力，并且分類結(jié)果一致性不高。本文針對(duì)傳統(tǒng)類中心分類算法由于訓(xùn)練文檔分散，不能準(zhǔn)確的表示各類別的中心向量，提出了優(yōu)化算法，從而提高分類準(zhǔn)確度。

1 類中心分類算法

文本分類的訓(xùn)練集是已經(jīng)分類好的文本，這些分類好的文本都具有各自類別的特點(diǎn)，我們可以通過學(xué)習(xí)這些分類好的文本，提取出代表每一類別各自的特點(diǎn)，這些特點(diǎn)能唯一的代表一個(gè)類別。在用向量空間模型表示的文本中，可以通過提取能代表該類別的特征項(xiàng)來表示類別。類中心分類算法是典型的應(yīng)用代表類別特點(diǎn)的特征項(xiàng)來表示類別的算法。它具有容易理解、思路清晰、分類效果好等優(yōu)點(diǎn)。類中心分類算法思路比較簡(jiǎn)單，將訓(xùn)練集中的每個(gè)文本應(yīng)用一定的特征權(quán)重算法表示成一個(gè)特征權(quán)重的向量 ：為了對(duì)不同長度的文檔統(tǒng)一描述，每一篇文檔都被規(guī)范化為統(tǒng)一的長度，例如：然后根據(jù)平均算法為每類文本生成代表該類的中心向量。令表示預(yù)定義的類別集合，類別Ci的中心向量定義為：

類中心分類算法是從訓(xùn)練集中得到類別的中心向量，它對(duì)訓(xùn)練集依賴性比較大，對(duì)訓(xùn)練集的集中程度和規(guī)模非常敏感，一般情況下訓(xùn)練集文本代表性越強(qiáng)、規(guī)模越大分類效果會(huì)越好。

2 優(yōu)化的類中心分類算法

在類中心文本分類算法中，類別的中心向量是由該類別文本特征向量的簡(jiǎn)單算術(shù)平均得到。在訓(xùn)練集中，就分類而言，文檔一般比較分散，所以在空間上，有些分類與其它類就會(huì)有重疊的區(qū)域，如果直接用這些文檔來計(jì)算各個(gè)類別的中心向量，就會(huì)出現(xiàn)模型偏差，因此不能達(dá)到理想的分類結(jié)果。研究一種優(yōu)化的類中心分類算法，以修正這種模型偏差。即用當(dāng)前的中心向量對(duì)訓(xùn)練集進(jìn)行分類，然后用訓(xùn)練錯(cuò)誤文檔來更新中心向量，并假設(shè)文檔集中的每一篇文檔都只屬于一個(gè)類別。它的中心思想為：在進(jìn)行的每一次迭代過程中用規(guī)范化中心向量對(duì)訓(xùn)練文本進(jìn)行分類，其目的是為了找出所有訓(xùn)練錯(cuò)誤文檔。并對(duì)它進(jìn)行歸類。但因?yàn)槲臋n分散原因的影響，不少文檔的分類弄錯(cuò)，可以適當(dāng)增加中心向量中這些文檔特征項(xiàng)的權(quán)重，相反，應(yīng)該減少中心向量中misin-ofi的各文檔特征權(quán)重大的特征項(xiàng)的權(quán)重。利用這些分類錯(cuò)誤文檔，更新類中心向量，并規(guī)范化，得到迭代后的規(guī)范化中心向量。

3 實(shí)驗(yàn)方法與結(jié)果

3.1 實(shí)驗(yàn)樣本

在文本自動(dòng)分類系統(tǒng)中，用于實(shí)驗(yàn)的文本集一般分為兩個(gè)部分：訓(xùn)練集和測(cè)試集。訓(xùn)練集是由一組文本組成，并且這些文本已經(jīng)分好類，用于歸納出各個(gè)類別的特性以構(gòu)造分類器。根據(jù)分類體系的設(shè)定，每一個(gè)類別都應(yīng)含有一定數(shù)量的訓(xùn)練文本；測(cè)試集是用于測(cè)試分類效果的文檔的集合。其中每個(gè)文本都通過分類器分類，然后與正確決策的分類結(jié)果相對(duì)比，從而得到對(duì)分類器效果的評(píng)價(jià)，但測(cè)試集并不參與分類器的建設(shè)。

3.2 結(jié)果評(píng)測(cè)標(biāo)準(zhǔn)

評(píng)估分類準(zhǔn)確程度的依據(jù)是通過專家對(duì)文本的正確分類結(jié)果的比較，與人工分類結(jié)果越相近，分類的準(zhǔn)確程度就越高。文本分類中常用的評(píng)測(cè)指標(biāo)有：準(zhǔn)確率和查全率。本文使用如下的評(píng)估標(biāo)準(zhǔn)：

查準(zhǔn)率：是在所有輸入系統(tǒng)中，進(jìn)行分類處理的文本中與專家分類結(jié)果完全吻合的文本所占的比率，即：被正確分到類別i的文本數(shù)與所有被分到類別i的文本數(shù)的比值。

查全率：是在分類系統(tǒng)中，分類正確的文本所占的比率，即：被正確分到類別i的文本數(shù)與實(shí)際屬于類別i的文本數(shù)的比值。

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

從對(duì)比中可以看到，類中心分類算法在任何類別的分類效果都不如優(yōu)化后的類中心分類算法。

[1]旺建華.中文文本分類技術(shù)研究[D].吉林大學(xué)，2007，9.

[2]王小燕.文本分類相關(guān)技術(shù)應(yīng)用與研究[D].西北大學(xué)，2007，4.