張志強(qiáng)

（華北計(jì)算技術(shù)研究所，北京市　100083）

基于自學(xué)習(xí)向量空間模型文本分類算法的研究與應(yīng)用

張志強(qiáng)

（華北計(jì)算技術(shù)研究所，北京市100083）

隨著網(wǎng)絡(luò)信息的迅猛發(fā)展，信息處理已經(jīng)成為人們獲取有用信息不可缺少的工具。文本自動(dòng)分類是信息處理的重要研究方向。它是指在給定的分類體系下，根據(jù)文本的內(nèi)容自動(dòng)判別文本類別的過(guò)程。本文對(duì)文本分類中所涉及的關(guān)鍵技術(shù)，包括向量空間模型，特征提取，機(jī)器學(xué)習(xí)方法等進(jìn)行了研究和探討。最后，本文實(shí)現(xiàn)了一套基于自學(xué)習(xí)向量空間模型的文本分類系統(tǒng)，并基于kafka消息隊(duì)列和storm流計(jì)算框架，實(shí)時(shí)地為文本進(jìn)行分類。

文本分類；向量空間模型；機(jī)器學(xué)習(xí)；kafka消息隊(duì)列；storm流計(jì)算

本文著錄格式：張志強(qiáng). 基于自學(xué)習(xí)向量空間模型文本分類算法的研究與應(yīng)用[J]. 軟件，2016，37（9）：118-121

1　引言

隨著信息技術(shù)的不斷普及，人們對(duì)信息資源的依賴性越來(lái)越大，如何實(shí)現(xiàn)信息的自動(dòng)分類，尤其是中文文本信息的有效分類是目前中文信息處理研究的一個(gè)重要分支領(lǐng)域。

中文文本分類已經(jīng)不是一個(gè)新的課題，但隨著信息化帶來(lái)的信息量急劇增長(zhǎng)，現(xiàn)有的中文文本分類技術(shù)面臨著新的挑戰(zhàn)，主要表現(xiàn)在：

1）動(dòng)態(tài)性。當(dāng)今社會(huì)日新月異，知識(shí)更新存在于每一領(lǐng)域，內(nèi)容變化迅速，信息交換變得更為頻繁。分類模型如果缺乏適應(yīng)性，分類質(zhì)量將無(wú)法得到保障。

2）非結(jié)構(gòu)化。網(wǎng)絡(luò)文本信息來(lái)源各異，往往具有不同的形式和語(yǔ)法。如何對(duì)這些非結(jié)構(gòu)化的數(shù)據(jù)進(jìn)行有效的處理，給文本分類技術(shù)提出了新的難題。

3）數(shù)據(jù)量大。因特網(wǎng)的發(fā)展帶來(lái)了信息海量式膨脹，信息出現(xiàn)的速度遠(yuǎn)遠(yuǎn)超出了人們接受的速度。這樣龐大的數(shù)據(jù)量對(duì)文本分類技術(shù)的時(shí)間效率和分類性能提出了新的挑戰(zhàn)。

本文研究的是一種基于自學(xué)習(xí)向量空間模型[1]文的本分類系統(tǒng)，這是在傳統(tǒng)的文本分類模型的基礎(chǔ)上的一種主動(dòng)學(xué)習(xí)的文本分類方法。本文還增加了對(duì)非結(jié)構(gòu)化的文本的處理，提供了把非結(jié)構(gòu)化文本標(biāo)準(zhǔn)化成詞向量模型的方法。同時(shí)本文最后實(shí)現(xiàn)的文本分類系統(tǒng)使用kafka消息隊(duì)列發(fā)布訂閱文本數(shù)據(jù)，并運(yùn)行在storm流計(jì)算框架上，增強(qiáng)了文本數(shù)據(jù)的處理數(shù)據(jù)量及實(shí)時(shí)處理的能力。

2　文本分類涉及的概念及文本分類算法的介紹

2.1文本分類涉及的概念

