Современное состояние дедупликации

Каковы современные методы дедупликации записей? Дедупликацию также иногда называют: связывание записи, разрешение объекта, разрешение идентификатора, объединение / очистка. Я знаю, например, о CBLOCK [1].

Я был бы признателен, если бы ответы также включали ссылки на существующее программное обеспечение, реализующее методы. Я знаю, например, что Mahout реализует кластеризацию навеса . Также есть герцог, который использует Lucene.

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

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

[1] CBLOCK: автоматический механизм блокировки для масштабных задач устранения дублирования

Tamr (ранее Data Tamer) выполняет дедупликацию базы данных в масштабе. Наивный байесовский и графа кластеризации участвуют.

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

Проверьте документ здесь .

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

Система дедупликации Tamr состоит из двух основных этапов работы с новым источником данных: (1) идентификация атрибута и (2) консолидация объектов. Они примерно эквивалентны дедупликации столбцов и дедупликации строк.

1) Сравнение нового источника данных с существующим, первым шагом является Идентификация атрибута.

Атрибуты (столбцы) нового источника сопоставляются с атрибутами существующего источника с помощью четырех алгоритмов:

• Сравните имена атрибутов с нечетким сравнением строк (косинусное сходство триграмм)
• Рассматривайте весь столбец как документ, разбивайте токены, измеряйте косинусное сходство общей частоты / обратной частоты документа (TF-IDF) между этим и другими столбцами.
• Минимальная описательная длина: сравните два столбца на основе размеров их пересечения и объединения с точным сопоставлением.
• Для числовых столбцов выполните t-тест между новым столбцом и существующими числовыми столбцами, чтобы определить, пришли ли они из одного и того же распределения.

2) Консолидация сущностей (дедупликация строк)

После идентификации атрибута мы хотим дедуплицировать строки (записи).

Категоризация с кластеризацией

Записи сначала группируются по категориям на основе сходства, а затем правила дедупликации изучаются на уровне категорий. В качестве примера классификации они приводят базу данных горнолыжных курортов, где западные горнолыжные курорты должны отличаться от восточных горнолыжных курортов, поскольку такие особенности, как базовая высота, сильно отделены от того, является ли курорт восточным или западным. Категоризация выполняется с помощью алгоритма кластеризации с использованием k-средних в качестве примера.

Дедупликация с наивным байесовским

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

Существует два типа правил дедупликации:

1. Пороговые значения для сходства атрибутов относительно функции расстояния, которая имеет смысл для атрибута. (В статье неясно, как эти пороги изучены.)
2. Распределение вероятностей для дупе и не дупс в каждом атрибуте. например P("Title" values similar | duplicate) ~ 1и Pr("State" values are different | duplicate) ~ 0

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

Мое предположение состоит в том , что для записи X1 = (a1,b1,c1,d1), X2 = (a2,b2,c2,d2)они вычисляют вектор подобия , S = (s_a, s_b, s_c, s_d)где s_iесть сходство для этого атрибута WRT на правильном расстоянии метрики.

Я предполагаю, что их наивный байесовский классификатор имеет такую ​​структуру:

P(dupe|S) = P(dupe)P(s_a|dupe)(s_b|dupe)(s_c|dupe)P(s_d|dupe) / P(S)

Разрешение объекта с кластеризацией графа

После этапа классификации у нас есть подмножество записей из данной категории, которые считаются попарно дубликатами. Теперь они должны быть разделены на отдельные объекты . Это решает проблему транзитивности: если запись t1 - это дуплекс t2, а t2 - дуплекс t3, то t1 также должна быть дуплексом t3. Это означает, что t1, t2 и t3 представляют одну и ту же сущность .

Структура графы используются для этого шага. Внутри категории каждая запись, которая может быть дублированием, является узлом. Узлы, которые подозреваются в обманах друг друга, имеют ребра между ними. Кластеры затем обнаруживаются на графике и затем объединяются вместе на основе порогов, касающихся того, насколько сильно один кластер связан с другим. Вот три примера пар кластеров, которые могут или не могут быть объединены вместе на основе их связанности:

  c1        c2    

x-x-x-----y-y-y
|\|/|     |\|/|
x-x-x-----y-y-y  Meets similiarity threshold
|/|\|     |/|\|
x-x-x-----y-y-y    

x-x-x     y-y-y
|\|/|     |\|/|
x-x-x-----y-y-y  Does not meet similarity threshold
|/|\|     |/|\|
x-x-x     y-y-y    

    x     y
    |     |
    x-----y      Meets similarity threshold
    |     |
    x     y

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

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