从多个地方采集数据,或者从同一个地方多次采集,重复项就随之而来。同一款产品会以三个略有不同的名称出现在三个市场平台上。同一家公司在一个注册库中是”Acme Widgets Ltd”,在另一个注册库中是”ACME WIDGETS LIMITED”。同一条列表出现两次,可能是因为你在爬取时分页发生了偏移,也可能是因为一个链接带有跟踪参数而另一个没有。
如果放任不管,重复项会虚增计数、把历史记录拆分到不同条目中,并在悄无声息中破坏建立在其之上的每一个指标。本指南将介绍如何解决这些问题:规范化标识符、优先按强键匹配、在大规模场景下安全地进行模糊匹配、聚类,以及选择保留哪个版本的记录。
关键要点
- 大多数重复项在任何模糊匹配之前,通过规范化标识符就能被发现:规范化的URL、经过校验的产品代码,以及清理过的公司名称。
- 优先按强标识符匹配。一个有效的条形码或注册号胜过任何程度的名称相似性。
- 永远不要把每条记录都与其他所有记录逐一比较。一百万条记录大约会产生5000亿对组合;分块(blocking)可以把这个数字降到可处理的规模。
- 判断哪种错误代价更大。对某些任务来说,错误合并比漏掉重复项更糟;对另一些任务则相反。
- 保留数据来源信息。合并后的记录应仍然能追溯到它来自的每一个来源。
三种重复项
| 类型 | 示例 | 如何发现 |
|---|---|---|
| 重复采集 | 同一个URL被抓取两次,或结果分页出现重叠 | 规范化URL或来源标识符 |
| 同一实体,不同来源 | 同一款产品在三个市场平台上被分别列出 | 共享标识符,再辅以模糊匹配 |
| 近似重复内容 | 同一篇文章经过小幅编辑后被转载 | 内容相似度,详见大规模变更检测 |
本指南聚焦于前两种情况,目标是让每一个真实存在的产品、公司或列表都只对应一条记录。
第一步:规范化标识符
规范化的成本很低,却能捕获的重复项比任何精巧的匹配方法都多。
URL。 同一个页面会以多种URL形式出现。将主机名转为小写、去掉www.、移除诸如utm_*、gclid和fbclid之类的跟踪参数、对剩余的查询参数排序,并去掉结尾的斜杠。http://www.Shop.com/p/123/?utm_source=x&b=2&a=1和https://shop.com/p/123?a=1&b=2会变成同一个键。
产品代码。 全球贸易项目代码(UPC和EAN条形码背后的数字)带有一个校验位,这让你能在信任这些代码之前拒绝掉输入错误或抓取有误的代码。GS1的方法是从校验位旁边的那一位数字开始,依次以3、1、3、1……的权重加权求和,然后取凑够下一个十的倍数所需的数值。在GS1自己给出的示例中,11位数主体61414121022的校验位是0。将有效代码补齐到14位,使同一代码的13位版本和14位版本能够比较相等。
公司名称。 在比较之前先统一大小写和重音符号、去掉标点符号,并移除诸如Ltd、Limited、Inc、GmbH和SA之类的法律后缀。“Acme Widgets Ltd.”和”ACME WIDGETS LIMITED”都会变成acme widgets。如果公司有注册号或法人识别码(Legal Entity Identifier),应优先使用这些标识符而非名称;关于将公司解析为标识符的内容,详见监控你的供应商的公开信息。
第二步:优先按强键匹配
一旦标识符经过规范化,基于它们的精确匹配既快速又可靠。两条具有相同有效条形码的记录就是同一款产品。两条具有相同规范化URL的记录就是同一个页面。两家具有相同注册号的公司就是同一家公司,不管它们的名称叫什么。
结构化数据在这里也很有帮助。许多产品页面会在JSON-LD中发布条形码和SKU,这比从可见页面中抓取要可靠得多;参见停止解析HTML。
第三步:模糊匹配,但仅限于分块内部
没有共享标识符的记录需要在名称、地址或描述上进行模糊匹配。这里的陷阱在于规模。将每条记录与其他所有记录比较,其增长速度是数据集规模的平方:一百万条记录会产生大约5000亿对组合。
分块(blocking)能解决这个问题。按照一个成本低廉、真正匹配的记录几乎总会共享的键对记录分组,比如国家加上规范化名称的第一个单词,或者品牌加产品类别,然后只在每个分组内部进行比较。一个好的分块键能把比较次数降低几个数量级,同时只损失很少的真实匹配。可以时不时地跨分块抽样比较一些记录对,来检查它究竟漏掉了什么。
在一个分块内部,由字符串相似度得分和一个阈值来决定是否匹配。一开始设得严格一些,大约0.9,只有在审查过更宽松的设置会合并哪些内容之后,才放宽阈值。
第四步:谨慎地聚类
匹配是成对的;实体是群组。并查集(union-find)结构能高效地把配对转化为聚类。但它也带来一个风险:传递性。如果A与B匹配,B与C匹配,那么即使A和C毫无共同之处,它们最终也会被归到一起。一长串弱匹配正是两家不同公司被合并的原因。留意异常庞大的聚类,并在接受之前先审查它们。
整个流程可以放进一个小模块里:
import re
import unicodedata
from collections import defaultdict
from difflib import SequenceMatcher
from urllib.parse import urlsplit, urlunsplit, parse_qsl, urlencode
LEGAL_SUFFIXES = {"ltd", "limited", "inc", "incorporated", "llc", "gmbh", "ag", "sa", "sas",
"srl", "bv", "nv", "plc", "co", "corp", "corporation", "company", "oy", "ab"}
TRACKING = re.compile(r"^(utm_|gclid$|fbclid$|mc_|ref$|ref_)")
def gtin_valid(code):
"""GS1 check digit: weights 3,1,3,... from the digit next to the check digit."""
digits = re.sub(r"\D", "", str(code or ""))
if len(digits) not in (8, 12, 13, 14):
return False
body, check = digits[:-1], int(digits[-1])
total = sum(int(d) * (3 if i % 2 == 0 else 1) for i, d in enumerate(reversed(body)))
return (10 - total % 10) % 10 == check
def norm_name(name):
text = unicodedata.normalize("NFKD", name or "").encode("ascii", "ignore").decode().lower()
tokens = [t for t in re.findall(r"[a-z0-9]+", text) if t not in LEGAL_SUFFIXES]
return " ".join(tokens)
def norm_url(url):
parts = urlsplit((url or "").strip())
query = urlencode(sorted((k, v) for k, v in parse_qsl(parts.query) if not TRACKING.match(k.lower())))
host = parts.netloc.lower().removeprefix("www.")
return urlunsplit(("https", host, parts.path.rstrip("/") or "/", query, ""))
def similar(a, b):
return SequenceMatcher(None, a, b).ratio()
def cluster(records, threshold=0.9):
"""Group records that refer to the same entity. Returns lists of record indexes."""
parent = list(range(len(records)))
def find(i):
while parent[i] != i:
parent[i] = parent[parent[i]]
i = parent[i]
return i
def union(i, j):
parent[find(i)] = find(j)
# 1. Exact matches on strong identifiers.
by_key = defaultdict(list)
for i, r in enumerate(records):
if gtin_valid(r.get("gtin")):
by_key["gtin:" + re.sub(r"\D", "", r["gtin"]).zfill(14)].append(i)
if r.get("url"):
by_key["url:" + norm_url(r["url"])].append(i)
for ids in by_key.values():
for j in ids[1:]:
union(ids[0], j)
# 2. Fuzzy name match, only within a cheap blocking key.
blocks = defaultdict(list)
for i, r in enumerate(records):
name = norm_name(r.get("name"))
if name:
blocks[(r.get("country") or "", name.split()[0])].append((i, name))
for members in blocks.values():
for a in range(len(members)):
for b in range(a + 1, len(members)):
if similar(members[a][1], members[b][1]) >= threshold:
union(members[a][0], members[b][0])
groups = defaultdict(list)
for i in range(len(records)):
groups[find(i)].append(i)
return list(groups.values())在一个小型测试集上,它会合并”Acme Widgets Ltd”、“ACME WIDGETS LIMITED”以及第三条共享该公司规范化URL的记录,合并两条条形码仅相差一个前导零的鞋类列表,并刻意把美国的”Acme Widget Co”保留为独立实体,因为分块键中包含了国家信息。最后这个决定是否正确,取决于你的数据,而这正是下一步要解决的问题。
第五步:决定保留哪条记录
一个聚类是同一实体的多个版本,而你需要的是一个。常见的存留规则(survivorship rules)有:
- 最完整的胜出,逐字段判断:对每个字段,选取来源最可靠的非空值,而不是整条记录中的某一个。
- 最新的胜出,适用于会变化的值,比如价格和库存情况。
- 最可信来源的胜出,适用于官方名称和地址这类值,比如注册库的数据优先于目录网站的数据。
无论你选择哪种规则,都要在合并后的记录上保留每一个来源标识符和URL,以及每次观测的时间。当某次合并被证明是错误的时候,来源信息正是让你能够重新拆分它的依据。
衡量准确率和召回率
实体解析有两类错误,而哪一类更重要取决于具体任务。
| 错误 | 发生的情况 | 对哪类任务最不利 |
|---|---|---|
| 错误合并 | 两个真实实体被合并为一个 | 公司和涉及个人的数据、合规事务,以及任何法律相关事项 |
| 漏掉重复项 | 一个实体仍以多条记录的形式存在 | 计数、市场规模估算、价格比较 |
手动标注几百对候选记录,同时衡量这两种错误率,并针对你最关心的错误来调整阈值和分块键。像构建B2B潜在客户数据库中的B2B潜在客户数据库,通常对漏掉重复项的容忍度要远高于错误地把两家公司合并。而像实时竞品价格信息流这样的价格比较信息流则恰恰相反:漏掉一个重复项意味着一款产品会以两个价格出现两次。
尽早在源头去重
重复项在损害准确性之前,先损害的是成本。对同一个规范化URL的每一次重复抓取,都是白白花费的带宽或额度,这就是为什么URL规范化应该在爬虫的待抓取队列(frontier)中完成,而不仅仅是在数据仓库中完成。这对单位成本的影响,详见每条干净记录的成本。
结论
去重工作大部分是规范化。规范化的URL、经过校验的产品代码和清理过的公司名称,能在任何模糊匹配运行之前捕获大部分重复项。在此之后,优先按强键匹配,只在分块内部进行模糊匹配,聚类时留意长链条,在每条合并记录上保留来源信息,并衡量对你的应用场景真正重要的那类错误。
做得好,一个真实存在的事物就会变成一条记录,并附带完整的历史信息。做得不好,数据集看起来更大,但同时也更不可信。