[机器学习实战] k-近邻算法

机器学习实战 系列参考于互联网资料与 人民邮电出版社 《机器学习实战》，编写目的在于学习交流，如有侵权，请联系删除

k-近邻算法概述

k-近邻算法概述

优点：精度高、对异常值不敏感、无数据输入假定

缺点：计算复杂度高、空间复杂度高

适用数据范围：数值型和标称型

k-近邻算法 (kNN)，存在一个样本数据集合，也称为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系，输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类

例如电影，区分爱情片和动作片，有人曾经统计过很多电影的打斗镜头和接吻镜头，假设有一部未看过的电影，如何确定它是爱情片还是动作片呢

电影名称	打斗镜头	接吻镜头	电影类型
California Man	3	104	爱情片
He’s Not Really into Dudes	2	100	爱情片
Beautiful Woman	1	81	爱情片
Kevin Longblade	101	10	动作片
Robo Slayer 3000	99	5	动作片
Amped II	98	2	动作片
?	18	90	未知

即使不知道未知电影属于那种类型，我们也可以通过某种方法计算出来。首先计算未知电影与样本集中其他电影的距离，在后面会给出 计算方法

已知电影与未知电影的距离

电影名称	与未知电影的距离
California Man	20.5
He’s Not Really into Dudes	18.7
Beautiful Woman	19.2
Kevin Longblade	115.3
Robo Slayer 3000	117.4
Amped II	118.9

现在我们得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到k个距离最近的电影。假定 k=3 ，那么最靠近的电影依次是 He’s Not Really into Dudes 、Beautiful Woman 和 California Man

k-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此我们判定未知电影是爱情片

• k-近邻算法的一般流程
  • 收集数据
    • 可以使用任何方法
  • 准备数据
    • 距离计算所需要的数值，最好是结构化的数据格式
  • 分析数据
    • 可以使用任何方法
  • 训练算法
    • 此步骤不适用于 k-近邻算法
  • 测试算法
    • 计算错误率
  • 使用算法
    • 首先需要输入样本数据和机构化的输出结果，然后运行 k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理

使用 Python 导入数据

创建 kNN.py 模块，并编写内容

from numpy import *
import operator


def create_data_set():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

create_data_set 创建数据集合标签

import kNN
group, labels = kNN.create_data_set()
group
Out[11]: 
array([[1. , 1.1],
       [1. , 1. ],
       [0. , 0. ],
       [0. , 0.1]])
labels
Out[12]: ['A', 'A', 'B', 'B']

这里有4组数据，每组数据有两个我们已知的属性或者特征值

如点 (1, 1.1) 定义为类 A， (0, 0.1) 定义为类 B

实施 kNN 分类算法

• 对未知类别属性的数据集中的每个点依次执行下面的操作
  1. 计算已知类别数据集中的点与当前点之间的距离
  2. 按照距离递增次序排序
  3. 选取与当前点距离最小的k个点
  4. 确定前k个点所在类别的出现频率
  5. 返回前k个点出现频率最高的类别作为当前点的预测分类

def classify0(in_x, data_set, labels, k_v):
    data_set_size = data_set.shape[0]
    diff_mat = tile(in_x, (data_set_size, 1)) - data_set  # 距离计算                              
    sq_diff_mat = diff_mat ** 2  # 距离计算  
    sq_distances = sq_diff_mat.sum(axis=1)  # 距离计算              
    distances = sq_distances ** 0.5  # 距离计算        
    sorted_dist_indices = distances.argsort()
    class_count = {}
    for i in range(k_v):  # 选取距离最小的k个点
        vote_i_label = labels[sorted_dist_indices[i]]  # 选取距离最小的k个点
        class_count[vote_i_label] = class_count.get(vote_i_label, 0) + 1  # 选取距离最小的k个点
    sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)  # 排序
    return sorted_class_count[0][0]

classify0 有4个输入参数: 用于分类的输入向量是in_x，输入的训练样本集为data_set，标签向量为labels，最后的参数 k 表示用于选择最近邻居的数目，其中标签向量的元素数目和矩阵 data_set 的行数相同

