近邻分类器-四川大学

近邻分类器（k-nearest neighbor classifier，简称k-NN分类器）是一种常见的机器学习算法，可用于分类和回归问题。

它的工作原理是根据输入实例的特征向量，在训练集中找出与该实例特征最相似的k 个实例，然后使用这k个实例中的多数类别（对于分类问题）或平均值（对于回归问题）作为预测结果。

在本文中，我们将介绍如何使用Matlab编程语言来构建k-NN分类器，以及如何实现k-NN分类方法。

我们将从k-NN分类器的基本原理开始介绍，然后逐步介绍Matlab代码的实现过程，并结合实例进行演示。

1. k-NN分类器的原理及特点k-NN分类器是一种基于实例的学习方法，不同于传统的基于模型的学习方法（如决策树、支持向量机等）。

它的主要特点包括：- 非参数化：k-NN分类器没有显式的模型参数，它的预测结果完全依赖于训练集中实例的分布。

- 适用性广泛：k-NN分类器适用于各种类型的数据，包括连续型、离散型、多类别、多标签等。

- 可解释性强：k-NN分类器的预测结果可以直观地解释为与输入实例最相似的训练集实例的类别。

2. Matlab中k-NN分类器的构建在Matlab中，使用Statistics and Machine Learning Toolbox工具箱可以方便地构建k-NN分类器。

我们需要加载训练集数据和对应的类别标签，然后使用fitcknn函数来构建k-NN分类器模型。

具体的步骤如下：2.1 加载训练集数据和类别标签在Matlab中，可以使用csvread函数或readtable函数来加载训练集数据，然后将数据分为特征向量和类别标签两部分。

例如： ```matlabdata = csvread('train_data.csv');X = data(:, 1:end-1); % 特征向量Y = data(:, end); % 类别标签```2.2 构建k-NN分类器模型使用fitcknn函数可以构建k-NN分类器模型，需要指定k的取值和距离度量方法等参数。

四川⼤学模式识别期末考试内容⼀．计算题1、在图像识别中，假定有灌⽊和坦克2种类型，它们的先验概率分别是0.7和0.3，损失函数如下表所⽰。

其中，类型w 1和w 2分别表⽰灌⽊和坦克，判决a 1=w 1，a 2=w 2。

