Разрешение сущностей определение реальных сущностей в зашумленных данных

Разрешение сущностей в зашумленных данных

Основные теории и реализации на Python

Изображение автора, использующего Midjourney

В современном мире, основанном на данных, организации часто сталкиваются с проблемами разнообразных и несогласованных источников данных. Разрешение сущностей, также называемое связыванием записей или удалением дубликатов, помогает идентифицировать и объединять дублирующиеся или связанные записи, не имеющие общих идентификаторов внутри или между наборами данных. Точное разрешение сущностей повышает качество данных, улучшает процесс принятия решений и обеспечивает ценные идеи.

Разрешение сущностей идентифицирует ту же реальную сущность внутри или между несогласованными источниками данных (Изображение автора)

Разрешение сущностей применяется в различных отраслях. Например, системы управления взаимоотношениями с клиентами объединяют информацию о клиентах, улучшают сервис и позволяют проводить целевой маркетинг, разрешая дублирующиеся записи клиентов. Электронно-коммерческие платформы используют разрешение сущностей для объединения списков товаров, улучшая функциональность поиска, рекомендации и опыт клиента.

В этой статье мы рассмотрим технические детали основных подходов к разрешению сущностей с использованием набора данных для оценки.

Содержание

  • Обзор разрешения сущностей
  • Набор данных для оценки
  • Блокирование
  • Обработка блоков
  • Сопоставление сущностей
  • Кластеризация
  • Оценка кластеров

Обзор разрешения сущностей

Стандартная система разрешения сущностей (ER) состоит из нескольких этапов: блокирование, обработка блоков, сопоставление сущностей и кластеризация.

1. Блокирование: Это первый шаг в разрешении сущностей и направлено на сокращение пространства поиска для идентификации одной и той же сущности путем разделения набора данных на более мелкие, управляемые блоки. Эти блоки содержат записи, которые имеют схожие атрибуты, что делает последующее сравнение более эффективным.

2. Обработка блоков: Этот шаг уточняет блоки для минимизации количества сравнений путем отбрасывания двух типов ненужных сравнений: избыточных, которые повторяются в нескольких блоках, и лишних, которые вовлекают записи, которые маловероятно совпадут.

3. Сопоставление сущностей: Это фокусируется на сравнении записей внутри блоков для поиска совпадений на основе сходства записей. Для классификации пар записей как совпадающие или несовпадающие можно использовать различные метрики сходства и алгоритмы сопоставления.

4. Кластеризация: Кластеризация включает группировку совпадающих записей в кластеры на основе их сходства. Созданные кластеры могут быть использованы для получения объединенного представления сущностей.

Рабочий процесс разрешения сущностей (Изображение автора)

Набор данных для оценки

В следующих разделах мы более подробно рассмотрим каждый шаг в процессе разрешения сущностей, а также реализацию на Python с использованием набора данных для оценки.

Набор данных, полученный из группы баз данных Университета Лейпцига и лицензированный Creative Commons, производится на основе фактических записей о песнях из базы данных MusicBrainz, но был намеренно изменен с помощью инструмента для загрязнения данных DAPO. Этот инструмент внедряет как дубликаты, так и ошибки в набор данных, в результате чего он содержит дубликаты для 50% исходных записей в двух до пяти источников. Эти дубликаты были сгенерированы с высокой степенью повреждения и служат строгим тестом для оценки эффективности подходов ER и кластеризации.

Мы можем загрузить данные с помощью следующего кода.

import requestsfrom io import BytesIOimport pandas as pdurl = "https://raw.githubusercontent.com/tomonori-masui/entity-resolution/main/data/musicbrainz_200k.csv"res = requests.get(url)df = pd.read_csv(BytesIO(res.content))

Некоторые примеры записей выглядят примерно так.

Каждая запись представляет собой песню, имеющую атрибуты, такие как исполнитель, название, альбом, год и т. д. (Описания полей можно найти по этой ссылке). CID – это идентификатор кластера, и записи с одинаковым CID являются дубликатами (в приведенном выше примере все три записи представляют одну и ту же песню). Нашей целью является идентификация этих дубликатов в этом шумном наборе данных.

Для упрощения нашей работы мы сосредотачиваемся только на английских песнях. В коде ниже идентифицируются записи с идентификаторами кластеров, содержащими английские песни.

english_cids = df[    df.language.str.lower().str.contains("^en|^eg", na=False)].CID.unique()df = df[df.CID.isin(english_cids)].reset_index(drop=True)

