K近邻分类的算法实现文档格式.docx
《K近邻分类的算法实现文档格式.docx》由会员分享，可在线阅读，更多相关《K近邻分类的算法实现文档格式.docx（24页珍藏版）》请在冰点文库上搜索。
）,x/〔…,x,丫,不,可的Lp距离定义为
厶八兀•，有）=（£
#一尤
\/-I
这里卩才。
当P=2时，称为欧式距离，即
L2（xf-,xp=[^x/-x/
当"
=1时，称为曼哈顿距离，即”
Li（xp^.）=£
L/-x/
MI
当p=g时，它是各个距离坐标的最大值，即
Lx（xiyXj）=maxx--x'
j
2.1.3K值的选择
k值的选择会对k近邻法的结果产生重大影响。
如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的（相似的）训练实例才会对预测结果起作用。
但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敬感。
如果近邻的实例点恰巧是噪声，预测就会出错。
换句话说，k值得减小就意味着整体模型变得复杂，容易发生过拟合。
如果选择较大的k值，就相当于用较大邻域中的训练实例进行预测。
其优点是可以减少学习的估计误差。
但缺点是学习的近似误差会增大。
这时与输入实例较远的（不相似的）训练实例也会对预测起作用，是预测发生错误。
K值得增大就意味着整体的模型变得简单。
如果k二N,那么无论输入实例是什么，都将简单的预测它属于在训练实例中最多的类。
这时，模型过于简单，完全忽略训练实例中的大量有用信息，是不可取的。
2.1.4分类决策规则
K近邻法中的分类决策规则往往是多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
多数表决规则有如下解释：
如果分类的损失函数为0-1损失函数，分类函数为
f：
R"
->
{q,C2,…，C*}
那么误分类的概率是
p（r^/（x））=i-p（r=/（x））
对给定的实例Vez,其最近邻的k个训练实例点构成集合Nk（x）。
如果涵盖NZ的区域的类别是勺那么误分类概率是
T工心宀）=1—£
工心=勺）
〉:
/（y=c）
要使误分类概率最小即经验风险最小，就要使W、'
小）1;
最大，所以多数
表决规则等价于经验风险最小化。
2.2K近邻算法
输入：
训练数据集
丁=｛（州，）'
1），（吃，『2），—，（亦川）｝
其中，兀“匸川为实例的特征向量，川）=6心,…S为实例的类别，
i二1,2,…，N;
实例特征向量x；
输出：
实例x所属的类y。
（1）根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x邻域记作Nk（x）；
（2）在NkW中根据分类决策规则（如多数表决）决定x的类别y：
y=argmax工/（）〔.=1,2,N;
丿=12…，K
C,形自\：
（.丫）
该式中，I为指示函数，即当时I为1,否则I为0。
当k取1的特殊情况时，k近邻算法即为最近邻算法。
对于输入的实例点或
是特征向量X,其分类由其最邻近的点的分类决定。
第三章数据模拟和实例分析
3.1数据模拟
用MATLAB随机生成150组数据，类别为三类，编程如下#程序1：
Al=rand（5O,2）;
holdonplot（Al（:
l）,Al（:
2）,T）A2=rand（50,2）+0.75;
holdon
plot（A2（:
l）,A2（:
2）,T）holdon
A3=rand（50,2）+l.5;
plot（A3（:
l）,A3（:
2）,'
.'
）
得到如图所示图像
图1模拟数据在坐标系中的分布
再用k近邻分类算法对这150组数据进行分类，取k二15近邻，程序如下
#程序2：
clearall
clc
y=importdata（,C:
\Users\adm\Desktop\test.txt,）;
p=y（:
2:
3）;
P二P：
Add=zeros（150J）;
Add（l:
50,:
）=ones（50J）;
Add（51:
100,:
）=2*ones（50J）;
Add（101:
l50,:
）=3*ones（50J）;
figure（l）,plot（y（:
J）,Add；
g.'
）;
holdon
gridon;
count=0;
fori=l:
3
forj=1:
50
fork=l:
150
distance（k）=mse（p（:
k）-p（:
（i-1）*50+j））;
%保存每个向量与所有训练样本之间的距离
end
[dlindex1]=sort（distance）;
%对距离distance向量进行从小到大的排序num=[000];
form=l:
20%考察num,存放的是排序后distance前20个属于每一类别的个数
ifindexl（m）<
=50
num（l）=num（l）+l;
elseifindexl（m）<
=100
num
（2）=num
（2）+l;
else
num（3）=num（3）+l;
[d2class]=max（num）;
%属于哪类的个数最多,就属于哪类,class即就是该向量所属的类别
ifi==class
count=count+l;
A（（i-1）*50+j）=class;
%存放判断的结果
count
rate=count/150
figure
（2）,plot（y（:
J）,A；
r/）;
%画图分类
程序运行后得到
count=143rate=0.9533
图•模拟数据原始分类
2.8
2.6
2.4
2
1.8
1.6
1.4
1.2
05
010015
2.2
图2K近邻方法得到的分类
实验结果分析
从图像和运行结果均可以看出，对上述模拟数据用取k=15的k近邻算法作出的分类正确率为95.33%,分类效果不错，符合预期。
改变k值，分别取k=1,5,10,15,20,30,40,60做测试，发现k取1的取值对分类结果没有明显的规律，当k=l时，即为最近邻的特殊情况，此时分类和原分类吻合，当k从1开始逐渐增大时，分类效果呈现起伏，这说明k值得选取对分类结果有一定的影响，程序执行如下表。
K值
衣2Iris数据集分类效果
正确率
错误
1
5
96%
4%
10
94.67%
5.33%
15
95.33%
4.67%
20
96.67%
3.33%
30
40
60
3.2实例分析
本文选取了著名的Iris数据集，Iris数据集共150组，有四个特征，分别是花萼和花瓣的长度和宽度，类别也是三类，取k=20,对前•文程序代码稍作修改如下。
#程序3：
y=impoitdata（'
C:
\Users\adm\Desktop\test.txt'
5）;
p=p:
figure（l）,plot（y（:
J）,Add,'
forj=1:
150distance（k）=mse（p（:
k）-p（:
（i-l）*50+j））;
20%考察num,存放的是排序后distance前20
个属于每一类别的个数
elseifindex1（m）<
%属于哪类的个数最多，就属于哪类»
class即就是该向量所属的类别
l）,A,TJ）；
gridon;
程序执行后得到以下结果：
count=147rate=0.9800
图3原始数据的分类图像
图4K近邻分类算法所得到的分类图像
上述程序运行后的结果表明k取20时对Iris数据集具有较好的分类效果，从某种意义上说，k近邻算法对花的分类可以给出一定的借鉴意义。
改变k值后，分别取k=4,6,8,10,12,14,16,18,20,22,24,30时，发现对于Iris数据集k取&
22之间的值最为合适，分类正确率稳定，当k小于8或是大于22时，分类效果下降。
执行程序得到的结果如下表。
衣2分类正确率
错误率
4
6
97.33%
2.67%
8
98%
2%
12
14
16
18
22
24
第四章结语
通过在MATLAB软件上编写和运行K近邻算法的过程中，我们了解到K近邻法是有监督的学习方法，在分类阶段，k是一个用户定义的常数。
一个没有类别标签的向量（查询或测试点）将被归类为最接近该点的k个样本点中最频繁使用的一类。
该算法的优点是精度高、对异常值不敏感、无数据输入假定。
然而该方法山于其计算量较大，对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点，在计算速度上有待改进，但也正因为如此它只是适用于一些样本容量比较大的类域的自动分类，而那些样本容量较小的类域釆用这种算法则容易产生误分。
k-近邻算法的另一个缺陷是它无法给出任何数据的基础结构信息，因此我们也无法知晓平均实例样本和典型实例样本具有什么特征。
附录
Iris数据集包含150个样本，都属于莺尾属下的三个亚属，分别是山莺尾、变色莺尾和维吉尼亚莺尾，有四个特征被用作样本的定量分析，它们第一列和第二列是花萼的长度和宽度，第二列是花瓣的长度和宽度。
花呼长
花萼宽
花瓣长
花瓣宽
类别
5.1
3.5
0.2
4.9
4.7
3.2
1.3
4.6
3.1
1.5
L
3.6
5.4
3.9
1.7
0.4
7
3.4
0.3
9
4.4
2.9
0.1
11
3.7
4.8
13
4.3
1.1
5.8
17
19
21
23
25
26
27
28
29
31
32
33
34
35
36
37
38
39
41
42
43
44
45
46
47
48
49
51
52
53
54
00
5.7
3.8
5・1
3.3
0.5
1.9
□
5.2
4.1
5.5
4.2
4.5
2.3
0.6
5.3
6.4
6.9
6.5
第14页
56
57
58
59
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
6.3
6.6
2.7
5.9
6・1
5.6
6.7
6.2
2.5
6.8
6.1
第15页
7.1
2.1
7.6
7.3
7.2
5.1
7.7
7.4
7.9
第16页
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
6.1
升级会员 