中文文本分類所涉及到的概念主要包括分詞技術(shù)、文本表示、特征抽取和分類算法的選擇。

1）分詞技術(shù)：相比于西方文本分類，中文文本分類的一個(gè)重要的區(qū)別在于預(yù)處理階段，中文文本的標(biāo)準(zhǔn)化需要分詞。分詞方法從簡(jiǎn)單的查字典的方法，到后來(lái)的基于統(tǒng)計(jì)語(yǔ)言模型的分詞方法，中文分詞的技術(shù)已趨于成熟。比較有影響力的當(dāng)屬于中科院計(jì)算所開(kāi)發(fā)的漢語(yǔ)詞法分析系統(tǒng)ICTCLAS，現(xiàn)已發(fā)布供中文文本分類的研究使用。

2）文本表示：計(jì)算機(jī)不具有人類的智慧，不能讀懂文字，所以必須把文本轉(zhuǎn)換成計(jì)算機(jī)能夠理解的形式，即進(jìn)行文本表示。目前文本表示模型主要是Gerard Salton和McGill于1969年提出的向量空間模型（VSM）。向量空間模型的基本思想是把文檔簡(jiǎn)化為特征項(xiàng)的權(quán)重，并使用向量表示：（w1,w2, w3,…,wn），其中wi為第i個(gè)特征項(xiàng)的權(quán)重，一般選取詞作為特征項(xiàng)，權(quán)重用詞頻表示。

最初的向量表示完全是0、1的形式，即：如果文本中出現(xiàn)了該詞，那么文本向量的該維為1，否則為0。這種方法無(wú)法體現(xiàn)這個(gè)詞在文本中的作用程度，所以0，1逐漸被更精確地詞頻代替，詞頻分為絕對(duì)詞頻和相對(duì)詞頻。絕對(duì)詞頻使用詞在文本中出現(xiàn)的頻率表示文本；相對(duì)詞頻為歸一化的詞頻，其計(jì)算方法主要運(yùn)用TF-IDF公式。本文采用的TF-IDF公式為：

3）特征抽取[2]：由于文本數(shù)據(jù)的半結(jié)構(gòu)化至于無(wú)結(jié)構(gòu)化的特點(diǎn)，當(dāng)用特征向量對(duì)文檔進(jìn)行表示時(shí)，特征向量通常會(huì)達(dá)到幾萬(wàn)維甚至幾十萬(wàn)維。因此我們需要進(jìn)行維數(shù)壓縮的工作，這樣做的目的主要有兩個(gè)：第一，為了提高程序的效率，提高運(yùn)行速度；第二，所有詞對(duì)文本分類的意義是不同的，一些通用的、各個(gè)類別都普遍存在的詞匯對(duì)分類的貢獻(xiàn)小；為了提高分類精度，對(duì)于每一類，我們應(yīng)該去除那些表現(xiàn)力不強(qiáng)的詞匯，篩選出針對(duì)該類的特征項(xiàng)集合，存在多種篩選特征項(xiàng)的算法，如下所列：

a）根據(jù)詞和類別的互相信息量判斷

b）根據(jù)詞熵判斷

c）根據(jù)KL距離判斷

本文采用了詞和類別的互信息量進(jìn)行特征抽取的判斷標(biāo)準(zhǔn)，其算法過(guò)程如下：

① 初始情況下，該特征項(xiàng)集合包含所有該類中出現(xiàn)的詞。

② 對(duì)于每個(gè)詞，計(jì)算詞和類別的互信息量。③ 對(duì)于該類中所有的詞，依據(jù)上面計(jì)算的互信息量排序。

④ 抽取一定數(shù)量的詞作為特征項(xiàng)。具體 需要抽取多少維的特征項(xiàng)，目前無(wú)很好的解決辦法，一般采用先定初始值，然后根據(jù)實(shí)驗(yàn)測(cè)試和統(tǒng)計(jì)結(jié)果確定最佳值。一般初始值定義在幾千左右。

