Bài toán so khớp ontology

Thứ hai , 15/05/2017, 07:42 GMT+7
     

Bài trước chúng ta đã đi qua vấn đề:

                                                               Bài 1: Phương pháp xây dựng Ontology

                                                               Bài 2: Mô hình Ontology trong lĩnh vực y tê

                                                               Bài 3: Fuzzy Ontology - Ontology mờ

1        Đặt vấn đề:

          Trong các hệ thống mở và tiến hoá, ví dụ như web, những nhóm khác  nhau nói chung thường dùng những ontology khác nhau. Sự không  đồng nhất giữa các ontology có thể xảy ra do một hoặc nhiều nguyên nhân sau đây:

         • Các nhóm làm việc ở các quốc gia khác nhau nên sử dụng các ngôn ngữ khác nhau.

         • Các nhóm sử dụng những thuật ngữ khác nhau trong cùng một ngôn ngữ để biểu diễn các khái niệm.

         • Các nhóm sử dụng các mô hình ontology khác nhau theo mục đích, lĩnh vực chuyên môn của mình,…

          So khớp ontology là một cách tiếp cận hợp lý cho vấn đề hỗn tạp về mặt ngữ nghĩa. Thao tác so khớp nhận hai ontology, chứa một tập các thực thể rời rạc (ví dụ các lớp, các thuộc tính, các bảng, các phần tử XML,…), làm đầu vào và xác định kết quả là các quan hệ (ví dụ, quan hệ tương đương, quan hệ gộp) thoả giữa những thực thể này. Những ánh xạ này có thể được dùng cho nhiều mục đích khác nhau.

2     Bài toán ví dụ:

           Giả sử một công ty thương mại điện tử cần thu mua một công ty khác. Về mặt kĩ thuật, hai công ty này cần hợp nhất cơ sở dữ liệu của các bên. Tài liệu của cả hai công ty đều lưu dưới dạng lược đồ XML, gọi tuần tự là O1 và O2. Bước đầu tiên để hợp nhất là xác định các ứng viên để trộn lại hoặc có quan hệ thứ bậc trong lược đồ hợp nhất. Bước này liên quan đến quá trình so khớp. Ví dụ, các phần tử có nhãn Price trong O1 và O2 là những ứng viên cần được trộn lại, trong khi đó, phần tử có nhãn Digital_Cameras trong O2 vào cần được sắp xếp vào nhóm có nhãn Photo_and_Cameras trong O1. Khi xác định được mối quan hệtương ứng giữa hai lược đồ, bước kế tiếp cần phát sinh, chẳng hạn như, các câu truy vấn tự động dịch các thực thể dữ liệu của hai lược đồ sang lược đồ hợp nhất.

         Nhìn vào ví dụ trên, dễ dàng nhận ra bài toán so khớp ontology không phải là bài toán với lời giải tầm thường. Trong khi các phần tử có nhãn như Electronicsvà  Price được chia sẻ ở  cả O1 và O2, hoặc cặp phần tử có nhãn Personal_Computer và PC có thể được nhận biết trùng khớp một cách trực quan dễ dàng, việc xác định trùng khớp giữa các cặp phần tử có nhãn Name và Brand, Quantity và Amount hay Microprocessors và PC_Board là không đơn giản. Nó có thể cần một chút kiến thức về ngữ nghĩa. Việc so khớp có thể còn gặp khó khăn do sự khác biệt về mặt cấu trúc, ví dụ trong trường hợp cả phần tử có nhãn Cameras_and_Photo và phần tử con Digital_Cameras trong O2 đều cùng có thể ánh xạ vào phần tử có nhãn Photo_and_Cameras trong O1. Cuối cùng, ta cũng để ý đến trường hợp phần tử có nhãn Accessories cùng xuất hiện trong O1 và O2 nhưng trong ngữ cảnh này rõ ràng không phải là một cặp ứng viên để trộn lại. Như vậy, việc so  khớp ontology đòi hỏi nhiều kỹ thuật xử lý hơn việc chỉ so sánh chuỗi thông thường

Hình 1 : Hai lược đồ XML đơn giản cần so khớp

3.    Các định nghĩa:

Định nghĩa 1: Tương ứng - correspondence

Cho hai ontology O và O’, một tương ứng là bộ năm 〈id, e1, e2, n, r〉, trong đó 

- id là định danh đơn nhất của tương ứng đang xét; 

