…研究生大数据技术报告

1、研究生（大数据技术）报告题目：第27组-基于KNN文本分类分析学号姓名专业计算机技术指导教师院（系、所）计算机学院填表注意事项一、本表适用于攻读硕士学位研究生选题报告、学术报告，攻读博 士学位研究生文献综述、选题报告、论文中期进展报告、学术报告等。二、以上各报告内容及要求由相关院（系、所）做具体要求。三、以上各报告均须存入研究生个人学籍档案。四、本表填写要求文句通顺、内容明确、字迹工整。1研究背景1.1研究背景以及现实意义随着In ternet的迅速发展，现在处于一个信息爆炸的时代，人们可以在 网络上获取更多的信息，如文本、图片、声音、视频等，尤其是文本最为常 用和重要。因此文本的分类在发现有

2、价值的信息中就显得格外重要。文本分 类技术的产生也就应运而生，与日常生活紧密联系，就有较高的实用价值文本分类的目的是对文本进行合理管理，使得文本能分门别类，方便用 户获取有用的信息。一般可以分为人工 和自动分类。人工分类是早期的做 法，这种方式有较好的服务质量和分类精度，但是耗时、耗力、效率低、费 用高。而随着信息量以惊人的速度增长，这种方式就显得很困难，所以需要 一种自动分类的方式来代替人工分类；自动分类节省了人力财力，提高准确 力和速度。1.2国内外研究现状国外对于文本分类的研究开展较早，20世纪50年代末，H.PLuhn3对文 本分类进行了开创性的研究将词频统计思想应用于文本分类，196

3、0年，Maro发表了关于自动分类的第一篇论文，随后，K.Spark, GSalton, R.M.Needham,M.E.Lesk以及K.S.Jones等学者在这一领域进行了卓有成效的研究。目前， 文本分类已经广泛的应用于电子邮件分类、电子会议、数字图书馆、搜索引擎、信息检索等方面4。至今，国外文本分类技术在以下一些方面取得了不 错的研究成果。(1) 向量空间模型5的研究日益成熟Salton等人在60年代末提出的向量空 间模型在文本分类、自动索引、信息检索等领域得到广泛的应用，已成为最 简便高效的文本表示模型之一。(2) 特征项的选择进行了较深入的研究对于英法德等语种，文本可以由单词、单词簇、短

4、语、短语簇或其他特征项进行表示。国内对于文本分类的研究起步比较晚，1981年，侯汉清教授对于计算机 在文本分类工作中的应用作了探讨，并介绍了国外计算机管理分类表、计算 机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，我国陆续研究出一批计算机辅助分类系统和自动分类系统。但是中英文之间存 在较大差异，国内的研究无法直接参照国外的研究成果，所以中文文本分类 技术还存在这一些问题。(1) 缺少统一的中文语料库不存在标准的用于文本分类的中文语料库，各个学者分头收集自己的训练文本集，并在此基础上开展研究，因此，系统的性能可比性不强。同时，由于财力人力有限，中文语料库的规模普遍不大。(2)

5、向量空间模型的研究还不十分成熟国内的学者，例如，吴立德和黄萱 菁也提出了如何选择特征项的问题，他们提出可以使用字、词、概念作为特 征项来构成向量空间模型，并对以此为基础的文本分类系统进行了初步的性 能比较。但是，在这方面的研究 还没有深入的开展，尤其是对于概念的定 义不清晰，没有全面的比较和测试系统。另外，在特征项抽取算法方面也缺 少深入的研究。(3) 文本分类算法的研究不十分完整每个分类器通常只实现一种分类算 法，然后进行测试和分析，缺少完整的多种分类算法性能的比较和测试。2解决方案2.1 KNN文本分类算法KNN算法最初由Cover和Hart于1968年提出，是一个理论上比较成 熟的方法。

6、该算法的基本思想是：根据传统的向量空间模型，文本内容被形式 化为特征空间中的加权特征向量，即 D=D(T1 , W1;T2, W2;Tn , Wn)。对 于一个测试文本，计算它与训练样本集中每个文本的相似度，找出K个最相似的文本，根据加权距离和判断测试文本所属的类别。具体算法步骤如下：(1) 对于一个测试文本，根据特征词形成测试文本向量。(2) 计算该测试文本与训练集中每个文本的文本相似度，计算公式为：工 Wik X WjL_ T S i midjjdi )=Fm77一V k=1 V t=L式中:di为测试文本的特征向量，dj为第j类的中心向量;M为特征向量 的维数;Wk为向量的第k维。(3)

