算法要点：

knn（k-nearst neighbor）

1：k：=最近邻点数，D：=training set of data

2：for (待测点z)

3：计算z和每个样例（x，y）的距离

4：选择离z最近的k个训练样例的集合

5：统计第4步得到的点哪一类多，则z就属于哪一类

6：end for

数据：

libraryI(ISLR)

names(Smarket )#R自带数据

knn代码：

attach(Smarket)

train=(Year<2005)                                                   #分离出2005之前的数据

train.X=cbind(Lag1,Lag2)[train,]                           #把2005年之前的数据中Lag1，Lag2组成矩阵，作为训练数据

test.X=cbind(Lag1,Lag2)[!train,]                           #把2005年之后的数据中Lag1，Lag2组成矩阵，作为测试数据

train.Direction=Direction[train]                              #训练数据的类标号

Direction.2005=Direction[!train]

set.seed(1)                                                               #set.seed(k)结果可以重现k次

knn.pred=knn(train.X,test.X,train.Direction,k=3)

table(knn.pred,Direction.2005)                            #confusion matrix

mean(knn.pred==Direction.2005)                       #accurate rate

实验结果

        Direction.2005
knn.pred Down Up
    Down   48 55
    Up     63 86
> mean(knn.pred==Direction.2005)
[1] 0.531746
算法分析：

优点：（i）基于实例的学习，不需要建立模型，不必维护源自数据的抽象（模型）；（ii）可以生成任意形状的决策边界，而决策树和基于规则的分类器只局限于直线决策边界（高维时是超平面）

缺点：（i）分类测试样例时，开销很大，为O(n)，n为training set个数；（ii）基于局部信息进行预测，所以当k比较小时，对噪声数据很敏感，而模型分类算法是基于整体的。

注意点：（i）选择什么样的临近度度量和数据处理很重要，如（身高，体重）来对人分类，身高的可变性可能很小（0.2-2.5m），而体重的可变范围比较大（5-150kg），如果不考虑属性单位，那么临近度就可能只被体重左右。（ii）k太小，则z身边的第一个点就决定了z的类，由于没有充分参考training set的信息，所以是underfitting 的，如果k太大，一个极端的例子就是k>n，则所有的点都属于多数一类。

knn算法及R语言实现（1）