- e1 và e2 lần lượt là thực thể (ví dụ, bảng, phần tử XML, tính chất, lớp, khái niệm…) của O và O’; 

- r là quan hệ (ví dụ, tương đương (=), tổng quát hơn (⊇), rời nhau (⊥),… ) giữa e1 và e2. 

- n là  độ tin cậy theo một cấu trúc toán học nào đó (thông thường trong đoạn [0,1]); 

  Tương  ứng  〈id, e1, e2, n, r〉khẳng  định mối quan hệ r giữa hai thực thể ontology e1 và e2 với độ tin cậy n. Độ tin cậy càng cao, quan hệ càng có khả năng xảy ra.

Theo một số thuật toán so khớp dựa trên phân tích cấu trúc và ngôn ngữ học, độ tin cậy (để quan hệ tương đương xảy ra) giữa các thực thể có nhãn  Photo_and_Cameras trong  O1 và  Cameras_and_Phototrong O2 có thể là 0.67. Giả sử thuật toán so khớp sử dụng ngưỡng 0.55 để xác định phép so khớp, tức là thuật toán xem mọi cặp thực thể có độ tin cậy lớn hơn 0.55 là tương ứng đúng. Như thế, thuật toán so khớp sẽ trả về cho người dùng tương ứng sau: 〈id3,3, Photo_and_Cameras, Cameras_and_Photo, 0.67, =〉. Quan hệ giữa cặp thực thể giống nhau cũng có thể được  xác định theo một cách khác, ví dụ quan hệ tương đương chính xác giữa hai thực thể (không cần phải tính độ tin cậy). Do  đó, kết quả trả  về cho người dùng trong trường hợp này là 〈id3,3, Photo_and_Cameras, Cameras_and_Photo, n/a, =〉

Định nghĩa 2: So khớp – Alignment

Cho hai ontology O và O’, một so khớp A giữa O và O' là:

− Một tập hợp các tương ứng giữa O và O'.

− Một lực lượng nào đó: 1-1, 1-*,…

− Một số siêu dữ liệu bổ sung nào đó (ví dụ ngày tháng, thuộc tính,…)

          Thao tác so khớp xác định phép so khớp A’ cho cặp ontology O và O', mỗi ontology là một tập các thực thể rời rạc, chẳng hạn như lớp, thuộc tính, hay thực thể. Hình 2.2 minh hoạ cho quá trình so khớp tổng quát. Ở đây, một số tham số mở rộng định nghĩa quá trình so khớp là: (i) việc sử dụng so khớp đầu vào A, là cái sẽ được hoàn chỉnh trong quá trình thực hiện so khớp, tham số đầu vào này sẽ được trình bày thêm trong phần tương tác người dùng; (ii) các tham số so khớp, ví dụ, trọng số, ngưỡng; và (iii) tài nguyên bên ngoài mà quá trình so khớp sử dụng đến, ví dụ tri thức phổ biến và từ điển chuyên ngành. Định nghĩa hình thức của một bài toán so khớp như sau:

Định nghĩa 3: Định nghĩa hình thức quá trình so khớp

Quá trình so khớp có thể xem như  một hàm f mà nó nhận vào một cặp ontology cần so khớp O và O', một so khớp đầu vào, một tập các tham số p và một một tập tài nguyên và tri thức r, trả ra một so khớp A’ giữa các ontology này:

Hình 2: Sơ đồ biểu diễn quá trình so khớp ontology

4.   Ứng dụng so khớp ontology:

          So khớp ontology là một tác vụ quan trọng trong các ứng dụng truyền thống, ví dụ phát triển ontology, tích hợp ontology, tích hợp dữ liệu, tích hợp các lược đồ và cất giữ dữ liệu (data warehouse). Thông thường, các ứng dụng này được đặc trưng hoá bởi các mô hình có cấu trúc hỗn tạp mà chúng sẽ được phân tích và so khớp hoặc bằng tay hay bán tự động vào thời điểm thiết kế. Trong những ứng dụng như thế, so khớp là điều kiện tiên quyết để chạy hệ thống thực tế. Hiện đang có một số ứng dụng nổi lên có thể bởi tính động của chúng, ví dụ chia sẻ thông tin ngang hàng, tích hợp dịch vụ web, giao tiếp đa tác nhân, trả lời truy vấn và duyệt web ngữ nghĩa. Các ứng dụng như thế, ngược với những ứng dụng truyền thống,  đòi hỏi thao tác so khớp ngay trong lúc thực thi và có ưu điểm là mô hình có tính khái niệm rõ ràng hơn.