现在做了2次实验，获得2个样本的类概率密度如下：5.02.0)|(1=ωx P 3.06.0)|(2=ωx P（1）试⽤最⼩错误率贝叶斯准则判决2个样本各属于哪⼀类？坦克、灌⽊。

（2）试⽤最⼩风险决策规则判决2个样本各属于哪⼀类？灌⽊、灌⽊。

答：（1）最⼩错误率贝叶斯准则，决策为坦克第⼀个样本：2121221111)|()|(5625.04375.01)|(1)|(4375.032143.0*6.07.0*2.07.0*2.0)()|()()|()|(ωωωωωωωωωω∈?>=-=-===+==∑=x x P x P x P x P P x p P x p x P j j j ，决策为灌⽊第⼆个样本：1121221111)|()|(449205.0795.01)|(1)|(795.044353.0*3.07.0*5.07.0*5.0)()|()()|()|(ωωωωωωωωωω∈?<==-≈-=≈=+==∑=x x P x P x P x P P x p P x p x P j j j（2）最⼩风险决策规则，决策为灌⽊第⼀个样本1212221212122212111211122211211)|()|(3175.25625.0*0.14375.0*4)|()|()|()|(35375.15625.0*24375.0*5.0)|()|()|()|(0.1425.0ωωλωλωλωλωλωλλλλλ∈?<=+=+===+=+======∑∑==x x a R x a R x P x P x P x a R x P x P x P x a R j j j j j j ，决策为灌⽊第⼆个样本12122212121222121112111)|()|(385.3205.0*0.1795.0*4)|()|()|()|(8075.0205.0*2795.0*5.0)|()|()|()|(ωωλωλωλωλωλωλ∈?<=+=+===+=+==∑∑==x x a R x a R x P x P x P x a R x P x P x P x a R j j j j j j2、给出⼆维样本数据(-1,1),(2,2),(1,-1),(-2,-2)，试⽤K-L 变换作⼀维数据压缩。

基于K-近邻法的分类器的研究与实现摘要模式识别的目的就是对未知的样本，判断它所在的类别。

人类的模式识别能力使得人们可以很好的认识周围的环境并与之交流，如果计算机也具有类似的能力，那么其智能程度将会大大提高，可以发挥更大的功能，更好的为人类服务。

本文的研究课题就属于计算机模式识别领域。

分类器是模式识别系统的重要组成部分；也是机器学习的重要研究领域。

本文主要研究对象是KNN分类方法，运用K近邻法(K Nearest Neighbor)对数据进行分类，并对分类结果进行比较研究。

本文的研究工作主要探讨基于K-近邻法的分类器的实现，主要集中在K-近邻法的理论分析，算法实现。

本文首先介绍了数据挖掘的目的、意义及现状，阐述了K-近邻算法在数据挖掘中的地位和作用，然后对K-近邻法进行了详细的研究与分析，并且实现基于K-近邻法的分类器。

本设计采用SQL Server 数据库系统和c#.net开发工具进行分析研究。

关键词：模式识别；数据挖掘；机器学习； K-近邻法；分类器THE RESEARCH & ACHIEVE OF CLASSIFIER BASED ON THE K-NEAREST NEIGHBOR ALGORITHMABSTRACTThe purpose of pattern recognition is judge it in the category for the unknown sample. The pattern recognition capabilities of human canmake it a good understanding of the environment around and exchange with them, If the computer also has a similar capability, its smart levelwill greatly improve ,the level they can play a greater role and better service to humanity. This research on the subject is a kind of computer pattern recognition.Classifier is an important component part in pattern recognition system;it is also an important research in the area of machine learning.This paper mainly targets KNN classification methods, using k-nearest neighbor for data classification, and compared the results.This article research on the achieve of classifier based on the k-nearest neighbor algorithm.Mainly concentrated in the k-nearest-neighbor theoretical analysis and algorithm .First of all,I introduce the purpose、meaning and recent development of data mining.and expatiate the status and function of k- nearest neighbour in this field.then research and analysis to the k-nearest-neighbor detailed and achieve theclassifier based on k-nearest-neighbor.I design this program with SQL Server database system and c #. net development tools for analysis and study.Key words: pattern recognition; data mining, machine learning; k nearest neighbour; classifier目录1 绪论 (1)1.1 课题背景及目的 (1)1.2 国内外研究状况 (2)1.3 课题研究方法 (2)1.4 论文构成及研究内容 (3)2 分类器概述 (4)2.1 分类器概念 (4)2.2 分类器构造方法 (4)2.3 近邻分类器的分类原理 (5)3 K-近邻法的研究与分析 (8)3.1 KNN概念 (8)3.2 K-近邻法算法研究 (9)3.2.1 K-近邻算法数学模型 (9)3.2.2 K-近邻法研究方法 (9)3.2.3 KNN算法需要解决的问题 (10)4 K-近邻法的分类器的设计与编程实现 (12)4.1 开发环境的选择 (12)4.1.1 数据库系统选择 (12)4.1.2 开发语言的选择 (12)4.2 程序设计实现 (14)4.2.1 界面设计 (14)4.2.2 功能模块设计 (15)4.2.3 数据库连接 (17)4.2.4程序运行与调试 (19)4.3 程序实现结果与分析 (20)5 结论 (21)参考文献 (22)致谢 (2)3附录源程序代码 (24)附件1 开题报告 (35)附件2 英文原文及翻译 (40)1 绪论模式识别或者通俗一点讲自动分类的基本方法有两大类，一类是将特征空间划分成决策域，这就要确定判别函数或确定分界面方程。

近邻分类分类器设计一、设计任务对“data3.m”数据，采用剪辑法、压缩法生成参考集，近似描绘其决策面，并用所有数据测试其分类效果。

二、设计原理1、最近邻法最近邻分类器(nearest neighborhood classifier, nnc): 最小距离分类器的一种极端的情况，以全部训练样本作为代表点，计算测试样本与所有样本的距离，并以最近邻者的类别作为决策。

最初的近邻法是由Cover 和Hart 于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。

最近邻法：将与测试样本最近邻样本的类别作为决策的结果。

对一个C 类别问题，每类有 i N 个样本,1,2,i C =，则第i 类i ω的判别函数为：()min ||||,1,2,,k i i i k g x x x k N =-= (1)因此，最近邻决策规则：若 ()min (),1,2,j i i g x g x i c ==(2)则决策 j x ω∈由上可以看出最近邻法在原理上最直观，方法上也十分简单，但明显的缺点就是计算量大，存储量大。

2、k -近邻法k -近邻法即为最近邻法的扩展，其基本规则是，在所有 N 个样本中找到与测试样本的k 个最近邻者，其中各类别所占个数表示成i k ,1,2,i C =，定义判别函数为：(),1,2,i i g x k i c == (3)因此，k -近邻决策规则：若 ()max j i ig x k = (4)则决策 j x ω∈k -近邻一般采用k 为奇数，跟投票表决一样，避免因两种票数相等而难以决策。

决策规则为：arg (),1,,i i j maxg x i c ==3、改进的近邻法近邻法的一个严重问题是需要存储全部训练样本，以及繁重的距离计算量。

从而提出了两类改进的方法：一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。

基于BP神经网络决策的KNN改进算法路敦利;宁芊;臧军【摘要】针对K近邻(KNN)算法中算法精度受K值选取影响较大的问题,提出了一种使用BP神经网络来优化KNN算法的改进算法来降低K值选取对算法精度的影响同时提高K近邻算法的准确率.所提改进算法主要是使用BP神经网络对K近邻算法分类完成后的结果进行改进优化.首先,通过对训练样本使用K值不同的K近邻算法进行初步分类,同一数据会得到多个不同的初步分类结果集;然后将初步分类结果集作为BP神经网络的输入,再对BP神经网络进行训练分类.在多个数据集上的实验表明,基于BP神经网络决策的K近邻改进算法降低了K值对算法精度的影响,同时极大地提高了分类的准确率.%Concerning the problem that the accuracy of K Nearest Neighbor (KNN) algorithm is greatly influenced by K value,an improved algorithm using BP neural network to optimize KNN algorithm was proposed to reduce the influence of K value selection on algorithm precision and improve the accuracy of KNN algorithm.The improved algorithm was used to optimize the results of KNN algorithm classification using BP neural network.First,by using the K Nearest Neighbor algorithm with different K values for the training samples,a number of different preliminary classification result sets were got for the samedata.Then,different preliminary classification result sets were used as the input of BP neural network for further training andclassification.Experiments on multiple data sets show that the improved KNN algorithm based on BP neural network decision making reduces theinfluence of K value on the accuracy of the algorithm and greatly improves the accuracy of classification.【期刊名称】《计算机应用》【年(卷),期】2017(037)0z2【总页数】4页(P65-67,88)【关键词】K近邻;BP神经网络;算法精度;分类算法;K值【作者】路敦利;宁芊;臧军【作者单位】四川大学电子信息学院,成都610065;四川大学电子信息学院,成都610065;中石化管道储运有限公司荆门输油处,湖北荆门448000【正文语种】中文【中图分类】TP301.6K近邻(K Nearest Neighbor, KNN)算法是解决分类问题中最为常用的算法之一，其算法具有原理简单易于理解、实现方便、分类有效等特点[1]。