KNN

一、算法思想

即最近邻居算法，分类算法，监督学习。

核心思想是：物以类聚，人以群分。假设一个未知样本数据x需要归类，总共有ABC三个类别，那么离x距离最近的有k个邻居，这k个邻居里有k1个邻居属于A类，k2个邻居属于B类，k3个邻居属于C类，如果k1>k2>k3，那么x就属于A类，也就是说x的类别完全由邻居来推断出来。

作为一个懒惰学习算法(Lazy learning)，其本身并没有损失函数与相关参数。

二、算法步骤

计算测试对象到训练集中每个对象的距离

按照距离的远近排序

选取与当前测试对象最近的K的训练对象，作为该测试对象的邻居。

统计这K个邻居的类别概率

K个邻居里频率最高的类别，即为测试对象的类别

常用距离公式

假定数据集的特征序列为{ $x_1,x_2,x_3......x_n$ }，预测(Prediction)数据为 P，相对比的单个数据为 X。

欧氏距离(Euclidean distance)

$D(P,X)=\sqrt{(p_1-x_1)^2+(p_2-x_2)^2+...+(p_n-x_n)^2}=\sqrt{\sum_{i=1}^n (p_i-x_i)^2}$

曼哈顿距离(Manhattan distance)

$D(P,X)=\vert p_1-x_1\vert+\vert p_2-x_2\vert+...+\vert p_n-x_n\vert=\sum_{i=1}^n \vert p_i-x_i\vert$

闵式距离(Minkowski distance)

闵式距离又称闵可夫斯基距离，它可以看作是差值向量的 $\alpha-Norm$ ( 先前介绍的曼哈顿距离与欧氏距离则分别是特殊的 $1 − N o r m$ 与 $2 − N o r m$ )，其中 $\alpha$ 为大于 $0$ 的常数

$D(P,X)=\sqrt[\alpha]{\sum_{i=1}^n \vert p_i-x_i\vert ^\alpha}$

标准化欧氏距离(Standardized Ed)

标准化欧式距离是针对传统距离公式无法解决各个特征维度之间的分布不同。就像由于特征之间数级尺度不同，进行梯度下降法之前要先对数据进行归一化。如果我们提前进行标准化，也能解决这个问题，而标准欧氏距离则可以通过更改内部公式，加入方差的倒数项 $s_i$ 来解决。

$D(P,X)=\sqrt{\sum_{i=1}^n (\dfrac{p_i-x_i}{s_i})^2}$

余弦距离(Cosine distance)

这里为了方便余弦距离公式的书写，其中 $P$ 代表的是单个预测数据的行向量， $X^i$ 代表的是数据集中第 $i$ 个数据的列向量。

$\cos (P, X^i)= \cfrac{PX^i }{\vert \vert P\vert \vert _2 \vert \vert X^i\vert \vert _2 }$

切比雪夫距离(Chebyshev distance)

$D(P,X)=max \vert p_i-x_i\vert$

k值的确定：

k值越小，模型整体变得越复杂，越容易过拟合。通常使用交叉验证法来选取最优k值

分类决策：

一般使用多数表决，即在 k 个临近的训练点钟的多数类决定输入实例的类。可以证明，多数表决规则等价于经验风险最小化

三、优点

天生支持增量学习（不需要训练，没有增量拓展的麻烦事儿）

可以用于非线性分类

能对超多变形的复杂决策空间建模

在数据量不多但数据代表性较强时，kNN分类效果较好

四、缺点

属于懒惰算法，时间复杂度较高，因为需要计算未知样本到所有已知样本的距离，样本平衡度依赖高，当出现极端情况样本不平衡时，分类绝对会出现偏差。可解释性差，无法给出类似决策树那样的规则。向量的维度越高，欧式距离的区分能力就越弱。

五、适用场景

数据敏感度

对数据没有假设，准确度高，对异常点不敏感

样本不平衡的时候，对稀有类别的预测准确率低

实际应用

经常在stacking中与其他模型组合使用，例如采用svm的特征为KNN加权

面试常见问题

不平衡的样本可以给KNN的预测结果造成哪些问题，有没有什么好的解决方式？

输入实例的K邻近点中，大数量类别的点会比较多，但其实可能都离实例较远，这样会影响最后的分类。
可以使用权值来改进，距实例较近的点赋予较高的权值，较远的赋予较低的权值。

为了解决KNN算法计算量过大的问题，可以使用分组的方式进行计算，简述一下该方式的原理。

