Tính tương quan văn bản nhạy cảm với ngữ cảnh

Question

Giả sử tôi muốn khớp các bản ghi địa chỉ (hoặc tên người hoặc bất kỳ thứ gì) với nhau để hợp nhất các bản ghi có nhiều khả năng đề cập đến cùng một địa chỉ. Về cơ bản, tôi đoán tôi muốn tính toán một số loại tương quan giữa giá trị văn bản và hợp nhất các bản ghi nếu giá trị này vượt quá một ngưỡng nhất định.

Ví dụ: "West Lawnmower Drive 54 A" có thể giống như "W. Lawn Mower Dr. 54A" nhưng khác với "East Lawnmower Drive 54 A".

Bạn tiếp cận vấn đề này như thế nào? Nó sẽ là cần thiết để có một số loại từ điển dựa trên ngữ cảnh mà biết, trong trường hợp địa chỉ, rằng "W", "W." và "Tây" là như nhau? Điều gì về lỗi chính tả ("mover" thay vì "mower", v.v ...)?

Tôi nghĩ đây là một vấn đề phức tạp - có lẽ có một số thuật toán nổi tiếng ngoài kia?

Answer 1

Một tốt cơ sở, có lẽ là một thực tế về chi phí tính toán tương đối cao và quan trọng hơn là sản xuất của nhiều dương tính giả, sẽ là các thuật toán chuỗi khoảng cách chung chung như

• Edit distance (aka Levenshtein khoảng cách)
• Ratcliff/Obershelp

Tùy thuộc vào mức độ chính xác cần thiết (trong đó, BTW, nên được chỉ định trong cả hai các điều khoản của recall and precision của nó, tức là nói chung là bỏ lỡ mối tương quan hơn là nhận dạng sai), quy trình phát triển tại nhà dựa trên [một số] ý tưởng và ý tưởng sau có thể thực hiện thủ thuật:

• tokenize đầu vào, tức là nhìn thấy đầu vào như một mảng các từ chứ không phải là một chuỗi
• tokenization cũng nên giữ các thông tin số dòng
• chuẩn hóa đầu vào với việc sử dụng một cuốn từ điển ngắn substituions chung (chẳng hạn như "dr" ở cuối dòng = "drive", "Jack" = "John", "Bill" = "William" ..., "W." ở đầu dòng là "West", v.v.
• Xác định (giống như gắn thẻ, như trong gắn thẻ POS) bản chất của một số thực thể (ví dụ: Mã ZIP và mã ZIP mở rộng, cũng như thành phố
• Xác định (tra cứu) một số thực thể này (ví dụ: bảng cơ sở dữ liệu ngắn tương đối có thể bao gồm tất cả Thành phố/thị trấn trong khu vực được nhắm mục tiêu
• Xác định (tra cứu) một số thực thể liên quan đến miền (nếu tất cả/nhiều địa chỉ giao dịch với người nói trong ngành pháp lý, tra cứu tên công ty luật hoặc tòa nhà liên bang có thể giúp đỡ.
• Nói chung, hãy đặt trọng lượng hơn trên các thẻ đến từ dòng cuối cùng của địa chỉ
• Đặt thêm (hoặc ít hơn) trọng lượng trên thẻ với loại thực thể cụ thể (ví dụ: "Drive", "Street", "Court" nên có ít hơn nhiều so với các thẻ mà trước họ.
• Hãy xem xét một biến đổi SOUNDEX thuật toán để giúp bình thường hóa

với trên trong tâm trí, thực hiện một đánh giá dựa trên luật lệ. Dự kiến, các quy tắc có thể được triển khai như khách truy cập vào cây/ar cấu trúc giống như tia mà đầu vào được phân tích cú pháp ban đầu (Visitor design pattern).
Lợi thế của khung dựa trên quy tắc, là mỗi heuristic có chức năng riêng và các quy tắc có thể được ưu tiên, tức là đặt một số quy tắc sớm trong chuỗi, cho phép hủy bỏ đánh giá sớm, với một số chẩn đoán mạnh mẽ (ví dụ: khác nhau Thành phố => Tương quan = 0, mức độ tin cậy = 95% v.v ...).

Một điều cần chú với tìm kiếm mối tương quan là cần phải tiên so sánh tất cả các mặt hàng duy nhất (ở đây giải quyết) với tất cả các mục khác, do đó đòi hỏi càng nhiều càng 1/2 n^2 so sánh item-level. Bởi vì điều này, có thể hữu ích khi lưu trữ các mục tham chiếu theo cách chúng được xử lý trước (được phân tích cú pháp, chuẩn hóa ...) và cũng có thể có thông báo thông báo có thể được sử dụng như [rất thô] chỉ số của một mối tương quan có thể (ví dụ: một khóa được tạo từ mã ZIP gồm 5 chữ số theo sau là giá trị SOUNDEX của tên "chính").

Answer 2

Tuyên bố từ chối trách nhiệm: Tôi không biết bất kỳ thuật toán nào thực hiện điều đó, nhưng thực sự muốn biết nếu nó tồn tại. Câu trả lời này là một nỗ lực ngây thơ của việc cố gắng giải quyết vấn đề, không có kiến ​​thức trước đó. Bình luận chào mừng, xin đừng cười quá.

Nếu bạn cố gắng thực hiện bằng tay, tôi khuyên bạn nên áp dụng một số loại "bình thường" cho chuỗi của mình: viết thường, xóa dấu câu, có thể thay thế các từ viết tắt phổ biến bằng từ đầy đủ (Dr. => drive, St = > đường phố, v.v ...).

Sau đó, bạn có thể thử sắp xếp khác nhau giữa hai chuỗi bạn so sánh và tính toán tương quan bằng trung bình chênh lệch tuyệt đối giữa các chữ cái tương ứng (ví dụ a = 1, b = 2, vv .. và corr(a, b) = |a - b| = 1):

west lawnmover drive 
    w lawnmower street 

Do đó, ngay cả khi một số chữ cái khác nhau, tương quan sẽ cao. Sau đó, chỉ cần giữ mối tương quan tối đa mà bạn tìm thấy và quyết định rằng chúng tương tự nhau nếu tương quan nằm trên một ngưỡng nhất định.

Answer 3

Tôi sẽ xem xét việc tạo ra một chỉ số so sánh tương tự, với hai đối tượng (chuỗi có thể), trả về "khoảng cách" giữa chúng.

Nếu bạn thực hiện đầy đủ các tiêu chí sau đó nó giúp:

1. khoảng cách giữa một đối tượng và chính nó là zero. (Phản)
2. khoảng cách từ điểm a đến b là như nhau trong cả hai hướng (transitive)
3. khoảng cách từ điểm a đến c là không hơn khoảng cách từ điểm a đến b cộng khoảng cách từ điểm a đến c. (Tam giác quy tắc)

Nếu số liệu của bạn tuân theo những họ bạn có thể sắp xếp đối tượng của bạn trong không gian metric có nghĩa là bạn có thể chạy các truy vấn như:

• Những đối tượng khác là nhất như này một
• Hãy cho tôi 5 đối tượng nhất như thế này.

Có một cuốn sách hay về nó here. Khi bạn đã thiết lập cơ sở hạ tầng để lưu trữ các đối tượng và chạy các truy vấn, bạn có thể chỉ cần cắm các thuật toán so sánh khác nhau, so sánh hiệu suất của chúng và sau đó điều chỉnh chúng.

Tôi đã làm điều này cho dữ liệu địa lý ở trường đại học và thật thú vị khi cố gắng điều chỉnh các thuật toán so sánh.

Tôi chắc chắn bạn có thể bắt đầu với thứ gì đó nâng cao hơn nhưng bạn có thể bắt đầu bằng một thứ đơn giản như giảm đường địa chỉ sang chữ số và chữ cái đầu tiên của mỗi từ. thuật toán.

Hy vọng điều đó sẽ giúp ích theo một cách nào đó.

Answer 4

Bạn có thể sử dụng Levenshtein edit distance để tìm các chuỗi chỉ khác nhau một vài ký tự. BK Trees có thể giúp tăng tốc quá trình khớp.

Answer 5

Khi tôi phải sửa đổi một chương trình độc quyền làm điều này, vào đầu những năm 90, phải mất hàng nghìn dòng mã trong nhiều mô-đun, được xây dựng qua nhiều năm kinh nghiệm. Kỹ thuật học máy hiện đại phải làm cho nó dễ dàng hơn, và có lẽ bạn không cần phải thực hiện tốt (đó là bánh mì và bơ của chủ nhân của tôi).

Vì vậy, nếu bạn đang nói về việc hợp nhất danh sách địa chỉ gửi thư thực tế, tôi sẽ làm điều đó bằng cách thuê ngoài nếu có thể.

USPS có một số xét nghiệm để đo lường chất lượng của các chương trình tiêu chuẩn hóa địa chỉ. Tôi không nhớ bất cứ điều gì về cách mà làm việc, nhưng bạn có thể kiểm tra xem họ vẫn làm điều đó - có lẽ bạn có thể nhận được một số dữ liệu đào tạo tốt.