5.    Các kĩ thuật cơ bản:

         Mục đích của so khớp là tìm mối quan hệ giữa những thực thể được biểu diễn trong các ontology khác nhau. Những mối quan hệ này thường là quan hệ tương đương nghĩa  được khám phá qua  độ đo tương tự giữa các thực thể trong các ontology. 

Định nghĩa:(Độ tương tự). Một độ tương tự σ : o × o → R là ánh xạ từ một cặp thực thể thành một số thực biểu diễn sự tương tự giữa hai đối tượng sao cho

  x, y  o, σ(x, y) ≥ 0   (dương)

 x o, y, z o, σ(x, x) ≥ σ(y, z)   (tính tối đại)

  x, y  o, σ(x, y) = σ(y, x)   (đối xứng)

  Dựa vào độ tương tự được sử dụng, các kỹ thuật có thể được chia thành bốn cách tiếp cận: tên gọi, khái niệm, mở rộng và ngữ nghĩa. Có một điểm lưu ý là các kỹ thuật này không thể dùng một cách đơn lẻ, mà mỗi cái trong chúng phải tận dụng các kết quả được cung cấp bởi những kỹ thuật khác. Một phần của nghệ thuật so khớp ontology nằm ở chỗ lựa chọn và kết hợp các phương pháp này theo cách thích hợp nhất. Các mục dưới đây giới thiệu một số nội dung cơ bản của các kỹ thuật này.

 5.1  Các kỹ thuật dựa trên tên

         Một số phương pháp dựa trên tên so sánh các chuỗi. Chúng có thể được áp dụng đối với tên, nhãn hay các chú thích của thực thể để tìm những cặp tương tự. Nó có thể dùng để so sánh tên lớp và/hay các URI (Uniform Resource Identifier). Khó khăn chính trong việc so sánh các thực thể ontology dựa trên cơ sở nhãn của chúng là do sự tồn tại của từ đồng nghĩa và từ đồng âm. Các từ đồng nghĩa là các từ khác nhau dùng để đặt tên cho cùng một thực thể. Ví dụ, “Article” và “Paper” là các từ đồng nghĩa trong một số ngữ cảnh nào đó. Các từ đa nghĩa là các từ dùng  để đặt tên cho các thực thể khác nhau. Ví dụ, “peer” là một danh từ có nghĩa là “người ngang hàng” cũng có một nghĩa khác là “người quý tộc”. Việc một từ có thể có nhiều nghĩa còn được gọi là tính đa nghĩa. Kết quả là, không thể không thể suy luận chắc chắn là hai thực thể tương tự nhau nếu chúng có cùng tên hay chúng khác nhau bởi vì chúng có tên khác nhau.

         Có hai loại phương pháp chính để so sánh các tên dựa vào việc chúng chỉquan tâm  đến chuỗi ký tự hay chúng dùng một số tri thức ngôn ngữ để hiểu những chuỗi này.

       Các phương pháp dựa trên chuỗi tận dụng cấu trúc của chuỗi (là một chuỗi các ký tự). Ví dụ, trong tiếng Anh, dựa vào tiền tố hệ thống có thể xác định sựtương tự của “net” và “network” cũng như “book” với “textbook” nếu dựa vào hậu tố. Tuy nhiên, cách này có thể xác định sai sự tương tự của những từ như“hot” và “hotel” hoặc bỏ qua các cặp quan hệ như “book” và “volume”. Một số độ đo tương tự tiêu biểu cho loại kỹ thuật này là:

          • Độ tương tự dựa trên edit distance (như khoảng cách Hamming, khoảng cách Levenshtein)

          • Độ tương tự chuỗi con

          • Độ tương tự n-gram

         • Độ đo Jaro và độ đo Jaro-Winkler

         • Độ tương tự cosine

         • TFIDF (Term frequency-Inverse Document frequency)

         • Độ tương tự dựa trên khoảng cách đường đi

         Các phương pháp so sánh chuỗi là hữu ích nếu người ta dùng các chuỗi rất tương tự nhau để biểu thị những khái niệm giống nhau. Nếu các từ đồng nghĩa với các cấu trúc khác nhau được dùng, việc này đưa đến độ tương tự thấp. Lựa chọn các cặp chuỗi với độ tương tự thấp có thể đưa đến các kết quả sai bởi vì hai chuỗi có thể rất tương tự nhau nhưng dùng biểu diễn những khái niệm khá khác biệt. Các  độ đo này thường dùng  để phát hiện hai chuỗi rất tương tự có  được dùng hay không. Nếu không, việc so khớp phải dùng các nguồn thông tin đáng tin cậy hơn. Một số gói phần mềm để tính toán khoảng cách chuỗi là: Simetrics, SecondString, Alignment API, SimPack.

         Các phương pháp dựa trên ngôn ngữ dùng các kỹ thuật xử lý ngôn ngữ tự nhiên để giúp rút trích các từ ngữ có ý nghĩa từ văn bản. So sánh những từ ngữnày và quan hệ của chúng có thể giúp đánh giá độ tương tự giữa các thực thể ontology mà chúng đặt tên hoặc chú thích. Mặc dù những phương pháp này dựa trên ngôn ngữ, chúng ta có thể phân biệt chúng dựa là chỉ dựa trên thuật toán hay dùng thêm các tài nguyên bên ngoài như các từ điển. Một số độ tương tự được dùng trong các phương pháp này là:

       • Độ tương tự đồng nghĩa

       • Độ tương tự cosynonymy 

       • Độ tương tự ngữ nghĩa Resnik

       • Độ tương tự lý thuyết thông tin

       • Độ chồng lấp của chú thích

