机器学习札记1-KNN算法

浏览: 1122

KNN导读

k-近邻算法(k-nearest neighbor, k-NN)是一种基本分类和回归的算法。k近邻算法中的输入为实例的特征向量,输出为实例的类别,类别可以有多类。算法主要思想:

  • 给定一个训练集的数据,实例的类别已定
  • 对于新的实例,根据k个最近邻的训练实例的类别,经投票表决等方式进行预测
  • 算法不具有显式的学习过程,实际上利用训练集对特征向量空间进行划分

KNN三要素

  • k的选择:k值如何选择?越大越好吗?奇偶性如何?经验值是多少?
  • 距离度量:选择什么距离来进行度量新实例和训练集上点的距离?
  • 分类决策规则:选择怎样的规则来对距离进行分类,从而判断新实例属于哪个类?

k近邻算法

直观解释:给定一个训练数据集,对于新输入的实例,在训练集数据中找出和该实例最邻近的k个实例。这k个实例中的多数属于某个类,就将新实例划分为这个类别。
输入训练数据集:
T=\{(x_1,y_1),(x_2,y_2),...(x_i,y_i)....(x_N,y_N)\}
其中,xi为实例特征向量,yi为实例的类别;i=1,2,3,...N。
输出:实例x所属的类别y

  • 根据给定的距离度量,在训练集T中找出与x最近邻的k个点,涵盖这个k个点的x的邻域记作:Nk(x)
  • 在邻域Nk(x)中根据分类规则决定x的类别y
    y = \mathop{argmax}\limits_{c_j}\sum_{x_i\in{N_k(x)}}I(y_i=c_j), i=1,2...,N;j=1,2,...K

上式中,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

推荐 0
本文由 皮大大 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册