Tôi làm cách nào để xây dựng thuật toán phù hợp?

Question

Tôi chưa bao giờ xây dựng một thuật toán cho phù hợp trước đây và không thực sự biết bắt đầu từ đâu. Vì vậy, đây là thiết lập cơ bản của tôi và tại sao tôi làm điều đó. Vui lòng sửa tôi nếu tôi không hỏi đúng câu hỏi.

Tôi có cơ sở dữ liệu về tên và số nhận dạng duy nhất cho mọi người. Một số số nhận dạng được tạo (được tạo bên trong và một số bên thứ ba), họ, tên và ngày sinh là những số nhận dạng chính mà tôi sẽ sử dụng.

Một vài lần trong năm tôi nhận được danh sách từ bên thứ ba cần được nhập và gắn với những người hiện có trong cơ sở dữ liệu của tôi nhưng dữ liệu không bao giờ sạch sẽ như tôi. ID có thể thay đổi, ngày sinh có thể có lỗi chính tả, tên có thể có lỗi chính tả, tên cuối cùng có thể thay đổi, v.v.

Mỗi lần nhập có thể có 20.000 bản ghi, ngay cả khi chính xác 99% vẫn là 200 bản ghi mà tôi phải vào thủ công và khớp. Tôi nghĩ rằng tôi đang tìm kiếm chính xác hơn 99,9% khi nói đến việc kết hợp những người đến với người dùng của tôi.

Vì vậy, làm cách nào để tôi thực hiện thuật toán có thể tìm ra điều này?

PS Ngay cả khi bạn không có câu trả lời chính xác nhưng biết một số tài liệu cần tham khảo cũng sẽ hữu ích.

PPS Một số ví dụ sẽ là tương tự như những gì m3rLinEz đã viết:

ID: 9876234 Fname: Jose  LName: Guitierrez  Birthdate:01/20/84 '- Original' 

ID: 9876234 Fname: Jose  LName: Guitierrez  Birthdate:10/20/84 '- Typo in birth date' 
ID: 0876234 Fname: Jose  LName: Guitierrez  Birthdate:01/20/84 '- Wrong ID' 
ID: 9876234 Fname: Jose  LName: Guitierrez-Brown Birthdate:01/20/84 '- Hyphenated last name' 
ID: 9876234 Fname: Jose, A. LName: Guitierrez  Birthdate:01/20/84 '- Added middle initial' 
ID: 3453555 Fname: Joseph LName: Guitierrez  Birthdate:01/20/84 '- Probably someone else with same birthdate and same last name' 

Answer 1

Bạn có thể quan tâm đến Levenshtein distance.

Các Levenshtein khoảng cách giữa hai chuỗi được định nghĩa là số tối thiểu về những sửa đổi cần thiết để chuyển đổi một chuỗi thành khác, với chỉnh sửa hoạt động cho phép là chèn, xóa, hoặc thay của một đơn tính cách. Nó được đặt tên sau khi Vladimir Levenshtein, người coi khoảng cách này trong 1965. 1

Có thể so sánh tất cả các lĩnh vực của bạn và tính toán tổng khoảng cách. Và bằng thử và lỗi, bạn có thể khám phá ngưỡng thích hợp để cho phép các bản ghi được diễn giải là phù hợp. Chưa thực hiện điều này bản thân mình nhưng chỉ nghĩ đến ý tưởng:}

Ví dụ:

• Ghi A - ID: 4831213321, Tên: Jane
• Ghi B - ID: 431.213.321, Tên: Jann
• Ghi C - ID: 4831211021, Tên: John

khoảng cách giữa A và B sẽ thấp hơn A và C/B và C, mà chỉ ra trận đấu tốt hơn.

Answer 2

Regular expressions là những gì bạn cần, tại sao minh lại bánh xe?

Answer 3

Nếu bạn đang xử lý các tập dữ liệu có kích thước này và các tài nguyên khác nhau được nhập, bạn có thể muốn xem xét giải pháp Quản lý danh tính. Tôi hầu như quen thuộc với Sun Identity Manager, nhưng nó có thể là quá mức cần thiết cho những gì bạn đang cố gắng làm.Nó có thể đáng xem xét.

Answer 4

Nếu dữ liệu bạn nhận được từ bên thứ ba là nhất quán (cùng một định dạng mỗi lần), tôi có thể tạo bảng cho từng bên thứ ba mà bạn đang nhận dữ liệu. Sau đó, nhập từng bộ dữ liệu mới vào cùng một bảng mỗi lần. Tôi biết có một cách để sau đó tham gia hai bảng dựa trên các cột phổ biến trong mỗi bảng bằng cách sử dụng một câu lệnh SQL. Bằng cách đó bạn có thể thực hiện các truy vấn SQL và lấy dữ liệu từ nhiều bảng, nhưng làm cho nó trông giống như nó đến từ một bảng thống nhất duy nhất. Các bản ghi tương tự đã được thêm vào mà không có các kết quả phù hợp trong cả hai bảng có thể được tìm thấy và sau đó ghép nối theo cách thủ công. Bằng cách này, bạn giữ dữ liệu 'sạch' của mình tách biệt khỏi rác mà bạn nhận được từ bên thứ ba. Nếu bạn muốn nhập thực sự, bạn có thể sử dụng bảng đã nối đó để tạo bảng thứ ba chứa tất cả dữ liệu của bạn.

Answer 5

Tôi sẽ bắt đầu với gần 100% các kết quả phù hợp nhất và xử lý chúng trước tiên, vì vậy bây giờ bạn có danh sách 200 câu hỏi cần sửa.

Đối với các hàng còn lại, bạn có thể sử dụng phiên bản đơn giản của Bayes' Theorem.

Đối với mỗi hàng chưa được so khớp, hãy tính khả năng rằng nó phù hợp với mỗi hàng trong tập dữ liệu của bạn giả định rằng dữ liệu chứa một số thay đổi nhất định xảy ra với xác suất nhất định. Ví dụ, một người thay đổi họ của họ với xác suất 0,1% (có thể cũng phụ thuộc vào giới tính), thay đổi tên của họ với xác suất 0,01%, và là có một lỗi đánh máy duy nhất với khả năng sinh sản 0,2% (sử dụng Levenshtein's distance để đếm số lỗi chính tả) . Các trường khác cũng thay đổi với xác suất nhất định. Đối với mỗi hàng, tính toán mức độ phù hợp với hàng xem xét tất cả các trường đã thay đổi. Sau đó chọn một trong đó có xác suất cao nhất là một trận đấu. Ví dụ một hàng chỉ với một lỗi đánh máy nhỏ trong một trường nhưng bằng nhau trên tất cả những người khác sẽ có cơ hội 0,2%, trong khi các hàng khác nhau ở nhiều trường có thể chỉ có 0,00001% cơ hội. Vì vậy, bạn chọn hàng có lỗi đánh máy nhỏ.

Answer 6

Khi nói đến một cái gì đó như thế này, không sáng tạo lại bánh xe. Khoảng cách Levehstein có lẽ là đặt cược tốt nhất của bạn nếu bạn phải tự làm điều này, nhưng nếu không, hãy nghiên cứu một số giải pháp hiện có để thực hiện truy vấn cơ sở dữ liệu và tìm kiếm mờ. Họ đã làm nó lâu hơn bạn, nó có thể sẽ tốt hơn, quá ..

Chúc may mắn!