统计学习方法之K近邻法1.k近邻法(k-nearest neighbor,k-NN)2.k近邻模型3.k近邻算法的实现

1.k近邻法(k-nearest neighbor,k-NN)

  • k近邻算法是一个基本分类和回归方法,k-NN的输入时实例的特征向量,对应于特征空间的点,输出是实力的类别,可以取多类。k-NN不具有显式的学习过程,k-NN实际上利用训练数据集对特征向量空间进行划分,并且作为其分类的“模型”。
  • k-NN简单直观:给定一个训练集,对新的输入实力,在训练数据集中找到与该实例最近邻的k个实例,这k个实例的多数所属于的类别就作为新实例的类。
  • 输入:训练数据集T=(x1,y1),(x2,y2),...(xN,yN) 输出:实例x所属的类y 算法步骤: (1)根据给定的距离度量,在训练集T中找出与x最近邻的k个点,涵盖这k个点的x的邻域记作Nk(x) (2)在Nk(x)中根据分类决策规则,如多数表决决定x的类别y。
  • 当k==1的时候,称为最近邻算法,对于输入的实例点,x,最近邻法将训练数据集中与x最近的点的所属类别作为x的类。

2.k近邻模型

  • k-NN使用的模型实际上对应于听特征空间的划分,模型由三个基本要素:距离度量,k值的选择,分类决策规则。k近邻模型的核心就是使用一种距离度量,获得距离目标点最近的k个点,根据分类决策规则,决定目标点的分类。

2.1距离度量

  • 特征空间中,两个实例点的距离是两个实例点的相似程度的反映。k-NN模型的特征空间一般是n维实数向量空间,使用的距离是欧氏距离,但也可以是其他距离,比如更一般的Lp距离(Lp distance)或者Minkowski距离。
  • 一个点和一个点之间的距离,无论是什么计算方式,基本上离不开Lp距离。欧式距离,则是L2范式,也就是p=2的情况,而另一个很熟悉的距离曼哈顿距离,则是L1范式。Lp距离的定义如下:
  • 当然,如果p→∞的时候,就叫做切比雪夫距离了。 除了这个闵可夫斯基距离集合外,还有另外的距离评估体系,例如马氏距离、巴氏距离、汉明距离,这些都是和概率论中的统计学度量标准相关。而像夹角余弦、杰卡德相似系数、皮尔逊系数等都是和相似度有关的。
  • 因此,简单说来,各种“距离”的应用场景简单概括为,空间:欧氏距离,路径:曼哈顿距离,国际象棋国王:切比雪夫距离,以上三种的统一形式:闵可夫斯基距离,加权:标准化欧氏距离,排除量纲和依存:马氏距离,向量差距:夹角余弦,编码差别:汉明距离,集合近似度:杰卡德类似系数与距离,相关:相关系数与相关距离。
  • 这其实只是个度量标准而已,应当根据数据特征选择相应的度量标准。
  • 由不同的距离度量所确定的邻近点是不同的。

2.2 k值的选择

近似误差、估计误差知乎解释

  • 选取比较小的k值(较复杂的模型),近似误差(approximation error)会减小,而估计误差(estimation error)会增大,如果选择的k值较小,就相当于用较小的的邻域中的训练实例进行预测。此时预测的结果会对近邻的实例点非常敏感,因为影响分类的都是比较近的样本,但一旦出现噪点,预测就会出错。 选取比较大的k值(较简单的模型),相反,减小噪点的影响,但是较远或不相似的样本也会对结果有影响,就相当于在较大的邻域中训练实例进行预测。此时,与输入实例较远的训练实例也会对预测起作用,使预测发生错误。极限情况下k=N,考虑所有样本,极简模型 。
  • 在应用中,k值一般选取一个比较小的数值,通常采用交叉验证法来选取最优的k值。

2.3分类决策规则

  • 大多情况是多数表决,即由输入实例的k个近邻中的多数类决定x的类别。也可以采用别的分类决策规则。 01损失函数CSDN

3.k近邻算法的实现

  • 实现k-NN算法,主要考虑的问题是如何对训练集进行快速k近邻搜索。
  • 简单实现方式:线性搜索,对于数据量很大时,此方法是不可行的。所以考虑更好的方法
  • 采用特殊结构来存储训练集,以减小计算距离的次数,比如kd树方法。

3.1简单实现

  • 文件数据
hei,wei,tag
1.5,40,thin
1.5,50,fat
1.5,60,fat
1.6,40,thin
1.6,50,thin
1.6,60,fat
1.6,70,fat
1.7,50,thin
1.7,60,thin
1.7,70,fat
1.7,80,fat
1.8,60,thin
1.8,70,thin
1.8,80,fat
1.8,90,fat
1.9,80,thin
1.9,90,fat
  • knn.py
# -*- coding: utf-8 -*-
"""
Created on Fri Dec  8 17:21:14 2017

@author: jasonhaven
"""

import os
import numpy as np
import pandas as pd
import operator
import matplotlib.patches as mpatches
import matplotlib.pyplot as plt

