基于Hadoop的SKNN文本分类算法的设计与实现

摘要

近年来，随着信息技术的高速发展，全球信息量迅猛增长，“大数据”时代已经到来。文本分类技术可以按照文本的主题对文本进行归类，从而方便组织和管理海量文本数据。经典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文本分类算法是一种有效的方法。进一步工作可以对朴素贝叶斯和支持向量机分类算法进行并行化研究。

目录

声明

摘要

第一章 绪论

1．1 课题研究背景及意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．3 研究内容和主要工作

1．4 论文组织结构

第二章 Hadoop平台和文本分类概述

2．1 Hadoop概述

2．1．1 MapReduce

2．1．2 HDFS

2．2 Hadoop平台搭建

2．3 文本分类概述

2．4 本章小结

第三章 基于MapReduce的文本预处理方法

3．1 文本预处理流程

3．1．1 文本集合

3．1．2 中文分词和去停用词

3．1．3 特征选择

3．1．4 文本表示

3．2 基于MapReduce的文本预处理方法实现

3．2．1 语料库预处理

3．2．2 语料库在HDFS中的存储策略

3．2．3 基于MapReduce的特征选择算法

3．2．4 基于MapReduce的TFIDF算法

3．3 实验结果及分析

3．4 本章小结

第四章 基于MapReduce的SKNN分类算法

4．1 KNN分类算法

4．1．1 KNN分类算法概述

4．1．2 KNN分类算法的改进

4．2 划分子类的SKNN分类算法

4．2．1 算法的基本思想

4．2．2 算法正确性分析

4．2．3 算法时间复杂度分析

4．3 基于MapReduce的SKNN分类算法实现

4．4 实验结果及分析

4．4．1 SKNN分类算法准确度和分类速度测试实验

4．4．2 参数K和S对SKNN分类结果的影响实验

4．4．3 Hadoop上SKNN的性能测试实验

4．5 本章小结

第五章 总结与展望

5．1 全文总结

5．2 研究展望

参考文献

致谢