本文中介绍的机器学习算法中的一种监督学习的算法:KNN
算法,全称是K-Nearest Neighbor
,中文称之为K
近邻算法。
它是机器学习可以说是最简单的分类算法之一,同时也是最常用的分类算法之一。在接下来的内容中,将通过以下的几个方面的内容对该算法进行详细的讲解:
<!--MORE-->
首先对KNN
算法的思想进行简单的描述:
KNN算法是一个基本的分类和回归的算法,它是属于监督学习中分类方法的一种。其大致思想表述为:
用一句俗语来总结KNN算法的思想:物以类聚,人以群分
KNN
算法的步骤非常简单:
K
(下面👇会具体讲解K值的相关问题)Majority-Voting
)规则,将未知实例归类为样本中最多数的类别下面通过一组图形来解释下KNN
算法的思想。我们的目的是:判断蓝色的点属于哪个类别
我们通过变化K的取值来进行判断。在该算法中K的取值一般是奇数,防止两个类别的个数相同,无法判断对象的类别 K=1、3、5、7…….
根据图形判断:蓝色图形应该是属于三角形
从图中可以看出来:蓝色部分还是属于三角形
此时我们观察到蓝色部分属于正方形了
这个时候蓝色部分又变成了三角形
当K取值不同的时候,判别的结果是不同的。所以该算法中K值如何选择将非常重要,因为它会影响到我们最终的结果。
上面的一系列图形中已经说明了该算法中K值对结果的影响。那么K值到底该如何选择呢?谜底揭晓:交叉验证
K值一般是通过交叉验证来确定的;经验规则来说,一般k是低于训练样本数的平方根
所谓交叉验证就是通过将原始数据按照一定的比例,比如6/4,拆分成训练数据集和测试数据集,K值从一个较小的值开始选取,逐渐增大,然后计算整个集合的方差,从而确定一个合适的K值。
经过使用交叉验证,我们会得到类似如下的图形,从图形中可以明显的:
k值太小:容易受到噪声点的影响
k值太大:分类太多,太细,导致包含太多其他类别的点
在上面的算法原理中提到,需要计算测试对象和训练集合中每个对象距离。在机器学习中,两个对象之间的距离包含:
常用的距离有以下几种:
在KNN
算法中我们一般采用的是欧式距离(常用)或者曼哈顿距离
N
维空间的距离:
当n=2
时候,称之为欧式距离:
其中X
称之为到原点的欧式距离
曼哈顿距离是闵可夫斯基距离的一种特殊情形。闵可夫斯基距离指的是:
当p=2
,变成欧式距离;
当p=1
,变成曼哈顿距离;
当p
区域无穷,变成切比雪夫距离;
KNN
算法可以说是机器算法中最简单易懂的算法。即使初学者没有太多的基础,相信也能明白它的原理。KNN
算法没有明确的数据训练过程,或者说它根本不需要进行数据的训练,直接可以对测试对象进行判断。什么时候使用KNN
算法?scikit-learn
官方中的一张图给出了一个答案:
下面通过一个简单的算法来实现KNN
算法,主要步骤为:
KNN
算法进行分类
# coding:utf-8
# author: Peter
from numpy import *
import operator
# 给出训练数据以及对应的类别
def createDataSet(): # 创建数据和标签
group = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
labels = ['A','A','B','B']
return group,labels
# 使用KNN算法进行分类
def classify(input, dataSet, label, k):
dataSize = dataSet.shape[0]
# 计算欧式距离
diff = tile(input,(dataSize,1)) - dataSet
sqdiff = diff ** 2
squareDist = sum(sqdiff,axis = 1) #行向量分别相加,从而得到新的一个行向量
dist = squareDist ** 0.5
##对距离进行排序:argsort()根据元素的值从大到小对元素进行排序,返回下标
sortedDistIndex = argsort(dist)
classCount={}
for i in range(k):
voteLabel = label[sortedDistIndex[i]]
# K个样本所属的类别个数进行统计
classCount[voteLabel] = classCount.get(voteLabel,0) + 1
# 选取出现的类别次数最多的类别
maxCount = 0
for key,value in classCount.items():
if value > maxCount:
maxCount = value
classes = key
return classes
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。