def read_from_csv(file):
    '''
    file:文件绝对地址
    功能:读入csv文件并解析出数据集和标签集
    '''
    pwd=os.getcwd()
    os.chdir(os.path.dirname(file))
    df=pd.read_csv('data.csv')
    os.chdir(pwd)
    datas=df.iloc[:,:2].astype(np.float).values
    labels = df.iloc[0:,-1:].astype(np.str).values#加载类别标签部分
    return datas,labels


def classify(instance,datas,labels,k):
    '''
    instance:新的实例特征向量
    datas:训练数据集
    labels:标签集
    k:选择相邻的k个实例
    '''
    num=datas.shape[0]
    #tile(A, reps)返回一个shape=reps的矩阵,矩阵的每个元素是A
    diffMat = np.tile(instance, (num, 1)) - datas
    #diffMat就是输入样本与每个训练样本的差值
    square_diffMat = diffMat**2
    #然后对其每个x和y的差值进行平方运算。
    square_distances=square_diffMat.sum(axis=1)
    #开平方根求出距离
    distances=square_distances**0.5
    #argsort函数返回的是关键字(数组值)从小到大的索引值
    sorted_distances = distances.argsort()
    
    class_count = {}
    # 投票过程,就是统计前k个最近的样本所属类别包含的样本个数
    for i in range(k):
        # sortedDistIndicies[i]是第i个最相近的样本下标
        voteIlabel = str(labels[sorted_distances[i]])
        # 然后将票数增1
        class_count[voteIlabel] = class_count.get(voteIlabel, 0) + 1
    # 把分类结果进行排序,然后返回得票数最多的分类结果
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_class_count[0][0]
    

def draw(datas,labels):
    plt.figure('KNN')
    plt.title('KNN')
    plt.xlabel('height')
    plt.ylabel('weight')
    
    green_patch=mpatches.Patch(color='green', label='thin')
    red_patch=mpatches.Patch(color='red', label='fat')
    handles=[red_patch,green_patch]
    plt.legend(handles=handles)
    for i,x in enumerate(datas):
        if labels[i]=='thin':
            plt.scatter(x[0],x[1],s=100,marker='.',c='g')
        else:
            plt.scatter(x[0],x[1],s=100,marker='x',c='r')
    plt.show()


if __name__=='__main__':
    #获取数据集
    file='./data.csv'#data.csv : 身高,体重,标签
    datas,labels=read_from_csv(file)
    labels=list(labels)
    #新实例
    instance=[1.7,60]
    k=2
    #分类
    label=classify(instance,datas,labels,k)
    draw(datas,labels)
    print("knn classify : %s's label is %s"%(str(instance),label))

3.2运行结果

  • 后续进行优化处理

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI星球

机器学习 | 聚类分析总结 & 实战解析

聚类分析是没有给定划分类别的情况下,根据样本相似度进行样本分组的一种方法,是一种非监督的学习算法。聚类的输入是一组未被标记的样本,聚类根据数据自身的距离或相似度...

37420
来自专栏SnailTyan

ResNet论文翻译——中英文对照

Deep Residual Learning for Image Recognition Abstract Deeper neural networks are...

28980
来自专栏智能算法

KNN最近邻算法及其Python实现

k-NN是一种基本的分类和回归方法,用于分类时,算法思路较简单:通过计算不同特征之间的距离方法来得到最近的k个训练实例,根据k个实例的类别采用多数表决等方式进...

94470
来自专栏mwangblog

k-近邻算法

使用数据范围:数值型和标称型。 优点:精度高、对异常值不敏感、无数据输入假定。 缺点:计算复杂度高、空间复杂度高。

10620
来自专栏数据科学学习手札

(数据科学学习手札29)KNN分类的原理详解&Python与R实现

  KNN(k-nearst neighbors,KNN)作为机器学习算法中的一种非常基本的算法,也正是因为其原理简单,被广泛应用于电影/音乐推荐等方面,即有些...

536130
来自专栏鸿的学习笔记

Rolling and Unrolling RNNs

当输入序列被馈送到这样的网络中时,向后的箭头在稍后的步骤将关于早先输入值的信息反馈回系统。我没有在上篇文章中描述的一件事是如何训练这样的网络。所以在这篇文章中,...

15520
来自专栏人工智能LeadAI

pytorch入门教程 | 第三章:构造一个小型CNN

学过深度卷积网络的应该都非常熟悉这张demo图(LeNet): ? 此图是LeNet的结构图,把32*32的手写英文字符图片作为输入,训练出一个对于手写字符的分...

39170
来自专栏烂笔头

曲线点抽稀算法-Python实现

目录[-] 何为抽稀 在处理矢量化数据时,记录中往往会有很多重复数据,对进一步数据处理带来诸多不便。多余的数据一方面浪费了较多的存储空间,另一方面造成所要...

63160
来自专栏Python小屋

KNN分类算法原理与Python+sklearn实现根据身高和体重对体型分类

KNN算法是k-Nearest Neighbor Classification的简称,也就是k近邻分类算法。基本思路是在特征空间中查找k个最相似或者距离最近的样...

41870
来自专栏Pulsar-V

原-图像处理基础(二)图像的放大与缩小

最近邻插值法 ? 其中 size(g(x))代表图像像素矩阵列宽 size(g(y))代表图像像素矩阵行高 scale 代表缩放倍数 \begin{matr...

61370

扫码关注云+社区

领取腾讯云代金券