Thuật toán mới về so khớp ontology
TÓM TẮT – So khớp ontology (ontology matching) là một phần quan trọng trong kỹ nghệ ontology của Web ngữ nghĩa với
mục tiêu tìm kiếm các so khớp (alignment) giữa các thực thể của các ontology đã cho. Trong nghiên cứu này chúng tôi đề xuất thuật
toán mới và một công cụ dựa trên thuật toán này để tìm sự tương đồng giữa các thực thể của các ontology đầu vào. Thuật toán đề
xuất này sử dụng độ đo mới về sự tương đồng của từ vựng và cũng sử dụng thông tin về cấu trúc của các ontology để xác định thực
thể tương ứng của chúng. Độ đo sự tương đồng về từ vựng tạo ra một tập từ cho mỗi thực thể dựa trên nhãn và thông tin mô tả của
chúng. Cách tiếp cận về cấu trúc tạo thành một mạng lưới cho mỗi nút trong các ontology. Sự kết hợp của phương pháp tiếp cận về
từ vựng và cấu trúc tạo thành ma trận đồng dạng giữa ontology nguồn và ontology đích. Thuật toán đề xuất này đã được thử
nghiệm dựa trên các chuẩn đã được công nhận và cũng được so sánh với các thuật toán khác hiện nay. Kết quả thực nghiệm của
chúng tôi cho thấy thuật toán đề xuất rất hiệu quả và nhanh hơn so với các thuật toán khác.
Tóm tắt nội dung tài liệu: Thuật toán mới về so khớp ontology
![Thuật toán mới về so khớp ontology Thuật toán mới về so khớp ontology](https://s1.tailieuvn.net/xb70nb5jd4llaq8g/thumb/2022/01/01/thuat-toan-moi-ve-so-khop-ontology_HxdNTPCqzJ.jpg)
Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 DOI: 10.15625/vap.2015.000210 THUẬT TOÁN MỚI VỀ SO KHỚP ONTOLOGY Huỳnh Nhứt Phát1, Hoàng Hữu Hạnh2, Phan Công Vinh3 1Đại học Huế 2Đại học Huế 3Trường Đại học Nguyễn Tất Thành TP. HCM huynhnhutphat@yahoo.com, hhhanh@hueuni.edu.vn, pcvinh@ntt.edu.vn TÓM TẮT – So khớp ontology (ontology matching) là một phần quan trọng trong kỹ nghệ ontology của Web ngữ nghĩa với mục tiêu tìm kiếm các so khớp (alignment) giữa các thực thể của các ontology đã cho. Trong nghiên cứu này chúng tôi đề xuất thuật toán mới và một công cụ dựa trên thuật toán này để tìm sự tương đồng giữa các thực thể của các ontology đầu vào. Thuật toán đề xuất này sử dụng độ đo mới về sự tương đồng của từ vựng và cũng sử dụng thông tin về cấu trúc của các ontology để xác định thực thể tương ứng của chúng. Độ đo sự tương đồng về từ vựng tạo ra một tập từ cho mỗi thực thể dựa trên nhãn và thông tin mô tả của chúng. Cách tiếp cận về cấu trúc tạo thành một mạng lưới cho mỗi nút trong các ontology. Sự kết hợp của phương pháp tiếp cận về từ vựng và cấu trúc tạo thành ma trận đồng dạng giữa ontology nguồn và ontology đích. Thuật toán đề xuất này đã được thử nghiệm dựa trên các chuẩn đã được công nhận và cũng được so sánh với các thuật toán khác hiện nay. Kết quả thực nghiệm của chúng tôi cho thấy thuật toán đề xuất rất hiệu quả và nhanh hơn so với các thuật toán khác. Từ khoá – lexical similarity, ontology matching, similarity measure, structure similarity. I. GIỚI THIỆU Các ontology là các mô hình khái niệm chia sẻ về một miền ứng dụng, cho nhiều người tham gia. Các ontology cho Web ngữ nghĩa được biểu diễn bởi RDFS hoặc OWL, đóng một vai trò rất quan trọng trong Web ngữ nghĩa. So khớp ontology được đề xuất như là một giải pháp tốt cho việc chia sẻ và tái sử dụng kiến thức, bằng cách cung cấp một cơ chế hình thức để xác định ngữ nghĩa của dữ liệu. Nó đóng một vai trò quan trọng trong việc mở rộng và sử dụng các ứng dụng dựa trên Web ngữ nghĩa [1]. Những năm gần đây có rất nhiều ontology được tạo ra với các miền khác nhau. So khớp ontology cho phép dữ liệu và tri thức được biểu diễn trong các ngôn ngữ khác nhau và các định dạng được chia sẻ. Chẳng hạn, với hai ontology ở đầu vào và tạo ra các so khớp (alignment) ở đầu ra. Các so khớp này là một tập hợp liên quan giữa các thực thể tương ứng về ngữ nghĩa, như là các lớp được đặt tên, các thuộc tính đối tượng và các thuộc tính dữ liệu của các ontology đầu vào. Trong bài báo này chúng tôi trình bày phương pháp tổ hợp để tìm sự tương ứng giữa các thực thể (ví dụ: các lớp được đặt tên, các thuộc tính đối tượng và các thuộc tính dữ liệu) của các ontology, dựa trên sự tương đồng về từ vựng và cấu trúc của chúng. Trước tiên, chúng tôi xác định sự tương đồng về từ vựng trong số các lớp được đặt tên (các nút trong ontology), các thuộc tính đối tượng (các cạnh trong ontology) và các thuộc tính dữ liệu (các giá trị), sử dụng độ đo khoảng cách mới, nó tạo ra một túi từ (bag of words) cho mỗi thực thể trong các ontology đã cho. Các túi sau đó, được so sánh với nhau để tính toán sự tương đồng về từ vựng giữa hai thực thể với kiểu giống nhau (ví dụ như hai lớp được đặt tên) từ hai ontology. Vì vậy, việc sử dụng độ đo khoảng cách này, chúng tôi đưa ra ba ma trận khác nhau về từ vựng, nó tương ứng với các đặc điểm giống nhau của các lớp được đặt tên, các thuộc tính đối tượng và các thuộc tính dữ liệu của ontology nguồn và ontology đích. Thứ hai, chúng tôi tìm kiếm điểm tương đồng giữa các nút (các lớp được đặt tên) của ontology nguồn và ontology đích dựa trên các cấu trúc ontology của chúng. Nói cách khác, chúng tôi tạo ra một mạng lưới gồm nhiều nút, với mỗi nút sử dụng các nút lân cận của nó trong ontology nguồn và ontology đích để so sánh về mặt cấu trúc giữa chúng. Cuối cùng, trong giai đoạn này, ba ma trận có được ở các giai đoạn trước đó tương đồng về từ vựng và tương đồng về cấu trúc sẽ được kết hợp và sử dụng thêm kỹ thuật để tạo ra ma trận tương đồng toàn diện. Chúng ta biết rằng so khớp ontology tạo ra sự tương ứng giữa các thực thể của hai ontology. Trong bài báo này chúng tôi trình bày thêm công cụ OMReasoner, nó tạo ra một khung ứng dụng có thể mở rộng về sự kết hợp của nhiều công cụ so khớp riêng lẻ và từ điển WordNet cũng như logic mô tả được sử dụng trong việc phân tích so khớp ontology. Nó xử lý so khớp ontology ở cả hai cấp độ từ và ngữ nghĩa, và nó sử dụng phần ngữ nghĩa cũng như cấu trúc của OWL-DL. Chúng tôi trình bày kết quả đạt được của OMReasoner với OAEI 2014 theo ba phương pháp: Benchmark, Conference và MultiFarm. Bài báo được tổ chức như sau: Phần I giới thiệu. Phần II khảo sát các nghiên cứu liên quan. Phần III thảo luận với thuật toán đề xuất chi tiết. Phần IV đưa ra một ví dụ minh họa. Phần V trình bày các kết quả thực nghiệm và công cụ được triển khai dựa trên thuật toán đã mô tả. Phần VI trình bày công cụ OMReasoner có thể mở rộng về sự kết hợp nhiều công cụ so khớp riêng lẻ, Phần VII các kết luận và nhận xét. II. CÁC NGHIÊN CỨU LIÊN QUAN Trong phần này chúng tôi khảo sát các phương pháp tiếp cận đã được đề xuất cho việc so khớp ontology [3-10]. Những phương pháp tiếp cận này có thể được chia thành bốn loại: từ vựng, ngữ nghĩa, cấu trúc và tổ hợp. 696 THUẬT TOÁN MỚI VỀ SO KHỚP ONTOLOGY Phương pháp tiếp cận về từ vựng là phương pháp dựa trên chuỗi để nhận dạng các thực thể tương đồng nhau trong các ontology đã cho. Phương pháp này có thể được dùng để nhận dạng các lớp tương đồng trong các ontology nguồn và ontology đích dựa trên sự giống nhau về nhãn hoặc về việc miêu tả của chúng [3]. Các kỹ thuật này xem các chuỗi có trình tự của các chữ cái. Chúng dựa trên sự nhận biết sau đây: các chuỗi giống nhau nhiều hơn, nhiều khả năng chúng biểu thị các khái niệm giống nhau. Việc so sánh các kỹ thuật so khớp chuỗi khác nhau, từ các vấn đề về khoảng cách đến các vấn đề dựa trên token có thể tìm thấy trong [4]. Một số ví dụ của các kỹ thuật dựa trên chuỗi được sử dụng rộng rãi trong các hệ thống so khớp là tiền tố, hậu tố, chỉnh sửa khoảng cách và n-gram. Các phương pháp tiếp cận tiền tố và hậu tố của hai chuỗi đầu vào và kiểm tra xem chuỗi thứ nhất có bắt đầu (kết thúc) so với chuỗi thứ hai hay không. Phương pháp tiếp cận này hiệu quả trong việc so khớp các chuỗi có cùng nguồn gốc và các từ viết tắt tương tự nhau (ví dụ int và integer). Các phương pháp tiếp cận chỉnh sửa khoảng cách của hai chuỗi đầu vào được tính toán để chỉnh sửa khoảng cách giữa chúng. Chỉnh sửa khoảng cách là số các ký tự được chèn vào, xóa đi hay thay thế để chuyển đổi một chuỗi này thành một chuỗi khác, được chuẩn hóa theo chiều dài của chuỗi dài hơn. Ví dụ, MLMA+algorithm [9] sử dụng khoảng cách Levenshtein [6] để chỉnh sửa khoảng cách và tính toán sự tương đồng về từ vựng giữa hai thực thể. Phương pháp tiếp cận dựa trên N-gram của hai chuỗi đầu vào và tính toán số lượng n-grams (tức là trình tự của n ký tự) giữa chúng. Ví dụ, 3-grams của chuỗi ‘nikon’ là ‘nik’, ‘iko’, ‘kon’. Vậy, khoảng cách giữa ‘nkon’ và ‘nikon’ dựa trên 3-grams sẽ là 1/3. Với phương pháp tiếp cận ngữ nghĩa theo cách thông thường là một hoặc nhiều tài nguyên về ngôn ngữ như từ vựng và từ điển chuyên ngành được sử dụng để xác định các thực thể đồng nghĩa [3]. Những phương pháp tiếp cận này thường sử dụng kiến thức phổ thông hoặc từ điển thuộc miền cụ thể để so khớp các từ dựa trên các mối quan hệ ngôn ngữ giữa chúng (ví dụ: các từ đồng nghĩa, các từ có nghĩa hẹp so với từ khái quát). Trong trường hợp này, tên các thực thể của ontology được xem như các từ của ngôn ngữ tự nhiên. Một số phương pháp tiếp cận sử dụng từ điển kiến thức phổ thông để có được ý nghĩa của các thuật ngữ sử dụng trong các ontology. Ví dụ, WordNet [7] là một cơ sở dữ liệu điện tử về từ vựng tiếng Anh (và các ngôn ngữ khác), trong đó các từ có nghĩa riêng biệt được đặt vào các bộ từ đồng nghĩa. Các quan hệ giữa các thực thể ontology có thể được tính toán liên quan đến các các ràng buộc về nghĩa trong WordNet [8-9]. Các phương pháp tiếp cận khác sử dụng từ điển về tên miền cụ thể thường lưu trữ một số kiến thức về miền cụ thể, nó không có sẵn trong bộ từ điển kiến thức phổ thông (ví dụ như tên riêng), như truy cập với từ đồng nghĩa, các từ có nghĩa hẹp so với từ khái quát và các mối quan hệ khác. Các phương pháp tiếp cận về cấu trúc nhận dạng các lớp giống nhau (các nút) bằng cách quan sát các đối sánh của chúng với các lớp khác dựa vào ontology được đề cập và các thuộc tính của chúng nữa. Ý tưởng chính với hai lớp của ontology nguồn và ontology đích là tương đồng nếu chúng có những lân cận giống nhau (các cấu trúc) và các thuộc tính giống nhau [2]. Ví dụ, GMO là một thuật toán về cấu trúc, nó sử dụng đồ thị hai bên tách biệt (bipartite graphs) để miêu tả các ontology. Nó đo các đồ thị tương đồng về cấu trúc bởi một phép đo mới. Tuy nhiên, GMO có một tập các cặp đối sánh, chúng thường được tìm thấy trước bởi các phương pháp tiếp cận khác, với dữ liệu nhập vào từ bên ngoài trong quá trình so khớp của nó. Một số so khớp khác về cấu trúc được sử dụng để so sánh các ontology, chúng so khớp dựa trên các nút con, các nút lá và các mối quan hệ. Trong trường hợp đối sánh, hai thực thể không phải nút lá được xem là tương đồng nếu chúng có các nút con hoặc các nút lá lần lượt tương đồng nhau. Trong quan hệ đối sánh, việc tính toán giữa các nút tương đồng cũng có thể dựa vào các mối quan hệ (thuộc tính đối tượng) của chúng [10]. Các phương pháp tiếp cận về tổ hợp, chúng kết hợp hai hoặc nhiều các phương pháp tiếp cận nói trên (tức là sự kết hợp về từ vựng, ngữ nghĩa và phương pháp tiếp cận về cấu trúc) để có được kết quả tốt hơn. MLMA+algorithm [5] và phiên bản cải tiến của nó là tổ hợp các phương pháp tiếp cận, nó sử dụng một kỹ thuật tìm kiếm lân cận, nó thực hiện ở hai cấp độ. Ở cấp độ đầu tiên, đo sự tương đồng về hai từ vựng của hai ontology đầu vào. Trường hợp này là đo sự tương đồng theo tên, nó sử dụng khoảng cách Levenshtein [6] và đo sự tương đồng về từ vựng, nó sử dụng WordNet [7]. Ở cấp độ thứ hai, các thuật toán được áp dụng đo sự tương đồng về cấu trúc để tìm các giải pháp so khớp tốt nhất. III. PHƯƠNG PHÁP TỔ HỢP ĐỂ ĐỐI SÁNH CÁC ONTOLOGY Trong phần này chúng tôi miêu tả phương pháp tổ hợp của chúng tôi trong so khớp các ontology dựa trên sự tương đồng về từ vựng và sự tương đồng về cấu trúc của chúng. Phương pháp đề xuất này bao gồm ba giai đoạn để tìm các đối sánh giữa ontology nguồn và ontology đích. Ở giai đoạn thứ nhất và giai đoạn thứ hai, các ontology đầu vào được so khớp tương ứng về từ vựng và về cấu trúc. Sau đó, ở giai đoạn thứ ba các kết quả tiếp nhận từ hai giai đoạn trước được kết hợp lại để tạo ra kết quả tổng thể. Các chi tiết của ba giai đoạn này được giải thích trong các mục tiếp theo. A. Các thực thể so khớp về từ vựng giữa hai ontology Các phương pháp tiếp cận so khớp tương đồng về từ vựng là các phương pháp dựa trên chuỗi của các thực thể tương đồng được xác định trong các ontology đã cho. Ở đây, chúng tôi tìm kiếm sự tương đồng về từ vựng được tách biệt giữa các thực thể (các lớp được đặt tên, các thuộc tính đối tượng và các thuộc tính dữ liệu) của ontology nguồn và ontology đích. Vì vậy, giai đoạn này chúng tôi sẽ đưa ra ba ma trận riêng biệt tương đồng về từ vựng như là đầu ra của nó. Chúng tôi giới thiệu độ đo mới tương đồng về khoảng cách để xác định sự tương đồng về từ vựng của các ontology đầu vào. Giả sử chúng tôi muốn tính toán sự tương đồng về từ vựng giữa chuỗi s và chuỗi t. Các chuỗi này có thể là một từ hoặc một văn bản chứa một số các phát biểu (statements). Lúc đầu, chúng tôi chuyển mỗi chuỗi ký tự Huỳnh Nhứt Phát, Hoàng Hữu Hạnh, Phan Công Vinh 697 thành chuỗi các token bằng cách sử dụng các dấu phân cách, sau khi chuyển đổi thành các token sẽ đưa vào một túi từ. Bất kỳ ký tự trong chuỗi đã cho không thuộc bảng chữ cái sẽ được xem như là một dấu phân cách. Ví dụ, nếu chuỗi ký tự s chứa hai ký tự không thuộc bảng chữ cái thì chúng tôi xem hai ký tự như là hai dấu phân cách và loại bỏ chúng ra khỏi chuỗi s. Kết quả là, chuỗi s sẽ chuyển đổi thành ba token tức là ba từ. Mỗi chuỗi s và t sau khi được chuyển đổi thành các token sẽ cho vào mỗi túi từ tương ứng, mỗi từ mà chung cho hai túi sẽ bị loại bỏ khỏi hai túi. Sau đó, nếu không còn gì trong túi thứ nhất và túi thứ hai, khoảng cách giữa hai chuỗi đầu vào sẽ là zero. Mặt khác, tất cả các từ còn lại trong mỗi túi sẽ được kết nối và dẫn đến khoảng cách tương đồng Levenshtein [6] được tính toán giữa hai từ. Sau khi tính toán khoảng cách giữa chuỗi s và t, thì sự tương đồng của chúng sẽ là phương trình sau đây: Lexical_Similarityሺs, tሻ ൌ 1 −݀݅ݏݐܽ݊ܿ݁ሺݏ, ݐሻ ݉ܽݔ_݈݁݊ሺݏ, ݐሻ⁄ (1) trong đó distance là khoảng cách giữa chuỗi s và t, và max_len là độ dài tối đa của chuỗi s và t. Hãy xét ví dụ sau đây: s = “Part Of” t = “is_part_of” bag_of_words(s) = {“Part”, “Of”} bag_of_words(t) = {“is”, “part”, “of”} Sau khi tạo các túi từ, chúng tôi loại bỏ hai từ “part” và “of” ra khỏi hai túi từ. Đến đây, chúng tôi sẽ có các túi sau: bags_of_words(s) = {} bags_of_words(t) = {“is”} Cuối cùng, sự tương đồng giữa chuỗi s và t sẽ là: Levenshtein_distance(“”, “is”) = 2 ܮ݁ݔ݈݅ܿܽ_ݏ݈݅݉݅ܽݎ݅ݐݕሺݏ, ݐሻ ൌ 1 െ ݀݅ݏݐܽ݊ܿ݁ሺݏ, ݐሻmax _݈݁݊ሺݏ, ݐሻ൨ ൌ 1 െ ܮ݁ݒ݁݊ݏ݄ݐ݁݅݊_݀݅ݏݐܽ݊ܿ݁ሺ"", "݅ݏ"ሻ max ሺ7,10ሻ ൨ ൌ 1 െ 2 10ൗ ൌ 0.80 Chúng tôi tính toán riêng biệt sự tương đồng về từ vựng trong số các lớp được đặt tên, các thuộc tính đối tượng và các thuộc tính dữ liệu của hai ontology đầu vào, sử dụng độ đo nói trên và sau đó tạo ra ba ma trận riêng biệt tương đồng về từ vựng. B. Các thực thể so khớp về mặt cấu trúc giữa hai ontology Trong phần này, chúng tôi đưa ra phương pháp so khớp về mặt cấu trúc giữa hai ontology đầu vào, trong Hình 1 cho thấy sơ đồ của phương pháp này (có độ phức tạp thuật toán O(n2)). Sau đây là các bước để tạo ra cấu trúc ma trận tương đồng giữa ontology nguồn và ontology đích: 1. Tạo một ma trận lân cận đối với mỗi ontology. 2. Tạo một dãy các danh sách liên kết đối với mỗi ontology dựa trên ma trận lân cận của nó. 3. Tính toán sự tương đồng về cấu trúc trong số các nút của ontology nguồn và ontology đích bằng cách sử dụng danh sách liên kết của chúng và tạo ra ma trận khởi tạo (ban đầu) tương đồng về cấu trúc. 4. Cải thiện ma trận khởi tạo tương đồng về cấu trúc bằng cách sử dụng ba thao tác bổ sung (bước 4, Hình 1). Các bước trên sau đây được mô tả một cách chi tiết. Để so sánh cấu trúc hai ontology đầu vào, chúng tôi tạo ra một mạng lưới gồm các nút của mỗi ontology. Những nút này sẽ được so sánh với mỗi nút của ontology khác dựa trên mạng lưới của chúng. Lưới này được mô phỏng bằng cách sử dụng một dãy các danh sách liên kết (tức là một dãy hai chiều). Điểm quan trọng của phương pháp này là số nút lân cận của một nút, cách thức chúng liên quan với nhau và với nút này (Hình 2). Chúng tôi xem hai nút trong một ontolo ... tương ứng có Hth c r ( r s 2 a c h c b c c c l uỳnh Nhứt Phát, ể thực hiện b ách sử dụng c Khung iêng lẻ. 3. Quá Description L Cuối cù ecall. Với OM o khớp riêng . Các kỹ thu ) Ngưỡng Ngưỡng hỉnh sửa của ai thực thể là húng tôi phải ) Kết hợp độ Mỗi cô huẩn hoá trướ • Thuật Độ tin ho một công • Phươ Độ đo t ) So khớp ng OMRea ogic mô tả (D Hoàng Hữu Hạn ằng cách sử hiến lược cụ ứng dụng sẽ h trình suy di ogic), trong đ ng, chúng tôi Reasoner, kh lẻ bao gồm Ed ật sử dụng cụ rất cần thiết “book” và “b tương đồng ( điều chỉnh cô đo tin cậy ng cụ so khớp c khi kết hợp toán tổng hợ cậy có thể đư cụ so khớp k simሺeଵ ng pháp cực đ in cậy cực đạ sim(e1 ữ nghĩa soner sử dụn L - Descriptio h, Phan Công Vi dụng từ điển thể. ỗ trợ về việc ễn: ngữ ngh ó các tương đ đánh giá các ung ứng dụn itDistance và Hìn Hình 6. M thể đối với nhiều ooklet” là 3/7 với độ do tin ng cụ so khớp riêng lẻ có . OMReasone p trọng số (W ợc tổng hợp b cụ thể và sim , eଶሻ ൌ ∑୬୩ୀଵ ại (Max) i được chọn tr , e2) = max(si g các phương n Logic). nh bên ngoài nh kết hợp các c ĩa tương ứng ồng về từ đượ kết quả dựa g rất linh hoạ WordNet (H h 5. So khớp inh hoạ về các công cụ so k (tức là, các đ cậy 0.57); ng thông qua n thể tạo ra các r bao gồm cá eightSum) ằng thuật toá k(e1, e2) là độ w୩ ൈ sim୩ሺe ong số n công m1(e1, e2), pháp so khớp ư WordNet. ông cụ đối sán có thể đượ c sinh ra ở bư vào các đối s t đối với các ình 5). ontology trong công cụ so khớ hớp (đặc biệt ộ đo tin cậy t ược lại nếu ng gưỡng. độ đo tin cậy c chiến lược li n tương đồng tin cậy của s ଵ, eଶሻ, trong đ cụ so khớp ( , simn(e1, e2 ngữ nghĩa n Sau đó, nhiều h, tạo điều ki c suy diễn b ớc 2 được xe ánh liên quan công cụ so kh OMReasoner p trong OMRea là cú pháp) v ương đồng là ưỡng là 0.6, tương ứng. nh hoạt sau đ về trọng số ( ự tương đồng ó ∑ w୩୬୩ୀଵ ൌ công thức 2). )) hư công cụ so kết quả so k ện thuận lợi c ằng cách sử m là đầu vào. , và tính toán ớp riêng lẻ. H soner ề sự tương đồ 1-3/7=0.57). thì chúng khô Tất cả các độ ây để kết hợp công thức 1), . 1.0 khớp WordN hớp được kết ho các công dụng logic hai độ đo: pr iện nay, nhiề ng. Ví dụ, kh Nếu ngưỡng ng tương đồn đo tin cậy nà các kết quả đ trong đó wk et và việc su 703 hợp bằng cụ so khớp mô tả DL ecision và u công cụ oảng cách là 0.55, thì g. Vì vậy, y sẽ được ối sánh: là trọng số (1) (2) y diễn bởi 7m đ b s p B p W 1 đ đ n p c n = 2 th ( 3 V n đ q ( k th C 04 WordN ột từ hay cụm ược tính toán ên ngoài như OMRea o khớp ontolo hiên bản này, . Kết quả củ Trong p hương pháp: indows Serv . Phương ph Với phư ược thay đổi ịnh danh với goài. Trong n hân cấp. Tron ho phép hoán gưỡng của W 0.95, τed = 0. . Phương ph Tập dữ ống của chú τwd = 0.9, τed = . Phương ph Phương ới phương p hau. Trong nh Trước h ược dịch sẽ đ uả. Chúng tôi τwd = 0.8, τed = ém hơn so vớ iết kế tốt để Để chọ onference. T et là một cơ s từ) của các với các thuật WordNet để soner sử dụn gy. Tuy nhiê khả năng suy a OMReason hần này, chú Benchmark, er 2008 R2 S áp Benchmark ơng pháp này để thay thế cá các tên khác t hóm 2 có các g nhóm 3 cá vị của các t ordNet, τed: n 9; S = Max). áp Conferenc liệu tin cậy b ng tôi theo ph 0.8; S = Ma áp MultiFarm pháp MultiF háp này, các óm 2 các đối ết, chúng tôi ưa vào các cô điều chỉnh cô 0.6; S = Ma i các đối sán so khớp với c n ngưỡng tốt uy nhiên, chú ở dữ liệu điệ từ được sắp ngữ ràng bu đạt được sự tư g logic mô tả n, khả năng s diễn được bỏ er theo từng p ng tôi trình bà Conference v tandard với bộ , các ontolog c nhãn hoặc đ heo một quy ontology thu c ontology đư ừ có chiều d gưỡng của Ed Các kết quả đ Bảng e ao gồm các o ương pháp C x). Bản arm bao gồm ontology có sánh ontolog sử dụng từ đ ng cụ so khớ ng cụ của ch x), trong đó c h ontology tr ác ontology k Bả hơn, chúng ng tôi vẫn sử n tử về từ vựn xếp tạo thành ộc về nghĩa c ơng ứng về n DL được cun uy diễn mất n qua. hương pháp y các kết quả à MultiFarm. vi xử lý Inte y có thể được ịnh danh về ước đặt tên cụ hẹp hệ thống ợc thách thứ ài cụ thể. Ch itDitance) và ạt được từ OM Bảng 3. Phâ 4. Các kết qủa ntology thực onference. C g 5. Kết quả đạ một tập con thể được chia y đều khác nh iển để dịch c p bằng cách s úng tôi bằng c ho thấy các đ ong nhóm 1. hác là vì chún ng 6. Các kết q tôi so sánh dụng chiến g tiếng Anh, các bộ từ đồ ủa WordNet. gữ nghĩa. g cấp bởi Jen hiều thời gian thực hiện đạt được từ O Các thử ngh l Core i5 chạy chia thành 3 chúng. Sự tha thể, một tên phân cấp, mở c lớn nhất về úng tôi điều c kết hợp chiến Reasoner the n loại theo chu đạt được theo B tế. Chúng tôi ác kết quả đạt t được theo Co của tập dữ liệ thành 2 loại au. ác ngôn ngữ ử dụng chiến ách sử dụng ộ đo F-Measu Chúng tôi thấ g được viết b uả đối với Mu các kết quả ( lược về phươ THU trong đó các ng nghĩa. Cá Công cụ so k a. OMReason và chỉ góp m MReasoner v iệm được tiến ở 2.8 Ghz và loại (Bảng 3) y đổi này bao ngẫu nhiên, m rộng hệ thốn đối sánh onto hỉnh công cụ lược S, sau đ o Benchmark ẩn 2014 enchmark 201 sử dụng chiến được từ OM nference 2014 u kết hợp, đư . Trong nhóm khác nhau sa lược Max. Cu ngưỡng và cá res của các đ y rằng những ằng các ngôn ltiFarm 2014 Bảng 7) trên ng pháp Max ẬT TOÁN MỚI nghĩa khác n c quan hệ giữ hớp riêng lẻ n er bao gồm c ột phần nhỏ ới OAEI 201 hành trên m 16 GB RAM . Trong nhóm gồm việc tha ột tên sai ch g phân cấp h logy. Ở đây bằng cách s ó nhận được được tóm tắ 4 lược kết hợp Reasoner đượ ợc dịch với tá 1 các đối sá ng tiếng Anh ối cùng chún c kết quả có t ối sánh ontol lý do mà OM ngữ hoàn toàn một số ngư để thực hiện VỀ SO KHỚP O hau (các nghĩ a các thực th ày sử dụng m ác luật suy di cho các kết q 4. Nó thực hi ột máy tính . 1, thông tin y thế các nhã ính tả hoặc m oặc tất cả đều các nhãn đượ ử dụng ngưỡ các kết quả t t trong Bảng 4 để thực thi c c tóm tắt tro m ngôn ngữ nh ontology . Sau đó, tiến g tôi nhận đư hể hiển thị tro ogy ở nhóm 2 Reasoner k khác nhau. ỡng theo phư công cụ của NTOLOGY a có thể là ể ontology ột từ điển ễn về việc uả. Trong ện theo ba đang chạy từ vựng đã n hoặc các ột từ nước không có c trộn sao ng T (τwd: ốt hơn (τwd . ông cụ hệ ng Bảng 5 khác nhau. đều giống g Anh đã ợc các kết ng Bảng 6 là rõ ràng hông được ơng pháp chúng tôi. HT m d M C 1 từ đ 2 c từ m m th đ c s c tư c tr th m m o uỳnh Nhứt Phát, ừ các kết qu easure = 0.6 ụng phương ultiFarm. . Nhận xét c . Thảo luận v Thực h các công cụ ược liệt kê nh a) Áp dụ trên tr b) Thêm trước c) Lấy c d) Xem e) Một v hiện n . Đề xuất cá Chúng a) Làm p được b) Tính c) Tìm c d) Tìm c e) Cải th f) Bao g Trong b ủa các ontolo vựng, cấu t ột phép đo m iêu tả, được ực thể. Tron ược đặt tên, c ấu trúc các on ánh chúng vớ ận của nút đó ơng đồng về ách áp dụng b ung bình có t ử nghiệm ch ột số hệ thốn easre tốt hơn ntology theo Hoàng Hữu Hạn ả, chúng tôi 47). Vì vậy m pháp Confer B hung ề cách thức đ iện việc suy d so khớp riên ư sau: ng nhiều chi ọng số. một số tiền x khi đưa vào c ác nhận xét v xét lại việc sử ấn đề khác tr ay. Và chúng c biện pháp m tôi thấy rằng O hong phú cá các khái niệm đến sự phân c ác từ đồng ng ác từ điển ng iện thuật toán ồm nhiều côn ài báo này ch gy đã cho dựa rúc, và tổ hợp ới về sự tươn chuyển đổi và g giai đoạn đ ác thuộc tính tology, chúng i nhau dựa trê và các lân c cấu trúc đượ a thao tác đư rọng số của c uẩn của OAE g đã tham gi . Ngoài ra, ba phương ph h, Phan Công Vi thấy rằng khi à chúng tôi ence, chúng ảng 7. So sánh ể cải thiện hệ iễn dựa trên c g lẻ sẽ nâng c ến lược linh h ử lý (Hình 6 ác công cụ đố à thông tin về dụng giá trị n ong công cụ tôi sẽ cải thiệ ới MReasoner c từ điển ngữ ngữ nghĩa to ấp các khái ni hĩa theo phươ ôn ngữ khác n của một số c g cụ so khớp úng tôi trình trên thông ti . Đối với việ g đồng, tron cho vào một ầu tiên, chún đối tượng và tôi tạo ra mộ n mạng lưới ận của các lâ c tính bằng cá ợc mô tả trong ác kết quả về I-08 và có cá a vào tổ chúc chúng tôi trìn áp: Benchma nh ngưỡng τwd sử dụng ngưỡ tôi nhận đư kết quả với cá thống đề xuấ ác tương ứng ao các kết qu oạt hơn tron ), chẳng hạn n i sánh. nhãn của ont gưỡng thích của chúng tô n nó trong tư có thể cải tiến nghĩa vì Wor àn diện. ệm ngữ nghĩa ng pháp kết h hau cho Mult ông cụ đối sá khác nhau. VII. bày thuật toá n về từ vựng c xác định sự g đó các thôn túi từ, sau đ g tôi thu đượ các thuộc tín t mạng lưới của chúng. M n cận đó đồn ch so sánh cá phần III mụ từ vựng và c c kết quả khả OAEI-08 và h bày thêm rk, Conferenc = 0.9, τed = 0 ng τwd = 0.9 ợc các ngưỡ c ngưỡng khác t về từ là rất k ả của chúng t g việc kết hợp hư loại bỏ đặ ology để tính hợp để tối ưu i là bỏ qua th ơng lai. rất nhiều. M dNet không p thay vì chỉ tí ợp. iFarm. nh. KẾT LUẬN n so khớp on và cấu trúc củ tương đồng g tin về từ vự ó chúng được c ba ma trận t h dữ liệu của cho mỗi nút tr ỗi mạng lưới g thời được th c mảng này. c B. Cuối cùn ấu trúc. Chún quan. Ngoài như trong Bả các kết quả c e và MultiFa .8, công cụ , τed = 0.8 the ng tốt hơn s nhau của Confe hó khăn, vì v ôi. Một số cá nhiều công c tính cụ thể toán, cá biệt k hóa độ chính ông tin về cấ ột số cách mớ hải là một từ nh đến tất cả tology tìm ra a chúng. Thu về từ vựng gi ng của mỗi th sử dụng cho ương đồng v hai ontology ong ontology của mỗi nút đ ể hiện bởi m Sau khi tạo ra g, trong giai đ g tôi đã thực ra chúng tôi ng 2 cho thấy ủa hệ thống rm. Chiến lượ của chúng tô o phương ph o với phươn rence 2014 ậy các kết qu ch để cải thiệ cụ so khớp th (ví dụ, '-', '_' hi tên của kh xác. u trúc bao gồ i được đề xuấ điển chuyên n các khái niệm sự tương đồn ật toán này th ữa các thực t ực thể, chẳn việc tìm kiếm ề từ vựng bằn . Trong giai đ nguồn và ont ược tạo ra bằ ột mảng hai ma trận này oạn thứ ba, c hiện thuật toá so sánh thuật thuật toán củ OMReasoner c kết hợp của i thực hiện tố áp Conferenc g pháp Benc ả chính xác đ n công cụ của ay vì chỉ tổn ) hoặc tách cá ái niệm này là m ontology ở t như sau: ghiệp, nó kh và thuộc tính g trong số cá ực hiện ở ba hể, chúng tôi g hạn như nh sự tương đồ g cách so sá oạn thứ hai, ology đích và ng cách sử dụ chiều. Ma trậ , nó được cải húng tôi tính n của chúng toán của chú a chúng tôi c cho việc đố nhiều công c 705 t nhất (F- e. Việc sử hmark và ược đưa ra chúng tôi g hợp dựa c từ ghép, vô nghĩa. giai đoạn ông thể có . c thực thể giai đoạn: giới thiệu ãn hoặc sự ng của các nh các lớp để so sánh sau đó so ng các lân n khởi tạo thiện bằng toán giá trị tôi trên bộ ng tôi với ó độ đo f- i sánh các ụ so khớp 706 THUẬT TOÁN MỚI VỀ SO KHỚP ONTOLOGY riêng lẻ và sự suy diễn logic mô tả DL bao hàm cả trong cách tiếp cận của chúng tôi. Các kết quả đạt được chúng tôi thấy vẫn chưa thỏa mãn và sẽ tiếp tục cải tiến nó trong tương lai. VIII. TÀI LIỆU THAM KHẢO [1] N. Arch-Int and P. Sophatsathit, A semantic information gathering approach for heterogeneous information sources on WWW, Journal of Information Science 29 (2003) 357–374. [2] M. Ehrig and J. Euzenat. Relaxed precision and recall for ontology matching, K-Cap 2005 Workshop on Integrating Ontologies2005 (Banff, Alberta, Canada) 25–32. [3] L. S. Xiao and R. Ellen, Automated schema mapping techniques: an exploratory study, Research Letters Information Science4 (2003) 113–136. [4] W. Cohen, P. Ravikumar and S. Fienberg, A comparison of string metrics for matching names and records, Proceedings of the Workshop on Data Cleaning and Object Consolidation at the International Conference on Knowledge Discovery and Data Mining (KDD)(2003). [5] A. Alasoud, V. Haarslev and N. Shiri, An empirical comparison of ontology matching techniques, Journal of Information Science35(4) (2009) 379–397. [6] V. I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Soviet Physics Doklady10 (1966) 707–710. [7] G. A. Miller, WordNet: A lexical database for english, Communications of the ACM38 (1995) 39–41. [8] P. Bouquet, L. Serafini and S. Zanobini, Peer-to-peer semantic coordination, Journal of Web Semantics 2(1) (2004) 81–97. [9] G. Pirro, A semantic similarity metric combining features and intrinsic information content, Journal of Data and Knowledge Engineering 68 (2009) 1289–1308. [10] A. Maedche and S. Staab, Measuring similarity between ontologies, In Proceedings of the International Conference on Knowledge Engineering and Knowledge Management(2002) 251–263. [11] Rahm, E. and Bernstein, P.: A survey of approaches to automatic schema matching. The VLDB Journal, ,10(4): 334--350(2001). [12] Shvaiko, P. and Euzenat, J.: A survey of schema-based matching approaches. Journal on Data Semantics (JoDS) IV, 146--171(2005). [13] Kalfoglou, Y. and Schorlemmer, M.: Ontology mapping: the state of the art. The Knowledge Engineering Review Journal, 18(1):1--31, (2003). A NEW ALGORITHM FOR ONTOLOGY MATCHING Huynh Nhut Phat, Hoang Huu Hanh, Phan Cong Vinh ABSTRACT − Ontology matching is an importance in ontology technology of the Semantic Web with a goal of finding alignments among the entities of given ontologies. Ontology matching is a necessary step for establishing interoperation and knowledge sharing among Semantic Web applications. In this study we present an algorithm and a tool developed based on this algorithm to find correspondences among entities of input ontologies. The proposed algorithm uses a new lexical similarity measure and also utilizes structural information of ontologies to determine their corresponding entities. The lexical similarity measure generates a bag of words for each entity based on its label and description information. The structural approach creates a grid for each node in the ontologies. The combination of lexical and structural approaches creates the similarity matrix between the source and target ontologies. The proposed algorithm was tested on a well known benchmark and also compared to other algorithms presented in the literature. Our experimental results show the proposed algorithm is effective and outperforms other algorithms.
File đính kèm:
thuat_toan_moi_ve_so_khop_ontology.pdf