改进的KNN方法及其在中文文本分类中的应用.pdfVIP

第27卷第2期 西华大学学报(自然科学版) 2008年3月 VoL27，No．2 ofXihua Science Mall．2008 Journal University·Natural 文章编号：1673-159X(2008)02-0033-36 改进的KNN方法及其在中文文本分类中的应用 刘 博1，杨 柳2，袁 方3 (I．河北农业大学信息科学与技术学院，河北保定071001；2．河北大学经济学院； 3．河北大学数学与计算机学院，河北保定071002) 摘要：介绍了基于KNN方法的中文文本分类流程及相关技术，在分析传统KNN方法不足的基础上提出一 种改进的KNN方法。该方法在特征选取、权值确定、相似度计算等方面进行了改进，并给出了优化措施。实验表 明：与传统的KNN方法相比，改进后的KNN方法在保证分类准确率的同时，使分类效率得到了有效提高。 关键词：文本分类；KNN；特征选取；相似度；优化 中图分类号：TP391 文献标识码：A 随着文本信息的快速增长，尤其是Intemet资为了便于处理，一篇文本通常用由其词集来描述，与 源信息的迅猛发展，文本分类已经成为现代信息处 英文不同，中文中各个词之间没有固定的分隔符，因 理研究的一大热点。作为一种带监督的机器学习过 此分词成为中文文本分类的必需环节，分词的准确 程，文本分类根据预定义的类别信息和训练文本，按 性直接关系到分类的结果。 照某种分类算法，训练生成相应的分类模型，然后利 用模型对未知类别的文本进行自动分类。目前常用 的分类算法主要有朴素贝叶斯方法¨J、KNN方法 ¨J、支持向量机方法(SVM)∞3等。其中基于统计的 KNN算法，具有操作简单，无需训练过程等优点，因 此得到了广泛应用。其主要的不足之处在于随着训 练文本数的增多，会在分类过程中产生较大的计算 开销，从而导致分类效率低下。本文提出了一种改 进的KNN方法，在特征选取、权值确定、相似度计算 等方面较传统KNN方法进行了改进，并给出了优化 措施。与传统的KNN方法相比，在保证分类准确率 图1分类流程图 的同时，有效提高了分类效率。 1 中文文本分类流程及相关技术 即使经过预处理的过程，训练文本所产生的词 中文文本分类的一般流程及所用到的相关技术 条数量仍然过于庞大，而且其中相当一部分词条对 见图l。由图l可见，训练文本在被输入到分类器 分类的准确性没有影响，因此需要进行特征选取以 之前，需经过预处理和特征选取的操作以将其转化 达到降维的目的，特征选取会找出那些具有较高类 为形式化的信息。不同的分类方法所需要的信息不 别区分度的词。常用的特征选取方法都是基于统计 原理。这包括互信息(Mutual 同，对于KNN、SVM方法是基于文本的向量空间模 (CrossEntropy)、信息增益(InformationGain)等旧o。 型(VSM)MJ，对于决策树，关联规则方法则是基于 布尔模型‘引。 通常使用某种特征选取方法进行全局选取，即计算 文本预处理主要包括分词、去停用词等技术。 某个词条与每个类别的相关度，选取平均相关度最 收稿日期：2007—12-28 基金项目：河北省科技攻关计划项目(No；河北省教育厅科研计划项日(No．2004406)。 作者简介：刘博(1981一)，男，河北保定人，助教，硕士，主要从事数据挖掘方面的研究。 万方数据