Набор данных для бессмысленного «Ближайшего соседа»?

Я думаю, что бумага правильная. Во-первых, ваш тест: одной из проблем с вашим тестом может быть то, что вы используете слишком мало баллов. Я использовал 10000 точек, и ниже приведены мои результаты (равномерно распределенные точки в [0,0 ... 1,0] во всех измерениях). При DIM=2 min/max различаются почти в 1000 раз, при DIM=1000 они отличаются только в 1,6 раза, при DIM=10000 в 1,248 раза. Так что я бы сказал, что эти результаты подтверждают гипотезу статьи.

DIM/N = 2 / 10000
min/avg/max= 1.0150906548224441E-5 / 0.019347838262624064 / 0.9993862941797146    
DIM/N = 10 / 10000.0
min/avg/max= 0.011363500131326938 / 0.9806472676701363 / 1.628460468042207
DIM/N = 100 / 10000
min/avg/max= 0.7701271349716637 / 1.3380320375218808 / 2.1878136533925328
DIM/N = 1000 / 10000
min/avg/max= 2.581913326565635 / 3.2871335447262178 / 4.177669393187736
DIM/N = 10000 / 10000
min/avg/max= 8.704666143050158 / 9.70540814778645 / 10.85760200249862

DIM/N = 100000 / 1000 (N=1000!)
min/avg/max= 30.448610133282717 / 31.14936583713578 / 31.99082677476165

Я предполагаю, что объяснение таково: давайте возьмем три случайно сгенерированных вектора, A, B и C. Общее расстояние основано на сумме расстояний каждой отдельной строки этих векторов. Чем больше размерностей имеют векторы, тем больше общая сумма разностей будет приближаться к общему среднему. Другими словами, крайне маловероятно, что вектор C во всех элементах имеет большее расстояние от A, чем другой вектор B от A. С увеличением размеров C и B будут иметь все более близкое расстояние до A (и друг от друга).

Мой тестовый набор данных был создан следующим образом. Набор данных, по сути, представляет собой куб со значениями от 0,0 до 1,0 в каждом измерении. Координаты были созданы с равномерным распределением по всем измерениям от 0,0 до 1,0. Пример кода (N=10000, DIM=[2..10000]):

public double[] generate(int N, int DIM) {
    double[] data = new double[N*DIM];
    for (int i = 0; i < N; i++) {
        int pos = DIM*i;
        for (int d = 0; d < DIM; d++) {
            data[pos+d] = R.nextDouble();
        }
    }
    return data;
}

Следуя уравнению, приведенному внизу принятого ответа здесь, мы получаем:

d=2 -> 98460

d=10 -> 142.3

d=100 -> 1.84

d=1,000 -> 0.618

d=10,000 -> 0.247

d = 100 000 -> 0,0506 (при использовании N = 1000)

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

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

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

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

Изменить о:

расстояния для каждой точки стали больше с большим количеством измерений!!!!

это ожидаемо, поскольку чем выше размерность пространства, тем оно разреженнее, а значит, тем больше расстояние. Более того, это ожидаемо, если подумать, например, о евклидовом расстоянии, которое становится тем больше, чем больше размеры.