An overview of end-to-end entity resolution for big data

An Overview of end-to-end entity resolution for big data를 번역하였습니다.

An overview of end-to-end entity resolution for big data, Christophides et al, ACM Computing Surveys, Desc. 2020, Article No. 127

새로운 분야에 대한 기초를 익히고자 할 때 ACM Computing Surveys를 요긴하게 사용하곤 합니다. 위 Survey Paper는 최근 핫한 주제인 Entity Resolution 분야에 대해 다루고 있습니다. Entity Resolution은 최신 Data Workflow를 다룰 때 굉장히 중요한 부분으로, 제가 다루는 하나의 프로젝트에서 씨름하고 있는 분야이기도 합니다.

Entity Resolution은 동일한 Real-world Entity (실 세계의 개념)를 가리키는 서로 다른 표현들을 식별하는 기법입니다. 데이터 소스에서 동일한 Entity 식별자를 사용하지 않아 발생합니다.

ER이 동일한 데이터소스에서 수집된 Record들에 적용되면, Deduplication을 위해 사용될 수 있습니다. Record Linking이라 불리는 기술로 동일한 Record들을 연결하여 하나로 표현하게 되면 Record들의 중복이 줄어들 수 있는 것이죠. 다만, 이 기술이 그리 단순하지만은 않습니다. 각 Entity를 다른 모든 Entity와 전부 비교해봐야 하는데 Input Size (N)의 제곱의 시간 복잡도가 발생합니다. (역자 추가: N 제곱이 단순해보이지만 빅 데이터라고 할 수도 없는 기가 스케일에서만 해도 N 제곱의 복잡도는 기가 Hz CPU 1개에서 10^9 초, 즉 1,902년이 걸리는 엄청난 작업이 됩니다..)

두 가지 개념을 먼저 정리하도록 하겠습니다.

• Entity Description: 각 Entity에 대한 데이터 소스 내의 Record 또는 Document를 의미합니다.
• Entity Collection: 이러한 Entity Description의 집합을 의미합니다.

ER Pipeline의 일반적인 흐름은 다음과 같습니다.

• Blocking은 Entity Description들을 Input으로 Blocking Key 별로 한 개 이상의 블록들에 할당하는 작업입니다. 이 작업을 통해 추 후 비교 횟수를 줄이는 것이 목적입니다. 주요 아이디어는 어떤 두 개의 Entity Description이 동일한 Real-world Entity를 가리킬 가능성이 있다면, 두 Entity를 최소 하나의 blocking key를 일치시켜 동일한 Block에 할당하는 것입니다. 따라서 실제 비교는 해당 블록 내의 Entity 간에만 수행하게 됩니다. (역자 추가: N 제곱이 블록 내 Entity 개수를 B라고 할 때 BN의 복잡도로 줄었네요.)

• Block Processing은 비교 횟수를 좀 더 줄이기 위해 분투하는 작업입니다. 여러 블록들에서 발생하는 중복되는 비교 작업을 줄이는 것으로 블록 내에서 불필요한 비교가 발생하는 것을 줄이는 작업입니다.

• Matching은 Block 내의 Entity Description을 실제 비교하는 작업입니다. 두 개의 Entity Description이 동일한 Real-world Entity를 가리키고 있는지 아닌지 식별하는 작업입니다. (Iterative ER 프로세스에서는 Matching작업과 Blocking작업이 블록들에 영향을 주는 작업으로 서로 동일한 리소스를 참조할 수도 있습니다; 역자추가: Pipelining에 영향을 주겠죠)

• Clustring는 식별된 Entity Description들을 그룹화합니다. 다시 말해, 하나의 그룹 내에는 동일한 Real-world Entity를 참조하는 Entity Description만 존재하게 됩니다. Clustering 단계를 통해 간접적인 Matching 관계들이 도출될 수 있습니다.

ER Pipeline의 결과로 발생한 Cluster들은 Input으로 들어온 Entity Collection을 Real-world Entity 집합으로 분리합니다.

ER Pipeline에 사용되는 여러 ER 기술들이 제안되었습니다. 이러한 ER 기술은 크게 세 가지 기준으로 분류될 수 있습니다.

• Schema-awareness - 데이터에 대한 스키마가 주어졌나요?
• The nature of the matching process - Entity Description 내의 단순 속성 비교로 Matching Process가 동작하나요? 아니면 보다 높은 신뢰도를 위해 복잡한 Matching Process를 수행하나요?
• The processing mode - 전통적인 배치 작업으로 수행되나요? 아니면 점진적으로 수행하나요?

각 Major Pipeline 단계마다 어떤 기술들이 포함되는지 각 Pipeline 단계별로 자세히 알아보도록 하겠습니다.

 

Blocking

Entity Resolution에서 Relational Data에 대한 Blocking Survey Paper가 있습니다. 따라서 본 Survey의 저자는 Schema-less Data에 대한 Blocking 기법을 조사하였습니다.

고전적인 접근 방식은 속성 (Attribute)와 관계 (Relation)를 살펴보는 것입니다. 예를들어 Token Blocking의 경우, 하나의 블록마다 고유한 Token을 만듭니다. Entity내의 Attribute의 종류와 무관하게 속성 값에 Token이 존재하면 해당 Block으로 포함시킵니다. 따라서 하나의 Entity가 여러 Block에 존재할 수 있게 되고 두 개의 Entity 간에 공유하는 Block이 많아질 수록 동일한 Entity를 참조할 확률이 높아지는데 이를 Redundancy Positive blocking 기법이라고 합니다. 반대의 경우인 Redundancy Neutral 기법의 예로는 Canopy Clustering가 있습니다. 이 방식 역시 Token 기반의 Block을 사용하지만 하나의 Entity는 단순 String Similarity Score (유사도)에 따라 Block에 배정하는 방식입니다. 이  때, 두 가지 Threshold를 사용하게 되고 Token의 String Similarity가 Tin 보다 높으면 해당 그룹에 배치하고 Tex (>Tin)보다 높으면 더 이상 다른 그룹에는 배치하지 않는 기법입니다. 따라서 Tex보다 높은 그룹에 할당된 Entity는 다른 그룹에 할당될 수 없어 두 Entity 간 공유하는 블록의 수가 동일 Entity를 참조할 확률과는 무관한 기법이 됩니다.

