2013-02-19 5 views
0

Мне недавно поручили разработать алгоритм проверки дубликатов записей клиентов в базе данных. макета DB довольно прост: десятки тысяч строк с полями, как FullName, улица, город, почтовый индекс, телефон, и т.д. ...Предварительный выбор вероятности для приближенного соответствия строк

Сначала немного:

Я сделал некоторые обширные исследования по алгоритмов, и решили, что каждое поле должно взвешиваться в определенной сумме с различными алгоритмами, поскольку не все они одинаково хорошо подходят при любых обстоятельствах. Например, LastName имеет коэффициент веса 0.50. Когда я оцениваю я выбирать, какие алгоритмы использовать и сколько они весят на окончательном решении:
фактора 0,25: JaroWinkler
Factor 0,60: косинус 2-гры Сходство
Factor 0,15: DamerauLevenshtein

Все работает хорошо, и с небольшой настройкой я обнаруживаю положительные результаты с небольшой ошибкой. Пока все хорошо. Однако, как вы можете себе представить, наличие времени выполнения O (n^2) - или фактически E-формы i = 0 до i = n - не очень эффективно при работе с десятками тысяч записей. Излишне говорить, что оптимизация с помощью оптимизации компилятора для скорости, многопоточности и т. Д. - это просто бандаиды, так как реальной проблемой является сложность.

По существу, я ищу способ предварительной фильтрации потенциальных совпадений и провел три дня исследований по этому вопросу. Я нашел ценную информацию о R-деревьях, R * -Trees, KD-деревьях, евклидовых векторах, minhashing и др. Тем не менее, большая часть информации обо всех этих, ну, весьма высокообразовательная. Самый ценный ресурс, я нашел в «Mining Наборов Массивных данных», глава 3.

Теперь мой вопрос:

Я прочитал всю эту информацию, но я не знаю, как поставить его все вместе.

Я думал о некотором индексировании в структуре данных дерева или графа, где я могу положить строку и сказать «Найди мне все, что имеет вероятность совпадения> 0,20». Этот алгоритм должен быть очень быстрым. Затем, когда я получаю список потенциальных (> 0.20) совпадений, я мог бы пойти и сравнить несколько элементов с моим «дорогим», но выборочным алгоритмом. Это должно сократить время выполнения до очень разумного значения, которое я считаю.

Я пытаюсь найти какой-то ссылочный код, чтобы делать то, что хочу делать выше, но я, кажется, не придумываю ничего, кроме научных статей. Я нашел «simstring», который на самом деле скомпилирован, но, похоже, не очень хорошо соответствовал 7 тестовым записям. Может ли кто-нибудь указать мне в правильном направлении? Конечно, кто-то должен был столкнуться с этим раньше и нашел решение ...

Спасибо вам большое!

P.S. Я делаю это в C++, но любые образцы в C#/C/Java/PHP будут в порядке.

ответ

1

Я ahve наконец удалось осуществить предварительный отбор, выполнив следующие действия: 1. Используйте определенные поля записи клиента построить 2Grams 2. Minhash 2Grams с Familiy 6 функций minhash к 192 битной подписи 3 Используйте реализацию rtree библиотек boost :: geometry для создания 6-мерного пространственного индекса над сигнатурами 4. Выберите ближайшую запись k (im my case 30) для записи, которую я сравниваю, и на этих кандидатах запускают оригинальные " дорогостоящее сравнение 5. Это уменьшает сложность от E (i, i = n, i = 1) до примерно 30n + m, где m - это время, необходимое для построения индекса (почти незначительно, неожиданно).

Я могу выполнить 15 000 сравнений с высокой точностью за 60 секунд, и это в однопоточном тесте. Многопоточность до 4 или 8 ядер будет работать еще быстрее.

1

Как первый разрез, я бы просто выделил те строки, которые были близки к той же длине, с которой они могли бы совпадать с заданной вероятностью. Это не будет очень избирательным, но (если вы не укажете довольно неплохие допуски), вероятно, устранит довольно большой процент невозможных совпадений очень быстро. (например., с метрикой редактирования, такой как Levenshtein, которая учитывает вставку как 1 операцию, если вы начинаете с строки длиной 5 и должны совпадать в течение 5 операций, тогда вы можете исключить все строки длиной более 10 без дальнейшего изучения).

Будет ли это достаточно избирательным, чтобы перейти прямо к вашему дорогостоящему сравнению, остается открытым вопрос - очевидно, что это будет зависеть от изменчивости длин строк, которые вы сопоставляете.

+0

Спасибо, что это определенно полезно. Об этом они говорили в главе 3 книги по интеллектуальному анализу. Я думаю, что длина строки может быть жизнеспособной, но не Левенштейном (иногда в записях есть почитаемые поля, такие как «Джон Смит» и «Смит, Джон», где Левенштейн ошибочно устраняет их как совпадение). Я дам длину строки и сравните время выполнения. У вас есть какой-либо вклад в жизнеспособность других вариантов (R/KD Tree и т. Д.), Упомянутых тоже? По крайней мере, почему они не будут красивыми (кроме сложности)? – namezero