知识融合的基本技术流程

小象实战讲义 · 知识图谱

上一节回答了“什么是知识融合”：把多个来源、互相异构的知识库在概念层和数据层对齐成一个整体。这一节拆开它的基本技术流程——从原始数据进门，到输出一批可信的 sameAs 对齐，中间要过哪几道工序、每道工序有哪些经典算法。工具（Falcon-AO、Dedupe、LIMES、Silk）留到下一节，本节先把流程与算法原理讲透，并用 Python 把最常用的相似度算子和分块过程跑起来。

💡 核心导读

• 知识融合在工程上分成本体对齐（概念层）与实体匹配（数据层）两条路线，流程同构，可流水线分开做，也可联合（joint）做。
• 完整流水线含五步：数据预处理 → 分块（Blocking）→ 匹配项计算 → 负载均衡 → 结果评估（这是工程流水线视角：分块放在匹配前，是为了先缩小候选、降低后续比较量）。而本节正文按课件讲授/概念展开视角组织——先把记录链接的匹配度量讲透，再把分块作为规模问题后置展开，两个视角顺序不同、并不矛盾（小结处会再次点明）。
• 记录链接（record linkage）分两步：先算逐属性的属性相似度（编辑距离、集合系数、TF-IDF 向量三大类），再聚合成实体相似度（聚合、聚类、知识表示学习三条路线）。
• 分块不直接决定效果，却决定“跑不跑得动”：两个百万级库直接两两比较是 10^12 量级，切 1000 个块可降到 10^9。
• 效果用准确率（Precision）、召回率（Recall）、F1 衡量，效率用运行时间与复杂度衡量，都要对标准答案（ground truth）交代。

一、流程总览：本体对齐与实体匹配

知识融合一般分为两步：本体对齐（ontology alignment）和实体匹配（entity matching）。两者的区别在于处理的层次：

• 本体对齐面向概念层：处理的是类（class）、属性（property）、关系这些 schema 层面的元素，例如知识库 A 的 Person 类与知识库 B 的 Human 类是否等价、A 的 bornIn 与 B 的 birthPlace 是否同一条关系。
• 实体匹配面向数据层：处理的是一条条具体记录（实例），例如 A 中的“北京大学第三医院”与 B 中的“北医三院”是不是同一个现实对象，判定后通常落一条 owl:sameAs 链接。

这两步既可按 pipeline 分开串行做，也可联合（joint）做，因为它们互相影响：若两个类下面的实体频繁被融合，这两个类本身很可能等价；反过来，概念层的等价与包含关系能约束实体匹配的候选输入和匹配函数置信度。这与知识抽取中“实体识别”与“关系抽取”既可流水线也可联合建模是同一个道理。

无论是本体对齐还是实体匹配，基本流程都很相似，可以概括为五个环节：

1. 数据预处理（preprocessing）：清洗、规范化原始数据，是后续一切精度的前提；
2. 分块（blocking）：为应对规模问题，先粗筛出“可能匹配”的候选对，把平方级比较压到块内；
3. 匹配项计算（alignment）：在候选对上逐对计算相似度，判定哪些实体/概念应当对齐；
4. 负载均衡（load balance）：把块分发到不同计算节点，避免短板，常见于 MapReduce 式分布式实现；
5. 结果评估（evaluation）：与标准答案（ground truth）对比，同时评估效果（准不准）和效率（快不快）。

下面按这条流水线依次展开，重点在第二、第三步的算法。

二、数据预处理：容易被忽视的“苦活”

原始数据质量直接决定最终链接结果：不同数据集对同一实体的描述方式往往不同，日期格式、电话写法、名称繁简、空格符号都可能让两个明明相同的实体“对不上”。预处理往往占用整个工程最长的时间，却决定了后续算法的难易程度，是“虽苦但必要”的活。它对应数据仓库里的 ETL（Extraction-Transform-Load，抽取-转换-加载），数据竞赛中常见的 EDA（Exploratory Data Analysis，探索式数据分析）也属于这一范畴——先摸清数据规律，再谈建模。

课件把预处理归纳为两类基础工作：

1. 语法正规化（syntax normalization）：对特定属性值做语法合法性匹配与统一。例如联系电话有 +86 010-xxxx-xxxx、(010)xxxxxxxx、138 xxxx xxxx 等写法；生日、日期、email、家庭地址这类综合属性也需先解析、归一到统一表示才能逐位比较。

2. 数据正规化（data normalization）：统一缩进与大小写，移除多余空格和《》、“”、- 等特殊符号，修正错字、多字、漏字等输入型拓扑错误；更高级的做法是实体归一化（entity normalization / entity linking），用全名或正式名替换别称、昵称、缩写，如把“北医三院”统一成“北京大学第三医院”。

预处理越干净，相似度算子越容易把真正相同的实体判成高相似；垃圾进、垃圾出，再精巧的匹配算法也救不回脏乱的输入。

三、记录链接第一步：属性相似度

