文档介绍：1
K- 近邻分类方法
简单概念
K-近邻基本思路
K-最近邻算法
K- 近邻分类方法也可作为预测方法
基于距离的分类方法
2
简单概念
K- 近邻分类方法特点
不是事先通过数据来学好分类模型, 再对未知样本分类,而存储带有标记的样本集,给一个没有标记的样本,用样本集中k个与之相近的样本对其进行即时分类。
由于没有事先学习出模型,所以把它称作基于要求或懒惰的学习方法。
这是一种基于示例的学习方法,一种基于类比的学习方法
3
简单概念
3. K-近邻就是找出k个相似的实例来建立目标函数逼近。这种方法为局部逼近。复杂度低,不失为一个方法。
4
简单概念--相似
4. 相似实例:什么是相似?
对于距离的计算方法有许多。
样本为 X=(x1,x2,…xn)
明考斯基距离:
曼哈坦距离:
欧氏距离:
距离近就相似
5
K-近邻基本思路
存储一些标记好的样本集(样本都分好了类)
一个未知类的样本(要对其分类)
逐一取出样本集中的样本,与未知类样本比较,找到K-个与之相近的样本,就用这K-个样本的多数的类(或类分布)为未知样本定类。
在样本集为连续值时,就用K-个样本的平均值为未知样本定值。
6
K-最近邻算法
样本:用 n 维数值属性表示
每个样本为n维空间一个点
X=(x1,x2,……..xn)
Y=(y1,y2,……..yn)
度量:点之间的距离(关系)表示
7
K-近邻算法
输入:
T //训练数据( 带有类标记的样本)
K //邻居的数目(给定k个近邻)
t //将要被分类的元组
输出:
c//元组t被分配的类别
算法://利用K-近邻(k-NN)算法对元组进行分类
8
N= ø; //对于元组t发现的邻居集合
for each d∈T do
if |N|≤K, then
N=N∪{d};
else
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
从数据集T中不断取d
一直取出K个
将t与数据集中都比一遍,留
留下k个与之最小距离的元组
9
K- 近邻分类方法也可作为预测方法
样本的输出不是类别,而为实数值,未知
样本返回的是k个近邻者的实数值平均值。
10
K-近邻方法的优缺点
优点:
(1)易于编程,且不需要优化和训练
(2)当样本增大到一定容量,k也增大到合适的程度,k-近邻的误差可与贝叶斯方法相比。
缺点:
(1)在高维和数据质量较差时,k-近邻方法表现不好。
(2)当n个训练样本,n大时,计算时间太大。
如计算一个点要p次操作,每次查询都要np次计算,时间复杂度为O(np)。往往用户难以接受。
K-近邻方法对k的选择也是要靠经验,也取决于要处理的问题与背景。