Головна › Архітектура корпоративної аналітики

Резолюція сутностей і графи знань

Блокування як єдиний спосіб не померти на O(n²), ймовірнісне зіставлення проти детермінованих правил, зіставлення схем як передумова, чесні метрики якості та подання розв'язаного домену як графа.

Востаннє переглянуто: 2026-09-04 · In English

У цьому напрямі

Один клієнт живе в CRM, у білінгу, у скарзі до кол-центру і в санкційному списку — під чотирма різними написаннями імені. Поки система цього не знає, будь-яка агрегація по «клієнту» — це агрегація по рядках таблиці, а не по людині. Резолюція сутностей — це конвеєр із чотирьох стадій: звести схеми, згенерувати кандидатні пари, вирішити, чи це одна сутність, склеїти пари в кластери. Кожна стадія має власну метрику і власний спосіб тихо провалитися. Цей модуль проходить усі чотири та закінчується там, де розв'язаний домен стає графом — вузли-сутності, ребра-відносини, збережена оборотність злиття.

Блокування: чому наївне порівняння O(n²) ніколи не доїжджає до продакшену

E4.1

Арифметика, яка закриває дискусію. Для 12 млн записів кількість неупорядкованих пар — 12e6² / 2 = 7,2 × 10¹³. Навіть за фантастичної швидкості 1 млн порівнянь на секунду це 833 доби безперервної роботи. Масштабування кластера тут не рятує: подвоєння записів множить роботу на чотири. Тому реальний пайплайн ніколи не порівнює всі пари — він спершу генерує кандидатів.

Блокування — це функція, що присвоює запису ключ; порівнюються лише записи в межах одного ключа. Робочі схеми в продакшені:

• Стандартне блокування: ключ як конкатенація фонетичного коду прізвища та року народження, або перших 4 символів індексу та перших 3 літер імені.
• Sorted neighbourhood: записи сортуються за складеним ключем, порівнюється ковзне вікно розміром w. Дешево, але чутливо до помилки в першому символі ключа — такий запис опиняється на іншому кінці сортування.
• MinHash + LSH: нечітке блокування за символьними n-грамами. Параметри band/rows задають фактичний поріг схожості Жаккара, за яким пари гарантовано потрапляють у спільний бакет.
• Багатопрохідність: 3–5 незалежних схем, результати об'єднуються (union). Кожен прохід ловить свій тип помилки; перетин звів би повноту до найслабшого проходу.

Дві метрики, які треба міряти окремо від матчера. Pair completeness (повнота пар) — частка істинних збігів, що взагалі потрапили в кандидати. Це стеля recall усього пайплайну: пару, яку блокування не породило, жоден матчер уже не відновить. Reduction ratio (коефіцієнт скорочення) — частка відкинутих пар. Схема з RR 0.9999 і PC 0.91 гірша за схему з RR 0.9990 і PC 0.985, попри вдесятеро більший обсяг обчислень: 9% втрачених збігів не купуються назад ніякими грошима на CPU.

Перекіс блоків убиває джоб раніше за обсяг. Розподіл розмірів блоків завжди важкохвостий: порожній індекс, значення-заглушка «N/A», найпоширеніше прізвище. Блок на 2 млн записів — це 2 × 10¹² пар в одному завданні Spark, тобто одна задача, що не завершиться ніколи, поки 511 інших давно готові. Стеля розміру блоку обов'язкова — але переповнені ключі перенаправляють на точніший прохід із додатковим полем, а не викидають: викинути блок означає тихо втратити recall.

Блокування — окрема стадія з окремим звітом. Її метрики міряють на власному наборі розмічених пар, не змішуючи з оцінкою матчера: інакше на питання «чому впав recall» неможливо відповісти — чи то нова схема ключів перестала породжувати пари, чи то зсунувся поріг оцінки збігу. Кожен прохід має власну виміряну PC; прохід, що додає обчислення і не додає жодної унікальної пари, прибирають зі схеми.