预处理之后先放下效率问题，看核心算子：怎么判断两个实体该不该匹配？这在数据库文献里叫记录链接（record linkage）。设两条记录 x、y 在第 i 个属性上的取值为 x_i、y_i，链接分两步：

1. 属性相似度：对每个属性分别计算 sim(x_i, y_i)，N 个属性就得到一个 N 维的属性相似度向量 [sim(x1,y1), sim(x2,y2), …, sim(xN,yN)]；
2. 实体相似度：再根据这个向量，综合判定 x 与 y 是否为同一实体。

属性相似度怎么算？课件给了三大类方法：基于字符的编辑距离、基于集合的系数、基于向量的相似度。

3.1 编辑距离：从 Levenshtein 到仿射间隙

Levenshtein 距离（最小编辑距离）用最少的编辑操作把一个字符串变成另一个，允许插入（insert）、删除（delete）、替换（substitute）三种操作，经典定义中代价均为 1，最少操作次数即距离。课件例子：Lvensshtain 变成 Levenshtein，依次为“L 后插入 e”“删除多余的 s”“a 替换为 e”，共 3 次，距离为 3。

最少次数用动态规划求解。记 d(i,j) 为第一个串前 i 个字符变到第二个串前 j 个字符的最小代价：边界上 d(i,0)=i、d(0,j)=j（空串只能逐个增删）；递推时 d(i,j) 取三者最小——d(i-1,j)+1（删除一位）、d(i,j-1)+1（插入一位）、d(i-1,j-1)+cost（末两位相同 cost=0，否则替换 cost=1）。

Wagner-Fisher 距离是 Levenshtein 的加权扩展：给删除、插入、替换分别赋予权重 del、ins、sub，动态规划结构不变，只把每步代价换成对应权重，从而贴合真实错误分布（如键盘相邻键误触的替换代价可定低）。

Edit Distance with Affine Gaps（仿射间隙编辑距离）针对“连续一串增删往往是一次手抖造成一段空缺”的直觉，引入 gap（间隙）：用“打开间隙（gap opening，代价 s）+ 延续间隙（gap extension，每单位长度代价 e）”替代逐个计费，长度为 l 的间隙代价为 Cost(g) = s + e·l。该模型在生物序列比对中常用，实体匹配里用得不多。课件给出 4 个间隙、s=2、e=1 时总代价 (2+1×1)×4=12；讲授中老师当场指出该页数字存在笔误，理解“开间隙贵、延间隙便宜”的思想即可。

下面用 Python 把编辑距离家族和集合系数一次性跑通：

# -*- coding: utf-8 -*-
"""属性相似度（一）：编辑距离与集合相似度，纯标准库可运行"""
from collections import Counter


