k近邻 机器学习 - CSDN
  • 1-1 机器学习算法分类 一、基本分类: ①监督学习(Supervised learning) 数据集中的每个样本有相应的“正确答案”, 根据这些样本做出 预测, 分有两类: 回归问题和分类问题。 步骤1: 数据集的创建和...

    1-1 机器学习算法分类

    一、基本分类:

    ①监督学习(Supervised learning)

    数据集中的每个样本有相应的“正确答案”, 根据这些样本做出
    预测, 分有两类: 回归问题和分类问题。

    步骤1: 数据集的创建和分类
    步骤2: 训练
    步骤3: 验证
    步骤4: 使用

    ( 1) 回归问题举例
    例如: 预测房价, 根据样本集拟合出一条连续曲线。
    ( 2) 分类问题举例
    例如: 根据肿瘤特征判断良性还是恶性,得到的是结果是“良性”或者“恶性”, 是离散的。

    监督学习:从给定的训练数据集中学习出一个函数(模型参数), 当新的数据到来时,可以根据这个函数预测结果。监督学习的训练集要求包括输入输出,也可以说是特征和目标。训练集中的目标是由人标注的。
    PCA和很多deep learning算法都属于无监督学习

    ②无监督学习

    无监督学习:输入数据没有被标记,也没有确定的结果。样本数据类别未知, 需要根据样本间的相似性对样本集进行分类(聚类, clustering)试图使类内差距最小化,类间差距最大化。
    实际应用中, 不少情况下无法预先知道样本的标签,也就是说没有训练样本对应的类别,因而只能从原先没有样本标签的样本集开始学习分器设计

    有监督学习 无监督学习
    样本 必须要有训练集与测试样本。在训练集中找规律,而对测试样本使用这种规律。 没有训练集,只有一组数据,在该组数据集内寻找规律。
    目标 方法是识别事物,识别的结果表现在给待识别数据加上了标签。 因此训练样本集必须由带标签的样本组成。 方法只有要分析的数据集的本身,预先没有什么标签。如果发现数据集呈现某种聚集性, 则可按自然的聚集性分类,但不予以某种预先分类标签对上号为目的。

    ③半监督学习

    半监督学习: 即训练集同时包含有标记样本数据和未标记样本数据。

    ④强化学习

    实质是: make decisions问题,即自动进行决策,并且可以做连续决策。
    主要包含四个元素: agent, 环境状态, 行动, 奖励;
    强化学习的目标就是获得最多的累计奖励。

    小结:

    监督学习:
    In:有标签
    Out:有反馈
    目的:预测结果
    案例:学认字
    算法:分类(类别),回归(数字)

    无监督学习:
    In:无标签
    Out:无反馈
    目的:发现潜在结构
    案例:自动聚类
    算法:聚类,降维

    半监督学习:
    已知:训练样本Data和待分类的类别
    未知:训练样本有无标签均可
    应用:训练数据量过时,
    监督学习效果不能满足需求,因此用来增强效果。

    强化学习:
    In:决策流程及激励系统
    Out:一系列行动
    目的:长期利益最大化,回报函数(只会提示你是否在朝着目标方向前进的延迟反映)
    案例:学下棋
    算法:马尔科夫决策,动态规划

    2-1 KNN基本流程

    一、概念:

    KNN(K Near Neighbor):k个最近的邻居,即每个样本都可以用它最接近的k个邻居来代表。
    这里写图片描述
    最近邻 (k-Nearest Neighbors, KNN) 算法是一种分类算法, 1968年由 Cover和 Hart 提出, 应用场景有字符识别、 文本分类、 图像识别等领域。
    该算法的思想是: 一个样本与数据集中的k个样本最相似, 如果这k个样本中的大多数属于某一个类别, 则该样本也属于这个类别。

    ###二、距离度量
    在选择两个实例相似性时,一般使用的欧式距离
    Lp距离定义:
    Lp(xi,xj)=(l=1nxi(l)xj(l)p)1pL_p(x_i, x_j) = \left( \sum_{l=1}^{n} | x_i^{(l)} - x_j^{(l)} |^p \right)^{\frac{1}{p}}
    其中xiRn,xjRnx_i \in \mathbf{R}^n,x_j \in \mathbf{R}^n, 其中L∞定义为:
    L(xi,xj)=maxlxi(l)xj(l)L_\infty(x_i, x_j) = \max_l|x_i^{(l)} - x_j^{(l)}|

    其中p是一个变参数。
    当p=1时,就是曼哈顿距离(对应L1范数)
    曼哈顿距离对应L1-范数,也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上,坐标(x1, y1)的点P1与坐标(x2, y2)的点P2的曼哈顿距离为:x1x2+y1y2|x_1-x_2|+|y_1-y_2|,要注意的是,曼哈顿距离依赖座标系统的转度,而非系统在座标轴上的平移或映射。
    曼哈顿距离:
    L1=k=1nx1kx2kL_1=\sum_{k=1}^n|x_{1k}-x_{2k}|
    L1范数表示为:
    L1x=i=1nxix=[x1x2xn]RnL_1定义为|x| = \sum_{i=1}^n| x_i|,其中x = \left[ \begin{matrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{matrix} \right] \in \mathbf{R}^n

    当p=2时,就是欧氏距离(对应L2范数)
    最常见的两点之间或多点之间的距离表示法,又称之为欧几里得度量,它定义于欧几里得空间中。n维空间中两个点x1(x11,x12,…,x1n)与 x2(x21,x22,…,x2n)间的欧氏距离
    欧氏距离:
    d12=k=1n(x1x2)2d_{12}=\sqrt{\sum_{k=1}^n(x_1-x_2)^2}

    L2范数:
    L2x=i=1nxi2x=[x1x2xn]RnL_2定义为|x| = \sqrt{ \sum_{i=1}^n x_i^2 },其中x = \left[ \begin{matrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{matrix} \right] \in \mathbf{R}^n

    当p→∞时,就是切比雪夫距离
    二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离:
    d12=max(x1x2,y1y2)d_{12}=max(|x_1-x_2|,|y_1-y_2|)
    n维空间点a(x11,x12,…,x1n)与b(x21,x22,…,x2n)的切比雪夫距离:
    d12=max(x1ix2i)d_{12}=max(|x_{1i}-x_{2i}|)

    ###三、k值选择
    如果选择较小的K值,就相当于用较小的邻域中的训练实例进行预测,学习的近似误差会减小,只有与输入实例较近的训练实例才会对预测结果起作用,单缺点是学习的估计误差会增大,预测结果会对近邻的实例点分成敏感。如果邻近的实例点恰巧是噪声,预测就会出错。换句话说,K值减小就意味着整体模型变复杂,分的不清楚,就容易发生过拟合。

    如果选择较大K值,就相当于用较大邻域中的训练实例进行预测,其优点是可以减少学习的估计误差,但近似误差会增大,也就是对输入实例预测不准确,K值得增大就意味着整体模型变的简单

    **近似误差:**可以理解为对现有训练集的训练误差。
    **估计误差:**可以理解为对测试集的测试误差。

    近似误差关注训练集,如果k值小了会出现过拟合的现象,对现有的训练集能有很好的预测,但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。

    估计误差关注测试集,估计误差小了说明对未知数据的预测能力好。模型本身最接近最佳模型。

    在应用中,K值一般取一个比较小的数值,通常采用交叉验证法来选取最优的K值。

    流程:
    1) 计算已知类别数据集中的点与当前点之间的距离
    2) 按距离递增次序排序
    3) 选取与当前点距离最小的k个点
    4) 统计前k个点所在的类别出现的频率
    5) 返回前k个点出现频率最高的类别作为当前点的预测分类

    优点:
    1、简单有效
    2、重新训练代价低
    3、算法复杂度低
    4、适合类域交叉样本
    5、适用大样本自动分类

    缺点:
    1、惰性学习
    2、类别分类不标准化
    3、输出可解释性不强
    4、不均衡性
    5、计算量较大

    例子如下图:
    距离越近,就越相似,属于这一类的可能性就越大
    这里写图片描述
    这里写图片描述

    import math
    
    movie_data = {"宝贝当家": [45, 2, 9, "喜剧片"],
                  "美人鱼": [21, 17, 5, "喜剧片"],
                  "澳门风云3": [54, 9, 11, "喜剧片"],
                  "功夫熊猫3": [39, 0, 31, "喜剧片"],
                  "谍影重重": [5, 2, 57, "动作片"],
                  "叶问3": [3, 2, 65, "动作片"],
                  "伦敦陷落": [2, 3, 55, "动作片"],
                  "我的特工爷爷": [6, 4, 21, "动作片"],
                  "奔爱": [7, 46, 4, "爱情片"],
                  "夜孔雀": [9, 39, 8, "爱情片"],
                  "代理情人": [9, 38, 2, "爱情片"],
                  "新步步惊心": [8, 34, 17, "爱情片"]}
    
    # 测试样本  唐人街探案": [23, 3, 17, "?片"]
    #下面为求与数据集中所有数据的距离代码:
    x = [23, 3, 17]
    KNN = []
    for key, v in movie_data.items():
        d = math.sqrt((x[0] - v[0]) ** 2 + (x[1] - v[1]) ** 2 + (x[2] - v[2]) ** 2)
        KNN.append([key, round(d, 2)])
    
    # 输出所用电影到 唐人街探案的距离
    print(KNN)
    
    #按照距离大小进行递增排序
    KNN.sort(key=lambda dis: dis[1])
    
    #选取距离最小的k个样本,这里取k=5;
    KNN=KNN[:5]
    print(KNN)
    
    #确定前k个样本所在类别出现的频率,并输出出现频率最高的类别
    labels = {"喜剧片":0,"动作片":0,"爱情片":0}
    for s in KNN:
        label = movie_data[s[0]]
        labels[label[3]] += 1
    labels =sorted(labels.items(),key=lambda l: l[1],reverse=True)
    print(labels,labels[0][0],sep='\n')
    

    代码和例子来自:https://blog.csdn.net/saltriver/article/details/52502253

    2-2 K值的选择

    一、近似误差与估计误差:
    近似误差:对现有训练集的训练误差,关注训练集,如果近似误差过小可能会出现过拟合的现象,对现有的训练集能有很好的预测,但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。
    估计误差:可以理解为对测试集的测试误差,关注测试集,估计误差小说明对未知数据的预测能力好,模型本身最接近最佳模型。
    二、K值确定标准:
    K值过小:k值小,特征空间被划分为更多子空间(模型的项越多),整体模型变复杂,容易发生过拟合,k值越小,选择的范围就比较小,训练的时候命中率较高,近似误差小,而用test的时候就容易出错,估计误差大,容易过拟合。
    K值=N:无论输入实例是什么,都将简单的预测他属于训练实例中最多的类。

    2-3 kd树

    一、原理:

    kd树(K-dimension tree)是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。 kd树是是一种二叉树,表示对k维空间的一个划分,构造kd树相当于不断地用垂直于坐标轴的超平面将K维空间切分,构成一系列的K维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。 利用kd树可以省去对大部分数据点的搜索, 从而减少搜索的计算量。

    一个三维k-d树。 第一次划分(红色)把根节点(白色)划分成两个节点,然后它们分别再次被划分(绿色) 为两个子节点。最后这四个子节点的每一个都被划分(蓝色) 为两个子节点。 因为没有更进一步的划分, 最后得到的八个节点称为叶子节点
    这里写图片描述
    类比“二分查找”: 给出一组数据: [9 1 4 7 2 5 0 3 8], 要查找8。如果挨个查找(线性扫描),那么将会把数据集都遍历一遍。而如果排一下序那数据集就变成了: [0 1 2 3 4 5 6 7 8 9], 按前一种方式我们进行了很多没有必要的查找, 现在如果我们以5为分界点, 那么数据集就被划分为了左右两个“簇” [0 1 2 3 4]和[6 7 8 9]。

    因此, 根本久没有必要进入第一个簇,可以直接进入第二个簇进行查找。把二分查找中的数据点换成k维数据点, 这样的划分就变成了用超平面对k维空间的划分。空间划分就是对数据点进行分类, “挨得近”的数据点就在一个空间里面。

    二、构造方法:

    第一个问题简单的解决方法可以是选择随机选择某一维或按顺序选择,但是更好的方法应该是在数据比较分散的那一维进行划分(分散的程度可以根据方差来衡量)。好的划分方法可以使构建的树比较平衡, 可以每次选择中位数来进行划分, 这样问题2也得到了解决。
    这里写图片描述
    代码实现:

    # -*- coding: utf-8 -*-
    
    #from operator import itemgetter
    import sys
    reload(sys)
    sys.setdefaultencoding('utf8')
    
    
    # kd-tree每个结点中主要包含的数据结构如下 
    class KdNode(object):
        def __init__(self, dom_elt, split, left, right):
            self.dom_elt = dom_elt  # k维向量节点(k维空间中的一个样本点)
            self.split = split      # 整数(进行分割维度的序号)
            self.left = left        # 该结点分割超平面左子空间构成的kd-tree
            self.right = right      # 该结点分割超平面右子空间构成的kd-tree
     
     
    class KdTree(object):
        def __init__(self, data):
            k = len(data[0])  # 数据维度
            
            def CreateNode(split, data_set): # 按第split维划分数据集exset创建KdNode
                if not data_set:    # 数据集为空
                    return None
                # key参数的值为一个函数,此函数只有一个参数且返回一个值用来进行比较
                # operator模块提供的itemgetter函数用于获取对象的哪些维的数据,参数为需要获取的数据在对象中的序号
                #data_set.sort(key=itemgetter(split)) # 按要进行分割的那一维数据排序
                data_set.sort(key=lambda x: x[split])
                split_pos = len(data_set) // 2      # //为Python中的整数除法
                median = data_set[split_pos]        # 中位数分割点             
                split_next = (split + 1) % k        # cycle coordinates
                
                # 递归的创建kd树
                return KdNode(median, split, 
                              CreateNode(split_next, data_set[:split_pos]),     # 创建左子树
                              CreateNode(split_next, data_set[split_pos + 1:])) # 创建右子树
                                    
            self.root = CreateNode(0, data)         # 从第0维分量开始构建kd树,返回根节点
    
    
    # KDTree的前序遍历
    def preorder(root):  
        print root.dom_elt  
        if root.left:      # 节点不为空
            preorder(root.left)  
        if root.right:  
            preorder(root.right)  
          
          
    if __name__ == "__main__":
        data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
        kd = KdTree(data)
        preorder(kd.root)
    
    展开全文
  • interactiveknn, 基于JavaScript的交互式K 近邻机器学习算法 基于的交互式k 近邻用k 近邻算法与浏览器中的点进行视觉上的交互以对未知点进行分类。可以在 Lettier.com 播放。开始git clone git@github....
  • k近邻(k-Nearest Neighbor 简称KNN)学习是一种常用的监督学习算法,给定一个测试样本,基于某种距离度量来找出训练集的所有样本中与该样本最为靠近的k个样本,然后根据这k个邻居的信息进行预测。 什么时候用到KNN...

    介绍

    k近邻(k-Nearest Neighbor 简称KNN)学习是一种常用的监督学习算法,给定一个测试样本,基于某种距离度量来找出训练集的所有样本中与该样本最为靠近的k个样本,然后根据这k个邻居的信息进行预测。

    什么时候用到KNN?

    knn算法既能够处理分类任务也能进行回归分析,两种任务所采用的方法略有不同。

    • 分类任务:通常使用“投票法”,将选择出的k个邻居样本出现最多的类别标记作为最终的预测结果。
    • 回归任务:使用“平均法”,测试样本的最终输出为k个邻居样本的实值输出标记的平均值;或者按照加权平均的方式求得,距离越近,权重越大。

    KNN是如何工作的?

    KNN算法是懒惰学习的代表,因为它没有显示的训练过程。KNN算法是基于特征相似度的,因此确定K值是整个KNN算法的重中之重。下面举个例子说明KNN的预测过程。


    优缺点分析

    pros

    • 能够承担多任务,即可分类又可回归。
    • 可解释性极强,算法逻辑通俗易懂。
    • 整个预测过程的周期较短。

    cons

    • 计算成本十分昂贵,由于算法保留了所有的训练数据。
    • 高存储的要求。
    • 对于数据的规模和非相关的特征来说十分敏感。

    参考

    《机器学习》- 周志华

    Introduction to k-Nearest Neighbors: Simplified (with implementation in Python)

    A Quick Introduction to K-Nearest Neighbors Algorithm

     

    展开全文
  • 机器学习k近邻

    2017-12-08 16:54:32
    核心思想KNN算法假设给定的训练集中的实例都已经分好类了,对于新的实例,根据离它最近的k个训练实例的类别来预测它的类别。即这k个实例大多数属于某个类别则该实例就属于某个类别。比如k为5,离新实例a最近的5个...

    核心思想

    KNN算法假设给定的训练集中的实例都已经分好类了,对于新的实例,根据离它最近的k个训练实例的类别来预测它的类别。即这k个实例大多数属于某个类别则该实例就属于某个类别。比如k为5,离新实例a最近的5个样本的情况为,3个样本属于A类,1个样本属于B类,一个样本属于C类,那么新实例a属于A类。

    这里写图片描述

    常用距离

    • 欧氏距离
      d(x,y)=ni=1(xiyi)2
    • 曼哈顿距离
      d(x,y)=ni=1|(xiyi)|
    • 切比雪夫距离
      d(x,y)=max(|xiyi|)

    这里写图片描述

    k值的影响

    k值的选取可能会影响到分类结果,如下图,k=3和k=5时的分类结果是不同的。

    这里写图片描述

    1. k值小可能会导致预测结果对近邻的样本点敏感,如果刚好是噪音则会导致预测结果出错,容易发生过拟合。近似误差小,估计误差大。
    2. k值大可能会导致较远的样本也影响预测,也可能会导致预测错误。近似误差大,估计误差小。
    3. k值一般先取较小的数,再用交叉验证方法选择最优k值。

    算法实现

    两种方式:线性扫描和kd树。

    线性扫描

    KNN的最简单朴素的方法即直接线性扫描,大致步骤如下:
    1. 计算待预测数据与各训练样本之间的距离;
    2. 按照距离递增排序;
    3. 选择距离最小的k个点;
    4. 计算这k个点类别的频率,最高的即为待预测数据的类别。

    代码实现

    from numpy import *
    import pylab as pl
    
    dataSet = array([[11, 12], [12, 12], [11, 11], [11, 16], [12, 16], [17, 11], [17, 12]])
    classes = ['A', 'A', 'A', 'B', 'B', 'C', 'C']
    k = 3
    dot = [13, 13]
    type
    r = 0
    dataSize = dataSet.shape[0]
    diff = tile(dot, (dataSize, 1)) - dataSet
    sqdiff = diff ** 2
    squareDist = sum(sqdiff, axis=1)
    dist = squareDist ** 0.5
    sortedDistIndex = argsort(dist)
    classCount = {}
    for i in range(k):
        label = classes[sortedDistIndex[i]]
        classCount[label] = classCount.get(label,0) + 1
        if dist[i] > r:
            r = dist[i]
    maxCount = 0
    for key, value in classCount.items():
        if value > maxCount:
            maxCount = value
            type = key
    pl.plot(dot[0], dot[1], 'ok')
    circle = [i*pi/180 for i in range(0,360)]
    x = cos(circle)*r+dot[0]
    y = sin(circle)*r+dot[1]
    pl.plot(x, y, 'r')
    pl.plot([point[0] for point in dataSet[0:3]], [point[1] for point in dataSet[0:3]], 'og')
    pl.plot([point[0] for point in dataSet[3:5]], [point[1] for point in dataSet[3:5]], 'or')
    pl.plot([point[0] for point in dataSet[5:7]], [point[1] for point in dataSet[5:7]], 'oy')
    pl.show()
    

    这里写图片描述

    kd树

    线性扫描非常耗时,为了减少计算距离的次数提高效率,使用kd树方法,它能快速地找到查询点近邻。

    可以通过将搜索空间进行层次划分建立索引树以加快检索速度。

    对于二维空间,它最终要划分的空间类似如下,

    这里写图片描述

    决定在哪个维度上进行分割是由所有数据在各个维度的方差决定的,方差越大说明该维度上的数据波动越大,更应该再该维度上对点进行划分。例如x维度方差较大,所以以x维度方向划分。

    分割时一般取分割维度上的所有值的中值的点,比如下图,第一次计算方差较大的维度为x维度,中值点为A,以x=Ax分割,接着对分割后的点分别又继续分割,计算方差并寻找中值,以y=Cy、y=By分割,以此类推。

    这里写图片描述

    kd树查找

    从根节点开始查找,直到叶子节点,整个过程将最短距离d和相应的点记录下来。

    回溯,通过计算待预测的点到分割平面的距离l与最短距离d比较,看是否要进入节点的相邻空间去查找。回溯的过程是为了确认是否有必要进入相邻子空间去搜索,当待预测点到最近点的距离d大于待预测点到分割面的距离l时,则需要到相邻子空间查找,否则则没必要,直接往上一层回溯。

    ========广告时间========

    公众号的菜单已分为“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等,可能有一款适合你的胃口。

    鄙人的新书《Tomcat内核设计剖析》已经在京东销售了,有需要的朋友可以购买。感谢各位朋友。

    为什么写《Tomcat内核设计剖析》

    =========================
    欢迎关注:

    这里写图片描述

    展开全文
  • K最近邻(k-Nearest Neighbor,KNN),是一种常用于分类的算法,是有成熟理论支撑的、较为简单的经典机器学习算法之一。该方法的基本思路是:如果一个待分类样本在特征空间中的k个最相似(即特征空间中K近邻)的样本中的...

    K最近邻(k-Nearest Neighbor,KNN),是一种常用于分类的算法,是有成熟理论支撑的、较为简单的经典机器学习算法之一。该方法的基本思路是:如果一个待分类样本在特征空间中的k个最相似(即特征空间中K近邻)的样本中的大多数属于某一个类别,则该样本也属于这个类别,即近朱者赤,近墨者黑。显然,对当前待分类样本的分类,需要大量已知分类的样本的支持,因此KNN是一种有监督学习算法。


    k-最近邻算法是基于实例的学习方法中最基本的,先介绍基于实例学习的相关概念。

    一、基于实例的学习

    1. 已知一系列的训练样例,很多学习方法为目标函数建立起明确的一般化描述;但与此不同,基于实例的学习方法只是简单地把训练样例存储起来。
      从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例,它分析这个新实例与以前存储的实例的关系,并据此把一个目标函数值赋给新实例。
    2. 基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上,很多技术只建立目标函数的局部逼近,将其应用于与新查询实例邻近的实例,而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂,但它可用不太复杂的局部逼近描述时,这样做有显著的优势。
    3. 基于实例方法的不足
      • 分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时,而不是在第一次遇到训练样例时。所以,如何有效地索引训练样例,以减少查询时所需计算是一个重要的实践问题。
      • 当从存储器中检索相似的训练样例时,它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时,那么真正最“相似”的实例之间很可能相距甚远。

    二、k-最近邻法算法简介

            K最近邻(K-Nearest Neighbor,KNN)算法,是著名的模式识别统计学方法,在机器学习分类算法中占有相当大的地位。它是一个理论上比较成熟的方法。既是最简单的机器学习算法之一,也是基于实例的学习方法中最基本的,又是最好的文本分类算法之一。

           如果你要了解一个人,可以从他k个最亲近的朋友去推测他是什么样的人。k是一个超参数。k表示最近的k个邻居,是表示个数,不是表示距离。

    超参数k的作用:

                           

                            左图中“?”处绿点是一个待分类的样本,
                            也就是说“?”到底是红色三角形,还是
                            蓝色正方形,暂时还不知道。
                            若令k=3,则“?”被分类为红色三角形。
                            若令k=5,则“?”被分类蓝色正方形。

     

    超参数k对算法的影响:

          k越大,就需要找出越多的邻居,计算量越大。K越大,则相当于做分类时的样本数越多,所以统计意义会更强。但是,如果这k个邻居离待分类样本太远的话,则统计意义就反而变弱了。所以,实践中不宜把k值取得太大。

    K值的选择:(借鉴李航--统计学习方法)

    K值的选择会对K近邻算法的结果产生重大的影响。

    K值较小:就相当于用较小的领域中的训练实例进行预测,“学习”近似误差会减小K值的减小就意味着整体模型变得复杂,容易发生过拟合; 

    K值较大:就相当于用较大领域中的训练实例进行预测,其优点是可以减少学习的估计误差,但缺点是学习的近似误差会增大。这时候,与输入实例较远(不相似的)训练实例也会对预测器作用,使预测发生错误,且K值的增大就意味着整体的模型变得简单。k很大,那么可以减少干扰数据的影响,但是此时就导致了系统性偏差(K值太小会造成过度拟合),比如如果取k为总的训练数据数,那么每次投票肯定都是训练数据中多的类别胜利。显然训练数据的系统性偏差会影响结果。 

    通常情况下,我们需要对 k 经过多种尝试,来决定到底使用多大的 k 来作为最终参数。k通常会在3~10直接取值,或者是k等于训练数据的平方根。比如15个数据,可能会取k=4。 

    在实际应用中,一般采用交叉验证法(简单来说,就是一部分样本做训练集,一部分做测试集)来选择最优的K值。 

    三、K近邻算法的原理

    首先,K近邻算法的推导实在是过于简单,这里就只描述下算法的设计流程。

    kNN分类算法的具体步骤如下:
    1)计算待分类样本点与所有已标注样本点之间的距离(如果样本多将非常耗时、耗空间)
    2)按照距离从小到大排序(对于每一个待分类的样本点,都要排序。耗时、耗空间)
    3)选取与待分类样本点距离最小的k个点
    4)确定前k个点中,每个类别的出现次数
    5)返回次数最高的那个类别

    这里要注意,距离的计算方法。

    由于sklearn中有现成的算法,这里根据算法中的参数来进行说明,我们使用sklearn.neighbors.KNeighborsClassifier就可以是实现上小结,我们实现的k-近邻算法。

    KNeighborsClassifier函数一共有8个参数

    class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5weights='uniform'algorithm='auto'leaf_size=30p=2

    metric='minkowski'metric_params=Nonen_jobs=1**kwargs)

    KNneighborsClassifier参数说明:

    • n_neighbors:默认为5,就是k-NN的k的值,选取最近的k个点。
    • weights:默认是uniform,参数可以是uniform、distance,也可以是用户自己定义的函数。uniform是均等的权重,就说所有的邻近点的权重都是相等的distance是不均等的权重,距离近的点比距离远的点的影响大。用户自定义的函数,接收距离的数组,返回一组维数相同的权重。
    • algorithm:快速k近邻搜索算法,默认参数为auto,可以理解为算法自己决定合适的搜索算法。除此之外,用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索brute是蛮力搜索,也就是线性扫描当训练集很大时,计算非常耗时kd_tree,构造kd树存储数据以便对其进行快速检索的树形数据结构,kd树也就是数据结构中的二叉树。以中值切分构造的树,每个结点是一个超矩形,在维数小于20时效率高ball tree是为了克服kd树高纬失效而发明的,其构造过程是以质心C和半径r分割样本空间,每个节点是一个超球体。
    • leaf_size:默认是30,这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度,同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。
    • metric:用于距离度量,默认度量是minkowski,也就是p=2的欧氏距离(欧几里德度量)。
    • p:距离度量公式。在上小结,我们使用欧氏距离公式进行距离度量。除此之外,还有其他的度量方法,例如曼哈顿距离。这个参数默认为2,也就是默认使用欧式距离公式进行距离度量。也可以设置为1,使用曼哈顿距离公式进行距离度量。
    • metric_params:距离公式的其他关键参数,这个可以不管,使用默认的None即可。
    • n_jobs:并行处理设置。默认为1,临近点搜索并行工作数。如果为-1,那么CPU的所有cores都用于并行工作。

    闵可夫斯基距离:minkowski

    闵可夫斯基距离(Minkowski distance)是衡量数值点之间距离的一种非常常见的方法,假设数值点 P 和 Q 坐标如下:

    那么,闵可夫斯基距离定义为:

    该距离最常用的 p 是 2 和 1, 前者是欧几里得距离(Euclidean distance),后者是曼哈顿距离(Manhattan distance)。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点,白色表示高楼大厦,灰色表示街道:

    绿色的斜线表示欧几里得距离,在现实中是不可能的。其他三条折线表示了曼哈顿距离,这三条折线的长度是相等的。

    其中,在计算距离的过程中,有几下几点需要特别注意:

    • 对于类别性变量,在计算之前需要先进行独热编码,转化为距离计算可以理解的数字型变量
    • 对于连续性变量,可以进行无量纲化的处理。

    四、KNN算法实现

    4.1 KNN算法蛮力实现

    首先我们看看最想当然的方式。

           既然我们要找到k个最近的邻居来做预测,那么我们只需要计算预测样本和所有训练集中的样本的距离,然后计算出最小的k个距离即可,接着多数表决,很容易做出预测。这个方法的确简单直接,在样本量少,样本特征少的时候有效。但是在实际运用中很多时候用不上,为什么呢?因为我们经常碰到样本的特征数有上千以上,样本量有几十万以上,如果我们这要去预测少量的测试集样本,算法的时间效率很成问题。因此,这个方法我们一般称之为蛮力实现。比较适合于少量样本的简单模型的时候用

       既然蛮力实现在特征多,样本多的时候很有局限性,那么我们有没有其他的好办法呢?有!这里我们讲解两种办法,一个是KD树实现,一个是球树实现。

    4.2 KD树实现原理

           KD树算法没有一开始就尝试对测试样本分类,而是先对训练集建模建立的模型就是KD树建好了模型再对测试集做预测。所谓的KD树就是K个特征维度的树,注意这里的K和KNN中的K的意思不同。KNN中的K代表特征输出类别,KD树中的K代表样本特征的维数。为了防止混淆,后面我们称特征维数为n。

      KD树算法包括三步,第一步是建树,第二部是搜索最近邻,最后一步是预测

    KD树的建立:

       我们首先来看建树的方法。KD树建树采用的是从m个样本的n维特征中,分别计算n个特征的取值的方差,用方差最大的第k维特征n_{k}来作为根节点。对于这个特征,我们选择特征n_{k}的取值的中位数n_{kv}对应的样本作为划分点,对于所有第k维特征的取值小于n_{kv}的样本,我们划入左子树,对于第k维特征的取值大于等于nkvnkv的样本,我们划入右子树,对于左子树和右子树,我们采用和刚才同样的办法来找方差最大的特征来做根节点递归的生成KD树。

    比如我们有二维样本6个,{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},构建kd树的具体步骤为:

       1)找到划分的特征。6个数据点在x,y维度上的数据方差分别为6.97,5.37,所以在x轴上方差更大,用第1维特征建树。

       2)确定划分点(7,2)。根据x维上的值将数据排序,6个数据的中值(所谓中值,即中间大小的值)为7,所以划分点的数据是(7,2)。这样,该节点的分割超平面就是通过(7,2)并垂直于:划分点维度的直线x=7;(很显然,中位数为6 ,这里选择(5,4)或者(7,2)都是可以的。这种情况任选一个即可)

       3)确定左子空间和右子空间。 分割超平面x=7将整个空间分为两部分:x<=7的部分为左子空间,包含3个节点={(2,3),(5,4),(4,7)};另一部分为右子空间,包含2个节点={(9,6),(8,1)}。

       4)用同样的办法划分左子树的节点{(2,3),(5,4),(4,7)}和右子树的节点{(9,6),(8,1)}。最终得到KD树。

        最后得到的KD树如下:

    KD树搜索最近邻

          当我们生成KD树以后,就可以去预测测试集里面的样本目标点了。对于一个目标点,我们首先在KD树里面找到包含目标点的叶子节点。目标点为圆心,以目标点到叶子节点样本实例的距离为半径,得到一个超球体最近邻的点一定在这个超球体内部。然后返回叶子节点的父节点,检查另一个子节点包含的超矩形体是否和超球体相交,如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。如果不相交那就简单了,我们直接返回父节点的父节点,在另一个子树继续搜索最近邻。当回溯到根节点时,算法结束,此时保存的最近邻节点就是最终的最近邻。

       从上面的描述可以看出,KD树划分后可以大大减少无效的最近邻搜索,很多样本点由于所在的超矩形体和超球体不相交,根本不需要计算距离。大大节省了计算时间。

      我们用3.1建立的KD树,来看对点(2,4.5)找最近邻的过程。

      先进行二叉查找,先从(7,2)查找到(5,4)节点,在进行查找时是由y = 4为分割超平面的,由于查找点为y值为4.5,因此进入右子空间查找到(4,7),形成搜索路径<(7,2),(5,4),(4,7)>,但 (4,7)与目标查找点的距离为3.202,而(5,4)与查找点之间的距离为3.041,所以(5,4)为查询点的最近点; 以(2,4.5)为圆心,以3.041为半径作圆,如下图所示。可见该圆和y = 4超平面交割,所以需要进入(5,4)左子空间进行查找,也就是将(2,3)节点加入搜索路径中得<(7,2),(2,3)>;于是接着搜索至(2,3)叶子节点,(2,3)距离(2,4.5)比(5,4)要近,所以最近邻点更新为(2,3),最近距离更新为1.5;回溯查找至(5,4),直到最后回溯到根结点(7,2)的时候,以(2,4.5)为圆心1.5为半径作圆,并不和x = 7分割超平面交割,如下图所示。至此,搜索路径回溯完,返回最近邻点(2,3),最近距离1.5。

    对应的图如下:

    4.3 球树实现原理

           KD树算法虽然提高了KNN搜索的效率,但是在某些时候效率并不高,比如当处理不均匀分布的数据集时,不管是近似方形,还是矩形,甚至正方形,都不是最好的使用形状,因为他们都有角。一个例子如下图:

             如果黑色的实例点离目标点星点再远一点,那么虚线圆会如红线所示那样扩大,导致与左上方矩形的右下角相交,既然相 交了,那么就要检查这个左上方矩形,而实际上,最近的点离星点的距离很近,检查左上方矩形区域已是多余。于此我们看见,KD树把二维平面划分成一个一个矩形,但矩形区域的角却是个难以处理的问题。

      为了优化超矩形体导致的搜索效率的问题,牛人们引入了球树,这种结构可以优化上面的这种问题。

      我们现在来看看球树建树和搜索最近邻的算法。

    球树的建立

    球树,顾名思义,就是每个分割块都是超球体,而不是KD树里面的超矩形体。

    我们看看具体的建树流程:

      1) 先构建一个超球体,这个超球体是可以包含所有样本的最小球体。

      2) 从球中选择一个离球的中心最远的点,然后选择第二个点离第一个点最远,将球中所有的点分配到离这两个聚类中心最近的一个上,然后计算每个聚类的中心,以及聚类能够包含它所有数据点所需的最小半径。这样我们得到了两个子超球体,和KD树里面的左右子树对应。(PS:这里选择两个点后,就以这两个点来聚类,所以先确定的是以这两个点为中心来计算其他点到该中心的距离。当所有点都确定自己的中心后,再重新计算一次该超球体的半径和球心。

        3)对于这两个子超球体,递归执行步骤2). 最终得到了一个球树。

        可以看出KD树和球树类似,主要区别在于球树得到的是节点样本组成的最小超球体,而KD得到的是节点样本组成的超矩形体,这个超球体要与对应的KD树的超矩形体小,这样在做最近邻搜索的时候,可以避免一些无谓的搜索。

    五、KNN算法小结

      KNN算法是很基本的机器学习算法了,它非常容易学习,在维度很高的时候也有很好的分类效率,因此运用也很广泛,这里总结下KNN的优缺点。

      KNN的主要优点有:

      1) 理论成熟,思想简单,既可以用来做分类也可以用来做回归

      2) 可用于非线性分类

      3) 训练时间复杂度比支持向量机之类的算法低,仅为O(n)

      4) 和朴素贝叶斯之类的算法比,对数据没有假设,准确度高,对异常点不敏感

      5) 由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合

      6)该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分

      KNN的主要缺点有:

      1)计算量大,尤其是特征数非常多的时候

      2)样本不平衡的时候,对稀有类别的预测准确率低

      3)KD树,球树之类的模型建立需要大量的内存

      4)使用懒散学习方法,基本上不学习,导致预测时速度比起逻辑回归之类的算法慢

      5)相比决策树模型,KNN模型可解释性不强

    六、适用场合

    1. kNN是一个有监督算法,需要有标注好的样本。
    2. 从算法复杂度的角度来看,更适合特征个数较少,已标注样本数量不是过多的场合。
    3. kNN的可解释性较差。无法给出决策树那样的规则,也无法象逻辑回归那样对数据给出整齐的划分。事实上,kNN更适合处理一些分类规则相对复杂的问题。

    参考资料:

    https://blog.csdn.net/qq_36330643/article/details/77532161

    http://cuijiahua.com/blog/2017/11/ml_1_knn.html

    https://www.cnblogs.com/pinard/p/6061661.html

     

    展开全文
  • 本篇主要是自己复习和总结机器学习算法中最基础入门的——k近邻(KNN)算法,内容由网上百度与摘抄唐宇迪老师的讲义。 k近邻介绍 k近邻参数 官网例子 k近邻实际应用 房租价格预测 k...
  •     k近邻法(k-nearest neighbor, kNN)是一种基本分类与回归方法,其基本做法是:给定测试实例,基于某种距离度量找出训练集中与其最靠近的k个实例点,然后基于这k个最近邻的信息来进行预测。     通常,...
  • 机器学习k近邻算法

    2018-02-11 10:42:42
    毕业10年,回过头看线性代数,全部还给了老师。翻看《Machine Learning in Action》做做笔记 1 欧式距离计算 # -*- coding: utf-8 -*- ''' Created on 2017年10月27日 @author: dzm ...from numpy import array, ...
  • k近邻法(K-NN)是一种基本的分类与回归方法。分类时,对新的实例,根据k个最近邻的训练实例的类别,通过多数表决等方式进行预测。k近邻的三要素:k值的选择、距离度量以及分类决策规则。k近邻算法简单、直观,给定...
  • 机器学习算法与Python实践之(一)k近邻(KNN)zouxy09@qq.comhttp://blog.csdn.net/zouxy09 机器学习算法与Python实践这个系列主要是参考《机器学习实战》这本书。因为自己想学习Python,然后也想对一些机器学习...
  • K近邻学习笔记

    2016-11-16 19:49:15
    但个人并不把它列入到机器学习中的学习算法,它本身并没有对数据进行理论建模的过程,而是根据现有的数据在n维空间的分布,来确定预测点的归属。这就好比,在现实世界的维度中,经常游走于男厕所的我们归为男性,而...
  • 机器学习实战 K近邻算法 1.前言 k近邻是一种基本分类与回归方法。k近邻法的输入为实例的特征向量,对应于特征空间的点,输出为实例的类别,可以取多类。k近邻法假设给定一个训练数据集,其中的实例类别已定。分类...
  • 参考文献:机器学习与数据挖掘参考文献 k近邻法是一种基本分类与回归方法。k近邻算法简单、直观:给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最近邻的k个实例,这k个实例的多数属于某个类,...
  • 理论部分与“机器学习算法与python实践:k近邻(kNN)”这篇博文相同,实践数据也相同,差别为代码部分为作者用Matlab重新编写。 最近开始学习机器学习,理论部分主要参考周志华老师的《机器学习》这本书,实践部分...
  •  K-近邻算法是一种易于理解的机器学习算法,它的工作原理是:存在一个样本数据集合,并且样本中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征...
  • 机器学习实战》-Ch2-k-近邻算法-源代码,笔记链接见:https://blog.csdn.net/qq_34243930/article/details/84948770
  • K近邻算法(KNN)(最简单易懂的机器学习算法,没有之一)一、定义 存在一个样本数据集合,也称作为训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签...
  • 可能有人会说,K近邻模型有什么好写的,那分明就是一个最简单的机器学习模型,哦,不,连机器学习也算不上的算法吧。但是这里,我想提醒的是,我们要讨论的,不仅仅是简单的K近邻模型,而是和它相关的一些有困惑的...
  • K近邻算法学习总结

    2017-11-28 21:42:59
    K近邻算法的学习总结本篇文章主要描述了K近邻算法的基本思路,实现原理,算法特征以及适用范围和可优化点,文章为本人学习后的感悟,仅供参考。 基本思路 实现原理 欧式距离 算法特征 适用范围 算法优化 算法案例 ...
  • 本文主要介绍K近邻(KNN)模型,KNN在机器学习中是很常见的: 1、KNN模型介绍 2、KNN数学原理 3、算法及Python实现 4、小结 1、KNN模型介绍 k近邻法(k-nearest neighbor, k-NN)是一种基于分类与回归方法,...
1 2 3 4 5 ... 20
收藏数 15,262
精华内容 6,104
热门标签
关键字:

k近邻 机器学习