[分享] 《机器学习算法与实现》1、k最近邻算法

一、本书介绍

在正式开始之前还是想先介绍以下这本书，本书的名称是《机器学习算法与实现——Python编程与应用实例》，作者布树辉是西北工业大学的教授，也是很厉害的人物。

本书总共有11章，我觉得主要可以分为3大块，第一部分是Python语言的基础知识；第二部分是机器学习的基础算法及实现；第三部分为深度学习及目标检测。

从内容可以看出来，本书层次感非常强，由浅入深，循序渐进。

另外，本书还配有视频教程和电子档的资料，b站就能免费观看。

最后，本书的质感还是可以的，彩版印刷，看起来相当舒服。

二、KNN算法介绍

书籍的基本信息介绍完毕后我们开始切入正体，这篇主要来学习机器学习中最简单的算法：k最近邻算法。有的书本上也叫做k近邻算法，我觉得叫做k最近邻算法更准确，因为英文原文是k-Nearest Neighbor，简称KNN。

KNN既可以用来解决分类问题，也可以用来解决回归问题。

KNN的核心思想是：通过度量给定样本到训练集中所有样本的特征距离，将与给定样本特征距离最近的k个样本中出现次数最多的类别指定为该样本最优估计的类别。

我的理解是：如果想要确定某个样本x属于那一种类型，只需要看与之最近的k个样本的类型，然后找出最多的那个类型，那么x就属于这个类型，其中k需要根据实际情况来选取。

如图，如果要确定Xu是属于w1,w2还是w3,如果k取5,那么只需要统计与它最近的5个点的属性，其中4个是红色（w1），那么Xu就确定为红色（w1）。

没错KNN算法就是这么简单，所以KNN算法基本上只涉及到欧式距离的计算。

三、数据生成

在正式编写算法之前，首先需要准备数据，接下来，我们自己通过python生成一些模拟数据。

import numpy as np
import matplotlib.pyplot as plt

# 生成模拟数据
np.random.seed(314)

data_size1 = 100

x1 = np.random.randn(data_size1, 2) + np.array([4,4])
y1 =[0 for _ in range(data_size1)]

data_size2 = 100

x2 = np.random.randn(data_size2, 2) * 2 + np.array([10, 10])
y2 = [1 for _ in range(data_size2)]

# 合并生成全部数据
x = np.concatenate((x1, x2), axis=0)
y = np.concatenate((y1, y2), axis=0)

data_size_all = data_size1 + data_size2
shuffled_index = np.random.permutation(data_size_all)
x = x[shuffled_index]
y = y[shuffled_index]

# 分割训练集和测试集
split_index = int(data_size_all * 0.7)
x_train = x[:split_index]
y_train = y[:split_index]
x_test = x[split_index:]
y_test = y[split_index:]


# 绘制结果
plt.scatter(x_train[:,0], x_train[:,1], c= y_train, marker='.')
plt.title("训练数据")
plt.show()

plt.scatter(x_test[:,0], x_test[:,1], c= y_test, marker='.')
plt.title("测试数据")
plt.show()

详细的python代码就不一一解释了，都是python语法，代码运行后，就会分别生成训练集和测试集，训练集占70%，测试集占30%，训练集+测试集一共200个。

数据可视化：

这个是训练集：
 

这个是测试集：

四、程序实现

数据准备好后，就可以尝试自己实现该程序了。

正式开始之前，再来梳理一下思路：

1、计算测试数据与个训练数据之间的距离

2、确认k个点中不同类别出现的频率，出现最多的的类即为测试数据的类别

可以实现三个函数，kNN_distance, kNN_vote,kNN_predict分别计算距离，投票，和预测。

# -------程序实现
def kNN_distance(v1, v2):
    '''计算两个多维向量的距离'''
    return np.sum(np.square(v1 - v2))

def kNN_vote(ys):
    '''根据ys的类别, 挑选类别最多的一类作为输出'''
    vote_dict = {}
    for y in ys:
        if y not in vote_dict.keys():
            vote_dict[y] = 1
        else:
            vote_dict[y] += 1

    # 找到类别最多的一类,也可以用循环遍历的方式来找，这里使用了max函数来直接返回值最大的键
    max_key =  max(vote_dict, key=lambda k: vote_dict[k])
    return max_key

def kNN_predict(x, train_x, train_y, k=3):
    '''
    针对指定的数据进行分类，参数：
    x - 输入的待分类样本
    train_x - 训练数据的样本
    train_y - 训练数据的标签
    k - 最近邻的样本数
    '''
    dist_arr = [kNN_distance(x, train_x[j]) for j in range(len(train_x))]
    sorted_index = np.argsort(dist_arr)
    top_k_index = sorted_index[:k]
    ys = train_y[top_k_index]
    return kNN_vote(ys)

然后分别对训练集和测试集进行预测，并计算精度：
 

 对训练集的样本进行分类
y_train_test = [kNN_predict(x_train[i], x_train, y_train) for i in range(len(x_train))]
print(y_train_test)

# 统计训练精度
n_correct = 0
for i in range(len(x_train)):
    if y_train_test[i] == y_train[i]:
        n_correct += 1

accuracy = n_correct / len(x_train) * 100.0
print("Train Accuracy: %f%%" % accuracy)

# 对测试集的样本进行分类
y_train_test = [kNN_predict(x_test[i], x_train, y_train) for i in range(len(x_test))]

# 统计训练精度
n_correct = 0
for i in range(len(x_test)):
    if y_train_test[i] == y_test[i]:
        n_correct += 1

accuracy = n_correct / len(x_test) * 100.0
print("Test Accuracy: %f%%" % accuracy)

运行结果：

Train Accuracy: 100.000000%
Test Accuracy: 96.666667%

五、其它

上面我们自己实现了KNN算法，但是自己实现的算法总规不是那么完美，比如在运行效率上面可能不是太好，数据量很大的时候会非常慢。

其实有很多机器学习框架都提供了非常好用的常用算法接口，比如sklearn，可以直接调用，并不需要重复造轮子，我们自己尝试实现KNN算法更多地是为了加深对KNN算法的理解。

关于sklearn的例子，书中也有描述和代码，这里就不照搬了。

大概意思就是如果要确定一个人说什么语言，只需要看他几个邻居说什么语言就能预测出他说什么语言

这挺好的，现在很流行这些算法，不知道从哪里可以拿到入门的学习资料。

个人理解：

已有多个类别，现在一个新sample，它该分在哪个类别里呢？

KNN的做法就是，让这个新sample和所有样本求距离，然后根据距离升序排序，最前面的K个样本中，哪个类别的样本数最多，新sample就加入那个类别。

问题是，K到底选多少为宜呢？

k的选取确实很重要，不能太大，也不能太小，只能根据实际情况动态去调整

看的还是有点云里雾里的，很迷茫，看来还没有入门

可以去b站看看视频教程

原理不难，但是距离函数的选取很重要，严重影响结果和性能。

距离公式我还停留在初等数学的距离公式上，如果关键在于它，那它一定还有多种选择了？

看来都是高手啊

这挺好的，现在很流行这些算法，不知道从哪里可以拿到入门的学习资料

可以留意一下论坛的书籍评测活动

有什么推荐的视频课吗，这些算法在实际应用中有什么好的使用吗

搜索一下，有很多讲机器学习的视频

好好，多谢啦。我去找找看看试试吧。还得多学习学习

《机器学习算法与实现》值得好好学习体会，多谢提供