研究基于分类的K-近邻算法设计方案第一章 绪论模式识别又常称作模式分类,从处理问题的性质和解决问题的方法等角度,模式识别分为有监督的分类〔Supervised Classification和无监督的分类两种二者的主要差别在于,各实验样本所属的类别是否预先已知一般说来,有监督的分类往往需要提供大量已知类别的样本,但在实际问题中,这是存在一定困难的,因此研究无监督的分类就变得十分有必要了模式还可分成抽象的和具体的两种形式前者如意识、思想、议论等,属于概念识别研究的畴,是人工智能的另一研究分支我们所指的模式识别主要是对语音波形、地震波、心电图、脑电图、图片、照片、文字、符号、生物传感器等对象的具体模式进行辨识和分类模式识别研究主要集中在两方面,一是研究生物体<包括人>是如何感知对象的,属于认识科学的畴,二是在给定的任务下,如何用计算机实现模式识别的理论和方法前者是生理学家、心理学家、生物学家和神经生理学家的研究容,后者通过数学家、信息学专家和计算机科学工作者近几十年来的努力,已经取得了系统的研究成果模式识别或者通俗一点讲自动分类的基本方法有两大类,一类是将特征空间划分成决策域,这就要确定判别函数或确定分界面方程。
而另一种方法则称为模板匹配[1],即将待分类样本与标准模板进行比较,看跟哪个模板匹配度更好些,从而确定待测试样本的分类近邻法则在原理上属于模板匹配分类的方法包括统计的方法、近邻法、神经网络分类法、无监督聚类法和新出现的基于统计学习理论的支持向量机法,K-近邻分类法是近邻分类法的扩展它将训练样本集中的每个样本都作为模板,用测试样本与每个模板做比较,看与哪个模板最相似<即为近邻> ,就按最近似的模板的类别作为自己的类别譬如A类有10个训练样本,因此有10个模板,B类有8个训练样本,就有8个模板任何一个待测试样本在分类时与这18个模板都算一算相似度,如最相似的那个近邻是B类中的一个,就确定待测试样本为B类,否则为A类因此原理上说近邻法是最简单的1.1 课题背景及目的数据挖掘是近年来很多领域竟相研究的一个热点领域,而分类器是数据挖掘的一个研究分支[2]为了研究基于分类的K-近邻算法,先对数据挖掘做一个概要的介绍数据挖掘是八十年代,投资AI研究项目失败后,AI转入实际应用时提出的它是一个新兴的,面向商业应用的AI研究数据挖掘是从大量的数据中,抽取出潜在的、有价值的知识〔模型或规则的过程数据挖掘有分类、估值、预言、相关性分组或关联规则、聚集、描述和可视化六种分析方法。
本文讨论的分类就是首先从数据中选出已经分好类的训练集,在该训练集上运用数据挖掘分类的技术,建立分类模型,对于没有分类的数据进行分类K-近邻法是最显著的模式识别系统统计学方法之一,已经有40多年的历史,它很早就被用于文本分类研究K-近邻算法的最大优点是：简单,直观,容易实现,应用围广,几乎可以用于各种不同类型的数据结构；知识以样本的形式表示,不需要进行模型的训练,容易获取,维护方便；在关系数据库中,算法可以用SQL语句来实现；非常适用于分布是计算缺点是：需要大量的已经准备好的历史数据；在对一个新样本分类时,要搜索所有的训练样本来寻找最近的邻居,计算量大,时间代价高；由于训练数据常驻存,会占用大量的存；且分类结果与参数有关在模板数量很大时其错误率指标还是相当不错的也就是说近邻法的研究还是有必要的1.2 国外研究状况近十几年来,人们利用信息技术生产和搜集数据的能力大幅度提高,无数个数据库被用于商业管理、政府办公、科学研究和工程开发等,这一势头仍将持续发展下去于是,一个新的挑战被提了出来:在这被称之为信息爆炸的时代,信息过量几乎成为人人需要面对的问题如何才能不被信息的汪洋大海所淹没,从中及时发现有用的知识,提高信息利用率呢?要想使数据真正成为一个公司的资源,只有充分利用它为公司自身的业务决策和战略发展服务才行,否则大量的数据可能成为包袱,甚至成为垃圾。
因此,面对"人们被数据淹没,人们却饥饿于知识"的挑战,数据挖掘和知识发现技术应运而生,并得以蓬勃发展,越来越显示出其强大的生命力由于K-近邻法实际应用效果好,但又因算法问题而使其计算量大,时间代价高；由于训练数据常驻存,会占用大量的存,增加成本所以国外对于K-近邻法的研究主要在分为两部分：一.对其算法的的改进研究工程技术大学的宇[3]提出了一种出了一种利用随机属性子集组合k-近邻分类器的算法通过随机的属性子集组合多个k 近邻分类器, 利用简单的投票, 对多个k-近邻分类器的输出进行组合, 这样可有效地改进k-近邻分类器的精度石油化工学院计算机与电子信息学院的周靖,晋胜[4]采用特征相关性差异优化距离的改进k近邻算法可以有效地解决 近邻算法训练样本规模及分类精度间的矛盾,提出了一种采用特征相关性差异优化距离的改进算法 该算法将特征熵值与其分布概率的乘积作为特征相关性的概念, 在此基础上定义围绕特征相关性差异的样本距离测度,明确特征在类别上的重要性及相关性,在小样本情况下提取针对分类的大量有效信息,以增强算法的全局优化能力对比仿真实验结果表明, 该算法在保持效率的情况下分类精度得到了极大地提高。
中国地质大学计算机科学系的陆微微, 晶[6]提出了一种一种提高 K- 近邻算法效率的新算法此方法是基 于凹凸轮廓结构特 征估计轮廓的宽度与高度比值, 进而快速、正确地对粘连字符进行切分,使把部分原本发生在分类阶段的计算移到训练阶段来完成该算法可以使knn算法的效率提高80%此外该方法还可用于 KNN 的所有变体 中, 具有 良好的推广能力 二.对K-近邻法的具体应用大学计算机科学与技术学院的锋,白凡[5]应用了一种改进的K近邻算法进行网页分类其针对传统K近邻算法对于噪声词敏感的缺点,结合网页文章构成的特殊性,对文档的特征向量表示模型进行了改进,从而也改进了K近邻算法中特证词的权值以及文档相似度的计算公式,实验结果表明改进后的K近邻算法提高了分类的精度但此算法增加了网页文本的预处理时间1.3 课题研究方法knn算法是一种的分类方法,即分类的时候,直接从训练样本中找出与测试样本最接近的k个样本,以判断测试样本的类属Knn算法的可扩展性比较差,因为每判决一个测试样本,都要将其与所有训练样本比较一次,计算距离但是knn算法对处理与训练样本类似页面的时候的精度比较高。
所以在样本比较少而对分类速度要求不高的情况下,即在图像识别是有很多应用可以使用knn分类器同样knn分类器也可以应用在只有正例训练样本的情况下在小规模仿真的时候使用精度较高的knn分类器,在大规模仿真和实际Web检验的时候使用knn分类器就没有有更好推广能力可以看出,尽管近邻法有其优良品质,但是它的一个严重弱点与问题是需要存储全部训练样本,以及繁重的距离计算量所以需要改良1.4 论文构成及研究容分类方法有许多,在本文我们主要讨论k-近邻分类方法在模式识别中的应用与研究本文的第1章是绪论,说明本设计课题的来源、目的、意义、国外研究状况、应解决的问题急应达到的技术要求本文的第2章介绍的近邻分类器的分类原理,KNN概念,K-近邻法算法研究, K-近邻算法数学模型, K-近邻法研究方法, KNN算法需要解决的问题其中K-近邻算法必须明确两个基本的因素：最近案例的数目K和距离的尺度对这个问题进行了讨论,并对KNN算法做出了评价本文的第3章介绍了分类器的概念和分类器的构造方法本文的第4章是K-近邻法的分类器的设计与编程实现,主要包括以下几个方面的容：开发环境的选择,K-近邻法程序实现,数据库连接,程序运行与调试及程序实现结果与分析。
最后一章总结论文中的主要工作和结果第二章 K-近邻算法的研究与分析2.1概述分类问题是数据挖掘邻域研究的一个基本的问题,给定一批具有类标记的训练实例,分类器被构造并被用于预测待分类实例的类标记.通常,一个实例 X用一个 m维的属性向量来表示,其中 xi 表示实例 X的第 i个属性值 令C表示实例的类标记,则实例 X的类标记可表示为C KNN算法作为一种基本的基于实例的分类算法,由于它的有效简单高鲁棒性而被广泛的应用于数据挖掘领域来解决分类问题近邻法是模式识别非参数法中最重要的方法之一,最初的近邻法是Cover和Hart于1968年提出的,由于该方法在理论上进行了深入分析,直至现在仍是分类方法中最重要的方法之一[7]直观的理解,所谓的K近邻,就是考察和待分类样本最相似的K个样本,根据这K个样本的类别来判断待分类样本的类别值在K近邻分类器中,一个重要的参数是K值的选择,K值选择过小,不能充分体现待分类样本的特点,而如果K值选择过大则一些和待分类样本实际上并不相似的样本亦被包含近来,造成燥声增加而导致分类效果的降低2.2最近邻法2.1.1最近邻法概述最近邻是将所有训练样本都作为代表点,因此在分类时需要计算待识别样本x到所有训练样本的距离,结果就是与x最近邻的训练样本所属于的类别。
假定有c个类别w1,w2,…,wc的模式识别问题,每类有标明类被的样本Ni个,i=1,2,…,c规定wi类的判别函数为gi=min ||x-xik||,k=1,2,…,Ni其中xik的角标i表示wi类,k表示wi类Ni个样本中的第k个决策规则可以写为：若gj=min gi,i=1,2,…,c,则决策x∈wj此分类示意图见图2.2所示 B□ A？ A ●□●B A□●B A B□●图2.1 近邻法分类图示2.1.2最近邻决策规则给定c 个类别 ,每类有标明类别的样本个,近邻法的判别函数为决策法则为直观的说,就是对待识别的模式向量,只要比较与所有已知类别的样本之间的欧式距离,并决策与离它最近的样本同类图2.2 最近邻法图示2.1.3最近邻法的错误率分析这里,设采用N个样本的最近邻法的平均错误率,并设则有以下的不等式成立：证明：最近邻法属于随机化决策,待分类模式X的近邻随样本集的变化而随机变化,设其最近邻为,错误的条件错误率为。
对于取平均下面我们看一下上面的两个表达式设对于给定的,概率密度是连续的且不为零那么,任何样本落入以为中心的一个超球S 中的概率为N个独立的样本落在S外的概率为即是,一个样本也不落在S 的概率为0,也就是说总有一个样本落在S的概率为1无论S多么小,这个结论也是成立的,所以上式即是最近法错误率的计算公式2.1.4总结从上面可以看出近邻法有方法简单的优点,但也存在这一些缺点：〔1存储量和计算量都很大；〔2没有考虑决策的风险,如果决策的错误代价很大时,会产生很大的风险；〔3以上的分析——渐近平均错误率,都是建立在样本数趋向无穷大的条件下得来的,在实际应用时大多是无法实现的所以我们要引入具有拒绝决策的k—近邻法2.2 K-近邻法的概念K-近邻算法的思想如下：首先,计算新样本与训练样本之间的距离,找到距离最近的K个邻居；然后,根据这些邻居所属的类别来判定新样本的类别,如果它们都属于同一个类别,那么新样本也属于这个类；否则,对每个后选类别进行评分,按照某种规则确定新样本的类别取未知样本X的K个近邻,看着。