[课件]K最近邻方法PPT

格式：ppt
大小：342.50 KB
文档页数：45

下载文档原格式

近邻法

N A1
（2）采用抽样的办法，使之能自适应选择k；
“科研反哺教学”，将自己的研究工作融入课堂；
6.3.2 核近邻法（续）
贝叶斯决策器
学习方法
4 3 2
分类错误率 5.5% 4.6% 4.1%
KNN （k=3） BKNN 贝叶斯决策器
KNN
1 0 -1
三种方法的分类错误率比较
BKNN
-2 -3 -4 -4
本人解决方案：
NN (Fix, 1951)
KNN (Yu,2002) (Peng,2004) BNN (Homes,2002)
定义最优核距离 (本章) 核化 (本章)
BKNN (本章)
（1）推导出“最优核距离”：
1 rko x , xl rko x, xl N A1 1 NA B x, xi , xl B x, xi , xl N i 1 A i 1
J. Peng. Adaptive Quasiconformal Kernel Nearest Neighbor Classification. IEEE Trans PAMI[J]. 2004, 26(5): 656 - 661.
Rd
x1 , t1 1 x5 , t5 1 1
6.1.1 关于近邻法
1951年Fix和Hodges首次提出
第 w1 类
第 w2 类
最经典的模式识别方法之一方法简单，便于理论分析
x
x1
x4
是其它模式识别方法的标尺
“距离”的度量方式有很多种
近邻法原理示意图
6.1.2 近邻法应用实例：人脸表情识别
欲解决的问题：
七类表情

K最近邻算法

K最近邻算法K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。

所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。

kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。

该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

kNN方法在类别决策时，只与极少量的相邻样本有关。

由于kNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，kNN方法较其他方法更为适合。

KNN算法的机器学习基础显示相似数据点通常如何彼此靠近存在的图像大多数情况下，相似的数据点彼此接近。

KNN算法就是基于这个假设以使算法有用。

KNN利用与我们童年时可能学过的一些数学相似的想法(有时称为距离、接近度或接近度)，即计算图上点之间的距离。

例如，直线距离(也称为欧氏距离)是一个流行且熟悉的选择。

KNN通过查找查询和数据中所有示例之间的距离来工作，选择最接近查询的指定数字示例( K )，然后选择最常用的标签(在分类的情况下)或平均标签(在回归的情况下)。

在分类和回归的情况下，我们看到为我们的数据选择正确的K是通过尝试几个K并选择最有效的一个来完成的。

KNN算法的步骤1.加载数据2.将K初始化为你选择的邻居数量3.对于数据中的每个示例4.3.1 根据数据计算查询示例和当前示例之间的距离。

5.3.2 将示例的距离和索引添加到有序集合中6.按距离将距离和索引的有序集合从最小到最大(按升序)排序7.从已排序的集合中挑选前K个条目8.获取所选K个条目的标签9.如果回归，返回K个标签的平均值10.如果分类，返回K个标签的模式'为K选择正确的值为了选择适合你的数据的K，我们用不同的K值运行了几次KNN算法，并选择K来减少我们遇到的错误数量，同时保持算法在给定之前从未见过的数据时准确预测的能力。

K近邻算法PPT课件

• 给定一个目标点，搜索其最近邻。首先找到包含目标点的叶结点；然后从该叶结点出发，依次回退到父结点；不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。这样搜索就被限制在空间的局部区域上，效率大为提高。
• 包含目标点的叶结点对应包含目标点的最小超矩形区域。以此叶结点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体内部。然后返回当前结点的父结点，如果父结点的另一子结点的超矩形区域与超球体相交，那么在相交的区域内寻找与目标点更近的实例点。如果存在这样的点，将此点作为新的当前最近点。
➢ 问题：给这个绿色的圆分类？ ➢ 如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝
色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。 ➢ 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。
区域内没有实例时终止。在此过程中，将实例保存在相应的结点
上。
2020/7/23
9
K近邻法的实现：kd树
2020/7/23
10
K近邻法的实现：kd树
2020/7/23
11
K近邻法的实现：kd树
➢ 搜索kd树
• 利用kd树可以省去大部分数据点的搜索，从而减少搜索的计算量。这里以最近邻为例，同样的方法可以应用到K近邻。
2020/7/23
5
K近邻的三个基本要素
2020/7/23
6
K近邻的三个基本要素
➢ K值的选择
• 如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测， “学习”的近似误差会减小，只有与输入实例较近的训练实例才会对预测结果起作用。但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感。换句话说，k值的减小意味着整体模型变得复杂，容易发生过拟合。

【最新】KNN分类算法PPT 课件教案讲义(获奖作品) 图文

