سرفصل‌ها درس 131 از 156 · ردیابی شخص، نه دستگاه
ردیابی شخص، نه دستگاه

گراف‌های هویت

چرا مهم است یک کارت وفاداری ایمیل شما را می‌داند. یک برنامهٔ خرید تلفنتان را می‌داند. یک شرکت تحویل نشانی‌تان را می‌داند. هیچ‌کدام به‌تنهایی تصویر کاملی نیست، اما یک دلال داده که هر سه را می‌خرد می‌تواند آن‌ها را در یک سابقه دربارهٔ شما به هم پیوند دهد. ساختن یک نسخهٔ کوچک توسط خودتان دقیقاً نشان می‌دهد کدام جزئیات مشترک پیونددادن را انجام می‌دهد، و در نتیجه به اشتراک‌گذاشتن کدام جزئیات را متوقف کنید.

تاری از نخ

تخته‌ای را با کارت‌های فهرست تصور کنید، یکی برای هر سابقه. هر وقت دو کارت یک نشانی ایمیل، یک شماره تلفن، یک شناسهٔ دستگاه یا یک نشانی خانه را مشترک داشته باشند، تکه‌ای نخ میانشان می‌بندید. وقتی تمام شد، هر کلاف کارت‌هایی که با نخ به هم پیوسته‌اند، زنجیره هر قدر هم بلند باشد، یک شخص است.

دلال داده (data broker): شرکتی که اطلاعاتی دربارهٔ آدم‌ها جمع می‌کند، می‌خرد و می‌فروشد، معمولاً آدم‌هایی که هرگز اسمش را نشنیده‌اند.

گراف هویت (identity graph): نقشهٔ یک دلال که سوابق بسیاری (ایمیل‌ها، تلفن‌ها، دستگاه‌ها، نشانی‌ها) را به یک شخص پیوند می‌دهد. در ریاضی یک گراف فقط نقطه‌هایی (اینجا، سوابق) است که با خط‌هایی (جزئیات مشترک) به هم وصل شده‌اند.

زنجیره بخش هوشمندانه است. کارت A یک ایمیل را با کارت B مشترک دارد. کارت B یک تلفن را با کارت C مشترک دارد. A و C هیچ چیز مشترکی ندارند، اما در همان کلاف قرار می‌گیرند. این راهی است که یک ثبت‌نام خبرنامه می‌تواند به یک بازی روی تلفنتان پیوند بخورد بی‌آنکه هیچ‌کدام هرگز دادهٔ دیگری را ببیند.

سوابق تمرینی

broker_records() سوابق ساختگی‌ای را از چند منبع برمی‌گرداند:

{"id": "r014", "source": "survey", "name": "Sam Smith",
 "email": "  SAM.SMITH88@MAIL.EXAMPLE ", "phone": "+44 7700 910283",
 "device": None, "address": None}

هر جزئیاتی ممکن است غایب باشد (None). ایمیل‌ها با فاصله‌ها و حروف بزرگ عجیب می‌رسند، پس باید اول یکدست شوند: با .strip() پیرایش و به حروف کوچک تبدیل شوند. شماره تلفن‌ها باید فقط رقم‌هایشان را نگه دارند، تا «+44 7700 910283» و «447700910283» جور شوند. ch.isdigit() به شما می‌گوید آیا یک نویسه رقم است.

دنبال‌کردن نخ

آن را در سه گام بسازید:

  1. نمایه: یک dict از هر جفت (field, value) به شناسه‌های سوابقی که آن را دارند. دو شناسه زیر یک کلید آن جزئیات را مشترک دارند.
  2. همسایه‌ها: برای هر شناسهٔ سابقه، مجموعهٔ شناسه‌هایی که چیزی با آن مشترک دارد.
  3. پیمایش: از سابقه‌ای که هنوز کسی بازدیدش نکرده شروع کنید، یک فهرست to_visit نگه دارید، و مدام یک شناسه از آن بردارید، دیده‌شده علامتش بزنید، و همسایه‌هایش را اضافه کنید. هر چه به آن برسید یک گروه است.
