人们总是吹捧KD树非常适合最近邻搜索。但是，如果您的数据集都是离散值，没有真正的距离度量，它们仍然有效吗？
例如，如果您的属性类似于[black, blue, red], [bread, milk, cheese], [right, left, straight, curved]没有连续性，并且测量距离的唯一方法是汉明距离（我们检查有多少与测试示例等效）。KD树在这些情况下仍然有效吗？怎么来的？
问问题
804 次
2 回答
0
我认为如果您的一组值没有度量标准，那么考虑（最近的）“邻居”是什么可能是合适的。具体来说，如何在没有距离度量的情况下定义集合中的元素是彼此相近还是相远？
话虽如此，KD-trees 可以用于离散集。一些效率本质上来自能够划分数据，因此我们可以通过一次比较消除大量元素，就像任何其他平衡树一样。但是，最自然的用途是在具有有用且有意义的拓扑的集合上。
于 2010-12-24T05:30:24.223 回答
0
KD 树仍然需要维度的概念。您的示例并未根据维度（离散与否）来描述数据点，因此不适用 KD 树。此外，KD 树依赖于将此类数据映射到维度上可能没有的一些不等式。
话虽如此，如果离散数据如前所述整齐地映射，则不是问题——计算机只存储离散的近似值。
于 2011-08-03T04:59:02.210 回答