博客详情页

KNN(K近邻)分类器是有监督学习领域之中，最简单且被普遍使用的分类器之一，KNN分类器一般被认为是一种懒惰的学习器。

1.什么是KNN

何谓K近邻算法，即K-Nearest Neighbor algorithm，简称KNN算法，单从名字来猜想，可以简单粗暴的认为是：K个最近的邻居，当K=1时，算法便成了最近邻算法，即寻找最近的那个邻居。用官方的话来说，所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居），这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

avatar

【问题】:如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在，我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），KNN就是解决这个问题的。

【分析】：如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

【核心思想】：当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。

2.距离度量

我们看到，K近邻算法的核心在于找到实例点的邻居，这个时候，问题就接踵而至了，如何找到邻居，邻居的判定标准是什么，用什么来度量。这一系列问题便是下面要讲的距离度量表示法。

(1)欧氏距离euclidean:最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中。

(2)曼哈顿距离manhattan：我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。通俗来讲，想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”，此即曼哈顿距离名称的来源，同时，曼哈顿距离也称为城市街区距离。

(3)切比雪夫距离manhattan：玩过国际象棋的朋友或许知道，国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？你会发现最少步数总是max( | x2-x1 | , | y2-y1 | ) 步。

【说明】：常用的就上面三种，还有一些距离度量：闵可夫斯基距离，标准化欧氏距离、马氏距离、巴氏距离、汉明距离、夹角余弦、皮尔逊系数和杰卡德相似系数等等...

3.何时使用kd树

实现KNN算法时，存在一个容易被人们忽视的问题：如何对训练数据进行快速k近邻搜索。这是因为，当数据集比较少的时候，计算机运行速度还是很快的，问题体现的不明显。kNN最简单的搜索实现：线性扫描(穷举搜索)即要计算输入实例与每一个训练实例的距离，计算并存储好以后，在查找k近邻。当数据集很大的时候，计算非常耗时。为了提高KNN搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数------kd树

4.KNN算法API初步使用

4.1 手动创建数据模拟分类问题

数据集仅含有1个特征，共有0、1两个类别

# 模块导入
from sklearn.neighbors import KNeighborsClassifier

# 创建数据集
x = [[1], [2], [10], [20]]
y = [0, 0, 1, 1]

# 实例化API
estimator = KNeighborsClassifier(n_neighbors=1)

# 模型训练
estimator.fit(x,y)

# 预测
print(estimator.predict([[0]]))

[0]

4.2 找到一个观察值的最近邻

from sklearn import datasets
from sklearn.neighbors import NearestNeighbors
from sklearn.preprocessing import StandardScaler

# 加载数据
iris = datasets.load_iris()
features = iris.data

# 创建standardizer
standardizer = StandardScaler()

# 特征标准化
features_standardized = standardizer.fit_transform(features)

# 两个最近的观察值
nearest_neighbors = NearestNeighbors(n_neighbors=2, metric='euclidean').fit(features_standardized)

# 创建一个观察值
new_observation = [1, 1, 1, 1]

# 获取离观察值最近的两个观察值的索引，以及到这两个点的距离
distances, indices = nearest_neighbors.kneighbors([new_observation])

# 查看最近的两个观察值
print(features_standardized[indices])
print(distances)

[[[1.03800476 0.55861082 1.10378283 1.18556721]
  [0.79566902 0.32841405 0.76275827 1.05393502]]]

[[0.49140089 0.74294782]]

4.3 创建一个KNN分类器

from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler

# 加载数据
iris = datasets.load_iris()
x = iris.data
y = iris.target

# 创建standardizer
standardizer = StandardScaler()

# 标准化特征
x_std = standardizer.fit_transform(x)

# 训练一个有5各邻居的KNN分类器
knn = KNeighborsClassifier(n_neighbors=5, n_jobs=-1).fit(x_std, y)

# 创建两个观察值
new_observation = [[1, 1, 1, 1],
                   [0.75, 0.75, 0.75, 0.75]]

# 预测这两个观察值的分类
print(knn.predict(new_observation))

# 查看每个观察值分别属于3个分类中的某一个概率
print(knn.predict_proba(new_observation))

[2 1]
[[0.  0.  1. ]
 [0.  0.6 0.4]]

【说明】：参数n_neighbors：设置邻居个数；参数n_jobs：设置使用多少个CPU内核

5.最佳K值

1)较小的K值：就相当于用较小的领域中的训练实例进行预测，“学习“近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合。

2)较大的K值：就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远(不相似的)训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。

3)K=N (N为训练样本个数)：则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用信息。

在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证波(简单来说，就是把训练数据在分成两组:训练集和验证集)来选择最优的K值。

from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline, FeatureUnion
from sklearn.model_selection import GridSearchCV

# 加载数据
iris = datasets.load_iris()
features = iris.data
target = iris.target

# 创建standardizer
standardizer = StandardScaler()
# 标准化特征
features_std = standardizer.fit_transform(features)

# 创建一个有5个邻居的KNN分类器
knn = KNeighborsClassifier(n_neighbors=5, n_jobs=-1)

# 创建一个流水线
pipe = Pipeline([("standardizer", standardizer), ("knn", knn)])
# 确定一个可选范围
search_space = [{"knn__n_neighbors": [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]}]
# 创建grid搜索
classifier = GridSearchCV(pipe, search_space, cv=5, verbose=0).fit(features_std, target)

# 查看最佳k值
print("最佳k值是: ", classifier.best_estimator_.get_params()["knn__n_neighbors"])

最佳k值是:  6

6.数据集基本操作及特征工程

sklearn.datasets中已经存在一部分小数据集，可以通过datasets.load_XXX()来载入小数据、datasets.fetch_XXX()从网络下载大数据集。

6.1查看数据集属性

from sklearn.datasets import load_iris

# 载入数据集
iris = load_iris()

# 获取数据集属性
# print("数据集特征值：\n", iris.data)
print("数据集目标值：\n", iris["target"])
print("数据集特征值名字：\n", iris.feature_names)
print("数据集目标值名字：\n", iris.target_names)
# print("数据集数据集的描述：\n", iris.DESCR)

数据集目标值：
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2
 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 2 2]
数据集特征值名字：
 ['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']
数据集目标值名字：
 ['setosa' 'versicolor' 'virginica']

6.2数据集可视化

import seaborn as sns
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.datasets import load_iris

iris = load_iris()

iris_d = pd.DataFrame(iris['data'], columns=['Sepal_Length', 'Sepal_Width', 'Petal_Length', 'Petal_Width'])
iris_d['target'] = iris.target

# 参数fit_reg=False：不连接
def iris_plot(data, col1, col2):
    sns.lmplot(x=col1, y=col2, data=data, hue='target', fit_reg=False)
    plt.title('Sepal_Width AND Petal_Length')
    plt.show()

iris_plot(iris_d, 'Sepal_Width', 'Petal_Length')
# iris_plot(iris_d, 'Sepal_Length', 'Petal_Width')