張志強(qiáng)
(華北計(jì)算技術(shù)研究所,北京市 100083)
基于自學(xué)習(xí)向量空間模型文本分類算法的研究與應(yīng)用
張志強(qiáng)
(華北計(jì)算技術(shù)研究所,北京市100083)
隨著網(wǎng)絡(luò)信息的迅猛發(fā)展,信息處理已經(jīng)成為人們獲取有用信息不可缺少的工具。文本自動分類是信息處理的重要研究方向。它是指在給定的分類體系下,根據(jù)文本的內(nèi)容自動判別文本類別的過程。本文對文本分類中所涉及的關(guān)鍵技術(shù),包括向量空間模型,特征提取,機(jī)器學(xué)習(xí)方法等進(jìn)行了研究和探討。最后,本文實(shí)現(xiàn)了一套基于自學(xué)習(xí)向量空間模型的文本分類系統(tǒng),并基于kafka消息隊(duì)列和storm流計(jì)算框架,實(shí)時地為文本進(jìn)行分類。
文本分類;向量空間模型;機(jī)器學(xué)習(xí);kafka消息隊(duì)列;storm流計(jì)算
本文著錄格式:張志強(qiáng). 基于自學(xué)習(xí)向量空間模型文本分類算法的研究與應(yīng)用[J]. 軟件,2016,37(9):118-121
隨著信息技術(shù)的不斷普及,人們對信息資源的依賴性越來越大,如何實(shí)現(xiàn)信息的自動分類,尤其是中文文本信息的有效分類是目前中文信息處理研究的一個重要分支領(lǐng)域。
中文文本分類已經(jīng)不是一個新的課題,但隨著信息化帶來的信息量急劇增長,現(xiàn)有的中文文本分類技術(shù)面臨著新的挑戰(zhàn),主要表現(xiàn)在:
1)動態(tài)性。當(dāng)今社會日新月異,知識更新存在于每一領(lǐng)域,內(nèi)容變化迅速,信息交換變得更為頻繁。分類模型如果缺乏適應(yīng)性,分類質(zhì)量將無法得到保障。
2)非結(jié)構(gòu)化。網(wǎng)絡(luò)文本信息來源各異,往往具有不同的形式和語法。如何對這些非結(jié)構(gòu)化的數(shù)據(jù)進(jìn)行有效的處理,給文本分類技術(shù)提出了新的難題。
3)數(shù)據(jù)量大。因特網(wǎng)的發(fā)展帶來了信息海量式膨脹,信息出現(xiàn)的速度遠(yuǎn)遠(yuǎn)超出了人們接受的速度。這樣龐大的數(shù)據(jù)量對文本分類技術(shù)的時間效率和分類性能提出了新的挑戰(zhàn)。
本文研究的是一種基于自學(xué)習(xí)向量空間模型[1]文的本分類系統(tǒng),這是在傳統(tǒng)的文本分類模型的基礎(chǔ)上的一種主動學(xué)習(xí)的文本分類方法。本文還增加了對非結(jié)構(gòu)化的文本的處理,提供了把非結(jié)構(gòu)化文本標(biāo)準(zhǔn)化成詞向量模型的方法。同時本文最后實(shí)現(xiàn)的文本分類系統(tǒng)使用kafka消息隊(duì)列發(fā)布訂閱文本數(shù)據(jù),并運(yùn)行在storm流計(jì)算框架上,增強(qiáng)了文本數(shù)據(jù)的處理數(shù)據(jù)量及實(shí)時處理的能力。
2.1文本分類涉及的概念
中文文本分類所涉及到的概念主要包括分詞技術(shù)、文本表示、特征抽取和分類算法的選擇。
1)分詞技術(shù):相比于西方文本分類,中文文本分類的一個重要的區(qū)別在于預(yù)處理階段,中文文本的標(biāo)準(zhǔn)化需要分詞。分詞方法從簡單的查字典的方法,到后來的基于統(tǒng)計(jì)語言模型的分詞方法,中文分詞的技術(shù)已趨于成熟。比較有影響力的當(dāng)屬于中科院計(jì)算所開發(fā)的漢語詞法分析系統(tǒng)ICTCLAS,現(xiàn)已發(fā)布供中文文本分類的研究使用。
2)文本表示:計(jì)算機(jī)不具有人類的智慧,不能讀懂文字,所以必須把文本轉(zhuǎn)換成計(jì)算機(jī)能夠理解的形式,即進(jìn)行文本表示。目前文本表示模型主要是Gerard Salton和McGill于1969年提出的向量空間模型(VSM)。向量空間模型的基本思想是把文檔簡化為特征項(xiàng)的權(quán)重,并使用向量表示:(w1,w2, w3,…,wn),其中wi為第i個特征項(xiàng)的權(quán)重,一般選取詞作為特征項(xiàng),權(quán)重用詞頻表示。
最初的向量表示完全是0、1的形式,即:如果文本中出現(xiàn)了該詞,那么文本向量的該維為1,否則為0。這種方法無法體現(xiàn)這個詞在文本中的作用程度,所以0,1逐漸被更精確地詞頻代替,詞頻分為絕對詞頻和相對詞頻。絕對詞頻使用詞在文本中出現(xiàn)的頻率表示文本;相對詞頻為歸一化的詞頻,其計(jì)算方法主要運(yùn)用TF-IDF公式。本文采用的TF-IDF公式為:
3)特征抽取[2]:由于文本數(shù)據(jù)的半結(jié)構(gòu)化至于無結(jié)構(gòu)化的特點(diǎn),當(dāng)用特征向量對文檔進(jìn)行表示時,特征向量通常會達(dá)到幾萬維甚至幾十萬維。因此我們需要進(jìn)行維數(shù)壓縮的工作,這樣做的目的主要有兩個:第一,為了提高程序的效率,提高運(yùn)行速度;第二,所有詞對文本分類的意義是不同的,一些通用的、各個類別都普遍存在的詞匯對分類的貢獻(xiàn)??;為了提高分類精度,對于每一類,我們應(yīng)該去除那些表現(xiàn)力不強(qiáng)的詞匯,篩選出針對該類的特征項(xiàng)集合,存在多種篩選特征項(xiàng)的算法,如下所列:
a)根據(jù)詞和類別的互相信息量判斷
b)根據(jù)詞熵判斷
c)根據(jù)KL距離判斷
本文采用了詞和類別的互信息量進(jìn)行特征抽取的判斷標(biāo)準(zhǔn),其算法過程如下:
① 初始情況下,該特征項(xiàng)集合包含所有該類中出現(xiàn)的詞。
② 對于每個詞,計(jì)算詞和類別的互信息量。③ 對于該類中所有的詞,依據(jù)上面計(jì)算的互信息量排序。
④ 抽取一定數(shù)量的詞作為特征項(xiàng)。具體 需要抽取多少維的特征項(xiàng),目前無很好的解決辦法,一般采用先定初始值,然后根據(jù)實(shí)驗(yàn)測試和統(tǒng)計(jì)結(jié)果確定最佳值。一般初始值定義在幾千左右。
⑤ 將每類中所有的訓(xùn)練文本,根據(jù)抽取的特征項(xiàng)進(jìn)行向量維數(shù)壓縮,精簡向量表示。
4)分類算法:分類算法是研究文本分類的核心問題。目前基于統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的方法已經(jīng)成為文本分類的主流方法,并且還在不斷發(fā)展,比較常見的文本分類算法有:樸素貝葉斯,KNN分類算法[3-5],決策樹算法,神經(jīng)網(wǎng)絡(luò),支持向量機(jī)。本文在接下來的一小節(jié)重點(diǎn)介紹和比較KNN分類算法和樸素貝葉斯算法。
2.2文本分類算法的介紹
2.2.1KNN算法
K Nearest Neighbor算法,簡稱KNN算法,KNN算法是一個理論上比較成熟的方法,最初由Cover和Hart于1968年提出,其思路非常簡單直觀,易于快速實(shí)現(xiàn),以及錯誤低的優(yōu)點(diǎn)。KNN算法的基本思想為:根據(jù)距離函數(shù)計(jì)算待分類樣本x和每個訓(xùn)練樣本的距離,選擇與待分類樣本距離最小的K個樣本作為x的K個最近鄰,最后根據(jù)x的K個最近鄰判斷x的類別。
它是一種比較簡單的機(jī)器學(xué)習(xí)算法,它的原理也比較簡單。下面用最經(jīng)典的一張圖來說明,如下圖:
如圖所示,假設(shè)現(xiàn)在需要對中間綠色的圓進(jìn)行分類,假設(shè)我們尋找距離這個綠色圓最近的3個樣本,即K=3,那么可以看出這個綠色圓屬于紅色三角形所在的類;如果K=5,因?yàn)樗{(lán)色方框最多,所以此時綠色圓屬于藍(lán)色方框所在的類。從而得到當(dāng)K值取值不同時,得到的分類結(jié)果也可能不一樣,所以很多時候K值得選取很關(guān)鍵,這就是KNN的核心思想。如果類別個數(shù)為偶數(shù),那么K通常會設(shè)置為一個奇數(shù);如果類別個數(shù)為奇數(shù),K通常設(shè)置為偶數(shù),這樣就能保證不會有平局的發(fā)生。
KNN算法是惰性學(xué)習(xí)法,學(xué)習(xí)程序直到對給定的測試集分類前的最后一刻對構(gòu)造模型。在分類時,這種學(xué)習(xí)法的計(jì)算開銷在和需要大的存儲開銷??偨Y(jié)KNN方法不足之處主要有下幾點(diǎn):①分類速度慢。②屬性等同權(quán)重影響了準(zhǔn)確率。③樣本庫容量依懶性較強(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)的概率,該概率沒有經(jīng)過當(dāng)前情況的證實(shí),因此被稱為類先驗(yàn)概率,或簡稱先驗(yàn)概率(prior probability)。(2)P(d|h)是當(dāng)某一輸出結(jié)果存在時,某輸入數(shù)據(jù)相應(yīng)出現(xiàn)的可能性。對于離散數(shù)據(jù)而言,該值為概率,被稱為類條件概率(classconditional probability);對于連續(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時,輸出結(jié)果h出現(xiàn)的概率,這是根據(jù)當(dāng)前情況對先驗(yàn)概率進(jìn)行修正后得到的概率,因此被稱為后驗(yàn)概率(posterior probability)。
顯然,當(dāng)機(jī)器處理問題時,它關(guān)心的是P(h|d)。對于兩個不同的輸出結(jié)果h1和h2,如果P(h1|d)> P(h2|d),表示結(jié)果h1的可能性更大,從而最終結(jié)果應(yīng)為h1。也就是說,應(yīng)優(yōu)先選擇后驗(yàn)概率值大的結(jié)果,這一策略被稱為極大后驗(yàn)估計(jì)(Maximum A Posteriori),簡稱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è),類條件概率(或概率密度)可表示為:
于是樸素貝葉斯分類器的決策公式為
公式表明:只要獲得每個數(shù)據(jù)分量對應(yīng)的P(d h)i,便獲得了類條件概率(或概率密度)。這一過程的計(jì)算量遠(yuǎn)遠(yuǎn)小于不做各分量獨(dú)立性假設(shè)而直接估計(jì)高維類條件概率(或類條件概率密度)的計(jì)算量。例如,設(shè)d=(d1,d2,…,dn)為離散數(shù)據(jù)向量,其中每個分量上的可能取值為m。如果假設(shè)各分量相互獨(dú)立,則只需學(xué)習(xí)mn個概率值;而如果假設(shè)各分量彼此相關(guān),則需要考慮所有可能的分量組合,這便需要學(xué)習(xí)個概率,顯然這兩個數(shù)據(jù)量之間的差距是驚人的。
就目前研究情況來說,國內(nèi)學(xué)者提出了很多文本分類算法,這些分類算法在封閉測試中表現(xiàn)良好,但是在開放測試中,尤其面對異常龐雜的網(wǎng)絡(luò)文本的測試中,往往不盡人意。究其原因,大多數(shù)的文本分類系統(tǒng)都采取“訓(xùn)練-分類”模式,訓(xùn)練和分類是兩個彼此獨(dú)立的過程,訓(xùn)練過程一般只針對訓(xùn)練語料進(jìn)行學(xué)習(xí),在這種模式下,分類系統(tǒng)的性能依賴于訓(xùn)練預(yù)料的質(zhì)量,缺乏適應(yīng)性,不適宜海量、非結(jié)構(gòu)化、動態(tài)的文本信息的處理要求。
本文研究的基于自學(xué)習(xí)向量空間模型文的本分類系統(tǒng),該系統(tǒng)將訓(xùn)練過程延伸到分類過程中,以訓(xùn)練驅(qū)動分類,以分類結(jié)果反饋進(jìn)行再訓(xùn)練,使得訓(xùn)練和分類兩個過程成為一個有機(jī)的整體,從而打破了訓(xùn)練、分類相對獨(dú)立的傳統(tǒng)模式,同時在訓(xùn)練過程中,克服了對訓(xùn)練預(yù)料的完全依賴性,從而增強(qiáng)了分類系統(tǒng)的自適應(yīng)能力。
本文介紹的自學(xué)習(xí)文本分類算法[6-7],首先得到分類后的結(jié)果,主觀的對結(jié)果進(jìn)行評估,并反饋給訓(xùn)練樣本,調(diào)整訓(xùn)練樣本的向量空間模型。這是個不斷學(xué)習(xí)的過程,通過迭代反饋,逐漸提高分類的準(zhǔn)確率。
本文為適應(yīng)不同格式的非結(jié)構(gòu)化文本,提供了文檔適配處理模塊[8]。利用Apache POI開源工具處理不同類型的電子文檔,包括Word、PDF、TXT等等,處理結(jié)果統(tǒng)一為文本分類系統(tǒng)能處理的純文本格式數(shù)據(jù)。然后把純文本格式數(shù)據(jù)標(biāo)準(zhǔn)化成向量空間模型。
Kafka是一種高吞吐量的分布式發(fā)布訂閱消息系統(tǒng),它可以處理消費(fèi)者規(guī)模的網(wǎng)站中所有動作流數(shù)據(jù)。由于采集數(shù)據(jù)的速度和數(shù)據(jù)處理的速度不一定同步,本文添加一個消息中間件kafka來作為緩沖。
Storm是一個免費(fèi)開源、分布式、高容錯的實(shí)時流計(jì)算框架。Storm令持續(xù)不斷的流計(jì)算變得容易,彌補(bǔ)了Hadoop批處理所不能滿足的實(shí)時要求。本文為提供高實(shí)時性的文本分類系統(tǒng),使用了storm實(shí)時流計(jì)算框架。
本文的文本分類系統(tǒng),使用kafka消息隊(duì)列做緩沖中間件,并建立在Storm流計(jì)算框架的基礎(chǔ)之上。眾所周知,kafka負(fù)責(zé)高吞吐的讀取消息,并對消息保存到消息隊(duì)列中,保存時可以根據(jù)Topic進(jìn)行歸類,消息發(fā)送者成為Producer,消息接收者成為Consumer。在本文中,kafka負(fù)責(zé)高吞吐地讀取消息成為消息生產(chǎn)者,kafka還負(fù)責(zé)緩沖消息到消息隊(duì)列中成為消息緩沖中間件,storm實(shí)時讀取緩沖區(qū)的消息并處理成為消息消費(fèi)者。Storm的兩個核心組件spout和bolt,譯為中文為噴口和螺栓更加形象貼切。Spout是storm流處理中流的源頭,本文中的spout負(fù)責(zé)從緩沖隊(duì)列中讀取消息。Bolt是storm流處理中具體的處理單元,本文中的文本分類算法就是運(yùn)行在bolt上的。
通過大量的不同格式的電子文檔的導(dǎo)入,進(jìn)行文本分類,本文的文本分類系統(tǒng)能夠?qū)崟r地處理并返回分類結(jié)果,分類的效果較好,分類準(zhǔn)確率平均在80%。用戶可以通過對文本和分類結(jié)果進(jìn)行比對,反饋給系統(tǒng)人為分類的結(jié)果,系統(tǒng)會根據(jù)反饋的結(jié)果,調(diào)整向量空間模型。通過這樣的不斷迭代反饋,逐步提高分類準(zhǔn)確率。實(shí)驗(yàn)結(jié)果圖如下:
本文所實(shí)現(xiàn)的文本分類系統(tǒng),實(shí)現(xiàn)了對本文開始提出的文本分類目前存在的三個問題數(shù)據(jù)量大、非結(jié)構(gòu)化、動態(tài)性的解決,為傳統(tǒng)的文本分類方式注入新鮮的血液。
本文所提出的文本分類系統(tǒng),仍然存在一些問題,具體體現(xiàn)在:
1)半監(jiān)督的學(xué)習(xí)模式。這種學(xué)習(xí)模式需要人為地干預(yù),這樣會一定程度上把分類的準(zhǔn)確性寄托在人為分類的基礎(chǔ)之上。
2)文本分類結(jié)果的準(zhǔn)確率上。本文實(shí)驗(yàn)的文本分類準(zhǔn)確率在80%,除了通過自學(xué)習(xí)這種“后天學(xué)習(xí)”方式來提高準(zhǔn)確率,還需提高“先天”的向量空間模型的建立以及分類算法的選擇上。
[1] 龐劍鋒, 卜東波, 白碩. 基于向量空間模型的文本自動分類系統(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é)報(自然科學(xué)版), 2003, 09: 1288-1291.
[3] 黃萱菁, 夏迎炬, 吳立德. 基于向量空間模型的文本過濾系統(tǒng)[J]. 軟件學(xué)報, 2003, 03: 435-442.
[4] 周炎濤, 唐劍波, 吳正國. 基于向量空間模型的多主題Web文本分類方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2008, 01: 142-144.
[5] 李文波, 孫樂, 張大鯤. 基于Labeled-LDA模型的文本分類新算法[J]. 計(jì)算機(jī)學(xué)報, 2008, 04: 620-627.
[6] 馬凱航, 高永明, 吳止鍰, 等. 大數(shù)據(jù)時代數(shù)據(jù)管理技術(shù)研究綜述[J]. 軟件, 2015, 36(10): 46-49.
[7] 謝子超. 非結(jié)構(gòu)化文本的自動分類檢索平臺的研究與實(shí)現(xiàn)[J]. 軟件, 2015, 36(11): 112-114.
[8] 路同強(qiáng). 基于半監(jiān)督學(xué)習(xí)的微博謠言檢測方法[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