文档章节

Python 实现 KD-Tree 最近邻算法

o
 osc_y8yehimr
发布于 2019/03/20 17:08
字数 347
阅读 22
收藏 0

精选30+云产品,助力企业轻松上云!>>>

这里将写了一个KDTree类,仅实现了最近邻,K近邻之后若有时间再更新:

from collections import namedtuple
from operator import itemgetter
from pprint import pformat
import numpy as np


class Node(namedtuple('Node', 'location left_child right_child')):
    def __repr__(self):
        return pformat(tuple(self))


class KDTree():
    def __init__(self, points):
        self.tree = self._make_kdtree(points)
        if len(points) > 0:
            self.k = len(points[0])
        else:
            self.k = None

    def _make_kdtree(self, points, depth=0):
        if not points:
            return None

        k = len(points[0])
        axis = depth % k

        points.sort(key=itemgetter(axis))
        median = len(points) // 2

        return Node(
            location=points[median],
            left_child=self._make_kdtree(points[:median], depth + 1),
            right_child=self._make_kdtree(points[median + 1:], depth + 1))

    def find_nearest(self,
                     point,
                     root=None,
                     axis=0,
                     dist_func=lambda x, y: np.linalg.norm(x - y)):

        if root is None:
            root = self.tree
            self._best = None

        # 若不是叶节点,则继续向下走
        if root.left_child or root.right_child:
            new_axis = (axis + 1) % self.k
            if point[axis] < root.location[axis] and root.left_child:
                self.find_nearest(point, root.left_child, new_axis)
            elif root.right_child:
                self.find_nearest(point, root.right_child, new_axis)

        # 回溯:尝试更新 best
        dist = dist_func(root.location, point)
        if self._best is None or dist < self._best[0]:
            self._best = (dist, root.location)

        # 若超球与另一边超矩形相交
        if abs(point[axis] - root.location[axis]) < self._best[0]:
            new_axis = (axis + 1) % self.k
            if root.left_child and point[axis] >= root.location[axis]:
                self.find_nearest(point, root.left_child, new_axis)
            elif root.right_child and point[axis] < root.location[axis]:
                self.find_nearest(point, root.right_child, new_axis)

        return self._best

测试:

point_list = [(2, 3, 3), (5, 4, 4), (9, 6, 7), (4, 7, 7), (8, 1, 1), (7, 2, 2)]
kdtree = KDTree(point_list)

point = np.array([5, 5, 5])
print(kdtree.find_nearest(point))

输出:

(1.4142135623730951, (5, 4, 4))

与 Scikit-Learn 性能对比(上是我的实现,下是 Scikit-Learn 的实现):

可以看到仅相差 1 毫秒,所以性能说得过去。

(本文完)

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
统计学习方法第三章:k近邻法(k-NN),kd树及python实现

统计学习方法第二章:感知机(perceptron)算法及python实现 统计学习方法第三章:k近邻法(k-NN),kd树及python实现 统计学习方法第四章:朴素贝叶斯法(naive Bayes),贝叶斯估计及python实现 ...

无限大的饿
2019/02/17
0
0
统计学习方法第四章:朴素贝叶斯法(naive Bayes),贝叶斯估计及python实现

统计学习方法第二章:感知机(perceptron)算法及python实现 统计学习方法第三章:k近邻法(k-NN),kd树及python实现 统计学习方法第四章:朴素贝叶斯法(naive Bayes),贝叶斯估计及python实现 ...

无限大的饿
2019/02/17
0
0
一文搞懂K近邻算法(KNN),附带多个实现案例

简介:本文作者为 CSDN 博客作者董安勇,江苏泰州人,现就读于昆明理工大学电子与通信工程专业硕士,目前主要学习机器学习,深度学习以及大数据,主要使用python、Java编程语言。平时喜欢看书...

AI科技大本营
2018/12/28
0
0
02-18 scikit-learn库之k近邻算法

[TOC]更新、更全的《机器学习》的更新网站,更有python、go、数据结构与算法、爬虫、人工智能教学等着你:<a target="_blank" href="https://www.cnblogs.com/nickchen121/p/11686958.html"......

osc_ibhs3ho3
2019/10/16
1
0
kd树 求k近邻 python 代码

  之前两篇随笔介绍了kd树的原理,并用python实现了kd树的构建和搜索,具体可以参考   kd树的原理   python kd树 搜索 代码   kd树常与knn算法联系在一起,knn算法通常要搜索k近邻,...

osc_sz3fldcb
2018/02/11
6
0

没有更多内容

加载失败,请刷新页面

加载更多

linux下java环境搭建

1、jdk下载: 官方地址:https://www.oracle.com/java/technologies/javase/javase-jdk8-downloads.html 如下图所示,我这边选择的是红框中的版本 2、压缩包上传至服务器 将下载的压缩包上传...

wc_飞豆
47分钟前
17
0
面试题:Java对象不再使用时,为什么要赋值为null?

前言 许多Java开发者都曾听说过“不使用的对象应手动赋值为null“这句话,而且好多开发者一直信奉着这句话;问其原因,大都是回答“有利于GC更早回收内存,减少内存占用”,但再往深入问就回...

码农突围
49分钟前
22
0
设计模式(5) 原型模式

原型模式 原型模式的适用场景 浅拷贝 深拷贝 用Initialize方法修改初始化状态 原型模式与之前学习的各种工厂方法、单例模式、建造者模式最大、最直观的区别在于,它是从一个既有的对象“克隆...

zhixin9001
49分钟前
7
0
获取免费的pycharm激活码网站

http://www.lookdiv.com/

云烟成雨forever
49分钟前
27
0
用Helm部署Kubernetes应用,支持多环境部署与版本回滚

1 前言 Helm是优秀的基于Kubernetes的包管理器。利用Helm,可以快速安装常用的Kubernetes应用,可以针对同一个应用快速部署多套环境,还可以实现运维人员与开发人员的职责分离。现在让我们安...

南瓜慢说
50分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部