Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, marx paul, Вы писали:
MP>>из постановки задачи следует, что для определения степени похожести (similarity) вам надо испольовать просто match (= количество совпадающих элементов).
MP>>Если будете читать литературу по similarities — не искушайтесь пользовать продвинутые функции типа cosine similarity - они, конечно, модные и красивые по замыслу, но работают хуже, чем та же евклидова дистанция. Для обобщения решения насчитанные similarities лучше отнормировать в пределах [0..1]. Но в Вашей постановке задачи это не критично.
К>А почему расстояние Евклида, а не Хэмминга (это, кстати, частный случай манхеттенского расстояния)?! Или Хэмминг заморочнее?
стоп машины!
Azazar'у я как раз и рекомендовал использовать match (известный в области information processing как hamming distance).
А евклидово расстояние
как характеристика похожести на практике работает лучше, чем cosine similarity. Потому что последнее не чувствительно к шкале и на последовательностях {1,2,3} и {7,8,9} даст меру похожести 100%. Словом, это были две разные мысли.
К>
К>На неискушённый взгляд: что, если сперва сделать выборку по грубому критерию?
К>Например: каждому булеву вектору соответствует его вес — расстояние Хэмминга от нулевого вектора.
тогда {0,1,0,1}, {1,1,0,0}, {1,0,1,0} и т.д. будут иметь один и тот же "вес", не смотря на то, что "активированы" у них разные измерения.
К>Всё множество векторов разбиваем на подмножества с одинаковыми весами (векторы, лежащие на "сферах" соответствующего радиуса).
поправьте меня, если я ошибаюсь, но мне кажется, что из-за "булевости" всех массивов в исходной задаче, радиусы всех возможных сфер будут равны "весу" подгруппы (за исключением null space {0,0,..,0})
К>И искать соответствие будем, начиная со "своей" сферы (радиус равен радиусу искомого вектора), постепенно отступая в обе стороны.
... не понял, куда отступать? если мы уже в верной подгруппе, то остается только менять измерения. а отступать-то, вроде и некуда.
К>Очевидно, что сфера D/2 (где D — размерность пространства) имеет максимальную "площадь", и мы можем нарваться на линейный перебор.
К>Чтобы избежать этого, введём ещё одно разбиение — по расстояниям от какого-нибудь вектора на сфере D/2 — например, от 01010101...01 или 00...011...1.
К>То есть, всем векторам сопоставлены несколько чисел — расстояния от нескольких опорных точек.
в итоге получаем lookup tables в количестве, равном количеству опорных точек, с количеством элементов n(n-1)/2 каждая.
К>Нужно найти вектор, чьи расстояния минимально отличаются от расстояний искомого вектора. То есть, некий аналог триангуляции
то есть искать будем уже не по массиву булевых массивов, а по массиву реальночисленных массивов
К>Таким образом, мы из D-мерного двоичного пространства перебрались в малоразмерное D-ричное.
К>(Хотя подразумевается, что это пространство N-мерное, где N — количество исходных векторов).
К>Выбор опорных точек — может быть и не априорный, а на основе анализа исходного множества.
короче, вроде, решение я понял и, на мой взгляд, оно должно работать.
но по эффективности и количеству используемых данных оно уступает простой lookup table похожестей