k 近邻算法(knn, k nearest neighbor)
算法基本介绍
• k近邻的非正式描述，就是给定一个样本集 exset，样本数为M，每个样本点是N维向量，对于给定目标点d，d也为N维向量，要从 exset中找出与d距离最近的k个点(k<=N)，当k=1时，knn问题就变成了最近邻问题。最原始的方法就是求出exset中所有样本与d 的距离，进行按出小到大排序，取前k个即为所求，但这样的复杂度为O(N)，当样本数大时，效率非常低下.
算法描述
• 该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距离最近（最相似）的 K 篇文本，根据这 K 篇文本所属的类别判定新文本所属的类别 • 右图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果 K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。
算法描述
• 算法分为以下几步：
一、:根据特征项集合重新描述训练文本向量二、:在新文本到达后，根据特征词分词新文本，确定新文本的向量表示三、:在训练文本集中选出与新文本最相似的 K 个文本，计算公式为：
算法描述
• 其中，K 值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整 K 值，一般初始值定为几百到几千之间。（这里K采取随机取值） • 四、:在新文本的 K 个邻居中，依次计算每类的权重，计算公式如下：
• 其中， x为新文本的特征向量， Sim(x,di)为相似度计算公式，与上一步骤的计算公式相同，而y(di,Cj)为类别属性函数，即如果di 属于类Cj ，那么函数值为 1，否则为 0。 • 五、:比较类的权重，将文本分到权重最大的那个类别中。

近邻法

i

则有Bayes条件错误率
P * (e | x) 1 P(m | x)
因此 P* P * (e | x) p ( x) dx

对于两类问题，由前面公式
N
lim PN (e | x) 1 P (i | x)
2 i 1
2
4.5.1最近邻法二、最近邻法的错误率分析
4.5.1最近邻法二、最近邻法的错误率分析
图4.14示出近邻法的上下界。一般地，最近邻法的错误率落在图中的阴影区域中。 c类别最近邻
分类器可能渐近误差率
4.5.1最近邻法二、最近邻法的错误率分析

4.5.1最近邻法二、最近邻法的错误率分析

可以证明以下关系式成立
c P* P P * (2 P*) c 1

其中P*为贝叶斯错误率，c为类数。
上式实际上给出了最近邻法渐近平均错误率P的范围，指出它在Bayes错误率P* c 和 P * (2 P*) 之间。 c 1

4.5.1最近邻法二、最近邻法的错误率分析
c i 1
知样本x，只要比较x与 N N i 个已知类别的样本之间的欧氏距离，并决策x与离它最近的样本同类。
4.5.1最近邻法
二、最近邻法的错误率分析

近邻法的错误率很难计算，因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。如图中所示
4.5.1最近邻法二、最近邻法的错误率分析
P* P * (e | x) p(x)dx [1 P(m | x)] p(x)dx 0
此时P = P*。
4.5.1最近邻法二、最近邻法的错误率分析

KNN方法附PPT教案学习

输入：训练数据X；近邻数目K；待分类的元组t。
输出：输出类别c。
（1）N=；
（2）FOR each d ∈X DO BEGIN
（3） IF |N|<K THEN
（4） N=N ∪{d}；
（5） ELSE
（6） IF u ∈N such that sim(t，u)<sim(t，d) THEN BEGIN
（7）
N=N - {u}；
（8）
N=N ∪{d}；
（9） END
（10）END
（11）c=class to which the most u ∈N.
第12页/共27页
序
号姓名
1 Kristina
2
Jim
KNN的例子（1）
性别女男
身高 1.6
2
类别矮高
“高度”用于计算距离，K=5，对<Pat，女， 1.6>分类。
在实际的计算中往往用距离来表征，距离越近，相似性越大，距离越远，相似性越小。
距离的计算方法有多种，最常用的是通过计算每个类的中心来完成。
第9页/共27页
基于距离的分类算法的一般性描述
算法基于距离的分类算法
输入：每个类的中心C1，…，Cm；待分类的元组x。输出：输出类别c。
（1）dist=∞；//距离初始化
起初公司管理人员认为司机每天行驶的时间与每天运送货物行驶的里程密切相关通过观察散点图管理人员假设能利用一元线性回归模型来描述行驶的小时数y与行驶的英里数x之间的关对公司的实际数据采用普通最小二乘法估计出回归方程为通过对方程的分析公司的管理人员发现虽然这一结果不错但方程只能解释每天行驶时间的变异性的664
•对T前K=5个记录，N={<Kristina，女， 1.6>、< Jim，男，2>、< Maggie，女， 1.9>、< Martha，女，1.88>和< Stephanie，女，1.7>}。 •对第6个记录d=< Bob，男，1.85>，得到 N={<Kristina，女， 1.6>、< Bob，男， 1.85>、< Maggie，女，1.9>、< Martha，女，1.88>和< Stephanie，女， 1.7>}。 •对第7个记录d=< Kathy，女，1.6>，得到N={<Kristina，女， 1.6>、< Bob，男， 1.85>、< Kathy，女，1.6>、< Martha，女，1.88>和< Stephanie，女，1.7>}。

第3章 k-近邻算法 (《统计学习方法》PPT课件)

• sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
• return sortedClassCount[0][0]
Shape函数
• group,labels=kNN.createDataSet()
Python导入数据
• from numpy import * • >>> import operator • >>> def createDataSet(): • group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]]) • labels=['A','A','B','B'] • return group,lables
• 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。
• 一般来说，只选择样本数据集中前N个最相似的数据。K一般不大于20，最后，选择k个中出现次数最多的分类，作为新数据的分类
K近邻算法的一般流程
• 收集数据：可以使用任何方法 • 准备数据：距离计算所需要的数值，最后是结构化的数据格式。 • 分析数据：可以使用任何方法 • 训练算法：（此步骤kNN）中不适用 • 测试算法：计算错误率 • 使用算法：首先需要输入样本数据和结构化的输出结果，然后运
• fr = open(filename)
• numberOfLines = len(fr.readlines()) #get the number of lines in the file

第12章 K最近邻分类

• 然后将距离从小到大排序，取出前k个值，这里我们假设k=5。也就是说我们取得离观测值最近的5个点，如图12.8所示
• 然后在这5个值里数一下各个类别的个数，个数最多的类别，就是该观测值的类别。比如在这个类别中三角形有3个，圆形有2个，三角形的个数大于圆形的个数，所以该观测值会被判定为三角形。
12.1.2 权重
• 权重是指某一个因素相对于整个事物的重要程度，它既体现了各个因素所占的百分比，同时也强调了因素的相对重要程度，贡献度和重要程度。
• 比如在大学里，我们的成绩评分是分为平时成绩和考试成绩，在我们学校，平时成绩占最后总成绩的30%，而考试成绩则占了70%。也就是说，如果我的平时成绩90分，考试成绩90分的话，我的总成绩是分。
• 由此可知，不同的k的选取，会对最后的结果造成很大的影响，那么应该如何确定k值呢？
• k值的确定可以通过设置不同的k值，然后比较不同k值对应的最后的分类的正确率来确定。
图12.11 当k=7时的结果
12.2.3 距离加权最近邻算法
• k值的选择会对结果造成不同的影响，想象一个特例，当我们去k=2时，正好周围有一个圆形和一个三角形，此时我们应该怎样对这个点进行分类呢？如图12.12所示，现在有一点[4.9,5],当k=2时,周围一个圆形,一个三角形。此图12.12 点[4.9,5],当k=2时, 时如果没有设置正确的程序，周围一个圆形,一个三角形则会出现异常的结果，因为圆形和三角形的个数相同，并没有最多的存在。
图12.3 坐标系中分布着若干个点
• 现在给出一个点[2,5]，我们很好判别这点应该属于三角形的类别，因为它的周围全部都是三角形，如图12.4所示。
• 同样的道理，给出线[8,5]，我们也很容易判别这一点应该属于圆形的类别，如图12.5所示。

K-近邻算法PPT课件

.
19
示例：使用k-近邻算法
改进约会网站的配对结果
1.问题描述：我都朋友佩琪一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但是她并不是喜欢每一个人。经过一番总结，她发现曾交往过三种类型的人：
不喜欢的人魅力一般的人极具魅力的人
.
20
示例：使用k-近邻算法
改进约会网站的配对结果
(3)分析数据：可以使用任何方法。 (4)测试算法：计算错误率。 (5)使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据属于哪个分类，最后应用对计算出的分类执行后续的处理。
.
10
准备：使用Python导入数据
1.创建名为kNN.py的Python模块
注：接下来所有的代码均保存于这个文件夹中，读者可以按照自己的习惯在自己创建的文件夹中编写代码，也可以去网上查找源代码，但笔者建议读者按照本PPT的顺序去创建模块并编写代码。
.
15
实施kNN分类算法
(2)以下为kNN近邻算法代码，将其保存于kNN.py中 def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0] diffMat = tile(inX, (dataSetSize,1)) - dataSet sqDiffMat = diffMat**2 sqDistances = sqDiffMat.sum(axis = 1) distances = sqDistances**0.5 sortedDistIndicies = distances.argsort() classCount = {} for i in range(k):

K最近邻方法

12
基于距离的分类方法
A
B
C
训练集（分3类）
9个未分类数据
将9个数据分类
13
基于距离的分类方法
输入： C1,C2,…Cm //样本有m个类 t //未知样本输出 C //t 属于的类基于距离的算法 Dist=∞ For i：=1 to m do if dis（Ci，t）＜dist, then C= Ci dist=dis（Ci，t)
2
简单概念
3. K-近邻就是找出k个相似的实例来建立目标函数逼近。这种方法为局部逼近。复杂度低，不失为一个方法。
3
简单概念--相似
4. 相似实例：什么是相似？对于距离的计算方法有许多。样本为 X=(x1,x2,…xn)
明考斯基距离: d (i, j ) q (| x x |q | x x |q ... | x x |q )
25
贝叶斯公式 P(H | X) P(X | H)P(H) 给出了这些关系
P(X)
在给定的数据集情况下：
P(H)：通过数据可以计算出来，一般为一常数。
P(X): 通过数据可以计算出来，一般为常数。
P(X|H):通过数据可以计算出来
P(H|X):由上述公式可计算出来。
26
朴素贝叶斯分类
1.
每个样本 X 由n维向量表示 X={ x1,x2,……xn }, 它代表n个属性A1, A2,…… An 一点取值, 如属性是相互独立,我们称其为朴素贝叶斯，说明它的属性间无关系,属性只与类有关。一个的属性取值与其它属性取值无关。 C
K-NN算法例子2
5.d={(5,0)}, dt=sqr(5),N={(2,1),(2,3),(3,1), (5,0)}, d1=sqr(5),d2=sqr(5),d3=sqr(2),d4=sqr(5). 6.d={(5,-1)}, dt=sqr(10),N={(2,1),(2,3),(3,1), (5,0)}, d1=sqr(5),d2=sqr(5),d3=sqr(2),d4=sqr(5). 7.d={(6,1)}, dt=sqr(5),N={(2,3),(3,1), (5,0), (6,1)}, d1=sqr(5),d2=sqr(2),d3=sqr(5),d4=sqr(5).

