基于聚类算法的KNN文本分类系统研究与实现

摘要

随着社会的进步和Internet高速发展，如何快速准确地获取自己所需的信息已经成为目前我们迫切需要解决的问题之一。文本分类和聚类是信息处理的重要技术，因而也成为了目前研究的热点。本文主要研究了文本分类和聚类的相关算法，分析了其中的相关技术以及难点。
　　 首先，介绍了文本分类中所涉及的主要技术：文本表示、特征选择与抽取、分类算法和分类性能的评测。其次，着重剖析了KNN文本分类算法，指出其优点及不足。为了克服KNN分类器速度慢的缺陷，提出采用文本聚类对训练集样本库进行合并，将若干样本合并为少量样本中心来减少计算量。再次，介绍了几种常见的文本聚类算法。对基于划分的分类算法：k-means和k-medoids进行了深入的分析与研究，发现k-means等基于划分的聚类算法对聚类初始点选择十分敏感。应用较多的随机选取聚类初始点的方法虽然简单，但是聚类结果很不稳定，时间开销大。针对这一点，本文提出了基于文档相似度的初始化聚类中心点算法，随后通过实验验证了其优越性，并采用这种基于文档相似度的k-means聚类算法对训练集样本库进行合并。最后，本文设计并初步实现了一个基于聚类算法的快速KNN文本分类系统，通过实验验证了采用文本聚类对训练集样本库进行合并，将若干样本合并为少量样本中心，可以在保证分类准确率的情况下，大幅提高KNN文本分类器速度。

目录

文摘

英文文摘

声明

1 引言

1.1 信息检索定义

1.2 文本挖掘定义

1.3 研究背景及现状

1.4 本文的主要工作

1.5 本文组织结构

2 文本分类

2.1 文本分类定义

2.2 文本表示

2.2.1 向量空间模型

2.2.2 特征项权重的计算

2.3 文本的特征选择与特征抽取

2.3.1 文档频率

2.3.2 信息增益

2.3.3 互信息

2.3.4 x2统计量

2.3.5 期望交叉熵

2.4 常用的文本分类算法

2.4.1 Rocchio’s分类算法

2.4.2 朴素贝叶斯分类算法

2.4.3 支持向量机分类算法

2.4.4 其他分类算法

2.5 分类性能的评测

2.5.1 分类性能的评估

2.5.2 分类性能的测试

2.6 本章小结

3 KNN分类算法

3.1 基于实例的学习算法

3.2 KNN分类算法

3.3 KNN分类器的特点

3.4 实验

3.4.1 实验设置

3.4.2 实验结果分析

3.4 本章小结

4 文本聚类

4.1 文本聚类定义

4.2 聚类算法介绍

4.3 基于划分的聚类算法

4.3.1 k-means算法

4.3.2 k-medoids算法

4.3.3 k-means及k-medoids算法的讨论

4.4 聚类中心点初始化方法的优化

4.5 聚类算法的评估

4.6 实验结果分析

4.7 本章小结

5 基于聚类算法的KNN文本分类系统的设计与实现

5.1 系统设计

5.2 实验

5.2.1 实验设置

5.2.2 实验结果分析

5.3 本章小结

6 总结与展望

6.1 总结

6.2 展望

参考文献

致 谢