Сделать алгоритм Sim Hash (локально-чувствительное хеширование) более точным? - PullRequest
Новая
       37

Сделать алгоритм Sim Hash (локально-чувствительное хеширование) более точным?

5 голосов
/ 30 ноября 2011

У меня есть «записи» (в основном строки CSV) с двумя именами и одним адресом. Мне нужно найти записи, которые похожи друг на друга: в основном имена и части адреса выглядят «одинаково», как если бы они были интерпретированы человеком.

Я использовал идеи из этого отличного поста в блоге: http://knol.google.com/k/simple-simhashing#, чтобы написать простой SimHash. Если результаты SimHash для двух или более строк совпадают, я передаю все записи этого подмножества в программу детального соответствия, которая является O (n ^ 2), которая сравнивает каждую запись набора с любой другой записью.

Для части SimHash у меня есть параметры, в которых я могу определить размер дейтаграммы (в основном скользящее окно размера n над строками) и количество итераций, чтобы определить, сколько (случайных) хэшей мне нужно использовать для расчет SimHash. Пока что датаграмма имеет размер 4 и использует 4 хеша для вычисления SimHash. Я пробовал различные другие комбинации, но эта дает лучшие результаты.

Проблема, с которой я сталкиваюсь, заключается в том, что этот метод находит около 80% дубликатов в имеющихся у меня наборах данных. Я знаю это, потому что я проверил весь набор данных по болезненно медленному полному совпадению O (n ^ 2), упомянутому выше. Сопоставление O (n ^ 2) в порядке для наборов данных менее 10 ^ 4, но быстро становится невыполнимым, поскольку мне нужно запускать наборы размером 10 ^ 8.

Любые идеи, предложения или мысли о том, как я могу повысить точность SimHash, чтобы больше «похожих» записей помечалось одинаковым номером SimHash?

EDIT: До SimHashing я делаю все символы [0-9A-Z] с большой буквы и удаляю их. Примеры вещей, которые должны совпадать (орфографические ошибки являются преднамеренными):

  • ДЖОН СМИТ, ЛЮБАЯ УЛИЦА 123, ЗИП
  • ДЖОННИ СМИТ, 123 ЛЮБОГО СТРЕТА
  • SOMETOWNE ZIP РОБЕРТ ПАРКЕР, 442 ЛЮБАЯ УЛИЦА SOMETOWN ZIP

Здесь 1 и 2 похожи, 3 нет. Выход должен быть: 1 + 2

Ответы [ 2 ]

3 голосов
/ 30 ноября 2011

Прежде чем пытаться проявить фантазию и изменить хеш-код, пытались ли применить к этой проблеме знания, относящиеся к конкретной области?

У вас есть список пропущенных пар для вашего алгоритма? Есть ли у них что-нибудь общее?

Вы пытались делать такие вещи, как удаление заглавных букв, преобразование псевдонимов в полные имена, удаление отчеств, расширение N, E, S, W и север, юг, восток, запад, расширение st на улицу и т. Д.?

0 голосов
/ 30 ноября 2011

(я бы поставил ниже в комментарии, но у меня еще нет представителя.)

Что в конечном итоге вы пытаетесь сделать? Найти все дубликаты? Как вы определяете дубликаты? Чувствительность к регистру имеет значение? Аналогичная формулировка?

Я немного озадачен тем, как вы поступаете по этому поводу - находите похожие записи и создаете набор, но затем O (n ^ 2) проверяет то, что я предполагаю, является точным равенством. Если вы проверяете точное равенство, то это, похоже, лишает цели поиска похожих записей (если только вы не используете это в качестве фильтра для вашего O (n ^ 2), чтобы сэкономить время.

Несколько случайных мыслей: Проведите каждую запись через своего рода дезинфицирующее средство, которое пытается преобразовать каждую запись в наиболее общую форму (если вам важно / это имеет значение).

Если вас интересует точное равенство, и память не является ограничением, но вы ищете скорость, вы можете просто создать объект Java для каждой записи. Определите .equals () для каждой записи (вы всегда можете настроить ее так, чтобы не было точного равенства). Затем вам нужно будет определить hashCode () для этого объекта. Затем вы можете вставить каждую запись в HashSet.

Полученный HashSet не будет иметь дубликатов (как определено вашей реализацией .equals () / .hashCode ()).

Или, если вы хотите найти дубликаты, то перед тем, как добавить в HashSet, проверьте, содержит ли он запись, а если нет, то вы нашли дубликат.

Эта реализация будет очень быстрой, но потенциально может использовать много памяти, поскольку вы будете хранить весь набор данных в памяти. Альтернативой этому может быть создание хеша для каждой записи, а затем сохранение его в HashSet и проверка хешей для каждой записи на равенство.

Недостатком создания хэша для каждой записи является проблема разработки хорошего поколения хэшей с хорошим распределением И, конечно, с хэшами вы должны беспокоиться о ложных срабатываниях при столкновениях. Но если ваш алгоритм хэширования является надежным, то вероятность столкновения должна быть настолько малой, что вам не стоит об этом беспокоиться.

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

...