模式识别课件(第六章 NO1)(最近邻法)

二. 剪辑近邻法
此类方法的基本思想是：剪掉(清理)两类间的边界，取掉类别混杂的样本，使两类边界更清晰。
1. 两分剪辑近邻法(亦称剪辑最近邻法) 基本过程为：设N个样本分成c类
æ
N
N , N ,……, = { æ1 æ2 æcN }
1
2
c
(N1+N2+……,+Nc= N)
N
step1：剪辑。利用已知样本集æ 中的样本进行预分类，并剪辑掉被错分类的样本，留下的样本构成 NE æ 剪辑样本集 step2：分类。利用 æ
6.3 近邻法的改进算法
共同特点是如何尽快地找出最近邻可能存在的小的空间，减少搜索的范围，从而达到减少近邻法中的计算量和存储量的问题。一. 快速近邻算法该算法对最近邻法和k-近邻法都适用。下面以最近邻法为例来讨论。 1. 基本思想将全部已知样本按级分成一些不相交的子集，并在子集的基础上进行搜索。也就是说，该算法由两个阶段组成：第一阶段：将样本集按级分解，形成树状结构。
二. 最近邻法的决策规则设有c类模式样本， ω1, ω2,……, ωc 每类有Ni个样本(i=1,2,……,c)，则最近邻法的(ωi类)判别函数为:
gi ( X ) min X X ik
k
(k 1,2,...... , Ni )
式中X ik 表示ωi类中的第k个样本。
对应的决策规则为：如果则决策
X i 。
具体就是：设k1,k2,......,kc分别为X的k个最近邻样本中属于
1 , 2 ,......, c
类的样本数，
则定义 i (i 1,2,......,c) 类的判别函数为：
g i ( X ) ki

k近邻算法 ptt

k近邻算法K近邻算法（K-Nearest Neighbors，简称KNN）是一种基本的分类（或回归）算法，常用于模式识别和数据挖掘领域。

它的原理很简单，即通过查找与待分类样本最近的K个已知类别样本，在这K个样本中进行投票或平均来确定待分类样本的类别（或预测值）。

在使用KNN算法进行分类时，常见的步骤如下：1. 准备数据集：首先，需要准备一个已知类别的数据集，其中包含特征（属性）和类别标签。

通常将数据集划分为训练集和测试集，用于训练模型和评估性能。

2. 计算距离：针对待分类样本，需要计算其与训练集中每个已知样本之间的距离。

常见的距离度量方法包括欧氏距离、曼哈顿距离等。

3. 选择K值：选择合适的K值，即在K个最近邻中进行投票判断的邻居数量。

K值的选择会影响KNN算法的性能，通常通过交叉验证或其他评估方法来确定。

4. 确定类别：根据K个最近邻的类别（或平均值），来确定待分类样本的类别。

对于分类问题，一般选择多数投票的类别作为预测结果；对于回归问题，一般选择平均值作为预测结果。

需要注意的是，KNN算法对于特征的选择和预处理非常重要。

对于连续特征，可能需要进行归一化或标准化处理，以避免某些特征对距离计算产生过大的影响。

在PTT中，由于是一个网络社区平台，KNN算法可以应用于多个场景，如用户推荐、文本分类、情感分析等。

通过收集用户的行为数据或文本数据，构建相应的特征和类别标签，然后使用KNN算法进行分类或回归预测。

总之，KNN算法是一种简单而常用的分类算法，通过计算待分类样本与已知样本之间的距离，利用最近的K个邻居进行分类或回归预测。

在PTT等领域中，可以应用于各种数据分析和模式识别任务。

最近邻法和k-近邻法

最近邻法和k-近邻法一.基本概念：最近邻法：对于未知样本x，比较x与N个已知类别的样本之间的欧式距离，并决策x 与距离它最近的样本同类。

K近邻法：取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。

K取奇数，为了是避免k1=k2的情况。

二.问题分析：要判别x属于哪一类，关键要求得与x最近的k个样本（当k=1时，即是最近邻法），然后判别这k个样本的多数属于哪一类。

可采用欧式距离公式求得两个样本间的距离s=sqrt（（x1-x2）^2+(y1-y2)^2）三.算法分析：该算法中任取每类样本的一半作为训练样本，其余作为测试样本。

例如iris中取每类样本的25组作为训练样本，剩余25组作为测试样本，依次求得与一测试样本x距离最近的k 个样本，并判断k个样本多数属于哪一类，则x就属于哪类。

