实体解析：在嘈杂数据中识别现实世界实体

实体解析：识别嘈杂数据中的实际实体

基本理论与Python实现

在今天的数据驱动世界中，组织常常面临着多样化和不一致的数据源的挑战。实体解析（也称为记录链接或去重）有助于识别和合并不在数据集内部或跨数据集中共享任何唯一标识符的重复或相关记录。准确的实体解析提高数据质量，增强决策能力，并提供有价值的见解。

实体解析适用于各个行业。例如，客户关系管理系统通过解决重复的客户记录来整合客户信息，提高服务质量，并实现定向营销。电子商务平台使用实体解析来合并产品列表，提升搜索功能、推荐以及客户体验。

在本文中，我们将探索使用基准数据集的基本实体解析方法的技术细节。

目录

• 实体解析概述
• 基准数据集
• 分块
• 块处理
• 实体匹配
• 聚类
• 聚类评估

实体解析概述

标准的实体解析（ER）框架包括几个步骤：分块、块处理、实体匹配和聚类。

• OpenAI公布了DALL·E 3：文本到图像生成的革命性跃进
• IBM研究人员提出了一种新的对抗性攻击框架，能够针对AI系统生成对抗性输入，无论其模态或任务如何
• Google Pub/Sub到BigQuery的简单方式

1. 分块：这是实体解析的第一步，旨在通过将数据集划分为更小、可管理的块，以减少搜索空间以识别相同实体。这些块包含具有相似属性的记录，使得后续的比较更加高效。

2. 块处理：此步骤通过丢弃两种类型的不必要比较来完善块，以减少比较的数量：冗余比较，这些比较在多个块中重复出现；多余比较，涉及不太可能匹配的记录。

3. 实体匹配：这一步聚焦于在块内比较记录，根据记录的相似性找到匹配项。可以使用各种相似度度量和匹配算法将记录对分类为匹配或非匹配。

4. 聚类：聚类涉及将匹配的记录根据相似性分组。创建的聚类可用于获得实体的综合视图。

基准数据集

在接下来的几节中，我们将深入介绍实体解析过程中每个步骤的更多细节，以及使用基准数据集进行Python实现。

该数据集来自莱比锡大学数据库组，并获得了知识共享许可。它是从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是集群ID，具有相同CID的记录是重复的（在上面的示例中，所有三个记录代表同一首歌曲）。我们的目标是在这个嘈杂的数据集中识别这些重复项。

为了简化我们的工作，我们只关注英文歌曲。下面的代码识别具有包含英文歌曲的集群ID的记录。

“`python
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)
“`

我们还对一些字符串字段进行预处理，以获得标准化的值。

“`python
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字段创建块。这种方法直观且易于实现，但其有效性对噪声非常敏感，因为重复项的阻塞键即使在最轻微的差异下也会将它们放在不同的块中。

下面的函数可以获得标准块。字典blocks将存储阻塞键（key）及其对应的记录索引（idx）。

“`python
from collections import defaultdict

def 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字段创建了三个独立的标准块。

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

标记阻塞

标记阻塞的重点是将属性的值分解（即标记化）为较小的单元，称为标记，然后使用这些标记来创建用于比较的块。标记通常是从文本中提取的单个单词或小的n-gram（长度为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()):        # concatenate columns and tokenize        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]        )        # create blocks        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)

排序邻域

排序邻域按字母顺序对特定字段的值进行排序。一个固定大小的窗口在排序后的记录上滑动，并且窗口内的所有可能配对被识别为进行比较的候选配对。请注意，它直接产生一系列配对而不是块。虽然此方法可以有效处理阻塞字段中的噪声，但选择较小的窗口会在精度上牺牲召回率，而较大的窗口召回率较高但精度较低。

下面的代码使用title，artist和album字段作为排序键，执行了窗口大小为3的排序邻域：

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. 在每个属性上计算相似度可以使用任何相似度度量，如余弦相似度、Jaccard相似度或Levenshtein距离相似度，根据数据的适用性或具体要求选择。对于某些度量方法，可能需要在计算相似度之前对文本字段进行分词。
2. 计算总体相似度将每个属性的相似度合并为总体相似度得分，可以通过应用手动定义的规则或利用已标记数据训练的机器学习模型来完成。
3. 确定匹配将总体相似度得分应用于相似度阈值，以找到匹配。

