星期日, 五月 06, 2012

为KNN分类器增加Cross-Validation功能


有这么一句很有趣的话,如果一个东西走路象鸭子、叫起来象鸭子、吃起来也象鸭子,那它就是一只鸭子。这是一种很符合我们直觉的思维方式:将未知的对象和已知的东西相比较,如果各个属性相近,我们就把它们归为一个类别。这就是KNN分类器的思想。

KNN即是kth Nearest Neighbor。如果我们已经拥有一些已知类别的数据,要对一些未知类别的数据进行分类。基本思路就是将数据看作是在多元空间中的点,先计算未知点和周围k个已知点之间的距离。然后根据周围k个已知点的类别进行投票来决定未知点的类别。例如设k为3,对某个未知点找出其周围最近的三个已知点,如果这三个点有两个属于A类,一个属于B类,那么根据多数原则,将未知点的类别预测为A类。

KNN算法的优势在于算法简单,稳健性强,可以构成非线性的判别边界,模型参数简单,只有距离测度和k参数。其弱点在于计算量较大,对异常点较为敏感,对不平衡数据也很敏感。R语言中class包的knn函数可以实行基本的KNN算法。

但只用knn函数来预测是有问题的。如果同样一个数据集,我们用它进行训练又用它进行预测,这显然是不合适的。这就好象是用课堂上讲过的例题来考察一个学生的掌握程度。这样往往会高估模型的准确性。或者说形成了过度拟合(Overfit)的情况。处理过度拟合的问题通常有以下几个思路:其一是保留数据,也就是Hold-Out,Cross-Validation,Loocv这些方法;其二是对模型的复杂度进行约束,例如AIC指标的思路就是对模型参数个数进行惩罚。再如岭回归(Ridge Regression)和套索方法(lasso)就是对模型参数的总强度进行惩罚。本文只涉及到Cross-Validation,其它的留待之后再分解吧。

Cross-Validation(交叉检验)就是将原始数据随机分割为F等分,保留其中一份数据,用剩下的数据进行训练,再用保留的数据对训练得到的模型进行检验。这样的步骤重复F次,我们就得到了较为客观的模型评价。从而可以确定较好的参数值。对Cross-Validation有兴趣的同学还可以参看这份文档

下面我们根据上述思路建立一个vknn函数,使其具备交叉检验的功能。利用iris数据集为研究对象。代码来自于《Concepts in Computing with Data》这本书。顺便推荐一下这本非常精彩的R教程。代码如下


当然,将上面的函数略加修改,即可用到其它的分类器上面。此外,class包中也有knn.cv函数,可以完成同样的工作。对于KNN算法,R语言中还有一个kknn包值得关注,它对于基本的knn函数有很大程度的扩展。它不只可以处理分类问题,还可以处理回归问题。另外它还可以结合核函数,利用距离进行加权计算。最后要说的是,使用KNN算法之前要先将数据标准化处理。

参考资料:
《Handbook of statistical Analysis and Data mining Applications》

2 条评论:

  1. 肖老师,您好。请问数据标准化处理常见的方法有哪些呢?
    data=apply(data,2,function(x){
    x=x/(max(x)-min(x))
    return(x)
    })
    像这样是最简单的,可行吗?

    回复删除
    回复
    1. 有很多,比如(x-mean(x))/sd(x) 或者 (x-median(x))/IQR(x) 。你这个好象有点错误,应该是:(x-min(x))/(max(x)-min(x))

      删除