使用欧式距离公式，计算两个向量点

$d=\sqrt{(xA_0-xB_0)^2+(xA_1-xB_1)^2}$

例如，点(0, 0)与(1, 2)之间的距离计算为

$\sqrt{(1-0)^2+(2-0)^2}$

如果数据集存在4个特征值，则点（1,0,0,1）与（7,6,9,4) 之间的距离计算为：

$\sqrt{(7-1)^2+(6-0)^2+(9-0)^2+(4-1)^2}$

计算完所有点之间的距离后，可对数据按照从小到大的次序排序。然后，确定前k个距离最小元素所在的主要分类，输入k总是正整数；最后，将 class_count 字典分解为元组列表，然后使用 itemgetter 方法，按照第二个元素的次序对元组进行排序，这里使用逆序，按照从大到小的次序排序，最后返回发生频率最高的元素标签

为了预测数据所在的分类，下面测试

kNN.classify0([0, 0], group, labels, 3)

输出的结果应该是 B

使用 k-近邻算法改进约会网站的配对效果

海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她并不是喜欢每一个人。经过一番总结，她发现曾经交往过三种类型的人：

• 不喜欢的人
• 魅力一般的人
• 极具魅力的人

因此，现在拟定的计划步骤为：

• 收集数据
  • 提供文本文件
• 准备数据
  • 使用 Python 解析文本文件
• 分析数据
  • 使用 Matplotlib 画二维扩散图
• 训练算法
  • 此步骤不适用于 k-近邻算法
• 测试算法
  • 使用海伦提供的部分数据作为测试样本
  • 测试样本和非测试样本的区别在于：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误
• 使用算法
  • 产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型

准备数据：从文本文件中解析数据

海伦收集约会数据已经有了一段时间，她把这些数据放到文本文件 datingTestSet2.txt 中，每个样本数据占据一行，总共有 1000 行，海伦的样本主要包含以下 3 种特征:

• 每年获得的飞行常客里程数
• 玩视频游戏所耗时间百分比
• 每周消费的冰激淋公升数

在将上述数据输入到分类器之前，必须将待处理的数据格式改变为分类器可以接受的格式，在 kNN.py 中创建名为 file2matrix 的函数，以此来处理输入格式问题。该函数的输入为文件名字符串，输出为训练样本矩阵和类标签向量

def file2matrix(filename):
    fr = open(filename)
    number_of_lines = len(fr.readlines())  # 得到文件的行数
    return_mat = zeros((number_of_lines, 3))  # 创建返回的 Numpy 矩阵
    class_label_vector = []  # 准备返回的标签
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        list_from_line = line.split('\t')
        return_mat[index, :] = list_from_line[0:3]
        class_label_vector.append(int(list_from_line[-1]))
        index += 1
    return return_mat, class_label_vector

在 Python 命令行输入以下命令：

import kNN
datingDataMat, datingLabels = kNN.file2matrix('datingTestSet2.txt')

导入以后，可以检查一下数据

datingDataMat
Out[4]: 
array([[4.0920000e+04, 8.3269760e+00, 9.5395200e-01],
       [1.4488000e+04, 7.1534690e+00, 1.6739040e+00],
       [2.6052000e+04, 1.4418710e+00, 8.0512400e-01],
       ...,
       [2.6575000e+04, 1.0650102e+01, 8.6662700e-01],
       [4.8111000e+04, 9.1345280e+00, 7.2804500e-01],
       [4.3757000e+04, 7.8826010e+00, 1.3324460e+00]])
datingLabels[0: 20]
Out[5]: [3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 3]

现在已经从文本文件中导入了数据，并将其格式化为想要的格式，接着我们需要了解数据的真实含义。一般来说，会采用图形化的方式直观地展示数据

分析数据：使用 Matplotlib 创建散点图

在 Python 命令行中输入：