5.2     Các kỹ thuật dựa trên cấu trúc

        Cấu trúc của các thực thể có thể được dùng trong các ontology được so khớp, bên cạnh việc so sánh tên hay định danh của chúng. Sự so sánh này có thể được chia thành so sánh cấu trúc bên trong một thực thể, nghĩa là ngoài tên và nhãn là các thuộc thuộc tính hay, trong trường hợp của OWL ontology, các thuộc tính mà sẽ nhận giá trị trong một kiểu dữ liệu, hoặc so sánh thực thể với các thực thể khác mà chúng có quan hệ. Loại đầu tiên là cấu trúc nội bộ và loại thứ hai được gọi là cấu trúc quan hệ. 

       Các phương pháp dựa trên cấu trúc nội bộ dựa vào cấu trúc bên trong các thực thể và dùng các tiêu chuẩn như tập các thuộc tính, miền giá trị, tính hữu hạn hay vô hạn và tính bắc cầu hay đối xứng của các thuộc tính để tính toán độ tương tự giữa chúng. Một số độ đo được dùng trong các phương pháp này là:

              • Khoảng cách kích thước tương đối

              • Độ tương tự bội số

       Các phương pháp dựa trên cấu trúc quan hệ  sử dụng tập các quan hệ mà thực thể có với các quan hệ khác. Trong phương pháp này, một ontology có thể được xem là một đồ thị với các đỉnh được gán nhãn bởi các tên quan hệ (nói theo toán học, đây là đồ thị của các đa quan hệ của ontology). Việc tìm các tương ứng giữa các phần tử của các đồ thị như thế tương đương với việc giải một dạng của bài toán đẳng cấu đồ thị. Cụ thể là nó có thể được liên hệ với việc tìm một đồ thị con chung tối đại. Một số độ đo của phương pháp này bao gồm:

             • Độ không tương tự topology cấu trúc trong các cấu trúc phân cấp

             • Độ tương tự Wu & Palmer

             • Độ tương tự cotopic hướng lên