测试10次，取10次分类正确率的平均值来检验算法的性能。

四.MATLAB代码：最近邻算实现对Iris分类clc;totalsum=0;for ii=1:10data=load('iris.txt');data1=data(1:50,1:4);%任取Iris-setosa数据的25组rbow1=randperm(50);trainsample1=data1(rbow1(:,1:25),1:4);rbow1(:,26:50)=sort(rbow1(:,26:50));%剩余的25组按行下标大小顺序排列testsample1=data1(rbow1(:,26:50),1:4);data2=data(51:100,1:4);%任取Iris-versicolor数据的25组 rbow2=randperm(50); trainsample2=data2(rbow2(:,1:25),1:4);rbow2(:,26:50)=sort(rbow2(:,26:50));testsample2=data2(rbow2(:,26:50),1:4);data3=data(101:150,1:4);%任取Iris-virginica数据的25组rbow3=randperm(50);trainsample3=data3(rbow3(:,1:25),1:4);rbow3(:,26:50)=sort(rbow3(:,26:50));testsample3=data3(rbow3(:,26:50),1:4);trainsample=cat(1,trainsample1,trainsample2,trainsample3);%包含75组数据的样本集testsample=cat(1,testsample1,testsample2,testsample3);newchar=zeros(1,75);sum=0;[i,j]=size(trainsample);%i=60,j=4[u,v]=size(testsample);%u=90,v=4for x=1:ufor y=1:iresult=sqrt((testsample(x,1)-trainsample(y,1))^2+(testsample(x,2)-trainsample(y,2))^2+(testsampl e(x,3)-trainsample(y,3))^2+(testsample(x,4)-trainsample(y,4))^2); %欧式距离newchar(1,y)=result;end;[new,Ind]=sort(newchar);class1=0;class2=0;class3=0;if Ind(1,1)<=25class1=class1+1;elseif Ind(1,1)>25&&Ind(1,1)<=50class2=class2+1;elseclass3=class3+1;endif class1>class2&&class1>class3m=1;ty='Iris-setosa';elseif class2>class1&&class2>class3m=2;ty='Iris-versicolor';elseif class3>class1&&class3>class2m=3;ty='Iris-virginica';elsem=0;ty='none';endif x<=25&&m>0disp(sprintf('第%d组数据分类后为%s类',rbow1(:,x+25),ty));elseif x<=25&&m==0disp(sprintf('第%d组数据分类后为%s类',rbow1(:,x+25),'none'));endif x>25&&x<=50&&m>0disp(sprintf('第%d组数据分类后为%s类',50+rbow2(:,x),ty));elseif x>25&&x<=50&&m==0disp(sprintf('第%d组数据分类后为%s类',50+rbow2(:,x),'none'));endif x>50&&x<=75&&m>0disp(sprintf('第%d组数据分类后为%s类',100+rbow3(:,x-25),ty));elseif x>50&&x<=75&&m==0disp(sprintf('第%d组数据分类后为%s类',100+rbow3(:,x-25),'none'));endif (x<=25&&m==1)||(x>25&&x<=50&&m==2)||(x>50&&x<=75&&m==3)sum=sum+1;endenddisp(sprintf('第%d次分类识别率为%4.2f',ii,sum/75)); totalsum=totalsum+(sum/75);enddisp(sprintf('10次分类平均识别率为%4.2f',totalsum/10));测试结果：第3组数据分类后为Iris-setosa类第5组数据分类后为Iris-setosa类第6组数据分类后为Iris-setosa类第7组数据分类后为Iris-setosa类第10组数据分类后为Iris-setosa类第11组数据分类后为Iris-setosa类第12组数据分类后为Iris-setosa类第14组数据分类后为Iris-setosa类第16组数据分类后为Iris-setosa类第18组数据分类后为Iris-setosa类第19组数据分类后为Iris-setosa类第20组数据分类后为Iris-setosa类第23组数据分类后为Iris-setosa类第24组数据分类后为Iris-setosa类第26组数据分类后为Iris-setosa类第28组数据分类后为Iris-setosa类第30组数据分类后为Iris-setosa类第31组数据分类后为Iris-setosa类第34组数据分类后为Iris-setosa类第37组数据分类后为Iris-setosa类第39组数据分类后为Iris-setosa类第41组数据分类后为Iris-setosa类第44组数据分类后为Iris-setosa类第45组数据分类后为Iris-setosa类第49组数据分类后为Iris-setosa类第51组数据分类后为Iris-versicolor类第53组数据分类后为Iris-versicolor类第54组数据分类后为Iris-versicolor类第55组数据分类后为Iris-versicolor类第57组数据分类后为Iris-versicolor类第58组数据分类后为Iris-versicolor类第59组数据分类后为Iris-versicolor类第60组数据分类后为Iris-versicolor类第61组数据分类后为Iris-versicolor类第62组数据分类后为Iris-versicolor类第68组数据分类后为Iris-versicolor类第70组数据分类后为Iris-versicolor类第71组数据分类后为Iris-virginica类第74组数据分类后为Iris-versicolor类第75组数据分类后为Iris-versicolor类第77组数据分类后为Iris-versicolor类第79组数据分类后为Iris-versicolor类第80组数据分类后为Iris-versicolor类第84组数据分类后为Iris-virginica类第85组数据分类后为Iris-versicolor类第92组数据分类后为Iris-versicolor类第95组数据分类后为Iris-versicolor类第97组数据分类后为Iris-versicolor类第98组数据分类后为Iris-versicolor类第99组数据分类后为Iris-versicolor类第102组数据分类后为Iris-virginica类第103组数据分类后为Iris-virginica类第105组数据分类后为Iris-virginica类第106组数据分类后为Iris-virginica类第107组数据分类后为Iris-versicolor类第108组数据分类后为Iris-virginica类第114组数据分类后为Iris-virginica类第118组数据分类后为Iris-virginica类第119组数据分类后为Iris-virginica类第124组数据分类后为Iris-virginica类第125组数据分类后为Iris-virginica类第126组数据分类后为Iris-virginica类第127组数据分类后为Iris-virginica类第128组数据分类后为Iris-virginica类第129组数据分类后为Iris-virginica类第130组数据分类后为Iris-virginica类第133组数据分类后为Iris-virginica类第135组数据分类后为Iris-virginica类第137组数据分类后为Iris-virginica类第138组数据分类后为Iris-virginica类第142组数据分类后为Iris-virginica类第144组数据分类后为Iris-virginica类第148组数据分类后为Iris-virginica类第149组数据分类后为Iris-virginica类第150组数据分类后为Iris-virginica类k近邻法对wine分类：clc;otalsum=0;for ii=1:10 %循环测试10次data=load('wine.txt');%导入wine数据data1=data(1:59,1:13);%任取第一类数据的30组rbow1=randperm(59);trainsample1=data1(sort(rbow1(:,1:30)),1:13);rbow1(:,31:59)=sort(rbow1(:,31:59)); %剩余的29组按行下标大小顺序排列testsample1=data1(rbow1(:,31:59),1:13);data2=data(60:130,1:13);%任取第二类数据的35组rbow2=randperm(71);trainsample2=data2(sort(rbow2(:,1:35)),1:13);rbow2(:,36:71)=sort(rbow2(:,36:71));testsample2=data2(rbow2(:,36:71),1:13);data3=data(131:178,1:13);%任取第三类数据的24组rbow3=randperm(48);trainsample3=data3(sort(rbow3(:,1:24)),1:13);rbow3(:,25:48)=sort(rbow3(:,25:48));testsample3=data3(rbow3(:,25:48),1:13);train_sample=cat(1,trainsample1,trainsample2,trainsample3);%包含89组数据的样本集test_sample=cat(1,testsample1,testsample2,testsample3); k=19;%19近邻法newchar=zeros(1,89);sum=0;[i,j]=size(train_sample);%i=89,j=13[u,v]=size(test_sample);%u=89,v=13for x=1:ufor y=1:iresult=sqrt((test_sample(x,1)-train_sample(y,1))^2+(test_sample(x,2)-train_sample(y,2))^2+(test_ sample(x,3)-train_sample(y,3))^2+(test_sample(x,4)-train_sample(y,4))^2+(test_sample(x,5)-train _sample(y,5))^2+(test_sample(x,6)-train_sample(y,6))^2+(test_sample(x,7)-train_sample(y,7))^2+ (test_sample(x,8)-train_sample(y,8))^2+(test_sample(x,9)-train_sample(y,9))^2+(test_sample(x,10)-train_sample(y,10))^2+(test_sample(x,11)-train_sample(y,11))^2+(test_sample(x,12)-train_sa mple(y,12))^2+(test_sample(x,13)-train_sample(y,13))^2); %欧式距离newchar(1,y)=result;end;[new,Ind]=sort(newchar); class1=0; class 2=0; class 3=0;for n=1:kif Ind(1,n)<=30class 1= class 1+1;elseif Ind(1,n)>30&&Ind(1,n)<=65class 2= class 2+1;elseclass 3= class3+1;endendif class 1>= class 2&& class1>= class3m=1;elseif class2>= class1&& class2>= class3m=2;elseif class3>= class1&& class3>= class2m=3;endif x<=29disp(sprintf('第%d组数据分类后为第%d类',rbow1(:,30+x),m));elseif x>29&&x<=65disp(sprintf('第%d组数据分类后为第%d类',59+rbow2(:,x+6),m));elseif x>65&&x<=89disp(sprintf('第%d组数据分类后为第%d类',130+rbow3(:,x-41),m));endif (x<=29&&m==1)||(x>29&&x<=65&&m==2)||(x>65&&x<=89&&m==3)sum=sum+1;endenddisp(sprintf('第%d次分类识别率为%4.2f',ii,sum/89));totalsum=totalsum+(sum/89);enddisp(sprintf('10次分类平均识别率为%4.2f',totalsum/10));第2组数据分类后为第1类第4组数据分类后为第1类第5组数据分类后为第3类第6组数据分类后为第1类第8组数据分类后为第1类第10组数据分类后为第1类第11组数据分类后为第1类第14组数据分类后为第1类第19组数据分类后为第1类第20组数据分类后为第3类第21组数据分类后为第3类第22组数据分类后为第3类第26组数据分类后为第3类第27组数据分类后为第1类第28组数据分类后为第1类第30组数据分类后为第1类第33组数据分类后为第1类第36组数据分类后为第1类第37组数据分类后为第1类第43组数据分类后为第1类第44组数据分类后为第3类第45组数据分类后为第1类第46组数据分类后为第1类第49组数据分类后为第1类第52组数据分类后为第1类第54组数据分类后为第1类第56组数据分类后为第1类第57组数据分类后为第1类第60组数据分类后为第2类第61组数据分类后为第3类第63组数据分类后为第3类第65组数据分类后为第2类第66组数据分类后为第3类第67组数据分类后为第2类第71组数据分类后为第1类第72组数据分类后为第2类第74组数据分类后为第1类第76组数据分类后为第2类第77组数据分类后为第2类第79组数据分类后为第3类第81组数据分类后为第2类第82组数据分类后为第3类第83组数据分类后为第3类第84组数据分类后为第2类第86组数据分类后为第2类第87组数据分类后为第2类第88组数据分类后为第2类第93组数据分类后为第2类第96组数据分类后为第1类第98组数据分类后为第2类第99组数据分类后为第3类第104组数据分类后为第2类第105组数据分类后为第3类第106组数据分类后为第2类第110组数据分类后为第3类第113组数据分类后为第3类第114组数据分类后为第2类第115组数据分类后为第2类第116组数据分类后为第2类第118组数据分类后为第2类第122组数据分类后为第2类第123组数据分类后为第2类第124组数据分类后为第2类第133组数据分类后为第3类第134组数据分类后为第3类第135组数据分类后为第2类第136组数据分类后为第3类第139组数据分类后为第3类第140组数据分类后为第3类第142组数据分类后为第3类第144组数据分类后为第2类第145组数据分类后为第1类第146组数据分类后为第3类第148组数据分类后为第3类第149组数据分类后为第2类第152组数据分类后为第2类第157组数据分类后为第2类第159组数据分类后为第3类第161组数据分类后为第2类第162组数据分类后为第3类第163组数据分类后为第3类第164组数据分类后为第3类第165组数据分类后为第3类第167组数据分类后为第3类第168组数据分类后为第3类第173组数据分类后为第3类第174组数据分类后为第3类五：问题和收获：该算法的优缺点总结为：优点：算法简单且识别率较高；缺点：算法需要计算未知样本x与周围每个样本的距离，然后排序选择最近的k个近邻，计算量和时间复杂度高。