import matplotlib
import matplotlib.pyplot as plt
fig = plt.figure()
ax = fig.add_subplot(111)
ax.scatter(datingDataMat[:,1], datingDataMat[:,2])
Out[10]: <matplotlib.collections.PathCollection at 0x289ec765348>
plt.show()

得到以下的图，散点图使用 datingDataMat 矩阵的第二、三列数据，x 轴表示 “玩视频游戏所耗时间百分比” y 轴表示 “每周消耗的冰激凌公升数”

由于没有使用样本分类的特征值，无法看到任何有用的数据模式信息。一般来说，我们会采用色彩或其他的记号来标记不同分类，以便更好地理解数据信息。Matplotlib 提供的 scatter 函数支持个性化标记散点图上的点，重新输入上面的代码，调用 scatter 函数

from numpy import *
import kNN
import matplotlib
import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.add_subplot(111)
datingDataMat, datingLabels = kNN.file2matrix('datingTestSet2.txt')
# ax.scatter(datingDataMat[:,1], datingDataMat[:,2])
ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0 * array(datingLabels), 15.0 * array(datingLabels))
ax.axis([-2, 25, -0.2, 2.0])
plt.xlabel('Percentage of Time Spent Playing Video Games')
plt.ylabel('Liters of Ice Cream Consumed Per Week')
plt.show()

得到的图如下

上图虽然也可以区别数据，但是下图采用矩阵的第一和第二列属性却可以得到更好的展示效果，图中清晰地表示了三个不同的样本分类区域，具有不同爱好的人其类别区域也不同

from numpy import *
import matplotlib
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle

n = 1000  # number of points to create
x_cord1 = []
y_cord1 = []
x_cord2 = []
y_cord2 = []
x_cord3 = []
y_cord3 = []
markers = []
colors = []
fw = open('testSet.txt', 'w')
for i in range(n):
    [r0, r1] = random.standard_normal(2)
    myClass = random.uniform(0, 1)
    if myClass <= 0.16:
        f_Flier = random.uniform(22000, 60000)
        tats = 3 + 1.6 * r1
        markers.append(20)
        colors.append(2.1)
        classLabel = 1  # 'didntLike'
        x_cord1.append(f_Flier)
        y_cord1.append(tats)
    elif (myClass > 0.16) and (myClass <= 0.33):
        f_Flier = 6000 * r0 + 70000
        tats = 10 + 3 * r1 + 2 * r0
        markers.append(20)
        colors.append(1.1)
        classLabel = 1  # 'didntLike'
        if tats < 0:
            tats = 0
        if f_Flier < 0:
            f_Flier = 0
        x_cord1.append(f_Flier)
        y_cord1.append(tats)
    elif (myClass > 0.33) and (myClass <= 0.66):
        f_Flier = 5000 * r0 + 10000
        tats = 3 + 2.8 * r1
        markers.append(30)
        colors.append(1.1)
        classLabel = 2  # 'smallDoses'
        if tats < 0:
            tats = 0
        if f_Flier < 0:
            f_Flier = 0
        x_cord2.append(f_Flier)
        y_cord2.append(tats)
    else:
        f_Flier = 10000 * r0 + 35000
        tats = 10 + 2.0 * r1
        markers.append(50)
        colors.append(0.1)
        classLabel = 3  # 'largeDoses'
        if tats < 0:
            tats = 0
        if f_Flier < 0:
            f_Flier = 0
        x_cord3.append(f_Flier)
        y_cord3.append(tats)

fw.close()
fig = plt.figure()
ax = fig.add_subplot(111)
# ax.scatter(xcord,ycord, c=colors, s=markers)
type1 = ax.scatter(x_cord1, y_cord1, s=20, c='red')
type2 = ax.scatter(x_cord2, y_cord2, s=30, c='green')
type3 = ax.scatter(x_cord3, y_cord3, s=50, c='blue')
ax.legend([type1, type2, type3], ["Did Not Like", "Liked in Small Doses", "Liked in Large Doses"], loc=2)
ax.axis([-5000, 100000, -2, 25])
plt.xlabel('Frequent Flier Miles Earned Per Year')
plt.ylabel('Percentage of Time Spent Playing Video Games')
plt.show()

