跨设备匹配
为什么重要 你可能在公交车上用手机,在单位用笔记本电脑,在沙发上用平板电脑,每一台都有自己的 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。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。