# Multi-pass blocking: candidate generation for 41M party records.
# Naive all-pairs = 41e6**2 / 2 = 8.4e14 comparisons -> never finishes, at any cluster size.
from pyspark.sql import functions as F

MAX_BLOCK = 1000  # hard ceiling: block cost is quadratic, so one fat block IS the job

def pass_keys(df, pass_name, key_expr):
    return (df.select(F.col("record_id"), key_expr.alias("bkey"))
              .where(F.col("bkey").isNotNull() & (F.length("bkey") > 3))
              .withColumn("pass", F.lit(pass_name)))

# Three independent passes, each blind to a different error mode.
blocks = (
    pass_keys(parties, "p1", F.concat_ws("|", F.soundex("last_name"), F.col("birth_year")))
    .unionByName(pass_keys(parties, "p2", F.concat_ws("|", F.substring("postcode", 1, 4),
                                                            F.substring("first_name", 1, 3))))
    .unionByName(pass_keys(parties, "p3", F.col("tax_id_normalised")))
)

# Kill the skew BEFORE the self-join. Route oversized keys to a finer pass; never drop them,
# because a dropped block is recall you lose without any log line saying so.
sizes     = blocks.groupBy("pass", "bkey").agg(F.count("*").alias("n"))
oversized = sizes.where(F.col("n") > MAX_BLOCK)      # -> refine_queue, reviewed every run
safe      = blocks.join(sizes.where(F.col("n") <= MAX_BLOCK), ["pass", "bkey"], "left_semi")

candidates = (safe.alias("a").join(safe.alias("b"), ["pass", "bkey"])
                  .where(F.col("a.record_id") < F.col("b.record_id"))  # each unordered pair once
                  .select("a.record_id", "b.record_id")
                  .distinct())                                          # union across the 3 passes

# Measure the blocking stage on its own, against a labelled pair set:
#   pair_completeness = |true_matches in candidates| / |true_matches|   <- recall ceiling
#   reduction_ratio   = 1 - |candidates| / (n*(n-1)/2)

Рішення про збіг: зіставлення схем, детерміновані правила та модель Фелегі–Сунтера

E4.2

Спершу схеми, лише потім записи. Порівнювати значення можна тільки після того, як відомо, які поля відповідають одне одному і в яких одиницях вони виражені. Schema matching дає гіпотези відповідності стовпців (dob ↔ birth_dt) — за назвами, типами, статистикою значень, а сьогодні й мовними моделями. Schema mapping — це вже виконуваний перетворювач: формати дат, одиниці, розщеплення full_name на два поля, кардинальність «один запис адреси проти трьох». Matching без mapping не переносить нічого; саме на цьому стику виникає найдорожчий клас дефектів резолюції.

Детермінований кістяк. Якщо в записі є верифікований ідентифікатор — податковий номер із контрольною сумою, LEI, номер поліса — правило виконують першим і фіксують результат. Це швидко, повністю пояснюване і не потребує розмітки. Ймовірнісна модель працює на решті — на записах, де ідентифікатора немає або він не збігається.

Фелегі–Сунтер: одна вага на поле. Для кожної кандидатної пари будується вектор порівнянь (згода/незгода/невідомо по кожному полю). Для поля оцінюють дві ймовірності: m = P(згода | збіг) та u = P(згода | не-збіг). Вага згоди — log₂(m/u), вага незгоди — log₂((1−m)/(1−u)); ваги сумуються.

• Вагу задає відношення, а не сам m. Стать із m = 0.92 і u = 0.50 дає log₂(1.84) ≈ 0.88 біта — майже нічого. Дата народження з m = 0.88 і u = 0.0004 дає ≈ 11 біт. Поле з двома значеннями не може розрізняти.
• m і u оцінюються без розмітки — EM на векторах порівнянь у моделі двох латентних класів. u перевіряється напряму: випадкова пара майже напевно не-збіг.
• Два пороги, не один. Вище верхнього — MATCH, нижче нижнього — NON_MATCH, між ними — зона, де доказів бракує в обидва боки. Її віддають людині і бюджетують за пропускною здатністю команди, а не вгадують одну точку відсічення.
• Пороги задає ціна помилки. Для санкційного скринінгу дорожчий пропуск, для дедуплікації розсилки — хибне злиття двох клієнтів. Один поріг на обох споживачів — це неявне рішення за обох.

