Thuật toán mới về so khớp ontology

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.