Entity Resolution 개념 (2)

How do I Entity Resolution?

1. Source normalization: 데이터를 깔끔하게 정리, 여러 소스에서 하나의 스키마로 맞춤. 이 스키마에서 사용되는 피처(column)들은 나중에 매치되는 짝들을 평가하는데 사용됨
2. Featurization and blocking key generation: blocking key를 위한 피처 생성. blocking key는 매치되는 레코드들 사이에서 공유되는 타겟화된 토큰임. 검색 공간을 N^2에서 더 계산이 수월하도록 제한하기 위함
3. Generate candidate pairs: blocking join key를 사용해서 후보 pair 생성. 기본적으로 blocking key에 대한 self-join임. 그래프 데이터 구조에서 실행됨 (레코드: 노드, 매칭정보: edge)
4. Matching socring and iteration: 후보 pair가 실제로 매치되었는지 match scoring function을 통해 결정. rule-based가 될 수 있는데, 일반적으로 non-linear한 decision boundary에서 적응하고 최적화할 수 있는 학습 알고리즘으로 더 잘 구현됨.
5. Generate entites: 그래프에서 매치되지 않은 엣지들을 제거하고, resolved-entities와 각각의 소스 레코드들에 연관된 맵핑을 생성함

---

2. Featurization and blocking key generation

• Featurization: 기존 column을 다른 레코드들이 같은 것을 참조하는지 알려주는 피처로 변환하는 것
• Blocking: 후보 매칭 pair를 효율적으로 만들기 위해 join key로 사용할 타겟 피처의 하위집합을 선택하는 것

 

• featurization이 잘된 경우는 효율적인 blocking이 가능하고, match accuracy가 좋음
• blocking이 잘된 경우 Entity Resolution의 효율을 드라마틱하게 향상시킬 수 있음. 또 많은 입력 소스와 대규모 데이터 세트로 확장할 수 있음
  • 후보 pair의 수는 N^2임 (N: 레코드 수)
  • 근데 모든 pair가 의미있는게 아니기 때문에 줄일 필요가 있다!
  • 그래서 blocking key를 사용함
    • blocking key가 제품의 정확한 이름일 경우, normalize된 이름이 제품 이름과 정확히 같은 것만 제품 후보 pair에 포함됨. 하지만 'learning quickbooks 2007'과 축약형으로 나타낸 'learning qb 2007'을 매칭시키지는 못함.
    • blocking key 선택: 효율과 false negative rate(실제 참, 판단 거짓)의 tradeoff

 

featurization 구현방법

• 소스데이터의 유형과, 원하는 다운스트림 비교 알고리즘에 따라 달라짐
• normalization 과정을 거쳐서 나온 데이터 세트에서 4 개의 column을 featurization에서 사용함
  • name, description, manufacturer, price
  • 이 중 name, description, manufacturer은 텍스트 기반 필드로 식별 정보가 존재함

 

• 텍스트 데이터를 featurize하는 방법의 유형
  • 1) Tokenization: 문장을 단어로 쪼개는 것
  • 2) Token standardization: stemming(파생된 단어를 root로 줄여나가는 과정) or lemmatization(파생된 단어를 하나로 묶어 하나의 항목으로 분석할 수 있도록 하는 과정)
  • 3) Embedding: TF-IDF, word embedding, sentence embedding

 

• TF-IDF 모델
  • 1) text를 토큰화하고, 2) stop-word를 제거하고, 3) TF-IDF 벡터화 진행
  • tensorflow의 Universal Sentence Encoder를 사용해 name, description string을 512차원의 벡터로 표현
  • TF-IDF 벡터화와 Universal Sentence Encoder 사용을 통해, 후보 pair의 match를 평가하고 blocking key를 선택하는 것을 돕는 많은 feature를 갖게 될 것임

• blocking key는 효율과 FNR 사이의 균형을 잘 맞춰야함
  • 여기서 full name을 그대로 선택해서 matching을 하면 FNR이 매우 높을 것임
  • 그래서 name에서 중요한 부분만 골라서 사용하려고 함
  • 이 과정이 TF-IDF가 하고자하는것임
  • ex) learning quickbooks 2007
    • 중요도: quickbooks > 2007 > learning
    • TF-IDF token weights: {"quickbooks":0.7, "2007":0.51, learning:"0.5"}

 

• Sentence encoding vector weights
  • 잠재 벡터 공간에서 어떤 차원이 문장의 의미에 가장 핵심적인지 말해줌
  • 그걸 blocking key로 선택해서 사용 가능
  • 하지만, sentence encoding의 경우 가장 높은 가중치를 가진 차원이 단어 토큰에 직접 매핑되지 않기 때문에 해석가능성이 낮음