Від пар до кластерів. Матчер видає ребра, а споживачеві потрібні сутності. Наївне транзитивне замикання (A~B, B~C ⇒ A~C) не має поняття ціни хибного ребра і зливає ланцюжки в гігантські псевдо-сутності. Кластеризація має враховувати і не-ребра — correlation clustering зі штрафом на зв'язки, що тримаються на одному спільному атрибуті.

# Fellegi-Sunter scoring: one log-likelihood weight per field, summed over the vector.
import math

# m = P(agree | match), u = P(agree | non-match). Both estimated by EM on unlabelled
# comparison vectors; u is sanity-checked against random pairs (almost surely non-matches).
FIELDS = {
    "birth_date": (0.880, 0.00040),   # agree -> +11.1 bits   : the workhorse
    "last_name":  (0.940, 0.00310),   # agree ->  +8.2 bits
    "first_name": (0.910, 0.00900),   # agree ->  +6.7 bits
    "postcode":   (0.790, 0.01200),   # agree ->  +6.0 bits
    "gender":     (0.920, 0.50000),   # agree ->  +0.9 bits   : nearly worthless, keep it honest
}
UPPER, LOWER = 8.0, -2.0   # MATCH / clerical-review band / NON_MATCH

def weight(field, state):
    m, u = FIELDS[field]
    if state == "agree":
        return math.log2(m / u)
    if state == "disagree":
        return math.log2((1.0 - m) / (1.0 - u))
    return 0.0                      # missing on either side contributes no evidence

def decide(comparison_vector):
    """comparison_vector: {'last_name': 'agree', 'birth_date': 'disagree', ...}"""
    w = sum(weight(f, comparison_vector.get(f, "missing")) for f in FIELDS)
    if w >= UPPER:
        return "MATCH", w
    if w <= LOWER:
        return "NON_MATCH", w
    return "REVIEW", w              # size this band against reviewer throughput, then set UPPER

# Deterministic core runs FIRST and wins outright - no probability needed for a checksummed id.
def resolve(pair):
    if pair["tax_id_a"] and pair["tax_id_a"] == pair["tax_id_b"]:
        return "MATCH", float("inf"), "rule:tax_id"
    label, w = decide(pair["cmp"])
    return label, w, "model:fs_v3"

Оцінка якості резолюції та розв'язаний домен як граф

E4.3

Парна метрика систематично бреше. Найпоширеніший спосіб оцінити ER — precision/recall/F1 на рівні пар. Проблема в тому, що кластер із k записів дає k(k−1)/2 пар: метрика зважена квадратом розміру кластера. Кілька гігантських хибних кластерів приносять мільйони «правильних» пар і маскують саме той збій, що найбільше болить користувачеві.

• B-cubed рахує precision і recall для кожного запису і усереднює по записах, а не по парах. Один запис — один голос, незалежно від розміру кластера. Розрив між парною F1 і B-cubed F1 — це не шум, а діагноз: він майже завжди вказує на кілька роздутих кластерів.
• Ground truth не будується випадковою вибіркою пар. Частка істинних збігів серед усіх пар — порядку 10⁻⁶; у вибірці з 10 000 випадкових пар не буде жодного позитиву. Розмітку роблять стратифіковано за оцінкою збігу, плюс окремий набір спеціально для вимірювання pair completeness блокування.
• Метрики розділяють по стадіях. PC/RR — за блокування, precision/recall — за матчер, B-cubed — за кластеризацію. Одне число на весь пайплайн ховає, яка саме стадія деградувала.

