机器学习之KNN算法

简单的机器学习算法K-近邻算法，即KNN算法。

最近加入了一个机器学习小组，目标是每周学习并输出一篇机器学习的文章，第一周的算法是KNN算法。

KNN算法属于监督学习，必须有结果集进行训练。

一、KNN介绍

kNN(k-NearestNeighbor)，也就是k最近邻算法，K最近邻，就是k个最近的邻居的意思。也就是在数据集中，认为每个样本可以用离他最距离近的k个邻居来代表。假设我们要判断x点是什么颜色的，找到与其距离最近的5个点，有4个是红色的，有1个是绿色的。因此我们认为x是属于红色的集合。

定义如下：

在一个给定的类别已知的训练样本集中，已知样本集中每一个数据与所属分类的对应关系（标签）。在输入不含有标签的新样本后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似的k个数据(最近邻)的分类标签。通过多数表决等方式进行预测。即选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
K近邻法不具有显式的学习过程，而是利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。

二、优缺点

优点：

KNN算法是机器学习的敲门砖，算法思想简单朴素，容易理解，适合入门。
很好用，理论成熟，简单粗暴，既可以用来做分类（天然支持多分类），也可以用来做回归。
与朴素贝叶斯之类的算法相比，由于其对数据没有假设，因此准确度高，对异常点不敏感。

缺点：

不知道

三、算法流程

通过理解算法思想，可以将其简化为“找邻居+投票”。K近邻法使用的模型，实际上是特征空间的划分。模型由三个基本要素决定：

距离度量
k值
分类决策规则

其中两个实例点之间的距离反映了相似程度。一般来说使用欧氏距离来计算。

梳理kNN算法流程如下：

计算测试对象到训练集中每个对象的距离
按照距离的远近排序
选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居
统计这k个邻居的类别频次
k个邻居里频次最高的类别，即为测试对象的类别

四、算法实现

案例：使用KNN算法对病人的肿瘤进行分类，训练集如下：

导入数据集

数据集展示

# 导入需要的数据模块
import numpy as np
import matplotlib.pyplot as plt
# raw_data_x是特征，raw_data_y是标签，0为良性，1为恶性
raw_data_X = [[3.393533211, 2.331273381],
              [3.110073483, 1.781539638],
              [1.343853454, 3.368312451],
              [3.582294121, 4.679917921],
              [2.280362211, 2.866990212],
              [7.423436752, 4.685324231],
              [5.745231231, 3.532131321],
              [9.172112222, 2.511113104],
              [7.927841231, 3.421455345],
              [7.939831414, 0.791631213]
             ]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

# 设置训练组
X_train = np.array(raw_data_X)
y_train = np.array(raw_data_y)

# 将数据可视化
plt.scatter(X_train[y_train==0,0],X_train[y_train==0,1], color='g', label = 'Tumor Size')
plt.scatter(X_train[y_train==1,0],X_train[y_train==1,1], color='y', label = 'Time')
plt.xlabel('Tumor Size')
plt.ylabel('Time')
plt.axis([0,10,0,5])
plt.show()

Snipaste_2020-05-17@13_17

横轴是肿块大小，纵轴是发现时间。每个病人的肿块大小和发病时间构成了二维平面特征中的一个点。对于每个点，我们通过label明确是恶性肿瘤（绿色）、良性肿瘤（黄色）。

接下来使用KNN计算肿瘤患者的数据（样本点）x：[8.90933607318, 3.365731514]，是良性肿瘤还是恶性肿瘤。

1、求距离

使用欧式距离计算距离

输出结果

x=np.array([8.90933607318,3.365731514])
x
distances = [] #记录x到样本数据集中每个点的距离
for xtrain in X_train:
    d = np.sqrt(np.sum((xtrain-x)**2))
#     print(xtrain)
#     print(x)
#     print(d)
    distances.append(d)
distances

