ТАиВТ. Минхэш в компьютерных науках и интеллектуальном анализе данных MinHas
 Скачать 16.16 Kb.
|
|
Минхэш – в компьютерных науках и интеллектуальном анализе данных MinHas — это метод быстрой оценки того, насколько похожи два множества. Схема была изобретена Андреем Бродером ( 1997 г.) и первоначально использовалась в поисковой системе AltaVista для обнаружения дубликатов веб-страниц и исключения их из результатов поиска. [2] Он также применялся в крупномасштабных задачах кластеризации , таких как кластеризация документов по сходству их наборов слов. Коэффициент сходства Жаккара является широко используемым индикатором сходства между двумя множествами. Пусть U — множество, а A и B — подмножества U , тогда индекс Жаккара определяется как отношение числа элементов их пересечения к числу элементов их объединения:  Это значение равно 0, когда два множества не пересекаются , 1, когда они равны, и строго между 0 и 1 в противном случае. Два набора более похожи (то есть имеют относительно больше общих элементов), когда их индекс Жаккара ближе к 1. Цель MinHash — быстро оценить J ( A , B ) без явного вычисления пересечения и объединения. В качестве примера возьмём обычный текст, но в общем случае это может быть любым массивом байт. Штука в том, что для сравнения любого документа с помощью MinHash его необходимо сначала преобразовать в множество элементов. Возьмём предложения “мама мыла раму” и “ мама мыла ”. И представим их как множества и рассортируем: [мама, мыла, раму] и [мама, мыла] Мы можем увидеть, что их схожесть составляет 2/3. Так же ещё можно разделить элемента множества на N-граммы и схожесть ещё незначительно увеличится. Далее преобразуем эти множества в хеш-функции. Хеш-функция — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом. Преобразование, производимое хеш-функцией, называется хешированием. Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования называется «хешем». С этим мы разобрались, а что такое Min-Hash? MinHash — это минимальный хэш из всех хэшей нашего множества. Скажем, если у нас есть простая случайная хэшфункция f(v) = v, то наши множества ID слов [1, 2, 3] и [1, 2] преобразуются в множество хэшей [1078, 2573, 7113] и [1078, 2573], и для каждого множества минхэш равен 1078. Вроде несложно. Вероятность того, что минимальные хэши для двух множеств совпадут, весьма точно равна похожести этих двух множеств. В 1999 г. Петр Индик доказал, что любое k-независимое семейство хеш-функций также приблизительно независимо по минимуму для К достаточно большой. Показывать вывод доказательства я не буду, так как нам потребуются ещё лишние минут 20 это раз, а во вторых там будет мало что понятно, так как курс дикретной математики у нас только начался. Для закрепления результата мы можем взять много разных хэш-функций и для каждой из них найти минхэш. Довольно просто можно получить много разных хэш-функций, сгенерировав много случайных, но различных чисел, и ксорить нашу первую хэшфункцию на эти числа. Скажем, сгенерируем совершенно случайные числа 700 и 7000, что даст нам две дополнительные хэш-функции. Тогда минхэши для [1, 2, 3] будут (1078, 2573, 7113) -> 1078, (1674, 2225, 6517) -> 1674, (8046, 4437, 145) -> 145, а для [1, 2] минхеши, она же сигнатура будет равна (1078, 2573) -> 1078, (1674, 2225) -> 1674, (8046, 4437) -> 4437. Как видно, первые две пары минхэшей совпадают, из чего очень грубо можно предположить, что похожесть исходных множеств равна 2/3. Понятно, что чем больше хешфункций, тем точнее можно определить похожесть исходных множеств. |