Граф як подання результату. Розв'язаний домен природно лягає в граф властивостей: вузол — сутність, ребро — відношення. Три архітектурні правила, які визначають, чи буде з цим графом можливо жити:

• Злиття лишається оборотним. Джерельні записи не переписуються і не видаляються — вони лишаються вузлами, а кластер стає додатковим вузлом із ребрами RESOLVES_TO. Хибне злиття скасовується видаленням ребер, а не відновленням з бекапу.
• Правила виживання — поатрибутні. Золотий запис не «береться з найбільшого джерела»: для кожного атрибута діє власний пріоритет (верифікованість → свіжість → пріоритет системи), і поруч зі значенням зберігається запис-джерело. Інакше на питання «звідки це ім'я» немає відповіді.
• Відносини перепідвішуються на розв'язані вузли. Якщо ребра платежів лишити між джерельними записами, кластер із трьох записів помножить кожен платіж на три. Ребро агрегується на рівні сутностей, але зберігає посилання на джерельне ребро.

Саме цей шар — стабільні ідентичності об'єктів поверх мінливих таблиць — вирішує онтологічний шар Palantir Foundry і подібні платформи: аналітик питає про «контрагента», а не про party_id у сьомій системі. Вибір моделі зберігання (граф властивостей проти RDF) вторинний і диктується споживачем: обхід сусідства й агрегації — Cypher/Gremlin; федерація та формальні онтології — SPARQL. Мости між мовами існують, тому це рішення не є незворотним.

// Resolved entity as a node that never destroys its sources.
// The cluster is an EXTRA layer, so an incorrect merge is undone by deleting edges.
MERGE (e:ResolvedParty {cluster_id: $cluster_id})
  ON CREATE SET e.created_at = datetime(),
                e.method     = $method,          // 'rule:tax_id' | 'model:fs_v3'
                e.model_ver  = $model_version
SET e.legal_name     = $survivor_name,           // survivorship, resolved per attribute
    e.legal_name_src = $survivor_name_record_id, // ... and always the record it came from
    e.confidence     = $cluster_confidence;

WITH e
UNWIND $members AS m
  MATCH (r:SourceRecord {record_id: m.record_id})
  MERGE (r)-[l:RESOLVES_TO]->(e)
    SET l.score = m.score, l.decided_by = m.decided_by, l.decided_at = datetime();

// Relationships are asserted between RESOLVED nodes, never between raw records:
// otherwise a 3-record cluster makes the same payment appear three times to the analyst.
MATCH (a:SourceRecord)-[p:PAID]->(b:SourceRecord),
      (a)-[:RESOLVES_TO]->(ra:ResolvedParty),
      (b)-[:RESOLVES_TO]->(rb:ResolvedParty)
MERGE (ra)-[agg:PAID_AGG {source_edge_id: p.edge_id}]->(rb)
  SET agg.amount = p.amount, agg.source_system = p.source_system;

// Undo a bad merge without touching a single source row:
// MATCH (r:SourceRecord {record_id: $bad})-[l:RESOLVES_TO]->(:ResolvedParty {cluster_id: $c})
// DELETE l;

Джерела, з яких виведено напрям

1. HyperBlocker Accelerating Rule based Blocking in Entity Re
2. Scalable Entity Resolution Using Probabilistic Signatures
3. A Robust and Efficient Pipeline for Enterprise Level Large
4. An Overview of End to End Entity Resolut
5. The Role of Schema Matching in Large Enterprises
6. Valentine Evaluating Matching Techniques for Dataset Disco
7. A LINK BASED APPROACH TO ENTITY RESOLUTI
8. Towards Scalable Schema Mapping using Large Language Model
9. A Practioner s Guide to Evaluating Entity Resolution Resul
10. Meta Property Graphs Extending Property Graphs with Metada
11. Expressive Reasoning Graph Store A Unified Framework for M
12. S2CTrans Building a bridge from SPARQL to Cypher

Далі в цьому треку