Đồ thị danh tính
Vì sao điều này quan trọng Một thẻ tích điểm biết email của bạn. Một ứng dụng mua sắm biết điện thoại của bạn. Một hãng giao hàng biết địa chỉ của bạn. Không cái nào tự nó là một bức tranh đầy đủ, nhưng một nhà môi giới dữ liệu mua cả ba có thể nối chúng thành một hồ sơ về bạn. Tự dựng một phiên bản tí hon cho thấy chính xác chi tiết dùng chung nào làm việc nối, và vì vậy chi tiết nào cần ngừng chia sẻ.
Một mạng lưới sợi dây
Hãy hình dung một bảng ghim với các thẻ ghi chú, mỗi thẻ cho một bản ghi. Mỗi khi hai thẻ có chung một địa chỉ email, một số điện thoại, một ID thiết bị hay một địa chỉ nhà, bạn buộc một sợi dây giữa chúng. Khi xong, mỗi búi thẻ được nối bằng dây, dù chuỗi dài bao nhiêu, là một người.
Nhà môi giới dữ liệu: một công ty thu thập, mua và bán thông tin về con người, thường là những người chưa bao giờ nghe tới nó.
Đồ thị danh tính: bản đồ của một nhà môi giới liên kết nhiều bản ghi (email, điện thoại, thiết bị, địa chỉ) với một người. Trong toán học một đồ thị đơn giản là các dấu chấm (ở đây là các bản ghi) được nối bằng các đường (những chi tiết dùng chung).
Chuỗi là phần thông minh. Thẻ A có chung một email với thẻ B. Thẻ B có chung một số điện thoại với thẻ C. A và C không có gì chung, vậy mà chúng rốt cuộc nằm trong cùng một búi. Đây là cách một lần đăng ký bản tin có thể bị nối với một trò chơi trên điện thoại của bạn mà không bên nào từng thấy dữ liệu của bên kia.
Các bản ghi luyện tập
broker_records() trả về các bản ghi bịa ra từ vài nguồn:
{"id": "r014", "source": "survey", "name": "Sam Smith",
"email": " SAM.SMITH88@MAIL.EXAMPLE ", "phone": "+44 7700 910283",
"device": None, "address": None}Bất kỳ chi tiết nào cũng có thể bị thiếu (None). Email tới với dấu cách và chữ hoa kỳ quặc, nên chúng phải được chuẩn hóa trước: cắt bằng .strip() và viết thường. Số điện thoại chỉ nên giữ các chữ số, để "+44 7700 910283" và "447700910283" khớp nhau. ch.isdigit() cho bạn biết một ký tự có phải là chữ số không.
Lần theo sợi dây
Dựng nó qua ba bước:
- Chỉ mục: một dict từ mỗi cặp
(field, value)tới các ID bản ghi có nó. Hai ID dưới cùng một khóa có chung chi tiết đó. - Láng giềng: với mỗi ID bản ghi, set các ID mà nó có chung bất cứ thứ gì.
- Đi bộ: bắt đầu từ một bản ghi chưa ai ghé, giữ một list
to_visit, và lặp lại việc lấy một ID ra khỏi nó, đánh dấu đã thấy, và thêm các láng giềng của nó. Mọi thứ bạn tới được là một nhóm.
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
...Trong các ngôn ngữ khác
Các nhà môi giới và nhà phân tích thường dùng một cấu trúc gọi là union-find thay vì đi bộ. Trong 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)Và tương tự trong Go:
func find(parent map[string]string, x string) string {
for parent[x] != x {
x = parent[x]
}
return x
}Một lỗi đầy cám dỗ
Script ở cuối cũng nối theo name. Hãy xem số người giảm xuống: hai người khác nhau tên "Sam Smith" bị gộp thành một. Các nhà môi giới thật cũng mắc kiểu lỗi này, đó là một lý do hồ sơ của họ về con người thường sai. Một hồ sơ sai vẫn có thể được bán và được dùng để hành động.
Cách phòng thủ
Việc nối diễn ra qua những chi tiết bạn lặp lại. Dùng một bí danh email khác cho mỗi cửa hàng hay bản tin (nhiều dịch vụ thư có cung cấp), chỉ đưa số điện thoại khi thật sự cần, và tránh các nút "đăng nhập bằng" trao một tài khoản cho nhiều trang. Bạn không ngăn được một nhà môi giới vẽ dây, nhưng bạn có thể cho nó ít thẻ khớp nhau hơn.
Tóm tắt
- Một đồ thị danh tính nối các bản ghi có chung bất kỳ chi tiết nào, và chuỗi các chi tiết dùng chung nối cả những bản ghi không có gì chung trực tiếp.
- Chuẩn hóa (cắt, viết thường, giữ chữ số điện thoại) là điều làm dữ liệu lộn xộn khớp được.
- Các khóa yếu như tên gộp những người khác nhau lại, nên hồ sơ của nhà môi giới có lỗi.
- Ít chi tiết lặp lại hơn (bí danh, không đưa điện thoại, đăng nhập riêng) nghĩa là ít lần nối hơn.
Viết hai hàm. normalise(field, value) trả về None cho None; nếu không thì nó cắt dấu cách và viết thường giá trị, chỉ giữ các chữ số khi field là "phone", và trả về None nếu không còn gì. link_records(records, keys) trả về một list các set ID bản ghi, mỗi set cho một người: hai bản ghi nằm trong cùng một set khi chúng có chung một giá trị đã chuẩn hóa ở bất kỳ trường nào trong keys, trực tiếp hoặc qua một chuỗi các bản ghi khác. Mọi ID bản ghi xuất hiện trong đúng một set.
Bạn thấy vấn đề gì trong bài học này? Hãy báo cáo nó · Hỏi về bài học này
Bài tập này sẽ sớm mở.
Hoàn thành bài học trước đó để mở khóa bài này. Toàn bộ khóa học là miễn phí, không cần tài khoản, và bạn có thể đọc bài học này ngay bây giờ.
Trình duyệt này đang chặn cookie cho learn.floati.life, nên các bài học bạn đã hoàn thành tại đây không thể mở theo thứ tự. Hãy cho phép cookie cho trang web này và tải lại trang.