1. 算法原理

KNN 属于懒学习（Lazy Learning）算法。所谓懒，就是训练阶段几乎不做什么计算，只是把训练数据原样存下来。

等到要预测的时候，KNN 才会拿测试点去跟训练集里每个点算距离，挑出最近的 K 个邻居，再根据这 K 个邻居的标签下判断：

分类问题：让 K 个邻居各自投票，得票最多的那个类别就是预测结果。
回归问题：把 K 个邻居的数值取平均，作为预测结果。

KNN 里最常用的距离是欧氏距离，除此之外也可以用曼哈顿距离、切比雪夫距离等。

K 值是这个算法里最关键的超参数。K 取小了，模型容易过拟合，K 取大了，又可能欠拟合，所以选 K 得讲究办法。常用的做法是交叉验证：在训练集上反复交叉验证，挑出让模型在验证集上表现最好的那个 K。

2. 算法优缺点

先说优点。KNN 的第一个好处是简单易懂，原理很直观，几乎没什么复杂的数学推导，学起来和写起来都不难。而且 KNN 不需要假设数据服从什么分布，这让它在面对一些传统模型难以刻画的复杂分布时，照样能正常工作。

缺点也很明显。头一个是计算开销大。预测时它要把测试点跟训练集里每个点都算一遍距离，数据一多，计算量蹭蹭往上涨，处理大规模数据时成本很高。

其次是存储开销大。KNN 得把整个训练集都存下来备用，数据海量的时候，内存压力也不小。

再有就是 KNN 对噪声很敏感。训练集或测试集里要是混进了噪声或异常点，它们可能被误当成邻居带偏结果，准确率跟着掉下来。数据不干净的时候，KNN 的表现就不太好看。

3. 算法优化

KNN 的计算复杂度会跟着数据维度一起涨。维度一高，KNN 的效率就明显下降，效果还可能被「维度灾难」拖垮。所谓维度灾难，是说特征空间的维度越高，样本点之间的距离就越拉不开差距，距离度量慢慢失效，算法性能也就跟着掉了。

怎么缓解呢？可以用降维方法，比如主成分分析（PCA）。PCA 会找出数据里的主成分，把数据投影到一个更低维的空间里，在保留大部分信息的同时把维度降下来。这样既减轻了计算负担，也能让 KNN 在高维数据上跑得更好。

想让 KNN 在大数据集上查得更快，常用 KD 树（K-dimensional tree）和 Ball 树（Ball tree）这两种数据结构。它们用不同的方式把训练数据组织起来，查邻居时就不必把整个数据集挨个遍历了。

KD 树：把数据按维度逐层划分的树形结构，每次选一个维度切一刀。查邻居会快不少，在低维数据上尤其好用。
Ball 树：基于球形区域来划分数据的树形结构，更适合高维数据集，在高维空间里搜邻居效率更高。

用了这些数据结构，KNN 在大数据集上的计算时间能明显缩短，跑起来更利索。

还可以用加权投票法。它跟简单投票不一样，邻居的话语权和它到测试点的距离成反比：离得越近，投票权重越大。这么做是为了压低那些离得远的邻居对结果的干扰，让预测更准。在不少数据集上，加权投票的效果都比简单投票好。

4. 算法使用

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split


def iris_data():
    """
    鸢尾花数据信息
    """

    # 1. 加载鸢尾花数据集
    dataset = load_iris()
    # 样本数量
    print("样本数量:", len(dataset.data))
    # 类别名称
    print("类别名称:", dataset.target_names)
    # 特征名称
    print("特征名称:", dataset.feature_names)
    # 样本类别
    print("样本类别:", dataset.target)
    # 样本数据
    print("样本数据:", dataset.data)


# knn API
def knn_api():

    # 1. 加载鸢尾花数据
    iris_dataset = load_iris()

    # 2. 创建 knn 分类对象
    knn = KNeighborsClassifier(n_neighbors=3)

    # 3. 将数据集划分为训练集和测试集[测试集占所有数据集的20%]
    X_train, X_test, y_train, y_test = \
        train_test_split(iris_dataset.data, iris_dataset.target, test_size=0.2)

    # 4. 训练数据
    knn.fit(X_train, y_train)

    # 5. 进行预测
    for index in range(len(X_test)):

        # 5.1 计算当前测试样本属于哪个分类
        class_label = knn.predict([X_test[index]])
        # 5.2 计算当前测试样本属于每个分类的概率
        class_proba = knn.predict_proba([X_test[index]])
        # 5.3 返回距离当前测试样本最近的 N 个样本
        nearest_neighbors = knn.kneighbors([X_test[index]], 5, False)

    # 预测准确率
    predict_score = knn.score(X_test, y_test, sample_weight=None)
    print("准确率:", predict_score)


if __name__ == "__main__":
    knn_api()

K 近邻算法（K-Nearest Neighbor）

K 近邻算法（K-Nearest Neighbor）

1. 算法原理

2. 算法优缺点

3. 算法优化

4. 算法使用