Если список массивов одинакового размера с булеановскими значениями, надо сделать класс для быстрого поиска массивов в этом списке, и такого же быстрого добавления(скорость поиска важнее, чем скорость добавления). Если в списке не удаётся найти точную копию заданного массива — тогда должен возвращаться массив с минимальными отличиями(с максимальным количеством совпадающих значений). Кто-нить сталкивался с чем-то подобным?
Здравствуйте, Azazar, Вы писали:
A>Если список массивов одинакового размера с булеановскими значениями, надо сделать класс для быстрого поиска массивов в этом списке, и такого же быстрого добавления(скорость поиска важнее, чем скорость добавления). Если в списке не удаётся найти точную копию заданного массива — тогда должен возвращаться массив с минимальными отличиями(с максимальным количеством совпадающих значений). Кто-нить сталкивался с чем-то подобным?
а массивы какой длины?
а длина массово одинаковая?
Здравствуйте, Azazar, Вы писали:
A>Здравствуйте, marx paul, Вы писали:
MP>>а массивы какой длины? MP>>а длина массово одинаковая?
A>Одинаковой длинны.
ну, поскольку Вы так неохотно распространяетесь о, на мой взгляд, существенных параметрах Вашей задачи, то приведу типовое решение тоже без притензий на полноту и абсолютную оптимальность.
Во-первых, (если длина массива не очень велика) можно подумать над тем, чтобы предсавлять массивы булевых элементов в ввиде байтов/слов.
Во-вторых, при добавлении нового массива надо просчитать степень похожести добавляемого массива на каждый из уже присутствующих в коллекции. Таким образом, получим lookup-table размерностью n(n-1)/2. Потом, при поиске, остается только дернуть из lookup таблицы ключик для массива, наиболее похожего на искоммый.
из постановки задачи следует, что для определения степени похожести (similarity) вам надо испольовать просто match (= количество совпадающих элементов).
Если будете читать литературу по similarities — не искушайтесь пользовать продвинутые функции типа cosine similarity — они, конечно, модные и красивые по замыслу, но работают хуже, чем та же евклидова дистанция. Для обобщения решения насчитанные similarities лучше отнормировать в пределах [0..1]. Но в Вашей постановке задачи это не критично.
Здравствуйте, marx paul, Вы писали:
MP>из постановки задачи следует, что для определения степени похожести (similarity) вам надо испольовать просто match (= количество совпадающих элементов). MP>Если будете читать литературу по similarities — не искушайтесь пользовать продвинутые функции типа cosine similarity — они, конечно, модные и красивые по замыслу, но работают хуже, чем та же евклидова дистанция. Для обобщения решения насчитанные similarities лучше отнормировать в пределах [0..1]. Но в Вашей постановке задачи это не критично.
А почему расстояние Евклида, а не Хэмминга (это, кстати, частный случай манхеттенского расстояния)?! Или Хэмминг заморочнее?
На неискушённый взгляд: что, если сперва сделать выборку по грубому критерию?
Например: каждому булеву вектору соответствует его вес — расстояние Хэмминга от нулевого вектора.
Всё множество векторов разбиваем на подмножества с одинаковыми весами (векторы, лежащие на "сферах" соответствующего радиуса).
И искать соответствие будем, начиная со "своей" сферы (радиус равен радиусу искомого вектора), постепенно отступая в обе стороны.
Очевидно, что сфера D/2 (где D — размерность пространства) имеет максимальную "площадь", и мы можем нарваться на линейный перебор.
Чтобы избежать этого, введём ещё одно разбиение — по расстояниям от какого-нибудь вектора на сфере D/2 — например, от 01010101...01 или 00...011...1.
То есть, всем векторам сопоставлены несколько чисел — расстояния от нескольких опорных точек.
Нужно найти вектор, чьи расстояния минимально отличаются от расстояний искомого вектора. То есть, некий аналог триангуляции
Таким образом, мы из D-мерного двоичного пространства перебрались в малоразмерное D-ричное.
(Хотя подразумевается, что это пространство N-мерное, где N — количество исходных векторов).
Выбор опорных точек — может быть и не априорный, а на основе анализа исходного множества.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, 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 похожестей
Здравствуйте, marx paul, Вы писали:
MP>стоп машины! ... Словом, это были две разные мысли.
Ааа. Кудряво вышло.
То есть, "если уж не Хэмминг — то хотя бы Евклид, и не заморачиваться прочими изощрениями".
К>> К>>На неискушённый взгляд: что, если сперва сделать выборку по грубому критерию? К>>Например: каждому булеву вектору соответствует его вес — расстояние Хэмминга от нулевого вектора.
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 лежит на сфере нулевого радиуса. Вектор 1111 — на сфере радиуса 4.
Площадь сферы равна C(D,R).
Может быть, слово "сфера" неудачно. Это грань гипероктаэдра (эквидистанта по манхеттенской метрике).
К>>И искать соответствие будем, начиная со "своей" сферы (радиус равен радиусу искомого вектора), постепенно отступая в обе стороны. MP>... не понял, куда отступать? если мы уже в верной подгруппе, то остается только менять измерения. а отступать-то, вроде и некуда.
Ну если мы в верной подгруппе не нашли совпадения. Задача-то найти вектор, наиболее близкий к заданному, а не обязательно — точно совпадающий.
Для точного совпадения все эти танцы с бубном не нужны: вводим абсолютно произвольный (например, лексикографический) порядок, сортируем вектора в этом порядке, и двоичным поиском скачем по этой последовательности. Можно ещё хэш-функцию прикрутить для ускорения поиска — порядок-то нас не интересует.
Расстояние до 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?
Кроме того, "по количеству данных" моё решение занимает O(N*K) памяти где K — количество опорных точек (какое-то небольшое). А таблица похожестей — это O(N*N).
Здравствуйте, Кодт, Вы писали:
К>>>На неискушённый взгляд: что, если сперва сделать выборку по грубому критерию? К>>>Например: каждому булеву вектору соответствует его вес — расстояние Хэмминга от нулевого вектора.
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 — твоя выигрывает по памяти, но может уступать по скорости.
Перекуём баги на фичи!