⑤ 將每類中所有的訓(xùn)練文本，根據(jù)抽取的特征項(xiàng)進(jìn)行向量維數(shù)壓縮，精簡(jiǎn)向量表示。

4）分類算法：分類算法是研究文本分類的核心問(wèn)題。目前基于統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的方法已經(jīng)成為文本分類的主流方法，并且還在不斷發(fā)展，比較常見(jiàn)的文本分類算法有：樸素貝葉斯，KNN分類算法[3-5]，決策樹(shù)算法，神經(jīng)網(wǎng)絡(luò)，支持向量機(jī)。本文在接下來(lái)的一小節(jié)重點(diǎn)介紹和比較KNN分類算法和樸素貝葉斯算法。

2.2文本分類算法的介紹

2.2.1KNN算法

K Nearest Neighbor算法，簡(jiǎn)稱KNN算法，KNN算法是一個(gè)理論上比較成熟的方法，最初由Cover和Hart于1968年提出，其思路非常簡(jiǎn)單直觀，易于快速實(shí)現(xiàn)，以及錯(cuò)誤低的優(yōu)點(diǎn)。KNN算法的基本思想為：根據(jù)距離函數(shù)計(jì)算待分類樣本x和每個(gè)訓(xùn)練樣本的距離，選擇與待分類樣本距離最小的K個(gè)樣本作為x的K個(gè)最近鄰，最后根據(jù)x的K個(gè)最近鄰判斷x的類別。

它是一種比較簡(jiǎn)單的機(jī)器學(xué)習(xí)算法，它的原理也比較簡(jiǎn)單。下面用最經(jīng)典的一張圖來(lái)說(shuō)明，如下圖：

