课程大纲 第 130 课,共 156 课 · 跟踪人,而不是设备
跟踪人,而不是设备

跨设备匹配

为什么重要 你可能在公交车上用手机,在单位用笔记本电脑,在沙发上用平板电脑,每一台都有自己的 Cookie。广告公司非常希望知道它们都属于同一个人。这个实验展示它们使用的线索、这些线索多常出错,以及哪一条线索是迄今为止最强的:登录。

把点连起来

想象一位侦探有三本独立的笔记本,每台设备一本。每本笔记本都列出了这台设备在哪里上网、以及什么时候上网。侦探的任务是判断哪几本笔记本属于同一个人。没有人告诉他们;他们根据重叠的地方来猜。

跨设备匹配:判断几台设备属于同一个人。确定性匹配使用确凿的联系,比如两台设备上登录了同一个账号。概率性匹配使用可能的联系,比如同一个家庭网络或同样的使用时段,并接受一些错误。

IP 地址:一台设备的流量所来自的网络地址。一台家用路由器后面的每台设备通常都共享这户人家的地址,而移动网络上的许多部手机也可能共享同一个地址。

三条线索

  • 共用的登录:两台设备上的同一个账号。非常强。
  • 共用的 IP 地址:暗示是同一户人家、同一间办公室或同一个移动网络,不一定是同一个人。
  • 相似的时段:两台设备在一天中相同的时间活跃。

我们的练习家庭来自 synthetic_households(),它返回一个事件列表以及答案。每个事件是 {"device": "phone-004", "ip": "203.0.113.7", "hour": 21, "login": "acct-1f2e3d"},当没有人登录时为 "login": None。这些地址来自专门留作文档用途的地址段,从不在真实的互联网上使用。

集合让重叠变得简单

Python 的集合是一袋互不相同的值,空集合写作 set()。s.add(x) 把一个值放进去。a & b 给出两个集合中都有的值,a | b 给出任意一个集合中有的值。在 if 里,空集合算作假:

a = {9, 21, 22}
b = {8, 21, 22, 23}
print(a & b)                    # {21, 22}
print(len(a & b) / len(a | b))  # 2 / 5 = 0.4, the share of hours in common
if a & b:
    print("they overlap")

打分与评判

你将给每一对设备打一个分:共用登录得 3 分,共用 IP 得 1 分,再加上共同时段所占的比例(0 到 1)。达到或超过某个阈值的设备对,算作“同一个人”。然后你要测量两样东西:

精确率:在你声称的设备对中,正确的所占的比例。召回率:在真正的设备对中,你找到的所占的比例。一个谨慎的匹配器精确率高;一个贪心的匹配器召回率高。

用其他语言实现

用 JavaScript 求集合的重叠(JavaScript 没有用于集合的 & 运算符;较新的引擎加入了 intersection() 方法,而过滤的写法在任何地方都有效):

const both = [...a.logins].some(x => b.logins.has(x));
const common = [...a.hours].filter(h => b.hours.has(h)).length;
const either = new Set([...a.hours, ...b.hours]).size;
const score = (both ? 3 : 0) + (either ? common / either : 0);

以及用 C#:

var common = a.Hours.Intersect(b.Hours).Count();
var either = a.Hours.Union(b.Hours).Count();
double score = (a.Logins.Overlaps(b.Logins) ? 3 : 0) + (either > 0 ? (double)common / either : 0);

你应该会看到什么

在阈值 1.0 时,仅凭一个共用的地址就够了,于是精确率崩溃了:室友、同事以及同一个移动网络上的陌生人都被合并在了一起。在 1.5 时,匹配器大约十次里对七次,并能找到大约十分之七的真正设备对。在 3.0 时,只有登录才算数:几乎每一次声称都是对的,但大多数真正的设备对都被漏掉了。登录,就是交出了那一条几乎确定的线索。

防御

在你不需要账号的地方保持未登录,并在你希望分开的设备上使用不同的账号(或者不用账号)。VPN 会改变 IP 这条线索,但改变不了登录或时段。这个模块的最后一课会把这些放在一起讲。

回顾

  • 设备通过登录(几乎确定)、共用的 IP 地址和相似的时段(两者都是猜测)被拼接起来。
  • 共用的地址拼接的是家庭和网络,而不是人,所以它们会产生许多错误的匹配。
  • 精确率和召回率展示了谨慎匹配和贪心匹配之间的权衡。
  • 登录是你交出的最强的线索。
轮到你了

编写四个函数。summarise(events) 返回一个字典,把每台设备映射到 {"ips": set, "hours": set, "logins": set},登录中不包括 None。pair_score(a, b) 接收两份这样的汇总,如果它们的登录集合有共同的值就返回 3,如果它们的 IP 集合有共同的值再加 1,再加上两者都有的时段数除以任意一方有的时段数(如果两者都为空就是 0)。match_devices(summaries, threshold) 返回一个由元组 (a, b) 组成的集合,其中 a < b,包含每一对分数至少为 threshold 的设备名称。precision_recall(predicted, truth) 返回一个元组 (precision, recall),当某个集合为空时使用 0。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。