KNN导读
k-近邻算法（k-nearest neighbor, k-NN）是一种基本分类和回归的算法。k近邻算法中的输入为实例的特征向量，输出为实例的类别，类别可以有多类。算法主要思想：
- 给定一个训练集的数据，实例的类别已定
- 对于新的实例，根据k个最近邻的训练实例的类别，经投票表决等方式进行预测
- 算法不具有显式的学习过程，实际上利用训练集对特征向量空间进行划分
KNN三要素
- k的选择：k值如何选择？越大越好吗？奇偶性如何？经验值是多少？
- 距离度量：选择什么距离来进行度量新实例和训练集上点的距离？
- 分类决策规则：选择怎样的规则来对距离进行分类，从而判断新实例属于哪个类？
k近邻算法
直观解释：给定一个训练数据集，对于新输入的实例，在训练集数据中找出和该实例最邻近的k个实例。这k个实例中的多数属于某个类，就将新实例划分为这个类别。
输入训练数据集：
其中，xi为实例特征向量，yi为实例的类别；i=1,2,3,...N。
输出：实例x所属的类别y
- 根据给定的距离度量，在训练集T中找出与x最近邻的k个点，涵盖这个k个点的x的邻域记作：Nk(x)
- 在邻域Nk(x)中根据分类规则决定x的类别y
上式中，I为指示函数，即当：yi=cj是为1，不等则为0
- k=1称之为
最近邻算法。对于输入的新实例，将训练集中离x最近点的所属类作为x的类别
导入库和样本
import numpy as np
from math import sqrt
import matplotlib.pyplot as plt
from collections import Counter
X_train_data = [[3.398183738, 2.339748328],
[3.111980280, 1.782018048],
[1.349838271, 3.368108483],
[3.501848049, 4.610848042],
[2.201804871, 2.091948545],
[7.428401824, 4.610948028],
[5.710380481, 3.530184804],
[9.171974792, 2.518408280],
[7.791837634, 3.401848052],
[7.901804805, 0.791794974]]
y_train_data = [1, 0, 1, 0, 0, 1, 0, 1, 0, 1]
# 将原始数据转换成numpy的np.array()
X_train = np.array(X_train_data)
y_train = np.array(y_train_data)
- 自定义待预测数据
# 带预测的数据
x = np.array([5.619483842, 2.419847827])
样本绘图
# scatter中的参数分别是x，y和color
# 制图中的两个坐标参数表示X_train中每个样本点的值
# X_train[y_train == 0,0]中，第一个0表示y取值为0，第二个0表示样本中第一个属性的值
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')
plt.scatter(x[0], x[1], color='b')
plt.show()
image.png
image.png
欧式距离
# 计算样本中每个实例数据和待测数据的欧氏距离计算，存入列表中
distances = []
for x_train in X_train:
d = sqrt(np.sum((x_train - x) ** 2))
distances.append(d)
- 列表解析式
# 上面的通过for列表解析式解决
distances = [sqrt(np.sum((x_train - x) ** 2)) for x_train in X_train]
image.png
- 按照从小到大的顺序返回上述距离的
索引值index：
# argsort函数返回上面数组值从小到大的索引值
nearest = np.argsort(distances)
nearest
image.png
取前k个值
# 取出前K个最小值
# nearest中索引代表的前6个值距离比较小
# i代表k个最小值的索引，通过索引对应y_train的值
k = 5
topK_y = [y_train[i] for i in nearest[:k]]
topK_y
# 结果
[0, 1, 0, 0, 1]
image.png
