KD ツリーは最近傍検索に最適であると常に宣伝されています。ただし、データ セットがすべて離散値であり、実際の距離メトリックがない場合でも、それらは効率的でしょうか?
たとえば、属性が[black, blue, red], [bread, milk, cheese], [right, left, straight, curved]連続性がなく、距離を測定する唯一の方法がハミング距離のようなものである場合 (テスト例と同等の数を確認します)。これらのシナリオでも KD ツリーは有効に機能しますか? どうして？
KD ツリーには、依然として次元の概念が必要です。あなたの例では、離散かどうかにかかわらず、次元の観点からデータポイントを説明していないため、KDツリーは適用されません。さらに、KD ツリーは、そのようなデータのディメンションへのマッピングにはない不等式に依存しています。
そうは言っても、前述のようにきちんとマッピングされている場合、離散データは問題ではありません。コンピューターは離散近似のみを保存します。
一連の値にメトリックがない場合、(最も近い)「隣人」が何であるかを検討することが適切であると思います。具体的には、セット内の要素が互いに近いか遠いかを、距離を測定せずにどのように定義しますか?
そうは言っても、KD ツリーは離散セットに対して機能します。他のバランス ツリーのように、1 回の比較で要素のチャンクを削除できるように、データを分割できることから、いくつかの効率が本質的に得られます。ただし、最も自然な使用法は、有用で意味のあるトポロジーを持つセットです。