Являются ли деревья KD эффективными, когда большинство / все атрибуты дискретны, а расстояние эквивалентно?

Question

Всегда говорят, что деревья KD отлично подходят для поиска ближайших соседей.Однако, если ваш набор данных - это все дискретные значения, без реальной метрики расстояния, они все еще эффективны?

Например, если ваши атрибуты были чем-то вроде [black, blue, red], [bread, milk, cheese], [right, left, straight, curved] Нет преемственности, и единственный способ измерить расстояние - это расстояние Хэмминга (где мы проверяем, сколько из них эквивалентно примеру тестирования).Деревья KD все еще эффективно сохраняются в этих сценариях?Как получилось?

Answer 1

Деревья KD все еще требуют понятия размеров. Ваши примеры не описывают точки данных в терминах измерений, дискретных или нет, поэтому дерево KD не применяется. Кроме того, деревья KD основаны на некоторых неравенствах, которых может не иметь отображение таких данных в измерениях.

При этом дискретные данные не являются проблемой, если они отображаются аккуратно, как указано выше - компьютеры хранят только дискретные приближения.

Answer 2

Я думаю, что было бы целесообразно рассмотреть, каким будет (ближайший) "сосед", если в вашем наборе значений нет метрики.В частности, как определить, находятся ли элементы в наборе рядом или далеко друг от друга без измерения расстояния?

При этом KD-деревья могут работать для дискретных множеств.Некоторые из них, по сути, эффективны благодаря возможности делить данные, чтобы мы могли исключить фрагменты элементов одним сравнением, как любое другое сбалансированное дерево.Но наиболее естественным является использование наборов, которые имеют полезную и значимую топологию.