Мы также предварительно обрабатываем некоторые из строковых полей, чтобы получить стандартизированные значения.

for col in ["title", "artist", "album"]:    df[col] = (        df[col]        .str.lower()        .replace("[^a-z0-9]", " ", regex=True)  # замена специальных символов пробелом        .replace(" +", " ", regex=True)         # удаление последовательных пробелов        .str.strip()                            # удаление ведущих и конечных пробелов    )df.loc[df.number.notna(), "number"] = (    df[df.number.notna()]    .number.replace("[^0-9]", "", regex=True)              # удаление нецифровых символов    .apply(lambda x: str(int(x)) if len(x) > 0 else None)  # удаление ведущих нулей)

Обратите внимание, что этот набор данных для проверки является единственным, и если у вас есть несколько источников данных, для которых вы хотите разрешить сущности, вам необходимо стандартизировать их схемы данных и объединить эти множественные источники данных в единый набор данных перед выполнением последующих шагов.

Блокирование

Блокирование – это первый шаг в разрешении сущностей, который группирует похожие записи на основе определенных атрибутов. Таким образом, процесс сужает свой поиск и рассматривает только сравнения внутри каждого блока, а не все возможные пары записей в наборе данных. Это значительно уменьшает количество сравнений и ускоряет процесс разрешения сущностей. При этом пропускаются многие сравнения, что может привести к пропущенным истинным совпадениям. Поэтому блокирование должно достичь хорошего баланса между эффективностью и точностью. В этом разделе мы рассмотрим три разные подхода к блокированию (стандартное блокирование, блокирование по токенам и соседство с сортировкой), чтобы найти наилучший баланс в этой компромиссной ситуации.

Стандартное блокирование

Самая простая техника блокирования заключается в разделении набора данных на блоки на основе определенного атрибута. Например, в нашем наборе данных можно создать блоки на основе поля Artist или Title. Этот подход интуитивно понятен и легко реализуем, но его эффективность очень чувствительна к шуму, так как даже незначительная разница в блокирующих ключах дубликатов приводит к их размещению в разных блоках.

Пример стандартного блокирования по полю Artist (изображение автора)

Мы можем получить стандартные блоки с помощью следующей функции. Словарь blocks будет хранить блокирующие ключи (key) и соответствующие им индексы (idx) заблокированных записей.

from collections import defaultdictdef standard_blocking(field_values: pd.Series) -> dict[str, list]:    blocks = defaultdict(list)    for idx, key in enumerate(field_values):        if key is not None:            blocks[key].append(idx)    return blocks

В следующем коде мы создаем три независимых стандартных блока, используя поля title, artist и album.

sb_title = standard_blocking(df.title)sb_artist = standard_blocking(df.artist)sb_album = standard_blocking(df.album)

Блокирование по токенам

Блокирование по токенам заключается в разделении (токенизации) значений атрибутов на более мелкие единицы, называемые токенами, и затем использовании этих токенов для создания блоков для сравнения. Токены обычно представляют собой отдельные слова или небольшие n-граммы (подстроки длиной n), извлеченные из текста. Блокирование по токенам создает блок для каждого уникального значения токена, независимо от связанных атрибутов: две записи будут находиться в одном блоке, если они имеют общий токен в любом из своих атрибутов. Это приводит к высокой полноте из-за избыточности (одна запись может принадлежать нескольким блокам), но снижает точность.

Пример блокировки токенов (изображение автора)

Функция ниже генерирует блоки токенов на основе слов-токенов. Обратите внимание, что мы исключаем стоп-слова (например, «a», «the», «is» и т.д.) из токенов.

from nltk.tokenize import word_tokenizedef token_blocking(df: pd.DataFrame, stop_words: set) -> dict[str, list]:    blocks = defaultdict(list)    for i, row in enumerate(df.itertuples()):        # объединяем столбцы и токенизируем        string = " ".join([str(value) for value in row if not pd.isna(value)])        tokens = set(            [word for word in word_tokenize(string) if word not in stop_words]        )        # создаем блоки        for token in tokens:            blocks[token].append(i)    return blocks

Поскольку мы знаем, какие поля являются релевантными для создания блоков, мы используем только определенные поля (title, artist и album) для выполнения блокировки токенов:

import stringfrom nltk.corpus import stopwordscolumns = ['title', 'artist', 'album']stop_words = set(stopwords.words('english') + list(string.punctuation))token_blocks = token_blocking(df[columns], stop_words)

Сортировка по соседству

Сортировка по соседству сортирует записи в алфавитном порядке по определенным значениям полей. Фиксированное окно определяет пары внутри окна в качестве кандидатов для сравнения. Обратите внимание, что она прямо создает список пар вместо блоков. В то время как этот метод эффективно обрабатывает шум в полях блокировки, выбор более маленького окна жертвует полнотой в пользу точности, в то время как более большое окно имеет более высокую полноту при более низкой точности.

Пример сортировки по соседству с размером окна 3 (изображение автора)

Код ниже выполняет сортировку по соседству с размером окна 3, используя поля title, artist и album в качестве ключей сортировки.

def sorted_neighborhood(    df: pd.DataFrame, keys: list, window_size: int = 3) -> np.ndarray:    sorted_indices = (        df[keys].dropna(how="all").sort_values(keys).index.tolist()    )    pairs = []    for window_end in range(1, len(sorted_indices)):        window_start = max(0, window_end - window_size)        for i in range(window_start, window_end):            pairs.append([sorted_indices[i], sorted_indices[window_end]])    return np.array(pairs)columns = ['title', 'artist', 'album']sn_pairs = sorted_neighborhood(df, columns)

Мы сравним производительность трех подходов, обсуждаемых в этом разделе, после выполнения обработки блоков и сопоставления сущностей в следующих двух разделах.

Обработка блоков

Этот шаг направлен на повышение точности блоков при сохранении сравнимого уровня полноты. Соответствующие техники включают сокращение ненужных и избыточных сравнений во входном наборе блоков B, что приводит к созданию нового набора блоков B′ с улучшенной точностью. Мы рассмотрим некоторые из основных техник обработки блоков в этом разделе.

Очистка блоков

Очистка блоков задает верхний предел размера блока и очищает блоки, если их размеры превышают предел. Она предполагает, что чрезмерно большие блоки в основном состоят из избыточных сравнений, что означает, что дубликаты, содержащиеся в этих блоках, скорее всего появятся в других более маленьких блоках.

Код ниже очищает блоки по предопределенному пределу (здесь установлено 1000 записей). Он также фильтрует блоки с одной записью, так как они не создают пары для сравнения. Мы выполняем эту функцию purge_blocks для трех стандартных блоков и блоков токенов из предыдущего раздела.

def purge_blocks(    blocks: dict[str, list], purging_threshold: int = 1000) -> dict[str, list]:    blocks_purged = {        key: indices        for key, indices in blocks.items()        if len(indices) < purging_threshold and len(indices) > 1    }    return blocks_purgedtoken_blocks = purge_blocks(token_blocks)sb_title = purge_blocks(sb_title)sb_artist = purge_blocks(sb_artist)sb_album = purge_blocks(sb_album)

Мета-блокировка

Мета-блокировка преобразует входную коллекцию блоков в граф (или матрицу смежности), где каждый узел соответствует записи, а ребра соединяют каждую пару записей, которые совпадают в блоке. Вес ребра представляет собой частоту совпадений пары по всем блокам: более высокие веса указывают на большую вероятность совпадения. Ребра с низкими весами отсекаются, так как они, вероятно, представляют избыточные сравнения. В результате для каждого сохраненного ребра генерируется новый блок, что приводит к уточненной коллекции блоков (или списку пар, так как каждый уточненный блок содержит только одну пару записей).

Пример мета-блокировки (изображение автора)

Мы выполняем мета-блокировку только на токенизированных блоках, так как они имеют много перекрытий между блоками. Следующий код создает список пар из токенизированных блоков, а затем преобразует его в матрицу смежности.

import itertoolsfrom scipy.sparse import csr_matrixdef get_pairs_from_blocks(blocks: dict[str, list]) -> list[list]:    return [        pair        for indices in blocks.values()        for pair in list(itertools.combinations(indices, 2))    ]def get_adjacency_matrix_from_pairs(    pairs: list[list], matrix_shape: tuple[int, int]) -> csr_matrix:    idx1 = [pair[0] for pair in pairs]    idx2 = [pair[1] for pair in pairs]    ones = np.ones(len(idx1))    return csr_matrix(        (ones, (idx1, idx2)), shape=matrix_shape, dtype=np.int8    )pairs = get_pairs_from_blocks(token_blocks)adj_matrix = get_adjacency_matrix_from_pairs(pairs, (len(df), len(df)))

Затем мы отсекаем ребра в матрице смежности на основе веса ребра. Здесь мы отсекаем все ребра с весом 1, что означает, что пары, которые появляются только в одном блоке, удаляются.

def prune_edges(    adj_matrix: csr_matrix,    edge_weight_threshold: float,) -> csr_matrix:    adj_matrix_pruned = adj_matrix >= edge_weight_threshold    return adj_matrix_prunedadj_matrix = prune_edges(adj_matrix, edge_weight_threshold=2)

Затем мы получаем пары из отсеченной матрицы смежности.

def get_pairs_from_adj_matrix(adjacency_matrix: csr_matrix) -> np.ndarray:    return np.array(adjacency_matrix.nonzero()).Ttb_pairs = get_pairs_from_adj_matrix(adj_matrix)

Объединение блоков

В случае стандартных блоков мы получаем объединение трех независимых блоков. Сначала мы преобразуем блоки в список матриц смежности.

adj_matrix_list = []for blocks in [sb_title, sb_artist, sb_album]:    pairs = get_pairs_from_blocks(blocks)    adj_matrix_list.append(        get_adjacency_matrix_from_pairs(pairs, (len(df), len(df)))    )

Затем мы получаем объединение матриц и пар кандидатов из него.

def get_union_of_adj_matrices(adj_matrix_list: list) -> csr_matrix:    adj_matrix = csr_matrix(adj_matrix_list[0].shape)    for matrix in adj_matrix_list:        adj_matrix += matrix    return adj_matrixadj_matrix_union = get_union_of_adj_matrices(adj_matrix_list)sb_pairs = get_pairs_from_adj_matrix(adj_matrix_union)

В таблице ниже суммируется конечное количество пар кандидатов из трех различных подходов к блокировке.

Мы определим, какой подход лучше для наших данных, рассмотрев результат сопоставления в следующем разделе.

Сопоставление сущностей

На этом этапе мы идентифицируем совпадающие пары из кандидатов, сгенерированных на предыдущем этапе. Хотя существует различные методы поиска совпадений, одним из прямолинейных подходов может быть следующий:

  1. Измерение сходства для каждого атрибутаВы можете использовать любые метрики сходства, такие как косинусное сходство, сходство Жаккара или расстояние Левенштейна, в зависимости от пригодности для ваших данных или конкретных требований. Поля текста могут потребовать токенизации перед вычислением сходства для некоторых метрик.
  2. Вычисление общего сходстваЭтот шаг объединяет сходства для каждого атрибута в общий показатель сходства, либо применяя вручную определенные правила, либо используя модель машинного обучения, обученную на размеченных данных, если они доступны.
  3. Определение совпаденийПрименяется порог сходства к общему показателю сходства для нахождения совпадений
Пример сопоставления сущностей (изображение автора)

Функция get_field_similarity_scores ниже занимается шагом 1 выше. Если sim_type установлен в «fuzzy», она вычисляет косинусную сходство; в противном случае она выполняет точное сопоставление. Косинусное сходство вычисляется на уровне 3-грамм на символьном уровне, векторизованных из входных строк с использованием модуля CountVectorizer из scikit-learn. Мы вычисляем косинусное сходство для полей title, artist и album, выполняя точное сопоставление для поля number.

from sklearn.preprocessing import normalizefrom sklearn.feature_extraction.text import CountVectorizerdef get_field_similarity_scores(    df: pd.DataFrame, pairs: np.ndarray, field_config: dict[str, str]) -> dict[str, np.ndarray]:    """    Измерение сходства по полю. Это либо косинусное сходство    (если sim_type == 'fuzzy'), либо точное сопоставление 0/1 (если sim_type == 'exact').     Оценки сходства атрибутов хранятся в словаре field_score     с именем поля в качестве ключа.    """    field_scores = {}    for field, sim_type in field_config.items():        if sim_type == "fuzzy":            field_scores[field] = cosine_similarities(                df[field].fillna(""), pairs            )        else:            field_scores[field] = exact_matches(df[field], pairs)    return field_scoresdef cosine_similarities(    field_values: pd.Series, pairs: np.ndarray) -> np.ndarray:    """    Вычисление косинусного сходства для пар    """    token_matrix_1, token_matrix_2 = get_token_matrix_pair(        field_values, pairs    )    cos_sim = cosine_similarities_on_pair_matrices(        token_matrix_1, token_matrix_2    )    return cos_simdef get_token_matrix_pair(    field_values: pd.Series, pairs: np.ndarray,) -> tuple[csr_matrix, csr_matrix]:    """    Преобразование пар в матрицы количества токенов (матрица записей     по токенам, заполненная количеством токенов).     """    all_idx = np.unique(pairs)    vectorizer = CountVectorizer(analyzer="char", ngram_range=(3, 3))    vectorizer.fit(field_values.loc[all_idx])    token_matrix_1 = vectorizer.transform(field_values.loc[pairs[:, 0]])    token_matrix_2 = vectorizer.transform(field_values.loc[pairs[:, 1]])    return token_matrix_1, token_matrix_2def cosine_similarities_on_pair_matrices(    token_matrix_1: csr_matrix, token_matrix_2: csr_matrix) -> np.ndarray:    """    Вычисление косинусного сходства для пары матриц количества токенов.    Сначала нормализуется каждая запись (ось=1), затем вычисляется скалярное произведение    для каждой пары записей.    """    token_matrix_1 = normalize(token_matrix_1, axis=1)    token_matrix_2 = normalize(token_matrix_2, axis=1)    cos_sim = np.asarray(        token_matrix_1.multiply(token_matrix_2).sum(axis=1)    ).flatten()    return cos_simdef exact_matches(    field_values: pd.Series, pairs: np.ndarray) -> np.ndarray:    """    Выполнение точного сопоставления для пар    """    arr1 = field_values.loc[pairs[:, 0]].values    arr2 = field_values.loc[pairs[:, 1]].values    return ((arr1 == arr2) & (~pd.isna(arr1)) & (~pd.isna(arr2))).astype(int)field_config = {    # <поле>: <sim_type>    "title": "fuzzy",    "artist": "fuzzy",    "album": "fuzzy",    "number": "exact",}field_scores_sb = get_field_similarity_scores(df, sb_pairs, field_config)

Правила сопоставления

Правила сопоставления (изображение автора)

После вычисления сходства в специфической области мы хотим объединить их в общий показатель сходства, как описано в шаге 2 выше. Здесь мы используем очень простой подход: мы просто вычисляем среднее значение оценок атрибутов, а затем применяем пороговое значение для определения совпадений (шаг 3). Значение порога уже настроено здесь, но вы можете настроить его, рассмотрев некоторые примеры совпавших/несовпавших пар при работе с вашим собственным набором данных.

def calc_overall_scores(field_scores: dict[str, np.ndarray]) -> np.ndarray:    return np.array(list(field_scores.values())).mean(axis=0)def find_matches(scores: np.ndarray, threshold: float) -> np.ndarray:    return scores >= thresholdscores_sb = calc_overall_scores(field_scores_sb)is_matched_sb = find_matches(scores_sb, threshold=0.64)

Приведенный выше код выполняет сопоставление пар из стандартного блока. Кроме того, мы расширяем этот процесс сопоставления для пар из блока токенов и отсортированного окружения, что позволяет сравнить их производительность. Ниже приведен код, который суммирует сравнение в таблице.

from IPython.display import displayfrom collections import Counterdef show_results(    is_matched_list: list[np.ndarray],    blocking_approach_name_list: list[str],):    result = pd.DataFrame(        [Counter(is_matched).values() for is_matched in is_matched_list],        columns=["Unmatch", "Match"],    )    result["Blocking Approach"] = blocking_approach_name_list    result["Matching Rate"] = result.Match / (        result.Match + result.Unmatch    )    result["Matching Rate"] = result["Matching Rate"].map("{:.1%}".format)    result["Match"] = result["Match"].map("{:,}".format)    result["Unmatch"] = result["Unmatch"].map("{:,}".format)    display(        result[["Blocking Approach", "Match", "Unmatch", "Matching Rate"]]    )is_matched_list = [is_matched_sb, is_matched_tb, is_matched_sn]blocking_approach_name_list = [    "Стандартное блокирование",    "Блокирование токенов",    "Отсортированное окружение",]show_results(is_matched_list, blocking_approach_name_list)

Ниже приведен вывод.

Как вы можете видеть в таблице, блокирование токенов дает наибольшее количество совпадений, в то время как отсортированное окружение имеет наивысший показатель сходства. Поскольку блокирование токенов, вероятно, имеет наименьшее количество пропущенных совпадений, мы будем продолжать с результатом этого подхода. Следует отметить, что наш маленький набор данных не вызывает проблем с масштабируемостью. Однако для больших наборов данных, где блокирование токенов может быть невозможно, рекомендуется рассмотреть другие более масштабируемые подходы.

Сопоставление с использованием машинного обучения

Сопоставление с использованием машинного обучения (изображение автора)

Если у вас есть помеченные данные или вручную помеченные образцы пар, как совпадающие или несовпадающие, вы можете обучить модель машинного обучения для прогнозирования сопоставленных пар. Поскольку наши данные имеют кластерные метки CID, мы преобразуем их в метки сопоставления (совпадение/несовпадение) для пар и обучим модель машинного обучения, сравнив ее производительность со сравнительным подходом, выполненным в предыдущем разделе.

Следующий код генерирует входные данные модели X и соответствующую целевую переменную y. Пары в одном и том же кластере CID определяются как совпадающие (y = 1), в то время как пары вне одного и того же кластера помечаются как несовпадающие (y = 0).

def get_x_y(    field_scores: dict[str, np.ndarray],    pairs: np.ndarray,    df: pd.DataFrame,) -> tuple[pd.DataFrame, np.ndarray]:    X = pd.DataFrame(field_scores)    y = df.loc[pairs[:, 0], "CID"].values == df.loc[pairs[:, 1], "CID"].values    return X, yX, y = get_x_y(field_scores_tb, tb_pairs, df)

Затем мы разделяем их на обучающий и тестовый наборы, а затем обучаем модель логистической регрессии.

from sklearn.model_selection import train_test_splitfrom sklearn.linear_model import LogisticRegressionX_train, X_test, y_train, y_test = train_test_split(    X, y, test_size=0.5, random_state=42)model = LogisticRegression(random_state=0).fit(X_train, y_train)

Ниже приведен код, который сравнивает его производительность (f1_score) с правиловым подходом.

from sklearn.metrics import f1_scorey_pred = model.predict(X_test)print(f"Модель f1_score: {f1_score(y_test, y_pred):.3f}")y_rule_base = is_matched_tb[X_test.index.values]print(f"Правило-основной f1_score: {f1_score(y_test, y_rule_base):.3f}")

Ниже показан вывод:

Хотя производительность модели лучше, производительность правилового подхода все равно может быть достаточно хорошей.

Для следующих шагов мы будем использовать совпавшие пары, определенные с помощью правилового подхода, учитывая, что во многих реальных случаях ручная разметка данных может быть непрактичной из-за ограничений ресурсов. Ниже приведен код, который извлекает совпавшие пары и их оценки сходства из кандидатских пар и их оценок блокировки токенов.

matched_pairs = tb_pairs[is_matched_tb]matched_scores = scores_tb[is_matched_tb]

Кластеризация

На этом шаге мы создаем кластеры сущностей на основе совпавших пар с предыдущего шага. Каждый кластер включает все записи, соответствующие отдельной реальной сущности.

Кластеризация для разрешения сущностей имеет несколько требований:

  1. Алгоритм без ограниченийАлгоритмы не должны требовать ввода каких-либо параметров, специфичных для области, таких как количество кластеров или диаметр кластеров.
  2. Способность обрабатывать неполную матрицу сходстваПоскольку процесс разрешения сущностей не вычисляет сходство для каждой возможной пары (что может быть описано как матрица N на N), алгоритмы должны быть способны обрабатывать неполную матрицу сходства (или список совпавших пар).
  3. МасштабируемостьРазрешение сущностей часто обрабатывает значительные наборы данных, поэтому важно, чтобы алгоритмы могли обрабатывать такие данные. В случае больших данных алгоритмы с высокой сложностью, например иерархическая кластеризация, могут быть непрактичными.

Для кластеризации мы рассмотрим три основных алгоритма однопроходной кластеризации: Partitioning (т.е. связанные компоненты), Center Clustering и Merge-Center Clustering, которые все удовлетворяют требованиям. Эти алгоритмы очень эффективны, так как они создают кластеры за один проход (или сложность O(n)) списка кандидатских пар, хотя некоторым из них требуется, чтобы список был отсортирован по оценке сходства.

Алгоритмы однопроходной кластеризации (источник: http://www.vldb.org/pvldb/vol2/vldb09-1025.pdf)

Partitioning/Connected Components

Этот алгоритм инициирует кластеризацию, сначала назначая каждому узлу свой собственный кластер. Затем он выполняет одно сканирование списка совпавших пар. Если он обнаруживает связанные узлы, которые не принадлежат одному и тому же кластеру, он объединяет их кластеры. Кратко говоря, он формирует кластер, группируя все связанные узлы через ребра (т.е. совпадающие записи через пары). Алгоритм может создавать кластеры, соединяющие непохожие записи через длинные пути.

Кластеризацию связанных компонентов можно выполнить с использованием модуля Scipy, как показано в приведенном ниже коде. Прежде чем выполнить его, вы захотите преобразовать список пар в матрицу смежности.

from scipy.sparse.csgraph import connected_componentsdef connected_components_from_pairs(    pairs: np.ndarray, dim: int) -> np.ndarray:    adjacency_matrix = get_adjacency_matrix_from_pairs(pairs, (dim, dim))    _, clusters = connected_components(        csgraph=adjacency_matrix, directed=False, return_labels=True    )    return clusterscc_clusters = connected_components_from_pairs(matched_pairs, len(df))

Center Clustering

Этот алгоритм [5] выполняет кластеризацию, где каждый кластер имеет центр и все записи в каждом кластере похожи на центр кластера. Он требует, чтобы список похожих пар был отсортирован по убыванию оценок сходства. Затем алгоритм выполняет кластеризацию за одно сканирование отсортированного списка. Когда узел u встречается впервые в процессе сканирования, он назначается центром кластера. Любые последующие узлы v, которые похожи на u (т.е. появляются в паре (u, v) в списке), присваиваются кластеру u и не рассматриваются снова в процессе.

Пример группировки по центру (Изображение автора)

Группировка слиянием центров

Этот алгоритм [6] выполняет аналогично группировке по центру, но объединяет две группы cᵢ и cⱼ, когда запись, похожая на центр группы cᵢ, также похожа на центр cⱼ. Обратите внимание, что при объединении двух групп не выбирается один центральный узел, что означает, что объединенные группы могут иметь несколько центральных узлов. Этот алгоритм можно выполнить аналогично в один проход по списку пар, сохраняя записи, связанные через объединенную группу.

Пример группировки слиянием центров (Изображение автора)

Для выполнения группировки по центру/слиянием центров сначала необходимо отсортировать список пар в порядке убывания оценок сходства.

def sort_pairs(pairs: np.ndarray, scores: np.ndarray) -> np.ndarray:    sorted_ids = (-1 * scores).argsort()    return pairs[sorted_ids]pairs_sored = sort_pairs(matched_pairs, matched_scores)

Затем, приведенный ниже код создает два набора пар: пары центр-ребенок, обозначенные как center_cluster_pairs, и пары объединенных узлов, обозначенные как merge_cluster_pairs. Затем мы можем создать группы центров и группы слиянием центров, применяя связанные компоненты к этим спискам пар.

def get_center_cluster_pairs(pairs, dim):    """    cluster_centers:         список, отслеживающий центр группы для каждой записи.        индексы списка соответствуют исходным индексам df        и значения представляют назначенные индексы центров групп    center_cluster_pairs:         список пар индексов, представляющих пары центр-ребенок    merge_cluster_pairs:        список пар объединенных узлов    """    cluster_centers = [None] * dim    center_cluster_pairs = []    merge_cluster_pairs = []    for idx1, idx2 in pairs:        if (            cluster_centers[idx1] is None            or cluster_centers[idx1] == idx1            or cluster_centers[idx2] is None            or cluster_centers[idx2] == idx2        ):            # если оба не являются ребенком, эти узлы объединяются            merge_cluster_pairs.append([idx1, idx2])        if cluster_centers[idx1] is None and cluster_centers[idx2] is None:            # если оба ранее не встречались, idx1 становится центром, а idx2 - ребенком            cluster_centers[idx1] = idx1            cluster_centers[idx2] = idx1            center_cluster_pairs.append([idx1, idx2])        elif cluster_centers[idx2] is None:            if cluster_centers[idx1] == idx1:                # если idx1 - центр, idx2 назначается этой группе                cluster_centers[idx2] = idx1                center_cluster_pairs.append([idx1, idx2])            else:                # если idx1 не центр, idx2 становится новым центром                cluster_centers[idx2] = idx2        elif cluster_centers[idx1] is None:            if cluster_centers[idx2] == idx2:                # если idx2 - центр, idx1 назначается этой группе                cluster_centers[idx1] = idx2                center_cluster_pairs.append([idx1, idx2])            else:                # если idx2 не центр, idx1 становится новым центром                cluster_centers[idx1] = idx1    return center_cluster_pairs, merge_cluster_pairscenter_cluster_pairs, merge_cluster_pairs = get_center_cluster_pairs(pairs_sored, len(df))ct_clusters = connected_components_from_pairs(center_cluster_pairs, len(df))mc_clusters = connected_components_from_pairs(merge_cluster_pairs, len(df))

Оценка группировки

Поскольку у нас есть метки групп, мы можем оценить качество группировки с помощью индекса Рэнда или скорректированного индекса Рэнда. Индекс Рэнда – это метрика оценки группировки, которая представляет собой долю пар, правильно сгруппированных вместе или разделенных. Он определяется следующим образом:

TP = Количество пар, которые объединены вместе в обоих предсказанных и истинных кластерах.

TN = Количество пар, которые разделены отдельно как в предсказанных, так и в истинных кластерах.

Индекс Рэнда = (TP + TN) / Общее количество возможных пар

Пример вычисления индекса Рэнда (изображение автора)

Скорректированный индекс Рэнда – это измененная версия индекса Рэнда, учитывающая случайность. Корректировка учитывает возможность случайного согласия в результатах кластеризации, которые были случайно назначены.

Уравнение скорректированного индекса Рэнда

Мы не будем вдаваться в то, как каждый термин в уравнении выше вычисляется здесь, но все, кто интересуется этой темой, могут обратиться к статье KY Yeung, которая объясняет метрику с примерами.

Ниже приведен код, который дает нам сравнение кластеров с использованием этих метрик, а также некоторой дополнительной базовой статистики.

from sklearn.metrics.cluster import rand_score, adjusted_rand_scorefrom IPython.display import displaydef get_stats(labels, clusters):    stats = []    stats.append(f"{rand_score(labels, clusters):.3f}")    stats.append(f"{adjusted_rand_score(labels, clusters):.3f}")    clus_dist = pd.Series(clusters).value_counts()    stats.append(f"{len(clus_dist):,}")    stats.append(f"{clus_dist.mean():.3f}")    stats.append(f"{clus_dist.min():,}")    stats.append(f"{clus_dist.max():,}")    return statsdef compare_clusters(cluster_list, cluster_names, labels):    stats_dict = {}    for clusters, name in zip(cluster_list, cluster_names):        stats = get_stats(labels, clusters)        stats_dict[name] = stats    display(        pd.DataFrame(            stats_dict,            index=[                "Индекс Рэнда",                "Скорректированный индекс Рэнда",                "Количество кластеров",                "Средний размер кластера",                "Минимальный размер кластера",                "Максимальный размер кластера",            ],        )    )cluster_list = [cc_clusters, ct_clusters, mc_clusters]cluster_names = ["Связные компоненты", "Центр", "Слияние-Центр"]compare_clusters(cluster_list, cluster_names, df.CID)

Ниже приведен вывод.

Как видно из таблицы, связные компоненты создают более крупные кластеры с наименьшим количеством кластеров, в то время как разница между связными компонентами и кластерами Слияние-Центр минимальна. Напротив, кластеры Центра дают более мелкие кластеры с наибольшим количеством. Обратите внимание, что у всех трех кластеров идеальный индекс Рэнда, так как у них большое количество кластеров, и межкластерные пары преобладают (т.е. даже случайная кластеризация дает уважаемый индекс Рэнда). Однако, если посмотреть на скорректированный индекс Рэнда, кластеризация Слияние-Центр является лучшей, в то время как ее отличие от связных компонент минимально.

Это завершает наше исследование фреймворка сопоставления сущностей. Как вы будете продолжать работу с созданными кластерами, зависит от ваших конкретных бизнес-требований или использования случая. Если вы стремитесь создать каноническое представление для каждого кластера, вы можете достичь этого, извлекая наиболее представительное значение (например, наиболее частое значение) для каждого поля внутри каждого кластера.

Если вас интересует, весь код доступен в Google Colab и репозитории GitHub ниже.

Google Colab

Сопоставление сущностей

colab.research.google.com

entity-resolution/entity_resolution_implementations.ipynb

Сопоставление сущностей

github.com

Ссылки

[1] Christophides et al., End-to-End Entity Resolution for Big Data: A Survey (2019)

[2] Papadakis et al., Comparative analysis of approximate blocking techniques for entity resolution (2016)

[3] Пападакис и др., Обзор техник блокировки и фильтрации для разрешения сущностей (2020)

[4] Хасанзаде и др., Фреймворк для оценки алгоритмов кластеризации при обнаружении дубликатов (2009)

[5] Хавеливала и др., Масштабируемые техники кластеризации веба (2000)

[6] Хасанзаде и Миллер, Создание вероятностных баз данных из дублированных данных (2009)