基于向量空间模型的文本自动分类系统的研究与实现
Research and Implementation of Text Categorization System Based on VSM
(Pang jianfeng) (Bu dongbo) (Bai shuo)
Institute of Computing Technology , CAS 100080E-mail: pangjf@ncic.ac.cn
TP391
AbstractIn 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 . It also describes a text categorization model based on VSM, and gives the evaluations and results .
Key wordsText Categorization Chinese Information Processing Vector Space Model
Internet 2问题描述
2.2
F1
另外有微平均和宏平均两种计算准确率、查全率和 F1 值的方法。
微平均：计算每一类的准确率、查全率和 F1 值。
宏平均：计算全部类的准确率、查全率和 F1 值。
3 关键技术
3.1 0 1目前，在信息处理方向上，文本的表示主要采用向量空间模型 (VSM)。向量空间模型的基本思想是以向量来表示文本：（W1,W2,W3……Wn），其中 Wi 为第 i 个特征项的权重，那么选取什么作为特征项呢，一般可以选择字、词或词组，根据实验结果，普遍认为选取词作为特征项要优于字和词组，因此，要将文本表示为向量空间中的一个向量，就首先要将文本分词，由这些词作为向量的维数来表示文本，最初的向量表示完全是 0、1 形式，即，如果文本中出现了该词，那么文本向量的该维为 1，否则为 0。这种方法无法体现这个词在文本中的作用程度，所以逐渐 0、1 被更精确的词频代替，词频分为绝对词频和相对词频，绝对词频，即使用词在文本中出现的频率表示文本，相对词频为归一化的词频，其计算方法主要运用 TF-IDF 公式，目前存在多种 TF-IDF 公式，我们在系统中采用了一种比较普遍的 TF-IDF 公式：
其中， 为词 t 在文本 中的权重，而 为词 t 在文本 中的词频，N 为训练文本的总数， 为训练文本集中出现 t 的文本数，分母为归一化因子。
另外还存在其他的 TF-IDF 公式，例如：
文本经过分词程序分词后，首先去除停用词，合并数字和人名等词汇，然后统计词频，最终表示为上面描述的向量。
3.2 构成文本的词汇，数量是相当大的，因此，表示文本的向量空间的维数也相当大，可以达到几万维，因此我们需要进行维数压缩的工作，这样做的目的主要有两个，第一，为了提高程序的效率，提高运行速度，第二，所有几万个词汇对文本分类的意义是不同的，一些通用的、各个类别都普遍存在的词汇对分类的贡献小，在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分类的贡献大，为了提高分类精度，对于每一类，我们应去除那些表现力不强的词汇，筛选出针对该类的特征项集合，存在多种筛选特征项的算法，如下所列：
1． 根据词和类别的互信息量判断
2． 根据词熵判断
3． 根据KL距离判断
在我们的系统中采用了词和类别的互信息量进行特征项抽取的判断标准，其算法过程如下所列：
STEP ONE:初始情况下，该特征项集合包含所有该类中出现的词。
STEP TWO:对于每个词，计算词和类别的互信息量
其中， ， 为 W 在 中出现的比重， 为该类的训练文本数， 为词 在 中的词频， 为总词数， 为该类所有词的词频和。
而 同上面的计算公式相同，只是计算词在所有训练文本中的比重，其中， 为全体训练文本数。
STEP THREE:对于该类中所有的词，依据上面计算的互信息量排序。
STEP FOUR:抽取一定数量的词作为特征项，具体需要抽取多少维的特征项，目前无很好的解决方法，一般采用先定初始值，然后根据实验测试和统计结果确定最佳值，一般初始值定在几千左右。
STEP FIVE:将每类中所有的训练文本，根据抽取的特征项，进行向量维数压缩，精简向量表示。
3.3 训练方法和分类算法是分类系统的核心部分，目前存在多种基于向量空间模型的训练算法和分类算法，例如，支持向量机算法、神经网络方法，最大平均熵方法，最近 K 邻居方法和贝叶斯方法等等，本文以下具体介绍三种分类算法：
1. 简单向量距离分类法
该方法的分类思路十分简单，根据算术平均为每类文本集生成一个代表该类的中心向量，然后在新文本来到时，确定新文本向量，计算该向量与每类中心向量间的距离（相似度），最后判定文本属于与文本距离最近的类，具体步骤如下：
STEP ONE:计算每类文本集的中心向量，计算方法为所有训练文本向量简单的算术平均
STEP TWO:新文本到来后，分词，将文本表示为特征向量
STEP THREE:计算新文本特征向量和每类中心向量间的相似度，公式为：
其中， 为新文本的特征向量， 为第 j 类的中心向量，M 为特征向量的维数， 为向量的第 K 维。
STEP FOUR:比较每类中心向量与新文本的相似度，将文本分到相似度最大的那个类别中。
2. 贝叶斯算法
该算法的基本思路是计算文本属于类别的概率，文本属于类别的几率等于文本中每个词属于类别的几率的综合表达式，具体算法步骤如下：
STEP ONE:计算特征词属于每个类别的几率向量，
其中， ，计算公式与计算互信息量的公式相同
STEP TWO:在新文本到达时，根据特征词分词，然后按下面的公式计算该文本 属于类 的几率：
其中， ， 为相似含义， 为类的总数， 为 在 中的词频，n 为特征词总数。
STEP THREE:比较新文本属于所有类的几率，将文本分到几率最大的那个类别中。
3. KNN（K 最近邻居）算法
该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距离最近（最相似）的 K 篇文本，根据这 K 篇文本所属的类别判定新文本所属的类别，具体的算法步骤如下：
STEP ONE:根据特征项集合重新描述训练文本向量
STEP TWO:在新文本到达后，根据特征词分词新文本，确定新文本的向量表示
STEP THREE:在训练文本集中选出与新文本最相似的 K 个文本，计算公式为：
其中，K 值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整 K 值，一般初始值定为几百到几千之间。
STEP FOUR:在新文本的 K 个邻居中，依次计算每类的权重，计算公式如下：
其中， 为新文本的特征向量， 为相似度计算公式，与上一步骤的计算公式相同，而 为类别属性函数，即，如果 属于类 ，那么函数值为 1，否则为 0。
STEP FIVE:比较类的权重，将文本分到权重最大的那个类别中。
除此以外，支持向量机和神经网络算法在文本分类系统中应用得也较为广泛，支持向量机的基本思想是使用简单的线形分类器划分样本空间。对于在当前特征空间中线形不可分的模式，则使用一个核函数把样本映射到一个高维空间中，使得样本能够线形可分。
3.4 上面的算法都是将新文本归于分类体系中的一个类，即与该文本关联最大的类，而事实上，分类体系中的类别不是完全互斥的，存在这样一些既属于其中一个类别，又同时属于其他类别的文本，对于这种文本，上述的分类算法无法确定文本所属的所有类别。因此，需要对每个类别确定阈值，当文本在该类的阈值之上时，就将文本归于该类中。
但是，阈值的确定是十分困难的，理论上，没有很好的解决方法，一般采用预定初始值，然后给出测试文本，使用分类器进行分类，再根据分类的准确程度调整初始值，这样的方法有两个缺点，首先，初始值的确定不容易，完全是根据经验或简单的测试而定，其次，调整的幅度无法确定，当初始值过高或过低需要增减时，增减的幅度无法很好的确定，只能反复测试，反复调整，这样就大大地增加了工作量。而且，一个分类系统的阈值由于测试文本的不同也无法完全应用于另一个分类系统中。
我们在系统中考虑了一种确定阈值的方法，称为百分比阈值确定法，它的基本思想是：首先依据上述训练算法和分类算法构造分类器，然后对于要确定阈值的类，用分类器分类该类中所有的训练文本，从而每个文本都得到一个相关的值，以上述算法为例：
简单向量距离分类法：文本与本类中心向量间的相似度值
贝叶斯算法：文本归属于类的几率
KNN 算法：K 个邻居中的类权重
然后按递减顺序排列所有本类训练文本得到的值，假定本类有 n 篇文本，那么这些文本的值为 ，那么本类阈值 y 确定如下：
其中，s 为初始值，根据训练文本的质量程度，可以确定为 80 或更高，这样就确定了本类的初始阈值，可以想象，S 越大，该分类器的查全率就越高，准确度就越低，相反地，S 越小，查全率就越低，准确率就越高，然后根据测试进行调整。
相应地，调整阈值可以转化为调整 s 值，如果对查全率满意而对准确率不满意，那么可以减少 s 值，否则就增加 s 值。
|
我们在一个具有2830篇中文文本的语料库上测试我们系统实现的分类算法，并对其效率和结果进行比较分析。
语料库中的文本都是新闻电讯稿，绝大部分采自新华社，还有200余篇采自中国新闻社和人民日报。所有的新闻稿都由领域专家事先进行分类，按照中图分类法分成政治、经济、军事等共38类。我们选择训练集和测试集的方法如下：将这些分好类的语料平均分成十份，选择其中一份作为开放测试集，剩余的九份作为训练集和封闭测试集。这样每一份都依次轮流作为开放测试集，运行分类算法，共执行10次分类操作，计算其平均值，实验结果如下表所示：
|
F1
F1
|
87.08%
|
87.08%
|
87.08%
|
80.23%
|
80.23%
|
80.23%
|
|
82.39%
|
83.78%
|
83.08%
|
76.17%
|
77.26%
|
76.71%
|
|
KNN
|
89.11%
|
91.42%
|
90.25%
|
83.29%
|
85.12%
|
84.20%
|
m k n
|
|
O (mn)
|
O (kn)
|
|
O (mn)
|
O (kn)
|
|
KNN
|
O (km+nm)
|
KNN 6 将来的工作
1. 2. 3. 7 结束语
1. David D. Lewis: Feature selection and feature extraction for text categorization, In Proceedings of Speech and Natural Language Workshop, pp 212-217. Defense Advanced Research Projects Agency, Morgan Kaufmann, February 1992
2. Yiming Yang: An evaluation of statistical approaches to text categorization, In Journal of Information Retrieval, 1999, Vol 1, No. 1/2, pp 67--88
3. David D. Lewis and Marc Ringuette: A comparison of tow learning algorithms of text categorization , In Third Annual Symposium on Document Analysis and Information Retrieval, pp 81-93, Las Vegas, NV, April 11-13 1994. ISRI; Univ. of Nevada, Las Vegas
4. Andrew McCallum and Kamal Nigam: A comparison of event models for naive bayes text categorization , AAAI-98 Workshop on "Learning for Text Categorization",1998
5. Yiming Yang and Xin Liu: A re-examination of text categorization methods , Proceedings of ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), 1999, pp 42--49
6. 2000 International Conference on Multilingual Information Processing , pp 37-43 , 2000
7. 2000 International Conference on Multilingual Information Processing , pp 31-36 , 2000
8. / 2000 11
|
|
|
|
|
|
|