9 марта 2011 в 13:38

MinHash — выявляем похожие множества

Категорически приветствую! В прошлый раз я писал о вероятностном алгоритме определения принадлежности элемента множеству, в этот раз будет про вероятностную оценку похожести. Не надо большого ума, чтобы додуматься до следующего показателя схожести двух множеств А и Б:

коэффициент Жаккара

То есть, количество элементов в пересечении делённое на количество элементов в объединении. Эта оценка называется коэффициентом Жаккара (Jaccard, поэтому «J»), коэффициент равен нулю, когда множества не имеют общих элементов, и единице, когда множества равны, в остальных случаях значение где-то посередине.


Как его посчитать?


Давайте прикинем, как посчитать этот коэффициент для пары строковых множеств, скажем, мы задумали выяснить насколько один фрагмент текста похож на другой. Для начала, нам необходимо разбить текст на отдельные слова — это будут элементы наших множеств, затем надо как-то посчитать размеры пересечения и объединения.

Обычно, для эффективного выполнения двух последних операций, множества представляют как хэш-таблицы без ассоциированных с ключами значений, работает такая структура очень быстро. Построение таблицы — O(n), их нужно две, вычисление пересечения — O(n) и вычисление объединения тоже O(n), где n — количество слов в тексте. Вроде всё отлично, но давайте усложним задачу.

Предположим, что у нас есть набор текстовых данных (посты, комментарии, т.д.), хранящийся в базе данных, и при добавлении новых записей, нам необходимо отсеивать слишком похожие на уже существующие. В этом случае, придётся загружать все документы и строить для них хэш-таблицы. Хотя делается это довольно быстро, количество операций напрямую зависит от размеров документов и их количества.

Последняя проблема может быть решена индексированием, скажем, тем же Сфинксом, тогда для сравнения можно загружать только документы, имеющие некоторое подмножество общих слов. Работает это хорошо, но только для маленьких документов, для больших, тестируемые подмножества становятся слишком большими. Решением первой и этой производной проблемы мы с вами и займёмся.

Ключевая идея MinHash


Предположим, у нас есть: два множества А, Б и хэш-функция h, которая умеет считать хэши для элементов этих множеств. Далее, определим функцию hmin(S), которая вычисляет функцию h для всех членов какого-либо множества S и возвращает наименьшее её значение. Теперь, начнём вычислять hmin(А) и hmin(Б) для различных пар множеств, вопрос: чему равна вероятность того, что hmin(А) = hmin(Б)?

Если задуматься, эта вероятность должна быть пропорциональна размеру пересечения множеств — при отсутствии общих членов, она стремится к нулю, и к единице, когда множества равны, в промежуточных случаях она где-то посередине. Ничего не напоминает? Ага, всё верно, это и есть J(А, Б) — коэффициент Жаккара!

Беда в том, что если мы просто посчитаем hmin(А) и hmin(Б) для наших двух фрагментов текста, а затем сравним значения, это нам ничего не даст, т.к. варианта всего два — равно или не равно. Нам надо каким-то образом добыть достаточный объём статистики по нашим множествам, чтобы вычислить близкий к истине J(А, Б). Делается это просто, вместо одной функции h, вводим несколько независимых хэш-функций, а точнее k функций:

Кол-во функций

, где ε — желаемая наибольшая величина ошибки. Так, для вычисления J(А, Б) с ошибкой не более чем 0.1, необходимо 100 хэш-функций — не мало. В чём же плюсы?

Во-первых, можно посчитать, так называемую, сигнатуру Hmin(S), т.е. минимумы всех хэш-функций для множества S. Трудоёмкость её вычисления больше, чем при построении хэш-таблицы, но, тем не менее, она линейна, и сделать это для каждого документа нужно всего один раз, например при добавлении в базу, потом достаточно оперировать только сигнатурами.

Во-вторых, как вы могли заметить, сигнатура имеет фиксированный размер при заданной максимальной величине ошибки. Для того чтобы сравнить любые два множества любого размера, необходимо выполнить фиксированное количество операций. Кроме того, в теории, сигнатуры гораздо удобней индексировать. «В теории» потому, что их индексирование не очень хорошо ложится на реляционные базы данных, на полнотекстовые движки тоже не особо. По крайней мере, я не смог придумать, как сделать это красиво.

Игрушечная реализация


Как обычно, нам необходимо семейство хэш-функций:

function Hash(size)
{
    var seed = Math.floor(Math.random() * size) + 32;
    
    return function (string)
    {
        var result = 1;
        for (var i = 0; i < string.length; ++i)
            result = (seed * result + string.charCodeAt(i)) & 0xFFFFFFFF;
        
        return result;
    };
}

Сам MinHash:

function MinHash(max_error)
{
    var function_count = Math.round(1 / (max_error * max_error));
    var functions = [];
    
    for (var i = 0; i < function_count; ++i)
        functions[i] = Hash(function_count);
    
    function find_min(set, function_)
    {
        var min = 0xFFFFFFFF;
        for (var i = 0; i < set.length; ++i)
        {
            var hash = function_(set[i]);
            if (hash < min) min = hash;
        }

        return min;
    }
    
    function signature(set)
    {
        var result = [];
        for (var i = 0; i < function_count; ++i)
            result[i] = find_min(set, functions[i]);

        return result;
    }
    
    function similarity(sig_a, sig_b)
    {
        var equal_count = 0;
        for (var i = 0; i < function_count; ++i)
            if (sig_a[i] == sig_b[i]) ++equal_count;
        
        return equal_count / function_count;
    }
    
    return {signature: signature, similarity: similarity};
}