准备数据：归一化数值

约会网站原始数据改进之后的样本数据：

玩视频游戏所耗时间百分比	每年获得的飞行常客里程数	每周消费的冰激凌公升数	样本分类
0.8	400	0.5	1
12	134 000	0.9	3
0	20000	1.1	2
67	32000	0.1	2

在上表中提供的 4 组数据，如果想要计算样本 3 和 样本 4 之间的距离，可以使用下面的方法：

$\sqrt{(0-67)^2+(20000-32000)^2+(1.1-0.1)^2}$

很容易发现，上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响远远大于表中其他两个特征——玩视频游戏所耗时间百分比和每周消费冰激凌公升数的影响。而产生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征值，但海伦认为这三种特征是同等的重要，因此作为三个等权重的特征之一，飞行常客里程数并不应该如此严重地影响到计算结果

在处理这种不同取值范围的特征值时，我们通常采用的方法就是将数值归一化，如将取值范围处理为 0 到 1 或者 -1 到 1 之间。下面的公式，可以将任意取值范围的特征值转化为 0 到 1 区间内的值：

newValue = (oldValue - min) / (max - min)

其中 min 和 max 分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了一个分类器的复杂度，但为了得到准确的结果，增加一个新函数 auto_norm，该函数可以自动将数字特征值转化为 0 到 1 的区间

def auto_norm(data_set):
    min_val = data_set.min(0)
    max_val = data_set.max(0)
    ranges = max_val - min_val
    norm_data_set = zeros(shape(data_set))
    m = data_set.shape[0]
    norm_data_set = data_set - tile(min_val, (m, 1))
    norm_data_set = norm_data_set / tile(ranges, (m, 1))  # 具体特征值相除
    return norm_data_set, ranges, min_val

函数 auto_norm 中，每列最小的值放在变量 min_val 中，将最大值放在变量 max_val 中，其中 data_set.min(0) 中的参数 0 使得函数可以从列中选取最小值，而不是选取当前行最小值，然后，函数计算可能的取值范围，并创建新的返回矩阵。正如前面所给出的公式，为了归一化特征，必须使用当前值减去最小值，然后除以取值范围。需要注意的是，特征值矩阵有 1000 * 3 个值，而 min_val 和 ranges 的值都为 1 x 3。为了解决这个问题，使用 Numpy 库中的 tile() 函数将变量内容复制成输入矩阵同样的大小矩阵，注意这是具体特征值相除，而对于某些数值处理软件包， / 可能意味着矩阵除法，但在 Numpy 中，矩阵除法需要使用函数 linalg.solve(matA, matB)

使用 Python 命令提示符，执行 auto_norm 函数，检测函数的执行结果

normMat, ranges, minVal = kNN.auto_norm(datingDataMat)
normMat
Out[5]: 
array([[0.44832535, 0.39805139, 0.56233353],
       [0.15873259, 0.34195467, 0.98724416],
       [0.28542943, 0.06892523, 0.47449629],
       ...,
       [0.29115949, 0.50910294, 0.51079493],
       [0.52711097, 0.43665451, 0.4290048 ],
       [0.47940793, 0.3768091 , 0.78571804]])
ranges
Out[6]: array([9.1273000e+04, 2.0919349e+01, 1.6943610e+00])
minVal
Out[7]: array([0.      , 0.      , 0.001156])

这里也可以只返回 normMat 矩阵，但是下一节将需要取值范围和最小化归一测试数据

测试算法：作为完整程序验证分类器

如果分类器满足要求，海伦就可以使用这个软件来处理约会网站的约会名单了。机器学习算法一个很重要的工作就是评估算法的正确率，通常只提供已有数据的 90% 作为训练样本来训练分类器，而使用其余的 50% 数据去测试分类器，检查分类器的正确率。50% 的测试数据应该是随机选择的，由于海伦提供的数据并没有按照特定目的来排序，所以可以随机选择 50% 数据而不影响其随机性