下面的函数get_field_similarity_scores负责上述步骤1。如果sim_type设置为“fuzzy”，则计算余弦相似度；否则进行精确匹配。余弦相似度计算在字符级别的3-gram上进行，这些3-gram是使用scikit-learn的CountVectorizer模块从输入字符串向量化得到的。我们计算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'，则计算余弦相似度；如果sim_type == 'exact'，则进行精确匹配，返回的是0/1。     属性的相似性得分存储在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:    """    计算对数计数矩阵对的余弦相似度。首先对每个记录进行归一化（axis=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=["不匹配", "匹配"],    )    result["阻塞方法"] = blocking_approach_name_list    result["匹配率"] = result.Match / (        result.Match + result.Unmatch    )    result["匹配率"] = result["匹配率"].map("{:.1%}".format)    result["匹配"] = result["匹配"].map("{:,}".format)    result["不匹配"] = result["不匹配"].map("{:,}".format)    display(        result[["阻塞方法", "匹配", "不匹配", "匹配率"]]    )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. 可扩展性实体解析通常处理大规模数据集，因此算法能够处理这样的数据非常重要。在大数据情况下，具有高复杂度的层次聚类等算法可能不可行。

对于聚类，我们将研究三种主要的单次遍历聚类算法：划分（即连通组件）、中心聚类和合并中心聚类，它们都满足要求。这些算法非常高效，因为它们通过对候选对列表进行单次扫描（或O(n)时间复杂度）来创建聚类，尽管其中一些算法要求列表按相似度得分排序。

划分/连通组件

该算法通过最初将每个节点分配到其各自的簇来初始化聚类。然后，它对匹配对列表进行单次扫描。如果它识别到不属于同一簇的相连节点，它将合并它们的簇。简而言之，它通过将所有通过边（即通过对的匹配记录）连接的节点组成一个簇。该算法可能会创建通过长路径连接不相似记录的簇。

可以使用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))

中心聚类

该算法[5]执行聚类，其中每个聚类有一个中心，该聚类中的所有记录都与聚类的中心相似。它要求相似对的列表按相似度得分的降序排序。然后，该算法通过对排序后的列表进行一次扫描来执行聚类。当在扫描中首次遇到节点u时，将其指定为聚类中心。任何后续与u相似的节点v（即在列表中出现在对(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))

聚类评估

由于我们有聚类标签，可以使用Rand指数或调整后的Rand指数来评估聚类的质量。Rand指数是一种聚类评估指标，表示正确聚类在一起或分开的配对比例。其定义如下：

TP = 预测和真实簇中被聚类在一起的配对数量。

TN = 预测和真实簇中被聚类分开的配对数量。

Rand指数 = (TP + TN) / 可能的配对总数

调整后的Rand指数是Rand指数的修改版本，它校正了偶然性。该校正考虑了聚类结果中由于随机分配而产生的随机一致性的可能性。

我们不会详细介绍上述公式中每个术语的计算方法，但对该主题感兴趣的人可以参考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=[                "Rand指数",                "调整后的Rand指数",                "簇数量",                "平均簇大小",                "最小簇大小",                "最大簇大小",            ],        )    )cluster_list = [cc_clusters, ct_clusters, mc_clusters]cluster_names = ["联通组件", "中心", "合并-中心"]compare_clusters(cluster_list, cluster_names, df.CID)

下面是输出结果。

如您所见，在表中，联通组件产生了较大的簇数，且簇数最少，而联通组件和合并-中心簇之间的差距较小。相反，中心簇产生了较小的簇数，且簇数最多。请注意，这三个簇的Rand指数都是完美的，因为它们有大量的簇，使得簇间配对占主导地位（即，即使是随机聚类也会产生可观的Rand指数）。然而，如果您查看调整后的Rand指数，则合并-中心聚类是最好的，而与联通组件聚类的差异很小。

这就结束了我们对实体解析框架的探索。您如何处理创建的簇取决于您的具体业务需求或用例。如果您的目标是为每个簇建立一个规范表示，您可以通过提取每个簇中每个字段的最具代表性的值（例如最频繁的值）来实现这一目标。

如果您感兴趣，完整的代码可以在以下Google Colab和GitHub存储库中找到。

Google Colaboratory

实体解析

colab.research.google.com

entity-resolution/entity_resolution_implementations.ipynb

实体解析

github.com

参考资料

[1] Christophides等人，大数据的端到端实体解析：一项调查（2019）

[2] Papadakis等人，实体解析的近似阻塞技术的比较分析（2016）

[3] Papadakis等人，用于实体解析的阻塞和过滤技术调查（2020）

[4] Hassanzadeh等人，用于重复检测中评估聚类算法的框架（2009）

[5] Haveliwala等人，用于对Web进行聚类的可扩展技术（2000）

[6] Hassanzadeh和Miller，从重复数据创建概率数据库（2009）