基于密度的样本裁剪算法的改进及在kNN中的应用研究

摘要

随着信息技术的飞速发展和迅速普及，人们可以方便快捷地获得大量的信息。
　　 然而，在浩瀚的信息海洋里，如何快速准确地找到所需要的信息已经成为人们不得不面对的现实问题。因此，海量信息的组织管理和高效利用已经成为急需解决的问题。目前，大多数信息表现为文本形式，为了有效利用这些文本信息，对它们进行高效、合理的分类是非常必要的。所以，文本分类已经成为处理大量文本信息的关键技术，并已成为数据挖掘领域中一个重要的研究方向。
　　 本文对文本分类及其相关技术进行了研究。首先介绍了文本分类的发展概况和文本分类过程中的相关技术，重点介绍了文本预处理、文本的表示、文本特征向量的提取、特征向量的加权、文本分类的经典算法kNN（k nearest neighbor)、训练样本裁剪算法以及文本分类效果评估等；其次，分析了kNN 算法和训练样本裁剪算法的不足并对其做出了改进。本文研究内容和创新工作主要包括以下两大方面：
　　 第一，对训练样本裁剪算法进行改进。在文本分类中，训练集的分布状态会直接影响kNN 分类器的效率和准确率。通过分析基于密度的kNN文本分类器训练样本的裁剪方法，发现它存在两大不足：一是裁减之后的均匀状态只是以e 为半径的球形区域意义上的均匀状态，而非最理想的均匀状态即两两样本之间的距离相等；二是未对低密度区域的样本做任何处理，裁减之后仍存在大量不均匀的区域。
　　 针对这两处不足，提出了以下两点改进：一是优化了裁减策略，使裁减之后的训练集更趋于理想的均匀状态；二是实现了对低密度区域样本的补充。通过实验表明，改进后的算法在稳定性和准确率方面都有明显提高。
　　 第二，对kNN算法进行改进。原始kNN 算法中最佳k值的确定目前还没有很好的方法，一般采用先设定一个初始值（一般为几百到几千之间），然后根据实验测试的结果来不断的调整k 值。这不利于kNN算法在实际中的推广应用。针对这种不足，本文在基于密度的训练样本裁剪算法的基础上提出一种改进算法。改进算法的基本思路是：在给定新文本后，考虑训练文本集中，属于该新文本的e邻域的k篇文本，根据这k篇文本所属的类别判定新文本所属的类别。通过实验表明，改进算法较好的解决了kNN算法中参数k 取值的问题，同时，在时间效率上也要优于原始kNN算法。在分类效果上，改进算法跟原始kNN 算法基本一致。

目录

文摘

英文文摘

1 绪 论

2 文本分类技术

3 裁剪算法的改进

4 kNN 算法的改进

5 论文总结与展望

致 谢

参考文献

附 录