机器学习(一):k最近邻(kNN)算法

一、概述

kNN算法,即K最近邻(k-NearestNeighbor)分类算法,是最简单的机器学习算法,没有之一。 该算法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。K通常是不大于20的整数。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

kNN

如上图所示,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。由此也说明了KNN算法的结果很大程度取决于K的选择。 在kNN中,计算对象之间的距离通常使用欧氏距离。比如若是求二维平面的欧氏距离,则公式为d = sqrt[(x1 - x2)^2 + (y1 - y2)^2] 接下来对KNN算法的思想总结一下:就是在训练集中数据和标签已知的情况下,输入测试数据,将测试数据的特征与训练集中对应的特征进行相互比较,找到训练集中与之最为相似的前K个数据,则该测试数据对应的类别就是K个数据中出现次数最多的那个分类,其算法的描述为: (一)计算测试数据与各个训练数据之间的距离; (二)按照距离的递增关系进行排序; (三)选取距离最小的K个点; (四)确定前K个点所在类别的出现频率; (五)返回前K个点中出现频率最高的类别作为测试数据的预测分类。

二、python函数准备

在用python编写kNN算法之前,有一些数值相关的python函数需要了解一下。 (一)shape() shape是numpy函数库中的方法,用于查看矩阵或者数组的维数 shape(array)若矩阵有m行n列,则返回(m,n) array.shape[0]返回矩阵的行数m,array.shape[1]返回矩阵的列数n

(二)tile() tile()是numpy函数库中的方法,作用是数组沿各维度重复自己。函数的形式是tile(A,reps)。 以A=[1,2]为例。

例1:tile(A,2) = [1,2,1,2] 分析:A的第一个维度重复2遍(包含本身的一遍),得到的结果为[1,2,1,2]

例2:tile(A,(2,3)) = [[1,2,1,2,1,2], [1,2,1,2,1,2]] 分析:reps的数字从后往前分别对应A的第N个维度的重复次数。A的第一个维度重复3遍,得到[1,2,1,2,1,2]。在此基础上,第二个维度重复2遍,得到[[1,2,1,2,1,2], [1,2,1,2,1,2]]

例3:tile(A,(2,2,3)) = [[[1,2,1,2,1,2], [1,2,1,2,1,2]],             [[1,2,1,2,1,2], [1,2,1,2,1,2]]]

分析:reps的数字从后往前分别对应A的第N个维度的重复次数。A的第一个维度重复3遍,得到[1,2,1,2,1,2]。在此基础上,第二个维度重复2遍,得到[[1,2,1,2,1,2], [1,2,1,2,1,2]]。在此基础上,第三个维度重复2遍,得到[[[1,2,1,2,1,2], [1,2,1,2,1,2]], [[1,2,1,2,1,2], [1,2,1,2,1,2]]]

(三)sum() sum()是numpy函数库中的方法 array.sum(axis=1)按行累加,array.sum(axis=0)按列累加 例:A = [[1,2],[3,4]],则A.sum(axis=1) = [3, 7],A.sum(axis=0) = [4, 6]

(四)argsort() argsort()是numpy中的方法,得到排序后新矩阵中每个元素对应于该元素在未排序前旧矩阵中的位置。 例:A = [3, 1, 2],则argsort(A) = [1, 2, 0]。因为排序后得到的新矩阵A’= [1, 2, 3],“1”是A的第1个元素,“2”是A的第2个元素,“3”是A的第0个元素,所以结果为[1, 2, 0]

(五)get() dict.get(key, default=None)是python中的方法,default表示假如指定的键不存在的话,返回的默认值。 例:dict d={‘age’, 20},则d.get(‘age’,0) = 20, d.get(‘name’, 0) = 0

三、程序实现

(一)代码

# coding:utf-8
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,labels,k):
    dataSize = dataSet.shape[0]
    # 计算欧氏距离
    diff = tile(input,(dataSize,1)) - dataSet
    diff2 = diff ** 2
    # 行向量分别相加,从而得到新的一个行向量
    dist2 = sum(diff2,axis = 1) 
    dist = dist2 ** 0.5
    # 对距离进行排序,按从小到大的规则
    distIndex = argsort(dist)
    labelCount = {}
    for i in range(k):
        label = labels[distIndex[i]]
        # 对选取的K个样本所属的类别个数进行统计
        labelCount[label] = labelCount.get(label,0) + 1
    # 选取出现的类别次数最多的类别
    maxCount = 0
    for key,value in labelCount.items():
        if value > maxCount:
            maxCount = value
            targetLabel = key
    return targetLabel
def test():
    dataSet,labels = createDataSet()
    input = array([1.1,0.3])
    K = 3
    output = classify(input,dataSet,labels,K)
    print("Test data:",input,"classify result:",output)

(二)运行结果 打开cmd命令行窗口,输入如下命令

> pushd E:\MachineLearning\kNN
> python 
>>> import kNN
>>> kNN.test()

result

四、程序分析

(一)这里训练集为 [[1.0, 2.0], [1.2, 0.1], [0.1, 1.4], [0.3, 3.5]] 训练集中的4个元素分别对应于类别A, A, B, B 可将训练集中的四个元素看做四个点: x0(1.0, 2.0), x1(1.2, 0.1), x2(0.1, 1.4), x3(0.3, 3.5) 测试点为x(1.1, 0.3)

