Najnowocześniejsza deduplikacja

Jakie są najnowocześniejsze metody deduplikacji rekordów? Deduplikacja jest również czasami nazywana: łączenie rekordów, rozpoznawanie jednostek, rozpoznawanie tożsamości, scalanie / czyszczenie. Wiem na przykład o CBLOCK [1].

Byłbym wdzięczny, gdyby odpowiedzi zawierały również odniesienia do istniejącego oprogramowania wdrażającego metody. Wiem na przykład, że Mahout stosuje klastrowanie baldachimu . Jest też Duke, który używa Lucene.

Istnieje wiele komercyjnych systemów deduplikacji. Warto wiedzieć, jak działają i jak wydajni są.

Interesuje mnie zarówno deduplikacja w ramach jednego zestawu danych, jak i łączenie wielu zestawów danych pochodzących z różnych źródeł. Ważna jest również wydajność i zdolność do przetwarzania dużych ilości danych.

[1] CBLOCK: automatyczny mechanizm blokujący do zadań usuwania duplikatów na dużą skalę

Tamr (wcześniej Data Tamer) wykonuje deduplikację bazy danych na dużą skalę. W grę wchodzą naiwne Bayes i grupowanie wykresów.

Wierzę, że algorytmy są w dużej mierze zaimplementowane w SQL, co jest nieco dziwne, ale głównym autorem ich oficjalnego dokumentu jest Michael Stonebraker, który pomógł w stworzeniu PostgreSQL.

Sprawdź oficjalny dokument tutaj .

Edycja: Poniżej podsumowałem kroki, jakie podejmuje ich praca. Niektóre z moich słów są prawie takie same jak w ich pracy.

System deduplikacji Tamr składa się z dwóch głównych etapów postępowania z nowym źródłem danych: (1) Identyfikacja atrybutu i (2) Konsolidacja jednostki. Są one w przybliżeniu równoważne deduplikacji kolumn i deduplikacji wierszy.

1) Porównując nowe źródło danych z istniejącym, pierwszym krokiem jest Identyfikacja atrybutu.

Atrybuty (kolumny) nowego źródła są mapowane na atrybuty istniejącego źródła za pomocą czterech algorytmów:

• Porównaj nazwy atrybutów z rozmytym ciągiem znaków (podobieństwo cosinusu trygramu)
• Rozważ całą kolumnę jako dokument, tokenizuj, zmierz całkowitą podobieństwo / odwrotną częstotliwość dokumentu (TF-IDF) podobieństwo cosinus między tą a innymi kolumnami.
• Minimalna długość opisowa: porównaj dwie kolumny na podstawie rozmiarów ich przecięcia i połączenia z dokładnym dopasowaniem.
• W przypadku kolumn numerycznych wykonaj test t między nową kolumną a istniejącymi kolumnami numerycznymi, aby ustalić, czy pochodzą one z tego samego rozkładu.

2) Konsolidacja jednostki (deduplikacja wiersza)

Po przeprowadzeniu identyfikacji atrybutu chcemy zduplikować wiersze (rekordy).

Kategoryzacja z klastrowaniem

Rekordy są najpierw grupowane w kategorie na podstawie podobieństwa, a następnie reguły deduplikacji są uczone na poziomie kategorii. Podany przez nich przykład kategoryzacji dotyczy bazy danych ośrodków narciarskich, w których zachodnie ośrodki narciarskie powinny być inną kategorią niż wschodnie ośrodki narciarskie, ponieważ takie cechy, jak wysokość bazy są silnie oddzielone od tego, czy ośrodek jest wschodni czy zachodni. Kategoryzacja odbywa się za pomocą algorytmu grupowania, z k-średnimi podanymi jako przykład.

Deduplikacja z Naive Bayes

Po zidentyfikowaniu atrybutów i zgrupowaniu rekordów w kategorie uczymy się zasad deduplikacji dla każdej kategorii w oparciu o zestaw szkoleniowy duplikatów i duplikatów.

Istnieją dwa typy reguł deduplikacji:

1. Progi podobieństwa atrybutów w odniesieniu do funkcji odległości, która ma sens dla atrybutu. (W artykule nie wyjaśniono, w jaki sposób uczą się tych progów.)
2. Rozkłady prawdopodobieństwa dupe i non-dupes w każdym atrybucie. np. P("Title" values similar | duplicate) ~ 1i Pr("State" values are different | duplicate) ~ 0

Dla każdej pary rekordów obliczamy podobieństwo każdego z ich atrybutów do odpowiedniej metryki odległości. Jeśli jakikolwiek atrybut ma podobieństwo powyżej swojego progu, para rekordów jest przekazywana przez klasyfikator Naive Bayes, aby zostać sklasyfikowanym jako dupe lub non-dupe.

Moje założenie jest, że rekordy X1 = (a1,b1,c1,d1), X2 = (a2,b2,c2,d2)oni obliczyć wektor podobieństwa S = (s_a, s_b, s_c, s_d)gdzie s_ijest podobieństwo do tego atrybutu wrt do prawidłowego metryki odległość.

Zakładam, że ich klasyfikator Naive Bayes ma następującą strukturę:

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

Rozdzielczość encji z grupowaniem wykresów

Po etapie klasyfikacji mamy podzbiór rekordów z danej kategorii, które uważa się za duplikaty par. Teraz należy je rozdzielić na odrębne byty . Rozwiązuje to problem przechodniości: jeśli rekord t1 jest dupesem t2, a t2 jest dupesem t3, to t1 musi również być dupesem t3. To znaczy, że t1, t2 i t3 reprezentują ten sam byt .

W tym kroku zastosowano strukturę wykresu . W obrębie kategorii każdy rekord, który może być duplikatem, jest węzłem. Węzły podejrzane o wzajemne duplikaty mają między sobą krawędzie. Klastry są następnie wykrywane na wykresie, a następnie łączone ze sobą na podstawie progów dotyczących tego, jak silnie jeden klaster jest połączony z drugim. Oto trzy przykłady par klastrów, które mogą, ale nie muszą zostać scalone ze względu na ich połączenie:

  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

Po zakończeniu algorytmu każdy klaster powinien reprezentować odrębny byt w ramach kategorii . Aby ukończyć proces, atrybuty tego elementu muszą zostać określone na podstawie atrybutów zawartych w nim rekordów . Najpierw odrzucane są wartości zerowe, a następnie stosowane są metody obejmujące częstotliwość, średnią, medianę i najdłuższą.

W artykule opracowano także metody korzystania z ekspertów w dziedzinie, aby pomóc, gdy algorytmy nie są pewne, oraz sposoby korzystania z wielu ekspertów o różnych poziomach wiedzy.