一起读《机器学习算法与实现 —— Python编程与应用实例》- 第4章 k最近邻算法

硬核王同学

一起读《机器学习算法与实现 —— Python编程与应用实例》- 第4章 k最近邻算法 [复制链接]

机器学习中有一种最基本的任务，就是分类。指将数据样本映射到一个已事先定义的类别中的学习过程，即生成一个分类函数或分类模型，将每个数据样本分配到某个定义好的类别中。

本章就先介绍一种最基本的分类方法：k最近邻算法。它既能用于分类，又能用于回归。

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

这句话很绕啊，我个人理解，给定一个k范围内，你和谁身上的特点相似的地方更多，你就属于哪种类型。比如我们都是黑头发、黄皮肤、黑眼睛，我们就更属于亚洲人，而不属于非洲人~

 

一、K最近邻原理

这里作者也做举了一个很形象的例子：

 

如图，如果要确定Xu是属于w1，w2还是w3，如果k取5，那么只需要统计，与它最近的5个点的距离。

如图所示，其中Xu有4个点是最靠近红色（w1），那么Xu就确定属于为红色（w1）。

而实际应用中，样本不可能会如此简单，书中做了其他特殊情况的描述，如果碰到了复杂问题可以再从书中进行深入了解。

 

特征距离计算

在k最近邻算法中，需要比较给定样本到其他样本的特征距离，因此要引入特征空间中的距离度量方式。在机器学习中有几种常用的，曼哈顿距离、欧氏距离等。k最近邻算法使用的通常是欧式距离。

在二维空间中，两个点之间的欧氏距离计算公式为：

 

在二维空间其实就是计算 (p1,p2)(p1,p2) 和 (q1,q2)(q1,q2) 的距离。拓展到多维空间，则公式变成：

 

k最近邻算法的本质是，计算待预测样本到所有已知样本的距离，然后对计算得到的距离排序，选出距离最小的k个值，看哪些类别比较多。

 

二、机器学习的思维模型

学习knn算法的原理和实现时，需要思考机器学习解决问题的思维方式，即在给定问题后，如何思考并解决机器学习问题。从问题到测试，机器学习的思维模型如下所示：

 

上图是机器学习的经典的流程

• 问题：我们需要解决的问题是什么？用什么表达待解决问题的关键要素？

• 核心思想： 通过什么手段解决问题？

• 数学理论： 如何构建数学模型，使用什么数学方法？

• 算法： 如何将数学理论、处理流程转化成计算机可以实现的算法？

• 编程： 如何把算法变成可以计算机执行的程序？

• 测试: 如何使用训练、测试数据来验证算法？

• 深入思考：所采用的方法能够取得什么效果，存在什么问题，如何改进？

 

三、数据生成

采用机器学习解决问题时，编程的第一步是生成并整理训练数据和测试数据，然后可视化这些数据。观察数据在特征空间中的分布，可以大致了解数据的特性。

因此先生成一些训练数据和测试数据，如下所示：

先打开Jupyter ，创建一个KNN的文件

%matplotlib inline

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()

以上代码分别从以（4,4）为中心和（10,10）为中心的两个不同高斯分布中抽取100个样本点。来自不同高斯分布的样本点属于不同的类。合并样本后，打乱顺序，取前70%作为训练数据，取后30%作为测试数据，同时可视化数据点的分布，结果如下所示：

训练数据：

 

测试数据：

 

 

四、程序实现

结合算法步骤，k最近邻算法的实现分为三步：

1.计算距离

kNN_distance()函数：计算测试数据与各个训练数据之间的距离。

 

2.按距离取样本点

kNN_vote()函数：确定k个点中不同类别的出现频率，返回其中出现频率最高的类别作为测试数据的预测类别。

 

3.投票决定类别。

调用kNN_distance()函数计算距离，对距离排序后，选取距离最小的k个点，在调用kNN_vote()函数得到预测类别。

 

具体算法实现：

import numpy as np
import operator

# -------程序实现
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函数来直接返回值最大的键
    maxk =  max(vote_dict, key=lambda k: vote_dict[k])
    return maxk

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_est = [kNN_predict(x_train[i], x_train, y_train) for i in range(len(x_train))]

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

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

# 对测试集的样本进行分类
y_test_est = [kNN_predict(x_test[i], x_train, y_train,3) 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)
print(n_correct,len(x_test))

输出为：

Train Accuracy: 100.000000%
Test Accuracy: 96.666667%
58 60

上述程序，先后对训练数据和测试数据应用kNN算法，并将分类结果与实际标签对比，发现分类准确性分别达到了100%和96.67%，说明kNN算法对数量少的简单数据具有优秀的分类能力。

 

五、将kNN算法封装为类

当我们想复用自己写的kNN算法，且进一步改进算法，可以将其封装为类。使用类分装程序的最大优点如下：1.统一调用API接口，让调用者更方便地集成各种算法；2.将数据和操作集成在一起，降低阅读和理解代码的难度。

下面是实现这一思路的简要描述，具体实现大家可以看书。

__init__()和fit()函数：分别用于存储初始化kNN类的k值和分类前已有的含标签数据。

_square_distance()、_vote()和predice()函数：与函数实现版本kNN_distance()、kNN_vote()和kNN_predict()的功能相同，区别是前者是基于类的方法，可以调用类存储的训练数据。

score()函数：计算分类结果的准确度。

 

六、基于sklearn的分类实现

动手编程实现的kNN分类器有些细节还不完美。例如：1.未优化算法，当数据量较大时，算法的效率很低；2.通用性较差。解决实际问题时，可以使用比较成熟的机器学习库，如传统学机器学习领域中著名的scikit-learn（也称sklearn），这个库包括了大部分机器学习方法，涵盖了几乎所有的主流机器学习算法，是基于Python语言的开源机器学习工具包，可通过NumPy，SciPy和Matplotlib等Python数值计算库高效地实现算法应用。sklearn中的k近邻分类器是KNeighborsClassifier。

书中通过一个实例讲解如何对sklearn中包含的手写字体数据集digits进行kNN分类，感兴趣的可以看书自行了解。

 

总结

本章讲述了k最近邻算法的原理和实现，还介绍了如何使用sklearn来进行kNN的识别实现。通过学习，初步掌握了k最近邻算法的原理和实现，了解了真正的机器学习算法的神奇之处。除此之外，还有很多其他的机器学习算法可以供我们学习。比如下章的k均值聚类算法！

 

Jacktang

我个人理解，给定一个k范围内，你和谁身上的特点相似的地方更多，你就属于哪种类型。比如我们都是黑头发、黄皮肤、黑眼睛，我们就更属于亚洲人，而不属于非洲人~

 

哈哈，通俗易懂