Ответ 1
Сначала возьмем второй вопрос:
И что я могу сделать для улучшения реализации С# MinHash?
Вы пытаетесь сравнить изображения на уровне byte для файлов, которые по своей сути структурированы очень по-разному (вы используете TIFF как одно изображение, а GIF - в другом). Даже если визуально эти файлы были точно такими же, ваша реализация никогда не найдет дубликаты, если файлы не имеют один и тот же тип.
Тем не менее, ваша реализация minhash должна зависеть от сопоставимых атрибутов изображений, которые вы используете для создания подписей.
Хотя значение байтов, безусловно, является атрибутом изображения, их нельзя сравнивать друг с другом, если они находятся в разных форматах.
Для изображений вы можете использовать, например, RGB (и, возможно, альфа) значения для каждого пикселя изображения. Эти значения сопоставимы независимо от формата изображения (вы можете использовать CMYK или любое другое цветовое пространство, которое вы хотите).
Однако использование отдельных значений для каждого пикселя даст вам плохие результаты. сходство с Jaccard используется для сравнения значений из каждого набора (независимо от того, есть ли у вас что-либо) или потому что у наборов нет никакого порядка назначенные им, изображения с одинаковым количеством пикселей одного и того же цвета, но расположенные в разных пространствах, приведут к ложному срабатыванию.
Возьмем, к примеру, следующие изображения:
Они равны 100px x 100px с 50 пикселями красного и 50 пикселей зеленого цвета.
Используя сходство Jaccard для сравнения двух, вы получите следующее (обратите внимание, что, поскольку значения одинаковы, набор содержит только один элемент для каждого цвета. Если вы хотите, вы можете использовать сравнение Jaccard bag, чтобы сравнить мешки с несколькими значениями одного и того же элемента, но в этом случае значение будет одинаковым):
Legend:
g = green
r = red
left image = { r, g }
right image = { r, g }
similarity = intersection(left, right) / union(left, right)
similarity = 1 / 1 = 100%
Заметка о представлении right image = { r, g }: потому что наборы неупорядочены, { r, g } совпадает с { g, r }, поэтому они действуют, то же самое, даже если вычисление Jaccard не вычисляется, этот момент делает очевидным.
Но, очевидно, эти изображения не совпадают.
Вот почему shingling обычно используется для поиска отдельных мини-регионов внутри набора, которые могут использоваться совместно, чтобы однозначно идентифицировать пункт.
Для изображений вы можете использовать последовательные значения RGB (в этом случае, перемещаясь слева направо, сверху вниз, обертывая при ударе края) фиксированной длины для генерации черепицы. В этом случае, если длина гальки равна трем, ваши наборы выглядят так (обратите внимание, что я использую квадратные скобки для обозначения атрибутов/векторов, поскольку черепица сама по себе не содержит):
left image = { [r, r, r], [r, r, g], [r, g, g], [g, g, g] }
right image = { [g, g, g], [g, g, r], [g, r, r], [r, r, r] }
И дает вам сходство с Jaccard:
intersection(left, right) = 2
union(right, left) = 6
similarity(left, right) = 2 / 6 = 33.33%
Это гораздо более близкая оценка того, насколько похожи эти изображения (в этом они нет), чем оригиналы.
Обратите внимание, что черепица может быть любой длины, которую вы выберете. Вам нужно будет решить, какие черепицы создают подходящие результаты сходства с Jaccard (и порог), чтобы ответить на вопрос "насколько похожи эти?"
Теперь, отвечая на ваш первый вопрос:
что такое значение юниверса?
В этом конкретном случае это количество элементов, которые могут существовать во Вселенной. Если вы использовали одиночные пиксели RGB, юниверс был бы:
255 * 255 * 255 = 16,581,375
При черепице значение намного, намного выше, поскольку вы имеете дело с комбинациями этих предметов. В идеале вы хотите создать набор совершенных хеш-функций для вашего набора хэш-функций, которые minhash. Однако из-за ограничений систем типов (или, поскольку вы не хотите хранить очень большие числа на другом носителе), ваш фокус должен быть на хэш-функции, которые минимизируют конфликты.
Если вы знаете количество возможных элементов в юниверсе элементов, то это может помочь вам генерировать хэш-функции, которые уменьшают количество столкновений.