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ę
źródło
Odpowiedzi:
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:
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:
P("Title" values similar | duplicate) ~ 1
iPr("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ństwaS = (s_a, s_b, s_c, s_d)
gdzies_i
jest 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:
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.
źródło