研究生（大数据技术）报告题目：第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基于模式聚合和特征降维的改进算法
在计算相似度时，不考虑特征词间的关联关系。针对这一不足进行的改进有:主要考虑文档间特征词属性关联与共现对相似度的作用，用一个匹配系数调整两文档间的距离。它实质上是强化了文本中语义链属性因子的作用，修正了次要因素的噪声影响，使文本分类结果更加理想，已有的测试结果证明了这一点，尤其在测试文本与训练文本集中的某些文本直观上较相似时，结果更佳。通过分析特征词对分类贡献的大小，提出了一种应用向量聚合技术的KNN文本分类方法，很好的解决了关联特征词的提取问题，该方法根据每个特征词的CHI 分布曲线来确定它们在分类中的贡献，应用向量聚合技术很好地解决了关联特征词的提取问题。其特点在于:聚合文本向量中相关联的特征词作为特征项，从而取代传统方法中一个特征词对应向量一维的做法，这样不但缩减了向量的维数，而且加强了特征项对文本分类的贡献。试验表明，该方法明显提高了分类的准确率和召回率。
2.2.3基于特征加权的改进算法
KNN方法是建立在VSM模型上的，其样本距离的测度使用欧式距离或余
弦距离，各维权值相同，也就是以为各维对于分类的贡献是相同的，这是不
符合实际情况的，同等的权重使得特征向量之间距离或夹角余弦的计算不够
准确，进而影响分类精度。针对这一不足，提出了基于神经网络和CHI的改进KNN方法，应用SOM神经网络进行VSM模型各维权重的计算。该方法首先运用CHI概率统计方法进行初步特征提取和模式聚合，其特征权重的计算原理为:如果某一维在各个类别中取值基本相同，那么此维对于文本分类的贡献率就相对较低，如果在各个类别中取值有较大的差异，那么就具有较强的文本分类能力，而方差正好是反应变量分布均匀状态的主要指标。该方法有效地提高了文本分类的精度。提出了利用SVM[9]来确定特征的权重，即基于SVM特征加权算法(FWKNN，featureweightedKNN)。试验表明，在一定的条件下，FWKNN能够极提高分类准确率。该方法利用SVM可以定量确定样本的每个特征与分类的相关度———由分类函数的权重向量给出:
其中为每个样本对应的Lagrange乘子。特征权重确定后，就可以修改样本之间的距离函数以便更好地反映实际问题。
3实验结果及分析
3.1数据集
实验数据集由中科院计算所提供的中文文本分类语料库TanCorpV1.0，本语料库收集了12类文本，共14150篇。该数据集中的文本已通过分词、去除停用词等预处理工作，可为实验节省一定的时间。本次实验在其中抽取了财经、电脑、教育、科技、体育和娱乐6个类，每个类别随机抽取600篇文本，共3600篇。计算出平均文本长度后，通过互联网各类论坛搜索出文本长度约为每个类别平均文本长1/5-1/2的测试文本共600篇，每类100篇。
3.2改进的KNN实验方案
在3600篇文本中随机抽取每个类中的400篇作为训练文本，其余的1200篇作为待测文本。反复使用不同Low值，观察分类结果，直到找到合适的值。
3.3改进的KNN实验结果及分析
执行3.2中方案，其目的在于观测Low的取值的对查全率、查准率、F1值以及分类耗时的影响，从中找到比较合适的Low值。其结果如图3-1和图3-2所示。
图3-1 Low/Mid∈[0,1]的分类结果
图3-2 Low/Mid∈[0,1]的分类耗时
可以看出，当Low/Mid ≥ 0.6时，KNN分类器的查全率、查准率和F1值开始趋于稳定，并且其分类耗时是随着Low/Mid的增大成正比的。
4总结与展望
本文系统地介绍了KNN文本分类算法基本原理，以及针对KNN算法的不足而做的各种改进，对文本分类算法的理论研究和实际应用起了指导作用。目前，KNN文本分类算法在科技文献分类、网络信息文本分类、中文不良文本的过滤以及对未知病毒的检测等领域取得了一定的成果。总之，随着互联网和多媒体技术的发展，要求文本分类技术在文本的处理方法、克服噪声干扰、分类精度等方面有进一步的提高。如何利用KNN算法在这些方面做进一步的改进依然是一个研究热点。
参考文献
1 袁军鹏, 朱东华, 毅. 文本挖掘技术研究进展. 计算机应用研究, 2006, 23(2): 1-4
2 J.W.Han, M. Kamber. 数据挖掘：概念与技术. . 机械工业出版, 2007: 3-6
3 Luhn H.P. Auto-encoding of documents for information retriveal systems. In: M.Boaz,
Modem Trends in Documentation, 1959: 45-58
4 金树, 博锋, 徐昕. 基于机械学习的中文文本分类技术研究进展. 软件学报，2006, 17: 1848-1859
5 Salton G, Wong A, Yang C S. A Vetor spaee Model for Automatic Indexing. In: munications of ACM, 1975, 18(11): 613-620
6 Nigam K, Mccallum A, Thrun S, et al. Learning to classify text from labeled and unlabeled documents. In: Mostow J, Madison C.R, eds. Proc. Of the 15
th
National Conf.
on Artificial Intelligence. Wisconsin, 1998: 792-799
7 Yiming Yang. An evaluation of statistical approaches to text categorization. In: Information Retrieval, 1999, 1(1): 69-90
8 Cover T.M, Hart P.E. Nearest neighbor pattern Classification. In: IEEE Transon Information Theory, 1967, 13(1): 21-27
9 Park SB, Zhang BT. Co-Trained support vector machines for large scale unstructured docmuent classificaiton using unlabled data and syntactie information. In: Information processing and Management, 2004, 4(03): 421-439
研究生签字
指导教师签字
院(系、所)领导签字
年月日