# 结果为：
[5.611968000921151,
 6.011747706769277,
 7.565483059418645,
 5.486753308891268,
 6.647709180746875,
 1.9872648870854204,
 3.168477291709152,
 0.8941051007010301,
 0.9830754144862234,
 2.7506238644678445]

2、对距离进行排序

# 对数组距离进行排序
nearest = np.argsort(distances) # 返回数组中从小到大的索引值
nearest

#输出：
array([7, 8, 5, 9, 6, 3, 0, 1, 4, 2], dtype=int64)

3、选择K值

# 选择K值，找出最近的6个点（top 6），并记录他们的标签值（y）
k = 6
topK_y = [y_train[i] for i in nearest[:k]]
topK_y

# 结果为
[1, 1, 1, 1, 1, 0]

4、投票决策并输出结果

# 大数规则进行决策，谁多谁胜
from collections import Counter
votes = Counter(topK_y)
votes

# 输出：
Counter({1: 5, 0: 1})

# Counter.most_common(n) 找出票数最多的n个元素，返回的是一个列表，列表中的每个元素是一个元组，元组中第一个元素是对应的元素是谁，第二个元素是频次
predict_y = votes.most_common(1)
predict_y

# 输出：
[(1, 5)]

# 输出预测结果，为1
predict_y[0][0]

# 输出：
1

5、完整KNN代码及调用

完整KNN代码

调用KNN.py

## 完整KNN代码
import numpy as np
from collections import Counter
class KNNClassifier:
    def __init__(self,k):
        """初始化分类器"""
        assert k >=1 ,'k must be valid'
        self.k = k
        self._X_train = None
        self._y_train = None
        
    def fit(self, X_train, y_train):
        """根据训练数据集X_train和y_train训练kNN分类器"""
        assert X_train.shape[0] == y_train.shape[0], \
            "the size of X_train must be equal to the size of y_train"
        assert self.k <= X_train.shape[0], \
            "the size of X_train must be at least k"
        
        self._X_train = X_train
        self._y_train = y_train
        return self
    def predict(self,X_predict):
        """给定待预测数据集X_predict，返回表示X_predict结果的向量"""
        assert self._X_train is not None and self._y_train is not None, \
            "must fit before predict!"
        assert X_predict.shape[1] == self._X_train.shape[1], \
            "the feature number of X_predict must be equal to X_train"
        y_predict = [self._predict(x) for x in X_predict]
        return np.array(y_predict)

    def _predict(self, x):
        distances = [np.sqrt(np.sum((x_train - x) ** 2)) for x_train in self._X_train]
        nearest = np.argsort(distances)
        topK_y = [self._y_train[i] for i in nearest]
        votes = Counter(topK_y)
        return votes.most_common(1)[0][0]

    def __repr__(self):
        return "kNN(k=%d)" % self.k

%run kNN.py

knn_clf = KNNClassifier(k=6)
knn_clf.fit(X_train, y_train)
X_predict = x.reshape(1,-1)
y_predict = knn_clf.predict(X_predict)
y_predict

# 输出：
array([1])

6、sklearn使用

# sklearn中调用knn算法
from sklearn.neighbors import KNeighborsClassifier

# 创建kNN_classifier实例
kNN_classifier = KNeighborsClassifier(n_neighbors=6)

# kNN_classifier做一遍fit(拟合)的过程，没有返回值，模型就存储在kNN_classifier实例中
kNN_classifier.fit(X_train, y_train)

# kNN进行预测predict，需要传入一个矩阵，而不能是一个数组。reshape()成一个二维数组，第一个参数是1表示只有一个数据，第二个参数-1，numpy自动决定第二维度有多少
y_predict = kNN_classifier.predict(x.reshape(1,-1))
y_predict

# 输出：
array([1])

7、sklearn相关参数

KNN参数：

n_neighbors: int, 可选参数(默认为 5)。用于kneighbors查询的默认邻居的数量

weights（权重）: str or callable(自定义类型), 可选参数(默认为 ‘uniform’)。用于预测的权重参数，可选参数如下：