to_visit = ["r001"]
while to_visit:              # keep going while the list is not empty
    current = to_visit.pop() # take the last id off the list
    ...
در زبان‌های دیگر

دلالان و تحلیلگران اغلب به‌جای پیمایش از ساختاری به نام union-find استفاده می‌کنند. در JavaScript:

const parent = {};
// every record starts as its own group: parent[id] = id
for (const r of records) parent[r.id] = r.id;
const find = x => (parent[x] === x ? x : (parent[x] = find(parent[x])));
const union = (a, b) => { parent[find(a)] = find(b); };
// for each shared (field, value): union(firstIdWithIt, thisId)

و همین در Go:

func find(parent map[string]string, x string) string {
    for parent[x] != x {
        x = parent[x]
    }
    return x
}

یک اشتباه وسوسه‌انگیز

اسکریپت پایین بر اساس name هم پیوند می‌دهد. افت تعداد آدم‌ها را تماشا کنید: دو شخص متفاوت به نام «Sam Smith» در یکی ادغام می‌شوند. دلالان واقعی هم این نوع خطا را مرتکب می‌شوند، که یکی از دلایلی است که پرونده‌هایشان دربارهٔ آدم‌ها اغلب نادرست است. یک سابقهٔ نادرست همچنان می‌تواند فروخته شود و بر اساسش عمل شود.

دفاع

پیوندها از راه جزئیاتی رخ می‌دهند که تکرار می‌کنید. برای هر فروشگاه یا خبرنامه از یک نام مستعار ایمیل متفاوت استفاده کنید (بسیاری از سرویس‌های ایمیل این را ارائه می‌دهند)، شماره تلفن را فقط وقتی واقعاً لازم است بدهید، و از دکمه‌های «log in with» که یک حساب را به سایت‌های بسیار می‌دهند پرهیز کنید. نمی‌توانید جلوی نخ‌کشیدن یک دلال را بگیرید، اما می‌توانید کارت‌های جور کمتری به آن بدهید.

خلاصه

  • یک گراف هویت سوابقی را که هر جزئیاتی را مشترک دارند به هم پیوند می‌دهد، و زنجیره‌هایی از جزئیات مشترک سوابقی را که مستقیماً هیچ چیز مشترکی ندارند پیوند می‌دهند.
  • یکدست‌کردن (پیرایش، حروف کوچک، نگه‌داشتن رقم‌های تلفن) چیزی است که دادهٔ درهم را جور می‌کند.
  • کلیدهای ضعیفی مانند نام‌ها آدم‌های متفاوت را ادغام می‌کنند، پس پرونده‌های دلالان خطا دارند.
  • جزئیات تکراری کمتر (نام‌های مستعار، بدون تلفن، ورودهای جدا) یعنی پیوندهای کمتر.
نوبت شما

دو تابع بنویسید. normalise(field, value) برای None مقدار None را برمی‌گرداند؛ وگرنه فاصله‌ها را حذف می‌کند و مقدار را به حروف کوچک تبدیل می‌کند، وقتی field برابر "phone" است فقط رقم‌ها را نگه می‌دارد، و اگر هیچ چیز نماند None برمی‌گرداند. link_records(records, keys) فهرستی از مجموعه‌های شناسهٔ سابقه برمی‌گرداند، یک مجموعه برای هر شخص: دو سابقه وقتی در یک مجموعه‌اند که برای هر فیلدی در keys یک مقدار یکدست‌شدهٔ مشترک داشته باشند، مستقیم یا از راه زنجیره‌ای از سوابق دیگر. هر شناسهٔ سابقه دقیقاً در یک مجموعه ظاهر می‌شود.

مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید

این تمرین به‌زودی باز می‌شود

درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و می‌توانید همین الان این درس را بخوانید.