大数据十大经典算法kNN讲解ppt课件

8
KNN算法是用来干什么的
K-最近邻算法是最近邻算法的一个延伸。基本思路是：选择未知样本一定范围内确定个数的K个样本，该K个样本大多数属于某一类型，则未知样本判定为该类型。
下面借助图形解释一下。
9
KNN算法的实现步骤
算法步骤： step.1---初始化距离为最大值 step.2---计算未知样本和每个训练样本的距离dist step.3---得到目前K个最临近样本中的最大距离maxdist step.4---如果dist小于maxdist，则将该训练样本作为K-最近
3.重复2步骤，直至遍历完original样本集中的所有样本，output样本集即为压缩后的样本集。
通过这种方式也能减少算法的计算量，但仍然无法减少存储量。
15
邻样本 step.5---重复步骤2、3、4，直到未知样本和所有训练样本的
距离都算完 step.6---统计K个最近邻样本中每个类别出现的次数 step.7---选择出现频率最大的类别作为未知样本的类别
10
KNN算法的缺陷
观察下面的例子，我们看到，对于位置样本 X，通过KNN算法，我们显然可以得到X应属于红点，但对于位置样本Y，通过KNN算法我们似乎得到了Y 应属于蓝点的结论，而这个结论直观来看并没有说服力。
6
KNN算法是怎么来的问题：有一个未知形状X(图中绿色的圆点)，如何判断X是什么形状?
7
K-最近邻算法
显然，通过上面的例子我们可以明显发现最近邻算法的缺陷——对噪声数据过于敏感，为了解决这个问题，我们可以可以把位置样本周边的多个最近样本计算在内，扩大参与决策的样本量，以避免个别数据直接决定决策结果。由此，我们引进K-最近邻算法。
11

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

