《机器学习实战》-KNN算法心得

@[TOC]《机器学习实战》-KNN算法心得)

准备开始在CSDN上用博客记录学习心得，同时也分享一些其中自己产生的脑洞（想法）
PS：第一次在CSDN上写，还不习惯这个编写方式

在写之前说一下，因为书里很多代码在python3以后都会编译错误，所以关于《机器学习实战》的总结，不会具体分析代码，代码问题在overstackflow或者matplotlib官网都能搜索到。

KNN是处理分类问题的，而且是监督的，即需要预先认为的给出一些已知类别的数据供KNN计算。其中对一个物体，需要人为的分成多个属性，并求出每个属性的值。它对属性的值要求可以是连续也可以是离散的。

书里介绍的KNN算法算是全书中最好理解的一部分了。其核心理论是将类别的多个属性看做是多维空间的参数，将已经识别的类数据库根据属性的值放置在这个多维空间中，然后用未知类别物体的属性值与已知的各个点进行距离计算（sqrt（x1^2+x22+x3^2……）），离得最近的点的类别就是这个未知类别物体的类别，当然，考虑到可能存在的误差，它取了前K个最近距离点，统计其中出现的类别次数，并返回出现次数最多的类别。

关于空间距离的说法，在很多机器学习的论文里，都会提到多维或者超维或者降维的问题，因为当初学线性代数的时候一上来就是行列式，所以以前没理解，后来看了一本《introduce to Linear algebra》（强烈推荐），上面一开始介绍时将[1,2,3]T介绍为三维空间中的指向从（0,0,0）点指向(1,2,3)的一个向量，因此上文所说的多维空间距离就是因为KNN把每个属性看做一个坐标系，值就是这个类别点在这个坐标系上的坐标，才有了距离一说。

另外，因为每个属性的值有大有小，所以在数据上预先将所以数据按照：（对应属性的值-此属性的最小值）/（此属性的最大值-最小值）的方式都归一化到[0,1]的范围内。

流程如下图所示：

按照KNN的算法，可以进行书中提供数据的分类，有意思的是，改变K值会发现，K值的提高并不会降低分类的错误率（错误率=错误的分类/总的数据，这是用一些检测数据来计算的），反而可能增加错误率，这是因为KNN不是一种特征提取的算法，它并不会从数据中识别出那些核心分类的特征，而只是单纯的计算用人为给出的属性值组成的参数距离。

同时减少K值对KNN的算法时间并没有明显的减少，从上面的算法就可以看出，找出前K个数，在K较小时并不耗时（如果不按书里的算法（先全排序再取前K个数）而是堆排后弹出前K个值还会更省时，而且因为其实前K个数不需要排序，所以用快排里的取前K的算法甚至在O（N）时间里就得到），反而是需要对已知分类的N个数，都要计算空间距离，相当于对矩阵进行了做差后平方（一次全遍历矩阵，O（NN）），求和（一次全遍历矩阵，O（NN）），开根号（因为是列表，所以是O（N）），当数据较大后非常耗时（都是浮点计算），数据小的时候又不准确，所以KNN是个非常耗时的算法。

另外，个人分析，KNN将属性值视作坐标系的做法，相当于默认属性间线性无关，如果人为选择的属性间线性相关（即相互影响），真实的距离和计算的距离就有偏差了，可能计算出来是最近的点，实际一旦正交化距离就远了。

KNN算法部分就到这里，接下来是决策树。