基于二阶隐马尔可夫模型的新闻分类算法

孙璇　李鲁群　江龙泉

摘 要： 提出一种基于二阶隐马尔可夫模型（HMM）的新闻分类算法，旨在提取新闻内容中的类别字，构成特征词集合.以该特征词集合作为不同二阶HMM分类器的观察序列，二阶HMM的隐藏状态反映了文档中词语之间的相关性差异，每个状态表示出现在语料库中的词语的相关性水平.实验结果表明，相比k近邻（kNN）、朴素贝叶斯（Naive Bayes）以及支持向量机（SVM）算法，二阶HMM算法的分类表现更显优势.

关键词： 新闻分类； 二阶隐马尔可夫模型（HMM）； 词频率-逆向文件频率； χ2检验； 特征词

中图分类号： TP 391 文献标志码： A 文章编号： 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 引 言

文本分类被认为是当下数据挖掘领域最热门的研究方向之一，许多自动分类和自组织文本文档技术在过去二十年里被相继提出[1-5].常用的分类算法有k近邻（kNN）、朴素贝叶斯（Naive Bayes）及支持向量机（SVM）算法.

隐马尔可夫模型（HMM）[6-7]用于描述一类重要的随机过程，广泛应用于语音识别、词性标注、中文分词等领域.现如今，HMM的应用正逐渐扩展至文本处理领域，如信息抽取[8]、信息检索[9]、文档归类[10]以及文本分类[11].

专业人员针对HMM进行了大量研究.Li等[11]构建了一个HMM与χ2检验相结合的分类器，反映不同类别中的语义关系；Janecek等[12]采用HMM构建了一个信息抽取模型，计算文档与用户查询相关的概率；Yi等[13]视文本分类过程为找到一个与给定文档相关类别的过程，文档被视为一个词列表，利用特定的HMM模型计算文档属于该类别的概率；Vieira等[14]基于内容对生物科技文档进行分类，着重分析数据集中文档与给定用户查询的相关性.然而，在上述的研究中，状态转换都是以相同的方式顺序进行排列，没有形成状态自循环的HMM，而且认为前一词是后一词出现的决定因素，但在自然语言中单个词出现的概率通常由前几个词同时决定.因此，采用一阶HMM，既不能完全反映语义信息，也无法准确地对状态序列进行预测.

本文作者提出一种基于二阶隐马尔可夫模型的新闻分类算法，改进以往研究中隐藏状态的转移概率的计算方法，结合互信息与改进的词频率-逆向文件频率（TF-IDF）方法计算发射概率，反映不同类别的语义关系.实验表明，该算法的执行效果良好.

2 实 验

2.1 新闻数据集

中文数据集采用Sogou实验室提供的搜狐新闻数据集，从该数据集中选取了3个类别，平均每个类别包含4 000个文档，其中训练样本集、验证样本集与测试样本集按5∶3∶2的比例划分.该数据集的统计数据如表1所示.

英文数据集采用摘自The Hindu、The New Indian Express、Business Line、The Economic Times和Times of India五家新闻机构的大约27 000条新闻组成的数据集.从该数據集中选取3个类别，平均每个类别包含1 200条新闻，其中训练样本集、验证集与测试样本集同样按5∶3∶2的比例划分.该数据集的统计数据如表2所示.

2.2 实验结果

为了与提出的基于二阶隐马尔可夫模型的分类算法进行比较，采取的对比策略是在相同的语料库和相同的类别下构建分类算法，分别评估每个分类算法的Precision、Recall以及F1值.Precision和Recall反映了分类器性能的两个方面，F1值则是为了平衡两者的影响而引入的.实验结果如表3所示.

通过实验结果可以看出，基于二阶隐马尔可夫模型具有较好的性能表现，相较于一阶隐马尔可夫模型，Precision、Recall以及F1值分别提升了3%、1%和2%，主要原因在于二阶隐马尔可夫模型综合考虑了前两个隐藏状态值，预测可信度更高.

3 结束语

本文作者提出了一种基于二阶隐马尔可夫模型的新闻文本分类模型，对体育、娱乐和政治等类别的网络新闻进行分类，应用了基于词相关性的推理系统，从一组未标记的数据集区分出相关文档.实验结果表明，与kNN、朴素贝叶斯和SVM算法相比，该分类算法的性能良好.然而，如何减少训练集的计算时间，对二阶HMM尚需进一步研究.

参考文献：

[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，Farahani 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.

（責任编辑：包震宇）