在本教程中，您将学习k最近邻居算法， 包括它的工作方式以及如何在Python中（没有库）从头开始实现它。
一种简单但功能强大的预测方法是对新数据使用最相似的历史示例。这是k最近邻居算法背后的原理。
完成本教程后，您将知道：
- 如何逐步编码k最近邻算法。
- 如何在真实数据集上评估k最近邻。
- 如何使用k最近邻居对新数据进行预测。
k最近邻居
k最近邻算法（简称KNN）是一种非常简单的技术。
整个训练数据集将被存储。当需要预测时，然后找到与训练数据集中的新记录最相似的k条记录。从这些邻居中，进行了汇总的预测。
记录之间的相似性可以用许多不同的方法来衡量。可以使用问题或特定于数据的方法。通常，使用表格数据时，一个好的起点是欧几里得距离。
一旦发现邻居，就可以通过返回最常见的结果或取平均值来进行汇总预测。这样，KNN可以用于分类或回归问题。
除了拥有整个训练数据集之外，没有其他可说的模型。因为直到需要预测才进行任何工作，所以KNN通常被称为惰性学习方法。
鸢尾花种类数据集
在本教程中，我们将使用鸢尾花种类数据集。
鸢尾花数据集涉及在给定鸢尾花的测量值的情况下预测花的种类。
这是一个多类分类问题。每个类别的观察次数是平衡的。有150个观测值，其中包含4个输入变量和1个输出变量。变量名称如下：
- 萼片长度，以厘米为单位。
- 萼片宽度，以厘米为单位。
- 花瓣长度，以厘米为单位。
- 花瓣宽度，以厘米为单位。
- 班级
下面列出了前5行的示例。
|
1
2
3
4
5
6
|
5.1,3.5,1.4,0.2,Iris-setosa
4.9,3.0,1.4,0.2,Iris-setosa
4.7,3.2,1.3,0.2,Iris-setosa
4.6,3.1,1.5,0.2,Iris-setosa
5.0,3.6,1.4,0.2,Iris-setosa
…
|
该问题的基准性能约为33％。
下载数据集，并使用文件名“ iris.csv ”将其保存到当前工作目录中。
k最近邻居（只需3个简单步骤）
首先，我们将在本节中开发算法的每一部分，然后在下一节中将所有元素绑定到一个适用于实际数据集的有效实现中。
此k-Nearest Neighbors教程分为3部分：
- 步骤1：计算欧几里得距离。
- 步骤2：取得最近的邻居。
- 步骤3：做出预测。
这些步骤将教您实现k-最近邻居算法并将其应用于分类和回归预测建模问题的基础知识。
注意：本教程假定您正在使用Python3。如果需要安装Python的帮助，请参阅本教程：
- 如何为机器学习设置Python环境
我相信本教程中的代码也可以与Python 2.7一起使用，而无需进行任何更改。
步骤1：计算欧几里得距离
第一步是计算数据集中两行之间的距离。
数据行主要由数字组成，计算两行或数字向量之间的距离的一种简便方法是绘制一条直线。这在2D或3D中是有意义的，并且可以很好地缩放到更高的尺寸。
我们可以使用欧几里得距离度量来计算两个向量之间的直线距离。它被计算为两个向量之间的平方差之和的平方根。
- 欧几里德距离= sqrt（总和i至N（x1_i – x2_i）^ 2）
其中x1是数据的第一行，x2是数据的第二行，i是当我们跨所有列求和时对特定列的索引。
对于欧几里得距离，值越小，两条记录将越相似。值为0表示两个记录之间没有差异。
下面是一个名为euclidean_distance（）的函数，该函数在Python中实现。
|
1
2
3
4
5
6
|
# calculate the Euclidean distance between two vectors
def euclidean_distance(row1, row2):
distance = 0.0
for i in range(len(row1)–1):
distance += (row1[i] – row2[i])**2
return sqrt(distance)
|
您可以看到该函数假定每行的最后一列是一个输出值，该值将从距离计算中忽略。
我们可以使用一个小的人为分类数据集来测试该距离函数。在构造KNN算法所需的元素时，我们将使用该数据集几次。
|
1
2
3
4
5
6
7
8
9
10
11
|
X1 X2 Y
2.7810836 2.550537003 0
1.465489372 2.362125076 0
3.396561688 4.400293529 0
1.38807019 1.850220317 0
3.06407232 3.005305973 0
7.627531214 2.759262235 1
5.332441248 2.088626775 1
6.922596716 1.77106367 1
8.675418651 -0.242068655 1
7.673756466 3.508563011 1
|
以下是使用不同颜色的数据集图，以显示每个点的不同类别。
用于测试KNN算法的小型人为数据集的散点图
放在一起，我们可以写一个小例子来测试我们的距离函数，方法是打印第一行和所有其他行之间的距离。我们希望第一行与其自身之间的距离为0，这是一件好事。
下面列出了完整的示例。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
# Example of calculating Euclidean distance
from math import sqrt
# calculate the Euclidean distance between two vectors
def euclidean_distance(row1, row2):
distance = 0.0
for i in range(len(row1)–1):
distance += (row1[i] – row2[i])**2
return sqrt(distance)
# Test distance function
dataset = [[2.7810836,2.550537003,0],
[1.465489372,2.362125076,0],
[3.396561688,4.400293529,0],
[1.38807019,1.850220317,0],
[3.06407232,3.005305973,0],
[7.627531214,2.759262235,1],
[5.332441248,2.088626775,1],
[6.922596716,1.77106367,1],
[8.675418651,–0.242068655,1],
[7.673756466,3.508563011,1]]
row0 = dataset[0]
for row in dataset:
distance = euclidean_distance(row0, row)
print(distance)
|
运行此示例将打印数据集中第一行与每一行之间的距离，包括其自身。
|
1
2
3
4
5
6
7
8
9
10
|
0.0
1.3290173915275787
1.9494646655653247
1.5591439385540549
0.5356280721938492
4.850940186986411
2.592833759950511
4.214227042632867
6.522409988228337
4.985585382449795
|
现在是时候使用距离计算来定位数据集中的邻居了。
步骤2：取得最近的邻居
数据集中新数据的邻居是k个最接近的实例，这由我们的距离度量定义。
为了在数据集中找到新数据的邻居，我们必须首先计算数据集中每个记录到新数据之间的距离。我们可以使用上面准备的距离函数来做到这一点。
一旦计算出距离，我们就必须根据它们与新数据的距离对训练数据集中的所有记录进行排序。然后，我们可以选择顶部k作为最相似的邻居返回。
我们可以通过以元组的形式跟踪数据集中每个记录的距离，通过距离（按降序）对元组列表进行排序，然后检索邻居来做到这一点。
下面是一个名为get_neighbors（）的函数，用于实现此功能。
|
1
2
3
4
5
6
7
8
9
10
11
|
# Locate the most similar neighbors
def get_neighbors(train, test_row, num_neighbors):
distances = list()
for train_row in train:
dist = euclidean_distance(test_row, train_row)
distances.append((train_row, dist))
distances.sort(key=lambda tup: tup[1])
neighbors = list()
for i in range(num_neighbors):
neighbors.append(distances[i][0])
return neighbors
|
您可以看到，在上一步中开发的euclidean_distance（）函数用于计算每个train_row与新的test_row之间的距离。
在使用自定义键的情况下，对train_row和distance元组的列表进行排序，以确保在排序操作中使用了元组中的第二项（tup [1]）。
最后，列表num_neighbors最相似的邻居test_row返回。
我们可以使用上一节中准备的小型人为数据集来测试此功能。
下面列出了完整的示例。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
# Example of getting neighbors for an instance
from math import sqrt
# calculate the Euclidean distance between two vectors
def euclidean_distance(row1, row2):
distance = 0.0
for i in range(len(row1)–1):
distance += (row1[i] – row2[i])**2
return sqrt(distance)
# Locate the most similar neighbors
def get_neighbors(train, test_row, num_neighbors):
distances = list()
for train_row in train:
dist = euclidean_distance(test_row, train_row)
distances.append((train_row, dist))
distances.sort(key=lambda tup: tup[1])
neighbors = list()
for i in range(num_neighbors):
neighbors.append(distances[i][0])
return neighbors
# Test distance function
dataset = [[2.7810836,2.550537003,0],
[1.465489372,2.362125076,0],
[3.396561688,4.400293529,0],
[1.38807019,1.850220317,0],
[3.06407232,3.005305973,0],
[7.627531214,2.759262235,1],
[5.332441248,2.088626775,1],
[6.922596716,1.77106367,1],
[8.675418651,–0.242068655,1],
[7.673756466,3.508563011,1]]
neighbors = get_neighbors(dataset, dataset[0], 3)
for neighbor in neighbors:
print(neighbor)
|
运行此示例将按相似性顺序将数据集中的3个最相似的记录打印到第一个记录。
不出所料，第一条记录与其本身最相似，并且位于列表的顶部。
|
1
2
3
|
[2.7810836, 2.550537003, 0]
[3.06407232, 3.005305973, 0]
[1.465489372, 2.362125076, 0]
|
现在我们知道了如何从数据集中获取邻居，我们可以使用它们进行预测。
步骤3：做出预测
从训练数据集中收集的最相似的邻居可以用来进行预测。
在分类的情况下，我们可以返回邻居中代表最多的类。
我们可以通过对来自邻居的输出值列表执行max（）函数来实现此目的。给定在邻居中观察到的类值列表，max（）函数采用一组唯一的类值，并为该集中的每个类值调用类值列表上的计数。
下面是实现此功能的名为predict_classification（）的函数。
|
1
2
3
4
5
6
|
# Make a classification prediction with neighbors
def predict_classification(train, test_row, num_neighbors):
neighbors = get_neighbors(train, test_row, num_neighbors)
output_values = [row[–1] for row in neighbors]
prediction = max(set(output_values), key=output_values.count)
return prediction
|
我们可以在上述人为设计的数据集上测试此功能。
以下是一个完整的示例。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
# Example of making predictions
from math import sqrt
# calculate the Euclidean distance between two vectors
def euclidean_distance(row1, row2):
distance = 0.0
for i in range(len(row1)–1):
distance += (row1[i] – row2[i])**2
return sqrt(distance)
# Locate the most similar neighbors
def get_neighbors(train, test_row, num_neighbors):
distances = list()
for train_row in train:
dist = euclidean_distance(test_row, train_row)
distances.append((train_row, dist))
distances.sort(key=lambda tup: tup[1])
neighbors = list()
for i in range(num_neighbors):
neighbors.append(distances[i][0])
return neighbors
# Make a classification prediction with neighbors
def predict_classification(train, test_row, num_neighbors):
neighbors = get_neighbors(train, test_row, num_neighbors)
output_values = [row[–1] for row in neighbors]
prediction = max(set(output_values), key=output_values.count)
return prediction
# Test distance function
dataset = [[2.7810836,2.550537003,0],
[1.465489372,2.362125076,0],
[3.396561688,4.400293529,0],
[1.38807019,1.850220317,0],
[3.06407232,3.005305973,0],
[7.627531214,2.759262235,1],
[5.332441248,2.088626775,1],
[6.922596716,1.77106367,1],
[8.675418651,–0.242068655,1],
[7.673756466,3.508563011,1]]
prediction = predict_classification(dataset, dataset[0], 3)
print(‘Expected %d, Got %d.’ % (dataset[0][–1], prediction))
|
运行此示例将打印预期的分类0和从数据集中3个最相似的邻居预测的实际分类。
|
1
|
Expected 0, Got 0.
|
我们可以想象到如何可以更改Forecast_classification（）函数以计算结果值的平均值。
现在，我们拥有使用KNN进行预测的所有方法。让我们将其应用于真实数据集。
鸢尾花种类案例研究
本部分将KNN算法应用于鸢尾花数据集。
第一步是加载数据集，并将加载的数据转换为可用于平均值和标准偏差计算的数字。为此，我们将使用辅助函数load_csv（）加载文件，使用str_column_to_float（）将字符串数字转换为浮点数，并使用str_column_to_int（）将类列转换为整数值。
我们将使用5倍的k倍交叉验证对算法进行评估。这意味着每个折叠中将有150/5 = 30个记录。我们将使用辅助函数validate_algorithm（）来评估具有交叉验证的算法，并使用precision_metric（）来计算预测的准确性。
开发了一个名为k_nearest_neighbors（）的新函数来管理KNN算法的应用，首先从训练数据集中学习统计信息，然后使用它们为测试数据集做出预测。
下面列出了完整的示例。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
# k-nearest neighbors on the Iris Flowers Dataset
from random import seed
from random import randrange
from csv import reader
from math import sqrt
# Load a CSV file
def load_csv(filename):
dataset = list()
with open(filename, ‘r’) as file:
csv_reader = reader(file)
for row in csv_reader:
if not row:
continue
dataset.append(row)
return dataset
# Convert string column to float
def str_column_to_float(dataset, column):
for row in dataset:
row[column] = float(row[column].strip())
# Convert string column to integer
def str_column_to_int(dataset, column):
class_values = [row[column] for row in dataset]
unique = set(class_values)
lookup = dict()
for i, value in enumerate(unique):
lookup[value] = i
for row in dataset:
row[column] = lookup[row[column]]
return lookup
# Find the min and max values for each column
def dataset_minmax(dataset):
minmax = list()
for i in range(len(dataset[0])):
col_values = [row[i] for row in dataset]
value_min = min(col_values)
value_max = max(col_values)
minmax.append([value_min, value_max])
return minmax
# Rescale dataset columns to the range 0-1
def normalize_dataset(dataset, minmax):
for row in dataset:
for i in range(len(row)):
row[i] = (row[i] – minmax[i][0]) / (minmax[i][1] – minmax[i][0])
# Split a dataset into k folds
def cross_validation_split(dataset, n_folds):
dataset_split = list()
dataset_copy = list(dataset)
fold_size = int(len(dataset) / n_folds)
for _ in range(n_folds):
fold = list()
while len(fold) < fold_size:
index = randrange(len(dataset_copy))
fold.append(dataset_copy.pop(index))
dataset_split.append(fold)
return dataset_split
# Calculate accuracy percentage
def accuracy_metric(actual, predicted):
correct = 0
for i in range(len(actual)):
if actual[i] == predicted[i]:
correct += 1
return correct / float(len(actual)) * 100.0
# Evaluate an algorithm using a cross validation split
def evaluate_algorithm(dataset, algorithm, n_folds, *args):
folds = cross_validation_split(dataset, n_folds)
scores = list()
for fold in folds:
train_set = list(folds)
train_set.remove(fold)
train_set = sum(train_set, [])
test_set = list()
for row in fold:
row_copy = list(row)
test_set.append(row_copy)
row_copy[–1] = None
predicted = algorithm(train_set, test_set, *args)
actual = [row[–1] for row in fold]
accuracy = accuracy_metric(actual, predicted)
scores.append(accuracy)
return scores
# Calculate the Euclidean distance between two vectors
def euclidean_distance(row1, row2):
distance = 0.0
for i in range(len(row1)–1):
distance += (row1[i] – row2[i])**2
return sqrt(distance)
# Locate the most similar neighbors
def get_neighbors(train, test_row, num_neighbors):
distances = list()
for train_row in train:
dist = euclidean_distance(test_row, train_row)
distances.append((train_row, dist))
distances.sort(key=lambda tup: tup[1])
neighbors = list()
for i in range(num_neighbors):
neighbors.append(distances[i][0])
return neighbors
# Make a prediction with neighbors
def predict_classification(train, test_row, num_neighbors):
neighbors = get_neighbors(train, test_row, num_neighbors)
output_values = [row[–1] for row in neighbors]
prediction = max(set(output_values), key=output_values.count)
return prediction
# kNN Algorithm
def k_nearest_neighbors(train, test, num_neighbors):
predictions = list()
for row in test:
output = predict_classification(train, row, num_neighbors)
predictions.append(output)
return(predictions)
# Test the kNN on the Iris Flowers dataset
seed(1)
filename = ‘iris.csv’
dataset = load_csv(filename)
for i in range(len(dataset[0])–1):
str_column_to_float(dataset, i)
# convert class column to integers
str_column_to_int(dataset, len(dataset[0])–1)
# evaluate algorithm
n_folds = 5
num_neighbors = 5
scores = evaluate_algorithm(dataset, k_nearest_neighbors, n_folds, num_neighbors)
print(‘Scores: %s’ % scores)
print(‘Mean Accuracy: %.3f%%’ % (sum(scores)/float(len(scores))))
|
运行示例将在每个交叉验证折叠上打印平均分类准确性得分以及平均准确性得分。
我们可以看到，平均准确度约为96.6％，远远高于基线准确度33％。
|
1
2
|
Scores: [96.66666666666667, 96.66666666666667, 100.0, 90.0, 100.0]
Mean Accuracy: 96.667%
|
我们可以使用训练数据集为新的观测值（数据行）做出预测。
这涉及到调用predict_classification（）函数，其中一行代表了我们用来预测类标签的新观察结果。
|
1
2
3
|
...
# predict the label
label = predict_classification(dataset, row, num_neighbors)
|
我们也可能想知道用于预测的类标签（字符串）。
我们可以更新str_column_to_int（）函数以打印字符串类名称到整数的映射，以便我们可以解释模型所做的预测。
|
1
2
3
4
5
6
7
8
9
10
11
|
# Convert string column to integer
def str_column_to_int(dataset, column):
class_values = [row[column] for row in dataset]
unique = set(class_values)
lookup = dict()
for i, value in enumerate(unique):
lookup[value] = i
print(‘[%s] => %d’ % (value, i))
for row in dataset:
row[column] = lookup[row[column]]
return lookup
|
结合在一起，下面列出了将KNN与整个数据集结合使用并对新观测值进行单个预测的完整示例。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
# Make Predictions with k-nearest neighbors on the Iris Flowers Dataset
from csv import reader
from math import sqrt
# Load a CSV file
def load_csv(filename):
dataset = list()
with open(filename, ‘r’) as file:
csv_reader = reader(file)
for row in csv_reader:
if not row:
continue
dataset.append(row)
return dataset
# Convert string column to float
def str_column_to_float(dataset, column):
for row in dataset:
row[column] = float(row[column].strip())
# Convert string column to integer
def str_column_to_int(dataset, column):
class_values = [row[column] for row in dataset]
unique = set(class_values)
lookup = dict()
for i, value in enumerate(unique):
lookup[value] = i
print(‘[%s] => %d’ % (value, i))
for row in dataset:
row[column] = lookup[row[column]]
return lookup
# Find the min and max values for each column
def dataset_minmax(dataset):
minmax = list()
for i in range(len(dataset[0])):
col_values = [row[i] for row in dataset]
value_min = min(col_values)
value_max = max(col_values)
minmax.append([value_min, value_max])
return minmax
# Rescale dataset columns to the range 0-1
def normalize_dataset(dataset, minmax):
for row in dataset:
for i in range(len(row)):
row[i] = (row[i] – minmax[i][0]) / (minmax[i][1] – minmax[i][0])
# Calculate the Euclidean distance between two vectors
def euclidean_distance(row1, row2):
distance = 0.0
for i in range(len(row1)–1):
distance += (row1[i] – row2[i])**2
return sqrt(distance)
# Locate the most similar neighbors
def get_neighbors(train, test_row, num_neighbors):
distances = list()
for train_row in train:
dist = euclidean_distance(test_row, train_row)
distances.append((train_row, dist))
distances.sort(key=lambda tup: tup[1])
neighbors = list()
for i in range(num_neighbors):
neighbors.append(distances[i][0])
return neighbors
# Make a prediction with neighbors
def predict_classification(train, test_row, num_neighbors):
neighbors = get_neighbors(train, test_row, num_neighbors)
output_values = [row[–1] for row in neighbors]
prediction = max(set(output_values), key=output_values.count)
return prediction
# Make a prediction with KNN on Iris Dataset
filename = ‘iris.csv’
dataset = load_csv(filename)
for i in range(len(dataset[0])–1):
str_column_to_float(dataset, i)
# convert class column to integers
str_column_to_int(dataset, len(dataset[0])–1)
# define model parameter
num_neighbors = 5
# define a new record
row = [5.7,2.9,4.2,1.3]
# predict the label
label = predict_classification(dataset, row, num_neighbors)
print(‘Data=%s, Predicted: %s’ % (row, label))
|
运行数据首先总结了类标签到整数的映射，然后将模型拟合到整个数据集。
然后定义一个新的观察值（在这种情况下，我从数据集中取了一行），并计算了一个预测标签。
在这种情况下，我们的观察预计属于第一类，我们知道这是“鸢尾花”。
|
1
2
3
4
|
[Iris-virginica] => 0
[Iris-setosa] => 1
[Iris-versicolor] => 2
Data=[4.5, 2.3, 1.3, 0.3], Predicted: 1
|
版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站不拥有所有权，不承担相关法律责任。如发现有侵权/违规的内容， 联系QQ1841324605，本站将立刻清除。
AI智能 