Пример использования:

var set_a = ['apple', 'orange'];
var set_b = ['apple', 'peach'];

var min_hash = MinHash(0.05);
var sig_a = min_hash.signature(set_a);
var sig_b = min_hash.signature(set_b);
alert(min_hash.similarity(sig_a, sig_b));

Тонкие моменты


В реальности, точность будет немного ниже, так как реальные хэш-функции не идеальны. Можно с этим смириться или ввести пару-другую дополнительных функций, хотя пара-другая не сильно поможет.

Почему-то нигде не упоминается, каким же должно быть количество битов выдаваемых функциями. По идее, это количество должно быть таким, чтобы представить все возможные варианты входных значений. Например, в английском языке порядка 250 000 слов, следовательно, достаточно порядка 18 бит. Но лучше, опять же, подстраховаться и добавить пару лишних битов.

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

Посравнивать тексты можно тут. Спасибо за внимание, до новых встреч.

P.S. ХабраСторадж у всех выдаёт ошибку при загрузке картинок или только у меня?
+30
2317
91
stab 48,3

комментарии (19)

+1
NYMEZIDE, #
Попробовал посравнивать по вашей ссылке. Текст который был слева скопировал в правую часть. Сравнение = 1.
Удалил "," и "." (всего 9 штук) — получаю = 0.585

Даже удаление нескольких слов дает 0,9хх. Почему из-за знаков препинания резко снижается индекс?
0
stab, #
Потому что это так для поиграться сделано, на слова разбивается просто по пробелам. Знаки препинания как часть слова в этом случае воспринимаются или как отдельное слово.
0
NYMEZIDE, #
но ведь хеш отдельных слов в сумме не может из-за одного символа резко так снижать индекс?

Просто я реализовывал (когда еще был студентом) для себя алгоритм подобной задачи.
Требовалось перелопатить все Excel входные файлы и привязать кривой ввод данных, от сотрудников и в особенности сотрудниц, к справочникам которые были получены и систематизированы в прошлом.
Входные данные были это были названия городов, населенных пунктов, улиц и т.д.
и у меня «ул. Чкалова» и «ул Чкалова» давали совсем не = 0.45, а 0.9х

Но я реализовывал подругому.
+1
Trept, #
В данной реализации слово, отличное на 1 символ — полностью другое слово, так что все верно.
0
stab, #
Вначале описан коэффициент Жаккара, у него именно такое поведение, плюс, не самые лучшие хэш-функции, на коротких словах плохо себя ведут.
+1
Trept, #
Думаю, нужно добавить, что ошибка при вычислении метрики похожести по методу MinHash нефатальна, поскольку всегда возможно пересчитать оригинальную метрику для близких множеств, выявленных по MinHash.
Иначе говоря, MinHash здесь будет работать, как предварительный фильтр, снижающий вычислительные затраты.
0
SergeyM, #
MinHash — это алгоритм снижения размерности, а не алгоритм поиска похожих множеств. Он используется как дополнение для алгоритмов поиска тех самых похожих множеств, когда объем данных очень велик. Изначально его применили для алгоритма поиска дубликатов документов.
0
stab, #
А какие алгоритмы есть для поиска похожих множеств? Актуальная для меня тема.
0
SergeyM, #
1. MinHash
2. LSH (Locality-Sensitive Hashing)

Это основные методы, может сейчас еще какие есть, я не слежу. LSH используется для поиска сильно похожих множеств.
+1
Trept, #
Это — вопрос терминологии, не более того.
Поясню: кому-то точности MinHash будет вполне достаточно, да и вопрос коллизий не всегда определяющий. В этом случае метод будет вполне полноценно искать похожие множества.
0
SergeyM, #
Это не различие терминологии, MinHash именно метод уменьшения размерности.
Простой пример: пусть у нас есть набор объектов, которые описываются большим вектором признаков, сравнивать такие объекты — это сравнивать их вектора-признаки, что очень дорого. Делаем чит — выбираем случайно и равновероятно объекты из этих векторов и получаем сокращенную сигнатуру, по которой и сравниваем все объекты. Вот эта случайная выборка и получается благодаря MinHash, потому что ее свойство — брать признаки равновероятно.
0
Trept, #
Я об этом способе использования MinHash выше написал.
А Ваш пример мой не опровергает, присмотритесь повнимательнее.
Кстати, интересно, свойство равновероятности для MinHash, хотя бы на уровне ассимптоты доказано?
+1
SergeyM, #
Возможно ли равновероятно брать значения? В идеале да, на практике стремятся к идеалу. Когда писал свой диплом, то тестировал этот MinHash и результаты мне понравились — в среднем алгоритм работает идеально, есть дисперсия, значение которой зависит от числа функций.
0
Trept, #
Для оценки равномерности распределения одной дисперсии маловато будет.
Не стоит ли оценить близость самого распределения, например, через обычную метрику скалярного произведения?
0
SergeyM, #
Я завис :) Честно, не знаю как ответить на этот вопрос.
0
Trept, #
Например, построим гистограмму, и оценим ее отклонения от равномерности.
+1
SergeyM, #
0
Trept, #
Например, построим гистограмму, и оценим ее отклонения от равномерности.
0
Trept, #
прошу прощения, не туда ответил

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.