如圖所示，假設(shè)現(xiàn)在需要對(duì)中間綠色的圓進(jìn)行分類，假設(shè)我們尋找距離這個(gè)綠色圓最近的3個(gè)樣本，即K=3，那么可以看出這個(gè)綠色圓屬于紅色三角形所在的類；如果K=5，因?yàn)樗{(lán)色方框最多，所以此時(shí)綠色圓屬于藍(lán)色方框所在的類。從而得到當(dāng)K值取值不同時(shí)，得到的分類結(jié)果也可能不一樣，所以很多時(shí)候K值得選取很關(guān)鍵，這就是KNN的核心思想。如果類別個(gè)數(shù)為偶數(shù)，那么K通常會(huì)設(shè)置為一個(gè)奇數(shù)；如果類別個(gè)數(shù)為奇數(shù)，K通常設(shè)置為偶數(shù)，這樣就能保證不會(huì)有平局的發(fā)生。

KNN算法是惰性學(xué)習(xí)法，學(xué)習(xí)程序直到對(duì)給定的測(cè)試集分類前的最后一刻對(duì)構(gòu)造模型。在分類時(shí)，這種學(xué)習(xí)法的計(jì)算開(kāi)銷在和需要大的存儲(chǔ)開(kāi)銷。總結(jié)KNN方法不足之處主要有下幾點(diǎn)：①分類速度慢。②屬性等同權(quán)重影響了準(zhǔn)確率。③樣本庫(kù)容量依懶性較強(qiáng)。④K值的確定。

2.2.2樸素貝葉斯算法

貝葉斯法則建立了P(h|d)、P(h)和P(d|h)三者之間的聯(lián)系如下：

其中：（1）P(h)是根據(jù)歷史數(shù)據(jù)或主觀判斷所確定的h 出現(xiàn)的概率，該概率沒(méi)有經(jīng)過(guò)當(dāng)前情況的證實(shí)，因此被稱為類先驗(yàn)概率，或簡(jiǎn)稱先驗(yàn)概率（prior probability）。（2）P(d|h)是當(dāng)某一輸出結(jié)果存在時(shí)，某輸入數(shù)據(jù)相應(yīng)出現(xiàn)的可能性。對(duì)于離散數(shù)據(jù)而言，該值為概率，被稱為類條件概率（classconditional probability）；對(duì)于連續(xù)數(shù)據(jù)而言，該值為概率密度，被稱為類條件概率密度（classconditional probability density），統(tǒng)計(jì)學(xué)中通常應(yīng)使用P(d|h)表示，以示與概率區(qū)別。（3）P(h|d)的意義同前，它反映了當(dāng)輸入數(shù)據(jù)d時(shí)，輸出結(jié)果h出現(xiàn)的概率，這是根據(jù)當(dāng)前情況對(duì)先驗(yàn)概率進(jìn)行修正后得到的概率，因此被稱為后驗(yàn)概率（posterior probability）。

顯然，當(dāng)機(jī)器處理問(wèn)題時(shí)，它關(guān)心的是P(h|d)。對(duì)于兩個(gè)不同的輸出結(jié)果h1和h2，如果P(h1|d)> P(h2|d)，表示結(jié)果h1的可能性更大，從而最終結(jié)果應(yīng)為h1。也就是說(shuō)，應(yīng)優(yōu)先選擇后驗(yàn)概率值大的結(jié)果，這一策略被稱為極大后驗(yàn)估計(jì)（Maximum A Posteriori），簡(jiǎn)稱MAP。設(shè)H表示結(jié)果集，則極大后驗(yàn)估計(jì)為

在樸素貝葉斯分類器中，假設(shè)數(shù)據(jù)向量中各分量相互獨(dú)立，從而將高維數(shù)據(jù)分布轉(zhuǎn)化為若干一維數(shù)據(jù)分布進(jìn)行處理。設(shè)d=(d1,d2,…,dn)，其中n為數(shù)據(jù)維數(shù)，則根據(jù)各分量相互獨(dú)立的假設(shè)，類條件概率（或概率密度）可表示為：

于是樸素貝葉斯分類器的決策公式為

公式表明：只要獲得每個(gè)數(shù)據(jù)分量對(duì)應(yīng)的P(d h)i，便獲得了類條件概率（或概率密度）。這一過(guò)程的計(jì)算量遠(yuǎn)遠(yuǎn)小于不做各分量獨(dú)立性假設(shè)而直接估計(jì)高維類條件概率（或類條件概率密度）的計(jì)算量。例如，設(shè)d=(d1,d2,…,dn)為離散數(shù)據(jù)向量，其中每個(gè)分量上的可能取值為m。如果假設(shè)各分量相互獨(dú)立，則只需學(xué)習(xí)mn個(gè)概率值；而如果假設(shè)各分量彼此相關(guān)，則需要考慮所有可能的分量組合，這便需要學(xué)習(xí)個(gè)概率，顯然這兩個(gè)數(shù)據(jù)量之間的差距是驚人的。

3　自學(xué)習(xí)的文本分類算法的研究

就目前研究情況來(lái)說(shuō)，國(guó)內(nèi)學(xué)者提出了很多文本分類算法，這些分類算法在封閉測(cè)試中表現(xiàn)良好，但是在開(kāi)放測(cè)試中，尤其面對(duì)異常龐雜的網(wǎng)絡(luò)文本的測(cè)試中，往往不盡人意。究其原因，大多數(shù)的文本分類系統(tǒng)都采取“訓(xùn)練-分類”模式，訓(xùn)練和分類是兩個(gè)彼此獨(dú)立的過(guò)程，訓(xùn)練過(guò)程一般只針對(duì)訓(xùn)練語(yǔ)料進(jìn)行學(xué)習(xí)，在這種模式下，分類系統(tǒng)的性能依賴于訓(xùn)練預(yù)料的質(zhì)量，缺乏適應(yīng)性，不適宜海量、非結(jié)構(gòu)化、動(dòng)態(tài)的文本信息的處理要求。

本文研究的基于自學(xué)習(xí)向量空間模型文的本分類系統(tǒng)，該系統(tǒng)將訓(xùn)練過(guò)程延伸到分類過(guò)程中，以訓(xùn)練驅(qū)動(dòng)分類，以分類結(jié)果反饋進(jìn)行再訓(xùn)練，使得訓(xùn)練和分類兩個(gè)過(guò)程成為一個(gè)有機(jī)的整體，從而打破了訓(xùn)練、分類相對(duì)獨(dú)立的傳統(tǒng)模式，同時(shí)在訓(xùn)練過(guò)程中，克服了對(duì)訓(xùn)練預(yù)料的完全依賴性，從而增強(qiáng)了分類系統(tǒng)的自適應(yīng)能力。

本文介紹的自學(xué)習(xí)文本分類算法[6-7]，首先得到分類后的結(jié)果，主觀的對(duì)結(jié)果進(jìn)行評(píng)估，并反饋給訓(xùn)練樣本，調(diào)整訓(xùn)練樣本的向量空間模型。這是個(gè)不斷學(xué)習(xí)的過(guò)程，通過(guò)迭代反饋，逐漸提高分類的準(zhǔn)確率。

4　標(biāo)準(zhǔn)化非結(jié)構(gòu)化文本

本文為適應(yīng)不同格式的非結(jié)構(gòu)化文本，提供了文檔適配處理模塊[8]。利用Apache POI開(kāi)源工具處理不同類型的電子文檔，包括Word、PDF、TXT等等，處理結(jié)果統(tǒng)一為文本分類系統(tǒng)能處理的純文本格式數(shù)據(jù)。然后把純文本格式數(shù)據(jù)標(biāo)準(zhǔn)化成向量空間模型。

5　kafka消息隊(duì)列及Storm流計(jì)算框架下的實(shí)時(shí)分類

Kafka是一種高吞吐量的分布式發(fā)布訂閱消息系統(tǒng)，它可以處理消費(fèi)者規(guī)模的網(wǎng)站中所有動(dòng)作流數(shù)據(jù)。由于采集數(shù)據(jù)的速度和數(shù)據(jù)處理的速度不一定同步，本文添加一個(gè)消息中間件kafka來(lái)作為緩沖。

Storm是一個(gè)免費(fèi)開(kāi)源、分布式、高容錯(cuò)的實(shí)時(shí)流計(jì)算框架。Storm令持續(xù)不斷的流計(jì)算變得容易，彌補(bǔ)了Hadoop批處理所不能滿足的實(shí)時(shí)要求。本文為提供高實(shí)時(shí)性的文本分類系統(tǒng)，使用了storm實(shí)時(shí)流計(jì)算框架。

本文的文本分類系統(tǒng)，使用kafka消息隊(duì)列做緩沖中間件，并建立在Storm流計(jì)算框架的基礎(chǔ)之上。眾所周知，kafka負(fù)責(zé)高吞吐的讀取消息，并對(duì)消息保存到消息隊(duì)列中，保存時(shí)可以根據(jù)Topic進(jìn)行歸類，消息發(fā)送者成為Producer，消息接收者成為Consumer。在本文中，kafka負(fù)責(zé)高吞吐地讀取消息成為消息生產(chǎn)者，kafka還負(fù)責(zé)緩沖消息到消息隊(duì)列中成為消息緩沖中間件，storm實(shí)時(shí)讀取緩沖區(qū)的消息并處理成為消息消費(fèi)者。Storm的兩個(gè)核心組件spout和bolt，譯為中文為噴口和螺栓更加形象貼切。Spout是storm流處理中流的源頭，本文中的spout負(fù)責(zé)從緩沖隊(duì)列中讀取消息。Bolt是storm流處理中具體的處理單元，本文中的文本分類算法就是運(yùn)行在bolt上的。

6　文本分類系統(tǒng)測(cè)試結(jié)果說(shuō)明

通過(guò)大量的不同格式的電子文檔的導(dǎo)入，進(jìn)行文本分類，本文的文本分類系統(tǒng)能夠?qū)崟r(shí)地處理并返回分類結(jié)果，分類的效果較好，分類準(zhǔn)確率平均在80%。用戶可以通過(guò)對(duì)文本和分類結(jié)果進(jìn)行比對(duì)，反饋給系統(tǒng)人為分類的結(jié)果，系統(tǒng)會(huì)根據(jù)反饋的結(jié)果，調(diào)整向量空間模型。通過(guò)這樣的不斷迭代反饋，逐步提高分類準(zhǔn)確率。實(shí)驗(yàn)結(jié)果圖如下：

