zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Tích hợp dữ liệu và XML - Chương 10: Đối sánh chuỗi

Chia sẻ: Cố Dạ Bạch | Ngày: | Loại File: PDF | Số trang:5

Báo xấu

7
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Tích hợp dữ liệu và XML - Chương 10: Đối sánh chuỗi. Chương này cung cấp cho sinh viên những nội dung gồm: giới thiệu; phát biểu bài toán; phương pháp tính độ tương đồng dựa trên chuỗi và dựa trên tập hợp;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tích hợp dữ liệu và XML - Chương 10: Đối sánh chuỗi

21/04/2013 Nội dung 1. Giới thiệu Đối sánh chuỗi 2. Phát biểu bài toán 3. Phương pháp tính ñộ tương ñồng 3.1. Dựa trên chuỗi Nguyễn Hồng Phương 3.2. Dựa trên tập hợp Email: phuong.nguyenhong@hust.edu.vn Site: http://is.hut.edu.vn/~phuongnh Bộ môn Hệ thống thông tin Viện Công nghệ thông tin và Truyền thông Đại học Bách Khoa Hà Nội 1 2 1. Giới thiệu 2. Phát biểu bài toán Là bài toán tìm các chuỗi trỏ tới cùng một Cho hai tập chuỗi X và Y; tìm tất cả các cặp thực thể trong thế giới thực. chuỗi (x, y), x∈X và y∈Y, sao cho x và y trỏ tới cùng thực thể thế giới thực. Ví dụ Chuỗi David Smith trong 1 CSDL có thể chỉ tới Gọi các cặp như vậy là các sánh ñôi (match) cùng một người David R. Smith trong CSDL Ví dụ: khác. Chuỗi 1210 W. Dayton St, Madison WI và 1210 Tập X Tập Y Sánh ñôi West Dayton, Madison WI 53706 cùng chỉ tới x1 = Dave Smith y1 = Dave D. Smith (x1,y1) một ñịa chỉ vật lý x2 = Joe Wilson y2 = Daniel W. Smith (x3,y2) x3 = Dan Smith Đối sánh chuỗi ñóng vai trò then chốt trong bài toán tích hợp dữ liệu, trích rút thông tin,… 3 4 3. Phương pháp tính ñộ tương ñồng Thách thức Độ tương ñồng s ánh xạ cặp (x,y) vào 1 Tính chính xác giá trị ∈[0,1] Lỗi chính tả s càng lớn thì x,y càng tương ñồng Định dạng khác nhau Thuật ngữ khác: khoảng cách, chi phí Tên khác nhau giá trị càng nhỏ thì ñộ tương ñồng càng cao => thước ño ñộ tương ñồng s(x,y)∈[0,1] Tính mở rộng Độ tương ñồng s mở rộng cho nhiều cặp của 2 tập X và Y => bùng nổ tích Đề-các => chỉ áp dụng s(x,y) với các bộ ñôi triển vọng 5 6 1
21/04/2013 3.1. Độ tương ñồng dựa trên chuỗi Phương pháp Edit Distance Coi các chuỗi là một dãy tuần tự các kí tự Còn gọi là khoảng cách Levenshtein Tính toán chi phí biến ñổi một chuỗi thành d(x,y) chi phí tối thiểu biến ñổi chuỗi x chuỗi kia thành chuỗi y Một số phương pháp Việc biến ñổi chuỗi sử dụng các thao tác Edit Distance sau: xóa một kí tự, chèn một kí tự, thay thế một Needleman-Wunch kí tự Affine Gap Ví dụ: chi phí biến ñổi chuỗi x=David Smith-Waterman Smiths thành chuỗi y=Davidd Simth là 4 Jaro Thêm d sau David; thay thế m bởi i; thay thế i Jaro-Winkler bởi m; xóa kí tự s cuối cùng d(x,y)=d(y,x) 7 8 Phương pháp Edit Distance (tiếp) Phương pháp Edit Distance (tiếp) Mối quan hệ giữa hàm khoảng cách d(x,y) Giá trị của d(x,y) có thể ñược tính toán và hàm tương ñồng s(x,y) dựa trên quy hoạch ñộng d(x, y) Cho s(x, y) = 1 − x = x1x2…xn, y = y1y2…ym max(length (x), length(y)) xi và yj là các kí tự Ví dụ: d(i,j): khoảng cách soạn thảo giữa x1x2…xi (tiền tố thứ i của x) và y1y2…yj (tiền tố thứ 4 s(David Smiths, Davidd Simth) = 1 − = 0.67 j của y) max(12,12) Ý tưởng: sử dụng biểu thức quay lui, tính d(i,j) từ các giá trị ñã tính trước ñó của d 9 10 Phương pháp Edit Distance (tiếp) Phương pháp Edit Distance (tiếp) Biến ñổi chuỗi x1x2…xi thành chuỗi y1y2…yj Biểu thức quay lui: (a) Biến ñổi x1x2…xi-1 thành y1y2…yj-1, sau ñó  d(i - 1, j - 1) if x i = y j copy xi vào yj nếu xi = yj  d(i - 1, j - 1) + 1 if x ≠ y  d(i, j) = min  i j (b) Biến ñổi x1x2…xi-1 thành y1y2…yj-1, sau ñó thay thế xi bởi yj nếu xi ≠ yj  d(i - 1, j) + 1 //del ete x i (c) Xóa xi, sau ñó biến ñổi x1x2…xi-1 thành d(i, j - 1) + 1 // insert y j  y1y2…yj Hoặc viết gọn: (d) Biến ñổi x1x2…xi thành y1y2…yj-1, sau ñó d(i - 1, j - 1) + c(x i , y j ) // copy or substitute chèn thêm yj  d(i, j) = min  d(i - 1, j) + 1 // delete x i Giá trị d(i,j) là tối thiểu của các chi phí  d(i, j - 1) + 1 // insert y j biến ñổi ở trên  0 if x i = y j c(x i , y j ) =  1 if x i ≠ y j 11 12 2
21/04/2013 Phương pháp Edit Distance (tiếp) Phương pháp Edit Distance (tiếp) Chú ý: d(i,0) = i và d(0,j) = j Ví dụ: tính khoảng cách soạn thảo d(x,y) y0 y1 y2 y3 y4 với x = "dva", y = "dave" y0 y1 y2 y3 y4 d a v e d a v e x0 0 1 2 3 4 x = d-va x0 0 1 2 3 4 x1 d 1 0 1 2 3 y = dave x1 d 1 0 1 x2 v 2 1 1 1 2 Thay thế a với e, x2 v 2 x3 a 3 2 1 2 2 chèn a sau d x3 a 3 13 14 Phương pháp Edit Distance (tiếp) Mũi tên ñi chéo từ ô (3,4) tới ô (2,3): kí tự Các phương pháp khác: sinh viên tự tìm x3 (kí tự a) ñược copy vào hoặc thay thế hiểu, coi ñó là bài tập ở nhà. bởi kí tự y4 (kí tự e). Mũi tên ñi chéo từ ô (2,3) tới ô (1,2): x2 (kí tự v) ñược copy vào hoặc thay thế bởi y3 (kí tự v). Mũi tên ñi ngàng từ ô (1,2) sang ô (1,1): một kí tự cách – ñược chèn vào x và bắt cặp với kí tự a trong y. Quá trình dừng lại khi tới ô (0,0) Độ phức tạp tính toán là O(|x||y|) 15 16 3.2. Tính ñộ tương ñồng dựa trên tập hợp Coi xâu kí tự là tập các ña tập token Cách khác: q-grams các xâu con ñộ dài q có mặt trong xâu ban ñầu Sử dụng tính chất tập hợp ñể tính toán ví dụ: xâu "david smith" có tập tất cả các 3- ñiểm tương ñồng grams là {##d, #da, dav, avi, ..., ith, th#, Sinh token từ xâu ñầu vào: h##} Cách phổ dụng: Một số phương pháp Xem xét các từ (phân cách nhau bởi kí tự Overlap cách) Jaccard Loại bỏ từ dừng TF/IDF Ví dụ: xâu "david smith" => tập token {david, smith} 17 18 3
21/04/2013 Phương pháp Overlap Phương pháp Jaccard Cho Bx và By là các tập các token sinh Độ tương ñồng Jaccard giữa 2 xâu x và ra từ xâu x và xâu y y là J(x,y)=|Bx∩By|/|Bx∪By| Độ overlap trả về số token chung Ví dụ: O(x,y) = |Bx∩By| x = dave; y = dav Ví dụ: Bx={#d, da, av, ve, e#} x = dave; y = dav By={#d, da, av, v#} 2-grams của x: Bx={#d, da, av, ve, e#} J(x,y)=3/6 2-grams của y: By={#d, da, av, v#} O(x,y)= 3 19 20 Phương pháp TF/IDF Phương pháp TF/IDF (tiếp) TF/IDF liên quan ñến lĩnh vực tìm kiếm Phương pháp TF/IDF có thể nhận ra Apple là thông tin: tìm các tài liệu phù hợp với các term ñặc biệt, trong khi CA và Corporation là những cái chung nhiều hơn. từ khóa truy vấn. Các cặp xâu ñem ñối sánh ñược lấy ra từ Hai xâu là tương ñồng nếu chúng chia sẻ một tập chuỗi các term ñặc biệt. Biến ñổi từng chuỗi thành một túi từ, gọi Ví dụ: là tài liệu. x = Apple Corporation, CA y = IBM Corporation, CA Ví dụ: z = Apple Corp x=aab Bx={a, a, b} Phương pháp edit distance và Jaccard sẽ cho y=ac By={a, c} s(x,y) cao hơn s(x,z) z=a Bz={a} 21 22 Phương pháp TF/IDF (tiếp) Phương pháp TF/IDF (tiếp) Tính term frequency (TF) và inverse Tiếp theo, biến ñổi từng tài liệu d thành document frequency (IDF): vector ñặc trưng vd Với mỗi từ t và tài liệu d, tf(t,d) = số lần t xuất Hai tài liệu càng tương ñồng nếu vector hiện trong d tương ứng của chúng gần nhau Với mỗi từ t, tính idf(t) = tổng số tài liệu trong bộ sưu tập chia cho số tài liệu chứa t Vector của d có ñặc trưng vd(t) với mỗi IDF càng cao nghĩa là sự xuất hiện của từ càng ñặc từ t. Giá trị của vd(t) là hàm của TF và biệt/khác biệt IDF tf(a,x)=2 idf(a)=3/3=1 vd có nhiều ñặc trưng bằng số term tf(b,x)=1 idf(b)=3/1=3 ... trong bộ sưu tập. idf(c)=3/1=3 tf(c,z)=0 23 24 4
21/04/2013 Phương pháp TF/IDF (tiếp) Phương pháp TF/IDF (tiếp) x=aab Bx={a, a, b} Tính ñiểm tương ñồng TF/IDF giữa 2 xâu a b c y=ac By={a, c} z=a Bz={a} bất kỳ p và q vx 2 3 0 T là tập tất cả các từ trong bộ sưu tập tf(a,x)=2 idf(a)=3/3=1 vy 3 0 3 tf(b,x)=1 idf(b)=3/1=3 Vector vp và vq (của xâu p và q): không gian vz 3 0 0 ... idf(c)=3/1=3 |T| chiều, mỗi chiều tương ứng với 1 từ tf(c,z)=0 Điểm TF/IDF giữa p và q ñược tính như là cosine góc giữa 2 vector này: Ba vector vx, vy, vz của ba tài liệu Bx, By, Bz vd(t) = tf(t,d).idf(t) s(p, q) = ∑ t∈T v p (t).v q (t) ∑ ∑ 2 vx(a) = 2.1 = 2 t∈T v p (t) 2 . t∈T v q (t) 25 26 Phương pháp TF/IDF (tiếp) Ví dụ trên: ñiểm TF/IDF giữa 2 xâu x và y là: 2.3 s(x, y) = = 0.39 2 + 32 . 32 + 32 2 27 28 Lời hay ý ñẹp Đường tuy gần, không ñi không bao giờ ñến. Việc tuy nhỏ, không làm chẳng bao giờ nên Tuân Tử 29 5

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.