t={(4,2)},K=4
1.
N={(1,0),(1,2),(1,4),(2,1)},
d1=sqr(13),d2=3,d3=sqr(13),d4=sqr(5)
2.d={(2,3)},dt=sqr(5),N={(1,2),(1,4),(2,1),(2,3)},
d1=3,d2=sqr(13),d3=sqr(5),d4=sqr(5)
3.d={20},比较,N={10,12,3,20},d1=8,d2=6,d3=15,d4=2
4.d={22},比较,N={12,3,20,22},d1=6,d2=15,d3=2,d4=4
5.d={21},比较,N={3,20,22,21},d1=15,d2=2,d3=4,d4=3
6.d={11},比
11
基于距离的分类方法
数据样本都是用n维数值属性描述的向量。
X=(x1,x2，……xn)
每个样本代表n维空间的一个点。这样所有的训练样本都存放在n维模式空间中。我们根据样本的m个类别，将同类样本计算出类中心：
Cj=(cj1,cj2, …… cjn)；j=1,2,…m
输入一个未知类别样本： Y=(y1,y2, …… yn)
8
K- 近邻分类方法也可作为预测方法
样本的输出不是类别，而为实数值，未知样本返回的是k个近邻者的实数值平均值。
9
K-近邻方法的优缺点
优点：
（1）易于编程，且不需要优化和训练（2）当样本增大到一定容量，k也增大到合适的程度，k-近
邻的误差可与贝叶斯方法相比。缺点：（1）在高维和数据质量较差时，k-近邻方法表现不好。（2）当n个训练样本，n大时，计算时间太大。
如计算一个点要p次操作，每次查询都要np次计算，时间复杂度为O(np)。往往用户难以接受。
K-近邻方法对k的选择也是要靠经验，也取决于要处理的问题与背景。
10
基于距离的分类方法
近邻的含义？用什么方法来判断近邻也因问题不同而不同。
距离的计算? 用什么方法来判断距离，距离怎样计算，这些都是因问题而异。
if u∈N such that sim(t, u) ≤sim(t, d),
then
begin
N=N-{u};//去掉与 t 距离大的u;
N=N∪{d};//加进与 t 距离小的d；
end
//发现分类的类别
c=class to which the most u∈N are classified;//N中的最多的类 c 赋给 t
K最近邻方法
简单概念
K- 近邻分类方法特点 1. 不是事先通过数据来学好分类模型, 再对未知
样本分类，而存储带有标记的样本集，给一个没有标记的样本，用样本集中k个与之相近的样本对其进行即时分类。由于没有事先学习出模型，所以把它称作基于要求或懒惰的学习方法。 2. 这是一种基于示例的学习方法，一种基于类比的学习方法
曼哈坦距离: d ( i , j ) | x i 1 x j 1 | | x i 2 x j 2 | . | . x i p . x j p |
欧氏距离： d ( i ,j ) (x i 1 | x j 1 |2 |x i 2 x j 2 |2 . . |x i . p x j p |2 )
if dis（Ci，t）＜dist, then
C= Ci
dist=dis（Ci，t)
14
K-NN算法例子
给样本数据集T={2,4,10,12,3,20,22,21,11,24}
t={18},K=4
1.
N={2,4,10,12},d1=16,d2=14,d3=8,d4=6
2.d={3},比较,N={4,10,12,3},d1=14,d2=8,d3=6,d4=15
距离近就相似 4
K-近邻基本思路
1. 存储一些标记好的样本集（样本都分好了类）
2. 一个未知类的样本（要对其分类） 3. 逐一取出样本集中的样本，与未知类样
本比较，找到K-个与之相近的样本，就用这K-个样本的多数的类（或类分布）为未知样本定类。 4. 在样本集为连续值时，就用K-个样本的平均值为未知样本定值。
较,N={20,22,21,11},d1=2,d2=4,d3=3,d4=7
15
基于距离的K-NN分类方法例子
给样本数据集T={3,11,22}//类中心 t={18} 1. d1=15,d2=7,d3=4
16
K-NN算法例子2
给样本数据集:
T={(1,0),(1,2),(1,4),(2,1),(2,3),(3,1),(3,-3),(5,0), (5,1),(6,1)}
输出： c//元组t被分配的类别
算法://利用K-近邻（k-NN）算法对元组进行分类
7
N= ø;
//对于元组t发现的邻居集合
for each d∈T do if |N|≤K, then
从数据集T中不断取d 一直取出K个
N=N∪{d}; else
将t与数据集中都比一遍，留留下k个与之最小距离的元组
2
简单概念
3. K-近邻就是找出k个相似的实例来建立目标函数逼近。这种方法为局部逼近。复杂度低，不失为一个方法。
3
简单概念--相似
4. 相似实例：什么是相似？对于距离的计算方法有许多。
样本为 X=(x1,x2,…xn)
明考斯基距离: d ( i ,j) q (x i 1 | x j 1 |q |x i2 x j2 |q . .|x i .p x j p |q )
5
K-最近邻算法
样本：用 n 维数值属性表示每个样本为n维空间一个点 X=(x1,x2,……..xn) Y=(y1,y2,……..yn)
度量：点之间的距离（关系）表示
n
d(X,Y) (xiyi )2 i1 6
K-近邻算法
输入： T //训练数据( 带有类标记的样本） K //邻居的数目（给定k个近邻） t //将要被分类的元组
判断Y的类别，将Y与Cj进行距离计算，与那个类
距离小，就是那类。计算距离方法因问题而异。 12
基于距离的分类方法
A
B
C
训练集（分3类）
9个未分类数据
将9个数据分类
13
基于距离的分类方法
输入：
Hale Waihona Puke C1,C2,…Cm //样本有m个类
t
//未知样本
输出
C
//t 属于的类
基于距离的算法
Dist=∞
For i：=1 to m do