def levenshtein(a: str, b: str) -> int:
    """经典 Levenshtein 最小编辑距离：插入/删除/替换代价均为 1，动态规划求解。"""
    n, m = len(a), len(b)
    # d[i][j] 表示 a[:i] 变换到 b[:j] 的最小编辑代价；边界：空串只能逐个增删
    d = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        d[i][0] = i
    for j in range(m + 1):
        d[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1  # 末位字符相同则替换代价为0
            d[i][j] = min(
                d[i - 1][j] + 1,        # 删除 a 的第 i 个字符
                d[i][j - 1] + 1,        # 向 a 插入 b 的第 j 个字符
                d[i - 1][j - 1] + cost  # 替换（相同即免费对齐）
            )
    return d[n][m]


def wagner_fisher(a: str, b: str, w_del=1.0, w_ins=1.0, w_sub=1.0) -> float:
    """Wagner-Fisher：Levenshtein 的加权扩展，三种编辑操作可赋不同代价。"""
    n, m = len(a), len(b)
    d = [[0.0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        d[i][0] = i * w_del
    for j in range(m + 1):
        d[0][j] = j * w_ins
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            sub = 0.0 if a[i - 1] == b[j - 1] else w_sub
            d[i][j] = min(d[i - 1][j] + w_del, d[i][j - 1] + w_ins, d[i - 1][j - 1] + sub)
    return d[n][m]


def bigrams(s: str):
    """把字符串切成相邻两字符的 bigram 集合，用于把文本变成集合再比较。"""
    return {s[i:i + 2] for i in range(len(s) - 1)}


def dice_multiset(a: str, b: str) -> float:
    """Dice 系数 = 2|S∩T|/(|S|+|T|)；字符按多重集（出现次数）计数，与课件算例一致。"""
    ca, cb = Counter(a), Counter(b)
    inter = sum((ca & cb).values())  # Counter 的 & 取逐字符最小计数
    return 2 * inter / (len(a) + len(b))


def jaccard(sa: set, sb: set) -> float:
    """Jaccard 系数 = |S∩T| / |S∪T|，天然归一化到 [0,1]，适合短文本。"""
    return len(sa & sb) / len(sa | sb)


if __name__ == "__main__":
    s1, s2 = "Lvensshtain", "Levenshtein"
    print("编辑距离 Levenshtein(%s -> %s) = %d" % (s1, s2, levenshtein(s1, s2)))
    print("  对齐路径：L 后插入 e、删除多余的 s、a 替换为 e，共 3 次操作")
    print("加权 Wagner-Fisher(替换代价=2) = %.1f" % wagner_fisher(s1, s2, w_sub=2.0))
    print("Dice(字符多重集) = 2*9/(11+11) = %.4f ≈ %.2f" % (dice_multiset(s1, s2), dice_multiset(s1, s2)))
    g1, g2 = bigrams(s1), bigrams(s2)
    print("bigram 集合 S =", sorted(g1))
    print("bigram 集合 T =", sorted(g2))
    print("Jaccard(bigram) = %.4f" % jaccard(g1, g2))
    print("Jaccard(字符集合) = %.4f" % jaccard(set(s1), set(s2)))
    # 编辑距离也可归一化到 [0,1] 的相似度：1 - dist / max(len)
    print("归一化编辑相似度 = %.4f" % (1 - levenshtein(s1, s2) / max(len(s1), len(s2))))

运行结果：

编辑距离 Levenshtein(Lvensshtain -> Levenshtein) = 3
  对齐路径：L 后插入 e、删除多余的 s、a 替换为 e，共 3 次操作
加权 Wagner-Fisher(替换代价=2) = 4.0
Dice(字符多重集) = 2*9/(11+11) = 0.8182 ≈ 0.82
bigram 集合 S = ['Lv', 'ai', 'en', 'ht', 'in', 'ns', 'sh', 'ss', 'ta', 've']
bigram 集合 T = ['Le', 'ei', 'en', 'ev', 'ht', 'in', 'ns', 'sh', 'te', 've']
Jaccard(bigram) = 0.4286
Jaccard(字符集合) = 0.8889
归一化编辑相似度 = 0.7273

3.2 集合相似度：Dice 与 Jaccard

把字符串看成集合，就可以用集合交并关系度量相似性，两个系数都天然归一化到 [0,1]：

• Dice 系数：sim(S,T) = 2|S∩T| / (|S|+|T|)。仍以 Lvensshtain 与 Levenshtein 为例，11 个字符位里只有 2 处不同（e/a、s/e），按字符多重集（计入重复出现次数）统计共有 9 个字符对齐，于是相似度 = 2×9/(11+11) ≈ 0.82。
• Jaccard 系数：sim(S,T) = |S∩T| / |S∪T|，分母从“两个集合大小之和”换成“并集大小”，定义与 Dice 类似，工程上更常用，尤其适合短文本。

文本变集合，除按分隔符切词（token）外，还可按 n-gram 切分：n=2 即 bigram，把 Lvensshtain 切成 {Lv, ve, en, ns, ss, sh, ht, ta, ai, in} 这样的相邻双字符集合再算交并。n-gram 对词序错位、轻微拼写错误更鲁棒。上面的代码同时给出字符集合与 bigram 集合两种口径的 Jaccard，可体会切分粒度对数值的影响。

3.3 向量相似度：TF-IDF 与余弦

第三类思路把文本映射成向量，再用向量间的距离度量相似性，信息检索里最经典的是 TF-IDF 加权配合余弦相似度（cosine similarity）。

• TF（Term Frequency，词频）衡量词在当前文档中的重要程度，出现越多越重要，TF = 词在文档中出现次数 / 文档总词数。
• IDF（Inverse Document Frequency，逆文档频率）方向相反：一个词若在太多文档出现（如英文冠词 the、a），就是区分度很低的停用词（stop word），IDF 应低。IDF = log(文档总数 / (包含该词的文档数 + 1))，分母加 1 防除零。
• 两者相乘得 TF-IDF 权重：词在本文档出现越多、在整个语料中越罕见，权重越高。文档向量化后用余弦（内积除以两向量模长之积）比较方向一致性，即得相似度。

课件算例：语料共 5 万篇文档，其中 2 万篇含“健康”；某篇文章共 1000 个词，“健康”出现 30 次，则 TF = 30/1000，IDF = log(50000/(20000+1))，TF-IDF ≈ 0.012（该结果对应以 10 为底的对数）。下面复现这个算例，并在一个微型机构名语料上比较 TF-IDF 向量的余弦：

# -*- coding: utf-8 -*-
"""属性相似度（二）：基于向量的 TF-IDF 与余弦相似度，纯标准库可运行"""
import math
from collections import Counter


def tokenize(text: str):
    """极简分词：按空白切分并小写化（中文工程里可换成 jieba 等分词器）。"""
    return text.lower().split()


def tf(term: str, doc_tokens: list) -> float:
    """词频 TF = 该词在文档中出现次数 / 文档总词数。"""
    return doc_tokens.count(term) / len(doc_tokens)


def idf(term: str, docs_tokens: list) -> float:
    """逆文档频率 IDF = log10(文档总数 / (包含该词的文档数 + 1))，分母 +1 防除零。
    课件算例结果 0.012 对应以 10 为底的对数。"""
    contain = sum(1 for d in docs_tokens if term in d)
    return math.log10(len(docs_tokens) / (contain + 1))


def tfidf_vector(doc_tokens: list, docs_tokens: list) -> dict:
    """把一篇文档表示成词表上的 TF-IDF 向量（用字典模拟稀疏向量）。"""
    c = Counter(doc_tokens)
    return {w: (c[w] / len(doc_tokens)) * idf(w, docs_tokens) for w in c}


def cosine(v1: dict, v2: dict) -> float:
    """余弦相似度 = 向量内积 / 各自模长的乘积，文本场景取值多在 [0,1]。"""
    common = set(v1) & set(v2)
    dot = sum(v1[w] * v2[w] for w in common)
    n1 = math.sqrt(sum(x * x for x in v1.values()))
    n2 = math.sqrt(sum(x * x for x in v2.values()))
    return dot / (n1 * n2) if n1 and n2 else 0.0


if __name__ == "__main__":
    # 复现课件算例：5 万篇文档，2 万篇含“健康”；某文共 1000 词、“健康”出现 30 次
    N, df = 50000, 20000
    tf_health = 30 / 1000
    idf_health = math.log10(N / (df + 1))
    print("TF(健康) = 30/1000 = %.4f" % tf_health)
    print("IDF(健康) = log10(50000/20001) = %.4f" % idf_health)
    print("TF-IDF(健康) = %.5f ≈ 0.012" % (tf_health * idf_health))

    # 微型语料：四条机构记录（已用空格分好词），比较名称这一属性的向量相似度
    corpus = [
        "北京大学 第三医院 骨科",
        "北京大学 第三医院 骨科 门诊",
        "清华大学 玉泉医院 内科",
        "北京大学 人民医院 骨科",
    ]
    corpus_tok = [tokenize(d) for d in corpus]
    rec_x = tokenize("北京大学 第三医院 骨科")        # 知识库 A 的名称
    rec_y = tokenize("北京大学 第三医院 骨科 门诊")   # 知识库 B：同一机构的更全写法
    rec_z = tokenize("清华大学 玉泉医院 内科")        # 另一家机构
    vx = tfidf_vector(rec_x, corpus_tok)
    vy = tfidf_vector(rec_y, corpus_tok)
    vz = tfidf_vector(rec_z, corpus_tok)
    print("cosine(记录X, 记录Y) = %.4f  # 同一机构的详略两种写法，应较相似" % cosine(vx, vy))
    print("cosine(记录X, 记录Z) = %.4f  # 不同机构，应较低" % cosine(vx, vz))

运行结果：

TF(健康) = 30/1000 = 0.0300
IDF(健康) = log10(50000/20001) = 0.3979
TF-IDF(健康) = 0.01194 ≈ 0.012
cosine(记录X, 记录Y) = 0.3833  # 同一机构的详略两种写法，应较相似
cosine(记录X, 记录Z) = 0.0000  # 不同机构，应较低

需要强调：没有哪种距离“包打天下”——编辑距离对插入替换敏感、集合系数重词项共现、TF-IDF 重全局区分度，各有适用与失灵场景，工程中通常多属性、多算子组合使用，这正是“实体相似度聚合”存在的原因。

四、记录链接第二步：实体相似度

拿到 N 维属性相似度向量后，怎么得出“x 与 y 是否同一实体”的最终判断？课件给了三条路线：聚合、聚类、知识表示学习。

4.1 聚合：加权平均、手工规则与分类器

（1）加权平均：把每一维相似度归一到 [0,1]，配一组和为 1 的权重 w1…wN，实体相似度 = Σ wi·sim(xi,yi)。权重通常按启发式经验设定，例如名称 0.5、地址 0.3、电话 0.2。

（2）手工制定规则：用阈值和逻辑组合表达业务经验，例如“名称相似度 > T1，且（AND/OR）地址相似度 > T2，且电话完全一致”。规则可解释、好调试，是工业界最常见的起步方案。

（3）训练分类器：把“实体对匹配/不匹配”当成二分类问题，逻辑回归（近似可学习的加权平均）、决策树（近似自动归纳的手工规则）、SVM、条件随机场都可上场，代价是必须有标注数据来学权重与阈值。

机器学习路线有三个难题：其一，训练集怎么构建——现实中往往只有少量已知对齐的正例，负例（明确不匹配的实体对）要自己产生；其二，这是高度不平衡的二分类——候选对里不匹配的数量远多于匹配的；其三，误分类难控制。应对思路包括无监督/半监督实体对齐（unsupervised / semi-supervised entity alignment）、EM（Expectation-Maximization，期望最大化）等生成式方法、主动学习（active learning）把易错样本交人工干预、众包标注。注意辨析：半监督不等于远程监督——半监督泛指“大量未标注数据 + 少量标注数据”的范式，标签传播（label propagation）、基于图的方法、bootstrapping、远程监督（distant supervision）都是它的具体实现，远程监督只是其中一种。

4.2 聚类：层次聚类、相关性聚类与 Canopy+K-means

不逐对二分类，而是把所有实体放进相似度空间做聚类（clustering），同簇即同一实体，课件介绍了三种：

（1）层次聚类（hierarchical clustering）：自底向上（bottom-up）聚合，初始每个实体自成一簇，每轮合并距离最近的两簇，结果是一棵二叉树状图（dendrogram）。在树的不同高度切分即可控制“哪些实体算匹配”：提前停止、只合并最有把握的簇，追求准确率；一路聚合到更高层，追求覆盖率（召回）。簇间距离有三种经典连法（linkage）：

• Single Linkage（SL，最近邻）：取两簇间最近一对点的距离，容易链式粘连；
• Complete Linkage（CL，最远邻）：取两簇间最远一对点的距离，簇更紧凑；
• Average Linkage（AL，平均）：取两簇所有点对距离的均值，折中最常用。

课件例子是 7 个一维数值实体 a–g 的 7×7 对称距离方阵：先合并距离最小的 B、C（38.5 与 39.5，欧氏距离 1.00），方阵降为 6×6；再按所选 linkage（SL 取 min、CL 取 max、AL 取均值）计算单点与 (B,C) 簇的距离，继续合并 E、D……迭代得到树状图。层次聚类天然契合 MapReduce 式并行迭代，这是它在大规模融合中受青睐的原因。

（2）相关性聚类（correlation clustering）：把实体看成图节点，相似度作为边权。令 p_xy 为 x、y 同属一类的概率（即相似度），切断边的代价 w⁺_xy = p_xy（越相似硬切开代价越高），保留边的代价 w⁻_xy = 1−p_xy（越不相似硬留在一起代价越高）；r_xy 表示 x、y 是否同簇，目标是最小化总代价 Σ r_xy·w⁻_xy + (1−r_xy)·w⁺_xy。这是 NP-hard 的图上最优化问题，可用贪心（greedy）近似求解，思路类似最大流最小割：高相似的实线尽量不切断、低相似的虚线尽量不强留，得到全局近似最优划分。

（3）Canopy + K-means：K-means 是需事先指定簇数 k 的平层聚类；Canopy 聚类速度快、不需指定 k，本质是粗糙的分块/聚类，两者常配合：先 Canopy 粗分块，再在每个 canopy 内做精细 pairwise 比较或 K-means。Canopy 用两个距离阈值 t1（宽）、t2（严）：随机选一个点作中心，距离小于 t1 的点归入该 canopy（块间允许重叠 overlap），距离小于 t2 的点确定同簇并从候选列表移除，循环至列表为空。其复杂度很低，Mahout 等基于 Hadoop/MapReduce 的机器学习平台均内置支持。

4.3 知识表示学习：把实体对齐变成向量空间中的近邻搜索

第三条路线是知识表示学习（knowledge representation learning）/ 知识嵌入（knowledge embedding）：把实体和关系映射成低维稠密向量，直接用向量距离（余弦、欧氏距离等）计算实体相似度，不依赖文本字面，捕获的是数据的深度结构特征。

翻译模型 TransE 对三元组 (h, r, t) 假设：头实体向量加关系向量近似等于尾实体向量，即 l_h + l_r ≈ l_t（主语 + 谓语 ≈ 宾语）。训练充分后，向量空间会出现“国王 − 女王 ≈ 男人 − 女人”式的平移规律；配合链接预测（link prediction，给定 s、p 预测 o，或给定 s、o 预测 p）即可推断实体等价关系。课件例子：KG1 有“义勇军进行曲 —作曲→ 聂耳”，KG2 有“中国国歌 —作曲→ 聂耳”，两图嵌入同一空间后，“义勇军进行曲”与“中国国歌”向量距离极近，等价性很高。

跨图谱嵌入的关键是如何把两个 KG 嵌入同一语义空间，桥梁是预链接实体对（seed alignments）：开放知识库中已有的 sameAs 链接可充当训练数据（至少是正例）。两种基本思想：

• 联合知识嵌入：把两个 KG 的三元组糅合（join）共同训练，将已知 sameAs 实体对视为 SameAs 关系三元组作为约束，使两空间在训练中对齐。TransE 单库训练像语言模型一样天然自带标注（自监督），跨库 sameAs 约束引入少量已知对齐，属于半监督。代表工作是 Zhu 等人的 Iterative Entity Alignment via Joint Knowledge Embeddings（IJCAI 2017，清华大学刘知远老师组，迭代式地用新发现的对齐再训练）。
• 双向监督训练：两个 KG 先各自单独训练，再用预链接数据交替交叉监督。

向量训练稳定后链接实体就水到渠成：对 KG1 中每个未链接实体，到 KG2 中找向量距离最近的实体建立链接（欧氏距离、余弦均可），本质是 sameAs 关系上的一次链接预测——先训练、再 apply。OAEI 提供了现成的实体对齐测试集，OpenKG 数据集与 LIMES 工具实战在后续小节展开。

五、分块、负载均衡与结果评估

5.1 分块：为规模而生

前面假设“不考虑效率”，但两库直接两两链接的时间复杂度是 O(|M|×|N|) 的平方级。课件引用本体匹配工具 Falcon-AO（南京大学胡伟老师团队开发，AO 即 Alignment Ontology，工具细节见下一节）给出对比：两个各含 10^6 条记录的数据集，无分块要做 10^12 次比较；均匀切成 1000 个块后只在块内比较，总量降到 10^9，少了三个数量级。

分块（blocking）是从所有实体对中选出潜在匹配的记录对作为候选项，并把候选集尽量缩小。它不直接决定效果，却会间接影响效果——分块键选错会把本该匹配的对拆到不同块，直接丢召回。因此分块目标是：在保证覆盖率（coverage，真正匹配的对尽量留在同块）的前提下，把显然无关的实体对排除在同块之外，减少后续精细比较的次数。

两类常用分块方法：

（1）基于 Hash 函数的分块：对记录 x 计算 hash(x)=h_i，把它映射到与关键字 h_i 绑定的块 C_i。常见 hash 键包括字符串前 n 个字符（first-n-letter）、n-gram，以及多个简单 hash 的组合；SimHash、MinHash 等局部敏感哈希在近重复网页检测（near duplicate detection）中也有广泛应用。

（2）邻近分块：其一是前述 Canopy 聚类；其二是排序邻域法（Sorted Neighborhood）：先生成排序关键字（基于 hash、n-gram 或首字母），按关键字排序后只在给定大小的滑动窗口（window）内两两比较，核心在关键字生成策略与动态窗口大小；其三是把分块建模成二部图、对特征（谓词）做选择的 Red-Blue Set Cover 方法，Dedupe 工具采用该思路，下一节展开。

5.2 负载均衡与结果评估

负载均衡（load balance）保证各块实体数目相当，使不同处理器/节点的处理时间相近、没有明显短板；最简单的手段是多次 Map-Reduce 操作重新打散、均衡分发。

结果评估分两条线：效果上用准确率（Precision）、召回率（Recall，也称覆盖率 coverage）、F 值（F-measure，通常取 F1，即二者的调和平均），把输出的对齐集合与 ground truth 逐一比对；效率上统计运行时间与复杂度，分块前后的耗时对比就是最直观的效率报告。

下面这段代码把“聚合判定 + Hash 分块 + 复杂度对比 + Canopy 粗分块”串成一个可运行的最小闭环：

# -*- coding: utf-8 -*-
"""实体相似度聚合 + 分块（Blocking）与复杂度对比，纯标准库可运行"""
import math
import random
from collections import defaultdict


# ---------- 第一步：把多个属性相似度聚合成一个实体相似度 ----------
def weighted_average(sims: list, weights: list) -> float:
    """加权平均：每一维相似度归一到 [0,1]，权重之和为 1，属于启发式聚合。"""
    return sum(s * w for s, w in zip(sims, weights))


def rule_based(sims: list, thresholds: list) -> bool:
    """手工规则：关键属性必须过硬阈值，其余属性给宽松约束，返回是否判为匹配。
    规则：第 0 维（名称）相似度必须 > thresholds[0]，且其余维都 > thresholds[1]。"""
    return sims[0] > thresholds[0] and all(s > thresholds[1] for s in sims[1:])


# 两条待判定的机构记录：[名称相似度, 地址相似度, 电话相似度]
pair_xy = [0.95, 0.88, 1.00]   # 疑似同一实体
pair_xz = [0.72, 0.30, 0.00]   # 名称有点像，但地址、电话对不上
weights = [0.5, 0.3, 0.2]
print("== 实体相似度聚合 ==")
for name, sims in [("X-Y", pair_xy), ("X-Z", pair_xz)]:
    print("记录对 %s：加权平均 = %.3f，手工规则判定 = %s"
          % (name, weighted_average(sims, weights), rule_based(sims, [0.9, 0.2])))

# ---------- 第二步：分块，把平方级比较压到块内 ----------
def block_key(name: str, n: int = 1) -> str:
    """最简单的 Hash 分块键：取规范化名称的前 n 个字符（first-n-letter）。"""
    return name.strip().lower()[:n]


records_a = ["北京大学第三医院", "北京大学人民医院", "清华大学玉泉医院", "清华大学校医院"]
records_b = ["北京大学第三医院", "北京大学第一医院", "清华大学玉泉医院", "中国人民大学医院"]
blocks_a, blocks_b = defaultdict(list), defaultdict(list)
for r in records_a:
    blocks_a[block_key(r, 2)].append(r)
for r in records_b:
    blocks_b[block_key(r, 2)].append(r)

naive_pairs = len(records_a) * len(records_b)
blocked_pairs = 0
candidate = []
for k in sorted(set(blocks_a) & set(blocks_b)):  # 排序键使候选对输出确定，便于对照
    for x in blocks_a[k]:
        for y in blocks_b[k]:
            blocked_pairs += 1
            candidate.append((x, y))
print("\n== Hash 分块（键=名称前2字）==")
for k in sorted(set(blocks_a) | set(blocks_b)):
    print("块 %r：A=%s | B=%s" % (k, blocks_a.get(k, []), blocks_b.get(k, [])))
print("无分块候选对数 = %d，分块后候选对数 = %d" % (naive_pairs, blocked_pairs))
print("候选对：", candidate)

# ---------- 第三步：大规模下的复杂度/耗时对比（复现课件数量级） ----------
def hours_str(seconds: float) -> str:
    if seconds >= 86400:
        return "%.1f 天" % (seconds / 86400)
    if seconds >= 3600:
        return "%.1f 小时" % (seconds / 3600)
    return "%.1f 分钟" % (seconds / 60)

M = N = 10 ** 6
per_cmp = 1e-6            # 单次比较约 1 微秒（按课件 11.6 天 / 16 分钟反推的量级）
no_block = M * N
K = 1000                  # 均匀切成 1000 个块
with_block = K * (M // K) * (N // K)
print("\n== 两个 10^6 规模数据集的链接耗时 ==")
print("无分块：%d 次比较，约 %s" % (no_block, hours_str(no_block * per_cmp)))
print("分 %d 块：%d 次比较，约 %s（降低 3 个数量级）"
      % (K, with_block, hours_str(with_block * per_cmp)))

# ---------- 第四步：Canopy 粗分块（双阈值 t1/t2，块之间允许重叠） ----------
def euclid(p, q):
    return math.dist(p, q)

def canopy(points, t1=3.0, t2=1.5):
    """随机选中心点：距离 < t1 的点归入该 canopy；距离 < t2 的点从候选列表移除。"""
    random.seed(42)
    pool = points[:]
    canopies = []
    while pool:
        center = random.choice(pool)
        inner = [p for p in pool if euclid(p, center) < t1]   # 宽阈值：进 canopy
        canopies.append(inner)
        pool = [p for p in pool if euclid(p, center) >= t2]   # 严阈值：确定同簇，移除
    return canopies

pts = [(0, 0), (0.5, 0.2), (1.0, 0.1), (8.0, 8.0), (8.4, 7.8), (9.0, 8.3)]
print("\n== Canopy 粗分块（t1=3.0, t2=1.5）==")
for i, c in enumerate(canopy(pts), 1):
    print("canopy %d：%s" % (i, c))

运行结果：

== 实体相似度聚合 ==
记录对 X-Y：加权平均 = 0.939，手工规则判定 = True
记录对 X-Z：加权平均 = 0.450，手工规则判定 = False

== Hash 分块（键=名称前2字）==
块 '中国'：A=[] | B=['中国人民大学医院']
块 '北京'：A=['北京大学第三医院', '北京大学人民医院'] | B=['北京大学第三医院', '北京大学第一医院']
块 '清华'：A=['清华大学玉泉医院', '清华大学校医院'] | B=['清华大学玉泉医院']
无分块候选对数 = 16，分块后候选对数 = 6
候选对： [('北京大学第三医院', '北京大学第三医院'), ('北京大学第三医院', '北京大学第一医院'), ('北京大学人民医院', '北京大学第三医院'), ('北京大学人民医院', '北京大学第一医院'), ('清华大学玉泉医院', '清华大学玉泉医院'), ('清华大学校医院', '清华大学玉泉医院')]

== 两个 10^6 规模数据集的链接耗时 ==
无分块：1000000000000 次比较，约 11.6 天
分 1000 块：1000000000 次比较，约 16.7 分钟（降低 3 个数量级）

== Canopy 粗分块（t1=3.0, t2=1.5）==
canopy 1：[(8.0, 8.0), (8.4, 7.8), (9.0, 8.3)]
canopy 2：[(0, 0), (0.5, 0.2), (1.0, 0.1)]

说明：逐字稿口述单次链接耗时为“1 毫秒”，但按课件给出的 11.6 天与 16 分钟反推，单次比较的量级应为 1 微秒（10^12 次 × 1µs ≈ 11.6 天，10^9 次 × 1µs ≈ 16.7 分钟），代码按可复现课件数字的口径取值。

📝 动手练一练

1. （手算 + 验证）不看代码，先在纸上用动态规划表手算 kitten 与 sitting 的 Levenshtein 距离（经典答案是 3），再把本节第 1 个代码块（Levenshtein/Wagner-Fisher）里的函数拿来验证；随后把替换权重 w_sub 调成 2、插入删除保持 1，观察 Wagner-Fisher 代价变成多少，并解释为什么。
2. （分块实验）修改本节第 3 个代码块（分块与复杂度对比）中 block_key 的参数 n：分别取名称前 1 字、前 2 字、前 3 字作为分块键，统计候选对数的变化，并构造一对“名称前两字不同但确实同院”的记录（例如带曾用名的机构），观察它被分到不同块后召回是怎么丢掉的，思考 SimHash 这类模糊哈希能如何补救。
3. （数据预处理）两家图书馆书目库里，同一本书被录成了两种样子：A 馆《深入理解计算机系统（第三版）》、出版日期 2016-11-01；B 馆 深入理解计算机系统(第3版)、出版日期 2016/11/1。若直接拿书名去算编辑距离，《》、全角括号（）都会被当成真实字符白白拉开距离，日期格式也对不上。请写两个规范化函数 norm_title 与 norm_date：去掉书名号《》、把全角括号统一成半角、把日期分隔符统一并给月/日补零，使两条记录预处理后在书名与日期这两个键上可比。再想一步：“第三版”与“第3版”这种汉字数字与阿拉伯数字的差异，光靠清理符号解决不了，该回到正文预处理的哪一招？

import re


def norm_title(t: str) -> str:
    t = t.replace("《", "").replace("》", "")        # 去书名号
    t = t.replace("（", "(").replace("）", ")")       # 全角括号统一为半角
    return re.sub(r"\s+", "", t)                    # 去掉多余空白


def norm_date(d: str) -> str:
    d = d.strip().replace("/", "-")                 # 日期分隔符统一
    p = d.split("-")
    if len(p) == 3:
        return "%s-%02d-%02d" % (p[0], int(p[1]), int(p[2]))  # 月、日补零
    return d


a, b = norm_title("《深入理解计算机系统（第三版）》"), norm_title("深入理解计算机系统(第3版)")
print(a, b, a == b)                  # 符号差异已消除；第三版 vs 第3版仍不相等
print(norm_date("2016/11/1"), norm_date("2016-11-01"))  # 均为 2016-11-01

本章小结

本节把知识融合的基本技术流程完整走了一遍：

1. 两条路线、五个环节：本体对齐（概念层）与实体匹配（数据层）流程同构、可分可合；本节按课件讲授顺序回顾为预处理 → 匹配计算（记录链接）→ 分块 → 负载均衡 → 结果评估（课件先讲预处理与记录链接的匹配算子，再把分块作为规模问题后置展开）。
2. 预处理是地基：语法正规化（电话、日期、email 格式合法性）与数据正规化（去符号、纠错、正式名替换别称缩写），对应数据仓库的 ETL 与数据分析中的 EDA，耗时但必要。
3. 记录链接两步走：属性相似度三大类算子——编辑距离（Levenshtein 动态规划、Wagner-Fisher 加权、仿射间隙）、集合系数（Dice、Jaccard，配合 n-gram 切分）、向量方法（TF-IDF + 余弦）；实体相似度三条路线——聚合（加权平均/手工规则/分类器，注意训练集生成与不平衡二分类难题，半监督≠远程监督）、聚类（层次聚类的 SL/CL/AL 三种连法、相关性聚类的 NP-hard 最小代价切图、Canopy+K-means 双阈值粗分块）、知识表示学习（TransE 的 l_h+l_r≈l_t、以预链接 sameAs 为桥梁联合嵌入同一空间、最近邻搜索完成链接）。
4. 分块决定能不能跑：O(|M|×|N|) 的平方级比较经 Hash 分块（首字/n-gram/SimHash/MinHash）或邻近分块（Canopy、Sorted Neighborhood、Red-Blue Set Cover）压到块内，百万级双库从 10^12 次比较降到 10^9；负载均衡靠多轮 Map-Reduce 消除短板。
5. 评估两条线：效果看 Precision/Recall/F1（对 ground truth），效率看运行时间与复杂度。

📋 行动清单

• 能默画知识融合五步流水线，并说清本体对齐与实体匹配在哪一层、为什么能互相影响
• 能手写 Levenshtein 的动态规划递推式，并用 Python 复现 Lvensshtain → Levenshtein 距离为 3
• 能说清 Dice 与 Jaccard 的公式差异，会用 bigram 把字符串转成集合再算相似度
• 能推导 TF-IDF 算例（30/1000 × log10(50000/20001) ≈ 0.012），并解释停用词为什么 IDF 低
• 能对比加权平均、手工规则、分类器三种聚合方式的适用前提，复述训练集生成与类别不平衡难题
• 能区分层次聚类的 Single/Complete/Average Linkage，讲清 Canopy 双阈值 t1/t2 的执行流程
• 能用 TransE 的“主语+谓语≈宾语”解释跨库实体嵌入对齐的原理与预链接实体对的桥梁作用
• 能手算分块前后的候选对数量级（10^12 → 10^9），并列举至少两种分块方法
• 记住最终评估口径：Precision / Recall / F1 + 运行时间，下一节带着这套流程去认识 Falcon-AO、Dedupe、LIMES、Silk 等工具

—— 小象教研组