(二)classify()函数逐行分析 dataSize = 4(行数) tile(input, (4, 1)) = [[1.1, 0.3], [1.1, 0.3], [1.1, 0.3], [1.1, 0.3]]

tile(input, (4, 1)) - dataSet = [[ 0.1, -1.7], [-0.1, 0.2], [1, -1.1], [0.8, -3.2]] 这里每行中的两个数,具体是这么算出来的: x - x0 = 0.1, y - y0 = -1.7 x - x1 = -0.1, y - y1 = 0.2 x - x2 = 1, y - y2 = -1.1 x - x3 = 0.8, y - y3 = -3.2

diff2 = [[0.01, 2.89], [0.01, 0.04], [1, 1.21], [0.64, 10.24] 这些数据是这么计算出来的: (x - x0)^2 = 0.01, (y - y0)^2 = 2.89 (x - x1)^2 = 0.01, (y - y1)^2 = 0.04 (x - x2)^2 = 1, (y - y2)^2 = 1.21 (x - x3)^2 = 0.64, (y - y3)^2 = 10.24

dist2 = [2.9, 0.05, 2.21, 10.88] 这里每个元素就代表每个点与x0的距离的平方,即 d0^2 = (x - x0)^2 + (y - y0)^2 = 2.9 d1^2 = (x - x1)^2 + (y - y1)^2 = 0.05 d2^3 = (x - x2)^2 + (y - y2)^2 = 2.21 d3^4 = (x - x3)^2 + (y - y3)^2 = 10.88

dist = [1.70293864, 0.2236068, 1.48660687, 3.2984845] 这里每个元素代表每个点与x的距离,即 d0 = 1.70293864 d1 = 0.2236068 d2 = 1.48660687 d3 = 3.2984845

distIndex = [1, 2, 0, 3],表示 最小的距离位于dist中的第1个位置,即d1 次小的距离的位于dist中的第2个位置,即d2 第三小的距离位于dist中的第0个位置,即d0 最大距离位于dist中的第3位置,即d3

第一个for循环中, for 0 in range(3) label = labels[1] = ‘A’ classCount[‘A’] = 1 for 1 in range(3) label = labels[2] = ‘B’ classCount[‘B’] = 1 for 2 in range(3) label = labes[0] = ‘A’ labelCount[‘A’] = 2 所以,字典labelCount中的值为{‘A’:2, ‘B’:1}。

第二个for循环中, for ‘A’,2 in labelCount value = 2, maxCount = 0, if条件成立 maxCount = 2, label = ‘A’ for ‘B’,1 in labelCount value = 1, maxCount = 2, if条件不成立。循环结束。

最终,返回targetLabel = ’A’

五、Github代码下载地址

kNN算法Github下载

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-03-06

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PaddlePaddle

【进阶篇】RNN配置

编写|PaddlePaddle 排版|wangp 本教程将指导你如何在 PaddlePaddle 中配置循环神经网络(RNN)。本教程中,您将了解如何: 配置循...

4608
来自专栏帮你学MatLab

《Experiment with MATLAB》读书笔记(十)

读书笔记(十) %% 矩阵的操作 format short A = magic(3) %产生三阶幻方矩阵 sum(A) %对列求和 ...

30512
来自专栏木子昭的博客

万能的0和1 之 字典特征抽取

机器是无法识别自然语言的,机器只能识别0和1,经典的案例就是字典特征抽取 0表示不存在 1表示存在 以国漫人物信息,做示例 原始数据 ? ...

3048
来自专栏CreateAMind

keras中文-快速开始Sequential模型

模型需要知道输入数据的shape,因此,Sequential的第一层需要接受一个关于输入数据shape的参数,后面的各个层则可以自动的推导出中间数据的shape...

1674
来自专栏书山有路勤为径

Batch Normalization怎么加入batch normalization

Batch Normalization 会使你的参数搜索问题变得很容易,使神经网络对超参数的选择更加稳定,超参数的范围会更加庞大,工作效果也很好,也会使你的训练...

902
来自专栏marsggbo

【TensorFlow】tf.nn.softmax_cross_entropy_with_logits的用法

在计算loss的时候,最常见的一句话就是 tf.nn.softmax_cross_entropy_with_logits ,那么它到底是怎么做的呢?

721
来自专栏数值分析与有限元编程

可视化 | MATLAB画杆系结构变形图

一图胜千言。将计算结果用图表达出来定是极好的! 调用MATLAB中的line函数可以画直线。例如line([1,2],[3,4])将画出(1,3)到(2,4)...

4185
来自专栏AIUAI

Caffe Loss层 - SoftmaxWithLossLayer

4559
来自专栏CreateAMind

keras doc 4 使用陷阱与模型

1041
来自专栏杂七杂八

numpy中random模块使用

在python数据分析的学习和应用过程中,经常需要用到numpy的随机函数,下面我们学习一下具体的使用,本文着重说明各个分布随机数的生成。 numpy.rand...

4505

扫码关注云+社区

领取腾讯云代金券