7　結(jié)束語(yǔ)

本文所實(shí)現(xiàn)的文本分類系統(tǒng)，實(shí)現(xiàn)了對(duì)本文開(kāi)始提出的文本分類目前存在的三個(gè)問(wèn)題數(shù)據(jù)量大、非結(jié)構(gòu)化、動(dòng)態(tài)性的解決，為傳統(tǒng)的文本分類方式注入新鮮的血液。

本文所提出的文本分類系統(tǒng)，仍然存在一些問(wèn)題，具體體現(xiàn)在：

1）半監(jiān)督的學(xué)習(xí)模式。這種學(xué)習(xí)模式需要人為地干預(yù)，這樣會(huì)一定程度上把分類的準(zhǔn)確性寄托在人為分類的基礎(chǔ)之上。

2）文本分類結(jié)果的準(zhǔn)確率上。本文實(shí)驗(yàn)的文本分類準(zhǔn)確率在80%，除了通過(guò)自學(xué)習(xí)這種“后天學(xué)習(xí)”方式來(lái)提高準(zhǔn)確率，還需提高“先天”的向量空間模型的建立以及分類算法的選擇上。

[1] 龐劍鋒, 卜東波, 白碩. 基于向量空間模型的文本自動(dòng)分類系統(tǒng)的研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)應(yīng)用研究, 2001, 09: 23-26.

