研究生（大数据技术）报告题目：第27组-基于KNN文本分类分析
学号
姓名
专业计算机技术
指导教师
院（系、所）计算机学院
填表注意事项
一、本表适用于攻读硕士学位研究生选题报告、学术报告，攻读博士学位研究生文献综述、选题报告、论文中期进展报告、学术报告等。
二、以上各报告内容及要求由相关院（系、所）做具体要求。
三、以上各报告均须存入研究生个人学籍档案。
四、本表填写要求文句通顺、内容明确、字迹工整。
1研究背景
1.1研究背景以及现实意义
随着Internet的迅速发展，现在处于一个信息爆炸的时代，人们可以在网络上获取更多的信息，如文本、图片、声音、视频等，尤其是文本最为常用和重要。因此文本的分类在发现有价值的信息中就显得格外重要。文本分类技术的产生也就应运而生，与日常生活紧密联系，就有较高的实用价值[1]。
文本分类的目的是对文本进行合理管理，使得文本能分门别类，方便用户获取有用的信息。一般可以分为人工[2]和自动分类。人工分类是早期的做法，这种方式有较好的服务质量和分类精度，但是耗时、耗力、效率低、费用高。而随着信息量以惊人的速度增长，这种方式就显得很困难，所以需要一种自动分类的方式来代替人工分类；自动分类节省了人力财力，提高准确力和速度。
1.2国内外研究现状
国外对于文本分类的研究开展较早，20世纪50年代末，H.P.Luhn[3]对文本分类进行了开创性的研究将词频统计思想应用于文本分类，1960年，Maro 发表了关于自动分类的第一篇论文，随后，K.Spark，GSalton，R.M.Needham，M.E.Lesk以及K.S.Jones等学者在这一领域进行了卓有成效的研究。目前，文本分类已经广泛的应用于电子邮件分类、电子会议、数字图书馆]、搜索引擎、信息检索等方面[4]。至今，国外文本分类技术在以下一些方面取得了不错的研究成果。
(1)向量空间模型[5]的研究日益成熟Salton等人在60年代末提出的向量空间模型在文本分类、自动索引、信息检索等领域得到广泛的应用，已成为最简便高效的文本表示模型之一。
(2)特征项的选择进行了较深入的研究对于英法德等语种，文本可以由单词、单词簇、短语、短语簇或其他特征项进行表示。
国内对于文本分类的研究起步比较晚，1981年，侯汉清教授对于计算机在文本分类工作中的应用作了探讨，并介绍了国外计算机管理分类表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，我
国陆续研究出一批计算机辅助分类系统和自动分类系统。但是中英文之间存在较大差异，国内的研究无法直接参照国外的研究成果，所以中文文本分类技术还存在这一些问题。
(1)缺少统一的中文语料库不存在标准的用于文本分类的中文语料库，各个学者分头收集自己的训练文本集，并在此基础上开展研究，因此，系统的性能可比性不强。同时，由于财力人力有限，中文语料库的规模普遍不大。
(2)向量空间模型的研究还不十分成熟国内的学者，例如，吴立德和黄萱菁也提出了如何选择特征项的问题，他们提出可以使用字、词、概念作为特征项来构成向量空间模型，并对以此为基础的文本分类系统进行了初步的性能比较。但是，在这方面的研究[6]还没有深入的开展，尤其是对于概念的定义不清晰，没有全面的比较和测试系统。另外，在特征项抽取算法方面也缺少深入的研究。
(3)文本分类算法的研究不十分完整每个分类器通常只实现一种分类算法，然后进行测试和分析，缺少完整的多种分类算法性能的比较和测试。
2解决方案
2.1KNN文本分类算法
KNN[7]算法最初由Cover和Hart于1968年提出[8]，是一个理论上比较成熟的方法。该算法的基本思想是:根据传统的向量空间模型，文本内容被形式化为特征空间中的加权特征向量，即D=D(T1，W1;T2，W2;…;Tn，Wn)。对于一个测试文本，计算它与训练样本集中每个文本的相似度，找出K个最相似的文本，根据加权距离和判断测试文本所属的类别。具体算法步骤如下:
(1)对于一个测试文本，根据特征词形成测试文本向量。
(2)计算该测试文本与训练集中每个文本的文本相似度，计算公式为:
式中:di为测试文本的特征向量，dj为第j类的中心向量;M为特征向量的维数;Wk为向量的第k维。
(3)按照文本相似度，在训练文本集中选出与测试文本最相似的k个文本。
(4)在测试文本的k个近邻中，依次计算每类的权重，计算公式如下:
式中:x为测试文本的特征向量;Sim(x，di)为相似度计算公式;b为阈值，有待于优化选择;而y(di，Cj)的取值为1或0，如果di属于Cj，则函数值为1，否则为0。
(5)比较类的权重，将文本分到权重最大的那个类别中。KNN方法基于类比学习，是一种非参数的分类技术，在基于统计的模式识别中非常有效，对于未知和非正态分布可以取得较高的分类准确率，具有鲁棒性、概念清晰等优点。但在文本分类中，KNN方法也存在不足，如KNN算法是懒散的分类算法，各维权值相同，使得特征向量之间的距离计算不够准确，影响分类
精度。针对这些不足，分别提出了相应的改进算法。下面将详细介绍。
2.2改进的KNN文本分类算法
2.2.1提高分类效率的改进算法
KNN算法的主要缺点是，当训练样本数量很大时将导致很高的计算开销。KNN算法是懒散的分类算法，对于分类所需的计算都推迟到分类时才进行，在其分类器中存储有大量的样本向量，在未知类别样本需要分类时，再
计算和所有存储样本的距离，对于高维文本向量或样本集规模较大的情况，
其时间和空间复杂度较高。针对这个缺点，提出了一些改进算法:如基于FuzzyART的K-最近邻分类改进算法，该算法用模糊自适应共振理论(FuzzyART)对K-最近邻的训练样本集进行浓缩，以改善K-最近邻的计算速度。该算法首先用FuzzyART将训练样本集中的每一类样本进行聚类，减少
了训练样本集的数据量，提高了算法的计算速度，保持了预测精度，从而使
该算法适用于海量数据集的情况。试验表明，该算法适用于对复杂而数据量
较大的数据库进行分类。提出了一种基于K-近邻方法的渐进式中文文本分类
技术，利用文本的标题、摘要、关键词、重点段落进行渐进式的分类处理。
这样，不用分析全文就能将部分待分类文本成功分类，从而提高了文本分类
的效率。试验结果表明，该方法在保证分类准确率的基础上能够有效地提高
分类效率。对于减少KNN计算量的优化而做的研究主要是如何从原始数据
集中选取代表实例集，大部分仅对低维的情况适用，而且在代表实例集每增
加或删除一个代表实例时，都要对样本进行一次测试，工作量大，为此，根
据测试文档在各个样本类中的分布情况提出了基于KNN分类的两个有助于
减少大量计算的重要算法:排类算法和归类算法。从而构建了一个基于KNN
的快速文档分类方法。理论与实验证明，这种方法可以在不影响原有准确率
的条件下，提高文档的分类速度。
2.2.2基于模式聚合和特征降维的改进算法
在计算相似度时，不考虑特征词间的关联关系。针对这一不足进行的改进有:主要考虑文档间特征词属性关联与共现对相似度的作用，用一个匹配系数调整两文档间的距离。它实质上是强化了文本中语义链属性因子的作用，修正了次要因素的噪声影响，使文本分类结果更加理想，已有的测试结果证明了这一
