Cách loại bỏ dữ liệu trùng lặp đã thu thập bằng cách phân giải thực thể

TL;DR:

• Bốn trang danh sách trả về 71 bản ghi đã giải quyết thành 66 thực thể, với 5 nhóm bản sao thực sự — những cuốn sách giống nhau xuất hiện trong cả danh sách thể loại và catalogue phân trang.
• Chuẩn hóa trước khi so sánh là điều khiến cho một khóa chính xác hoạt động: gập chữ hoa, chuẩn hóa Unicode và xóa dấu câu biến ba cách thể hiện của một tiêu đề thành một khóa.
• Chặn là đo được, không mơ hồ. 66 thực thể là 2,145 so sánh tất cả các cặp; một khóa khối bốn ký tự cắt giảm điều đó xuống còn 154 qua 48 khối, giảm 92.8%.
• Chọn người ghi điểm trước ngưỡng. Cùng một cặp tiêu đề ghi được 87.8 trên ratio và 100.0 trên token_set_ratio.
• Dải ngưỡng có thể đo được trên dữ liệu của bạn: các tiêu đề trực tiếp không liên quan đạt đỉnh 63.4 trong khi ba thể hiện của một cuốn sách ghi được 93.5 trở lên.
• Trên một catalogue sạch, các khóa chính xác đã bắt được mọi bản sao và việc so khớp mờ không tìm thấy gì trên 90 — so khớp mờ kiếm được chỗ đứng của nó qua các nguồn, không phải trong một.
• Thu thập các bản ghi đa nguồn mà điều này hòa giải với kế hoạch miễn phí Scrapeless.

Lấy dữ liệu từ một trang và các bản sao rất hiếm. Lấy dữ liệu từ cùng một catalogue thông qua một danh sách thể loại và một chỉ số phân trang, hoặc cùng một sản phẩm từ hai nhà bán lẻ, và các bản sao xuất hiện theo cấu trúc — quá trình thu thập đã truy cập cùng một mục theo hai con đường và không có cách nào để biết.

Giải quyết thực thể là bước chuyển những bản ghi đó trở lại thành các thứ. Nó chạy sau khi trích xuất và trước khi lưu trữ, và chủ yếu là một chuỗi các quyết định rẻ tiền: cái gì được coi là cùng một chuỗi, cái gì được coi là cùng một bản ghi, và phiên bản nào tồn tại.

Mọi con số dưới đây đều đến từ một bộ sưu tập 71 bản ghi được lấy từ bốn trang danh sách trực tiếp.

Pipeline at a Glance

Dòng chảy là chuẩn hóa → khóa chính xác → khối → so sánh mờ → hợp nhất. Mỗi giai đoạn rẻ hơn giai đoạn sau, vì vậy mỗi giai đoạn đều tồn tại để giảm bớt công việc mà giai đoạn tiếp theo phải làm.

Giai đoạn 1: Chuẩn hóa trước khi so sánh

Hai bản ghi mô tả cùng một sản phẩm hiếm khi mang các chuỗi byte giống hệt nhau. Chữ hoa, dấu nhấn và dấu câu đều có thể thay đổi.

import re
import unicodedata

def norm(text):
    text = unicodedata.normalize("NFKD", text or "").casefold()
    text = re.sub(r"[^a-z0-9 ]+", " ", text)
    return re.sub(r"\s+", " ", text).strip()

Lần NFKD quan trọng hơn vẻ bề ngoài của nó. Tài liệu bổ sung chuẩn hóa Unicode định nghĩa một số hình thức, và một phân giải tương thích là điều làm cho một é đã được tạo trước và một e trống cộng với dấu nhấn so sánh với nhau — hai cách đánh vần này thì giống hệt nhau về mặt hình ảnh nhưng khác nhau về byte, chính xác là trường hợp dẫn đến một bản sao mà không ai có thể thấy trong đầu ra.

Gập chữ hoa thay vì chuyển thành chữ thường là đối tác trong việc so sánh, và ghi chú mô hình ký tự W3C về chuẩn hóa là tài liệu tham khảo lý do tại sao hai cái khác nhau đối với văn bản không phải ASCII.

Trên các bản ghi đã thu thập:

[1] collected 71 records from 4 listing pages
    raw distinct titles        66
    normalised distinct titles 66

Giống hệt ở đây, vì catalogue này thì sạch. Điều đó đáng để biết hơn là giả định — thực hiện so sánh cho bạn thấy liệu việc chuẩn hóa có đang làm bất kỳ công việc nào trên dữ liệu của bạn trước khi bạn xây dựng bất cứ điều gì trên đó.

Giai đoạn 2: Nhóm theo một khóa chính xác