[2] 張東禮, 汪東升, 鄭緯民. 基于VSM的中文文本分類系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2003, 09: 1288-1291.

[3] 黃萱菁, 夏迎炬, 吳立德. 基于向量空間模型的文本過(guò)濾系統(tǒng)[J]. 軟件學(xué)報(bào), 2003, 03: 435-442.

[4] 周炎濤, 唐劍波, 吳正國(guó). 基于向量空間模型的多主題Web文本分類方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2008, 01: 142-144.

[5] 李文波, 孫樂(lè), 張大鯤. 基于Labeled-LDA模型的文本分類新算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2008, 04: 620-627.

[6] 馬凱航, 高永明, 吳止鍰, 等. 大數(shù)據(jù)時(shí)代數(shù)據(jù)管理技術(shù)研究綜述[J]. 軟件, 2015, 36(10): 46-49.

[7] 謝子超. 非結(jié)構(gòu)化文本的自動(dòng)分類檢索平臺(tái)的研究與實(shí)現(xiàn)[J]. 軟件, 2015, 36(11): 112-114.

[8] 路同強(qiáng). 基于半監(jiān)督學(xué)習(xí)的微博謠言檢測(cè)方法[J]. 軟件, 2014, 35(9): 104-108.

[9] 申超波, 王志海, 孫艷歌. 基于標(biāo)簽聚類的多標(biāo)簽分類算法[J]. 軟件, 2014, 35(8): 16-21.

Research and Implementation of Text Categorization System Based on VSM and ML

ZHANG Zhi-qiang
(CETC 15 Institute, Beijing 100083, China)

In recent years, information processing turns more and more important for us to get useful information. Text categorization, the automated assigning of natural language texts to predefined categories based on their contents, is a task of increasing importance. This paper gives a research to several key techniques about text categorization, including vector space model, feature extraction, machine learning. At the last of this paper, a text categorization system based on VSM and ML is implemented, and it also can dispose text categorization at real time through kafka and storm, which is a flow calculation framework.

Text categorization; Vector space model; Machine learning; Kafka; Storm flow calculation

TP391.1

A

10.3969/j.issn.1003-6970.2016.09.028