Сделать алгоритм Sim Hash (локально-чувствительное хеширование) более точным?
У меня есть "записи" (в основном строки 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?
РЕДАКТИРОВАТЬ: До SimHashing я пишу с большой буквы и удаляю все символы [0-9A-Z]. Примеры вещей, которые должны совпадать (орфографические ошибки являются преднамеренными):
- ДЖОН СМИТ, ЛЮБАЯ УЛИЦА, 123, ЗИМА
- ДЖОННИ СМИТ, 123 ЛЮБОГО СТРЕТА
- SOMETOWNE ZIP РОБЕРТ ПАРКЕР, 442 ЛЮБАЯ УЛИЦА SOMETOWN ZIP
Здесь 1 и 2 похожи, 3 нет. Выход должен быть: 1 + 2
2 ответа
Прежде чем пытаться проявить фантазию и изменить сим-хэш, пытались ли вы применить специфические знания предметной области к проблеме?
У вас есть список пропущенных пар для вашего алгоритма? Есть ли у них что-то общее?
Пытались ли вы сделать такие вещи, как удаление заглавных букв, преобразование псевдонимов в полные имена, удаление отчеств, расширение N, E, S, W и север, юг, восток, запад, расширение st до улицы и т. Д.?
(Я бы поставил ниже в комментарии, но пока нет представителя.)
Что в итоге вы пытаетесь сделать? Найти все дубликаты? Как вы определяете дубликаты? Чувствительность к регистру имеет значение? Похожая формулировка?
Я немного озадачен тем, как вы поступаете по этому поводу - находите похожие записи и создаете набор, но затем, позже, O(n^2) проверяет, что я предполагаю, является точным равенством. Если вы проверяете точное равенство, то это, похоже, лишает цели поиска похожих записей (если только вы не используете это в качестве фильтра для вашего O(n^2), чтобы сэкономить время.
Несколько случайных мыслей: Проведите каждую запись через своего рода дезинфицирующее средство, которое пытается преобразовать каждую запись в наиболее общую форму (если вам это важно / это имеет значение).
Если вас интересует точное равенство, и память не является ограничением, но вы ищете скорость, вы можете просто создать объект Java для каждой записи. Определите.equals() для каждой записи (вы всегда можете настроить ее так, чтобы не было точного равенства). Затем вам нужно будет определить hashCode() для этого объекта. Затем вы можете вставить каждую запись в HashSet.
Полученный HashSet не будет иметь дубликатов (как определено вашей реализацией.equals() / .hashCode()).
Или, если вы хотите найти дубликаты, то перед тем, как добавить в HashSet, проверьте, содержит ли он запись вначале, а если да, то вы нашли дубликат.
Эта реализация будет очень быстрой, но потенциально может использовать много памяти, так как вы будете хранить весь набор данных в памяти. Альтернативой этому может быть создание хеша для каждой записи, а затем сохранение его в HashSet и проверка хешей для каждой записи на равенство.
Недостатком создания хэша для каждой записи является проблема создания хорошего хэша с хорошим распределением и, конечно же, с хэшем, вам нужно беспокоиться о ложных срабатываниях при столкновениях. Но если ваш алгоритм хеширования является надежным, то вероятность столкновения должна быть настолько редкой, что вам не стоит об этом беспокоиться.
Некоторые мысли о хешах, которые вы могли бы сделать, являются чем-то простым, как MD5 конкатенации всех полей. Вы могли бы сделать контрольную сумму. Или вы можете взять сумму хэш-кода для каждого поля. Я не гений супер математики, поэтому я не могу сказать вам, какое поведение будет наилучшим при распределении и, следовательно, приведет к наименьшей вероятности возникновения коллизий. Возможно, стоит попробовать, если вы решите пойти по этому пути.
Simhash не является подходящим алгоритмом для этой цели, так как он полезен только для обнаружения почти дублированных, когда различия очень незначительны, а большая часть функций идентична. См. Мой учебник по симхашу и решению проблемы расстояния Хэмминга.
Лучшим подходом был бы minhash, возможно, с LSH. Похоже, что ваши функции для хеширования лучше всего сгенерировать в виде черепицы символов (с длиной, возможно, 4), а не битой слов.
С учетом таких коротких текстовых полей и того, что порядок слов, вероятно, не сильно изменится, вам следует подумать о включении оконечной черепицы: черепицы от начала и конца текстового поля, которые содержат меньше, чем обычно, количество символов, плюс конечный знак. Это, как правило, более снисходительно к различиям в написании коротких отрывков текста, например, "Уитмор" и "Уайтмор" без завершения черепицы даст
[ WHIT, HITM, ITMO, TMOR, MORE ] и [ WHIT, HITE, ITEM, TEMO, EMOR, MORE ] с низким сходством по Жаккару 2/9;
тогда как с включенной концевой черепицей они дали бы
[ #W, #WH, #WHI, WHIT, HITM, ITMO, TMOR, MORE, ORE#, RE#, E# ] и [ #W, #WH, #WHI, WHIT, HITE, ITEM, TEMO, EMOR, MORE, ORE#, RE#, E# ] с более высоким сходством по Жаккару 8/15;
Предложения Роба Нейгауза о предварительной нормализации очень разумны. Я бы нормализовал длинные слова до их сокращений (например, "Сент-Джеймс-стрит" будет нормализован до "ST JAMES ST"). Нормализация в другом направлении может быть затруднена из-за иногда неоднозначных сокращений ("St" -> "STREET" или "SAINT"?), А также, сокращенные формы способствуют меньшему количеству черепицы и, следовательно, имеют меньшее влияние на общее сходство, что является хорошо, потому что люди часто ошибочно набирают "Дорога" вместо "Улица" и т. д., и это не сильно меняет смысл.