7、 按照文本相似度，在训练文本集中选出与测试文本最相似的k个文本。(4) 在测试文本的k个近邻中，依次计算每类的权重，计算公式如下：4 如果 工P(X,Cj)=恥如0其它式中:x为测试文本的特征向量；Sim(x，di)为相似度计算公式;b为阈值， 有待于优化选择;而 y(di，Cj)的取值为1或0,如果di属于Cj，则函数值为1， 否则为0。(5) 比较类的权重，将文本分到权重最大的那个类别中。KNN方法基于类比学习，是一种非参数的分类技术，在基于统计的模式识别中非常有效，对于未知和非正态分布可以取得较高的分类准确率，具有鲁棒性、概念清晰 等优点。但在文本分类中，KNN方法也存在不足，如KNN算

8、法是懒散的分 类算法，各维权值相同，使得特征向量之间的距离计算不够准确，影响分类精度。针对这些不足，分别提出了相应的改进算法。下面将详细介绍2.2改进的KNN文本分类算法221提高分类效率的改进算法KNN算法的主要缺点是，当训练样本数量很大时将导致很高的计算开 销。KNN算法是懒散的分类算法，对于分类所需的计算都推迟到分类时才进 行，在其分类器中存储有大量的样本向量，在未知类别样本需要分类时，再 计算和所有存储样本的距离，对于高维文本向量或样本集规模较大的情况， 其时间和空间复杂度较高。针对这个缺点，提出了一些改进算法：如基于FuzzyART的K-最近邻分类改进算法，该算法用模糊自适应共振理论

9、 (FuzzyART)对K-最近邻的训练样本集进行浓缩，以改善 K-最近邻的计算速 度。该算法首先用FuzzyART将训练样本集中的每一类样本进行聚类，减少 了训练样本集的数据量，提高了算法的计算速度，保持了预测精度，从而使 该算法适用于海量数据集的情况。试验表明，该算法适用于对复杂而数据量 较大的数据库进行分类。提出了一种基于K-近邻方法的渐进式中文文本分类 技术，利用文本的标题、摘要、关键词、重点段落进行渐进式的分类处理。 这样，不用分析全文就能将部分待分类文本成功分类，从而提高了文本分类 的效率。试验结果表明，该方法在保证分类准确率的基础上能够有效地提高 分类效率。对于减少 KNN计算量

10、的优化而做的研究主要是如何从原始数据 集中选取代表实例集，大部分仅对低维的情况适用，而且在代表实例集每增 加或删除一个代表实例时，都要对样本进行一次测试，工作量大，为此，根 据测试文档在各个样本类中的分布情况提出了基于KNN分类的两个有助于减少大量计算的重要算法：排类算法和归类算法。从而构建了一个基于KNN的快速文档分类方法。理论与实验证明，这种方法可以在不影响原有准确率 的条件下，提高文档的分类速度。2.2.2基于模式聚合和特征降维的改进算法在计算相似度时，不考虑特征词间的关联关系。针对这一不足进行的改进 有:主要考虑文档间特征词属性关联与共现对相似度的作用，用一个匹配系数调 整两文档间的距

11、离。它实质上是强化了文本中语义链属性因子的作用，修正了 次要因素的噪声影响，使文本分类结果更加理想，已有的测试结果证明了这一点，尤其在测试文本与训练文本集中的某些文本直观上较相似时，结果更佳。 通过分析特征词对分类贡献的大小， 提出了一种应用向量聚合技术的 KNN文本 分类方法，很好的解决了关联特征词的提取问题， 该方法根据每个特征词的CHI 分布曲线来确定它们在分类中的贡献，应用向量聚合技术很好地解决了关联特 征词的提取问题。其特点在于：聚合文本向量中相关联的特征词作为特征项，从 而取代传统方法中一个特征词对应向量一维的做法，这样不但缩减了向量的维 数，而且加强了特征项对文本分类的贡献。试验

12、表明，该方法明显提高了分类 的准确率和召回率。223基于特征加权的改进算法KNN方法是建立在VSM模型上的，其样本距离的测度使用欧式距离或 余弦距离，各维权值相同，也就是以为各维对于分类的贡献是相同的，这是 不符合实际情况的，同等的权重使得特征向量之间距离或夹角余弦的计算不 够准确，进而影响分类精度。针对这一不足，提出了基于神经网络和CHI的改进KNN方法，应用SOM神经网络进行VSM模型各维权重的计算。该方 法首先运用CHI概率统计方法进行初步特征提取和模式聚合，其特征权重的 计算原理为:如果某一维在各个类别中取值基本相同， 那么此维对于文本分类 的贡献率就相对较低，如果在各个类别中取值有较

