Entity Resolution의 개념과 역사적 흐름을 literature review 같이 설명하는 논문이다. 분량은 많지 않지만, 생소한 개념과 단어들이 많이 나오고, 약간의 수식이 등장해서 완벽하게 이해되지 않은 부분이 있고, 개인적으로는 지금 보고 있는 스터디 교안의 1장을 먼저 공부하고 읽으니 더 이해가 잘 되는 느낌이었다.
1️⃣ Introduction
Entity Resolution(이하 ER)은 크고 노이즈가 많은 데이터에서 중복된 개체를 식별하고 제거하는 과정으로, 여러 소스의 데이터셋의 통합 활용을 위해 널리 사용되는 방법이다. ER은 컴퓨터 과학, 통계학, 기계학습, 사회 과학, 의학, 법학 등 다양한 분야에서 광범위하게 연구되고 적용되어 왔다.
ER의 다양한 측면 중 ‘결정론적 레코드 연계’는 규칙과 유사성 기반으로 접근되고, ‘확률론적 레코드 연계’는 기존의 방식과 현대에 제시된 Fellegi나 Bayesian 연계 방법들을 다룬다. 특히 이 부분은 최근 기계 학습과 컴퓨터 과학 커뮤니티의 기여가 두드러지는 영역이다.
2️⃣ Overview of Entity Resolution
Impactful entity rresolution applications
Record Linkage(=ER)를 처음으로 언급한 사람은 Dunn이며, 동일한 개인을 지칭하는 정보를 조립하는 과정으로 설명했다. 이는 다양한 분야에서 관심을 끌었는데, 우선 과학 분야에서는 미국의 십년 인구 조사(Decennial census)가 있다. 인구 조사를 하기 위해서는 개별 개체가 다르다는 것, 즉 다른 사람이라는 것을 파악해야 하며, 중복 제거가 필수적이다. 이와 유사하게, 엘살바도르에서는 내전이 일어났을 당시 3개의 데이터베이스가 기록됐는데, 여기서 중복된 사망자를 집계될 가능성이 있다. 시리아의 전쟁 역시 다수의 데이터베이스에서 정확한 집계를 위해서는 ER의 적용 가능성이 대두된다.
이 외에도, 노스 캐롤라이나의 유권자를 추정하기 위한 상황이나(이사, 결혼 등 여러가지 이유로 유권자 번호가 중복될 수 있으므로), 동명이인의 발명가와 저자의 모호성을 줄이기 위한 경우에도 ER는 중요한 요소로 작용한다.
Terminology and definitions
ER과 관련된 핵심 용어들을 정의하면 다음과 같다.
- Database: record들의 집합
- Record: 데이터베이스 내에서 하나의 개체에 대한 정보를 담고 있는 단위. 각 레코드는 속성(attribute, field, feature) 들을 포함함
- Entity: 데이터베이스 내 record들이 참조하는 실제 대상 (person, event, object, etc)
- Entity Resolution: 동일한 개체를 참조하는 기록들을 식별하는 문제. 두 기록이 동일한 개체를 참조하는 것을 Coreferent 또는 Link라고 하며, 그 반대는 Non-coreferent, Nonlink라고 함.
- ER는 클러스터링 문제(참조하는 개체에 따라 군집화하는 것) 혹은 동일한 개체를 참조하는 기록 쌍을 식별하는 방식으로도 설명될 수 있음
- 동의어: Record Linkage, Deduplicattion, Data Mathcing, Instance Matching, Data Linkage
The data cleaning pipeline
ER은 data cleaning의 한 과정으로도 볼 수 있다.
- attribute alignment: 두 데이터세트 간의 공통 속성을 식별하기 위한 과정
- blocking: 유사한 레코드를 블록으로 분류한 뒤, 유사한 블록만 비교하고, 그렇지 않은 것들은 자동으로 불일치로 결정
- entity resolution: coreferent 레코드가 식별됨
- canonicalization: 일치하는 엔티티를 병합하여 단일한 대표 레코드를 생성
Challenge of entity resolution
- 대규모 데이터셋: N개의 레코드가 있을 경우, N(N-1)/2 만큼의 비교가 필요하고, 이에 따라 대규모 데이터셋일 경우 평가가 어려워짐. 물론 대부분의 ER은 모든 쌍을 비교하진 않지만, 이는 속도는 빨라지지만, 정확성은 줄어들 수 있음
- 불확실성이 존재할 가능성: 위에서 언급한 것과 같이 blocking을 통해서 일부만 비교함으로써 오류와 불확실성이 발생할 수 있음
- 데이터베이스 자체의 오류를 설명하는 방법: 데이터 자체에 왜곡이나 오류가 있는 경우, 복잡한 생성모델(?)이 좋지만, 대규모 데이터셋에는 적용하지 못한다는 한계가 있음
Differences in entity resolution disciplines
ER은 광범위한 학제간 연구 분야이다. 이 논문에서는 정형적이고 구조화된 ER에 초점을 맞추지만, 설명 텍스트나 이미지 등과 같은 비정형 데이터의 경우 더욱 복잡해진다고 설명한다. 또한 이 연구는 불확실성을 정량화하는 접근 방식에 초점을 두는데, 이는 두 개체가 유사할 확률을 90%와 같이 확률적 수치를 파악하는 방법으로, 대규모의 데이터를 빨리 처리하는 방법에 초점을 맞춘 기존의 연구와 차이가 있다.
3️⃣ Deterministic Record Linkage
일반적으로 사용되는 ER 방법은 레코드 속성 비교와 관련된 결정론적 규칙(규칙 기반, 유사도 기반 이라고도 함)을 기반으로 한다. 이 예시로는 exact 매칭이 있는데, 모든 속성을 비교해서 공통 쌍을 찾아내는 방법이며, 엄격함의 정도는 매칭 로직을 유사성 정도로 낮춤으로써 조절할 수 있다(간단하게, 텍스트 매칭을 할 때 완전히 매칭되는 걸 찾는게 아니라 특정 단어가 포함된 것을 찾는다거나, 특정 단어로 시작하는 것 찾는 등의 규칙으로 이해할 수 있음). 그러나 이 방식은 확률 모델을 사용하지 않아 불확실성을 측정할 수 없다는 특징이 있다.
자연어로 기록된 데이터에는 노이즈가 있을 가능성이 높은데, record linkage는 이를 고려해야 한다. 가장 간단한 방법은 Levenshtein(두 문자열을 같게 만들기 위해 편집해야 하는 최소 횟수)이나 Jaro-Winkler 거리와 같은 문자열 거리 함수이다. 또한 Jaccard 유사도나 cosine 유사도와 같은 토큰 기반 유사도 측정 방법도 존재한다.
4️⃣ Probability Record Linkage
Dunn’s “Book of Life” and early references
1946년, Dunn은 record linkage를 처음 정의했으며 정부에서 동일한 개인의 정보 통합을 위한 목적으로 시작했다. Dunn은 record linkage를 logistical(물류?)적 관점에서 봤는데, 예를 들어, 출생증명서 번호가 널리 사용된다면, 중앙집중식 인덱스는 개별 기록들을 이 번호를 통해서 연결할 수 있다는 것이다. 그러나 실제로는 이 고유번호가 다른 데이터베이스들에서도 공통적으로 사용되지 않는 경우들이 많이 때문에, 동일한 개인을 참조하는 기록을 식별하기 위해 사용할 수 있는 최적의 매개체가 뭔지를 알아내는 알고리즘적 문제가 된다고 한다.
Newcombe는 인구통계학 연구를 위해 고유 식별자가 없는 데이터를 연결하는 방법으로 우선 Blocking을 통해서 이름을 문자열 코드화를 진행한다(Soundex coding schema). 이후 두 데이터 간의 코드를 매칭한 뒤, 실제로 일치할 가능성과 그렇지 않을 가능성을 비교하는 likelihood ratio를 계산해서 임계값을 넘는 경우만 연결한다. 연구 결과 약 98.3%의 정확도를 보였다고 한다.
A theory of record linkage
1969년 Fellegi-Sunter은 Newcombe의 접근 방식을 의사결정 이론적 틀에서 형식화하는데, 이 프레임워크는 record linkage에 대한 중요한 토계적 기반을 제공하였다.
프레임워크는 개별 기록을 독립적인 쌍으로 간주하며, 1종 오류(잘못 매치되는 비율)와 2종 오류(잘못 매칭되지 않는 비율)을 최소화하는 것을 목표로 한다. 비교는 연결(to link), 가능한 연결(to possibly link; 판단이 불확실하므로 추가적으로 확인이 필요한 상태), 연결되지 않음(to not link) 세 가지로 판단된다.
likelihood ratio는 다음과 같이 계산된다. 예를 들어, A와 B를 비교하는데 이름과 생년월일이 동일하지만 주소는 다르다는 결과(r; 감마)이 있는 경우, m(r)은 A와 B가 실제로 같은 사람일 때 이름, 생년월일은 갖고 주소는 다를 확률일고, u(r)은 실제로 다른 사람일 때 해당 결과가 나올 확률이다. 이때의 likelihood는 m(r)/u(r) 로 정의된다. 즉, 이 값이 클 경우 A와 B가 같은 사람일 가능성이 더 높고, 작을 경우 다른 사람일 가능성이 더 크다고 해석할 수 있다.
- m(y): 매칭이라는 가설 하에서 y가 관찰될 우도
- u(y): 비매칭이라는 가설 하에서 y가 관찰될 우도
✅ 우도(likelyhood): 특정 모델이나 가설이 주어졌을 때, 실제로 관찰된 데이터가 나타날 가능성
- 확률: 동전(p=0.5)을 던졌을 때 앞면이 7번 나올 확률은?
- 우도: 앞면이 7번 나왔을 때, 동전이 p=0.5일 가능성은?베이지안 정리를 활용한 매칭 확률
- 기본 베이즈 정리 공식: p(M|γ) = λm(γ)/p(γ)
- p(λ) = λm(γ) +(1 −λ) u(γ)를 베이즈 정리에 대입하면 p(M|γ) = λm(γ) / [λm(γ) + (1-λ)u(γ)] 가됨
이때의 매칭 가중치는 W(r) = log (m(r)) − log (u(r)) 로, 양수인 경우 A와 B는 같은 사람일 가능성을 높여주고, 음수인 경우는 다른 사람일 가능성을 높여준다. 0인 경우는 중립을 의미한다.
한편, m과 u 확률을 추정하는 방법에 대하여 Fellegi와 Sunter는 두 가지 비지도학습 방식을 제안하였다. 이때는 모두 각 비교 결과가 서로 독립적이라는 것을 가정한다. 우선 첫번째 방법은 비교 벡터를 활용하는 것으로, 각 속성의 비교가 일치하는 경우 어떤 특정값으로 일치하는 지를 고려하여, 일치할 가능성이 낮음에도 일치하는 경우에 가능성 수치를 더 높여준다. 예를 들어, 'John'이라는 이름은 흔하지만, 'Xander'와 같은 덜 흔한 이름이 일치하면 실제로 같은 개체일 확률이 높다는 것이다. 두 번째는 이진 비교 방법으로, 단순히 일치, 불일치를 나타내는 것만 고려하는 방식이다. 이후 Wrinkler나 Jaro는 EM 알고리즘과 같은 통계적 기법을 도입하여 이 추정 과정의 정확성과 실용성을 높였다고 한다.
이후 확률 모델과 관련하여 Fellegi-Sunter 모델에 대한 보다 자세한 내용과 한계를 극복하기 위해 제시된 발전된 현대 모델(Bayesian Fellehi-Sunter 등)과 관련된 설명을 진행하는데, 이 부분에 대해서는 완벽하게 이해하지 못했으므로 설명은 생략하겠다. 논문의 6~7 페이지 부분을 참고하면 된다.
Semi, Fully supervised classification
레코드 쌍을 분류하는 방법으로 앞서 비지도학습 방법이 언급되었는데, 이 부분에서는 반지도학습, 지도학습 방법에 대해서 설명한다. 우선 반지도학습 방식의 경우, 소량의 레이블 데이터(정답이 있는 데이터)를 활용하는 방법으로, 다음 세 가지 유형이 언급된다. (1) 생성적 반지도 접근 방식은 레이블이 지정된 데이터와 지정되지 않은 데이터의 결합 가능도를(joint likelihood)를 목표로 한다 (2) 표현 변경 반지도 접근 방식은 비지도 프레임워크로 모든 레코드 쌍의 매칭 가중치를 얻은 뒤, 레이블이 있는 예제를 사용하여 매칭 가중치에 혼합하여 사용하는 방식이다 (3) 자체 학습 알고리즘은 랜덤 포레스트나 다층 퍼셉트론 부스팅을 결합하여 소량의 레이블이 지정된 쌍으로 좋은 성능을 얻는 방법이다.
완전 지도 방식의 접근은 레이블링된 대량의 데이터가 필요한데(DL 학습에 필요한 만큼은 아님), 이는 crowdsourcing이나 수동 작업, 비지도 방법을 통한 생성 등의 방법을 활용한다. 이를 활용한 실제 적용 사례로는 미국 특허청(USPTO) 특허의 발명가 중복 제거 사례 연구가 있다. 렌덤 포레스트를 활용해서 각 블록 내의 레코드 쌍에 대한 비교 벡터를 계산하고, 학습된 분류기(이전 발명가 이력서와 생명 과학 분야 학자들에 대한 이전 연구를 통해 학습)를 통해 일치할 예측 확률을 계산한다. 그리고 이 예측 확률을 각 레코드 쌍의 비유사도 추정치로 변환한 뒤 계층적 클러스터링을 사용하여 클러스터를 결정한다. 결과적으로 모든 클러스터링 결과를 결합하여 중복이 제거된 최종 레코드 세트를 얻을 수 있다.
5️⃣ Entity Resolution as a Clustering Problem
쌍으로 두 레코드를 비교하는 방식은 Bayesian Fellegi-Sunter 방식 이외에는 기록 쌍들을 서로 독립적인 것으로 취급하여 연결구조에 대한 다른 제약 조건들을 고려하지 않으며, 두 개 이상의 데이터베이스를 연결하는 데는 한계가 있다. 따라서 ER을 클러스터링 관점에서 접근하는 시도가 이뤄졌는데, 이는 각 레코드를 독립적인 관계로 보는 것이 아니라, 여러 레코드들이 하나의 개체를 대표하는 그룹, 즉 클러스터로 묶이는 방식으로 문제를 해결하려는 것이다.
클러스터링을 시도한 대부분의 연구는 probabilistic record linkage의 두번째 단계(post-preprocessing step)로 활용하는데, 이를 통해 비전이성(intransitivities)를 해결하고 일관된 출력을 보장할 수 있게 된다. 이때 말하는 비전이성은 예를 들어, A=B이고 B=C라면, A=C라고 판단이 가능한데, 쌍별 매칭에서는 논리적 맥락을 참고하지 않으므로 A와 C가 다르다고 판단하는 것을 의미한다. 클러스터링 활용 예시로는 (1) 기록 간의 연결 관계를 그래프로 표현한 뒤, 서로 연결된 기록들을 하나의 클러스터로 묶기(계산 효율성, 레코드 수가 많을 때 미리 그룹을 나누는 블로킹 단계에서도 활용 가능) (2) 클러스터 내부의 연결된 수는 최대로 하고, 밖의 연결되지 않은 수는 최소로 하는 상관 클러스터링(계산 복잡) (3) 계층적으로 하나씩 합쳐가면서 클러스터 트리를 만드는 계층적 응집 클러스터 방식이 있다.
모델 기반의 접근은(Graphical entity resolution) 불확실성을 정량화할 수 있는 방법으로, LDA나 기록과 잠재 개체(latent individuals)와 연결하는 기법, fully hierarchical Bayesian 방식 등이 제시되었다. 특히 잠재 개체와 연결하는 모델은 기존과 같이 레코드1과 레코드2가 동일한지를 비교하는 것이 아니라, 해당 레코드가 어떤 잠재된 개체에 대한 정보인지를 찾아서 연결하는 방식이다. 또한 오타가 있어도 ‘히트 앤 미스’ 라는 통계 모델을 사용해서 데이터의 불완전함이나 왜곡을 통계적으로 설명할 수 있다는 장점이 있다.
Microclustering property는 ER에서 클러스터의 크기가 전체 레코드 수에 비해 비선형적(sublinear)으로 증가한다는 것을 공식화한 것이다. 즉, 전체 기록 수가 증가하더라도 클러스터의 수는 그것 보다 느린 속도로 증가한다. 반면, 전통적인 확률적 생성 모델들은 일반적으로 전체 레코드 수에 대한 멱법칙(power law, 선형적)을 가정하므로, ER 처럼 클러스터의 크기가 작고, 비선형적으로 클러스터의 수가 증가하는 케이스에는 모델이 데이터를 제대로 설명하지 못한다.
6️⃣ Discussion
ER은 두 엔티티의 일치 가능성을 보여주지만, 실제로 어떤 레토드가 기본(underlying) 엔티티인지 알 수 없다. ER 이후의 작업인 데이터 융합과 병합, 정규화(Data fusion, merging, and canonicalization)는 유사성을 기반으로 하나의 레코드로 만드는 작업으로, 규칙 기반이나 학습 모델(머신러닝 기반으로 이해함)을 사용할 수 있다.
방법론적 발전이 있음에도 ER의 평가는 여전히 어렵다. 벤치마크 데이터셋을 활용할 때에는 레코드 수, 데이터의 노이즈 수준, 전반적인 데이터 품질, 데이터 내 식별자의 신뢰성 등을 고려해야 하며, 이를 고려해서 활용한다고 해도 특정 도메인 분야를 전부 다루지 못할 가능성이 있으며, 현실 세계의 데이터셋 특성을 반영하지 못하는 경우가 존재한다. 또한 전문가가 레이블링한 데이터를 통해 ER을 평가할 수도 있으며, 해당 분야에 대한 연구는 진행 중이다.
ER은 여러 데이터를 하나로 연결, 통합하는 것을 목표로 한다는 점에서 윤리적인 이슈가 발생할 수 있다. 즉, 익명화된 데이터도 ER을 통해 공개될 수 있다는 것이다. 이런 문제를 해결하기 위해 제시된 방법 중 SDC(Statistical Disclosure Control)는 공개된 데이터의 유용성과 개인 정보 보호 간의 균형을 맞추는 것을 목표로 하며, Top-coding, data swapping, data perturbation(교란), synthetic data generation 등의 기법을 활용한다. 또한 서로 다른 조직에서 개인정보를 포함하는 데이터베이스를 공유할 수 없을 때 PPRL(Privacy-Preserving Record Linkage)가 중요하며, 데이터가 공유되고 공개되는 것의 위험을 신중하게 평가해야 한다고 설명한다.
한편, 앞서 언급했듯 비정형 데이터나 멀티 모달 ER은 더 어려운 작업이며, 아직까지 많이 연구되지 않은 분야이다. 이는 범죄 현장에서 지문과 같은 증거를 기반으로 유사성을 판단하는 작업에 활용될 수 있다. 또한 개인 수준의 프라이버시를 유지하는 알고리즘에 대한 필요성과 함께 차동 프라이버시(differential privacy)의 측정치에 대해서 실제로 어떻게 사용될 수 있는지 이해하기 위한 사례 연구가 필요하다고 설명한다.
