Luận văn Ứng dụng phân hạng tổng hợp cho bài toán so khớp lược đồ

52 Chương 4- Thuật toán phân hạng tổng hợp Để giải quyết cho bài toán so khớp lược đồ, ban đầu các hướng tiếp cận tập trung nghiên cứu cải tiến các kỹ thuật so khớp lược đồ. Sau đó, một số nhóm nghiên cứu đề xuất ý tưởng kết hợp các kỹ thuật so khớp nhằm bổ sung cho nhau và có thể khắc phục những điểm yếu của nhau. Một số công trình nghiên cứu thực nghiệm đã báo cáo kết quả đáng khích lệ khi sử dụng bộ so khớp lược đồ kết hợp. Nhưng thậm chí khi đã có một sự kết hợp tốt giữa các bộ so khớp lược đồ cũng không đảm bảo xác định được ánh xạ chính xác giữa các lược đồ. Để giải quyết tình huống như vậy, người ta có thể chấp nhận hướng tiếp cận phân hạng top- k ánh xạ lược đồ. Công trình nghiên cứu của A. Gal và các đồng sự [14] về tìm kiếm top-k ánh xạ lược đồ đã trình bày ở chương 3 mở ra hướng nghiên cứu kết hợp các hệ thống so khớp lược đồ như (Cupid, COMA, Similarity, OntoBuilder,…) với phương pháp tìm top-k ánh xạ lược đồ. Tuy nhiên, thực nghiệm của nhóm tác giả này cho thấy độ chính xác và độ phủ của top-k ánh xạ trả về phụ thuộc vào các hệ thống so khớp. Trong các công trình nghiên cứu về so khớp lược đồ, nhiều heuristic đã được đề xuất trong các hệ thống so khớp lược đồ. Với việc sử dụng heuristic trong so khớp lược đồ, những hệ thống so khớp lược đồ này chỉ có thể trả về ánh xạ lược đồ có chất lượng tốt đối với một số dạng lược đồ mà nó hướng đến (điều này được trình bày cụ thể trong chương 2). Tuy nhiên, rất khó có thể lựa chọn bộ so khớp phù hợp giữa rất nhiều hệ thống so khớp, vì số lượng các bộ so khớp vẫn tiếp tục tăng lên, hơn nữa người dùng cũng không thể biết được với mỗi cặp lược đồ cụ thể, bộ so khớp nào là phù hợp nhất để lựa chọn. Vì vậy, luận văn đề xuất kết hợp giữa các hệ thống so khớp lược đồ hiện có với hướng tiếp cận top-k ánh xạ lược đồ ứng dụng các thuật toán phân hạng tổng 53 hợp được phát triển trong lĩnh vực tìm kiếm thông tin. Ý tưởng chính của thuật toán phân hạng tổng hợp là giữa n kết quả trả về từ n hệ thống tìm kiếm khác nhau, chọn được một kết quả tốt (có độ chính xác cao) trong số n kết quả này. Phần tiếp theo luận văn trình bày các thuật toán và kết quả thực nghiệm của các phương pháp phân hạng tổng hợp trong lĩnh vực tìm kiếm thông tin, và nhận xét đánh giá về các thuật toán (phần 4.1), đề xuất ứng dụng một thuật toán phân hạng tổng hợp cho bài toán so khớp lược đồ (phần 4.2), cài đặt thử nghiệm thuật toán này để giải quyết bài toán so khớp lược đồ (phần 4.3), thử nghiệm và đánh giá (phần 4.4). 4.1. Thuật toán phân hạng tổng hợp trong lĩnh vực tìm kiếm thông tin Máy tìm kiếm liên hợp (Meta-Search Engine) là một công cụ được phát triển để tăng hiệu suất tìm kiếm thông tin bằng cách thực thi câu truy vấn của người dùng trên nhiều máy tìm kiếm khác nhau, sau đó kết hợp các kết quả trả về thành một danh sách phân hạng duy nhất. Khi người dùng đưa ra một câu truy vấn q, máy tìm kiếm liên hợp gởi câu truy vấn này đến n máy tìm kiếm khác nhau và nhận n danh sách top-k tài liệu liên quan do các máy tìm kiếm trả về. Máy tìm kiếm liên hợp sử dụng các thuật toán phân hạng tổng hợp để tính điểm cho từng tài liệu trong n danh sách này hoặc tính điểm cho từng hệ thống tìm kiếm và trả về một danh sách top-k tài liệu có điểm cao nhất. Trong bài báo [21], Lee đã nhận xét: “các thuật toán tìm kiếm khác nhau tìm kiếm nhiều tài liệu liên quan giống nhau nhưng tài liệu không liên quan thì khác nhau”. Và K. B. Ng và P. B. Kantor [26] đã kết luận với Lee rằng nếu nhận định này đúng thì bất kỳ kỹ thuật phân hạng tổng hợp nào cũng sẽ làm tăng độ chính xác, và đã chỉ ra một số điểm mạnh của máy tìm kiếm liên hợp: “Cải thiện độ phủ: khi máy tìm kiếm liên hợp thực hiện hợp nhất nhiều danh sách tài liệu trả về, độ phủ sẽ được cải thiện nếu các hệ thống thành phần tìm được nhiều tài liệu liên quan khác nhau.” 54 Với ý tưởng chính dựa vào nhận xét của Lee, hai thuật toán phân hạng tổng hợp là đếm Borda và đếm tham chiếu thực hiện tính điểm cho tài liệu dựa vào tần xuất xuất hiện và vị trí của chúng trong n danh sách top-k. 4.1.1. Mô hình thuật toán phân hạng tổng hợp Hình 4.1 Mô hình thuật toán phân hạng tổng hợp Thuật toán phân hạng tổng hợp trong Hình 4.1 nhận đầu vào là n danh sách top-k. Mỗi danh sách là kết quả trả về của một máy tìm kiếm thông tin (như Google, Yahoo,…). Các thuật toán phân hạng tổng hợp tính điểm cho mỗi tài liệu trong n danh sách top-k tài liệu hoặc tính điểm cho từng danh sách top-k và trả về một danh sách top-k tài liệu có điểm cao nhất. 4.1.2. Thuật toán đếm Borda Năm 2001, J. A. Aslam và M. Montague trong [1] đã tiến hành thực nghiệm và kết luận thuật toán phân hạng tổng hợp đếm Borda trả về kết quả có độ chính xác trung bình cao nhất trong số các hệ thống tìm kiếm và siêu tìm kiếm hiện có. Một số ký hiệu: • Ri: hệ thống tìm kiếm thứ i, i = 1..n • Li: Danh sách top-k tài liệu do Ri sinh ra • Mỗi Li gồm k tài liệu (di,1, di,2,..., di,k) 55 • dij: Tài liệu thứ j trong danh sách Li, i = 1..n, j = 1..k 4.1.2.1. Thuật toán Bước 1: Tính điểm cho tất cả các tài liệu dij trong n danh sách top-k đầu vào. Bước 2: Phát sinh danh sách top-k tài liệu có điểm cao nhất Thuật toán tính điểm của các tài liệu dij trong n danh sách top-k, mỗi tài liệu dij được tính điểm dựa vào vị trí của tài liệu này trong n danh sách Li (Điểm của tài liệu d có vị trí thứ j trong danh sách Li là s (di) = k - j. Tổng điểm của d là s(d) = ∑ = n i i ds 1 )( ). Thuật toán tính điểm của các tài liệu dij như sau: For each dij { s(di) = 0; for (j = 1; j ≤ n; j++) { for (t =1; t ≤ k; t++) If (di = Ljt) s(di) = s(di) + k + 1 - t ; } } Từ điểm của các tài liệu, thuật toán xây dựng danh sách L0 gồm k tài liệu có điểm cao nhất. Thuật toán đếm Borda có thể được sử dụng để kết hợp những danh sách phân hạng trả về bởi các hệ thống tìm kiếm, không cần quan tâm đến điểm phân hạng 56 từng tài liệu(điểm do hệ thống tìm kiếm Ri đánh giá) và không cần dữ liệu huấn luyện, thuật toán kết hợp đơn giản và hiệu quả. Hơn nữa, thực nghiệm cho thấy hiệu suất đếm Borda khá tốt. Ví dụ 4.1 Cho 4 danh sách: L1 = {a, b, c, d}; L2 = {a, d, b, e}; L3 = {c, a, f , e}; L4 = {b, g, e, f} s(a) = 4 + 4 +3 = 11 s(b) = 3 + 2 + 4 = 9 s(c) = 2 + 4 = 6 s(d) = 1 + 3 = 4 s(e) = 1 + 1 + 2 = 4 s(f) = 2 + 1 = 3 s(g) = 3 Vậy danh sách thứ tự toàn cục là a, b, c, {d, e}, {f, g} Vì d,e và f, g có điểm bằng nhau nên chọn ngẫu nhiên vị trí giữa d, e và f, g. 4.1.2.2. Đếm Borda có trọng số J. A. Aslam và M. Montague đã kết luận: “máy tìm kiếm liên hợp thực hiện tốt hơn khi trọng số của các hệ thống tìm kiếm không bằng nhau”. Một lược đồ trọng số đơn giản nhưng hiệu quả là các điểm được gán cho một tài liệu trong danh sách trả về bởi hệ thống tìm kiếm Ri có trọng số αi. Trọng số hợp lý có thể bao gồm một đánh giá về hiệu suất của hệ thống, như độ chính xác trung bình,… 4.1.2.3. Kết quả thực nghiệm của hai thuật toán đếm Borda và đếm Borda có trọng số J. A. Aslam và M. Montague đã tiến hành thực nghiệm cho hai thuật toán đếm Borda và đếm Borda có trọng số. Bộ dữ liệu thực nghiệm được sử dụng là TREC3, 57 TREC5, và TREC9 (TREC cung cấp những bộ dữ liệu chuNn để đánh giá chất lượng của các thuật toán tìm kiếm thông tin). Nhóm tác giả này so sánh độ chính xác trung của hệ thống tìm kiếm có độ chính xác cao nhất trong số các hệ thống tìm kiếm đầu vào (ký hiệu SEbest) với hai thuật toán đếm Borda, đếm Borda có trọng số, và CombMNZ (một trong những máy tìm kiếm liên hợp), với số lượng các hệ thống tìm kiếm đầu vào thay đổi từ 1 đến 12 hệ thống. Kết quả thực nghiệm cho thấy khi tăng số lượng hệ thống tìm kiếm đầu vào thì cả 4 độ chính xác trung bình đều tăng lên. Với bộ dữ liệu TREC3, cả ba thuật toán đếm Borda và đếm Borda có trọng số đều trả về độ chính xác trung bình cao hơn SEbest, trong đó đếm Borda có trọng số có độ chính xác cao nhất khi số lượng hệ thống đầu vào nhỏ hơn 4, khi số lượng hệ thống đầu vào tăng lên, CombMNZ có độ chính xác trung bình cao hơn khoảng 0.3%. Với TREC 5, thuật toán Borda có trọng số có độ chính xác cao nhất và thuật toán đếm Borda có độ chính xác thấp nhất. Với TREC9, đếm Borda có độ chính xác thấp nhất, đếm Borda có trọng số có độ chính xác trung bình thấp hơn SEbest khoảng 1.5% và cao hơn khoảng 1% so với CombMNZ khi số lượng hệ thống tìm kiếm đầu vào nhỏ hơn 8, và thấp hơn CombMNZ khoảng 0.5% khi số lượng hệ thống tìm kiếm từ 8 đến 12. Thuật toán so khớp Borda cài đặt đơn giản, nhưng kết quả trả về của nó có độ chính xác trung bình thường vượt qua các hệ thống so khớp đầu vào, với thuật toán Borda có trọng số gần như chắc chắn cải thiện được độ chính xác khi chọn được trọng số phù hợp. 4.1.3. Thuật toán đếm tham chiếu Nhóm tác giả S.Wu và F.Crestani [34] đã đề xuất thuật toán đếm tham chiếu để đánh giá các hệ thống tìm kiếm thông tin. Để đánh giá hiệu suất của một hệ thống tìm kiếm thông tin, thuật toán sử dụng một độ đo được gọi là đếm tham chiếu. Thuật toán tính điểm của mỗi danh sách top-k tài liệu đầu vào, danh sách có điểm cao nhất được đánh giá là tốt nhất trong số n danh sách top-k đầu vào, và cũng chính là danh sách top-k được trả về. 58 Thuật toán đếm tham chiếu thực hiện theo hai bước sau: Bước 1:Tính điểm cho của mỗi danh sách top-k đầu vào. Bước 2: Trả về danh sách top-k tài liệu có điểm được tính ở bước 1 cao nhất. 4.1.3.1. Thuật toán cơ sở • Mỗi Li: o dij được gọi là tài liệu ban đầu; dl, p = dij , l ≠ i thì dl, p là tài liệu tham chiếu. o o(dij): là số các tài liệu tham chiếu của dij trong m-1 danh sách Ll (l ≠ i) o Si(k): tổng số đếm tài liệu tham chiếu của danh sách Li: Si(k) = ∑kj=1 o(dij) • Thuật toán tính điểm của Si(k): for i = 1; i ≤ m; i++ { for j = 1 ; j ≤ k; j++ { o(dij) = 0 for t = 1; t ≤ m; t++ { If (t ≠ i ) then If dij in Lt then o(dij) = o(dij) + 1 } Si(k) = Si(k) + o(dij) } } 59 Trong thuật toán cơ sở, o(dij) được tính bằng cách cộng thêm 1 khi xuất hiện một tài liệu tham chiếu của dij, mà không quan tâm đến vị trí của các tài liệu tham chiếu. Ví dụ, tài liệu ban đầu d1,1 có hai tài liệu tham chiếu là d2,n và d3, n; tài liệu ban đầu d2,1 có hai tài liệu tham chiếu là d3,1, d4,1. Mặc dù d1,1 xuất hiện ở cuối danh sách của L2 và L3 và d2,1 xuất hiện ở đầu danh sách L3 và L4, o(d1,1) = o (d2,1) = 2. Thông tin về vị trí của một tài liệu trong danh sách là rất quan trọng trong các thuật toán phân hạng nhưng thuật toán này đã bỏ qua nó. Ví dụ 4.2 Cho 4 danh sách: L1 = {a, b, c, d}; L2 = {a, d, b, e}; L3 = {c, a, f , e}; L4 = {b, g, e, f} L1: o(d11) = 2; o(d12) = 2; o(d13) = 1; o(d14) = 1 s1(4) = 2 + 2 + 1 + 1 = 6 L2: o(d21) = 2; o(d22) = 1; o(d23) = 2; o(d24) = 2 s2(4) = 2 + 1 + 2 + 2 = 7 L3: o(d31) = 1; o(d32) = 2; o(d33) = 1; o(d34) = 2 s3(4) = 1 + 2 + 1 + 2 = 6 L4: o(d41) = 2; o(d42) = 0; o(d43) = 2; o(d44) = 1 s4(4) = 2 + 0 + 2 + 1 = 5 Vậy L2 là danh sách toàn cục 4.1.3.2. Một số thuật toán tham chiếu trọng số Thuật toán đếm tham chiếu có trọng số dựa vào thuật toán đếm tham chiếu cơ sở, nhưng có tính thêm trọng số của các tài liệu tham chiếu và tài liệu ban đầu dựa vào vị trí của chúng trong n danh sách top-k. 60 Thuật toán 1: Gán trọng số khác nhau cho mỗi tài liệu tham chiếu ở những vị trí khác nhau. o(dij) được tính theo công thức sau: o(dij) = ∑ w(dl, p) Trong đó - dl, p là tài liệu tham chiếu của dij , dl,p = dij (l ≠ i); - w(dl,p) = K- p, K là một hằng số. Ví dụ 4.3 Cho 4 danh sách: L1 = {a, b, c, d}; L2 = {a, d, b, e}; L3 = {c, a, f , e}; L4 = {b, g, e, f} Cho hằng số K = 6 L1: o(d11) = 9; o(d12) = 8; o(d13) = 5; o(d14) = 4 s1(4) = 9 + 8 + 5 + 4 = 26 L2: o(d21) = 9; o(d22) = 2; o(d23) = 9; o(d24) = 5 s2(4) = 9 + 2 + 9 + 5 = 25 L3: o(d31) = 3; o(d32) = 10; o(d33) = 2; o(d34) = 5 s3(4) = 3 + 10 + 2 + 5 = 20 L4: o(d41) = 7; o(d42) = 0; o(d43) = 4; o(d44) = 3 s4(4) = 7 + 0 + 4 + 3 = 14 Vậy L1 là danh sách thứ tự toàn cục Thuật toán 2: o(dij) vẫn được tính như thuật toán cơ sở nhưng gán trọng số khác nhau cho mỗi tài liệu ban đầu khác nhau. 61 Si(k) = ∑kj=1 wj * o(dij) Để tính Si , wj được tính theo công thức sau: Cho k là số tài liệu tương tự trong danh sách Li cần tính điểm, u là độ chính xác trung bình của Li, v = k/u, q = 1/u, 1 ≤ t ≤ v, 1 ≤p ≤q-1. Trọng số wj được tính như sau: Với j = qt thì: wj = Z(v) – Z(t-1) Với j = qt – p: wj = wqt – 1/t + q/j Z là hàm Zeta: Z(0) = 0; Z(n) = 1 + 1/2 +1/3+…+1/n. Công thức trên được giải thích như sau: giả sử tài liệu tương tự được phân bố trong danh sách k tài liệu với độ chính xác trung bình u ở các vị trí 1/u, 2/u, 3/u,…k. Độ chính xác trung bình là (1/1/u + 2/2/u + …+ v/v/u)/ v = (u + u +…+ u)/v = u (vì u + u +..+ u : là tổng của v giá trị u). Tính phân bố xác xuất cho mỗi tài liệu tương tự như sau: Tài liệu tương tự ở vị trí 1/u là (1/1/u + 1/2/u + … + 1/v/u)/v = (1 + 1/2 + …+ 1/v)*u/v = (1 + 1/2 + …+ 1/v)/k. Tương tự với tài liệu thứ 2/u là (1/2/u + 1/3/u + …+ 1/v/u)/v = (1/2 + 1/3 + …+ v/u)/k Và với tài liệu thứ k là (1/v)/k Ví 1/k là thừa số chung nên có thể bỏ đi. Do đó với j = q*t (q = 1/u) thì wj = ∑ = v tj j 1 = Z(v) – Z(t-1). Nếu có một tài liệu tương tự không ở vị trí q*t, mà ở vị trí j = qt – p (1 ≤ t ≤ v, 1 ≤ p ≤ q-1) còn các tài liệu tương tự còn lại vẫn giữ nguyên vị trí thì tài liệu tương tự ở vị trí qt – p được phân bố với độ chính xác trung bình: wj = wqt – 1/t + q/j 62 Ví dụ 4.4 Cho 4 danh sách: L1 = {a, b, c, d}; L2 = {a, d, b, e}; L3 = {c, a, f , e}; L4 = {b, g, e, f} k = 4, cho u = 0.5 với mỗi Li (thực tế mỗi danh sách Li có một độ chính xác trung bình ui khác nhau) w2 = Z (2) – z (0) = 3/2 w4 = Z (2) – z (1) = 1/2 w1 = w2 -1 + 2 = 5/2 w3 = w4 – 1/2 + 2/3 = 2/3 L1: o(d11) = 2; o(d12) = 2; o(d13) = 1; o(d14) = 1 s1(4) = 5/2*2 + 3/2*2 + 2/3*1 + 1/2*1 = 9.2 L2: o(d21) = 2; o(d22) = 1; o(d23) = 2; o(d24) = 2 s2(4) = 5/2*2 + 3/2*1 + 2/3*2 + 1/2*2 = 8.8 L3: o(d31) = 1; o(d32) = 2; o(d33) = 1; o(d34) = 2 s3(4) = 5/2*1 + 3/2*2 + 2/3*1 + 1/2*2 = 7.2 L4: o(d41) = 2; o(d42) = 0; o(d43) = 2; o(d44) = 1 s4(4) = 5/2*2 + 3/2*0 + 2/3*2 + 1/2*1 = 6.5 Vậy L1 là danh sách thứ tự toàn cục Thuật toán 3: kết hợp của thuật toán 1 và 2: gán trọng số cho cả tài liệu tham chiếu và tài liệu ban đầu: o(dij) = ∑ w(dl,p) 63 Si(k) = ∑kj=1 wj * o(dij) 4.1.3.3. Kết quả thực nghiệm của thuật toán đếm tham chiếu cơ sở và các thuật toán đếm tham chiếu trọng số Thực nghiệm trong [34] được thực hiện trên 5 tập TREC (TREC 3, TREC 5, TREC 6, TREC 7, and TREC 2001) và đánh giá độ chính xác trung bình của thuật toán đếm tham chiếu cơ sở, ba thuật toán đếm tham chiếu trọng số và hệ thống CombMNZ (một trong những máy tìm kiếm liên hợp). Kết quả thực nghiệm cho thấy thuật toán cơ sở và thuật toán tham chiếu trọng số 1 có độ chính xác thấp nhất, thuật toán trọng số 3 có độ chính xác cao nhất trong số 4 thuật toán đếm tham chiếu. Khi số hệ thống tìm kiếm đầu vào nhỏ hơn 10, thuật toán 3 có độ chính xác trung bình cao hơn CombMNZ khoảng 5%, khi số lượng này từ 10 đến 15 hệ thống, CombMNZ có độ chính xác trung bình cao hơn thuật toán 3 khoảng 2%. S.Wu va F.Crestani [34] đã kết luận, “các thuật toán đếm tham chiếu thực hiện tốt hơn nếu số lượng các hệ thống tìm kiếm dưới 10 hệ thống”. Thuật toán đếm tham chiếu không quan tâm đến vị trí của các tài liệu tham chiếu, đây là thông tin quan trọng phản ánh mức độ tương tự giữa hai lược đồ. Vì vậy thuật toán đếm tham chiếu trả về kết quả không tốt so với những thuật toán tham chiếu trọng số. 4.1.4. Nhận xét Cả hai thuật toán đếm Borda và đếm tham chiếu đều thực hiện phân hạng dựa vào một heuristic là “các thuật toán tìm kiếm khác nhau tìm kiếm nhiều tài liệu liên quan giống nhau nhưng tài liệu không liên quan thì khác nhau” (Lee[21]). Vì vậy, cả hai thuật toán dựa vào tần xuất xuất hiện và vị trí của các tài liệu tương tự trong n danh sách top-k đầu vào, tài liệu nào xuất hiện càng nhiều và có vị trí xếp hạng cao trong n danh sách đầu vào thì điểm càng cao. Tuy nhiên, thuật toán đếm Borda chỉ quan tâm đến tần xuất xuất hiện và vị trí của mỗi tài liệu trong n danh sách mà không quan tâm đến danh sách chứa nó. Ngược lại, thuật toán đếm tham chiếu tính điểm của các tài liệu trong cùng một danh sách để tính điểm cho danh sách đó, qua 64 điểm của từng danh sách, thuật toán đánh giá chất lượng của hệ thống tìm kiếm tương ứng khi thực hiện tìm kiếm với câu truy vấn q. Thuật toán đếm Borda có trọng số và đếm tham chiếu có trọng số chỉ dựa vào vị trí và tần xuất xuất hiện các tài liệu trong n danh sách top-k tài liệu trả về để phân hạng tổng hợp , do đó hai thuật toán này đạt hiệu suất (thời gian xử lý, không gian nhớ,…) cao, và có thể áp dụng cho bài toán so khớp lược đồ. Hơn nữa, hai thuật toán này được cài đặt đơn giản và cho kết quả tốt, vì vậy luận văn chọn thuật toán này để cài đặt thử nghiệm trong hệ thống so khớp lược đồ. Luận văn cũng sử dụng thuật toán đếm tham chiếu trọng số để tính trọng số của các hệ thống so khớp lược đồ. Và trọng số này được dùng làm trọng số cho thuật toán đếm Borda có trọng số. 4.2. Thuật toán phân hạng tổng hợp cho bài toán so khớp lược đồ Các thuật toán đếm Borda có trọng số và đếm tham chiếu có trọng số sử dụng cùng một heuristic là “các thuật toán tìm kiếm khác nhau tìm kiếm nhiều tài liệu liên quan giống nhau nhưng tài liệu không liên quan thì khác nhau”. Và điều này cũng xảy ra tương tự trong lĩnh vực so khớp lược đồ (trình bày ở chương 3 trong phần kết quả thực nghiệm). Do đó luận văn đề xuất ứng dụng hai thuật toán này cho bài toán so khớp lược đồ. Lĩnh vực tìm kiếm thông tin và so khớp lược đồ có nhiều điểm giống nhau, do đó có nhiều kỹ thuật và hướng tiếp cận đã được nghiên cứu trong lĩnh tìm kiếm thông tin được phát triển trong lĩnh vực so khớp lược đồ. Tuy nhiên, chúng cũng có một số điểm khác nhau, một trong những điểm khác nhau cơ bản giữa hai lĩnh vực này là trong lĩnh vực tìm kiếm thông tin, mỗi phần tử trong danh sách top-k là một tài liệu liên quan với câu truy vấn q, còn trong so khớp lược đồ, mỗi phần tử trong danh sách top-k là một ánh xạ lược đồ gồm một tập các ánh xạ phần tử. Do đó, để ứng dụng thuật toán phân hạng tổng hợp cho bài toán so khớp lược đồ, luận văn đã điều chỉnh như sau: khi tính điểm của một ánh xạ lược đồ trong một danh sách top- k, thay vì phải tìm những ánh xạ lược đồ này trong n-1 danh sách top-k còn lại, thì 65 chỉ tìm những ánh xạ tương đương với nó. Hai ánh xạ tương đương khi tỷ lệ % các ánh xạ phần tử giống nhau đạt trên một ngưỡng t cho trước. 4.2.1. Phát biểu thuật toán Đầu vào: n danh sách top-k ánh xạ lược đồ. Đầu ra: Một danh sách top-k ánh xạ lược đồ toàn cục. Thuật toán phân hạng tổng hợp mà luận văn đề xuất ứng dụng cho bài toán so khớp lược đồ thực hiện như sau: Sử dụng thuật toán đếm tham chiếu có trọng số tính điểm của mỗi danh sách top-k, từ đó tính trọng số tương ứng cho danh sách top-k đó. Trọng số này được lấy làm trọng số cho thuật toán đếm Borda có trọng số như sau: điểm của mỗi ánh xạ lược đồ trong một danh sách được tính bằng cách xác định vị trí của nó trong danh sách top-k đó nhân với trọng số của danh sách top-k. Điểm toàn cục của một ánh xạ lược đồ bằng tổng số điểm của nó trong n danh sách top-k. Thuật toán trả về danh sách gồm k ánh xạ có điểm cao nhất. 66 4.2.1.1. Sơ đồ thuật toán Đầu vào: n danh sách top-k ánh xạ lược đồ. Đầu ra: Danh sách top-k ánh xạ lược đồ có điểm cao nhất. Ghi chú:
Tính điểm cho mỗi danh sách top-k ánh xạ lược đồ sử dụng thuật toán đếm tham chiếu, và dựa vào số điểm này để tính trọng số cho thuật toán đếm Borda có trọng số.
Tính điểm của mỗi ánh xạ lược đồ sử dụng thuật toán đếm Borda có trọng số. 67 Sơ đồ thuật toán tính trọng số cho mỗi danh sách top- ánh xạ lược đồ: 68 Sơ đồ thuật toán tính điểm cho mỗi ánh xạ lược đồ: 4.2.1.2. Mã giả của một số hàm chính Khi tính điểm của một ánh xạ lược đồ trong một danh sách top-k, thay vì phải tìm những ánh xạ lược đồ này trong n-1 danh sách top-k còn lại, thì chỉ tìm những ánh xạ tương đương với nó. Vì vậy, để tính điểm cho các ánh xạ lược đồ, phải sử dụng thêm hàm xác định hai ánh xạ tương đương nhau. Hàm xác định hai ánh xạ tương đương nhau. Hàm xác định hai ánh xạ tương tương xác định hai ánh xạ lược đồ tương đương nhau khi tỷ lệ các phần tử ánh xạ giống nhau giữa hai lược đồ trên tổng số ánh xạ phần tử cao hơn ngưỡng t cho trước. Đầu vào: Hai ánh xạ lược đồ, và ngưỡng t Kết quả: trị Đúng nếu hai ánh xạ tương, trị Sai nếu hai ánh xạ không tương đương. 69 Equivalent (m1, m2, t) { float Count = 0; float size = số ánh xạ phần tử của một ánh xạ lược đồ; for (int i = 0 ; i < size ; i++) { for (int j = 0 ; j <size ; j++) if (m[i] == m[j]) Count ++; } if (Count/size > t) return true; return false; } 4.2.2. Các hàm tính điểm cho mỗi danh sách top-k ánh xạ lược đồ Tính điểm cho n danh sách top-k ánh xạ lược đồ dựa vào thuật toán đếm tham chiếu trọng số 3, gán trọng số cho cả tài liệu ban đầu và tài liệu tham chiếu. • Hàm tính điểm tham chiếu của một ánh xạ trong một danh sách Li: Đầu vào: ánh xạ ban đầu m, và chỉ số i của danh sách Li Đầu ra: điểm đếm tham chiếu của ánh xạ ban đầu m trong danh sách Li ComputeScoreOfMapList(m, i) 70 { int j = 0 ; while (j < k) do { if (Equivalent (m, Lij)) then { Return K – j; } j++ ; } return 0 ; } • Hàm tính điểm đếm tham chiếu của một ánh xạ trong danh sách Li: Đầu vào: ánh xạ ban đầu m, chỉ số i của danh sách. Đầu ra: điểm tham chiếu của ánh xạ ban đầu m trong danh sách Li ComputeScoreMap (m, i) { int l = 0, score = 0 ; while (l < n) do { if (l != i) then score += ComputeScoreOfMapList(m, l) ; l++; 71 } Return score ; } • Hàm tính điểm cho một danh sách Li: Đầu vào: chỉ số i của danh sách cần tính điểm Đầu ra: điểm đếm tham chiếu của danh sách Li ComputeScoreOfList (i) { int j = 0; real score = 0 ; while (j < k) do { score += w. ComputeScoreMap (Lij, i) } return score ; } Ghi chú: trọng số w được tính theo công thức được trình bày trong thuật toán 3 phần 4.1.3.2. • Hàm tính trọng số cho mỗi danh sách top-k ánh xạ lược đồ Đầu vào: n danh sách top-k ánh xạ lược đồ. Đầu ra: Trọng số của n danh sách top-k ánh xạ lược đồ 72 ComputeWeight() { real score [n] = 0, totalScore = 0; for int i = 0 ; i < n ; i++ { score [i] = ComputeScoreOfList (i) ; totalScore += score [i] ; } for int i = 0 ; i < n ; i++ score[i] = score [i] / totalScore ; return score; } 4.2.3. Các hàm tính điểm cho mỗi ánh xạ lược đồ • Hàm tính điểm của một ánh xạ lược đồ m trong danh sách Li Đầu vào: ánh xạ m, chỉ số i của danh sách Li Đầu ra: điểm đếm Borda của ánh xạ m ConputeScoreMapList (m , i) { int j = 0 ; while (j < k) { 73 if (Equivalent (m, Lij)) then return k - j ; j++ ; } return 0 ; } • Hàm tính điểm của một ánh xạ lược đồ: Đầu vào: ánh xạ lược đồ m Đầu ra: điểm đếm Borda trọng số của ánh xạ m ComputeScoreMap (m) { real score[][] ; real weight[] = ComputeWeight() ; for (int i = 0 ; i < n ; i++) { int j = 0 ; while (j < k) { score[i][j] += k - j ; int i1 = i +1 ; while (i1 < n) 74 { score[i][j] += weight[i1] * ScoreMapList(i1, Lij) ; i1++ ; } j++; } } } 4.3. Chương trình cài đặt 4.3.1. Hệ thống OntoBuilder được sử dụng trong chương trình OntoBuilder là một hệ thống được xây dựng với nhiều mục đích khác nhau của Viện công nghệ Technion-Israel (Technion-Israel Institute of Technology) [13], [14], [15], [16]. Một trong những mục đích của hệ thống OntoBuilder là so khớp lược đồ sử dụng cấu trúc ontology [15]. Ngoài ra, OntoBuilder còn được xây dựng để đánh giá các thuật toán so khớp lược đồ [16]. Luận văn sử dụng hệ thống OntoBuilder với mục đích thứ nhất khi xây dựng n danh sách top-k đầu vào cho thuật toán phân hạng tổng hợp được đề xuất,và sử dụng với mục đích thứ hai khi đánh giá kết quả thực nghiệm của thuật toán này. Chi tiết về hệ thống OntoBuilder được trình bày trong phần phụ lục. OntoBuilder rút trích ontology từ các web form và thực hiện so khớp lược đồ dựa trên các ontology, hệ thống sử dụng bốn kỹ thuật cơ bản và lai ghép các kỹ thuật này với nhau. Bốn kỹ thuật cơ bản được sử dụng là: So khớp từ (Term): từ là sự kết hợp của một nhãn và một tên. So khớp từ so khớp nhãn và tên để xác định những từ tương tự về cú pháp. Để đạt được kết quả tốt hơn, 75 từ được tiền xử lý, sử dụng một số kỹ thuật trong lĩnh vực tìm kiếm thông tin về so sánh chuỗi. So khớp từ dựa vào so sánh từ hoặc so sánh chuỗi. So khớp giá trị (Value): So khớp giá trị sử dụng ràng buộc miền giá trị (như checkbox, radiobutton,…) để tính độ tương tự giữa các từ. Tập giá trị ràng buộc rất hữu ích khi so sánh hai từ không thể so khớp chính xác thông qua nhãn. So khớp kết hợp (Composition): Một từ kết hợp được tạo thành từ nhiều từ khác (hoặc nguyên tố hoặc các từ kết hợp khác). Từ kết hợp có thể chuyển thành một cấu trúc phân cấp. Bộ so khớp này đánh giá độ tương tự của từ dựa vào độ tương tự láng giềng của chúng. So khớp thứ tự (Precedence): Quan hệ thứ tự là kỹ thuật khác biệt của hệ thống OntoBuilder. Trong bất kỳ xử lý tương tác nào, thứ tự cung cấp dữ liệu rất quan trọng, thuật toán so khớp thứ tự dựa vào một kỹ thuật được gọi là trục đồ thị (graph pivot) như sau: cho một từ vi, tập các từ được chia thành hai tập: precede(vi) = {vj| vj trước vi theo thứ tự thời gian hiển thị cho người dùng} và succeed(vi) = {vj| vj sau vi theo thứ tự thời gian hiển thị cho người dùng}. Khi so khớp hai từ u và v, thuật toán tính độ tương tự của precede(u) và precede(v), và độ tương tự của succeed(u) và succeed(v) dựa vào độ tương tự cú pháp của kỹ thuật so khớp từ và giá trị. 4.3.2. Mô hình của hệ thống được cài đặt thử nghiệm Hình 4.2 Mô hình hệ thống so khớp lược đồ được cài đặt thử nghiệm Hình 4.2 mô tả hệ thống cài đặt thử nghiệm, hệ thống sử dụng công cụ so khớp OntoBuilder để phát sinh năm danh sách top-k ánh xạ từ hai lược đồ S1 và S2, và 76 năm danh sách top-k này được dùng làm dữ liệu vào cho thuật toán đếm Borda có trọng số do luận văn đề xuất. Hệ thống được thực hiện theo hai bước: Bước 1- Phát sinh dữ liệu đầu vào cho thuật toán phân hạng tổng hợp: Ý tưởng chính của thuật toán này là nhận n danh sách top-k được trả về bằng cách kết hợp thuật toán tìm top-k ánh xạ lược đồ (của A.Gal và các đồng sự được trình bày trong chương 3) với một số các hệ thống so khớp lược đồ như COMA, Similarity Flooding,…. Tuy nhiên vì những lý do khách quan như thời gian thực hiện luận văn và những những khó khăn trong quá trình tìm kiếm các hệ thống so khớp lược đồ nên luận văn sử dụng hệ thống OntoBuilder để phát sinh n danh sách top-k ánh xạ lược đồ. Mỗi danh sách top-k ánh xạ lược đồ được phát sinh bằng cách thực thi một thuật toán lai ghép giữa một số các thuật toán của hệ thống OntoBuilder, sau đó sử dụng thuật toán tìm top-k ánh xạ lược đồ được cài đặt sẵn trong hệ thống OntoBuilder để phát sinh danh sách top-k ánh xạ lược đồ . Trong hệ thống thử nghiệm cài đặt với n = 5. Bước 2:- Phát sinh danh sách top-k ánh xạ lược đồ có điểm cao nhất: • sử dụng thuật toán phân hạng tổng hợp tính điểm toàn cục cho các ánh xạ lược đồ trên n danh sách. • Phát sinh danh sách top-k ánh xạ lược đồ toàn cục bao gồm những ánh xạ lược đồ có điểm toàn cục cao nhất. 4.3.3. Màn hình kết quả Trong quá trình so khớp lược đồ, nếu chưa có tập tin xml chứa thông tin về lược đồ, người dùng có thể sử dụng màn hình rút trích lược đồ từ các web form trong Hình 4.3. Khi thực hiện so khớp lược đồ, người dùng có thể chọn thuật toán so khớp lược đồ, hệ thống hỗ trợ 6 thuật toán so khớp: 5 thuật toán lai ghép của hệ thống OntoBuilder và thuật toán phân hạng tổng hợp (thuật toán đếm Borda có 77 trọng số); ngoài ra, người dùng có thể chọn giá trị của k (giá trị mặc định là 20) như Hình 4.4. Hình 4.3 - Màn hình rút trích lược đồ từ web form 78 Hình 4.4 - Màn hình so khớp lược đồ 4.4. Thử nghiệm và đánh giá 4.4.1. Độ đo sử dụng để đánh giá Đánh giá các thuật toán được thực hiện dựa vào ba độ đo phổ biến có nguồn gốc từ lĩnh vực tìm kiếm thông tin là độ chính xác, độ phủ và độ đo F. Các độ đo này được tính như sau: Các ánh xạ lược đồ được phân thành 4 tập như sau: • A (False negatives) tập những ánh xạ phần tử mà các thuật toán so khớp tự động không xác định được. • B (true positives) tập những ánh xạ phần tử mà các thuật toán so khớp tự động xác định đúng. • C (false positives) tập những ánh xạ phần tử mà các thuật toán so khớp tự động xác định sai. 79 • D (True negatives) tập những ánh xạ phần tử không chính xác mà các thuật toán so khớp tự động đã loại bỏ. C và A làm giảm chất lượng so khớp. Độ chính xác = CB B + Độ chính xác là tỷ lệ giữa các tương ứng tìm thấy chính xác trên toàn bộ các tương ứng được tìm thấy Độ phủ = BA B + Độ phủ là tỷ lệ giữa tương ứng được tìm thấy trên toàn bộ tương ứng giữa hai lược đồ. Trong trường hợp lý tưởng, khi tập những so khớp mà các thuật toán so khớp tự động xác định sai -C và tập những so khớp mà các thuật toán so khớp tự động không xác định được – A đều rỗng, độ chính xác = độ phủ = 1. Tuy nhiên, chỉ sử dụng độ chính xác hoặc độ phủ không thể đánh giá chính xác chất lượng so khớp. Độ phủ có thể dễ dàng đạt tối đa bằng cách trả về tất cả những tương ứng có thể có giữa hai lược đồ, khi đó độ chính xác sẽ giảm đáng kể. Ngược lại, có thể đạt được độ chính xác cao bằng cách chỉ trả về một vài tương ứng chính xác, khi đó độ phủ giảm đáng kể. Vì vậy cần phải xem xét cả hai độ đo này hoặc sử dụng một độ đo kết hợp như độ đo F: 4.4.2. Bộ thử nghiệm Bộ thử nghiệm được dùng trong luận văn là bộ dữ liệu được cung cấp trong hệ thống OntoBuilder với mục đích đánh giá các thuật toán so khớp lược đồ. Bộ dữ liệu này được thu thập từ 86 web form thuộc nhiều miền ứng dụng khác nhau, như 80 thư điện tử, đặt phòng khách sạn, mỹ phNm, mai mối, diễn đàn,... Mỗi cặp lược đồ trong cùng một miền ứng dụng được cung cấp một ánh xạ chính xác do con người thực hiện so khớp. 4.4.3. Quá trình thử nghiệm Quá trình thực nghiệm được tiến hành theo các bước sau: Bước 1 - Phát sinh 5 ma trận tương tự giữa mỗi cặp lược đồ trong bộ dữ liệu thử nghiệm. Sử dụng các thuật toán của hệ thống OntoBuilder phát sinh các ma trận tương tự giữa tất cả các cặp web form có khả năng tương thích miền ứng dụng với nhau. 5 thuật toán lai ghép giữa các bộ so khớp của hệ thống OntoBuilder được sử dụng là {Term, Value, Precedence}, {Term, Value, Composition}, {Term, Composition, Precedence }, {Value, Composition, Precedence}, và {Value, Combine{Term, Value}, Composition}. Bước 2- Phát sinh 5 danh sách top-k ánh xạ lược đồ (với giá trị k thay đổi từ 1 đến 10) Sử dụng thuật toán tìm top-k ánh xạ lược đồ phát sinh 5 danh sách top-k ánh xạ lược đồ từ 5 ma trận tương tự ở bước 1. Bước 3- Phát sinh một danh sách top-k ánh xạ lược đồ có điểm cao nhất (thay đổi ngưỡng t – ngưỡng đánh giá sự tương đương giữa hai ánh xạ lược đồ) Sử dụng thuật toán phân hạnh tổng hợp do luận văn đề xuất để tính điểm cho tất cả các ánh xạ lược đồ trong 5 danh sách top-k ánh xạ lược đồ ở bước 2, và trả về một danh sách k ánh xạ lược đồ có điểm cao nhất. 4.4.4. Kết quả thử nghiệm Luận văn đánh giá thuật toán bằng cách so sánh với 5 thuật toán lai ghép của hệ thống OntoBuilder dùng để phát sinh 5 danh sách top-k đầu vào của thuật toán 81 này (mỗi thuật toán được đánh số tương ứng với thứ tự được liệt kê ở bước 1 trong phần 4.4.3). Thử nghiệm đầu tiên được tiến hành với giá trị k = 10, và ngưỡng t = 0.85 (ngưỡng t là ngưỡng được sử dụng để xác định hai ánh xạ tương đương trong hàm xác định tương đương giữa hai ánh xạ lược đồ, được trình bày trong phần 4.2.1.2), kết quả thử nghiệm được trình bày trong Bảng 4.1. Bảng 4.1- Kết quả thử nghiệm trên bộ dữ liệu thử nghiệm với giá trị k = 10, t = 0.85 Thuật toán Độ chính xác Độ phủ Độ đo F Thuật toán 1 48.0% 79.2% 59.8% Thuật toán 2 47.8% 75.4% 58.5% Thuật toán3 47.5% 78.6% 59.2% Thuật toán4 43.7% 75.3% 55.3% Thuật toán5 43.7% 77.3% 55.8% Thuật toán phân hạng tổng hợp 48.9% 77.4% 59.9% Hình 4.5-Biểu đồ so sánh Độ chính xác và Độ phủ của các thuật toán 82 Hình 4.6-Biểu đồ so sánh độ đo F giữa các thuật toán Nhận xét Trong Hình 4.5 và Hình 4.6, thuật toán phân hạng tổng hợp được đề xuất có độ chính xác và độ đo F cao hơn độ chính xác của các thuật toán đầu vào nhưng độ phủ thấp hơn. Độ phủ thấp hơn có thể do ngưỡng t có giá trị cao. Với t = 0.85, khi xác định hai ánh xạ tương đương, những ánh xạ lược đồ chứa các ánh xạ phần tử chính xác nhưng có tỷ lệ các ánh xạ phần tử chung thấp hơn 0.85 sẽ không được đánh giá tương tương nhau, và do đó điểm của chúng rất thấp thậm chí có thể bằng 0. Điều này xảy ra trong những trường hợp các ánh xạ phần tử chính xác không tập trung trong cùng một ánh xạ lược đồ, mà phân tán ở nhiều ánh xạ lược đồ khác nhau. Để kiểm tra nhận định này, luận văn tiến hành thử nghiệm thứ hai là đo độ chính xác và độ phủ của thuật toán phân hạng tổng hợp với k = 10, giá trị t thay đổi ở 3 mức là 0.5, 0.7 và 0.85. Kết quả so sánh độ phủ khi t = 0.5, 0.7 và 0.85 được thể hiện trong biểu đồ Hình 4.7. 83 Hình 4.7-Biểu đồ Độ chính xác và độ phủ của thuật toán phân hạng tổng hợp khi t thay đổi Nhận xét: Trong hình Hình 4.7, độ phủ của thuật toán cao nhất và độ phủ giảm khi t = 0.85 và t = 0.5. Như vậy nhận định nêu trên là đúng, khi giá trị t cao làm giảm độ phủ của thuật toán. Khi t thấp (t = 0.5) những ánh xạ lược đồ không tương đương vẫn được đánh giá tương đương, còn những ánh xạ lược đồ tương đương lại bị bỏ qua, do đó khi t = 0.5, độ chính xác và độ phủ của thuật toán giảm. Thử nghiệm thứ ba được tiến hành nhằm so sánh thuật toán phân hạng tổng hợp với 5 thuật toán đầu vào khi tăng độ chính xác và giảm độ phủ bằng bằng cách thử nghiệm với giá trị k thay đổi từ 1 đến 10 và t = 0.85. Kết quả thử nghiệm được thể hiện trong biểu đồ Hình 4.8-Biểu đồ so sánh Độ chính xác và Độ phủ của các thuật toán khi k thay đổi 84 Hình 4.9-Biểu đồ so sánh Độ đo F của các thuật toán khi k thay đổi Nhận xét 5 thuật toán đầu vào có độ chính xác giảm dần và độ phủ tăng lên khi k tăng lên. Thuật toán phân hạng tổng hợp có độ chính xác tăng khi k tăng đến 5 và giảm dần khi k có giá trị từ 6 đến 10, còn độ phủ tăng chậm khi k nhỏ hơn năm và tăng nhanh khi k có giá trị từ 6 đến 10. Độ đo F của thuật toán phân hạng tổng hợp của các thuật toán tăng dần khi giá trị k tăng đến 9 và giảm khi k = 10. 4.4.5. Kết luận Kết quả thực nghiệm cho thấy thuật toán phân hạng tổng hợp có thể ứng dụng tốt cho bài toán so khớp, độ chính xác trung bình nó luôn cao hơn các thuật toán đầu vào. Độ bao phủ của thuật toán thấp hơn một số thuật toán đầu vào do việc chọn ngưỡng t trong hàm xác định hai ánh xạ tương đương. Tuy, độ bao phủ thấp hơn một số thuật toán khác nhưng độ đo F của thuật toán phân hạng tổng hợp vẫn cao hơn các thuật toán đầu vào.