文档介绍：数据挖掘方法六 K-Nearest Neighbor K最近邻分类
原理
K最近邻(k-Nearest Neighbor,KNN)算法,是一个理论上比较成熟的分类方法。
该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
KNN算法的指导思想是“近朱者赤,近墨者黑”,由你的邻居来推断出你的类别。
计算步骤如下:
1)算距离:给定测试对象,计算它与训练集中的每个对象的距离
2)找邻居:圈定距离最近的k个训练对象,作为测试对象的近邻
3)做分类:根据这k个近邻归属的主要类别,来对测试对象分类
距离衡量常用的是欧式距离(Euclidean distance):二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离为
d = sqrt((x1-x2)^2+(y1-y2)^2)
KNN的算法过程是是这样的:
从右图中我们可以看到,图中的数据集是良好的数据,即都打好了label,一类是蓝色的正方形,一类是红色的三角形,那个绿色的圆形是我们待分类的数据。
如果K=3,那么离绿色点最近的有2个红色三角形和1个蓝色的正方形,这3个点投票,于是绿色的这个待分类点属于红色的三角形。
如果K=5,那么离绿色点最近的有2个红色三角形和3个蓝色的正方形,这5个点投票,于是绿色的这个待分类点属于蓝色的正方形。
我们可以看到,KNN本质是基于一种数据统计的方法
举例一
表中显示了6部已知电影中出现的打斗镜头次数及接吻镜头次数,及电影所属的类型。下面将计算每部已知电影与未知电影的距离(本例中采用欧式距离)
我们得到了样本集中所有电影与未知电影的距离,按照距离递增排序,可以找到k个距离最近的电影。假定k=3,三个最靠近的电影依次是He's Not Really into Dudes、Beautiful Woman、California Man。从K-近邻算法按照距离最近的三部电影的类型,决定未知电影的类型,而这三部电影全是爱情片,因此我们判定未知电影是爱情片。
sqrt[(18-3)^2+(90-104)^2]=
sqrt(421)=
举例二:iris鸢尾花
150朵花的属性
4个定量变量:
1个定性变量:Species花的种类,[山鸢尾(setosa) 蓝旗鸢尾(versicolor) 维珍尼亚鸢尾(virginica)]
本例中用4个定量变量把150朵花分为3类,定性变量为分类。
(123)
> training=sample(1:150,145)
> test=(1:150)[-training]
> test
Species
88 versicolor
103 virginica
104 virginica
106 virginica
123 virginica