假设有这么一份数据图,其中蓝色的点是恶性肿瘤,而红色的点是良性肿瘤,现在进来一个新的数据,我们要判断这个数据是良性的还是恶性的。k近邻算法的意思就是说,看这个点最近的k个点的距离,来根据这些点是蓝色还是红色的数量大小,来决定这个新来的点是蓝色还是红色。现在我们假设这个k值为3,则有
这个新进来的点,我们设为绿色,那么离它最近的点有两个是红色,一个是蓝色,则我们就可以认为这个新进来的点是一个红色的良性肿瘤的点。
由于这里面有求解距离的需求,则我们在求解距离上使用的是欧拉距离(其实就是勾股定理)
这里分别是二维、三维和高维空间的欧拉距离的计算公式,实际上就是各个数据的相同维度的值相减,平方后再将不同维度的平方值相加再开根号。
最终就是
现在我们来编程实现这个k近邻算法
import numpy as np
import matplotlib.pyplot as plt
from math import sqrt
from collections import Counter
if __name__ == "__main__":
# 所有的肿瘤数据
raw_data_x = [[3.393533211, 2.331273381],
[3.110073483, 1.781539638],
[1.343808831, 3.368360954],
[3.582294042, 4.679179110],
[2.280362439, 2.866990263],
[7.423436942, 4.696522875],
[5.745051997, 3.533989803],
[9.172168622, 2.511101045],
[7.792783481, 3.424088941],
[7.939820817, 0.791637231]]
# 肿瘤数据的类型,0为良性肿瘤,1为恶性肿瘤
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')
plt.scatter(X_train[Y_train == 1, 0], X_train[Y_train == 1, 1], color='r')
x = np.array([8.093607318, 3.365731514])
plt.scatter(x[0], x[1], color='b')
# 计算新样本到已有样本各个点的距离
distances = [sqrt(np.sum((x_train - x)**2)) for x_train in X_train]
print(distances)
# 对这个距离进行排序,排序的结果是已知样本的索引
nearest = np.argsort(distances)
print(nearest)
# 这里我们取6个近邻数据
k = 6
# 获取这前6个数据的肿瘤类型
topK_y = [Y_train[i] for i in nearest[:k]]
print(topK_y)
# 对这6个相近的肿瘤类型进行投票,投票数高的,新进的肿瘤数据就是该类型的肿瘤
votes = Counter(topK_y)
# 打印出新进肿瘤数据的肿瘤类型
print(votes.most_common(1)[0][0])
plt.show()
运行结果
[4.812566907609877, 5.229270827235305, 6.749798999160064, 4.6986266144110695, 5.83460014556857, 1.4900114024329525, 2.354574897431513, 1.3761132675144652, 0.3064319992975, 2.5786840957478887]
[8 7 5 6 9 3 0 1 4 2]
[1, 1, 1, 1, 1, 0]
1
由最终结果可知,新进入的肿瘤数据是一个恶性肿瘤。
肿瘤数据分布图如下
这里绿色是良性肿瘤,红色是恶性肿瘤,蓝色是新进肿瘤数据。