二维空间KD-Tree生成的边界矩形如何编号满足顺序单调性,该方法可否拓展至高维
基于scikit-learn KD-Tree空间划分矩形的单调性编号探究
基础实验配置
- 输入数据集:1000个二维空间数据点,存储为列表
lst - 空间划分逻辑:基于scikit-learn框架的KD-Tree算法,设置参数
leaf_size=30,生成尺寸近似相等的空间划分边界矩形,核心初始化代码为:
import sklearn lst # 存储1000个二维数据点 sklearn.KDTree(lst, leaf_size=30)
- 提取的划分结果要素:
mins:所有划分矩形的左下角坐标集合maxs:所有划分矩形的右上角坐标集合data:每个矩形对应的归属数据点集合
核心探究目标
- 验证第一类问题:是否存在可行的矩形编号(索引)规则,满足全局顺序单调性要求——若矩形B内任意点(x,y)的坐标分量全大于矩形A内任意点(x',y')(即同时满足x>x'且y>y'),则B的映射编号必须严格大于A的映射编号
- 验证第二类问题:符合要求的编号规则是否能够拓展应用到更高维度的空间场景
已尝试方案的失效情况
此前测试了两类基于距离的排序编号方案,均存在跨位置矩形的单调性失效问题,空间中部区域的矩形排序错位尤为突出:
- 方案一:按矩形左下角到原点的距离排序编号
- 方案二:按矩形右上角到原点的距离排序编号
典型错位案例:采用右上角到原点距离排序生成的编号中,相邻编号13、14的矩形完全违反单调性要求:矩形13内存在坐标分量全大于矩形14内任意点的情况。仅手动互换这两个错位矩形的编号,虽在局部案例上逻辑自洽,但尚未从理论层面证明该调整思路的全局有效性。
现有距离排序逻辑实现代码
import numpy as np # mins为所有矩形的左下角坐标集合 # maxs为所有矩形的右上角坐标集合 # data为每个矩形对应的归属数据点集合 mins, maxs, data # 计算每个矩形右上角到原点的距离作为排序键 distances = [distance(i, [0]*2) for i in maxs] sort_indices = np.argsort(distances) # 按排序结果重排所有矩形的对应属性 mins = mins[sort_indices] maxs = maxs[sort_indices] data = [data[i] for i in sort_indices] # 后续可通过matplotlib可视化矩形边界与归属数据点
内容的提问来源于stack exchange,提问作者George Wu
相关产品推荐
相关产品推荐

