论文部分内容阅读
近年来,随着信息技术的高速发展,全球信息量迅猛增长,“大数据”时代已经到来。文本分类技术可以按照文本的主题对文本进行归类,从而方便组织和管理海量文本数据。经典KNN分类算法具有实现简单、分类结果稳定和准确性高等特点,但其计算量大,分类用时较长。本文提出了一种SKNN分类算法,可以有效降低KNN的时间复杂度。此外,在处理海量文本数据时,基于单机的传统文本分类技术在存储和计算能力两个方面都表现不足,开源云计算平台Hadoop提供海量数据存储和并行计算的解决方案。本文主要研究基于Hadoop的SKNN文本分类算法的设计与实现。文本预处理和文本分类是文本分类技术的两个重要的步骤。本文在文本预处理阶段的工作中,考虑到单个文本属于小文件的特点,结合HDFS分布式文件系统对数据的管理方式,设计了文本数据集在HDFS中的存储策略。分析了中文分词、去停用词、特征选择和文本表示的过程和相关计算所需的词频、文档频率等统计量,结合MapReduce计算模型,设计实现了将整个文本预处理过程进行并行化处理的方法。在对46.9M、93.8M、234M、469M和938M五个不同数据量的文本数据进行预处理的实验结果表明,Hadoop处理较大的数据更有优势,另外在处理相同数据量的数据时,多节点的集群比单节点的集群速度更快,且数据越大速度提高的效果越明显。本文在文本分类阶段的工作中,针对经典KNN分类算法的不足,提出了一种划分子类的SKNN分类算法。该算法吸收了急迫性学习算法的思想,在训练阶段通过给每个类别划分S个子类来构造初级分类器,测试文本先找出距离最近的K个子类,再从K个子类中找出最近的K个文本来判别测试文本的类别,通过降低了需要进行比较的训练文本数,减少了计算量。本文分析了SKNN分类算法的正确性和时间复杂度小于经典KNN算法。在对大量待测文本数据进行分类时,基于MapReduce的SKNN分类算法可以提高分类的效率。实验结果表明在分类准确度相当的情况下,SKNN分类算法所需分类时间比经典KNN分类算法少,另外,Hadoop处理大量文本数据分类问题能够发挥其时间上的优势。本文在文本分类技术及其并行化方面进行了研究与设计。结果表明,基于Hadoop的SKNN文本分类算法是一种有效的方法。进一步工作可以对朴素贝叶斯和支持向量机分类算法进行并行化研究。