基于最大最小距离的人脸识别
- 格式:doc
- 大小:284.50 KB
- 文档页数:13
人脸识别主要算法原理主流的人脸识别技术基本上可以归结为三类,即:基于几何特征的方法、基于模板的方法和基于模型的方法。
1. 基于几何特征的方法是最早、最传统的方法,通常需要和其他算法结合才能有比较好的效果;2. 基于模板的方法可以分为基于相关匹配的方法、特征脸方法、线性判别分析方法、奇异值分解方法、神经网络方法、动态连接匹配方法等。
3. 基于模型的方法则有基于隐马尔柯夫模型,主动形状模型和主动外观模型的方法等。
1. 基于几何特征的方法人脸由眼睛、鼻子、嘴巴、下巴等部件构成,正因为这些部件的形状、大小和结构上的各种差异才使得世界上每个人脸千差万别,因此对这些部件的形状和结构关系的几何描述,可以做为人脸识别的重要特征。
几何特征最早是用于人脸侧面轮廓的描述与识别,首先根据侧面轮廓曲线确定若干显著点,并由这些显著点导出一组用于识别的特征度量如距离、角度等。
Jia 等由正面灰度图中线附近的积分投影模拟侧面轮廓图是一种很有新意的方法。
采用几何特征进行正面人脸识别一般是通过提取人眼、口、鼻等重要特征点的位置和眼睛等重要器官的几何形状作为分类特征,但Roder对几何特征提取的精确性进行了实验性的研究,结果不容乐观。
可变形模板法可以视为几何特征方法的一种改进,其基本思想是:设计一个参数可调的器官模型(即可变形模板),定义一个能量函数,通过调整模型参数使能量函数最小化,此时的模型参数即做为该器官的几何特征。
这种方法思想很好,但是存在两个问题,一是能量函数中各种代价的加权系数只能由经验确定,难以推广,二是能量函数优化过程十分耗时,难以实际应用。
基于参数的人脸表示可以实现对人脸显著特征的一个高效描述,但它需要大量的前处理和精细的参数选择。
同时,采用一般几何特征只描述了部件的基本形状与结构关系,忽略了局部细微特征,造成部分信息的丢失,更适合于做粗分类,而且目前已有的特征点检测技术在精确率上还远不能满足要求,计算量也较大。
2. 局部特征分析方法(Local Face Analysis)主元子空间的表示是紧凑的,特征维数大大降低,但它是非局部化的,其核函数的支集扩展在整个坐标空间中,同时它是非拓扑的,某个轴投影后临近的点与原图像空间中点的临近性没有任何关系,而局部性和拓扑性对模式分析和分割是理想的特性,似乎这更符合神经信息处理的机制,因此寻找具有这种特性的表达十分重要。
人脸识别技术的使用技巧人脸识别技术是一种通过分析和比对人脸特征进行身份验证的先进技术。
随着技术的不断进步,人脸识别技术已经广泛应用于各个领域,如门禁系统、手机解锁、人证比对等。
为了更好地应用人脸识别技术,以下是几个使用技巧。
第一,保持合适的距离。
在进行人脸识别时,首先要确保与摄像头之间的距离合适。
一般推荐距离为0.5米至2米之间。
如果距离太近或太远,可能会导致识别失败或识别准确率降低。
因此,在使用人脸识别设备时要注意保持合适的距离。
第二,保持正脸。
人脸识别技术对于正脸的识别准确率较高,因此,在进行人脸识别时要尽量保持正脸朝向摄像头。
避免侧脸、低头或仰头等姿势,以免影响识别效果。
同时,要保持面部表情自然,不要做出夸张的表情,以提高识别准确率。
第三,注意光线条件。
光线条件的好坏直接影响人脸识别技术的效果。
在光线暗的环境下,可能会导致图像模糊、细节不清晰,从而影响识别准确率。
因此,在使用人脸识别设备时,要选择光线充足的环境,避免直接面对强光源,以获得更好的识别效果。
第四,定期更新人脸库。
人脸库是人脸识别技术的重要组成部分,包含了需要识别和比对的人脸信息。
为了提高识别准确率,定期更新人脸库非常重要。
随着时间的推移,人脸可能会发生变化,如年龄增长、发型改变等,如果不及时更新人脸库,可能导致无法识别的情况发生。
因此,要定期检测和更新人脸库,确保人脸信息的及时、准确。
第五,合理设置识别阈值。
识别阈值是人脸识别系统中的一个重要参数,用来控制识别的容错率和准确率。
阈值越高,识别的容错率越低,准确率越高;阈值越低,识别的容错率越高,准确率越低。
在使用人脸识别技术时,要根据实际需求和场景,合理设置识别阈值,确保满足安全性和便利性的要求。
第六,保护用户隐私。
在使用人脸识别技术时,保护用户的个人隐私是非常重要的。
要确保人脸识别系统的安全性,防止人脸数据被非法获取和滥用。
同时,在收集和使用人脸数据时,要遵循相关法律法规,取得用户的明确同意,严格限制数据的使用范围,加强数据保护措施,以保护用户的个人隐私权益。
基于主成分分析(PCA)的⼈脸识别技术本科期间做的⼀个课程设计,觉得⽐较好玩,现将之记录下来,实验所⽤。
1、实验⽬的(1)学习主成分分析(PCA)的基础知识;(2)了解PCA在⼈脸识别与重建⽅⾯的应⽤;(3)认识数据降维操作在数据处理中的重要作⽤;(4)学习使⽤MATLAB软件实现PCA算法,进⾏⼈脸识别,加深其在数字图像处理中解决该类问题的应⽤流程。
2、实验简介(背景及理论分析)近年来,由于恐怖分⼦的破坏活动发⽣越发频繁,包括⼈脸识别在内的⽣物特征识别再度成为⼈们关注的热点,各国均纷纷增加了对该领域研究的投⼊。
同其他⽣物特征识别技术,如指纹识别、语⾳识别、虹膜识别、DNA识别等相⽐,⼈脸识别具有被动、友好、⽅便的特点。
该技术在公众场合监控、门禁系统、基于⽬击线索的⼈脸重构、嫌疑犯照⽚的识别匹配等领域均有⼴泛应⽤。
⼈脸识别技术是基于⼈的脸部特征,对输⼊的⼈脸图像或者视频流,⾸先判断其是否存在⼈脸。
如果存在⼈脸,则进⼀步的给出每个脸的位置、⼤⼩和各个主要⾯部器官的位置信息。
其次并依据这些信息,进⼀步提取每个⼈脸中所蕴涵的⾝份特征,并将其与已知的⼈脸进⾏对⽐,从⽽识别每个⼈脸的⾝份。
⼴义的⼈脸识别实际包括构建⼈脸识别系统的⼀系列相关技术,包括⼈脸图像采集、⼈脸定位、⼈脸识别预处理、⾝份确认以及⾝份查找等;⽽狭义的⼈脸识别特指通过⼈脸进⾏⾝份确认或者⾝份查找的技术或系统。
我们在处理有关数字图像处理⽅⾯的问题时,⽐如经常⽤到的图像查询问题:在⼀个⼏万或者⼏百万甚⾄更⼤的数据库中查询⼀幅相近的图像。
其中主成分分析(PCA)是⼀种⽤于数据降维的⽅法,其⽬标是将⾼维数据投影到较低维空间。
PCA形成了K-L变换的基础,主要⽤于数据的紧凑表⽰。
在数据挖掘的应⽤中,它主要应⽤于简化⼤维数的数据集合,减少特征空间维数,可以⽤较⼩的存储代价和计算复杂度获得较⾼的准确性。
PCA法降维分类原理如下图所⽰:如上图所⽰,其中五⾓星表⽰⼀类集合,⼩圆圈表⽰另⼀类集合。
第一节主成分分析基本理论一、什么是主成分分析?主成分分析为Principle component analysis[10,11,12]的中文翻译,其英文简写为PCA。
它是一种非常流行和实用的数据分析技术,最重要的应用是对原有数据进行简化。
主成分分析可以有效的找出数据中最“主要”的元素和结构,去除噪声和冗余,将原有的复杂数据降维处理,揭示出隐藏在复杂数据背后的简单结构。
它的优点是简单,而且无参数限制,可以方便的应用与各个场合。
因此应用极其广泛,从神经科学到计算机图形学都有它的身影。
PCA被称为应用线形代数最有价值的结果之一。
本节下面的内容将开始讲解PCA的具体内容。
具体安排为:首先将从一个简单的例子开始说明PCA应用的场合以及想法的由来,进行一个比较直观的解释;然后加入数学的严格推导,引入线形代数,进行问题的求解。
随后将揭示PCA与SVD(Singular Value Decomposition)之间的联系以及如何将之应用于真实世界。
最后将分析PCA理论模型的假设条件以及针对这些条件可能进行的改进。
二、例子在实验科学中常常遇到的情况是,使用大量的变量代表可能变化的因素,例如光谱、电压、速度等等。
在实际中,由于实验环境和观测手段的限制,实验数据往往变得极其的复杂,混乱,而且数据存在很大的冗余。
如何对数据进行分析,取得隐藏在数据背后变量间的本质关系,是一个很困难的问题。
在神经科学、气象学、海洋学等等学科实验中,假设的变量个数往往非常之多,但是真正的影响因素以及它们之间的关系可能又是非常之简单的。
下面的例子取自一个我们都非常熟悉的物理学中的实验。
这个实验看上去似乎过于简单,但足以说明问题。
如图表 4.1所示,这是一个理想弹簧运动规律的测定实验。
假设球是连接在一个无质量无摩擦的弹簧之上,从平衡位置沿x 轴拉开一定的距离然后释放。
图4.1理想弹簧运动规律模型对于一个具有先验知识的实验者来说,这个实验是非常容易的。
人脸识别最好用的距离函数人脸识别技术已经成为了现代社会中不可或缺的一部分。
在人脸识别技术中,距离函数是非常重要的一个组成部分。
距离函数的作用是将两个人脸之间的相似度量化,从而判断它们是否属于同一个人。
在本文中,我们将探讨人脸识别最好用的距离函数。
首先,我们需要了解距离函数的基本概念。
距离函数是一种用于测量两个对象之间距离的函数。
在人脸识别中,距离函数的作用是将两个人脸之间的相似度量化。
距离函数的值越小,表示两个人脸越相似,反之则越不相似。
目前,人脸识别最常用的距离函数有欧氏距离、余弦相似度和曼哈顿距离等。
其中,欧氏距离是最常用的距离函数之一。
欧氏距离是指两个向量之间的距离,即两个向量之间的欧氏距离越小,表示它们越相似。
欧氏距离的计算公式为:d(x,y) = sqrt((x1-y1)^2 + (x2-y2)^2 + ... + (xn-yn)^2)其中,x和y分别表示两个向量,n表示向量的维度。
除了欧氏距离之外,余弦相似度也是人脸识别中常用的距离函数之一。
余弦相似度是指两个向量之间的夹角余弦值,即两个向量之间的余弦相似度越大,表示它们越相似。
余弦相似度的计算公式为:cos(x,y) = (x1y1 + x2y2 + ... + xnyn) / (sqrt(x1^2 + x2^2 + ... +xn^2) * sqrt(y1^2 + y2^2 + ... + yn^2))最后,曼哈顿距离也是人脸识别中常用的距离函数之一。
曼哈顿距离是指两个向量之间的曼哈顿距离,即两个向量之间的曼哈顿距离越小,表示它们越相似。
曼哈顿距离的计算公式为:d(x,y) = |x1-y1| + |x2-y2| + ... + |xn-yn|综上所述,欧氏距离、余弦相似度和曼哈顿距离都是人脸识别中常用的距离函数。
在实际应用中,我们需要根据具体的场景和需求选择最合适的距离函数。
例如,在需要考虑人脸姿态和光照变化等因素的情况下,余弦相似度可能更适合;而在需要考虑人脸形状和轮廓等因素的情况下,欧氏距离可能更适合。
人脸识别常用算法人脸识别是一种通过计算机视觉技术对图像或视频中的人脸进行检测、识别和验证的技术。
它在安防监控、人脸支付、人脸解锁等领域有着广泛的应用。
人脸识别的核心在于算法的设计与优化,下面将介绍几种常用的人脸识别算法。
一、特征提取算法特征提取算法是人脸识别的关键步骤,它通过对人脸图像进行分析和处理,提取出具有代表性的特征信息。
常用的特征提取算法有主成分分析(PCA)算法、线性判别分析(LDA)算法和局部二值模式(LBP)算法。
PCA算法通过对人脸图像进行降维,将高维的图像数据映射到低维的特征空间中,然后利用这些特征进行分类和识别。
LDA算法则是通过最大化类间距离和最小化类内距离的方式,寻找最优的投影方向,以实现人脸的区分和识别。
LBP算法则是一种局部特征描述算法,它通过对图像的每个像素点与其周围像素点进行比较,得到一个二进制编码,从而提取出人脸的纹理信息。
二、人脸检测算法人脸检测算法是人脸识别的前置步骤,它主要用于检测图像或视频中是否存在人脸,并将其位置标记出来。
常用的人脸检测算法有Viola-Jones算法、卷积神经网络(CNN)算法和级联分类器算法。
Viola-Jones算法是一种基于机器学习的人脸检测算法,它通过训练一个级联的强分类器来实现人脸的检测。
CNN算法则是一种深度学习算法,它通过构建多层的卷积神经网络来提取图像的特征,并通过分类器进行人脸检测。
级联分类器算法则是将多个分类器组合在一起,通过级联的方式进行人脸检测,以提高检测的准确率和速度。
三、人脸识别算法人脸识别算法是通过对提取的人脸特征进行匹配和比对,从而实现对人脸的识别和验证。
常用的人脸识别算法有支持向量机(SVM)算法、人工神经网络(ANN)算法和卷积神经网络(CNN)算法。
SVM算法是一种监督学习算法,它通过构建一个超平面来实现对不同类别的人脸进行分类和识别。
ANN算法则是一种模拟人脑神经元工作原理的算法,它通过构建多层的神经网络来实现对人脸的识别。
1 绪论1.1人脸表情识别研究的目的和意义人脸是人最重要的外貌特征,由于脸部信息可以通过非接触的方式(如摄像头)取得,所以非常适合于作为身份鉴别的依据。
人脸识别就是对于输入的人脸图像或者视频,首先判断其中是否存在人脸,如果存在人脸,则进一步确定每张人脸的位置、大小和各个主要面部器官的位置信息,并依据这些信息,进一步提取每张人脸中所蕴含的身份特征,并将其与已知人脸库中的人脸进行对比,从而识别每张人脸所代表的个人。
人脸识别是一个交叉学科,它的研究内容涉及计算机视觉、模式识别、计算机图形学、图像处理、生理学、心理学、认知科学等。
人脸识别技术可采用非接触式的、连续的和实时的方式,在国家安全、军事安全和公安、司法、民政、金融、民航、海关、边境、口岸、保险及民用等领域实际应用具有极广阔的前景。
这一技术典型应用如下:(1)身份鉴定(一对多的搜索):在鉴定模式下,确定一个人的身份,该技术可以快速地计算出实时采集到的面纹数据与面像数据库中已知人员的面纹数据之间的相似度,给出一个按相似度递减排列的可能的人员列表,或简单地返回鉴定结果(相似度最高的)和相对应的可信度。
(2)身份确认(一对一的比对):在确认模式下,待确认人已知的面纹数据可以存储在智能卡中或数码记录中,该技术只需要简单地将实时的面纹数据与存储的数据相比对,如果可信度超过一个指定的阀值,则比对成功,身份得到确认。
(3)监视:可以在监控范围内发现人脸,而不论其远近和位置,能连续地跟踪该人脸图像并将其从背景中分离出来,将面像与监控列表进行比对。
整个过程完全是无需干预的,连续的和实时的。
(4)面像数据压缩:能将面纹数据压缩到84字节以便用于智能卡、条形码或其他仅含有有限存储空间的设备中。
(5)多通道的人机交互界面:可以把跟踪得到的人脸表情作为一种人机交互的手段。
为使用者提供一个个性化、智能、便捷的工作环境,这也是智能计算机研究的重要内容。
人脸表情识别研究的主要目的在于:(1)在人机接口中实现计算机对人脸面部表情的自动识别;(2)在视频片段检索中实现面部表情的跟踪与识别;(3)研究人脸表情编码模型,解决低带宽的脸部数据传输、多媒体中的脸部图像压缩等问题。
第一章.方案概述1.1项目概况随着经济的发展,城镇建设速度加快,以及互联网的突飞猛进,导致城市中人口密集,流动人口增加,引发了城市建设中的交通、社会治安、重点区域防范、网络犯罪日益突出等城市管理问题,今后现代化城市的建设、网络信息必然将安全作为重中之重,与城市的经济建设处于同等重要的地位.近年来,社会犯罪率呈逐年升高的趋势,特别是网络犯罪更加的严重,网络逃犯频频发生,罪犯的犯罪手法也更加隐蔽和先进,给广大公安人员侦破案件增加了难度。
同时,恶性事件时有发生,使人们对公共生活场所的安全感普遍降低。
同时公安人员在对通缉犯进行人工排查时如大海捞针,成功率极低,效果也不明显。
主要有如下实际问题:1.首先,由于罪犯群体不断扩大,要在数以百万计的人员照片库中找出犯罪嫌疑人,不仅费时费力,还有可能造成遗漏等情况,破案的效率大打折扣。
2.其次,目前公安机关侦察案件大多数仍然依靠事后追查和通缉,对已经发生的案件造成的损失很难有效弥补。
3。
最后,如果在案发的同时即能防患于未然,就能第一时间将损失控制在最小范围内.平安城市建设从最初的视频监控、卡口电警建设,系统已大量掌握了视频图像资源和卡口车辆数据和价值图片,但是针对人员侦查,身份确认还是需要通过技侦或网侦手段,无法充分利用视频图像资源快速定位人员身份。
即使出动大量警力,采用“人海战术”但受制于肉眼识别劳动强度的极限,再加上人工排查效率不足,视频图像拍摄受光线、角度倾斜等不确定因素影响,无法保证查找的准确性和时效性,尤其出现突发紧急案件时,往往会贻误最佳破案时机。
如何提供更加丰富以及实用的“人像防控”应用,从“事后被动侦查"到“事前主动预警”将是平安城市下一建设阶段面临的主要需求。
1.2需求分析人像大数据系统采用高效的人脸检测定位及识别比对系统,可以第一时间帮助公安侦查人员快速识别辨别特定人员真实身份,把过去人工排查海量的视频图像资源比对需求变成现实,从而有效的为公安视频侦查、治安管理、刑侦立案等工作提供实战上的有效帮助和解决方法.第二可帮助公安侦查人员办案时候追查和通缉,真正从打变为防,能够极大的减少警力资源浪费和事故发生概率。
面向人脸识别的最大间距准则优化研究摘要:随着人工智能技术的不断发展,人脸识别技术已经广泛应用于各个领域。
然而,在实际应用中,人脸识别技术仍然存在一些问题,如识别准确率不高、受光线、角度等因素影响较大等。
本文基于最大间距准则,提出了一种优化人脸识别技术的方法,并在实验中验证了该方法的有效性。
关键词:人脸识别;最大间距准则;优化一、引言人脸识别技术是近年来人工智能领域的一个热门研究方向,它已经广泛应用于安防、金融、医疗、教育等领域。
然而,人脸识别技术在实际应用中仍然存在一些问题,如识别准确率不高、受光线、角度等因素影响较大等。
为了解决这些问题,研究人员提出了各种优化方法,如人脸对齐、特征提取、分类器设计等。
本文基于最大间距准则,提出了一种优化人脸识别技术的方法,并在实验中验证了该方法的有效性。
二、最大间距准则最大间距准则是一种分类算法,它的基本思想是在不同类别之间找到一个最大的间隔,使得不同类别的样本尽可能地分开。
最大间距准则是支持向量机(SVM)算法的基础,它被广泛应用于模式识别、图像分类等领域。
在人脸识别中,最大间距准则可以用来优化特征空间的划分。
具体地,假设我们有两个类别的人脸样本,分别记为X1和X2。
我们的目标是找到一个超平面,将这两个类别分开。
超平面可以表示为:w·x + b = 0其中,w是法向量,b是截距。
对于任意一个样本x,它到超平面的距离可以表示为:d(x) = |w·x + b| / ||w||其中,||w||是w的范数。
我们的目标是找到一个超平面,使得不同类别之间的最小距离最大化。
这个最小距离可以表示为:dmin = min(d(x1), d(x2))因此,我们的优化目标是最大化dmin。
具体地,我们可以将优化问题转化为下面的二次规划问题:min 1/2||w||^2s.t. y1(w·x1 + b) >= 1, y2(w·x2 + b) <= -1其中,y1和y2分别表示两个类别的标签。
面向人脸识别的最大间距准则优化研究人脸识别技术在社会生活中得到了广泛的应用,但是在实际应用中,由于人脸图像的质量、光照条件、角度等因素的影响,人脸识别的准确率和鲁棒性受到了很大的挑战。
本文针对这一问题,提出了一种基于最大间距准则的人脸识别优化方法。
首先,通过对人脸图像进行预处理,提取出人脸的特征点;其次,利用最大间距准则对特征点进行优化,提高人脸识别的准确率和鲁棒性。
实验结果表明,该方法在不同光照条件和角度下均能取得较好的识别效果,具有很好的应用前景。
关键词:人脸识别;最大间距准则;特征点;优化方法;鲁棒性;准确率一、引言人脸识别技术是一种通过计算机技术对人脸图像进行处理,从而实现对人脸进行自动识别的技术。
该技术广泛应用于安全监控、人脸识别支付、智能门禁等领域。
但是,在实际应用中,由于人脸图像的质量、光照条件、角度等因素的影响,人脸识别的准确率和鲁棒性受到了很大的挑战。
因此,如何提高人脸识别的准确率和鲁棒性,成为了当前研究的热点问题。
本文提出了一种基于最大间距准则的人脸识别优化方法。
该方法通过对人脸图像进行预处理,提取出人脸的特征点;利用最大间距准则对特征点进行优化,提高人脸识别的准确率和鲁棒性。
实验结果表明,该方法在不同光照条件和角度下均能取得较好的识别效果,具有很好的应用前景。
二、相关工作目前,人脸识别技术主要包括基于特征匹配、基于模板匹配、基于神经网络等方法。
其中,基于特征匹配的方法是最常用的一种人脸识别方法。
该方法通过对人脸图像中的特征点进行匹配,从而实现对人脸的自动识别。
但是,由于人脸图像的质量、光照条件、角度等因素的影响,特征点的匹配精度受到了很大的挑战。
为了提高特征点匹配的精度,研究者们提出了很多优化方法。
例如,利用SIFT算法对特征点进行提取和匹配,可以提高匹配的准确率和鲁棒性;利用LBP算法对人脸图像进行特征提取,可以提高人脸识别的效果。
但是,这些方法仍然存在一些问题,例如对光照条件和角度的鲁棒性较差等。
Neighbor Search with Global Geometry:A Minimax Message PassingAlgorithm基于全局数据集合结构的近邻搜索:极大极小信息传递算法人脸识别简介:人脸识别技术是基于人的脸部特征,对输入的人脸图象或者视频流 . 首先判断其是否存在人脸 , 如果存在人脸,则进一步的给出每个脸的位置、大小和各个主要面部器官的位置信息。
并依据这些信息,进一步提取每个人脸中所蕴涵的身份特征,并将其与已知的人脸进行对比,从而识别每个人脸的身份。
广义的人脸识别实际包括构建人脸识别系统的一系列相关技术,包括人脸图像采集、人脸定位、人脸识别预处理、身份确认以及身份查找等;而狭义的人脸识别特指通过人脸进行身份确认或者身份查找的技术或系统。
人脸识别技术中被广泛采用的区域特征分析算法,它融合了计算机图像处理技术与生物统计学原理于一体,利用计算机图像处理技术从视频中提取人像特征点,利用生物统计学的原理进行分析建立数学模型,即人脸特征模板。
利用已建成的人脸特征模板与被测者的人的面像进行特征分析,根据分析的结果来给出一个相似值。
通过这个值即可确定是否为同一人。
基本算法:1.基于人脸特征点的识别算法(Feature-based recognition algorithms )。
2.基于整幅人脸图像的识别算法(Appearance-based recognition algorithms )。
3.基于模板的识别算法(Template-based recognition algorithms )。
4.利用神经网络进行识别的算法(Recognition algorithms using neural network )。
5.利用线性回归进行识别的算法。
6.利用稀疏表示进行识别的算法。
我的课题是利用最小最大距离进行人脸识别的算法( Neighbor with Global Geometry :A Minimax Message Passing Algorithm )核心算法:1. k-Nearest Neighbor algorithm (k 邻近算法)K 最近邻(k-Nearest Neighbor ,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。
该方法的思路是:如果一个样本在特征空间中的k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
KNN 算法中,所选择的邻居都是已经正确分类的对象。
该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
KNN 方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。
由于KNN 方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN 方法较其他方法更为适合。
具体来说就是在N 个已知样本中,找出X 的k 个近邻。
设这N 个样本中,来自1w 类的样本有1N 个,来自2w 类的有2N 个,…,来自c w 类的有c N 个,若12,,...,c k k k 分别是k 个近邻中属于12,...,c w w w 类的样本数,则我们可以定义判别函数为:(),1,2,...,i i g x k i c ==决策规则为:若 ()max j i i g x k =则决策j x w ∈。
上图中,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。
2. minimum spanning tree (最小生成树)在一给定的无向图 G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边(即 ),而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集(即 )且为无循环图,使得 w(T) 最小,则此 T 为 G 的最小生成树。
许多应用问题都是一个求无向连通图的最小生成树问题。
例如:在设计电子线路时,常常要把数个元件的引脚连接在一起,使其电位相同。
要是n 个引脚互相连通,可以使用n-1条连接线,每条连接线连接两个引脚。
在各种连接方案中,通常希望找出连接线最小的接法。
可以把这一接线问题模型化为一个无向连通图G=(V,E ),其中V 是引脚集合,E 是每对引脚之间可能互联的集合。
对图中每一条边,都有一个权值 , 表示 u 和 v 的代价(需要接线数目)。
我们希望找出一个无回路的子集 ,它连接了所有的顶点,且其权值之和:为最小。
因为T 无回路且连接所有的顶点,所以它必然是一棵树,称为生成树(spanning tree ),因为它“生成”了图G 。
把确定树T 的问题称为最小生成树。
3. 欧氏距离欧几里得度量定义欧几里得空间中,点 x = (x1,...,xn) 和 y = (y1,...,yn) 之间的距离为:(u,v)E ∈(,)w u v T E ⊆(,)()(,)u v Tw T w u v ∈=∑向量的自然长度,即该点到原点的距离为.它是一个纯数值。
在欧几里得度量下,两点之间直线最短。
欧氏距离变换在数字图像处理中的应用范围很广泛,尤其对于图像的骨架提取,是一个很好的参照。
论文分析:对于人脸识别来讲,我们需要将人脸的正面图片转换成为矩阵,通过数字矩阵来表征人脸,每张人脸图片都是一个1024*1的矩阵,在不同的光照和位置的环境下,每个人一共有10张不同的图片,即1024*10矩阵。
一共40个人,则会有一个1024*400矩阵。
我们要做的工作就是给定一个这40个中的一个人的人脸数据,对人脸数据进行鉴别分类,最后确定这张人脸是哪个人。
具体来讲,我们都会用kNN算法进行分类,用欧氏距离计算出测试样本到训练样本的距离,并对最近的距离进行排列,对k取值,例如取5,那么分析前5个中哪一类占比重大,如果一类有3个,那么将把测试样本归入1类中。
但是,利用欧氏距离进行kNN分类存在问题,尤其是在基于全局数据几何结构的邻近搜索中,见下图:对于(a)图来讲,用欧式距离结果是正确的,可以把黑星分类正确,但是对于(b)图来讲,用欧式距离会把黑星分类给蓝色的叉号一类,造成分类错误。
对于(c)图,绿线以上的黑点会分类到红圈中,绿线以下的黑点会分类到蓝叉中。
由此会发现欧式距离来对具有几何结构的数据进行分类会造成严重的误差。
然而,欧式距离更适用于具有球形分布结构的数据,人脸数据一般不满足这一条件,最大最小距离(minimax distance)基于数据的流型结构,是一种更适合人脸的度量方法。
下面介绍用构造最小生成树来计算距离然后进行分类。
用最小生成树得到一棵权值之和最小的树,由最小生成树的性质可知,从一个点到任何一个端点的路径是唯一的,那么我们定义每一个训练样本点a到测试样本点b的距离d为:d等于从a到b路径上所有点的两点之间的最大值。
然后记录下来这个距离,那么每个训练样本到测试样本点的距离都计算并保存起来,为了达到更加精确减小误差,我们在距离d的基础上加上(λ*欧式距离),得到最终的距离,根据kNN算法,对这些距离排序,根据k的取值不同,最后得到哪个类标所占的比重更大,就把测试样本分类过去。
几点需要注意的,1.要把所有的测试样本和训练样本加到一起来生成MST。
2.把测试样本加进去一起生成树的原因是能够较为准确的反应几何流线型。
结果的分析就是,例如,我们从400个样本中选取200个特征脸数据当做测试样本,另外200张脸当做训练样本,因为我们已知测试样本属于的类标,根据分类结果的样本类标分析结果,如果180个样本相符合,那么正确率就是180/200*100%=90%。
算法设计:1. 对1024*400的人脸数据建立全连接,即每张人脸数据到其他人脸数据的欧式距离,构造一个全连接。
2. 生成最小生成树MST。
3. 计算测试样本到训练样本的距离(A=MMD+0.01*ED;MMD是最小生成树计算得到的两点之间的距离,ED 是两点之间的欧式距离,加上欧式距离是因为太多点之间点的距离是相等的,使得最终距离之间产生区分)。
4. 从生成的距离矩阵中提取测试离样本,然后对每一个测试样本到所有训练样本的距离进行排序,用kNN算法取前k个距离最近的训练样本,比较所占比例最大的训练样本类,将测试样本分类到训练样本类中。
5. 最终根据测试样本分类正确的数目比上测试样本的总量得到精度accuracy。
精确度分析:影响精确度(accuracy)有以下几个方面:①样本维度。
②λ的取值大小。
③k的选取。
④测试样本和训练样本的比例(label_train的设置)。
⑤精确度的平均次数n。
结果如下:维度改变&k值改变λ=0.01/label_train>0/n=20k样本维度 1 2 3 4 5 6 7 8 ORL_32*32(1024*400) 85.1 77.03 75.34 68.74 63.31 57.48 55.76 52.77 data_test_JAFFE(191*213)98.78 97.73 97.73 98.17 97.82 96.12 95.98 94.54 data_test_ORL(88*400)84.83 76.55 72.78 68.07 63.04 56.35 55 52.21 k样本维度9 10 12 15 20 50 100ORL_32*32(1024*400) 49.04 44.34 36.07 30.75 25.01 7.81 2.23data_test_JAFFE(191*213)93.19 92.32 92.45 85.69 68.22 68.61data_test_ORL(88*400)48.96 45.8 36.68 29.63 24.07 7.1 2.16)λ改变(A=MMD+*ED维度=1024*400/k=3/label_train>0/n=20λ0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 (%) 73.68 73.71 72.53 73.7 72.83 75.04 72.25 71.78 λ0.09 0.1 0.12 0.14 0.18 0.2 0.5 0.9 (%) 73.4 72.73 73.62 72.4 72.91 71.31 71.35 71.34label_train改变(测试样本和训练样本的比例)维度=1024*400/λ=0.01/k=3/n=20label_train 0.01/0.99 0.02/0.98 0.03/0.97 0.05/0.95 0.08/0.92 0.1/0.9 0.2/0.8 (%) 93.11 91.62 94.15 91.26 91.19 90.34 87.1 label_train 0.3/0.7 0.4/0.6 0.5/0.5 0.6/0.4 0.7/0.3 0.8/0.2 0.9/0.1 (%) 83.09 78.51 73.42 67.2 52.71 39.89 21.05N(平均次数)改变维度=1024*400/λ=0.01/k=3/label_train>0N 1 2 3 4 5 6 7 8 9 10 (%) 75.14 74.2 73.9 75.09 75.5 75.28 75 73.34 71.24 75.46 N 11 12 13 14 15 16 17 18 19 20 (%) 73.79 74.3 74.8 73.76 73.5 73.22 73 72.02 72.57 73.41从上面表格的分析数据我们可以看出:1.精确度的平均次数n对精确度基本上没有影响。