Với một khóa đã chuẩn hóa, lần đầu tiên là một nhóm, không phải một sự so sánh. Điều này là O(n) và nó bắt được mọi bản sao đồng ý chính xác.

from collections import defaultdict

by_key = defaultdict(list)
for record in records:
    by_key[norm(record["title"])].append(record)

dupe_groups = {k: v for k, v in by_key.items() if len(v) > 1}

[2] exact-key duplicates: 5 group(s), 10 records collapse to 5
    Sharp Objects                        x2  ['mystery', 'catalogue1']
    In a Dark, Dark Wood                 x2  ['mystery', 'catalogue2']
    In Her Wake                          x2  ['catalogue2', 'thriller']
    The Elephant Tree                    x2  ['catalogue2', 'thriller']
    Behind Closed Doors                  x2  ['catalogue2', 'thriller']

Lưu ý nơi các bản sao đến từ: mỗi nhóm trải dài trên hai trang danh sách khác nhau. Không có trang đơn nào chứa một bản sao. Đó là hình dạng chung — các bản sao là thuộc tính của quá trình thu thập, không phải của trang, vì vậy một trình thu thập chỉ đọc một danh sách sẽ không thấy chúng và một trình thu thập đọc bốn sẽ thấy.

Sử dụng một định danh ổn định làm khóa bất cứ khi nào trang công bố một cái. Một ID sản phẩm, một ISBN hoặc một đường dẫn URL chuẩn sẽ vượt trội hơn một tiêu đề, bởi vì tiêu đề là bản sao tiếp thị và thay đổi mà không cần sản phẩm thay đổi. Các hệ thống định danh đã công bố tồn tại chính xác để các bên độc lập có thể đồng ý về danh tính — đặc tả tên miền ISBN URN là ví dụ trong thế giới sách, và một trang được thu thập mà xuất hiện một cái đã giải quyết vấn đề so sánh cho bạn rồi.

Giai đoạn 3: Chặn trước khi so sánh các cặp

So sánh mờ là theo cặp, và theo cặp thì là bậc hai. Đối với 66 thực thể thì có 2,145 so sánh; đối với 10,000 thì chỉ kém 50 triệu một chút.

Chặn lại cắt bỏ lĩnh vực bằng cách chỉ so sánh các bản ghi đã chia sẻ một điều gì đó giá rẻ:

blocks = defaultdict(list)
for entity in merged:
    blocks[norm(entity["title"])[:4]].append(entity)