uniform : 统一的权重. 在每一个邻居区域里的点的权重都是一样的。
distance : 权重点等于他们距离的倒数。使用此函数，更近的邻居对于所预测的点的影响更大。
[callable] : 一个用户自定义的方法，此方法接收一个距离的数组，然后返回一个相同形状并且包含权重的数组。
algorithm（算法）: {‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, 可选参数（默认为 'auto'）。计算最近邻居用的算法：ball_tree 使用算法BallTree、kd_tree 使用算法KDTree、brute 使用暴力搜索、auto 会基于传入fit方法的内容，选择最合适的算法。注意 : 如果传入fit方法的输入是稀疏的，将会重载参数设置，直接使用暴力搜索。

leaf_size（叶子数量）: int, 可选参数(默认为 30)。传入BallTree或者KDTree算法的叶子数量。此参数会影响构建、查询BallTree或者KDTree的速度，以及存储BallTree或者KDTree所需要的内存大小。此可选参数根据是否是问题所需选择性使用。

p: integer, 可选参数(默认为 2)。用于Minkowski metric（闵可夫斯基空间）的超参数。p = 1, 相当于使用曼哈顿距离，p = 2, 相当于使用欧几里得距离]，对于任何 p ，使用的是闵可夫斯基空间。

metric（矩阵）: string or callable, 默认为 ‘minkowski’。用于树的距离矩阵。默认为闵可夫斯基空间，如果和p=2一块使用相当于使用标准欧几里得矩阵. 所有可用的矩阵列表请查询 DistanceMetric 的文档。

metric_params（矩阵参数）: dict, 可选参数(默认为 None)。给矩阵方法使用的其他的关键词参数。

n_jobs: int, 可选参数(默认为 1)。用于搜索邻居的，可并行运行的任务数量。如果为-1, 任务数量设置为CPU核的数量。不会影响fit

对于KNeighborsClassifier的方法：

方法名	含义
fit(X, y)	使用X作为训练数据，y作为目标值（类似于标签）来拟合模型。
get_params([deep])	获取估值器的参数。
neighbors([X, n_neighbors, return_distance])	查找一个或几个点的K个邻居。
kneighbors_graph([X, n_neighbors, mode])	计算在X数组中每个点的k邻居的（权重）图。
predict(X)	给提供的数据预测对应的标签。
predict_proba(X)	返回测试数据X的概率估值。
score(X, y[, sample_weight])	返回给定测试数据和标签的平均准确值。
set_params(**params)	设置估值器的参数。

五、拓展

KNN 不仅可以做分类，还可以做回归。首先讲下什么是回归。在数据分析实战案例中，如
果想要对未知电影进行类型划分，这是一个分类问题。首先看一下要分类的未知电影，离
它最近的 K 部电影大多数属于哪个分类，这部电影就属于哪个分类。
如果是一部新电影，已知它是爱情片，想要知道它的打斗次数、接吻次数可能是多少，这
就是一个回归问题。
那么 KNN 如何做回归呢？
对于一个新点，我们需要找出这个点的 K 个最近邻居，然后将这些邻居的属性的平均值赋
给该点，就可以得到该点的属性。当然不同邻居的影响力权重可以设置成不同的。举个例
子，比如一部电影 A，已知它是动作片，当 K=3 时，最近的 3 部电影是《战狼》，《红
海行动》和《碟中谍 6》，那么它的打斗次数和接吻次数的预估值分别为
(100+95+105)/3=100 次、(5+3+31)/3=13 次。

同样 KNN 也可以用于推荐算法，虽然现在很多推荐系统的算法会使用 TD-IDF、协同过
滤、Apriori 算法，不过针对数据量不大的情况下，采用 KNN 作为推荐算法也是可行的。

六、应用

待完成：

入门：KNN算法来做最普通的水仙花分类

算法进阶：KNN算法做手写数字识别https://blog.csdn.net/UFv59to8/article/details/80241272?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

最后

附上Jupyter Notebook文件：

KNN算法.html