美文网首页嵌牛IT观察
大数据经典算法解析(8)一KNN算法

大数据经典算法解析(8)一KNN算法

作者: 冬瓜小正太 | 来源:发表于2017-12-15 21:39 被阅读0次

      姓名:崔升    学号:14020120005

      转载自:http://www.cnblogs.com/en-heng/p/5173704.html

    【嵌牛导读】:

     本文讨论的kNN算法是监督学习中分类方法的一种。所谓监督学习与非监督学习,是指训练数据是   否有标注类别,若有则为监督学习,若否则为非监督学习。监督学习是根据输入数据(训练数据)   学习一个模型,能对后来的输入做预测。在监督学习中,输入变量与输出变量可以是连续的,也可   以是离散的。若输入变量与输出变量均为连续变量,则称为回归;输出变量为有限个离散变量,则   称为分类;输入变量与输出变量均为变量序列,则称为标注[2]。

    【嵌牛鼻子】:经典大数据算法之kNN算法的简单介绍

    【嵌牛提问】:kNN是一种怎么的算法,其数学原理又是如何?

    【嵌牛正文】:

    1. 引言

    顶级数据挖掘会议ICDM于2006年12月评选出了数据挖掘领域的十大经典算法:C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naïve Bayes与 CART。 以前看过关于这些数据挖掘算法,但对背后数学原理未做过多探究,因而借此整理以更深入地理解这些算法。

    2. kNN算法

    kNN算法的核心思想非常简单:在训练集中选取离输入的数据点最近的k个邻居,根据这个k个邻居中出现次数最多的类别(最大表决规则),作为该数据点的类别。

    算法描述

    训练集T={(x1,y1),(x2,y2),⋯,(xN,yN)}T={(x1,y1),(x2,y2),⋯,(xN,yN)},其类别yi∈{c1,c2,⋯,cK}yi∈{c1,c2,⋯,cK},训练集中样本点数为NN,类别数为KK。输入待预测数据xx,则预测类别

    y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,⋯,N;j=1,2,⋯,K(1)(1)y=arg⁡maxcj⁡∑xi∈Nk(x)I(yi=cj),i=1,2,⋯,N;j=1,2,⋯,K

    其中,涵盖xx的k邻域记作Nk(x)Nk(x),当yi=cjyi=cj时指示函数I=1I=1,否则I=0I=0。

    分类决策规则

    kNN学习模型:输入XX,通过学习得到决策函数:输出类别Y=f(X)Y=f(X)。假设分类损失函数为0-1损失函数,即分类正确时损失函数值为0,分类错误时则为1。假如给xx预测类别为cjcj,即f(X)=cjf(X)=cj;同时由式子(1)(1)可知k邻域的样本点对学习模型的贡献度是均等的,则kNN学习模型误分类率为

    1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)(2)(2)1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)

    若要最小化误分类率,则应

    maxcj∑xi∈Nk(x)I(yi=cj)maxcj⁡∑xi∈Nk(x)I(yi=cj)

    所以,最大表决规则等价于经验风险最小化。

    存在问题

    k值得选取对kNN学习模型有着很大的影响。若k值过小,预测结果会对噪音样本点显得异常敏感。特别地,当k等于1时,kNN退化成最近邻算法,没有了显式的学习过程。若k值过大,会有较大的邻域训练样本进行预测,可以减小噪音样本点的减少;但是距离较远的训练样本点对预测结果会有贡献,以至于造成预测结果错误。下图给出k值的选取对于预测结果的影响:

    前面提到过,k邻域的样本点对预测结果的贡献度是相等的;但距离更近的样本点应有更大的相似度,其贡献度应比距离更远的样本点大。可以加上权值wi=1/∥xi−x∥wi=1/‖xi−x‖进行修正,则最大表决原则变成:

    maxcj∑xi∈Nk(x)wi∗I(yi=cj)maxcj⁡∑xi∈Nk(x)wi∗I(yi=cj)

    3. 参考资料

    [1] Michael Steinbach and Pang-Ning Tan, The Top Ten Algorithms in Data Mining.

    [2] 李航,《统计学习方法》.

    相关文章

      网友评论

        本文标题:大数据经典算法解析(8)一KNN算法

        本文链接:https://www.haomeiwen.com/subject/xwcjwxtx.html