Block Processing

Blocking과 함께 Block Processing에도 다양한 방식들이 존재합니다. Block Cleaning 기법은 과도하게 큰 block을 삭제할 수 있습니다. (이런 Block은 종종 식별자를 Token으로 인식하여 발생하는 블록인데, 이 경우 대부분 Matching에 불필요한 Computing Resource만 잡아먹는 블록이 됩니다.). 또한 Block Clearning 기법을 통해 특정 Entity Description이 존재하는 Block들을 정리할 수도 있습니다. 예를 들어, 중복도 r이 가장 높은 Description을 제거하면 Block Size가 줄어듭니다. 좀 더 복잡하게는, 블록들을 쪼개고 병합하는 작업을 수행합니다. Dynamic Block Processing 기법은 Block Processing을 Blocking하는 중에 주기적으로 수행하도록 하여 효율성을 증가 시킵니다.

 

Comparison Cleaning 기법은 Redundancy Positive Blocking 기법들을 대상으로 이루어집니다. Entity Description들을 Node로, 같은 Block에 배치된 Node에 대해 Edge를 생성하여 그래프를 만들면 각 Edge의 Weight는 곧 두 Entity Description이 동일할 확률을 의미하게 됩니다. 그래프가 구축되면, Edge-pruning을 사용하여 Weight가 낮은 Edge들을 삭제합니다. 이 때, Weight를 정하는 방식과 Edge를 Pruning하는 방식에도 여러 가지 전략이 존재합니다. 예를 들어 Weighted Edge Pruning 방식은 평균 Edge Weight 이하의 모든 Edge를 제거하는 방식을 사용합니다. Pruning 후 새로운 Block들이 만들어지게 되는데, Learning-based Pruning 기법은 Pruning할 Edge를 분류하는 모델을 학습하는 방식을 사용합니다.

 

Matching

Matching 함수 M은 Entity Description Pair를 받아 Sim 함수를 호출하여 두 Entity 간의 유사도를 측정합니다. 만약 유사도가 특정 Threshold가 넘으면 Match이고, 아니면 No Match를 Return합니다. 좀 더 나아가서, Match 함수는 스코어 값이 애매한 유사도를 가지면 uncertain상태를 반환할 수도 있습니다. Similarity 함수는 Jaccard 유사도 처럼 Atomic한 함수를 사용하거나 Attribute 별 Similrarity 함수 결과 값을 선형적으로 연결하여 측정하는 Composite 함수를 사용합니다. 다음과 같은 조건을 만족하면 유사도 함수로 사용할 수 있습니다. 

 

Collective 기반의 Matching 프로세스들은 기존에 만들어진 Match 결과들을 토대로 새로운 Match를 찾아내는 반복적인 프로세스를 사용합니다. Merging-based Collective 기술들은 Match 페어를 병합하여 새로운 Entity Description을 생성하고 기존의 Description들을 삭제합니다. Relationship-based Collective 기술들은 기존 Entity graph의 관계를 사용하여 추가적인 Similarity 측정 단서를 제공합니다. 예를 들어, Entity Graph를 생성한 후, 두 개의 Node가 같은 Node에 연결되어 있을 때 Match일 확률이 더 높다는 가정하에, 반복적으로 Node들을 Clustering한 후, 두 개의 가장 유사한 Cluster들을 병합하는 방식을 계속해서 반복하여 Match를 수행할 수 있습니다.

 

Supervised, Semi-supervised, 그리고 Unsupervised Matching 등 다양한 Matching기술이 개발되어 왔습니다.

Matching Process의 결과는 하나의 Similarity Graph입니다. Similarity Graph에서 Node는 Entity Description을 의미하며 Weighted Edge는 연결 된 두 Noode 간의 Similarity를 의미합니다.

Clustering

Clustering은 Matching 결과로부터 Weight가 높지 않은 Edge를 제거하면서 Indirect Match를 찾아내어 추가적인 Edge를 추론하는 데 목적이 있습니다. 가장 단순한 방법은 단순히 연결된 Component들을 찾아내는 방식이지만 대개 Advanced Clustering 기법들이 사용됩니다. 예를 들어, Markov Clustering은 클러스터 내 Edge들은 강화하고 클러스터 간 Edge들은 약화시키기 위한 Random Walk기법을 사용합니다.

Making it incremental

Survey 문서의 Section 8에서는 Incremental 방식들에 대해 다루고 있습니다. 그러나 필자의 개인적인 분석으로는 다소 빈약해보이며 대부분 Query에 응답하기 위해 정보를 취합하는 방식을 위해 Entity Resolution을 하는 Online 방식을 향하고 있습니다. 예외적으로 Incremental Correlation Clustering을 다루고 있는데 이는 Description이 새롭게 추가, 변경, 삭제되었을 때 Clustering 결과를 Online으로 변경하는 기법입니다. 본 섹션에서 다루어지는 모든 기법들은 Schema를 필요로 합니다.

 

Open Source ER Systems

ER 시스템에 대한 오픈소스 분석은 다음과 같습니다.