KD树(KNN的plus版

简介: KD树(KNN的plus版

核心思想

利用高维的二分查找,建立KD树,减小查找最近点的时间复杂度

算法内容

建立KD树

while(所有点挂载完){

1、每一层按逐个维度排序本层的点(什么叫逐个维度,就比如二维的点就x、y轮流替换)

2、取中位数作为本层根节点,左子树的放小的,右子树放大的

搜索

已知点 = input()

路径列表 = 空

while(true){

1、按照上面逐层按其维度向下搜寻路径,加入路径列表

if (叶子节点加入路径列表){break}

最小距离 = 空

while(路径列表不为空){

1、计算已知点到路径列表最后一个点的距离,给最小距离一直存储最小距离

2、该点从路径列表移除

3、比较最小距离和到路径列表最后一个点的维度距离

4、if(相交){将另一侧的点加入路径列表}

参考

【KD树 - CSDN App】http://t.csdnimg.cn/tzUtp

目录
相关文章
|
24天前
|
机器学习/深度学习 算法 搜索推荐
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
Machine Learning机器学习之决策树算法 Decision Tree(附Python代码)
|
1月前
|
机器学习/深度学习 算法 数据库
KNN和SVM实现对LFW人像图像数据集的分类应用
KNN和SVM实现对LFW人像图像数据集的分类应用
34 0
|
1月前
|
机器学习/深度学习 算法 数据挖掘
请解释Python中的决策树算法以及如何使用Sklearn库实现它。
决策树是监督学习算法,常用于分类和回归问题。Python的Sklearn库提供了决策树实现。以下是一步步创建决策树模型的简要步骤:导入所需库,加载数据集(如鸢尾花数据集),划分数据集为训练集和测试集,创建`DecisionTreeClassifier`,训练模型,预测测试集结果,最后通过`accuracy_score`评估模型性能。示例代码展示了这一过程。
|
1月前
|
机器学习/深度学习 算法
随机森林算法是如何通过构建多个决策树并将它们的预测结果进行投票来做出最终的预测的?
【2月更文挑战第28天】【2月更文挑战第102篇】随机森林算法是如何通过构建多个决策树并将它们的预测结果进行投票来做出最终的预测的?
|
1天前
|
算法
数据结构与算法-AVL树入门
数据结构与算法-AVL树入门
5 0
|
1天前
|
算法
数据结构与算法-Trie树添加与搜索
数据结构与算法-Trie树添加与搜索
5 0
|
1天前
|
机器学习/深度学习 数据采集 算法
共享单车需求量数据用CART决策树、随机森林以及XGBOOST算法登记分类及影响因素分析
共享单车需求量数据用CART决策树、随机森林以及XGBOOST算法登记分类及影响因素分析
|
2天前
|
机器学习/深度学习 自然语言处理 算法
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享(下)
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享
10 0
|
2天前
|
机器学习/深度学习 算法 大数据
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享(上)
【视频】K近邻KNN算法原理与R语言结合新冠疫情对股票价格预测|数据分享
|
2天前
|
机器学习/深度学习 算法 数据挖掘
R语言逻辑回归、Naive Bayes贝叶斯、决策树、随机森林算法预测心脏病
R语言逻辑回归、Naive Bayes贝叶斯、决策树、随机森林算法预测心脏病