基于K-近邻法的分类器的研究与实现(毕业论文)

基于K-近邻法的分类器的研究与实现基于K-近邻法的分类器的研究与实现摘要模式识别的目的就是对未知的样本，判断它所在的类别。人类的模式识别能力使得人们可以很好的认识周围的环境并与之交流，如果计算机也具有类似的能力，那么其智能程度将会大大提高，可以发挥更大的功能，更好的为人类服务。本文的研究课题就属于计算机模式识别领域。分类器是模式识别系统的重要组成部分；也是机器学习的重要研究领域。本文主要研究对象是KNN分类方法，运用K近邻法(KNearestNeighbor)对数据进行分类，并对分类结果进行比较研究。本文的研究工作主要探讨基于K-近邻法的分类器的实现，主要集中在K-近邻法的理论分析，算法实现。本文首先介绍了数据挖掘的目的、意义及现状，阐述了K-近邻算法在数据挖掘中的地位和作用，然后对K-近邻法进行了详细的研究与分析，并且实现基于K-近邻法的分类器。本设计采用SQLServer数据库系统和c#.net开发工具进行分析研究。关键词：模式识别；数据挖掘；机器学习；K-近邻法；分类器基于K-近邻法的分类器的研究与实现THERESEARCH&ACHIEVEOFCLASSIFIERBASEDONTHEK-NEARESTNEIGHBORALGORITHMABSTRACTThepurposeofpatternrecognitionisjudgeitinthecategoryfortheunknownsample.Thepatternrecognitioncapabilitiesofhumancanmakeitagoodunderstandingoftheenvironmentaroundandexchangewiththem,Ifthecomputeralsohasasimilarcapability,itssmartlevelwillgreatlyimprove,theleveltheycanplayagreaterroleandbetterservicetohumanity.Thisresearchonthesubjectisakindofcomputerpatternrecognition.Classifierisanimportantcomponentpartinpatternrecognitionsystem;itisalsoanimportantresearchintheareaofmachinelearning.ThispapermainlytargetsKNNclassificationmethods,usingk-nearestneighborfordataclassification,andcomparedtheresults.Thisarticleresearchontheachieveofclassifierbasedonthek-nearestneighboralgorithm.Mainlyconcentratedinthek-nearest-neighbortheoreticalanalysisandalgorithm.Firstofall,Iintroducethepurpose、meaningandrecentdevelopmentofdatamining.andexpatiatethestatusandfunctionofk-nearestneighbourinthisfield.thenresearchandanalysistothek-nearest-neighbordetailedandachievetheclassifierbasedonk-nearest-neighbor.IdesignthisprogramwithSQLServerdatabasesystemandc#.netdevelopmenttoolsforanalysisandstudy.Keywords:patternrecognition;datamining,machinelearning;knearestneighbour;classifier基于K-近邻法的分类器的研究与实现目录1绪论………………………..………………………………….………………………….11.1课题背景及目的………………………………………………………………………11.2国内外研究状况………………………………………………………………………21.3课题研究方法…………………………………………………………………………21.4论文构成及研究内容…………………………………………………………………32分类器概述………………………………………………………………………………...42.1分类器概念…………………………………………………...…………………….42.2分类器构造方法……………………………………………...…………………….42.3近邻分类器的分类原理……………………………………...…………………….53K-近邻法的研究与分析…………………………………………………………………...83.1KNN概念………………………………………………….………………………..83.2K-近邻法算法研究……………………………………….………………………..93.2.1K-近邻算法数学模型…………………………………………………….…...93.2.2K-近邻法研究方法…………………………………………………….…...93.2.3KNN算法需要解决的问题……………………………………………....…104K-近邻法的分类器的设计与编程实现………………….………………..………....124.1开发环境的选择………..………………………………………………………….124.1.1数据库系统选择………………………………………...………………….124.1.2开发语言的选择………………………………………...………………….124.2程序设计实现………………..…………………………………………………….144.2.1界面设计………………………………………………...………………….144.2.2功能模块设计………………………………………...…………………….154.2.3数据库连接………………………………………...…………………….174.2.4程序运行与调试……………………………………...…………………….194.3程序实现结果与分析…..…………………………………………………………..205结论……………………………………………………………………………………...21基于K-近邻法的分类器的研究与实现参考文献…………………………………………………………………………….……..22致谢…………………………………………………………………………………….…..23附录源程序代码…………………………………………………………….……………..24附件1开题报告…………………………………………………….…………………35附件2英文原文及翻译………………………………………..………………………40基于K-近邻法的分类器的研究与实现第1页共35页1绪论模式识别或者通俗一点讲自动分类的基本方法有两大类，一类是将特征空间划分成决策域，这就要确定判别函数或确定分界面方程。而另一种方法则称为模板匹配[1]，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。近邻法则在原理上属于模板匹配。一般模式识别系统都由相互联系的两大部分组成，即特征提取器和分类器。分类的方法包括统计的方法、近邻法、神经网络分类法、无监督聚类法和新出现的基于统计学习理论的支持向量机法，K-近邻分类法是近邻分类法的扩展。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，就按最近似的模板的类别作为自己的类别。譬如A类有10个训练样本，因此有10个模板，B类有8个训练样本，就有8个模板。任何一个待测试样本在分类时与这18个模板都算一算相似度，如最相似的那个近邻是B类中的一个，就确定待测试样本为B类，否则为A类。因此原理上说近邻法是最简单的。1.1课题背景及目的数据挖掘是近年来很多领域竟相研究的一个热点领域，而分类器是数据挖掘的一个研究分支[2]。为了研究基于分类的K-近邻算法，先对数据挖掘做一个概要的介绍。数据挖掘是八十年代，投资AI研究项目失败后，AI转入实际应用时提出的。它是一个新兴的，面向商业应用的AI研究。数据挖掘是从大量的数据中，抽取出潜在的、有价值的知识（模型或规则）的过程。数据挖掘有分类、估值、预言、相关性分组或关联规则、聚集、描述和可视化六种分析方法。本文讨论的分类就是首先从数据中选出已经分好类的训练集，在该训练集上运用数据挖掘分类的技术，建立分类模型，对于没有分类的数据进行分类。K-近邻法是最显著的模式识别系统统计学方法之一，已经有40多年的历史，它很早就被用于文本分类研究。K-近邻算法的最大优点是：简单，直观，容易实现，应用范围广，几乎可以用于各种不同类型的数据结构；知识以样本的形式表示，不需要进行模型的训练，容易获取，维护方便；在关系数据库中，算法可以用SQL语句来实现；非常适用于分布是计算。基于K-近邻法的分类器的研究与实现第2页共35页缺点是：需要大量的已经准备好的历史数据；在对一个新样本分类时，要搜索所有的训练样本来寻找最近的邻居，计算量大，时间代价高；由于训练数据常驻内存，会占用大量的内存；且分类结果与参数有关。在模板数量很大时其错误率指标还是相当不错的。也就是说近邻法的研究还是有必要的。1.2国内外研究状况近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，无数个数据库被用于商业管理、政府办公、科学研究和工程开发等，这一势头仍将持续发展下去。于是，一个新的挑战被提了出来:在这被称之为信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢?要想使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。因此，面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识发现(DMKD)技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。数据挖掘(DataMining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。还有很多和这一术语相近似的术语，如从数据库中发现知识(KDD)、数据分析、数据融合(DataFusion)以及决策支持等。人们把原始数据看作是形成知识的源泉,就像从矿石中采矿一样。原始数据可以是结构化的，如关系型数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门广义的交叉学科，涉及到人工智能、数据库、数理统计、机器学习、知识获取、数据可视化、高性能计算等多个领域[3]。1.3课题研究方法knn(k-nearestneighbor)分类器是一种在线分类器，即分类的时候,直接从训练样本中找出与测试样本最接近的k个样本,以判断测试样本的类属。knn分类器的可扩展性比较差，因为每判决一个测试样本，都要将其与所有训练样本比较一次，计算距离。但是knn分类器对处理与训练样本类似页面的时候的精度比较高。所以在样本比较少而对分类速度要求不高的情况下，可以使用knn分类器.同样knn分类器也可以应用在只有正例基于K-近邻法的分类器的研究与实现第3页共35页训练样本的情况下。在小规模仿真的时候使用精度较高的knn分类器，在大规模仿真和实际Web检验的时候使用knn分类器就没有