1. 分类任务概述
   
   
   
   曼哈顿距离：|x1-x2| + |y1-y2|
   欧几里得距离：
   汉明距离：
   距离测量——“相似”是什么意思？
   

2.最近邻算法
提供一种思路，即：未知的豆离哪种豆最近就认为未知豆和该豆是同一种类。由此，我们引出最近邻算法的定义：为了判定未知样本的类别，以全部训练样本作为代表点，计算未知样本与所有训练样本的距离，并以最近邻者的类别作为决策未知样本类别的唯一依据。但是，最近邻算法明显是存在缺陷的，我们来看一个例子。

如果蓝色的是噪声，那其实绿点本应该属于红色。但最近邻算法毫无疑问地将其分类为蓝色，所以存在不足。
显然，通过上面的例子我们可以明显发现最近邻算法的缺陷——对噪声数据过于敏感，为了解决这个问题，我们可以可以把位置样本周边的多个最近样本计算在内，扩大参与决策的样本量，以避免个别数据直接决定决策结果。由此，我们引进K-最近邻算法。

3.k近邻算法
k-近邻算法，也叫KNN算法(K-Nearest Neihbor，KNN)，是一个非常适合入门的算法，拥有如下特性：
适用于分类问题，尤其是二分类，当然也可以用来预测回归问题
思想极度简单，应用数学知识少(近乎为零)

那么k近邻算法是什么呢?

上图中的数据点是分布在一个特征空间中

横轴表示肿瘤大小，纵轴表示发现时间
恶性肿瘤用蓝色表示，良性肿瘤用红色表示
新来了一个病人(下图绿色的点)，如何判断新来的病人(即绿色点)是良性肿瘤还是恶性肿瘤？

k-近邻算法的做法如下：
取一个值k=3(k值后面介绍，现在可以理解为算法的使用者根据经验取的最优值)

让最近的点所属的类别进行投票
最近的三个点都是蓝色的，所以该病人对应的应该也是蓝色，即恶性肿瘤。

本质：如两个样本足够相似，那他们两个大概率属于同一类别
选择K个样本判断相似：如果只看一个已知样本，可能不准确
如果K个样本中大多数属于同一个类别，则被预测的样本就很可能属于对应的类别
如何衡量“相似性”：依靠距离衡量

再比如：

上图中和绿色的点距离最近的点包含两个红色和一个蓝色，此处红色点和蓝色点的数量比为2:1，则绿色点为红色的概率最大，最后判断结果为良性肿瘤。

K-近邻算法实现分类
1.绘制基本图像
2.加入预测点，绘制图像
预测蓝色点属于哪一个类别，需要找到距离蓝色点最近的K个邻居，找到K个邻居需要计算距离：
欧式距离：任意空间下两个点的对应维度的坐标值相减的平方和再开方
欧式距离公式：
平面中两点之间的欧式距离：
立体中两点之间的距离：
任意维度下的欧拉距离：

3.实现距离计算
4.定义k值，得出计算结果
5.特点
knn算法没有得到模型，它是机器学习中唯一一个不需要训练过程的算法
没有模型的算法
为了和其他算法统一，可以认为数据集就是模型本身

归一化(Normalization)：把所有数据映射到(0,1)之间
计算流程：$$\Large x{scale}=\frac{x-x{min}}{x{max}-x{min}}$$

先计算所有样本的每个特征的最大值和最小值计算出来
用每个样本的特征值减去对应的最小值
x−xmin
x−xmin，
再计算最大值和最小值的差值 $$x{max}-x{min}$$
最后将两个结果进行除法操作，得到最终的特征归一化结果
xscale
xscale。
适用情况：分布有明显边界
举例：学生分数0-100有明显边界，图片像素点的值0-255有明显边界。

缺点：受异常值（outlier）影响较大
观察公式，结果受$$x{max}和x{min}$$影响严重

标准化(standardization)：把所有数据利用均值和标准差进行转换,均值为0,标准差为1
$$\Large x{scale}=\frac{x-x{mean}}{S}$$
利用每个特征值减去特征值均值再除以特征值的标准差得到标准化的结果
适用情况：数据分布没有明显边界
优点：不容易受到极端数据值的影响

数据归一化代码实现：
data_minmax = data.copy()

对两列特征进行归一化

min0 = np.min(data_minmax[:,0])
max0 = np.max(data_minmax[:,0])
data_minmax[:,0]=(data_minmax[:,0]-min0)/(max0-min0)
min1 = np.min(data_minmax[:,1])
max1 = np.max(data_minmax[:,1])
data_minmax[:,1]=(data_minmax[:,1]-min1)/(max1-min1)

数据可视化

plt.scatter(data_minmax[:,0],data_minmax[:,1])
plt.show()

5. KD树
   1.在k-d树中进行数据的查找也是特征匹配的重要环节，其目的是检索在k-d树中与查询点距离最近的数据点。这里先以一个简单的实例来描述最邻近查找的基本思路。
   星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行’回溯’操作：算法沿搜索路径反向查找是否有距离查询点更近的数据点。此例中先从（7,2）点开始进行二叉查找，然后到达（5,4），最后到达（2,3），此时搜索路径中的节点为<（7,2），（5,4），（2,3）>，首先以（2,3）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为0.1414，然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如图4所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中去搜索。再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。
   
   查找（2.1，3.1）点的两次回溯判断
   2.一个复杂点的例子如查找点为（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。以（2，4.5）为圆心，以3.041为半径作圆，如图5所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找。此时需将（2,3）节点加入搜索路径中得<（7,2），（2,3）>。回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如图6所示。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。k-d树查询算法的伪代码如表所示。
   
   查找（2，4.5）点的第一次回溯判断

查找（2，4.5）点的第二次回溯判断!

总结：
优点：1. 可以处理分类问题，算法简单易懂
2. 可以免去训练过程
3. KNN还可以处理回归问题，也就是预测
缺点：1. 效率低，每一次分类都要对训练数据进行计算
2. 对训练数据依赖度特别大，过拟合、欠拟合问题难以权衡
3. 存在维数灾难问题

参考：https://blog.csdn.net/qq_34405401/article/details/102760761?ops_request_misc=&request_id=&biz_id=102&utm_term=最近邻搜素kd树&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduweb~default-0-102760761.142^v63pc_rank_34_queryrelevant25,201^v3control_1,213^v2t3_control2&spm=1018.2226.3001.4187