Здравствуйте, Кодт, Вы писали:

К>>>На неискушённый взгляд: что, если сперва сделать выборку по грубому критерию?
К>>>Например: каждому булеву вектору соответствует его вес — расстояние Хэмминга от нулевого вектора.

MP>>тогда {0,1,0,1}, {1,1,0,0}, {1,0,1,0} и т.д. будут иметь один и тот же "вес", не смотря на то, что "активированы" у них разные измерения.
К>Именно так. Твои векторы лежат на разных краях одной сферы с радиусом 2 и центром в {0,0,0,0}.

К>>>Всё множество векторов разбиваем на подмножества с одинаковыми весами (векторы, лежащие на "сферах" соответствующего радиуса).

MP>>поправьте меня, если я ошибаюсь, но мне кажется, что из-за "булевости" всех массивов в исходной задаче, радиусы всех возможных сфер будут равны "весу" подгруппы (за исключением null space {0,0,..,0})

К>Ну да. А почему "за исключением"? Вектор 0000 лежит на сфере нулевого радиуса.

Да как-то из линейной алгебры сохранилось нежное отношение и осторожность к этому вектору. В основном из-за того, что это null space и в него проецируется, что не может спроецироваться в наше пространство, т.е. все подряд (в частности мультиколинеарные вектора из-за которых матрица получается вырожденной, ну и прочие там сингулярности). И радиус этой сферы нулевой только в пространстве ранга матрицы. А если ранг матрицы не полный, то радиус нулевого вектора != 0.

К>Вектор 1111 — на сфере радиуса 4.
К>Площадь сферы равна C(D,R).

К>Может быть, слово "сфера" неудачно. Это грань гипероктаэдра (эквидистанта по манхеттенской метрике).

ну да и фиг с ним.

К>>>И искать соответствие будем, начиная со "своей" сферы (радиус равен радиусу искомого вектора), постепенно отступая в обе стороны.
MP>>... не понял, куда отступать? если мы уже в верной подгруппе, то остается только менять измерения. а отступать-то, вроде и некуда.

К>Ну если мы в верной подгруппе не нашли совпадения. Задача-то найти вектор, наиболее близкий к заданному, а не обязательно — точно совпадающий.

+1. Это до меня дошло, что ты имел ввиду, когда я уже отправил сообшение

К>Для точного совпадения все эти танцы с бубном не нужны: вводим абсолютно произвольный (например, лексикографический) порядок, сортируем вектора в этом порядке, и двоичным поиском скачем по этой последовательности. Можно ещё хэш-функцию прикрутить для ускорения поиска — порядок-то нас не интересует.

К>Расстояние до 0000 — это не хэш-функция, точнее, не только хэш-функция. Потому что нас интересует не только тот же самый класс, но и смежные классы (тогда как хэш-функция хэширует, т.е. перемешивает, классы в произвольном порядке).

MP>>в итоге получаем lookup tables в количестве, равном количеству опорных точек, с количеством элементов n(n-1)/2 каждая.

К>Да, lookup table — возможно, иерархически устроенная.

К>>>Нужно найти вектор, чьи расстояния минимально отличаются от расстояний искомого вектора. То есть, некий аналог триангуляции
MP>>то есть искать будем уже не по массиву булевых массивов, а по массиву реальночисленных массивов

К>... но при этом радикально сужаем и очень постепенно наращиваем круг поиска.

MP>>короче, вроде, решение я понял и, на мой взгляд, оно должно работать.
MP>>но по эффективности и количеству используемых данных оно уступает простой lookup table похожестей

К>Я не очень понял твоё решение.
К>Как с помощью таблицы d[i,j] = |v[i],v[j]| можно найти v[k] наиболее близкий к данному вектору u?

если i и j — сигнатуры векторов (а с булевыми массивами тут проблем не будет, т.к. их всегда можно представит байтом/словом и т.д.),
то если k равно одному из i, то мы тупым поиском можем найти j, с наименьшей дистанцией до i (или наибольшей похожестью) — так же, как ты описал выше.
если нет — мы считаем (нормированные) дистанции от k до всех j до тех пор пока не получим d[k,j] == 1. такой j и будет искомым массивом/вектором.
Для нового вектора надо будет посчитать максимум n дистанций. При добавлении нового вектора — (n-1). [в твоем варианте k*n]

К>Кроме того, "по количеству данных" моё решение занимает O(N*K) памяти где K — количество опорных точек (какое-то небольшое).
К>А таблица похожестей — это O(N*N).
Ну да, ты прав. У тебя чаще должно быть меньше (все зависит от k).
А таблица похожестей — симметрична и всегда занимает памяти n(n-1)/2.

Налицо трейдофф. При малых n твоя моделька может выигрывать. При больших n — твоя выигрывает по памяти, но может уступать по скорости.