研究报告大数据技术报告

----研生（大数据技术报告题目

第27组于KNN文本类析学姓

号名专

业

计算机术指导教师院（系所）

计算机院-总结资料

----填表意事项一本表适于攻读士学位究生选报告报攻博士位究文综报告中进报术告。二以各报告及要求相院系所做体求三以各报告须存入究个学档。四本填写要文句通、明、迹整-总结资料

----1研究景1.1研背以及现实意随着Internet的迅速发展，现在处于一个信息爆炸的时代，们可以在网络上获取多的信息，如文本、图片、声音、视频等，尤是文本最为常用和重要。此文本的分类在发现有价值的信息中就显得格重要。文本分类技术的产也就应运而生，与日常生活紧密联系，就有较的实用价[1]。文本分类的的是对文本进行合理管理，使得文本能分门别，方便用户获取有用信息。一般可以分为人工和自动分类。人工分类早期的做法，这种方有较好的服务质量和分类精度，但是耗时、耗、效率低、费用高。而随信息量以惊人的速度增长，这种方式就显得很难，所以需要一种自动分的方式来代替人工分类；自动分类节省了人力力，提高准确力和速度。1.2国研现状国外对于文分类的研究开展较早，20世纪50年末，H.P.Luhn对文本分类进行开创性的研究将词频统计思想应用于文本分类1960年Maro发表了关于动分类的第一篇论文，随后K.Spark，GSalton，R.M.NeedhamM.E.Lesk以及K.S.Jones等者在这一领进行了卓有成的研究目前文本分类已经泛的应用于电子分类、电子会议、数字图书馆搜索引擎、信息检索等方[。至今国外文本分类技术在以一些方面取了不错的研究成果。-总结资料

----(1)向量间模型[5]的研究日益成熟Salton等人在60年代末提出的向空间模型在文分类、自动索引、信息检索等领域得到广泛的用，已成为最简便高效的本表示模型之一。(2)特征的选择进行较深入的研究对于英法等语种文本可由单词、单词簇短语、短语簇或其他特征项进行表示。国对于文本类的研究起步比较晚1981年侯汉清授对于计算机在文本分类工中的应用作了探讨，并介绍了国外计算机管理类表、计算机分类检索、算机自动分类、计算机编制分类表等方面的概。此后，我国陆续研究出批计算机辅助分类系统和自动分类系统。但是英文之间存在较大差异，的研究无法直接参照国外的研究成果，所以中文本分类技术还存在这一问题。(1)缺少一的中文语库不存在标准的用于文分类的中文料库各个学者分头集自己的训练文本集，并在此基础上开展研究因此，系统的性能可比性强。同时，由于财力人力有限，中文语料库的模普遍不大。(2)向量间模型的研还不十分成熟国的学者例如，吴立和黄萱菁也提出了如选择特征项的问题，他们提出可以使用字、词概念作为特征项来构成向空间模型，并对以此为基础的文本分类系统进了初步的性能比较。但是在这方面的研究还没有深入的开展，尤其是对于念的定义不清晰，没全面的比较和测试系统。另外，在特征项抽取法方面也缺少深入的研究-总结资料

----(3)文分类算法的究不十分完整每个分类通常只实现种分类算法，然后进测试和分析，缺少完整的多种分类算法性能的较和测试。-总结资料

----2解决案2.1KNN文分算KNN算法初由Cover和Hart于1968年提出[8]一个理论上比较成熟的方法。该法的基本思想:根据传统的向量间模型，文本容被形式为特征空间中加权特征向量，即D=D(T1，W1;T2，W2;;Tn，Wn)。于一个测试文本，算它与训练样本集中每个文本的相似度，找出K个相似的文本，根据加距离和判断测试文本所属的类别。具体算法步如下:(1)对于个测试文本根据特征词形成测试文向量。(2)计算测试文本与练集中每个文本的文本似度，计算式为:式中:di为测试文本的征向量dj为第j类的中心向量M为特征向量维数;Wk为向的第k维。(3)按照本相似度练文本中选出与测试本最相似的个文本(4)在测文本的k个近邻，依次计算每类的权重，计算公式如下:式中:x为测试文本的征向量;Sim(x，di)为相似度计算公式;b为阈值，有待于优化择;而y(di的取值为1或0，如果di于Cj，则函数值为，否则为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文本分类方法，好的解决了关联特征词的提取问题，该方法根每个特征词的HI分布曲线来定它们在分类中的贡献，应用向量聚合技术很地解决了关联特征词的提取题。其特点在:聚合文本向量中相关联的特征词作特征项，从而取代传统法中一个特征词对应向量一维的做法，这样不缩减了向量的维数，而且加了特征项对文本分类的贡献。试验表明，该方明显提高了分类的准确率和回率。2.2.3基特加的进算KNN方是建立在VSM模型上的样本距离的度使用欧式距离或余弦距离，各权值相同，也就是以为各维对于分类的贡献是同的，这是不符合实际情的，同等的权重使得特征向量之间距离或夹角弦的计算不够-总结资料

----准确，进而响分类精度。针对这一不足，提出了基于神经络和CHI的改进KNN方法，应用SOM神经网络进行VSM模各维权重的计算。该方法首先运用CHI概率统计方进行初步特征提取和模式聚合，其特征权重计算原理为:如某一维在各个类别中取值基本相同那此维对于文本分类的贡献率就相对低，如果在各个类别中取值有较大的差异，那就具有较强的文本分类能，而方差正好是反应变量分布均匀状态的主要标。该方法有效地提高了本分类的精度。提出了利用SVM来定特征的权重，即基于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篇文本中随机取每个类中篇作为训练文本的1200篇作为待测本复使用不同Low值察分类结果直到找到合适的值。3.3改的KNN验果分执行3.2中方案，其的在于观测Low的取值的对查全率、查准率、F1值以及分类时的影响，从中找到比较合适的Low值。其结果如图3-1图3-2所示。-总结资料

----图3-1Low/Mid∈[0,1]分类结果图3-2Low/Mid∈[0,1]的分类耗时可以看出，Low/Mid≥0.6时KNN分器的查全率、查准率和F1值开始趋于稳，并且其分类耗时是随着Low/Mid的增大成正比的-总结资料

----4总结展望本文系统地绍了KNN文本分类算法基本理，以及针KNN算法的不足而做的种改进本分类算法理论研究和实际应起了指导作。目前，KNN文分类算法在科技文献分类、网络信息文本分类、中不良文本的过滤以对未知病毒的检测等领域取得了一定的成果。之，随着互联网和多媒体术的发展，要求文本分类技术在文本的处理方、克服噪声干扰分类精度方面有进一步的提高如何利用KNN算法在这些方面做进步的改进依是一个研究热点。-总结资料

----参文1袁军,朱东华,毅.文本挖掘技术研究进展.计算机应用究2006,23(2):1-42J.W.Han,M.Kamber.数据挖掘：概念与技术..机械工业出版,2007:3-63LuhnH.P.Auto-encodingofdocumentsforinformationretrivealsystems.In:M.Boaz,ModemTrendsDocumentation,1959:45-584金树,博锋,徐昕.基于机械学习的中文文本分类术研究进展.软件学报，2006,17:1848-18595SaltonWongA,YangCS.VetorspaeeModelAutomaticIndexing.In:municationsACM,1975,18(11):613-6206NigamK,MccallumA,ThrunS,etal.Learningtoclassifytextfromlabeledandunlabeleddocuments.In:MostowJ,MadisonC.R,eds.Proc.the15-总结资料

----thNationalConf.onArtificialIntelligence.Wisconsin,1998:792-7997YimingYang.Anevaluationstatisticalapproachestotextcategorization.InformationRetrieval,1999,1(1):69-908CoverT.M,HartP.E.NearestneighborpatternClassification.In:IEEETransonInformation19