一、前言
K-近邻算法是一种基本的用于分类和回归的非参数统计方法,本篇blog将对分类问题中的k-近邻算法进行总结以及在文末给出了简单的Python实现。see more details in KNN.
二、K-近邻算法
K-近邻算法应用于分类问题时,算法具体内容很简单。首先需要注意的是: K-近邻算法是一种非参数统计方法。
顾名思义,K-近邻算法不具备有显式的学习过程,当对新的样本进行分类时,K-近邻算法将计算该样本与训练集中所有样本的"距离",并根据其k个最近邻的训练实例的类别,通过多数表决的方法来对新样本的类别进行预测:
y = arg max c j ∑ x i ∈ N k ( x ) I ( y i = c j ) , i = 1 , 2 , . . . , N , j = 1 , 2 , . . . , K {\rm{y}} = \mathop {\arg \max }\limits_{{c_j}} \sum\limits_{{x_i} \in {N_k}(x)} {I({y_i} = {c_j}),i = 1,2,...,N,j = 1,2,...,K}y =c j ar g max x i ∈N k (x )∑I (y i =c j ),i =1 ,2 ,...,N ,j =1 ,2 ,...,K
其中,c j {c_j}c j 为实例类别集合中类别,I I I为指示函数,N k ( x ) {N_k}(x)N k (x )为在训练集中与样本最近邻的k个样本的集合,N N N为训练集中的样本总数。
K-近邻算法的 三个基本要素是:k值的选择+距离度量+分类决策规则。分类决策规则采用多数表决的方法,距离度量有如欧氏距离、曼哈顿距离等方式,这里不再赘述,K-近邻算法的关键在于k值的选择,当k减少时,模型变得更加复杂,当k增加时,模型变得简单,实际应用时通常采用交叉验证法来对k值进行选择。
对给定的实例x ∈ X x\in X x ∈X,其最近邻的k个训练实例点构成集合N k ( x ) {N_k}(x)N k (x ),如果涵盖N k {N_k}N k 的区域类别是c j {c_j}c j ,那么误分类率是:1 k ∑ x i ∈ N K ( x ) I ( y i ≠ c j ) = 1 − 1 k ∑ x i ∈ N K ( x ) I ( y i = c j ) \frac{1}{k}\sum\limits_{{x_i} \in {N_K}(x)} {I({y_i} \ne {c_j})} = 1 - \frac{1}{k}\sum\limits_{{x_i} \in {N_K}(x)} {I({y_i} = {c_j})}k 1 x i ∈N K (x )∑I (y i =c j )=1 −k 1 x i ∈N K (x )∑I (y i =c j )
要使得误分类率最小即经验风险最小,就要使得∑ x i ∈ N K ( x ) I ( y i = c j ) \sum\limits_{{x_i} \in {N_K}(x)} {I({y_i} = {c_j})}x i ∈N K (x )∑I (y i =c j )最大,所以多数表决规则等价于经验风险最小化。
三、简单的Python实现
3.1 数据准备
from sklearn.datasets import make_blobs
from sklearn.model_selection import train_test_split
import numpy as np
import pandas as pd
data, labels = make_blobs(n_samples=200, n_features=3, centers=2, random_state=42)
x_train, x_test, y_train, y_test = train_test_split(data, labels, train_size=0.9, random_state=42)
3.2 具体代码
k = 4
def distance(x, y):
return np.sqrt(np.sum(np.square((x-y).T), axis=0))
def knn(train_data, train_label, test_data, k):
pred_labels = []
for i in test_data:
temp = {}
distance_list = distance(i, train_data)
k_labels = train_label[np.argsort(distance_list)][:k]
for i in range(k):
if k_labels[i] in temp:
temp[k_labels[i]] += 1
else:
temp[k_labels[i]] = 1
pred_labels.append(max(temp, key=lambda x : temp[x]))
return pred_labels
def acc(y_pred, y_true):
print(sum(y_pred == y_true) / len(y_true))
四、K-近邻法的实现:kd树
上述给出了K-近邻法最简单的实现方法,即线性扫描,但是当训练集很大时,线性扫描的方法计算十分耗时。为了提高K-近邻搜索的效率,考虑使用特殊的数据结构存储训练数据,以减少计算距离的次数,比如下述的kd树。
4.1 kd树的构建
输入:D = { x 1 , x 2 , . . . , x N } D={{x_1},{x_2},...,{x_N}}D ={x 1 ,x 2 ,...,x N },其中x i = ( x i ( 1 ) , x i ( 2 ) , x i ( 3 ) . . . , x i ( k ) ) T {x_i}=({\rm{x}}i^{(1)}, {\rm{x}}_i^{(2)}, {\rm{x}}_i^{(3)}...,{\rm{x}}_i^{(k)})^T x i =(x i (1 ),x i (2 ),x i (3 )...,x i (k ))T,i = 1 , 2 , . . . , N i=1,2,...,N i =1 ,2 ,...,N
_输出:kd树
- 构造根节点,根节点对应于包含D的k维空间的超矩形区域:选择x ( 1 ) {x^{(1)}}x (1 )所对应的维度为坐标轴,利用D中所有实例的x ( 1 ) {x^{(1)}}x (1 )维度对应的坐标的中位数作为切分点。
- 对深度为j 的结点,选择x ( l ) {x^{(l)}}x (l )作为切分的坐标轴,其中l = j ( m o d ) k + 1 l=j(mod)k+1 l =j (m o d )k +1,剩下的步骤与第一步相同。
- 重复上述递归,直到实例被划分完全,这样就完成了kd树的构建。
4.1.1 Python实现
KD树构建:
class KD_Node:
def __init__(self, data, depth):
self.data = data
self.depth = depth
self.right = None
self.left = None
class KD_Tree:
def __init__(self, data):
self.data = data
self.root = None
def _build(self, points, depth):
if len(points) == 0:
return None
k = len(points[0])
_axis = depth % k
points.sort(key=lambda x : x[_axis])
median_idx = len(points) // 2
node = KD_Node(points[median_idx], depth)
node.left = self._build(points[0:median_idx], depth+1)
node.right = self._build(points[median_idx+1:], depth+1)
return node
def build(self):
self.root = self._build(self.data, 0)
return self.root
def preorder(root):
print(root.data)
if root.left:
preorder(root.left)
if root.right:
preorder(root.right)
def inorder(root):
if root.left:
inorder(root.left)
print(root.data)
if root.right:
inorder(root.right)
利用统计学习方法P54例3.2中给定的二维空间的数据集对KD树构建进行检查:
x = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
完成KD树构建并对其进行前序和中序遍历得下:
前序遍历和中序遍历的结果均正确,KD树构建成功。
4.2 搜索KD树
4.2.1 搜索基本流程
首先给出KD树最近邻搜索算法的基本流程:
输入:构造好的KD树,以及目标点x
输出:目标点的最近邻
- 首先在KD树中寻找包含目标点的叶结点:从根节点出发,按照上述构建kd树depth和特征向量维度的关系改变样本数据比较的维度,在当前维度axis上,若目标点x [ a x i s ] < n o d e [ a x i s ] x[axis],则当前节点移动到左子结点,否则移动到右子节点,直到节点为叶节点为止。
- 以当前叶结点为"当前最近点"。
- 递归地向上回退,在每个结点上进行如下操作:
a. 如果当前结点保存的实例点比当前最近点距离目标点更近,则以该实例点为"当前最近点"。
b.当前最近点存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一个子结点对应的区域是否有更近的点。具体地,检查另一个子结点对应区域是否以目标点为球心、以目标点与"当前最近点"的距离为半径的超球体相交:如果相交,可能在另一个子结点对应的区域存在距离目标点更近的点,移动到另一个子结点,接着递归地进行最近邻搜索;不相交则向上回退。 - 回退到根节点时,搜索结束,最后的"当前最近点"即为x x x的最近邻点。
4.2.2 算法步骤分解
视频讲解链接:KNN KD_Trees
根据上图,可以看到图片构建好的KD树以及目标点( 6 , 7 ) (6,7)(6 ,7 )。在算法启动时,我们将最近距离(best distance)设置为f l o a t [ " i n f " ] float["inf"]f l o a t ["i n f "]、将当前最近点设置为N o n e None N o n e。
按照算法流程走,第一步先将目标节点与根节点进行比较:计算出目标结点与根结点的距离,并与保存的最近距离相比较。将 最近距离_更新为目标结点与根节点的距离,将 _当前最近点_设置为根结点。
第二部即递归向下遍历各结点:此时,算法通过比较结点与目标点当前轴上的数据大小来决定走左子树或者右子树。可以很容易看出,a x i s = 0 axis=0 a x i s =0时6 < 7 6,此时结点向左子树移动。
接着是不断递归向下遍历直到当前结点为叶结点,在这个过程中,将计算每个节点与目标点的距离,如果这个距离小于上述所保存的 _最近距离,则将 最近距离_更新为这个距离,同时更新 _当前最近点。
当我们 遍历到叶结点时,需要特别注意的是:我们需要对所谓的"bad side of the tree"上的结点与目标点进行比较吗?答案是不需要,这也是算法中3(b)步: 检查该子结点的父结点的另一个子结点对应的区域是否有更近的点。
但在此处我们并不需要计算目标点与( 2 , 3 ) (2,3)(2 ,3 )的距离,以上图为例,我们只需要计算目标点到"bad side of the tree"所对应的轴的距离,并将这个距离与当前保存的最近距离进行比较,因为这也是目标点距离这片区域最近的点(红色区域):
若该距离大于最近距离,那么就没有再去比较的必要。该步对应于算法中的: 检查另一个子结点对应区域是否以目标点为球心、以目标点与"当前最近点"的距离为半径的超球体相交。
如果距离小于最近距离,则意味着区域内可能存在节点到目标点的距离小于当前最小距离的节点,因此需要转移到另一个节点,递归搜索最近的邻居。
[En]
If the distance is less than the nearest distance, then it means that there may be nodes in the region where the distance between the node and the target point is less than the current minimum distance, so it is necessary to transfer to another node and recursively search the nearest neighbor.
最后,回退到根节点时,搜索结束,最后的"当前最近点"即为x x x的最近邻点。
; 4.2.3 最近邻搜索的Python实现
result = collections.namedtuple("result", "nearest_point nearest_dist")
def find_nearest(kd_tree, point):
k = len(point)
def search(kd_node, target, max_dist):
if kd_node is None:
return result([0] * k, float("inf"))
split = kd_node.depth % k
node_data = kd_node.data
if target[split] node_data[split]:
nearer_node = kd_node.left
farther_node = kd_node.right
else:
nearer_node = kd_node.right
farther_node = kd_node.left
templeaf = search(nearer_node, target, max_dist)
nearest = templeaf.nearest_point
dist = templeaf.nearest_dist
if dist < max_dist:
max_dist = dist
temp_dist = abs(node_data[split] - target[split])
if max_dist < temp_dist:
return result(nearest, dist)
temp_dist = np.sqrt(sum((p1 - p2) ** 2 for p1,p2 in zip(node_data, target)))
if temp_dist < dist:
nearest = node_data
dist = temp_dist
max_dist = dist
temp2 = search(farther_node, target, max_dist)
if temp2.nearest_dist < dist:
nearest = temp2.nearest_point
dist = temp2.nearest_dist
return result(nearest, dist)
return search(kd_tree, point, float("inf"))
4.3 KD_Tree上的KNN
4.3.1 算法描述
输入: 构造好的kd树;目标点x
输出: x的k个近邻
- 在kd树中找出包含目标点的叶结点:从根节点出发递归向下访问,目标点当前维度的数据小于当前结点当前维度的数据时移动到左子结点,反之则移动到右子结点,直到结点为叶结点。
- 若当前k近邻点集元素数量小于k或者叶结点距离小于"当前k近邻点集"中的最远距离,那么将叶结点插入到"当前k近邻点集";
- 递归地向上回退:
a. 如果当前k近邻点集元素数量小于k或者当前结点小于当前k近邻点集中最远点距离,那么将该结点插入当前k近邻点集
b. 检查另一个子结点所对应的区域是否以目标点为球心、以目标点与当前k近邻点集中最远点间的距离为半径的超球体相交,如果相交,可能在另一个子结点对应的区域存在距离目标点更近的点,移动到另一个子结点,接着,递归地进行最近邻搜索;如果不相交,向上回退; - 当回退到根结点时,搜索结束,最后的"当前k近邻点集"即为x的最近邻点。
4.3.2 Python实现
Code:DataWhale
import json
class Node:
"""节点类"""
def __init__(self, value, index, left_child, right_child):
self.value = value.tolist()
self.index = index
self.left_child = left_child
self.right_child = right_child
def __repr__(self):
return json.dumps(self, indent=3, default=lambda obj: obj.__dict__, ensure_ascii=False, allow_nan=False)
class KDTree:
"""kd tree类"""
def __init__(self, data):
self.data = np.asarray(data)
self.kd_tree = None
self._create_kd_tree(data)
def _split_sub_tree(self, data, depth=0):
if len(data) == 0:
return None
l = depth % data.shape[1]
data = data[data[:, l].argsort()]
median_index = data.shape[0] // 2
node_index = [i for i, v in enumerate(
self.data) if list(v) == list(data[median_index])]
return Node(
value=data[median_index],
index=node_index[0],
left_child=self._split_sub_tree(data[:median_index], depth + 1),
right_child=self._split_sub_tree(
data[median_index + 1:], depth + 1)
)
def _create_kd_tree(self, X):
self.kd_tree = self._split_sub_tree(X)
def query(self, data, k=1):
data = np.asarray(data)
hits = self._search(data, self.kd_tree, k=k, k_neighbor_sets=list())
dd = np.array([hit[0] for hit in hits])
ii = np.array([hit[1] for hit in hits])
return dd, ii
def __repr__(self):
return str(self.kd_tree)
@staticmethod
def _cal_node_distance(node1, node2):
"""计算两个结点之间的距离"""
return np.sqrt(np.sum(np.square(node1 - node2)))
def _search(self, point, tree=None, k=1, k_neighbor_sets=None, depth=0):
if k_neighbor_sets is None:
k_neighbor_sets = []
if tree is None:
return k_neighbor_sets
if tree.left_child is None and tree.right_child is None:
return self._update_k_neighbor_sets(k_neighbor_sets, k, tree, point)
if point[0][depth % k] < tree.value[depth % k]:
direct = 'left'
next_branch = tree.left_child
else:
direct = 'right'
next_branch = tree.right_child
if next_branch is not None:
k_neighbor_sets = self._update_k_neighbor_sets(
k_neighbor_sets, k, next_branch, point)
if direct == 'left':
node_distance = self._cal_node_distance(
point, tree.right_child.value)
if k_neighbor_sets[0][0] > node_distance:
return self._search(point, tree=tree.right_child, k=k, depth=depth + 1,
k_neighbor_sets=k_neighbor_sets)
else:
node_distance = self._cal_node_distance(
point, tree.left_child.value)
if k_neighbor_sets[0][0] > node_distance:
return self._search(point, tree=tree.left_child, k=k, depth=depth + 1,
k_neighbor_sets=k_neighbor_sets)
return self._search(point, tree=next_branch, k=k, depth=depth + 1, k_neighbor_sets=k_neighbor_sets)
def _update_k_neighbor_sets(self, best, k, tree, point):
node_distance = self._cal_node_distance(point, tree.value)
if len(best) == 0:
best.append((node_distance, tree.index, tree.value))
elif len(best) < k:
self._insert_k_neighbor_sets(best, tree, node_distance)
else:
if best[0][0] > node_distance:
best = best[1:]
self._insert_k_neighbor_sets(best, tree, node_distance)
return best
@staticmethod
def _insert_k_neighbor_sets(best, tree, node_distance):
"""将距离最远的结点排在前面"""
n = len(best)
for i, item in enumerate(best):
if item[0] < node_distance:
best.insert(i, (node_distance, tree.index, tree.value))
break
if len(best) == n:
best.append((node_distance, tree.index, tree.value))
def print_k_neighbor_sets(k, ii, dd):
if k == 1:
text = "x点的最近邻点是"
else:
text = "x点的%d个近邻点是" % k
for i, index in enumerate(ii):
res = X_train[index]
if i == 0:
text += str(tuple(res))
else:
text += ", " + str(tuple(res))
if k == 1:
text += ",距离是"
else:
text += ",距离分别是"
for i, dist in enumerate(dd):
if i == 0:
text += "%.4f" % dist
else:
text += ", %.4f" % dist
print(text)
import numpy as np
X_train = np.array([[2, 3],
[5, 4],
[9, 6],
[4, 7],
[8, 1],
[7, 2]])
kd_tree = KDTree(X_train)
k = 1
dists, indices = kd_tree.query(np.array([[3, 4.5]]), k=k)
print_k_neighbor_sets(k, indices, dists)
Original: https://blog.csdn.net/JIANGSAS/article/details/123325477
Author: jyyym
Title: 【统计学习方法】K-近邻法
相关阅读
Title: Ubuntu20.04+3090ti+cudatoolkit=11.3+tensorflow-gpu=2.6+pytorch=1.10 环境配置踩坑记录 可通过配置文件迁移引用
Ubuntu20.04+3090ti+cudatoolkit=11.3+tensorflow-gpu=2.6.2+pytorch=1.10.2 环境配置
最近实验室刚配了一台3090ti的服务器用来跑实验,最近经过几天的折腾终于把tensoflow和pytorch的环境搭建好了,下面就把踩过的坑讲一下,希望能帮助一些同样需要配置的伙伴。
说明:本博客非教程帖,非保姆教程,有些步骤并没有记录,所以不要按我下面的指令配置,只是提供参考和说明。
1、基础条件:
CPU:Intel i9 12900KF,
GPU:微星3090ti 24GB显存,
系统:Ubuntu 20.04
显卡驱动: 510.54
2、第一个坑:显卡驱动不用非得装最新,也不用非得装官网的驱动。
通过命令查看自己显卡的驱动版本:
nvidia-smi
开始我是从官网下载的驱动,然后通过tty命令装的,但是在装的过程中出错了,所以又重装的系统,后来就直接使用Ubuntu 系统的包装的,这样流程相对简单,事实证明也没有问题。
3、第二个坑:cuda和cudnn的安装
这里通过上面的图片可以看到CUDA Version: 11.6
这里的cuda版本其实并不是系统的cuda真实版本,我的理解是该驱动下可以支持的cuda最高版本
nvcc -V
通过 nvcc -V 命令可以看到,我安装的的cuda版本为11.0,只要是11.0以上版本应该都是可以的
3090系列的显卡必须保证cuda版本为11.0以上,这里务必注意
如果你的nvcc -V 命令并不能输出cuda版本,如果看到这里的你准备去安装cuda的话,我劝你可以先不用去装cuda,直接进行后面的tensorflow和pytorch配置, 这也就是第二个坑,在后面的配置你会发现,conda虚拟环境中会重新安装cudatoolkit,所以cuda不是必须安装的,在虚拟环境中安装完全可以。 所以看到这里的你可以停一停,不用先着急配置cuda,除非你有其他的需求显卡的需求。
4、tensorflow-gpu配置
这里我是使用的Anaconda3进行的环境配置,所以以下的说明都是在conda虚拟环境中进行的。
tensorflow-gpu安装过程中会伴随安装一个cudatoolkit包,安装确认之前(Yes/No),务必查看自己安装的tensorflow-gpu版本伴随安装的cudatoolkit版本,保证在11.0以上
第三个坑:conda命令下的tensorflow-gpu版本过低,使用pip安装更高版本
如果你使用conda命令安装,即
conda install tensorflow-gpu
在python=3.6的版本下,最高只支持到了2.4.1。但是tensorflow-gpu==2.4.1伴随安装的是cudatoolkit==10.1,在3090ti中无法使用进行加速运算,在后面跑程序的时候你会发现,数据会放到显存中,但是无法运算。
conda search tensorflow-gpu
所以这里我们要使用的是pip进行安装,pip 库中包含更高版本的tensorflow-gpu,
pip install tensorflow-gpu==
python=3.6环境下安装tensorflow-gpu==2.6.2
pip install tensorflow-gpu==2.6.2
python=3.7环境下安装tensorflow-gpu==2.8.0
pip install tensorflow-gpu==2.8.0
然后再使用conda 安装cudatoolkit==11.3.1
conda install cudatoolkit==11.3.1
5、pytorch配置
pytorch配置和tensorflow一样,需要注意的是在安装包之前,确认使用的cudatoolkit版本大于11.0,否则安装更高版本的pytorch。
这里python==3.6环境下,pytorch安装1.10.0以上版本
这里我还遇到了一个python=3.6的小版本过低的问题,最后升级到python==3.6.13小问题解决,所以尽量使用当前的最新python版本。
期间我还遇到了其他的小问题,比如python=3.7下的包可以使用,但是配置到3.6版本下就无法使用了。
总结:
1、进行深度学习框架的安装,cudn可以在虚拟环境中安装,外部不配置也可以
**
2、3090ti 在进行tensorflow-gpu和pytorch安装的过程中,确保cudatoolkit的版本大于11.0,若在安装其他包的时候,伴随将cudatoolkit降级的操作,谨慎进行,查看安装更高版本
**
3、conda下的某些包版本并不高,可以配合使用pip进行安装
最后给出我的两套环境下的yml配置文件,同样3090ti的显卡下,可以查看或者直接安装我的配置:
py36
python=3.6.13
tensorflow-gpu=2.6.2
tensorboard=2.6.0
keras=2.6.0
pytorch=1.10.2
scikit-learn=0.24.2
cudatoolkit=11.3.1
配置文件下载
py37
python=3.7.13
tensorflow-gpu=2.8.0
tensorboard=2.8.0
keras=2.8.0
pytorch=1.11.0
scikit-learn=1.0.2
cudatoolkit=11.3.1
配置文件下载
conda env create -f environment.yml
希望能帮助一些小伙伴,少踩一些坑,有理解的不对的或者未说清楚的,欢迎指正交流~
Original: https://blog.csdn.net/weixin_42213421/article/details/124225950
Author: 春天不是读书人
Title: Ubuntu20.04+3090ti+cudatoolkit=11.3+tensorflow-gpu=2.6+pytorch=1.10 环境配置踩坑记录 可通过配置文件迁移引用

009-独立按键与矩阵按键

ModuleNotFoundError: No module named ‘tensorflow‘

2022自动驾驶竞赛WAD介绍 CVPR 2022 Workshop on Autonomous Driving

NLP(一)——文本处理

WAV文件格式详解

ORB-SLAM3笔记(编译、踩坑、论文、看代码)

顶会预告 | Magic Data 与您相约 NAACL 2022

图像处理技术(二)滤波去噪(上)

Opencv之图像边缘检测:3.Laplacian算子(cv2.Laplacian)

把一个服务器上的环境迁移到另一个服务器上

iOS15更新体验报告

bert4keras加载BERT模型并获取文本字向量、句向量CLS

TensorFlow Lite post-training quantization (PTQ,训练后量化)

大数据分析-第八章 推荐系统
