【李飞飞的AI课】Introduction to Convolut | Hello！Welcom to Tumy-Time！

k-Nearest Neighbors分类算法

单纯比较相似性

k-最近邻（k-Nearest Neighbors，k-NN）算法是一种简单的机器学习算法，用于分类和回归分析。在分类问题中，k-NN 算法根据训练数据集中的 k 个最接近的样本（称为“邻居”）来预测新样本的类别。
以下是 k-NN 算法的基本步骤：

选择 k 值：首先，你需要选择一个正整数 k，这决定了算法中要考虑的最近邻的数量。k 的值通常通过交叉验证等方法来确定，但也可以根据具体问题设定。
计算距离：对于新样本，计算它与训练数据集中每个样本的距离。常用的距离度量有欧几里得距离、曼哈顿距离、余弦距离等。
选择邻居：根据距离，选择 k 个最近的样本。这些样本称为“k 个最近邻”。
预测类别：根据最近邻的类别，对新样本进行预测。通常使用多数表决原则，即新样本的类别是 k 个最近邻中出现次数最多的类别。如果 k 个邻居中有多个类别出现次数相同，那么新样本的类别是不确定的。
回归分析：在回归问题中，k-NN 算法预测新样本的值是 k 个最近邻的值的平均值或加权平均值。
k-NN 算法的一些关键特性：

简单直观：k-NN 算法非常直观，易于理解和实现。
不需要训练：k-NN 算法不需要训练模型，因为它不需要学习参数，而是直接使用训练数据进行预测。
高维数据：k-NN 算法可以处理高维数据，因为它只是计算样本之间的距离，而不是对数据进行降维或特征选择。
计算复杂度：k-NN 算法的计算复杂度较高，因为它需要计算新样本与所有训练样本的距离，并选择最近的 k 个邻居。
k-NN 算法在处理小规模数据集或当新样本的类别可以从其邻近样本的类别中直观地推断出来时效果较好。然而，在处理大规模数据集或当新样本的类别难以从其邻近样本的类别中推断出来时，k-NN 算法可能不够有效。此外，k-NN 算法对噪声和异常值比较敏感，因此在实际应用中可能需要对数据进行预处理。

欧式距离与曼哈顿距离的区别

欧氏距离就是我们最常用的两点之间的直线距离。
以二维空间为例，两点(x1,y1),(x2,y2)之间的欧式距离为：
$ \rho = \sqrt{(x_2-x_1)^2+(y_2-y_1)^2} $
曼哈顿距离则表示两个点在标准坐标系上的绝对轴距之和。
还是以二维空间为例，两点(x1,y1),(x2,y2)之间的曼哈顿距离为：
$ c = |x_1-x_2|+|y_1-y_2| $

用一张图来区分一下两者:

为什么要提出曼哈顿距离呢？
——为了简化计算。

曼哈顿距离中的距离计算公式比欧氏距离的计算公式看起来简洁很多，只需要把两个点坐标的 x 坐标相减取绝对值，y 坐标相减取绝对值，再加和。
从公式定义上看，曼哈顿距离一定是一个非负数，距离最小的情况就是两个点重合，距离为 0，这一点和欧氏距离一样。
曼哈顿距离和欧氏距离的意义相近，也是为了描述两个点之间的距离，不同的是曼哈顿距离只需要做加减法，这使得计算机在大量的计算过程中代价更低，而且会消除在开平方过程中取近似值而带来的误差。不仅如此，曼哈顿距离在人脱离计算机做计算的时候也会很方便。

import numpy as np


class NearestNeighbor:
    def __init__(self):
        pass

    def train(self, X, y):
        """X is N x D where each row is an example.
        Y is l-dimension of size N"""
        # the nearest neighbor classifier simply remembers all the training data
        self.Xtr = X
        self.ytr = y

    def predict(self, X):
        """X is N x D where each row is an example we wish to predict label for"""
        num_test = X.shape[0]
        Ypred = np.zeros(num_test, dtype=self.ytr.dtype)
        distances = np.zeros((X.shape[0], self.Xtr.shape[0]))

        # loop over all test rows
        for i in np.xrange(num_test):
            # find the nearest training image to the i'th test image
            # using the L1 distance (sum of absolute value differences)
            distances[i] = np.sum(np.abs(self.Xtr - X[i, :]), axis=1)
            min_index = np.argmin(distances[i])  # get the index with the smallest distance
            Ypred[i] = self.ytr[min_index]  # predict the label of the nearest example

        return Ypred

为什么distance是二维的：
对于测试样本集中的每个测试样本 X[i, :]，我们计算它与训练样本集中的每个训练样本 self.Xtr[j, :] 之间的 L1 距离，并存储在 distances[i] 中。由于有多个测试样本，所以需要一个矩阵来存储这些距离。

k-Nearest Neighbors分类算法

你的赏识是我前进的动力