先将样本按距离分解成组，获得质心，然后计算未知样本到各质心的距离，选出距离最近的一组或几组，再在这些组内引用KNN。本质上就是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本，该方法比较适用于样本容量比较大时的情况。

KD树建立过程中切分维度的顺序是否可以优化？

先对各个维度计算方差，选取最大方差的维度作为候选划分维度(方差越大，表示此维度上数据越分散)；对split维度上的值进行排序，选取中间的点为node-data；按照split维度的node-data对空间进行一次划分；对上述子空间递归以上操作，直到空间只包含一个数据点。分而治之，且循环选取坐标轴。从方差大的维度来逐步切分，可以取得更好的切分效果及树的平衡性。

4、KD树每一次继续切分都要计算该子区间在需切分维度上的中值，计算量很大,有什么方法可以对其进行优化？

算法开始前，对原始数据点在所有维度进行一次排序，存储下来，然后在后续的中值选择中，无须每次都对其子集进行排序，提升了性能。

六、代码

# 导入算法包
import numpy as np
import pandas as pd
from random import choice
from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import KFold, StratifiedKFold

# 预设进行10段交叉验证
N = 10

#采用鸢尾花数据集： X 为特征向量，y 为标签向量
#iris = datasets.load_iris()
path = './iris.data'  # 数据文件路径
# 读取数据：
iris=pd.read_csv(path,header=None)
x, y = np.split(iris.values, (4,), axis=1)

# 定义候选值，对于二分类模型，通常选取20以内的奇数
k_candidate = [i for i in range(1,20) if i%2!=0]
# 进行10折交叉验证，返回的是训练集和验证集的下标
# KFold,StratifiedKFold中选择StratifiedKFold是考虑数据分布，选择KFold为考虑均分
# fk = KFold(n_splits=N, shuffle=True, random_state=521)
fk = StratifiedKFold(n_splits=N, shuffle=True, random_state=521)


# 预设准确率
maximum_accuracy = 0
# 预设best的k
best_k = choice(k_candidate)
# 遍历所有的候选值
for k in k_candidate:
    # 记录10段的准确率之和 
    count_accuracy = 0
    # 遍历10段的数据集
    # for train_index,valid_index in fk.split(X):
    for train_index,valid_index in fk.split(X,y):
        # 实例化KNN模型
        clf = KNeighborsClassifier(n_neighbors=k)
        # 训练模型
        clf.fit(X[train_index], y[train_index])
        # 统计累计准确率
        count_accuracy = count_accuracy + clf.score(X[valid_index], y[valid_index])
    # 计算KNN模型的K值为k时的平均准确率值
    count_accuracy = count_accuracy/N
    print('平均准确率为：%.2f' % count_accuracy)
    # 判断平均准确率值是否大于目前最大的准确率值
    if count_accuracy > maximum_accuracy:
        # 将平均准确率值替代原先最大的准确率值
        maximum_accuracy = count_accuracy
        # 将目前的K值替换原先最好的K值
        best_k = k
    print('当前最好的K值为：%d'%best_k,"当前最大的准确率值为：%.2f"%maximum_accuracy)
    print("*"*60)
print('评估最合适的K值为：%d'%best_k,"其准确率为：%.2f"%maximum_accuracy)

结果

参考
机器学习之KNN算法原理_喽哥的博客-CSDN博客_knn算法的原理和步骤
 分类算法-KNN(原理+代码+结果)_突然好想你616的博客-CSDN博客_knn算法的原理和步骤
 knn算法适合在什么场景下用 - CSDN

python 机器学习算法 KNN

python 机器学习算法 KNN

KNN

一、算法思想

二、算法步骤

常用距离公式

欧氏距离(Euclidean distance)

曼哈顿距离(Manhattan distance)

闵式距离(Minkowski distance)

标准化欧氏距离(Standardized Ed)

余弦距离(Cosine distance)

切比雪夫距离(Chebyshev distance)

k值的确定：

分类决策：

三、优点

四、缺点

五、适用场景

数据敏感度

实际应用

面试常见问题

六、代码

推荐阅读更多精彩内容

python 机器学习算法 KNN

KNN

一、 算法思想

二、算法步骤

常用距离公式

欧氏距离(Euclidean distance)

曼哈顿距离(Manhattan distance)

闵式距离(Minkowski distance)

标准化欧氏距离(Standardized Ed)

余弦距离(Cosine distance)

切比雪夫距离(Chebyshev distance)

k值的确定：

分类决策：

三、 优点

四、缺点

五、适用场景

数据敏感度

实际应用

面试常见问题

六、代码

推荐阅读更多精彩内容

一、算法思想

三、优点