K-近邻研究应用

1 研究基于分类的 第一章 绪论 模式识别又常称作模式分类，从处理问题的性质和解决问题的方法等角度，模式识别分为有监督的分类（ 无监督的分类 (种。二者的主要差别在于，各实验样本所属的类别是否预先已知。一般说来，有监督的分类往往需要提供大量已知类别的样本，但在实际问题中，这是存在一定困难的，因此研究无监督的分类就变得十分有必要了。 模式还可分成抽象的和具体的两种形式。前者如意识、思 想、议论等 ,属于概念识别研究的范畴 ,是人工智能的另一研究分支。我们所指的模式识别主要是对语音波形、地震波、心电图、脑电图、图片、照片、文字、符号、生物传感器等对象的具体模式进行辨识和分类。 模式识别研究主要集中在两方面 ,一是研究生物体 (包括人 )是如何感知对象的，属于认识科学的范畴 ,二是在给定的任务下 ,如何用计算机实现模式识别的理论和方法。前者是生理学家、心理学家、生物学家和神经生理学家的研究内容 ,后者通过数学家、信息学专家和计算机科学工作者近几十年来的努力 ,已经取得了系统的研究成果。 模式识别或者通俗一点讲 自动分类的基本方法有两大类，一类是将特征空间划分成决策域，这就要确定判别函数或确定分界面方程。而另一种方法则称为模板匹配 1，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。近邻法则在原理上属于模板匹配。 分类的方法包括统计的方法、近邻法、神经网络分类法、无监督聚类法和新出现的基于统计学习理论的支持向量机法， 它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似 (即为近邻 ) ， 就按最近似的模板的类别作为 自己的类别。譬如 A 类有 10个训练样本，因此有 10个模板， 个训练样本，就有 8个模板。任何一个待测试样本在分类时与这 18 个模板都算一算相似度 ， 如最相似的那个近邻是 B 类中的一个，就确定待测试样本为 则为 此原理上说近邻法是最简单的。 题背景及目的 数据挖掘是近年来很多领域竟相研究的一个热点领域，而分类器是数据挖掘的一个研究分支 2。为了研究基于分类的 对数据挖掘做一个概要的介绍。 2 数据挖掘是八十年代，投资 究项目失败后， 入实际应用时提出的。它是一个新兴的，面向商 业应用的 究。 数据挖掘是从大量的数据中，抽取出潜在的、有价值的知识（模型或规则）的过程。数据挖掘有分类、估值、预言、相关性分组或关联规则、聚集、描述和可视化六种分析方法。本文讨论的分类就是首先从数据中选出已经分好类的训练集，在该训练集上运用数据挖掘分类的技术，建立分类模型，对于没有分类的数据进行分类。 经有 40 多年的历史，它很早就被用于文本分类研究。 单，直观，容易实现，应用范围广，几乎可以用于各种不同类型的数据结构；知识以样 本的形式表示，不需要进行模型的训练，容易获取，维护方便；在关系数据库中，算法可以用 常适用于分布是计算。缺点是：需要大量的已经准备好的历史数据；在对一个新样本分类时，要搜索所有的训练样本来寻找最近的邻居，计算量大，时间代价高；由于训练数据常驻内存，会占用大量的内存；且分类结果与参数有关。 在模板数量很大时其错误率指标还是相当不错的。 也就是说近邻法 的研究还是 有必要 的。 内外研究状况 近十几年来 ， 人们利用信息技术生产和搜集数据的能力大幅度提高 ， 无数个数据库被用于商业管理、政府办公、科学 研究和工程开发等 ， 这一势头仍将持续发展下去。于是 ， 一个新的挑战被提了出来 :在这被称之为信息爆炸的时代 ， 信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没 ， 从中及时发现有用的知识 ， 提高信息利用率呢 ?要想使数据真正成为一个公司的资源 ， 只有充分利用它为公司自身的业务决策和战略发展服务才行 ， 否则大量的数据可能成为包袱 ， 甚至成为垃圾。因此 ，面对 “ 人们被数据淹没 ， 人们却饥饿于知识 ” 的挑战 ， 数据挖掘和知识发现 (术应运而生 ， 并得以蓬勃发展 ， 越来越显示出其强大的生命力。 由于 好，但又因算法问题而使其计算量大，时间代价高；由于训练数据常驻内存，会占用大量的内存，增加成本 。 所以国内外对于 一 辽宁工程技术大学的张宇 3提出了一种出了一种利用随机属性子集组合 k 近邻分类器 , 利用简单的投票 , 对多个 这样可有效地改进 广东石油化工学院计算机与电子信息学院的周靖，刘晋胜 4采用特征相关性差异优 3 化距离的改进 k 近邻算法。可以有效地 解决 近邻算法训练样本规模及分类精度间的矛盾，提出了一种采用特征相关性差异优化距离的改进算法 ( 该算法将特征熵值与其分布概率的乘积作为特征相关性的概念， 在此基础上定义围绕特征相关性差异的样本距离测度，明确特征在类别上的重要性及相关性，在小样本情况下提取针对分类的大量有效信息，以增强算法的全局优化能力。对比仿真实验结果表明， 该算法在保持效率的情况下分类精度得到了极大地提高。 中国地质大学计算机科学系的陆微微 , 刘晶 6提出了一种一种提高 邻算法效率的新算法。此方法是基 于凹凸轮廓 结构特 征估计轮廓的宽度与高度比值 , 进而快速、正确地对粘连字符进行切分 ,使把部分原本发生在分类阶段的计算移到训练阶段来完成。该算法可以使 法的效率提高 80%。此外该方法还可用于 所有变体 中 , 具有 良好的推广能力 。 二 安徽大学计算机科学与技术学院的刘锋，白凡 5应用了一种改进的 K 近邻算法进行网页分类。其针对传统 合网页文章构成的特殊性，对文档的特征向量表示模型进行了改进，从而也改进了 公式，实验结果表明改进后的 此算法增加了网页文本的预处理时间。 题研究方法 法 是一种在线 的分类方法 ， 即分类的时候 ,直接从训练样本中找出与测试样本最接近的 k 个样本 ,以判断测试样本的类属 。 法 的可扩展性比较差 ， 因为每判决一个测试样本 ， 都要将其与所有训练样本比较一次 ， 计算距离 。但是 处理与训练样本类似页面的时候的精度比较高 。 所以在样本比较少而对分类速度要求不高的情况下 ， 即在图像识别是有很多应用。 可以使用 类器 。 同样类器也可以应用在只有正例训练样本的情况下 。 在小规模仿真的时候使用精度较高的 在大规模仿真和实际 没有 有更好推广能力 。 可以看出，尽管近邻法有其优良品质，但是它的一个严重弱点与问题是需要存储全部训练样本，以及繁重的距离计算量。 所以需要改良。 文构成及研究内容 分类 方法有许多，在本文我们主要讨论 用与研究。 4 本文的第 1章是绪论，说明本设计课题的来源、目的、意义、国内外研究状况、应解决的问题急应达到的技术要求。 本文的第 2 章介绍的近邻分类器的分类原理， 念， 法需要解决的问题。其中 近案例的数目 这个问题进行了讨论，并对 本文的第 3章介绍了分类器的概念和分类器的构造方法。 本文的第 4章是 要包括以下几个方面的内容：开发环境的选择， 据库连接，程序运行与调试及程序实现结果与分析。 最后一章总结论文中的主要工作 和结果。 5 第二章 法的研究与分析 述 分类问题是数据挖掘邻域研究的一个基本的问题，给定一批具有类标记的训练实例，分类器被构造并被用于预测待分类实例的类标记 个实例 X 用一个 表示，其中 示实例 令 实例 X 的类标记可表示为 C(x) 法作为一种基本的基于实例的分类算法，由于它的有效简单高鲁棒性而被广泛的应用于数据挖掘领域来解决分类问题 。 近邻法是模式识 别非参数法中最重要的方法之一，最初的近邻法是 968 年提出的，由于该方法在理论上进行了深入分析，直至现在仍是分类方法中最重要的方法之一 7。直观的理解，所谓的 K 近邻，就是考察和待分类样本最相似的 K 个样本，根据这 个重要的参数是 K 值的选择， K 值选择过小，不能充分体现待分类样本的特点，而如果 K 值选择过大。则一些和待分类样本实际上并不相似的样本亦被包含近来，造成燥声增加而导致分类效果的降低。 近邻 法 最近邻是将所有训练样本都作为代表点，因此在分类时需要计算待识别样本 果就是与 定有 w1， ， 类有标明类被的样本 i=1,2, ,c。规定 gi(x)=|,k=1,2, , 其中 i 表示 策规则可以写为：若 gj(x)=gi(x),i=1,2, ,c,则决策 x 此分类示意图见图 6 A？ B A B A B A B 图 邻法分 类图示 给定 c 个类别 12,c ，每类有标明类别的样本 ，近邻法的判别函数为 ( ) m i n , 1 , 2 , ,ki i k N x x ) m i n ( ) , 1 , 2 , , ji ig g i c jx x 是对待识别的模式向量 x ，只要比较 x 与所有已知类别的样本之间的欧式距离， 并决策 x 与离它最近的样本同类。 图 近邻法图示 这里，设 ( ) 1 ( )mP e P ) ( )P P e p d x x x( ) m a x ( ) 1 , 2 , , i c 采用 )，并设 l i m ( ) e则有以下的不等式成立： 21 P 证明：最近邻法属于随机化决策，待分类模式 其最近邻为 x ，错误的条件错误率为 ()x , x 。对于 x 取平均 132x 7 l i m ( ) ( )N p x x x x 11( ) 1 ( , ) 1 ( ) ( )i i i e P P P x , x x , x x x 11( ) 1 ( , ) 1 ( ) ( )i i i e P P P x , x x , x x x 21l i m ( ) 1 ( )e P x , x x 212121l i m ( ) l i m ( ) ( )l i m 1 ( ) ( )l i m 1 ( ) ( )1 ( )e P e p dP p x x , x x x xx x x xx x x l i m ( ) ( )N p x x x x 设对于给定的 x ，概率密度是连续的且不为零。那么，任何样本落入以 x 为中心的一个超球 S 中的概率为 ()SP p d S 外的概率为 (1 ) li m (1 ) 0 即是，一个样本也不落在 S 内的概率为 0，也就是说总有一个样本落在 S 内的概率为 1。无论 S 多么小，这个结论也是成立的，所以 l i m ( ) ( )N p x x x x。 8 21l i m ( ) l i m ( ) ( )1 ( ) ( ) e P e p dP p d x x xx x 从上面可以看出近邻法有方法简单的优点，但也存在这一些缺点： （ 1）存储量和计算量都很大； （ 2）没有考虑决策的风险，如果决策 的错误代价很大时，会产生很大的风险； （ 3）以上的分析 渐近平均错误率，都是建立在样本数趋向无穷大的条件下得来的，在实际应用时大多是无法实现的。 所以我们要引入具有拒绝决策的 k 近邻法 先 ， 计算新样本与训练样本之间的距离 ， 找到距离最近的 后 ， 根据这些邻居所属的类别来判定新样本的类别 ， 如果它们都属于同一个类别 ， 那么新样本也属于这个类；否则 ， 对每个后选类别进行评分 ， 按照某种规则确定新样本的类别 。 取未知样本 个近邻，看着 类，就把 ，在 个样本中，找出 个近邻。 开始生长，不断的扩大区域，直到包含进 且把测试样本 个训练样本中出现频率最大的类别。例如，图 =6 的情况，根据判定规则，测试样本 9 。 . 。 . . . . 图 近邻分类是基于眼球的懒散的学习法，即它存放所有的训练样本，并且知道新的样本需要分类时才建立分类。这与决策数和反向传播算法等形成鲜明对比，后者在接受待分类的新样本之前需要构造一个一般模型。懒散学习法在训练时比急切学习法快，但在分类时慢，因为所有的计算都推迟到那时。 优点 :简单，应 用范围广；可以通过 型不需要预先构造。 缺点 :需要大量的训练数据；搜索邻居样本的计算量大，占用大量的内存；距离函数的确定比较困难；分类的结果与参数有关 。 用最近邻方法进行预测的理由是基于假设：近邻的对象具有类似的预测值。最近邻算法的基本思想是在多维空间 找到与未知样本最近邻的 k 个点，并根据这 k 个点的类别来判断未知样本的类。这 法假设所有的实例对应于 n 维空间中的点。一个实例的最近邻是根据标 准欧氏距离定义，设 其中， ar(x)表示实例 x 的第 r 个属性值。两个实例 d(xi，其中： d( a r ( x j) ) 2-( a r ( 在最近邻学习中，离散目标分类函数为 f： 其中 即各不同分类集。最近邻数 不. . . . . . . . . . 10 同的应用可以选取不同的 如果未知样本 么该 很大，反之则小。因此最近邻算法易受噪声数据的影响，尤其是样本空间中的孤立点的影响。其根源在于基本的 预测样本的 自然社会中，通常一个对象受其近邻的影响是不同的，通常是距离越近的对象对其影响越大 9。 该算法没有学习的过程，在分类时通过类别已知的样本对新样本的类别进行预测，因此属于基于实例的推理方法。如果取 ，待分样本的类别就是最近邻居的类别，称为 只要训练样本足够多， 法就能达到很好的分类效果。当训练样本 数趋近于 -时， 法的分类误差最差是最优贝叶斯误差的两倍；另外，当 K 趋近于时 ,法的分类误差收敛于最优贝叶斯误差。下面对 输入：训练数据集 D=(i),1 i N，其中 新样本 X，距离函数 d。 输出 :。 i=1 算 d()； 距离排序，得到 d(X, d(X, d(X, 选择前 S=( (； 统计 定 。 (1) 寻找适当的训练数据集 训练数据集应该是对历史数据的一个很好的覆盖，这样才能保证最近邻有利于预测，选择训练数据集的原则是使各类样本的数量大体一致，另外，选取的历史数据要有代表性。常用的方法是按照类别把历史数据分组，然后再每组中选取一些有代表性的样本组成训练集。这样既降低了训练集的大小，由保持了较高的准确度。 (2) 确定距离函数 距离函数决定了哪些样本是待分类本的 的选取取决于实 际的数据和决策问题。如果样本是空间中点，最常用的是欧几里德距离。其它常用的距离函是由 11 绝对距离、平方差和标准差。 (3) 决定 邻居的个数对分类的结果有一定的影响，一般先确定一个初始值，再进行调整，直到找到合适的值为止。 (4) 综合 多数法是最简单的一种综合方法，从邻居中选择一个出现频率最高的类别作为最后的结果，如果频率最高的类别不止一个，就选择最近邻居的类别。权重法是较复杂的一种方法，对 离越大，权重就越小。在统计类别时，计算每个类别的权重和，最大的那个就是新样 本的类别 9。 结 在 其是 往是通过对大量独立的测试数据，多个模型来验证最佳的选择。下面是一些被提及的处理 方法： 10，也可以使用动态 用固定的距离指标，这样只对小于该指标的案例进行统计。 对于样本的维护，也并不是简单的增加新样本。也可以采取适当的办法来保证空间的大小，如符合某种条件的样本可以加入库里，同时可以对库里已有符合某种条件的样本进行删除等。 此外，为考虑提高性能，可以把所有的数据放在内存中，如 存在内存中的 有监督学习 )。它实际并不需要产生额外的数据来描述规则，它的规则本身就是数据 (样本 )。 于机器学习的基于样本的学习。它区别于归纳学习的主要特点是直接用已有的样本来解决问题，而不是通过规则推导来解决问题。它并不要求数据的一致性问题，即可以通过噪音，并且对样本的修改是局部的，不需要重新组织。 个近邻样本的类别来预测未知样本的类别，而在选择样本时根据一定的距离公式计算与未知样本的距离来确定是否被选择。其优点是方 法简单，算法稳定。缺点是需要大量样本才能保证数据的精度，此外，更主要的是它需要计算大量的样本间的距离，导致使用上的不便。对于每个新的样本都要遍历一次全体数据， 时间和空间的复杂性是必须考虑的。 8。 12 第三章 分类器概述 类器的概念 分类器的定义：输入的数据含有千万个记录，每个记录又有很多个属性，其中有一个特别的属性叫做类（例如信用程度的高，中，低）。分类器的目的就是分析输入的数据，并建立一个模型，并用这个模型对未来 的数据进行分类，数据分类技术在信用卡审批、目标市场定位、医疗诊断、故障检测、有效性分析、图形处理及保险欺诈分析等领域 ,都可以看到分类器广泛应用。 分类是一种典型的有监督的机器学习方法 3,其目的是从一组已知类别的数据中发现分类模型 ,以预测新数据的未知类别。 用于分类的数据是一组已知类别的样本，每个样本包含一组相同的属性。根据在分类中的作用，属性可以分为条件属性和目标属性两种。这样，一个样本就可以表示为 (2， .Y)的形式，其中， 类的目的就是发现 2, 种依赖关系又称为分类模型或者分类器。可以认为，分类器就是一个函数，它的输入是未知类别的样本，输出是样本的类别。 类器的构造方法 分类的方法不同，模型的表示形式就不同。利用决策树方法构造的分类模型就可能表示为树状结构或者分类规则，神经网络的分类模型则可表示为由单元和系数构成的网络模型，而贝叶斯分类的模型则表现为数学公式。 图 13 模型构造 模 型测试 模型应用 图 类的三个步骤 一个完整的分类过程一般包括模型构造，模型测试和模型应用这三步 4。具体地说，每个步骤的功能如下： (1)模型构造 分析样本的类别和其具备的一些特征之间的依赖关系，并将这种关系用特定的模型表示出来。例如，分析以往的病历，根据病人的症状和诊断结果，得到疾病诊断模型。用来构造模型的数据集称为训练数据集或者训练样本集，即训练集。 (2)模型测试 检测模型的准确度 ,最终得到描述每个类别的分类模型。用来评价模型的数据集称为测试数据集或者测试样本集 ,简称测试集。测试的过程是对测试数据依次检测，根据模型确定样本的类别，然后与实际类别相比较 ,如果相同 ,则称预测结果是正确的，否则说明预测结果是错误的。模型的准确度定义为测试集中结果正确的样本的比例。 (3)模型应用 利用得到的分类模型，预测在未知的情况下样本所属的类别。这个过程与模型评价基本相同，只是输入数据的类别是未知的。 结 人脸识别的 研究始于 60年代末， 率等参数为特征，建 成了一个半自动的人脸识别系统。早期的人脸识别方法通常是以人脸器官位置、尺度作为描述人脸的特征 。到了 20世纪 90年代人脸识别技术进一步发展。而基于人脸图像整体特征识别方法，取得了比较好的识别性能。提取有效的特征之后，识别的关键在于设计具有良好分类能力的分类器。通常线性分类器速度较快，而且实现方便，准确率也不错。而 于其方便实用的特点，是目前图像识别领域比较流行的方法。 数据 训练集 测试集 分类模型 类别 测试后的分类模型 新数据 14 第四章 发环境的选择 上使用最为广泛的数学软件，它具有相当强大的数值计算、数据处理、系统分析、图形显示，甚至符号运算功能，是一个完整的数学平台，在这个平台上，你只需寥寥数语就可以完成十分复杂的功能，大大提高了工程分析计算的效率。另外由于 是出现了为各个领域专门使用的工具箱 (即在某一研究领域常用数学工具的函数包 )，这些工具箱的出现更加促进了 但 大的功能只能在它所提供的平台上才能使用，也就是说，你必需在安装有 统的机器上使用 件，这样就给工程计算带来了很大不便；特别是，在 用的行解释方式执行代码，这样大大地限制了代码执行速度。 而 编程工作变得更加容易，开发投资的回报率趋于最大化。 外，将显示特性与 如语音或手写识别，而不必去重写程序。 创了全新的商业模 型，它使得一个公司可以用多种方法来把自己的技术商品化。 15 “用户界面友好”作了重新定义。终端用户能够享受一个智能化的、个性化的 能记住用户的个人设置，并在适当的时候，向用户使用的智能设备上发送适当的数据 10。 C#是微软公司发布的一种面向对象的、运行于 C#独有的特点： (1)中间代码：微软在用户选择何时 软公司很小心的声称 而是被编译成 了机器码。 (2)命名空间中的申明：当你创建一个程序的时候，你在一个命名空间里创建了一个或多个类。同在这个命名空间里 (在类的外面 )你还有可能声明界面，枚举类型和结构体。必须使用 (3)基本的数据类型： C#拥有比 C， C+或者 广泛的数据类型。这些类型是 样，所有这些类型都有一个固定的大小。又象 C 和 C+一样 ,每个数据类型都有有符号和无符号两种类型。与 同的是，一个字符变量包含的是一个 16 位的符。 C#新的数据类型是 据类型，对于货币数据，它能存放 28 位10进制数字。 (4)两个基本类：一个名叫 类是所有其他类的基类。而一个名叫 类也象 样是这个语言的一部分。作为语言的一部分存在意味着编译器有可能使用它 译器会创建一个 象来保存它。 (5)参数传递：方法可以被声明接受可变数 目的参数。缺省的参数传递方法是对基本数据类型进行值传递。 键字可以用来强迫一个变量通过引用传递，这使得一个变量可以接受一个返回值。 键字也能声明引用传递过程，与 同的地方是，它指明这个参数并不需要初始值。 (6)与 C#对 际上，最终有可能在任何 户和服务器端。 C#编写的类可以子类化一个以存在的 件；生成的类也能被作为一个 后又能使用。 所以 决定取其两者优点当研究学习时使用 c# k 近邻算法的程序 的探究 由前面的分析可知，需要对 6 现。 而 又因算法问题而使其计算量大，时间代价高；由于训练数据常驻内存，会占用大量的内存，增加成本。所以我们先对传统的 对于传统 代码如下 % % - - - - of % % if x / 8 |= (0 (x % 8); 0, ( y), （ 2） 识别图像 使用 主要代码如下： / ，给每个测试样例予 以一个类型 / 距离和权重成反比 & k) i = 0; i != ; +i) j = 0; j != d