对于分类器来说，错误率就是分类器给出错误结果的次数除以测试数据的总数，完美分类器的错误率为 0 ，而错误率为 1 的分类器不会给出任何正确的分类结果。代码里定义一个计数器变量，每次分类器错误地分类数据，计数器就加 1， 程序执行完成后计数器的结果除以数据点总数即是错误率

为了测试分类器的效果，在 kNN.py 中创建函数 dating_class_test ，该函数是自包含的，可以在任何时候在 Python 运行环境中使用该函数测试分类器效果

def dating_class_test():
    ho_ratio = 0.50  # hold out 50%
    dating_data_mat, dating_labels = file2matrix('datingTestSet2.txt')  # load dataset from file
    norm_mat, ranges, min_val = auto_norm(dating_data_mat)
    m = norm_mat.shape[0]
    num_test_vec = int(m * ho_ratio)
    error_count = 0.0
    for i in range(num_test_vec):
        classifier_result = classify0(norm_mat[i, :], norm_mat[num_test_vec:m, :], dating_labels[num_test_vec:m], 3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifier_result, dating_labels[i]))
        if classifier_result != dating_labels[i]:
            error_count += 1.0
    print("the total error rate is: %f" % (error_count / float(num_test_vec)))
    print(error_count)

函数 dating_class_test，首先使用了 file2matrix 和 auto_norm 函数从文件中读取数据并将其转换为归一化特征值。接着计算测试向量的数量，此步决定了 norm_mat 向量中那些数据用于测试，那些数据用于分类器的训练样本；然后将这两部分数据输入到原始 kNN 分类器函数 classify0，最后函数计算错误率并输出结果。

kNN.dating_class_test()
the classifier came back with: 3, the real answer is: 3
the classifier came back with: 2, the real answer is: 2
················
the classifier came back with: 1, the real answer is: 1
the classifier came back with: 1, the real answer is: 1
the classifier came back with: 2, the real answer is: 2
the total error rate is: 0.066000

33.0

分类器处理约会数据集的错误率是 6.6% 。可以改变函数内变量 ho_ratio ，检测错误率是否随着变化值的变化而增加。依赖于分类算法，数据集和程序设置，分类器的输出结果可能有很大的不同

使用算法：构建完整可用系统

上面在数据上对分类器进行了测试，现在终于可以使用这个分类器为海伦来对人们分类，我们会给海伦一小段程序，通过该程序海伦会在约会网站上找到某个人并输入他的信息，程序会给出她对对方的喜欢程序的预测值

kNN.classify_person()
percentage of time spent playing video games ?> 10
frequent flier miles earned per year ?> 10000
liters of ice cream consumed per year ?> 0.5
You will probably like this person :  in small doses

示例：手写识别系统

简单起见，将使用 k-近邻分类器来识别数字 0-9， 需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小： 宽高是 32*32 的黑白图像，尽管采用文本格式存储图像不能有效地利用内存空间，但是为了方便理解，所以采用文本的格式

使用 k-近邻算法的手写识别系统：

• 收集数据
  • 提供文本文件
• 准备数据
  • 编写函数 img2vector()，将图像格式转换为分类器使用的向量格式
• 分析数据
  • 在 Python 命令提示符中检查数据，确保它符合要求
• 训练算法
  • 此步骤不适用于 k-近邻算法
• 测试算法
  • 编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误
• 使用算法
  • 本例没有完成此步骤

准备数据：将图像转换为测试向量

目录 trainingDigits 中包含了大约 2000 个例子，每个数字大约有 200 个样本，目录 testDigits 中包含了大约 900 个测试数据，使用目录 trainingDigits 中的数据训练分类器，使用目录 testDigits 中的数据测试分类器的效果

将 32x32 二进制图像矩阵转换为 1x1024 向量，这样前面使用的分类器就可以处理数字图像信息了

