K-近邻算法(KNN)概述

最简单最初级的分类器是将全部的训练数据所对应的类别都记录下来,当测试对象的属性和某个训练对象的属性完全匹配时,便可以对其进行分类。但是怎么可能所有测试对象都会找到与之完全匹配的训练对象呢,其次就是存在一个测试对象同时与多个训练对象匹配,导致一个训练对象被分到了多个类的问题,基于这些问题呢,就产生了KNN。

KNN是通过测量不同特征值之间的距离进行分类。它的的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。K通常是不大于20的整数。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

下面通过一个简单的例子说明一下:如下图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。

由此也说明了KNN算法的结果很大程度取决于K的选择。

在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离:

同时,KNN通过依据k个对象中占优的类别进行决策,而不是单一的对象类别决策。这两点就是KNN算法的优势。

接下来对KNN算法的思想总结一下:就是在训练集中数据和标签已知的情况下,输入测试数据,将测试数据的特征与训练集中对应的特征进行相互比较,找到训练集中与之最为相似的前K个数据,则该测试数据对应的类别就是K个数据中出现次数最多的那个分类,其算法的描述为:

1)计算测试数据与各个训练数据之间的距离;

2)按照距离的递增关系进行排序;

3)选取距离最小的K个点;

4)确定前K个点所在类别的出现频率;

5)返回前K个点中出现频率最高的类别作为测试数据的预测分类。

#########################################

# kNN: k Nearest Neighbors  
# Input:      newInput: vector to compare to existing dataset (1xN)  
#             dataSet:  size m data set of known vectors (NxM)  
#             labels:   data set labels (1xM vector)  
#             k:        number of neighbors to use for comparison   
# Output:     the most popular class label  
#########################################  
from numpy import * 
import operator  
# create a dataset which contains 4 samples with 2 classes  
def createDataSet(): 
 # create a matrix: each row as a sample  
    group = array([[1.0, 0.9], [1.0, 1.0], [0.1, 0.2], [0.0, 0.1]]) 
    labels = ['A', 'A', 'B', 'B'] # four samples and two classes  
 return group, labels  
# classify using kNN  
def kNNClassify(newInput, dataSet, labels, k): 
    numSamples = dataSet.shape[0] # shape[0] stands for the num of row  
 ## step 1: calculate Euclidean distance  
 # tile(A, reps): Construct an array by repeating A reps times  
 # the following copy numSamples rows for dataSet  
    diff = tile(newInput, (numSamples, 1)) - dataSet # Subtract element-wise  
    squaredDiff = diff ** 2 # squared for the subtract  
    squaredDist = sum(squaredDiff, axis = 1) # sum is performed by row  
    distance = squaredDist ** 0.5 
 ## step 2: sort the distance  
 # argsort() returns the indices that would sort an array in a ascending order  
    sortedDistIndices = argsort(distance) 
    classCount = {} # define a dictionary (can be append element)  
 for i in range(k): 
 ## step 3: choose the min k distance  
        voteLabel = labels[sortedDistIndices[i]] 
 ## step 4: count the times labels occur  
 # when the key voteLabel is not in dictionary classCount, get()  
 # will return 0  
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 
 ## step 5: the max voted class will return  
    maxCount = 0 
 for key, value in classCount.items(): 
 if value > maxCount: 
            maxCount = value  
            maxIndex = key  
 return maxIndex  

原文发布于微信公众号 - 瓜大三哥(xiguazai_tortoise)

原文发表时间:2018-01-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

机器学习之随机森林

机器执行的每一个步都依赖于我们的指令。它们需要指导去哪里做什么,就像一个不了解周围环境而无法自己做决定的孩子。因此,开发人员会需要为机器编写指令。然而当我们谈论...

2058
来自专栏mantou大数据

[机器学习实战]K-近邻算法

1. K-近邻算法概述(k-Nearest Neighbor,KNN) K-近邻算法采用测量不同的特征值之间的距离方法进行分类。该方法的思路是:如果一个样本在特...

4465
来自专栏along的开发之旅

glLoadIdentity()与glTranslatef()和glRotatef()--坐标变换

初学OpenGL,对它的矩阵变换不甚了解,尤其是glTranslatef和glRotatef联合使用,立即迷得不知道东西南北。在代码中改变数据多次,终于得到了相...

1244
来自专栏绿巨人专栏

神经网络学习笔记-02-循环神经网络

3637
来自专栏瓜大三哥

基于FPGA的非线性滤波器(一) 之概述

一类比较重要的非线性滤波器就是统计排序滤波器。 统计排序滤波器对窗口内的像素值进行排序并通过多路选择选择器选择排序后的值,例如中值滤波、最大/最...

1919
来自专栏深度学习与数据挖掘实战

干货|深度学习面试问答集锦

No.19 CNN中,conv layer、ReLu layer、Pooling layer、Fully connected layer的区别?

1184
来自专栏机器学习原理

图像处理和数据增强图片处理数据增强颜色空间转换噪音数据的加入样本不均衡

7394
来自专栏yw的数据分析

R语言通过loess去除某个变量对数据的影响

  当我们想研究不同sample的某个变量A之间的差异时,往往会因为其它一些变量B对该变量的固有影响,而影响不同sample变量A的比较,这个时候需要对samp...

4298
来自专栏海天一树

决策树

决策树是一种特殊的树形结构,一般由节点和有向边组成。其中,节点表示特征、属性或者一个类。而有向边包含有判断条件。如图所示,决策树从根节点开始延伸,经过不同的判断...

2392
来自专栏刘明的小酒馆

图片相似检测:三行代码实现

检查两个图片的相似度,一个简单而快速的算法:感知哈希算法(Perceptual Hash),通过某种提取特征的方式为每个图片计算一个指纹(哈希),这样对比两个图...

5455

扫码关注云+社区

领取腾讯云代金券