13、大的差异，那么就具有较 强的文本分类能力，而方差正好是反应变量分布均匀状态的主要指标。该方 法有效地提高了文本分类的精度。提出了利用 SVM9来确定特征的权重，即 基于SVM 特征加权算法(FWKNN，featureweightedKNN)。试验表明，在一 定的条件下，FWKNN能够极大地提高分类准确率。该方法利用SVM可以定量确定样本的每个特征与分类的相关度 由分类函数的权重向量给出：W=(W|5w2,ws-wJ=工 ya&QiMCI其中为每个样本对应的Lagrange乘子。特征权重确定后，就可以修改样 本之间的距离函数以便更好地反映实际问题。3实验结果及分析3.1数据集实验数据集由

14、中科院计算所提供的中文文本分类语料库Tan CorpVI.O,本语料库收集了 12类文本，共14150篇。该数据集中的文本已通过分词、 去 除停用词等预处理工作，可为实验节省一定的时间。本次实验在其中抽取了 财经、电脑、教育、科技、体育和娱乐 6个类，每个类别随机抽取600篇文 本，共3600篇。计算出平均文本长度后，通过互联网各类论坛搜索出文本长 度约为每个类别平均文本长1/5-1/2的测试文本共600篇，每类100篇。3.2改进的KNN实验方案在3600篇文本中随机抽取每个类中的400篇作为训练文本，其余的1200 篇作为待测文本。反复使用不同Low值，观察分类结果，直到找到合适的值。3.

15、3改进的KNN实验结果及分析执行3.2中方案，其目的在于观测Low的取值的对查全率、查准率、F1 值以及分类耗时的影响，从中找到比较合适的 Low值。其结果如图3-1和图 3-2所示。图3-1 Low/Mid 0,1的分类结果0 LJ_LJ_LJ_LJ_LJ_LJ_LJ_LJ_LJ_LJ_L.00 10.2 0 3 0.40.5 0.6 0.7 0 8 0 91Loyv.Xiid图3-2 Low/Mid 0,1的分类耗时可以看出，当Low/Mid > 0.6时，KNN分类器的查全率、查准率和 F1值开始趋于稳定，并且其分类耗时是随着Low/Mid的增大成正比的4总结与展望本文系统地介绍了

16、 KNN文本分类算法基本原理，以及针对KNN算法的 不足而做的各种改进，对文本分类算法的理论研究和实际应用起了指导作用。 目前，KNN文本分类算法在科技文献分类、网络信息文本分类、中文不良文 本的过滤以及对未知病毒的检测等领域取得了一定的成果。总之，随着互联 网和多媒体技术的发展，要求文本分类技术在文本的处理方法、克服噪声干 扰、分类精度等方面有进一步的提高。如何利用KNN算法在这些方面做进一步的改进依然是一个研究热点。参考文献1袁军鹏,朱东华,李毅文本挖掘技术研究进展计算机应用研究,2006, 23(2):1-42 J.W.Han, M. Kamber.数据挖掘：概念与技术.北京.机械工业出

17、版，2007: 3-63 Luhn H.P. Auto-encoding of documents for information retriveal systems. In: M.Boaz,Modem Trends in Docume ntatio n, 1959: 45-584苏金树，张博锋，徐昕.基于机械学习的中文文本分类技术研究进展.软件学报，2006, 17: 1848-18595 Salton G Wong A, Yang C S. A Vetor spaee Model for Automatic In dex in g. I n: Communications of ACM,

18、1975, 18(11): 613-6206 Nigam K, Mccallum A, Thrun S, et al. Lear ning to classify text from labeled andunlabeled documents. In: Mostow J, Madison C.R, eds. Proc. Of the 15thNatio nal Conf.on Artificial In tellige nee. Wisco nsi n, 1998: 792-7997 Yiming Yang. An evaluation of statistical approaches t

19、o text categorization. In:In formation Retrieval, 1999, 1(1): 69-908 Cover T.M, Hart P.E. Nearest neighbor pattern Classification. In: IEEE TransonIn formation Theory, 1967, 13(1): 21-279 Park SB, Zhang BT. Co-Trained support vector machines for large scale un structureddocmuent classificaiton using

20、 uniabled data and syntactie information. In: In formatio nprocessi ng and Ma nageme nt, 2004, 4(03): 421-439研究生签字指导教师签字院（系、所）领导签字年 月 日倚窗远眺，目光目光尽处必有一座山，那影影绰绰的黛绿色的影，是春天 的颜色。周遭流岚升腾，没露出那真实的面孔。面对那流转的薄雾，我会幻想， 那里有一个世外桃源。在天阶夜色凉如水的夏夜，我会静静地，静静地，等待 一场流星雨的来临许下一个愿望，不乞求去实现，至少，曾经，有那么一刻，我那还未枯萎 的，青春的，诗意的心，在我最美的年华里，同星空做了一次灵魂的交流秋日