论文部分内容阅读
摘 要：支持向量机（SVM）是最常用的文本分类算法之一，但文本特征空间维数巨大的问题会影响分类的效果。为此，提出了一种提高SVM分类性能的方法。本文利用LPP算法对特征空间的维数进行降维，然后用SVM算法进行分类。实验结果证明，该算法能够有效地提高分类的准确率。
关键词：Rocchio算法；LPP算法；文本分类
引言
随着互联网的快速增长，信息资源也飞速的增多，形式也多种多样，其中文本占大多数。那么怎样从大量的文本信息中搜索到自己想要的信息[1]，就成为了人们关注的焦点。文本分类技术在信息检索中起着重要的作用，因此，文本分类技术的成为了研究的对象。本文是对特征维数在利用互信息进行特征提取的基础上，然后采用LPP进行降维，从而提高了Rocchio分类器的分类性能。
1.Rocchio算法
Rocchio算法[2]又称为类中心最近距离判别算法，是基于向量空间模型和最小距离的算法，最早是由Hull提出来的，它是通过信息检索中用来计算“询问”与文本间的关联程度Rocchio公式改造而来的。由于Rocchio分类器非常的直观和简单，使得它广泛应用于文本分类领域中。
Rocchio算法的训练过程的目的是获得所有类别的中心向量，分类阶段是计算测试集文本与每一个类别中心向量的相似度，相似度最大的类别就是测试集文本所属的类别。Rocchio算法对于类间距离较大而类内距离较小的类别分布情况能达到较好的分类效果。这种算法计算简单、迅速，因此采用它有助于节省时间，提高效率。其计算类中心向量Oj公式为：
其中，Nj表示第Cj类中文本的总数，Yij表示类别Cj中的第i个文本向量。
向量相似度的度量方法有夹角余弦、向量内积、欧氏距离等，本文采用的是夹角余弦的方法，即
总的来说，Rocchio算法分类原理简单，且在进行训练和分类时计算量也相对较小，分类速度较快。
2.LPP算法
LPP算法具有保持数据集的局部非线性流行结构信息的能力，计算简单，处理速度快等特点，利用该算法可以大大减少参与比较的向量文本的数目，其基本思想是通过原始空间中离得近的点在降维后的低维空间中也保持较近，因此能保留原始数据的局部结构。
LPP算法过程为：m给定个数据点构成的集合 ，每个数据点属于高维空间Rn。[需要找到一个转移矩阵A，将这m个数据点映射到另一组点集合
3.基于LPP和Rocchio文本分类算法
本文在常用的文本分类技术之上，先采用LPP算法对特征维数进行降维，然后采用Rocchio算法进行文本分类，其算法步骤如下：
（1）依据训练文本的特征集合，建立训练文本向量空间模型，即对于文本集合 ，它的特征词集合 其中，Ti为特征词是一维的。用m维的向量 来表示文档di，而Wij的值用TF/IDF来计算第 维特征词在文档di中的权重；
（2）将样本E，先利用信息增益提取特征，再利用LPP算法使向量di再次降维；
（3）待分类文本利用（1）的方法表示成向量的形式；
（4）用Rocchio算法进行分类。
4.实验测试与分析
为了验证其效果，需要用实验证明。本文的实验数据来自于复旦大学中文语料库，其中包括：科技、医药、生活、教育、娱乐、军事、艺术、建筑、交通、体育十个领域类，共2850篇，从中共选取了2192篇作为训练样本集，其余的文本作为测试样本集。
采用分词程序IKAnalyzer3.2.8对文本进行分词，用信息增益进行特征选取，再用TF/IDF计算文本特征词的权重值。评价分类效果，通常用查全率、查准率、F1测试值来进行评估。
其中：
查全率=分类正确文本数/类内应有的文本数
查准率=分类正确文本数/实际分类的文本数
F1=（查准率×查全率×2）/（查准率+查全率）
实验结果如表1所示：
从表1可以看出，对于每一个类别，在查全率、查准率及F1测试值上，本文算法要比传统的Rocchio算法都有所提高。本文算法比传统的Rocchio算法在平均查全率，平均查准率及F1测试值上有所提高，因此，本文算法确实提高了分类器的分类性能。
5.总结
本文是在通常的文本分类技术上，运用了LPP算法对特征维数进行降维，实验结果可以看出，本文算法比传统的Rocchio的分类效果要好。分类器的构造是文本分类的关键，还需进一步的研究。
参考文献：
[1]梁俊杰，冯玉才.LBD：基于局部位码比较的高维空间KNN搜索算法.2007； 34（6）：145-148，161.
[2]张征杰，王自强.文本分类及算法综述[J].电脑知识与技术.2012.
[3]周志华，杨强.机器学习及其应用2011[M].清华大学出版社，2011：20-22.
关键词：Rocchio算法；LPP算法；文本分类
引言
随着互联网的快速增长，信息资源也飞速的增多，形式也多种多样，其中文本占大多数。那么怎样从大量的文本信息中搜索到自己想要的信息[1]，就成为了人们关注的焦点。文本分类技术在信息检索中起着重要的作用，因此，文本分类技术的成为了研究的对象。本文是对特征维数在利用互信息进行特征提取的基础上，然后采用LPP进行降维，从而提高了Rocchio分类器的分类性能。
1.Rocchio算法
Rocchio算法[2]又称为类中心最近距离判别算法，是基于向量空间模型和最小距离的算法，最早是由Hull提出来的，它是通过信息检索中用来计算“询问”与文本间的关联程度Rocchio公式改造而来的。由于Rocchio分类器非常的直观和简单，使得它广泛应用于文本分类领域中。
Rocchio算法的训练过程的目的是获得所有类别的中心向量，分类阶段是计算测试集文本与每一个类别中心向量的相似度，相似度最大的类别就是测试集文本所属的类别。Rocchio算法对于类间距离较大而类内距离较小的类别分布情况能达到较好的分类效果。这种算法计算简单、迅速，因此采用它有助于节省时间，提高效率。其计算类中心向量Oj公式为：
其中，Nj表示第Cj类中文本的总数，Yij表示类别Cj中的第i个文本向量。
向量相似度的度量方法有夹角余弦、向量内积、欧氏距离等，本文采用的是夹角余弦的方法，即
总的来说，Rocchio算法分类原理简单，且在进行训练和分类时计算量也相对较小，分类速度较快。
2.LPP算法
LPP算法具有保持数据集的局部非线性流行结构信息的能力，计算简单，处理速度快等特点，利用该算法可以大大减少参与比较的向量文本的数目，其基本思想是通过原始空间中离得近的点在降维后的低维空间中也保持较近，因此能保留原始数据的局部结构。
LPP算法过程为：m给定个数据点构成的集合 ，每个数据点属于高维空间Rn。[需要找到一个转移矩阵A，将这m个数据点映射到另一组点集合
3.基于LPP和Rocchio文本分类算法
本文在常用的文本分类技术之上，先采用LPP算法对特征维数进行降维，然后采用Rocchio算法进行文本分类，其算法步骤如下：
（1）依据训练文本的特征集合，建立训练文本向量空间模型，即对于文本集合 ，它的特征词集合 其中，Ti为特征词是一维的。用m维的向量 来表示文档di，而Wij的值用TF/IDF来计算第 维特征词在文档di中的权重；
（2）将样本E，先利用信息增益提取特征，再利用LPP算法使向量di再次降维；
（3）待分类文本利用（1）的方法表示成向量的形式；
（4）用Rocchio算法进行分类。
4.实验测试与分析
为了验证其效果，需要用实验证明。本文的实验数据来自于复旦大学中文语料库，其中包括：科技、医药、生活、教育、娱乐、军事、艺术、建筑、交通、体育十个领域类，共2850篇，从中共选取了2192篇作为训练样本集，其余的文本作为测试样本集。
采用分词程序IKAnalyzer3.2.8对文本进行分词，用信息增益进行特征选取，再用TF/IDF计算文本特征词的权重值。评价分类效果，通常用查全率、查准率、F1测试值来进行评估。
其中：
查全率=分类正确文本数/类内应有的文本数
查准率=分类正确文本数/实际分类的文本数
F1=（查准率×查全率×2）/（查准率+查全率）
实验结果如表1所示：
从表1可以看出，对于每一个类别，在查全率、查准率及F1测试值上，本文算法要比传统的Rocchio算法都有所提高。本文算法比传统的Rocchio算法在平均查全率，平均查准率及F1测试值上有所提高，因此，本文算法确实提高了分类器的分类性能。
5.总结
本文是在通常的文本分类技术上，运用了LPP算法对特征维数进行降维，实验结果可以看出，本文算法比传统的Rocchio的分类效果要好。分类器的构造是文本分类的关键，还需进一步的研究。
参考文献：
[1]梁俊杰，冯玉才.LBD：基于局部位码比较的高维空间KNN搜索算法.2007； 34（6）：145-148，161.
[2]张征杰，王自强.文本分类及算法综述[J].电脑知识与技术.2012.
[3]周志华，杨强.机器学习及其应用2011[M].清华大学出版社，2011：20-22.