K最近邻算法

一、近朱者赤，近墨者黑

通常称对门、楼上、楼下和隔壁均是我们的邻居。为什么呢？离得近呗。 “近朱者赤近墨者黑”“昔孟母，择邻处”等充分说明了邻居对我们的重要性。基本上你的邻居是什么人，你也是什么人。假如你楼上是马云，楼下是马化腾，那你肯定也是亿万富翁，否则也买不起那里的房子。
2020年7月份，我校网站、中国教育在线等各大网站都在发送下面这条新闻：

2020年7月份，南阳理工学院信息工程学院2016级考研学子喜讯频传，其中一男生宿舍6名同学全部收到了研究生录取通知书。
在青年公寓B205宿舍里，住着2016级光电信息科学与工程专业6位男生，在硕士研究生考试中，以优异成绩全部被录取。他们的考取学校分别是：马凤阳，复旦大学；王玉杰，四川大学；梁瑞，中国海洋大学；张志鹏，华南师范大学；梁爱杰，暨南大学；陈林，深圳大学。
谈起考研，6位男生都有不一样的想法，但是他们的目标都一致。梁瑞说经过大学四年的学习，对本专业产生浓厚的兴趣，想要更加深入的学习与研究。考研是一场孤独的旅行，在这场旅行中，有艰辛，有磨练，更有对未来的憧憬和期待……马凤阳和张志鹏等6名同学每天早上6：30准时起床去教室学习，晚上十点多回寝室，在备考过程中难免会有厌倦、烦躁、焦虑，但他们相互鼓励，继续努力奋斗……

算法简介

1. KNN算法的全称是K-Nearest Neighbor，即k最近邻，由Cover和Hart在1968年提出。
2. K指的是最近邻的个数，K最近邻指的是离你最近的k个邻居。显然，当K=1,3,5等不同值时，最近邻是不同的。
3. 该算法是监督学习算法，适用于分类和回归任务。
4. 通过测量不同样本的特征值之间的距离来寻找最近的K个邻居，然后根据这些邻居的信息来预测目标变量。如果A最亲近的几个好友人品都不错，那么可预测A的人品也不错（分类）；也可根据A几个好友的收入来预测A的收入（回归）。
5. 在分类任务中，算法会查找距离待预测样本最近的K个邻居，然后根据这些邻居的类别，通过多数投票机制确定待预测样本的类别。在回归任务中，算法同样查找距离待预测样本最近的K个邻居，但是它会计算这些邻居的目标变量的平均值（或中位数），并将此值作为预测结果。
   
   显然，当K=1和K=5时，绿色点的最近邻是不同的。

算法的核心

核心1：如何确定最近邻？

可计算样本间的距离或相似度，用距离或相似度来衡量样本之间的差异。
常用的计算距离的公式有：欧氏距离、曼哈顿距离、和闵可夫斯基距离等。
常用的计算相似度的公式有：余弦相似度、皮尔逊相关系数等。例如常见的推荐系统，即通过计算目标用户与其他用户之间的相似度，找到与目标用户最相似的K个用户，然后根据这K个用户的喜好来为目标用户推荐物品。
选择距离度量的方式需要考虑到数据的特点和实际问题的需求。例如，欧氏距离适用于大多数场景，但在某些特征有不同权重的情况下，可能需要考虑加权欧氏距离；曼哈顿距离在城市街区距离计算中有应用，而切比雪夫距离在国际象棋中计算国王的移动距离时使用。如果数据中包含许多0值，那么使用余弦相似度可能更合适。如果特征值差异较大，可能需要考虑归一化后的欧氏距离或曼哈顿距离。

核心2：如何确定K值？

K值的选择会极大影响K近邻的结果。试想一下：如果K=1或者K=样本总数，预测结果会怎样？
K值的确定方法：经验值、交叉验证方法（通过模型在验证集上的表现来选择最佳的k值）等。此外，K值最好为奇数。

标题KNN是如何解决分类和回归问题的？

在分类任务中，算法会查找距离待预测样本最近的K个邻居，然后根据这些邻居的类别，通过多数投票机制确定待预测样本的类别。观察下图，想想绿色点的类别应为红色还是蓝色？

如果按照投票的方式，应该分为蓝色类别，但从距离上看，样本距离红色类别更近，划为红色似乎更加合理，这里就需要引入距离权重的概念。
在KNeighborsClassifier中有一个参数weight，不指定该参数的情况下默认为uniform也就是多数投票，也可以指定weight为distance，即可采用距离权重的方式进行分类。
此外，在回归任务中，算法同样查找距离待预测样本最近的K个邻居，但是它会计算这些邻居的目标变量的平均值（或中位数），并将此值作为预测结果。

实战

步骤1：导入所需包库

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

步骤2：导入数据集，提取特征和标签

iris=load_iris( )
X=iris[‘data’]
y=iris[‘target’]

步骤3：训练集和测试集的划分

X_train,X_test,y_train,y_test=train_test_split(X,yrandom_state=1)

步骤4：创建KNN分类器实例，设置不同的k值进行交叉验证测试

k_values = [1, 3, 5, 7, 9]
accuracies = [ ]

for k in k_values:
knn = KNeighborsClassifier(n_neighbors=k)
scores = cross_val_score(knn, X_train, y_train, cv=5, scoring=‘accuracy’)
accuracies.append(scores.mean())

步骤5：找出最佳k值

best_k = k_values[accuracies.index(max(accuracies))]
print(f"最佳k值为: {best_k}")

步骤6：用最佳K值来训练模型，并在测试集上进行预测

knn=KNeighborsClassifier(n_neighbors=best_k)
knn.fit(X_train,y_train)
knn.score(X_test,y_test)

步骤7：模型用于预测新样本的类别

X_new=[[1.2,3.4,5,3.8]] #假设获得的一个新样本
print(knn.predict(X_new))
print(knn.predict_proba(X_new))
print(knn.classes_)
print(iris.target_names[knn.predict(X_new)])
运行结果：

KNeighborsClassifier详解

KNeighborsClassifier(n_neighbors=5, weights=‘uniform’, algorithm=‘auto’, leaf_size=30, p=2, metric=‘minkowski’, metric_params=None, n_jobs=1, **kwargs)
主要参数见下表：

拓展

1.利用KD树来找最近邻
from sklearn.neighbors import KDTree
#构建KD树
tree = KDTree(X_train, leaf_size=40, metric=‘minkowski’)
#查询最近邻居
distances, indices = tree.query(X_test, k=5)
#输出最近的5个邻居的距离和索引
print(“邻居距离：”)
print(distances)
print(“邻居索引：”)
print(indices)
2. 利用BallTree来找最近邻（KD树的变种，适用于不同形状的数据分布）
from sklearn.neighbors import BallTree

构建球树

ball_tree = BallTree(X_train, leaf_size=40, metric=‘minkowski’)

查询最近邻居

distances, indices = ball_tree.query(X_test, k=5)

输出最近的5个邻居的距离和索引

print(“邻居距离：”)
print(distances)
print(“邻居索引：”)
print(indices)
参考链接：https://blog.csdn.net/weixin_36431814/article/details/142418794