blocked_pairs = sum(len(b) * (len(b) - 1) // 2 for b in blocks.values())

[4] 66 entities
    all-pairs comparisons  2145
    blocked on 4-char key  154 across 48 blocks
    reduction              92.8%

Thỏa thuận là rõ ràng: một bản ghi có tiêu đề bắt đầu khác nhau sẽ không bao giờ được so sánh, vì vậy một khóa chặn quá tích cực sẽ che giấu các kết quả thực. Chặn theo bốn ký tự đầu tiên bỏ lỡ một cặp như The Elephant Tree so với Elephant Tree vì bài viết đã di chuyển. Các câu trả lời phổ biến là chặn theo một tiền tố khóa đã được sắp xếp, theo một định danh số, hoặc theo nhiều khóa cùng lúc và lấy hợp nhất của các cặp ứng viên.

Giai đoạn 4: So sánh mờ, và khi nào không cần thiết

Chạy phép so sánh mờ trên danh mục này đã tạo ra một kết quả đáng báo cáo một cách trung thực:

[5] fuzzy near-duplicates above 90 (token_sort_ratio)
    brute force 2145 pairs in 2.5 ms -> 0 candidate(s)

Không có gì. Sau khi chuẩn hóa và nhóm chính xác, một danh mục sạch đã không còn bản sao gần nào. Một phép so sánh mờ ở đây sẽ là mã mà không bao giờ kích hoạt.

So sánh mờ có vị trí của nó khi các bản ghi đến từ các nguồn định dạng tiêu đề khác nhau. Lấy một tiêu đề thực sự và thể hiện nó theo cách mà ba danh sách khác nhau sẽ lưu giữ:

from rapidfuzz import fuzz

VARIANTS = [
    "A Study in Scarlet (Sherlock Holmes #1)",
    "A Study In Scarlet - Sherlock Holmes Book 1",
    "A Study in Scarlet, Sherlock Holmes #1 [Paperback]",
]
keys = [norm(v) for v in VARIANTS]
print("distinct exact keys:", len(set(keys)))
for i in range(len(keys)):
    for j in range(i + 1, len(keys)):
        print(f"ratio {fuzz.ratio(keys[i], keys[j]):5.1f} | "
              f"token_sort {fuzz.token_sort_ratio(keys[i], keys[j]):5.1f} | "
              f"token_set {fuzz.token_set_ratio(keys[i], keys[j]):5.1f}")

distinct exact keys: 3
ratio  93.5 | token_sort  93.5 | token_set 100.0
ratio  87.8 | token_sort  87.8 | token_set 100.0
ratio  85.1 | token_sort  82.8 | token_set  93.5

Ba khóa cho một cuốn sách — giai đoạn khóa chính xác không thể giúp ở đây. Và điểm số thay đổi câu trả lời nhiều hơn ngưỡng. ratio so sánh các chuỗi như các chuỗi liên tiếp và bị kéo xuống bởi phần hậu tố [Paperback]; token_set_ratio so sánh các tập hợp các token, vì vậy các từ thêm vào không tốn gì và hai biến thể đầu tiên điểm được 100 sạch.

Hoà giải các bản ghi từ nhiều nguồn? Kế hoạch Scrapeless miễn phí bao phủ đủ yêu cầu để thu thập danh mục thứ hai khiến các bản sao xuất hiện.

Chọn Ngưỡng Từ Dữ Liệu Của Bạn

Một ngưỡng chỉ có thể được bảo vệ nếu có sự tách biệt đo lường. Hai con số giới hạn nó ở đây:

Bất cứ điều gì nằm giữa hai số đó tách biệt các tập hợp một cách rõ ràng trên dữ liệu này. Phương pháp tổng quát: điểm một mẫu các trận đấu đã biết và một mẫu các không phải là trận đấu, xem xét nơi mà các phân phối ngừng chồng lấn, và đặt ngưỡng ở khoảng trống. Một số toàn cầu duy nhất sao chép từ một bài viết là một suy đoán về dữ liệu của người khác.

Nơi mà các phân phối chồng lấn, câu trả lời trung thực là một băng đánh giá — tự động hợp nhất ở trên giới hạn trên, tự động từ chối ở dưới giới hạn dưới, và xếp hàng những gì nằm giữa chúng. Liên kết bản ghi thống kê đã giải quyết vấn đề này theo cách này trong nhiều thập kỷ, và nghiên cứu liên kết bản ghi của Cục Điều tra Dân số Hoa Kỳ là tài liệu tham khảo tiêu chuẩn cho khung xác suất.

Giai đoạn 5: Tồn tại

Quyết định rằng hai bản ghi là giống nhau để lại câu hỏi về điều gì mà bản ghi hợp nhất nói. Loại bỏ kẻ thua cuộc một cách lặng lẽ ném bỏ bằng chứng rằng sự khớp đã xảy ra.

def survivor(group):
    best = sorted(group, key=lambda r: (r["href"] is None, len(r["href"] or "")))[0]
    return {**best,
            "seen_in": sorted({g["source"] for g in group}),
            "prices": sorted({g["price"] for g in group})}

[3] 71 records -> 66 entities
    merged example: 'Sharp Objects' seen_in=['catalogue1', 'mystery'] prices=['£47.82']

Hai thuộc tính của bản ghi hợp nhất đó là quan trọng. seen_in giữ lại nguồn gốc, vì vậy một hợp nhất sai có thể được truy tìm sau này thay vì vô hình. Và prices là một tập hợp thay vì một giá trị đơn: khi hai nguồn không đồng ý, sự không đồng ý là điều thú vị, và gộp nó lại với bất kỳ bản ghi nào xảy ra trước sẽ phá hủy nó.

Các quy tắc cấp trường đánh bại một người thắng toàn bộ bản ghi. Mô tả dài nhất, dấu thời gian gần nhất, bản ghi đầy đủ nhất, nguồn có độ tin cậy cao nhất — được chọn theo từng trường thay vì từng bản ghi — là điều giúp một hợp nhất không thừa hưởng khoảng trống của một nguồn.

Nơi Điều Này Ngồi Trong Một Quy Trình

Xóa trùng thuộc về bước biến đổi, sau khi trích xuất và trước khi ghi. Chạy nó sớm hơn có nghĩa là chuẩn hóa các chuỗi mà bạn chưa phân tích; chạy nó muộn hơn có nghĩa là các bản sao đã có trong bảng và việc sửa trở thành một việc di dời.
Thu thập các sản phẩm giống nhau từ nhiều nguồn chính là điều làm cho giai đoạn này trở nên cần thiết ngay từ ban đầu — pipeline giá cả cạnh tranh có hình dạng chính xác như vậy, và Universal Scraping API là thứ giữ cho hình dạng bản ghi nhất quán khi một trong những nguồn đó được hiển thị phía khách hàng. Giá cả liệt kê chi phí của các nguồn bổ sung.

Kết luận

Giải quyết thực thể có bốn giai đoạn rẻ trước một giai đoạn đắt. Chuẩn hóa quyết định cái gì được coi là cùng một chuỗi, nhóm chính xác sẽ bắt tất cả những gì đồng ý — 5 nhóm và 10 bản ghi ở đây — chặn loại bỏ 92.8% các cặp mà không ai cần so sánh, và chỉ những gì tồn tại sau đó mới đến tay người đánh giá mờ.

Hai phát hiện đáng để mang vào dữ liệu của riêng bạn. Điểm số quan trọng hơn ngưỡng: 87.8 so với 100.0 trên cùng một cặp. Và đo lường sự tách biệt trước khi chọn một con số, vì khoảng cách 63.4 đến 93.5 đã làm cho sự lựa chọn trở nên rõ ràng ở đây là một đặc điểm của danh mục này, chứ không phải là một hằng số.

Sẵn sàng để hòa giải các bản ghi từ hơn một nguồn? Bắt đầu với kế hoạch miễn phí của Scrapeless và thu thập danh mục thứ hai khiến cho các bản sao trở nên rõ ràng.

Câu hỏi thường gặp

Q: Làm thế nào để tôi xoá các bản sao từ dữ liệu được thu thập?

Chuẩn hóa trường khóa, nhóm vào nó, sau đó gộp từng nhóm lại. Gập trường hợp, chuẩn hóa Unicode NFKD và loại bỏ dấu câu biến các chuỗi giống hệt về mặt hình thức thành một khóa, và việc nhóm là O(n) hơn là theo từng cặp. Trong 71 bản ghi ở trên đã gộp 10 bản ghi thành 5 thực thể mà không cần bất kỳ điểm số tương đồng nào. Chỉ sử dụng việc so khớp mờ cho những gì tồn tại sau khi vượt qua.

Q: Giải quyết thực thể là gì?

Quyết định bản ghi nào tham chiếu đến cùng một đại diện thực tế và hợp nhất chúng thành một bản ghi chuẩn mực. Loại bỏ bản sao là cùng một hoạt động trong một nguồn duy nhất; thuật ngữ này thường dành riêng cho trường hợp khó hơn giữa các nguồn, nơi không có mã định danh chung tồn tại và quyết định phải được đưa ra từ độ tương đồng của các trường.

Q: Chặn là gì và tại sao nó quan trọng?

Chỉ so sánh các bản ghi đã chia sẻ một khóa rẻ, vì vậy giai đoạn theo từng cặp không chạy trên tất cả mọi thứ. 66 thực thể là 2,145 cặp khả thi; một khóa tiền tố bốn ký tự đã cắt giảm con số đó xuống còn 154, giảm 92.8%. Chi phí là các bản ghi mà khóa của chúng khác nhau sẽ không bao giờ được so sánh, vì vậy một khóa khối quá chặt chẽ sẽ âm thầm ẩn giấu các đối số có thể phù hợp.

Q: Tôi nên sử dụng điểm số so khớp mờ nào?

token_set_ratio cho các tiêu đề thu thập thêm từ các nguồn khác nhau, vì nó so sánh các tập hợp token và bỏ qua các phần thừa — nó đạt điểm 100.0 trong khi ratio chỉ đạt 87.8 trên cùng một cặp. Sử dụng ratio khi vị trí và thứ tự mang ý nghĩa, chẳng hạn như mã hoặc địa chỉ. Kiểm tra cả hai trên các đối số đã biết từ dữ liệu của bạn trước khi chọn.

Q: Ngưỡng độ tương đồng nào tôi nên đặt?

Đo lường nó thay vì sao chép nó. Chấm điểm một mẫu của các đối số đã biết và các không phải đối số và đặt ngưỡng ở nơi các phân phối ngừng chồng chéo. Ở đây, điểm số cao nhất giữa các cuốn sách khác nhau là 63.4 và điểm số thấp nhất trong các bản hiển thị của một cuốn sách là 93.5, vì vậy bất kỳ điều gì trong dải đó đều hiệu quả. Nơi hai thứ chồng chéo, tự động gộp ở trên, tự động loại bỏ ở dưới, và xếp hàng ở giữa để xem xét.

Q: Bản ghi nào nên tồn tại sau khi gộp?

Chọn theo từng trường, không theo từng bản ghi. Lấy mô tả dài nhất, giá gần đây nhất, địa chỉ đầy đủ nhất, và giữ nguyên nguồn gốc — thực thể đã gộp ở trên giữ seen_in và toàn bộ bộ giá cả quan sát được. Giữ danh sách nguồn giúp cho việc gộp xấu có thể truy vết; giữ mỗi giá cả quan sát được bảo tồn sự không đồng nhất giữa các nguồn, điều này thường là tín hiệu mà bạn muốn.