基于遗传算法的文本分类技术

摘要：针对常用的文本分类算法参数难以确定的问题，该文引入遗传算法，在编码方案、种群的初始化、适应度函数和停止标准等方面进行优化，得到更好的文本分类结果。通过三种文本分类算法的对比实验，该文提出的算法效果最好。

关键词：文本分类；遗传算法；适应度函数

中图分类号：TP18 文献标识码：A文章编号：1009-3044(2011)22-5425-02

The Technology of Text Classification Based on Genetic Algorithm

WU Mou-shuo

(Compute and Experiment Center, South Central University for Nationality, Wuhan 430074, China)

Abstract: For the puzzle of parameter ascertainment in text classification, this paper proposed genetic algorithm. In the period of encoding, we used float encoding. In the period of population initiation, fitness function and stop criterion, we optimized several parameters and strategies to obtain better result. Experiments of three text classifications showed that our method performed the best.

Key words: text classification; genetic algorithm; fitness function

人们需要从海量信息中快速、准确地获取有用信息。文本分类在自然语言处理与理解、信息组织与管理、内容信息过滤等领域都有广泛的应用。现在主流的文本分类方法是基于机器学习的方法, 此方法首先使用训练样本进行特征选择和分类器训练, 然后把特征形式化，待分类样本输人到分类器进行类别判定, 最终得到输人样本的类别。文本分类的方法有很多种，如Rocchio 方法[1] 早就提出了、K-近邻（K-Nearest Neighbours）方法[2] 早就提出了、贝叶斯（Naive Bayes）方法[3] 早就提出了、而且支持向量机（Support Vector Machine, SVM）算法[4]、还有决策树（Decision Tree）方法[5]和以及神经网络（Neural Networks）方法[6]等都已经有了。

文本分类中的许多问题，如果进行适当的转换，可以看作优化问题。本文将遗传算法引入文本分类的过程中，在种群的初始化、适应度函数和遗传算法的停止标准等方面进行优化，得到更好的文本分类结果。

本文第二部分详细描述了基于遗传算法的文本分类技术，第三部分是本文的实验与结果分析部分，第四部分是结论与将来的工作。

1 基于遗传算法的文本分类算法

文本特征表示时经常是采用向量空间模型方法来表示文本，对文本的特征进行刻画。文本特征权重计算的前提是进行文本特征抽取。

相似性的计算公式有相关系数法，还有距离函数法等。本文相似度仍然采用向量夹角余弦公式来计算。具体计算公式如下：

(1)

用遗传算法进行分类时，要考虑遗传因子、适应度函数和遗传算法的停止标准等关键因素。

在种群初始化的时候，我们并不采用随机数生成算法，而是通过随机选择样本点，避免了随机数生成法必须人为确定随机数上下限的缺点。

如果类中心已经确定，那类的划分算法可以采用最邻近算法进行计算。

我们将遗传算法的适应度函数定义如下：

(2)

选择策略对遗传算法的效果有比较重的影响。第i文本Indi可以按照概率Ps(Indi)选择出来，这样可以提高种群的适应度。第i文本Ps(Indi)可以用下面的公式进行计算。

(3)

在遗传算法中，当文本类别划分不再发生变化，或者是迭代次数达到最大值时停止。

2 实验结果与分析

为了使本文提出的文本分类技术得到的结果具有可比性，本文将Naive Bayes分类方法和支持向量机算法引入，进行对比实验。

Naive Bayes算法可以说是一种有效的分类方法。假设在某种语境环境里，文档之间是相互独立的。令di为文档标志，该文档di包含于文档类别集合C={c1, c2,…, ck}中间的某一个类别cj里面。根据Naive Bayes算法有下面公式：

(4)

(5)

在这种情况下，需要计算在di已经知道的情况下的条件概率，取最后概率值最大的类别作为di所在的类别，也就是：

(6)

采用多项式模型进行计算，则在文档类别情况已经知道的情况下文档di的概率计算公式为：

(7)

但是，上面的概率可能会出现0，所以使用+1平滑技术对其进行处理。

几种常用的文本分类评价指标包括准确率、召回率、F-measure，用这三个参数对系统进行客观评测，这三个参数具体含义如下：

准确率的定义。对于一个文档集i和一个分类j, 假设N为在文档集i中属于类别j的数目, M为文档集i中所有文档的数目,则准确率P定义为:

P = N/M(8)

召回率的定义。对于一个文档集i和一个分类j, 假设N为在文档集i中属于分类j的数目, K为分类j中所有文档的数目,则召回率R定义为:

R = N/K(9)

准确率P衡量的是所有被分到类别j的文档中,正确文档的比率; 召回率R衡量的是所有实际属于类别j的文档被分到该类别中的比率。只用其中之一进行评价可能有失偏颇，F-measure指标是上述召回率和准确率的综合，能正确反映文本分类在召回率和准确率平衡方面的效果，其具体计算公式可以表达成：

(10)

对于中文语料的实验，我们从新浪、腾讯等网站上下载了2000个网页，从中提取出2000篇文档,根据语料主题分为10类:军事(200篇) 、体育(200篇) 、政治(200篇) 、环境(200篇) 、交通(200篇) 、艺术( 200篇) 、医药 (200篇) 、经济(200篇) 、教育(200篇) 、健康(200篇)。实验结果如表1所示。

3 结论与将来的工作

文本分类是文本挖掘中的一个重要工具，应用非常广泛，针对常用的文本分类算法参数难以确定的问题，本文引入遗传算法，在编码方案、种群的初始化、适应度函数和停止标准等方面进行优化，得到更好的文本分类结果。通过三种文本分类算法的对比实验，本文提出的算法效果最好。

在下一步的工作中，我们将继续研究不同环境下适应度函数的合适表达方式，同时，进一步研究和分析选择策略，让遗传算法的收敛速度更快，效果更好。

参考文献：

[1] Joachims T.A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization.Proc of ICML'97,1997.

[2] Yang Y.Expert network: Effective and efficient learning from human decisions in text categorization and retrieval.Proc of SIGIR'94,1994:13-22.

[3] Baker L D,Mccallum A K.Distributional clustering of words for text categorization.Proc of SIGIR'98,1998:96-103.

[4] Cortes C,Vapnik V.Sup of event models for naive port vector networks.Machine Learning,1995(20):1-25.

[5] Lewis D D,Ringuette parison of two learning algorithms for text categorization.Proc of SDAIR,1994:81-93.

[6] Wiener E,Pedersen J O,Weigend A S.A Neural Network Approach to Topic Spotting.Proc of SDAIR'95,1995:317-332.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文