knn机器学习_机器学习 knn - CSDN
  •  KNN算法的原理就是,存在一个训练样本集,我们知道样本集中每一数据与其所属分类的对应关系,然后输入没有标签的新数据,我们可以通过将它的特征与样本集中数据的特征进行比较,提取样本中最相似的分类标签,一般....

     预测电影类型

        现有爱情片和动作片(不是爱情动作片,雾)的打斗场面和接吻场面的次数统计,然后给出一个电影打斗场面和接吻场面出现的次数,预测其类型。


    那么如何预测呢?当然用KNN了。

            KNN算法的原理就是,存在一个训练样本集,我们知道样本集中每一数据与其所属分类的对应关系,然后输入没有标签的新数据,我们可以通过将它的特征与样本集中数据的特征进行比较,提取样本中最相似的分类标签,一般提取前K个,k通常不大于20。简单地说就是计算它与样本集中哪些数据最相似,将抽象的相似性用距离可视化,可计算化,选取前K个最相似的标签。

    代码:

    from numpy import *
    import operator
    import matplotlib
    import matplotlib.pyplot as plt
    
    #样本训练集
    def createDataSet():
        group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
        labels=['A','A','B','B']
        return group,labels
    
    #inx:测试集,dataset:训练集,labels:标签,k:选取前k个
    def classify0(inx,dataSet,labels,k):
        dataSetSize=dataSet.shape[0] #dataset的行数
        # tile函数将inx变成datasetsize行,1列的矩阵,做差之后矩阵即为
        #[[xi-x0,yi-y0],..[xi-xd,yi-yd]]
        diffMat=tile(inx,(dataSetSize,1))-dataSet
        #矩阵每个元素都平方
        sqDiffMat=diffMat**2
        #axis=1表示按行加,0表示按列加
        sqDistances=sqDiffMat.sum(axis=1)
        #开方求距离
        distances=sqDistances**0.5
        #argsort()返回数组从小到大的索引值
        sortedDistIndicies=distances.argsort()
        classCount={}
        for i in range(k):
            #选取前k个,voteIlbale表示距离从前往后的标签
            voteIlbale=labels[sortedDistIndicies[i]]
            #统计标签出现的次数
            classCount[voteIlbale]=classCount.get(voteIlbale,0)+1
            #按照标签出现的次数排序,反向排序
            sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
            #返回出现次数最多的标签
            return sortedClassCount[0][0]

    展开全文
  • 机器学习中的KNN算法

    2019-05-06 10:25:32
    文章目录机器学习中的KNN算法一.KNN的简单介绍二.KNN的原理关注菜鸟解说大数据 机器学习中的KNN算法 一.KNN的简单介绍   KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别...

    微信公众号:关注菜鸟解说大数据
    关注可了解更多的大数据相关的内容。问题或建议,请公众号留言,或者可以浏览我的CSDN
    如果你觉得我写的文章对你有帮助,欢迎关注和赞赏我

    机器学习中的KNN算法

    一.KNN的简单介绍

      KNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。机器学习入门的第一个算法是k-近邻算法(KNN),它的工作原理是:存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般来说,我们只选择样本数据集中前k个最相似的数据,这就是k-近邻算法中k的出处,通常k是不大于20的整数。最后,选择k个最相似数据中出现次数最多的分类,作为新数据的分类。由此也说明了KNN算法的结果很大程度取决于K的选择。

    二.KNN的原理

    在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离:
    欧氏距离:
    欧氏距离
    曼哈顿距离:
    曼哈顿距离
    同时,KNN通过依据k个对象中占优的类别进行决策,而不是单一的对象类别决策。这两点就是KNN算法的优势。接下来对KNN算法的思想总结一下:就是在训练集中数据和标签已知的情况下,输入测试数据,将测试数据的特征与训练集中对应的特征进行相互比较,找到训练集中与之最为相似的前K个数据,则该测试数据对应的类别就是K个数据中出现次数最多的那个分类,其算法的描述为:

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

    关注菜鸟解说大数据

    如果你觉得到作者的文章对你有帮助,欢迎赞赏,有你的支持,公众号一定会越来越好!
    公众号二维码

    展开全文
  • https://mp.csdn.net/mdeditor/85250661 使用Knn完成验证码识别,环境是python3+jupyter notebook。做完这个就会对knn有深入的理解
  •  关于实现车牌定位和字符分割的算法,大家可以去网上找相关的论文,本文的重点是介绍利用机器学习KNN算法实现简单的字符识别。 KNN算法全称k-NearestNeighbor,是机器学习分类领域最简单的算法之一。它的主要...

      小编的毕业设计做的就是车牌识别系统,主要包含车牌定位、字符分割、车牌识别模块。先附上做的系统界面图。



      关于实现车牌定位和字符分割的算法,大家可以去网上找相关的论文,本文的重点是介绍利用机器学习的KNN算法实现简单的字符识别。


      KNN算法全称k-NearestNeighbor,是机器学习分类领域最简单的算法之一。它的主要思想是将待预测的样本和已知分类的样本集中每一个样本进行“距离计算”,选择前K个“距离”最短的样本,在这K个样本中,分类次数出现最多的那个分类就被视为待预测样本的所属分类。


      “距离计算”因样本而不同,车牌字符识别中的样本当然是字符图像。每一张字符图像都是长宽相同的二值图像,本文是16*32的二值图像。这样每一张字符图像都和16*32的二维数组一一对应,并且数组的取值只能为0或1。为了方便比较,我们将16*32的二维数组排成长度为512的一维数组,则“距离计算”的公式如下。

                             

      其中xi为待识别字符图像对应的一维数组的第i个值,xki为字符样本集第k个样本对应的一维数组的第i个值。


      本文的字符集包含了省份简称、英文字母、数字,一共有3500张图像。其中英文字符“A”的所有图像如下。




      KNN算法有一个很明显的缺点就是要想预测样本的分类,就要把样本和已知分类的样本集中的所有样本进行比较,这样算法的时间复杂度就比较高。还有算法的实际效果很大程度上也取决于已知分类的样本集质量。本文系统的字符识别的正确率只有80%左右,并且每次都要等待大约6、7秒才出结果。


      车牌字符识别算法目前已经很成熟了,大家如果有兴趣,可以在网上找一找大牛做的,小编只是抛砖引玉。


    展开全文
  • 机器学习 从广义上讲,机器学习是一种能够赋予机器学习的能力,让它以此完成直接编程无法完成的功能的方法 从实践的意义上讲,机器学习是一种通过利用数据,训练出模型,然后使用模型预测的一种方法 人类的学习是一...

    机器学习

    • 从广义上讲,机器学习是一种能够赋予机器学习的能力,让它以此完成直接编程无法完成的功能的方法
    • 从实践的意义上讲,机器学习是一种通过利用数据,训练出模型,然后使用模型预测的一种方法
    • 人类的学习是一个人根据过往的经验,对一类问题形成某种认识或总结出一定的规律,然后利用这些知识来对新的问题下判断的过程
    • 机器学习是指用某些算法知道计算机利用已知数据得出适当的模型,并利用此模型对新的情景给出判断的过程

    整个过程中最重要的是数据!,如果说模型是我们希望造出来的火箭,那数据就是它的燃料,数据直接决定了我们的火箭只是个概念玩具,还是能够载人登月,还是可以飞出太阳系探寻智慧生物,正所谓“No data,no intelligence”

    机器学习分类

    • 机器学习根据所处理数据种类的不同,可以分为有监督学习,无监督学习,半监督学习和强化学习等几种类型(实践中前两种使用较多)

    • 监督学习

      • 所谓监督学习,就是说数据样本会告诉计算机在该情形下的正确输出结果,希望计算机能够在面对没有见过的输入样本时也给出靠谱的输出结果,从而达到预测未知的目的X ----> y(目标值)。就像一个学生通过做多套高考模拟卷并订正答案的方式来提高高考成绩
      • 根据输出结果是离散值还是连续值,监督学习可以分为分类问题和回归问题两大类
      • 监督学习在文字、语音、图像识别,垃圾邮件分类与拦截,网页检索,股票预测等方面有着广泛应用
    • 无监督学习

      • 无监督学习,是指数据样本中没有给出正确的输出结果信息。这就像做了好多套没有答案的模拟卷,最后还要去高考

    机器学习算法

    • KNeighborClassifier
    • LinerRegression
    • Logistic
    • SVM
    • DecisionTree
    • XGboost
    • 贝叶斯
    • KMeans
    • TensorFlow

    开源平台

    • Github
    • Kaggle
    • 天池大数据竞赛(阿里巴巴)

    算法一. kNN (k(个数) nearest neighbor)

    简介:

    1.邻近算法,或者说K最近邻(kNN,k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。

    2.kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 kNN方法在类别决策时,只与极少量的相邻样本有关。由于kNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,kNN方法较其他方法更为适合。

    工作原理:

    1. 样本集:存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据 与所属分类的对应关系。输人没有标签的新数据后,将新数据的每个特征与样本集中数据对应的 特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般来说,我们 只选择样本数据集中前K个最相似的数据,这就是K-近邻算法中K的出处,通常K是不大于20的整数。 最后 ,选择K个最相似数据中出现次数最多的分类,作为新数据的分类。

    2. 欧几里得距离(Euclidean Distance):欧几里得度量(euclidean metric)(也称欧氏距离)是一个通常采用的距离定义,指在m维空间中两个点之间的真实距离,或者向量的自然长度(即该点到原点的距离)。在二维和三维空间中的欧氏距离就是两点之间的实际距离。
    在这里插入图片描述

    3. kNN近邻分类算法原理图解
    在这里插入图片描述

    从上图中我们可以看到,图中的数据集都有了自己的标签,一类是蓝色的正方形,一类是红色的三角形,那个绿色的圆形是我们待分类的数据

    如果K=3,那么离绿色点最近的有2个红色三角形和1个蓝色的正方形,这3个点投票,于是绿色的这个待分类点属于红色的三角形.

    如果K=5,那么离绿色点最近的有2个红色三角形和3个蓝色的正方形,这5个点投票,于是绿色的这个待分类点属于蓝色的正方形
    我们可以看到,KNN本质是基于一种数据统计的方法!其实很多机器学习算法也是基于数据统计的

    总结:

    KNN是一种基于记忆的学习(memory-based learning),也是基于实例的学习(instance-based learning),属于惰性学习(lazy learning)。即它没有明显的前期训练过程,而是程序开始运行时,把数据集加载到内存后,不需要进行训练,就可以开始分类了。

    优点:

    1.简单,易于理解,易于实现,精度高,对异常值不敏感,无需估计参数,无需训练,无需数据输入假定;

    2.适合对稀有事件进行分类;

    3.特别适合于多分类问题(multi-modal,对象具有多个类别标签), kNN比SVM的表现要好。

    缺点:

    1.时间复杂度高、空间复杂度高。

    2.当样本不平衡时,比如一个类的样本容量很大,其他类的样本容量很小,输入一个样本的时候,K个临近值中大多数都是大样本容量的那个类,这时可能就会导致分类错误。改进方法是对K临近点进行加权,也就是距离近的点的权值大,距离远的点权值小。

    3.计算量较大,每个待分类的样本都要计算它到全部点的距离,根据距离排序才能求得K个临近点,改进方法是:先对已知样本点进行剪辑,事先去除对分类作用不大的样本。

    适用数据范围:数值型和标称型

    1.标称型:标称型目标变量的结果只在有限目标集中取值,如真与假(标称型目标变量主要用于分类)

    2.数值型:数值型目标变量则可以从无限的数值集合中取值,如0.100,42.001等 (数值型目标变量主要用于回归分析)

    展开全文
  • 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)
    
    展开全文
  • 其实是这样的人工智能包含机器学习机器学习包含深度学习,换句话说人工智能范围最大,机器学习在人工智能中,深度学习又是机器学习的一个分支。 今天介绍机器学习中很重要的一个算法,这个算法对数学的要求很低,...
  • 用python学习机器学习的笔记,所有的代码和实例来源于《机器学习实战》一书。所有源代码和数据都可以在我的github上下载。 1.机器学习基础 机器学习可以分为监督学习和无监督学习,监督学习又可以分为分类...
  • 机器学习-KNN

    2020-07-21 22:09:47
    机器学习-KNN KNN入门-了解KNN import numpy as np import matplotlib as mpl mpl.rcParams['font.sans-serif'] = ['simHei'] mpl.rcParams['axes.unicode_minus'] = False import matplotlib.pyplot as plt # 随机...
  • KNN算法简介 KNN(K-Nearest Neighbor)最邻近分类算法是数据挖掘分类(classification)技术中最简单的算法之一,其指导思想是”近朱者赤,近墨者黑“,即由你的邻居来推断出你的类别。 KNN最邻近分类算法的...
  • 机器学习实战 KNN实战

    2018-10-16 23:06:52
    KNN实战1、KNN算法的一般流程1、搜集数据:可以使用任何方法2、准备数据:距离计算所需要的数值,最好是结构化的数据格式3、分析数据:可以使用任何方法4、训练算法:此...学习《机器学习实战》 1、KNN算法的一般...
  • 机器学习实战 KNN代码

    2017-10-11 12:00:28
    机器学习实战(一) KNN 本人,研一机器学习和数据挖掘的课比较少,加上对机器学习比较感兴趣,本科也接触了一些知识和项目,发现很多算法都是直接调用库,实现很少实操,特此把每个算法的步骤都复现一遍,算是加强...
  • 机器学习实战——kNN

    2018-05-21 22:13:14
    最近在学习机器学习算法,感觉有本书写得很不错——《机器学习实战》,如果有一点基础去看这本书,然后在结合书中实例进行实践,还是很有收获的。 之后,可能会不定时的更新此书的相关内容,主要内容参考此书,...
  • 机器学习笔记-KNN

    2019-01-31 00:24:27
    机器学习笔记-KNN 0x00 系列文章目录 机器学习笔记-KNN 机器学习笔记-决策树 0x01 摘要 K近邻(KNN),全名为k nearest neighbours,最近的K个邻居。 核心思想是找到目标节点最近的K个样本点,将他们的Y值...
  • K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。knn的基本思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个...
  • 机器学习KNN算法

    2019-08-13 14:21:36
    KNN(最邻近规则分类K-Nearest-Neighibor)KNN算法 1. 综述 1.1 Cover和Hart在1968年提出了最初的邻近算法 1.2 分类(classification)算法 1.3 输入基于实例的学习(instance-based learning), 懒惰学习(lazy ...
  • 机器学习knn总结

    2018-03-27 10:08:38
    1.过程:计算测试样本与训练样本之间的距离,这里的距离有欧式距离,曼哈顿距离,拉普拉斯距离等。按照距离进行排序选择其中最近的k个值,这里k值的选择用到交叉验证的方法,交叉验证包括s折,随机,留一根据分类决策...
  • 描述上图中,绿色圆要被决定赋予哪个类...K最近邻(k-Nearest Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中
  • KNN算法概述     k近邻(简称KNN)算法是一种基本的分类与回归方法。工作机制:给定测试样本,基于某种距离度量找出训练集中与其最靠近的K个训练样本,然后基于这K个”邻居“的信息来预测。 &...
  • 最近在学习机器学习,觉得机器学习特别有趣,现在将KNN算法做一个总结。 一、简介  KNN是一种有监督的分类算法,思想很简单,就是通过测量预测数据与训练数据之间的距离,选取前K个距离最短(或距离在K以内)的...
1 2 3 4 5 ... 20
收藏数 24,480
精华内容 9,792
关键字:

knn机器学习