函数 img2vector ，将图像转换为向量，该函数创建 1x1024 的 Numpy 数组，然后打开给定的文件，循环读出文件的前 32 行，并将每行 32 个字符值储存在 Numpy 数组中，最后返回数组

def img2vector(filename):
    return_vec = zeros((1, 1024))
    fr = open(filename)
    for i in range(32):
        line_str = fr.readline()
        for j in range(32):
            return_vec[0, 32 * i + j] = int(line_str[j])
    return return_vec

将上述代码进行测试：

testVector = kNN.img2vector('testDigits/0_13.txt')
testVector
Out[5]: array([[0., 0., 0., ..., 0., 0., 0.]])
testVector[0, 0:31]
Out[6]: 
array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1.,
       1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])

测试算法：使用 k-近邻算法识别手写数字

def handwriting_class_test():
    hw_labels = []
    training_file_list = listdir('trainingDigits')  # 获取目录的内容
    m = len(training_file_list)
    training_mat = zeros((m, 1024))
    for i in range(m):
        file_name_str = training_file_list[i]
        file_str = file_name_str.split('.')[0]  # 去除 .txt
        class_num_str = int(file_str.split('_')[0]) # 从文件名获取数字
        hw_labels.append(class_num_str)
        training_mat[i, :] = img2vector('trainingDigits/%s' % file_name_str)
    test_file_list = listdir('testDigits')  # iterate through the test set
    error_count = 0.0
    m_test = len(test_file_list)
    for i in range(m_test):
        file_name_str = test_file_list[i]
        file_str = file_name_str.split('.')[0]  # 去掉 .txt
        class_num_str = int(file_str.split('_')[0])
        vector_under_test = img2vector('testDigits/%s' % file_name_str)
        classifier_result = classify0(vector_under_test, training_mat, hw_labels, 3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifier_result, class_num_str))
        if classifier_result != class_num_str:
            error_count += 1.0
    print("the total number of errors is: %d" % error_count)
    print("the total error rate is: %f" % (error_count / float(m_test)))

文件按照规则命名，如文件 9_45.txt 的分类是9，它是数字 9 的第 45 个实例。随后将分类标签储存到 hw_lables 变量中，使用前面讨论的 img2vector 函数载入图像。在下一步中，对 testDigits 目录中的文件执行相似的操作，不同之处是并不将这个目录下的文件载入矩阵中，而是使用 classify0 函数测试该目录下的每个文件。由于文件中的值已经在 0 和 1 之间，因此并不需要 auto_norm 函数

在 Python 命令行中使用 kNN.handwriting_class_test：

kNN.handwriting_class_test()
the classifier came back with: 0, the real answer is: 0
the classifier came back with: 0, the real answer is: 0
the classifier came back with: 0, the real answer is: 0
·····································
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the total number of errors is: 10
the total error rate is: 0.010571

k-近邻算法识别手写数字数据集，错误率为 1.0571%。改变 k 的值、修改随机选取训练样本、改变训练样本的数目，都会对 k-近邻算法错误率产生影响

实际使用这个算法时，算法的执行效率并不高。因为算法需要为每个测试向量做 2000次距离计算，每个距离计算包括了1024个维度浮点运算，总计要执行 900 次，此外，我们还需要为测试向量准备 2MB 的储存空间，是否存在一种算法减少储存空间和计算时间的开销呢？ k 决策树就是 k-近邻算法的优化版，可以节省大量的计算开销

小结

k-近邻算法是分类数据最简单最有效的算法，是基于实例的学习，使用算法时必须有接近实际数据的训练样本数据。k-近邻算法必须保存全部数据集，如果训练数据集很大，必须使用大量的储存空间。此外，由于必须对数据集中的每个数据计算距离值，实际使用时可能非常耗时

k-近邻算法的另一个缺陷就是它无法给出任何数据的基础结构信息，因为也无法知晓平均实例样本和典型实例样本具有什么特征

源码示例

GitHub 下载