基于二階隱馬爾可夫模型的新聞分類(lèi)算法

孫璇　李魯群　江龍泉

摘 要： 提出一種基于二階隱馬爾可夫模型（HMM）的新聞分類(lèi)算法，旨在提取新聞內(nèi)容中的類(lèi)別字，構(gòu)成特征詞集合.以該特征詞集合作為不同二階HMM分類(lèi)器的觀察序列，二階HMM的隱藏狀態(tài)反映了文檔中詞語(yǔ)之間的相關(guān)性差異，每個(gè)狀態(tài)表示出現(xiàn)在語(yǔ)料庫(kù)中的詞語(yǔ)的相關(guān)性水平.實(shí)驗(yàn)結(jié)果表明，相比k近鄰（kNN）、樸素貝葉斯（Naive Bayes）以及支持向量機(jī)（SVM）算法，二階HMM算法的分類(lèi)表現(xiàn)更顯優(yōu)勢(shì).

關(guān)鍵詞： 新聞分類(lèi)； 二階隱馬爾可夫模型（HMM）； 詞頻率-逆向文件頻率； χ2檢驗(yàn)； 特征詞

中圖分類(lèi)號(hào)： TP 391 文獻(xiàn)標(biāo)志碼： A 文章編號(hào)： 1000-5137（2018）04-0488-06

Abstract： A novel algorithm based on second order Hidden Markov Model （HMM） was proposed to classify the documents of news，aiming to extract categorical feature words from news contents as a feature set.The feature set was considered as the observation sequence of different second order HMM classifiers，and the hidden state of which reflected the differences between the words in the relevant documents，and each state of which represented correlation of words occurring in the corpus.The experiment showed that the proposed classification algorithm based second order HMM had prominent advantage over k-Nearest Neighbor （kNN），Naive Bayes and Support Vector Machine （SVM） algorithms.

Key words： news classification； second order Hidden Markov Model（HMM）； term frequency-inverse document frequency； χ2 test； feature word

0 引 言

文本分類(lèi)被認(rèn)為是當(dāng)下數(shù)據(jù)挖掘領(lǐng)域最熱門(mén)的研究方向之一，許多自動(dòng)分類(lèi)和自組織文本文檔技術(shù)在過(guò)去二十年里被相繼提出[1-5].常用的分類(lèi)算法有k近鄰（kNN）、樸素貝葉斯（Naive Bayes）及支持向量機(jī)（SVM）算法.

隱馬爾可夫模型（HMM）[6-7]用于描述一類(lèi)重要的隨機(jī)過(guò)程，廣泛應(yīng)用于語(yǔ)音識(shí)別、詞性標(biāo)注、中文分詞等領(lǐng)域.現(xiàn)如今，HMM的應(yīng)用正逐漸擴(kuò)展至文本處理領(lǐng)域，如信息抽取[8]、信息檢索[9]、文檔歸類(lèi)[10]以及文本分類(lèi)[11].

專(zhuān)業(yè)人員針對(duì)HMM進(jìn)行了大量研究.Li等[11]構(gòu)建了一個(gè)HMM與χ2檢驗(yàn)相結(jié)合的分類(lèi)器，反映不同類(lèi)別中的語(yǔ)義關(guān)系；Janecek等[12]采用HMM構(gòu)建了一個(gè)信息抽取模型，計(jì)算文檔與用戶查詢(xún)相關(guān)的概率；Yi等[13]視文本分類(lèi)過(guò)程為找到一個(gè)與給定文檔相關(guān)類(lèi)別的過(guò)程，文檔被視為一個(gè)詞列表，利用特定的HMM模型計(jì)算文檔屬于該類(lèi)別的概率；Vieira等[14]基于內(nèi)容對(duì)生物科技文檔進(jìn)行分類(lèi)，著重分析數(shù)據(jù)集中文檔與給定用戶查詢(xún)的相關(guān)性.然而，在上述的研究中，狀態(tài)轉(zhuǎn)換都是以相同的方式順序進(jìn)行排列，沒(méi)有形成狀態(tài)自循環(huán)的HMM，而且認(rèn)為前一詞是后一詞出現(xiàn)的決定因素，但在自然語(yǔ)言中單個(gè)詞出現(xiàn)的概率通常由前幾個(gè)詞同時(shí)決定.因此，采用一階HMM，既不能完全反映語(yǔ)義信息，也無(wú)法準(zhǔn)確地對(duì)狀態(tài)序列進(jìn)行預(yù)測(cè).

本文作者提出一種基于二階隱馬爾可夫模型的新聞分類(lèi)算法，改進(jìn)以往研究中隱藏狀態(tài)的轉(zhuǎn)移概率的計(jì)算方法，結(jié)合互信息與改進(jìn)的詞頻率-逆向文件頻率（TF-IDF）方法計(jì)算發(fā)射概率，反映不同類(lèi)別的語(yǔ)義關(guān)系.實(shí)驗(yàn)表明，該算法的執(zhí)行效果良好.

2 實(shí) 驗(yàn)

2.1 新聞數(shù)據(jù)集

中文數(shù)據(jù)集采用Sogou實(shí)驗(yàn)室提供的搜狐新聞數(shù)據(jù)集，從該數(shù)據(jù)集中選取了3個(gè)類(lèi)別，平均每個(gè)類(lèi)別包含4 000個(gè)文檔，其中訓(xùn)練樣本集、驗(yàn)證樣本集與測(cè)試樣本集按5∶3∶2的比例劃分.該數(shù)據(jù)集的統(tǒng)計(jì)數(shù)據(jù)如表1所示.