5.3     Các kỹ thuật mở rộng

           Việc có sẵn các biểu diễn cá thể (hay thể hiện) là cơ hội rất tốt cho các hệ thống so khớp . Khi hai ontology có chung một tập các cá thể, sự so khớp có thể trở nên dễ dàng hơn. Ví dụ, nếu hai lớp có chính xác cùng một tập các cá thể, thì có thểcó một giả định mạnh rằng những lớp này biểu diễn cho một so khớp đúng. Ngay cả khi các lớp không có chung tập cá thể, những phương pháp này cũng cho phép đặt quá trình so khớp trên những chỉ số xác thực không dễ gì thay đổi.  Ví dụ “title” của “Book” không có lý do gì để thay đổi. Nên nếu “title” của “Book” là khác nhau, thì hầu như chắc chắn chúng không phải là như nhau. Khi đó, việc so khớp một lần nữa có thể dựa trên việc so sánh cá thể. Do đó các phương pháp mở rộng được chia thành ba loại: những phương pháp áp dụng với các ontology có các tập thể hiện chung, những phương pháp áp dụng kỹ thuật nhận diện thể hiện trước khi dùng những kỹ thuật mở rộng và những phương pháp không cần việc nhận diện. Các phương pháp so sánh mở rộng chung đơn giản thực hiện kiểm tra phần giao của các thể hiện giữa hai tập. Một số độ đo của phương pháp này là:

           • Khoảng cách Hamming

           • Độ tương tự Jaccard

         Các kỹ thuật nhận diện thể hiện cố gắng nhận diện thể hiện nào từ một tập là tương ứng với thể hiện khác từ tập khác, nếu giữa hai tập không tồn tại một tập thể hiện con chung. Phương pháp này hữu ích khi biết rằng các thể hiện là nhưnhau. Ví dụ, phương pháp này hoạt động được khi tích hợp cơ sở dữ liệu nhân sự của cùng công ty, nhưng không áp dụng được với những công ty khác nhau hay cơ sở dữ liệu của các sự kiện mà chúng không có quan hệ nào cả. Các phương pháp so sánh mở rộng rời nhau sử dụng các kỹ thuật xấp xỉ để so sánh các mở  rộng lớp khi không thể trực tiếp suy luận ra một tập dữ liệu chung giữa hai ontology. Các phương pháp này có thể dựa trên độ đo thống kê về các đặc trưng của các thành viên lớp, dựa trên độ tương tự được tính giữa các thể hiện hay các lớp hoặc dựa vào việc so khớp giữa các tập thực thể. Một số độ đo của các phương pháp này là:

           • Khoảng cách Hausdorff

           • Độ tương tự dựa trên trùng khớp

  Các kỹ thuật dựa trên ngữ nghĩa

          Đặc điểm chính của những phương pháp ngữ nghĩa là dùng các ngữ nghĩa theo lý thuyết mô hình để đánh giá các kết quả. Do đó chúng là các phương pháp suy diễn. Dĩ nhiên, các phương pháp suy diễn nếu chỉ đơn thuần hoạt động một mình sẽ không có nhiều hiệu quả đối với nhiệm vụ suy diễn cơ  bản như so khớp ontology. Do đó chúng cần một bước tiền xử lý cung cấp các điểm neo, ví dụ các thực thể được khai báo là tương đương (dựa vào việc nhận diện theo tên hay do người dùng nhập vào đối với thể hiện). Các phương pháp ngữ nghĩa đóng vai trò như bộ khuếch đại cho những so khớp hạt giống này. Các phương pháp này dựa trên việc sử dụng tài nguyên hình thức đang có để khởi tạo một so khớp mẫu mà chúng có thể được xem xét sâu hơn. Các kỹ thuật này bao gồm các kỹ thuật dựa trên các ontology bên ngoài  và các kỹ thuật suy diễn.

6.    Các Chiến lược So khớp

          Các kỹ thuật cơ bản được giới thiệu ở phần trên là các khối cơ bản mà dựa trên đó người ta xây dựng lời giải so khớp. Khi  độ  tương tự giữa các thực thể ontology đã sẵn sàng, phần còn lại là tính so khớp. Việc này liên quan nhiều hơn đến các giải pháp toàn cục. Cụ thể, việc xây dựng một hệ thống so khớp hoạt động thường gồm các mặt sau:

           -  Tổng hợp các kết quả của các phương pháp cơ bản để tính độ tương tự phức giữa các thực thể và tổ chức tổ hợp các độ tương tự hay các thuật toán so khớp khác nhau.

           -  Phát triển một chiến lược để tính những độ tương tự này bất chấp các chu trình và sự phi tuyến trong các ràng buộc bao trùm các độ tương tự.

           -  Học từ dữ liệu phương pháp tốt nhất và các tham số tốt nhất để so khớp.

           -   Sử dụng các phương pháp xác suất để kết hợp các chương trình so khớp hay để suy diễn ra các tương ứng còn thiếu.

           -   Đưa người dùng vào quá trình so khớp.

           -  Rút trích các so khớp từ các độ tương tự kết quả: thực vậy, các so khớp với các đặc điểm khác nhau có thể được rút ra từ cùng một độ tương tự. 

 

ontology so khop bai toan so khop tri tue nhan tao nang cao ai uit fuuzy mờ do an AI