关键词：
参考技术A 姓名：崔升 学号：14020120005【嵌牛导读】：
本文讨论的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,⋯,cKyi∈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=argmaxcj∑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] 李航，《统计学习方法》.
pyhon3实现机器学习经典算法knn(代码片段)
...KNN概述 K-（最）近邻算法KNN（k-NearestNeighbor）是数据挖掘分类技术中最简单的方法之一。它具有精度高、对异常值不敏感的优点，适合用来处理离散的数值型数据，但是它具有 非常高的计算复杂度和空间复杂度，需... 查看详情
邻居数 KNN 算法
...一个1*64的矢量。因此，每次我将第一个数字与所有其余数据集（非常大）进行比较时，然后将第二个数字与其余数据集等等等等等等。现在我的问题是，不是1个邻居是最佳选择吗总是？由于我使用的是欧几里 查看详情
大数据学习笔记-knn算法
1.背景：分类（Classification）是数据挖掘领域中的一种重要的技术，它是从一组已知的训练样本中发现分类模型，并且使用这个分类模型来预测待分类样本。建立一个有效的分类算法模型最终将待分类的样本进... 查看详情
数据挖掘之分类算法---knn算法(有matlab样例)
knn算法(k-NearestNeighboralgorithm).是一种经典的分类算法.注意,不是聚类算法.所以这样的分类算法必定包含了训练过程.然而和一般性的分类算法不同,knn算法是一种懒惰算法.它并不是像其它的分类算法先通过训练建立分类模型.,而是... 查看详情
18大经典数据挖掘算法小结
18大经典数据挖掘算法小结本文所有涉及到的数据挖掘代码的都放在了我的github上了。地址链接: https://github.com/linyiqun/DataMiningAlgorithm大概花了将近2个月的时间，自己把18大数据挖掘的经典算法进行了学习并且进行了代码... 查看详情
大数据学习笔记-knn算法
1.背景：分类（Classification）是数据挖掘领域中的一种重要的技术，它是从一组已知的训练样本中发现分类模型，并且使用这个分类模型来预测待分类样本。建立一个有效的分类算法模型最终将待分类的样本进... 查看详情
数据挖掘经典算法之k-邻近算法（超详细附代码）
...分类算法。目的是根据已知类别的样本点集求出待分类的数据点类别。基本思想kNN的思想很简单：在训练集中选取离输入的数据点最近的k个邻居，根据这个k个邻居中出现次数最多的类别（最大表决规则），作为该数据点的类别... 查看详情
machine_learning-knn算法具体解释(近邻算法)
...算法是机器学习算法中的入门算法，该算法用于针对已有数据集对未知数据进行分类。该算法核心思想是通过计算预測数据与已有数据的相似度猜測结果。举例：如果有例如以下一组数据(在下面我们统一把该数据作为训练数... 查看详情
ml:knn算法
...简单的理解为由那离自己最近的K个点来投票决定待分类数据归为哪一类。这个算法是机器学习里面一个比较经典的算法，总体来说KNN算法是相对比较容易理解的算法。其中的K表示最接近自己的K个数据样本。KNN算法和K-Means算法... 查看详情
机器学习算法原理解析——分类(代码片段)
...衡量样本之间的相似度。1.2算法图示从训练集中找到和新数据最接近的k条记录，然后根据多数类来决定新数据类别算法涉及3个主 查看详情
knn算法的实现
KNN算法是机器学习经典十大算法之一，简单易懂。这里给出KNN的实现，由两个版本：1.机器学习实战上作者的实现版本，我自己又敲了一遍感觉还是蛮有收获的；2.用自己的理解的一个实现，主要的区别就是效率没有第一个高，... 查看详情
使用knn算法对鸢尾花种类预测(代码片段)
使用KNN算法对鸢尾花种类预测一.数据集介绍1.1小数据集获取load_*1.2大数据集获取fetch_*1.3查看数据分布seaborn画图的二.数据集的划分三.特征工程3.1归一化处理MinMaxScaler3.2标准化StandardScaler四.流程实现4.1导包4.2获取数据集4.3数据基... 查看详情
大数据算法：分类算法
...种基本的分类算法。其主要原理是：对于一个需要分类的数据，将其和一组已经分类标注好的样本集合进行比较，得到距离最近的K个样本，K个样本最多归属的类别，就是这个需要分类数据的类别。下面我给你画了一个KNN算法的... 查看详情
k-近邻算法（knn）(代码片段)
...4k值选择5KNN优化—kd树5.1kd树简介5.2构造方法5.3案例分析6数据集6.1获取数据集6.2划分数据集7特征工程—特征预处理7.1归一化7.2标准化7.3案例分析8交叉验证8.1什么是交叉验证8.2模型选择与调优8.3增加K值调优案例9综合案例9.1案 查看详情
数据挖掘之knn算法（c#实现）
在十大经典数据挖掘算法中，KNN算法算得上是最为简单的一种。该算法是一种惰性学习法（lazylearner），与决策树、朴素贝叶斯这些急切学习法（eagerlearner）有所区别。惰性学习法仅仅只是简单地存储训练元组，做一些少量工作... 查看详情
数据挖掘中的10大算法
...类器。为了做到这一点，需要给定C4.5表达内容已分类的数据集合。等下， 查看详情
knn算法理解
...分类器也许是那种死记硬背式的分类器，记住所有的训练数据，对于新的数据则直接和训练数据匹配，如果存在相同属性的训练数据，则直接用它的分 查看详情
经典算法问题-最大连续子数列和
...决这个问题。为了更清晰的理解问题，首先我们先看一组数据：8-26-154-723第一行的8是说序列的 查看详情