英文數(shù)據(jù)集采用摘自The Hindu、The New Indian Express、Business Line、The Economic Times和Times of India五家新聞機(jī)構(gòu)的大約27 000條新聞組成的數(shù)據(jù)集.從該數(shù)據(jù)集中選取3個(gè)類(lèi)別，平均每個(gè)類(lèi)別包含1 200條新聞，其中訓(xùn)練樣本集、驗(yàn)證集與測(cè)試樣本集同樣按5∶3∶2的比例劃分.該數(shù)據(jù)集的統(tǒng)計(jì)數(shù)據(jù)如表2所示.

2.2 實(shí)驗(yàn)結(jié)果

為了與提出的基于二階隱馬爾可夫模型的分類(lèi)算法進(jìn)行比較，采取的對(duì)比策略是在相同的語(yǔ)料庫(kù)和相同的類(lèi)別下構(gòu)建分類(lèi)算法，分別評(píng)估每個(gè)分類(lèi)算法的Precision、Recall以及F1值.Precision和Recall反映了分類(lèi)器性能的兩個(gè)方面，F(xiàn)1值則是為了平衡兩者的影響而引入的.實(shí)驗(yàn)結(jié)果如表3所示.

通過(guò)實(shí)驗(yàn)結(jié)果可以看出，基于二階隱馬爾可夫模型具有較好的性能表現(xiàn)，相較于一階隱馬爾可夫模型，Precision、Recall以及F1值分別提升了3%、1%和2%，主要原因在于二階隱馬爾可夫模型綜合考慮了前兩個(gè)隱藏狀態(tài)值，預(yù)測(cè)可信度更高.

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

本文作者提出了一種基于二階隱馬爾可夫模型的新聞文本分類(lèi)模型，對(duì)體育、娛樂(lè)和政治等類(lèi)別的網(wǎng)絡(luò)新聞進(jìn)行分類(lèi)，應(yīng)用了基于詞相關(guān)性的推理系統(tǒng)，從一組未標(biāo)記的數(shù)據(jù)集區(qū)分出相關(guān)文檔.實(shí)驗(yàn)結(jié)果表明，與kNN、樸素貝葉斯和SVM算法相比，該分類(lèi)算法的性能良好.然而，如何減少訓(xùn)練集的計(jì)算時(shí)間，對(duì)二階HMM尚需進(jìn)一步研究.

參考文獻(xiàn)：

[1] Zanasi A，Zanasi A.Textmining and its applications to intelligence，CRM and knowledge management [M].Southampton：WIT Press，2007.

[2] Kataria A，Singh M D.Areview of data classification using k-nearest neighbour algorithm [J].International Journal of Emerging Technology and Advanced Engineering，2013，3（6）：354-360.

[3] Xu S.Bayesian Nave Bayes classifiers to text classification [J].Journal of Information Science，2016，44（1）：48-59.

[4] Haddoud M，Mokhtari A，Lecroq T，et al.Combining supervised term-weighting metrics for SVM text classification with extended term representation [J].Knowledge and Information Systems，2016，49（3）：909-931.

[5] Dadgar S M H，Araghi M S，F(xiàn)arahani M M.A novel text mining approach based on TF-IDF and Support Vector Machine for news classification [C].IEEE International Conference on Engineering and Technology.Coimbatore：IEEE，2016.

[6] Haddad K E，Dupont S，Urbain J，et al.Speech-laughs：An HMM-based approach for amused speech synthesis [C].IEEE International Conference on Acoustics，Speech and Signal Processing.Brisbane：IEEE，2015.

[7] Wang L，Soong F K.HMM trajectory-guided sample selection for photo-realistic talking head [J].Multimedia Tools and Applications，2015，74（22）：9849-9869.

[8] Jiménez P，Corchuelo R.Roller：a novel approach toweb information extraction [J].Knowledge & Information Systems，2016，49（1）：197-241.

[9] Paula M C D，Neto F B D L.A new approach using Hidden Markov Model for generating movie captions to aid the hearing impaired，which is capable of visual encoding emotional information [C].Latin America Congress on Computational Intelligence.Curitiba：IEEE，2015：1-5.

[10] Chithra S，Sinith M S，Gayathri A.Musicinformation retrieval for polyphonic signals using Hidden Markov Model [J].Procedia Computer Science，2015，46：381-387.

[11] Li K，Chen G，Cheng J.Research on Hidden Markov Model-basedtext categorization process [J].International Journal of Digital Content Technology & Its Applications，2011，5（6）：244-251.

[12] Janecek A，Gansterer W N，Demel M，et al.On the relationship between feature selection and classification accuracy [J].Journal of Machine Learning Research，2008，4：90-105.

[13] Yi K，Beheshti J.A Hidden Markov Model-based text classification of medical documents [J].Journal of Information Science，2009，35（1）：67-81.

[14] Vieira A S，Iglesias E L，Borrajo L.T-HMM：Anovel biomedical text classifier based on Hidden Markov Models [C].8th International Conference on Practical Applications of Computational Biology & Bioinformatics.Berlin：Springer International Publishing，2014.

（責(zé)任編輯：包震宇）