Дедупликация данных

[Uzito]

Возник вопрос. Какие есть алгоритмы для дедупликации адресной книги?
Есть таблица в базе c 150000 записей - имя, фамилия, телефон, емейл, адрес, город, штат, страна, почтовый индекс.
Нужно создать другую таблицу, которая будет содержать ссылки на одинаковые или очень близкие по содержанию записи из оригинала.

Пример дупликатов:
Robert, Smith, 123-456-7890, blah@blah.com, 1 Main st, Chicago, IL, US, 12345
Bob, Smith, 123-456-7890
Dr. Robert, Smith, 123-4567890, blah@bah.com, One Main, Chicago, IL, US, 12345
Robert, Smith, 567-123-4567, a@a.com, ABC Hospital / 1 Main st, Chicago, IL, US, 12345

[zgur]

http://www.firstlogicsolutions.com/postalsoft.aspx

[zVlad]

Возник вопрос. Какие есть алгоритмы для дедупликации адресной книги?
Есть таблица в базе c 150000 записей - имя, фамилия, телефон, емейл, адрес, город, штат, страна, почтовый индекс.
Нужно создать другую таблицу, которая будет содержать ссылки на одинаковые или очень близкие по содержанию записи из оригинала.

Пример дупликатов:
Robert, Smith, 123-456-7890, blah@blah.com, 1 Main st, Chicago, IL, US, 12345
Bob, Smith, 123-456-7890
Dr. Robert, Smith, 123-4567890, blah@bah.com, One Main, Chicago, IL, US, 12345
Robert, Smith, 567-123-4567, a@a.com, ABC Hospital / 1 Main st, Chicago, IL, US, 12345

И зачем это? Я имею в виду зачем нужна другая таблица, которая бы содержала ссылки на очень близкие записи (одинаковые полнозтью записи должны просто удаляться, а ссылки на них соответствующим образом корректироваться).
Любой автомат (программный продукт), если он будет сам принимать решение о близкости данных рано или поздно ошибется и признает близкими то что на самом деле совершенно разное.

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

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

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

[Uzito]

Да, клиенты само-регистрируются на разные проекты и вводят близкие, но не всегда одинаковые данные. Вопрос встал, когда возникла необходимость собрать статистику по клиентам. Исправлять вручную 150000 записей народу не хватит, старые проекты уже закрыты и смысла (и легальной авторизации) править адреса и имена нет.

Так что хотелось бы найти более менее приличный способ аггрегировать клиентов под одним алиасом.

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

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

[zVlad]

Да, клиенты само-регистрируются на разные проекты и вводят близкие, но не всегда одинаковые данные. Вопрос встал, когда возникла необходимость собрать статистику по клиентам. Исправлять вручную 150000 записей народу не хватит, старые проекты уже закрыты и смысла (и легальной авторизации) править адреса и имена нет.

Так что хотелось бы найти более менее приличный способ аггрегировать клиентов под одним алиасом.

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

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

Пока они так и бубдут само-регистрироваться снежным ком будет расти и расти.

Вы не обратили внимания на мой вопрос: "И зачем это? Я имею в виду зачем нужна другая таблица, которая бы содержала ссылки на очень близкие записи (одинаковые полноcтью записи должны просто удаляться, а ссылки на них соответствующим образом корректироваться)." Может просто закрыть на это глаза, не тратить время и деньги на сизифов труд?

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

Кстати, в Вашей модели нет уникального атрибута. Как же тогда другие таблицы ссылаются на эту?

И опять же - что Вам даст искомая таблица алиасов?

[Uzito]

И зачем это? Я имею в виду зачем нужна другая таблица, которая бы содержала ссылки на очень близкие записи.

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

Кстати, в Вашей модели нет уникального атрибута. Как же тогда другие таблицы ссылаются на эту?

Уникальный аттрибут есть - CLIENT_ID, sequence, number. По нему и ссылаются.

Чует мое сердце, придется ваять на коленке приладу чтобы вручную похожие записи искать и объединять.

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

Ежедневно регистрируются 300-400 новых клиентов. Чтобы вручную проверять придется нанимать как минимум пару человек.

[mynameiszb]

Чует мое сердце, придется ваять на коленке приладу чтобы вручную похожие записи искать и объединять.

Это надо будет или подцеплять какой-то навороченный эврестический анализатор, или делать поделку с regexp и т.п.

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

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

[Boriskin]

По идее, фамилию никак низзя переделать, это будет первый разделитель на группы. Далее, по хорошему, надо сортировать по адресу, правда не очень понятно, как различать одно и тоже аля "10th line" & "Tenth line" или "3rd ave" & "Third ave", чисто теоритически можно попытаться присосаться к чему нить навроде google map и смотреть на "Do you mean xxxxx" или тупо снимать показания координат двух адресов - если координаты совпадают - значит адрес один.

Если совпали и фамилия и адрес - смотреть на имена, но это опять же не гарантирует - Вася Иванов может иметь сына Васю Иванова.

Вообще - непростая задачка из категории не решаемых точно.

[helg]

Адреса можно нормализовать через Google Maps API. Можно повторения в нормализованном текстое ловить. Лучше, наверно, ловить координатами - там ещё английский-испанский-французский схлопнутся в одну точку.

https://developers.google.com/maps/docu ... Structured
https://developers.google.com/maps/docu ... ngRequests

[Albert_al]

Поможет soundex function http://docs.oracle.com/cd/B19306_01/ser ... ons148.htm

[Teh Instructor]

Поможет soundex function http://docs.oracle.com/cd/B19306_01/ser ... ons148.htm

А еще лучше Levenshtein Distance - имплементаций можно найти на большинстве диалектах SQL и языком программирования.
Она показывает насколько одна строка "близка" к другой, своего рода "расстояние".
Алгоритм дедупликации тогда будет примерно такой - надо превратить каждую запись в строку и найти расстояния от каждой к каждой. Получится граф в моногомерном пространстве в котором точки - оригинальные записи соединены отрезками разной длины. Эти точки образуют "облака", где отрезки между точками относительно короткие. Каждое такое "облачко" будет соответствовать одной дедуплицированной записи.

[Uzito]

Поможет soundex function http://docs.oracle.com/cd/B19306_01/ser ... ons148.htm

А еще лучше Levenshtein Distance - имплементаций можно найти на большинстве диалектах SQL и языком программирования.
Она показывает насколько одна строка "близка" к другой, своего рода "расстояние".

Да, смотрел уже Левенштейна. Jaro-Winkler лучше, но проблема в том, что 150k*150k = 22 миллиарда сравнений. Оракл нагнулся и не разгибается.

[Teh Instructor]

Да, смотрел уже Левенштейна. Jaro-Winkler лучше, но проблема в том, что 150k*150k = 22 миллиарда сравнений. Оракл нагнулся и не разгибается.

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

[helg]

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