Thạc Sĩ So trùng mờ các đồ thị tri thức

Luận văn thạc sĩ
Đề tài: SO TRÙNG MỜ CÁC ĐỒ THỊ TRI THỨC

MỤC LỤC
LỜI CẢM ƠN .1
TÓM TẮT .2
SUMMARY 3
MỤC LỤC .4
DANH MỤC CÁC HÌNH 5
DANH MỤC CÁC BẢNG .6
1 - PHÁT BIỂU VẤN ĐỀ 7
2 - CƠSỞLÝ THUYẾT 10
2.1 - Ngôn ngữtruy vấn đồthịtri thức .10
2.1.1 Sesame và SeRQL 10
2.1.2 Đồthịý niệm 13
2.2 - Độtương tựgiữa các từ .15
2.2.1 Hướng tiếp cận dựa trên kho ngữliệu 15
2.2.2 Hướng tiếp cận dựa trên ontology 17
2.3 - Độ đo giữa các chuỗi .25
2.3.1 Các độ đo dựa trên chuỗi 25
2.3.2 Các độ đo dựa trên token 27
3 - CÁC ĐỘ ĐO GIỮA HAI ĐỒTHỊTRI THỨC .32
3.1 - Độtương tựgiữa các kiểu thực thể 32
3.2 - Độbao phủgiữa các kiểu thực thể .35
3.3 - Độbao phủgiữa các tên thực thể .37
3.4 - Độ đo giữa đồthịtruy vấn và kết quả 39
4 - THIẾT KẾVÀ HIỆN THỰC GIẢI THUẬT SO TRÙNG MỜ ĐỒTHỊTRI THỨC .42
4.1 - Kĩthuật biến đổi truy vấn 42
4.2 - Ánh xạ đồthịý niệm truy vấn sang ngôn ngữtruy vấn SeRQL 50
4.3 - Giải thuật so trùng mờcác đồthịý niệm .57
5 - ĐÁNH GIÁ 64
6 - KẾT LUẬN 71
7 - HƯỚNG MỞRỘNG 72
DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ 73
TÀI LIỆU THAM KHẢO .74

TÓM TẮT
Tri thức có thể được biểu diễn nhưlà các đồthịgồm các ý niệm và quan hệgiữa các ý
niệm. Luận văn này đưa ra một cách tiếp cận mới cho việc tìm kiếm ngữnghĩa bằng cách so
trùng mờcác đồthịtri thức dựa trên việc nghiên cứu độ đo vềmặt ngữnghĩa giữa hai kiểu ý
niệm, kiểu quan hệvà các ràng buộc thuộc tính trên kiểu ý niệm đó. Trong đó, chúng tôi dẫn
ra cách tính độ đo tương tựvà bao phủgiữa các kiểu ý niệm, kiểu quan hệdựa trên sốlượng
thực thểcủa các kiểu ý niệm, kiểu quan hệ đó có trong cơsởtri thức. Từ đó, chúng tôi tính
được độ đo tương tựvà độ đo bao phủgiữa một đồthịtruy vấn và một kết quả.
Mặt khác, đểtận dụng khảnăng tìm kiếm có sẵn của hệthống Sesame, công trình này
sửdụng kĩthuật biến đổi truy vấn đểtìm các đồthịkết quảmà gần với đồthịtruy vấn của
người sửdụng. Điều đó có nghĩa là, tri thức sẽ được lưu dưới dạng các phát biểu RDF mà có
thể được xem là các đồthịtri thức. Một đồthịtruy vấn mới sẽ được sinh ra thông qua kĩthuật
biến đổi truy vấn và được sửdụng đểtruy vấn các đồthịRDF kết quả. Những đồthịRDF kết
quảmà được so trùng chính xác với đồthịtruy vấn vừa được biến đổi sẽ được so trùng với đồ
thịtruy vấn ban đầu đểtính toán các độ đo và trảvềcho người sửdụng.

1 - PHÁT BIỂU VẤN ĐỀ
Nhưchúng ta đã biết, ngày nay cùng với sựbùng nổvà phát triển nhanh chóng của
World Wide Web, Internet lưu trữmọi tài nguyên thông tin chia sẻtrên toàn cầu. Vấn đề đặt
ra là làm thếnào đểcó thểkhai thác và sửdụng tài nguyên đó một cách hiệu quảtrong khi dữ
liệu được lưu trữtrên Web là bán cấu trúc và việc tìm kiếm dữliệu chỉdựa vào việc so trùng
các từkhóa mà không sửdụng ngữnghĩa là không chính xác. Do đó, một cách tiếp cận mới
đểcó thểbiểu diễn, tổchức thông tin, và xây dựng nên một mô hình tìm kiếm thích hợp là
điều cần thiết.
Một dạng chuẩn cho việc biểu diễn nội dung, thông tin của các tài liệu và ngữnghĩa tri
thức trên Web là dùng các phát biểu RDF (Resource Description Framework), mà trong đó,
các phát biểu có thểxem nhưlà các đồthị. Từ đó, các hệthống quản lý thông tin và tri thức
dần dần xuất hiện. Cụthểlà Sesame ([14]) với ngôn ngữtruy vấn SeRQL ([23]) cho việc lưu
trữvà truy vấn các đồthịRDF. Tất cảchúng đều là mã nguồn mởvà đã được sửdụng trong
các hệthống lớn.
Công trình mà chúng tôi đang nghiên cứu và hiện thực cũng sửdụng các phát biểu RDF
đểlưu trữvà biểu diễn tri thức, đồng thời sửdụng Sesame và ngôn ngữtruy vấn mạnh, cho
phép tìm kiếm chính xác của nó là SeRQL đểquản lý và truy vấn các đồthịRDF. Một đồthị
RDF bao gồm các kiểu ý niệm, kiểu quan hệvà các ràng buộc vềgiá trịthuộc tính trên kiểu ý
niệm. Trong đó, các kiểu ý niệm, kiểu quan hệ được định nghĩa trong một mạng phân cấp
ontology. Do đó, mục tiêu của luận văn này là đưa ra cách tiếp cận mới cho việc tìm kiếm
theo ngữnghĩa bằng cách so trùng mờcác đồthịtri thức dựa trên việc nghiên cứu các độ đo
khoảng cách ngữnghĩa giữa các kiểu ý niệm, giữa các kiểu quan hệvà các độ đo giữa các giá
trịthuộc tính.
Mục tiêu đặt ra của công trình đã hướng chúng tôi nỗlực nghiên cứu các độ đo giữa các
ý niệm, mà cụthểlà nghiên cứu các độ đo giữa các từcủa các công trình trước đây mà cách
tiếp cận được phân chia làm hai hướng chính, gồm cách tiếp cận dựa trên tập ngữliệu và cách
tiếp cận dựa trên ontology. Trong cách tiếp cận dựa trên tập ngữliệu, khoảng cách ngữnghĩa
giữa các từ đại diện cho các ý niệm và các quan hệ được xác định dựa trên sự đồng xuất hiện
của chúng trong các ngữcảnh khác nhau trong một tập ngữliệu. Trong cách tiếp cận dựa trên
ontology, khoảng cách vềmặt ngữnghĩa được xác định dựa trên các mạng ngữnghĩa gắn liền
với sựliên hệgiữa các từ. Tuy nhiên, các phương pháp theo các cách tiếp cận trên không thể
So trùng mờcác đồthịtri thức
Trang 8 / 77
áp dụng được cho các nhãn kiểu không có ý nghĩa bởi vì chúng đều dựa trên sựxuất hiện thực
sựvà ý nghĩa của các từcó trong một tập ngữliệu.
Cơsởtri thức của công trình mà chúng tôi nghiên cứu được xây dựng dựa trên
ontology, gồm các nhãn kiểu ý niệm và nhãn kiểu quan hệ. Do đó, đểthực hiện việc tính
khoảng cách ngữnghĩa giữa các ý niệm được đại diện bởi các nhãn kiểu ý niệm và nhãn kiểu
quan hệ đó, chúng tôi thực hiện việc sửa đổi công thức tính khoảng cách ngữnghĩa giữa các
từdựa trên mạng phân cấp ontology của Jiang-Conrath ([13]). Cụthểnhưsau, thay vì tính
xác suất xuất hiện của các từtrong công thức dựa trên một tập ngữliệu, chúng tôi dẫn ra xác
suất xuất hiện của các kiểu ý niệm hoặc kiểu quan hệ được tính dựa trên sốlượng thực thểcủa
kiểu ý niệm hoặc kiểu quan hệ đó có trong cơsởtri thức của công trình đang làm.
Mặt khác, các độ đo khoảng cách ngữnghĩa trên là độ đo tương tựgiữa hai kiểu ý niệm,
kiểu quan hệ. Đó là các độ đo đối xứng. Điều này hướng chúng tôi đến việc nghiên cứu các
độ đo bất đối xứng. Bởi vì trên thực tế, chúng ta có thểcần đo và tính xem một đồthịtruy vấn
bao phủmột đồthịkết quảmột giá trịlà bao nhiêu. Trong công trình, chúng tôi đưa ra một độ
đo bao phủbất đối xứng cho các kiểu thực thểcũng dựa trên nền tảng xác suất của độ đo
khoảng cách ngữnghĩa của Jiang-Conrath.
Ngoài việc nghiên cứu các độ đo giữa các từcủa các công trình trước đây để đưa ra
phương pháp mới cho công trình của mình, chúng tôi còn tiến hành nghiên cứu các độ đo giữa
các giá trịthuộc tính. Trong công trình của luận văn, chúng tôi giới hạn chỉnghiên cứu các độ
đo giữa các giá trịthuộc tính chuỗi là tên của thực thể. Các cách tiếp cận của các công trình
trước đây về độ đo giữa các chuỗi được chia làm hai phương pháp, gồm phương pháp đo
chuỗi tĩnh và phướng pháp đo chuỗi dựa trên các token. Trong công trình này, chúng tôi áp
dụng phương pháp SoftTF-IDF ([1]), là phương pháp đo lai ghép giữa phương pháp đo chuỗi
tĩnh và phương pháp đo dựa trên token cho việc tính độ đo giữa các thuộc tính chuỗi là tên
thực thể.
Nếu xét vềkhía cạnh hiện thực, việc tiến hành triển khai xây dựng một hệthống rút
trích xấp xỉcác đồthịtri thức ngay từban đầu là công việc khó khăn, đòi hỏi nhiều thời gian
và công sức. Vì vậy, chúng tôi sửdụng kĩthuật biến đổi truy vấn nhưlà một giải pháp chiến
lược, đồng thời sửdụng lại các chức năng so trùng có sẵn của Sesame và ngôn ngữtruy vấn
của nó là SeRQL cho việc quản lý và so trùng chính xác các đồthịtri thức.
Điều đó có nghĩa là, tri thức sẽ được lưu dưới dạng các phát biểu RDF mà có thể được
xem là các đồthịtri thức có trong cơsởtri thức được quản lý bởi hệthống Sesame. Một đồ
So trùng mờcác đồthịtri thức
Trang 9 / 77
thịtruy vấn mới sẽ được sinh ra thông qua kĩthuật biến đổi truy vấn và được sửdụng đểtruy
vấn các đồthịRDF kết quảthông qua ngôn ngữSeRQL. Những đồthịRDF kết quảmà được
so trùng chính xác với đồthịtruy vấn vừa được biến đổi sẽ được so trùng với đồthịtruy vấn
ban đầu đểtính toán các độ đo tương tựvà bao phủvà trảkết quảvềcho người sửdụng.
So trùng mờcác đồthịtri thức
Trang 10 / 77
2 - CƠSỞLÝ THUYẾT
2.1 - Ngôn ngữtruy vấn đồthịtri thức
2.1.1 Sesame và SeRQL
RDF cùng với định dạng cấu trúc của nó là RDF Schema (RDFS) là một dạng chuẩn
cho việc biểu diễn nội dung, thông tin của các tài liệu và ngữnghĩa tri thức trên Web. Do đó,
chúng ta cần có một hệthống hữu hiệu đểcó thểquản lý lưu trữ, truy vấn, sửdụng một cách
hiệu quảcác tri thức và thông tin được lưu trữdưới dạng các phát biểu RDF và RDFS này.
Sesame là một hệthống nhưvậy với mã nguồn mở, được viết bằng ngôn ngữlập trình Java,
cho phép lưu trữ, truy vấn và suy diễn trên dữliệu RDF và RDFS. Ngoài ra, Sesame còn cung
cấp các công cụcho phép phân tích cú pháp, thông dịch, truy vấn, quản lý lưu trữthông tin
RDF và RDFS, cung cấp thưviện nhúng vào trong các ứng dụng hoặc có thểlàm việc từxa
với nhiều giao thức giao tiếp khác nhau nhưHTTP, RMI, và SOAP.
Cùng với sựxuất hiện với chuẩn RDF và RDFS, nhiều ngôn ngữtruy vấn RDF và
RDFS đã ra đời nhưRQL và RDQL. Tuy nhiên, các ngôn ngữnày vẫn còn thiếu khảnăng
biểu diễn biểu thức đường dẫn đủmạnh đểcó thể đơn giản biểu thức truy vấn. Vì vậy,
Sesame đưa ra một ngôn ngữSeRQL (Sesame RDF Query Language) nhưlà một ngôn ngữ
RDF và RDFS mới, thừa hưởng tất cảcác đặc điểm tốt của RQL và RDQL, và hỗtrợmột số
đặc điểm mới mạnh hơn. SeRQL cũng hỗtrợkhảnăng bao phủ(subsumption), nghĩa là một
kiểu ý niệm hoặc một quan hệtrong câu truy vấn có thểso trùng (match) được với các kiểu
con của nó trong cơsởtri thức.
Thành phần cơbản của truy vấn SeRQL là các URI (univeral resource identifiers),
hằng, và biến. Một URI trong Sesame có thể được viết dưới hai dạng, hoặc là URI đầy đủ, ví
dụ, ta có <http://www.dit.hcmut.edu.vn/vnkim/vnkimkb.rdf#Quốc_gia_1>là danh hiệu
URI của thực thểquốc gia Việt Nam trong cơsởtri thức, hoặc ta có thểviết ởdạng URI viết
tắt là <vnkimkb_rdf:Quốc_gia_1>. Trong trường hợp viết tắt, tiếp đầu ngữ vnkimkb_rdfsẽ
được ánh xạthành chuỗi đầy đủlà http://www.dit.hcmut.edu.vn/vnkim/vnkimkb.rdftự
động bởi hệthống tìm kiếm Sesame. Các thuộc tính của các đối tượng mang giá trịhằng
thuộc các kiểu dữliệu cơbản nhưsốthực, sốnguyên, chuỗi, . Các biến đại diện cho các
danh hiệu URI của các đối tượng hoặc các giá trịthuộc tính của đối tượng mà chúng ta muốn
có và được chỉra trong câu truy vấn thông qua các tên biến.

TÀI LIỆU THAM KHẢO
[1] Bilenko M., Mooney R., Cohen W., Ravikumar P., and Fienberg S., 2003. “Adaptive
Name Matching in Information Integration”. IEEE Intelligent system, vol. 18, No. 5, pp.
16-23.
[2] Budanitsky A. and Hirst G., 2001. “Semanticdistance in WordNet: An experimental,
application-oriented evaluation of five measures”. Proceedings of the Workshop on
WordNet and Other Lexical Resources, the 2nd
Meeting of the North American Chapter of
the Association for Computational Linguistics, Pittsburgh, Pennsylvania, USA.
[3] Church K.W. and Hanks P., 1989. “Word Association Norms, Mutual Information, and
Lexicagraphy”. Proceedings of the 27
th
Annual Meeting of the Association for
Computational Linguistics, pp. 76-83.
[4] Cohen W. W., Ravikuma P., and Feinberg S. E., 2003. “A comparision of string distance
metrics for name-matching tasks”. Proceedings of the IJCAI-2003 Workshop on
Information Integration on the Web.
[5] Cohen W. W., Ravikuma P., and Feinberg S. E., 2003. “A comparision of string distance
metrics for matching names and records”. Proceedings of the KDD-2003 Workshop on
Data Cleaning, Record Linkage, and Object Consolidation.
[6] Gauch S., Wang J., and Rachakonda S. M., 1997. “A corpus Analysis Approach for
Automatic Query Expansion and its Extension to Multiple Database”. Proceedings of the
International Conference on Information and Knowledge Management.
[7] Gotoh O., 1981. “An Improved Algorithm for Matching Bological Sequences”. Journal of
Molecular Biology, vol. 162, pp. 705-708.
[8] Grefenstette G., 1992. “Use of Syntactic Context to Produce Term Association Lists for
Text Retrieval”. Proceedings of the 15
th
Annual International conference on research and
Development in Information Retreval, SIGIR’92.
[9] Hirst G. and St-Onge D., 1998. “Lexical Chainsas Representations of Context for the
Detection and Correction of Malapropisms”. C. Fellbaum (ed.): WordNet: An Electronic
Lexical Database, Cambridge: MIT Press, pp. 305-332.
So trùng mờcác đồthịtri thức
Trang 75 / 77
[10] Jaccard, 1912, “The distribution of the flora of the alpine zone”. New Phytologist vol.
11, pp. 37-50.
[11] Jaro M. A., 1989. “Advances in record-linkage methodology as applied to the 1985
census of Tampa, Florida”. Journal of the American Statistical Society, vol. 84, no. 406,
pp. 414-420.
[12] Jaro M. A., 1995 “Probabilistic linkage of large public health data file”. Statistics in
Medicine, vol. 14, pp. 491-498.
[13] Jiang J. and Conrath D. W., 1997. “Semantic similarity based on corpus statistics and
lexical taxonomy”. Proceedings of the International Conference on Research in
Computational Linguistics, Taiwan.
[14] Kampman A., Harmelen F., and Broekstra J., 2002. “Sesame: a generic architecture
for storing and querying RDF and RDF Schema”. Proceedings of the 1
st
International
Semantic Web Conference. Also at http://www.openRDF.org/ (Last visited: May 2005).
[15] Kozima H. and Furugori T., 1993. “Similarity between words computed by spreading
activation on an English dictionary”. Proceedings of 6th Conference of the European
Chapter of the Association for Computational Linguistics (EACL-93), Utrecht.
[16] Kozima H. and Ito A., 1997. “Context-sensitive word distance by adaptive scaling of a
semantic space”. In Ruslan Mitkov and Nicolas Nicolov, editors, Recent Advances in
Natural Language Processing, Amsterdam, John Benjamins Publishing Company, pp.
111–124.
[17] Leacock C. and Chodorow M., 1998. “Combining local context and WordNet
similarity for wod sense identification”. In C. Fellbaum, editor, WordNet: An electronic
lexical database, MIT Press, pp. 265-284.
[18] Lin D., 1998. “An Information-Theoretic Definition of Similarity”. Proceedings of the
15
th
International ConferenceOn Machine Learning, Madison, Wisconsin, USA.
[19] Monge A. E. and Elkan C. P., 1996. “The Field-Matching Problem: Algorithm and
Applications”. Proceedings of the Second International Conference on Knowledge
Discovery and Data Minning, AAAI Press, pp. 267-270.
[20] Needleman S. B. and Wunsch C. D., 1970. “A general method applicable to the
search for similarities in the amino acid sequences of two proteins”. Journal of Molecular
Biology 48: 443–453.
So trùng mờcác đồthịtri thức
Trang 76 / 77
[21] Ho N. D. and Cédirick F., 2004. “Lexical Similarity based on Quantity of Information
Exchanged – Synonym Extraction”. Proceedingsof the Research Informatics VietnamFrancophony, Hanoi, Vietnam, Feb. 2004, pp. 193–198.
[22] Resnik P., 1995. “Using Information content to evaluate semantic similarity in a
taxonomy”. Proceedings of the 14
th
International Joint Conference on Artificial
Intelligence, Montreal, Canada, Aug. 1995, pp. 448–452.
[23] SeRQL Manual. Available at http://www.openRDF.org/(Last visited: May 2005).
[24] Smith T. F. and Waterman M. S., 1981. “Identification of common molecular
subsequences”. Journal of Molecular Biology, 147: 195-197.
[25] Sussna M. J., 1997. “Text Retrieval Using Inference in Semantic Metanetworks”.
Ph.D. thesis, University of California, San Diego.
[26] Tru H. Cao, Dat T. Huynh, 2005. “Approximate retrieval of knowledge graphs”.
Proceedings of Intelligent Fuzzy Information Systems: Beyond the Relational Data Model
for the 11
th
World Congress of International Fuzzy Systems Association (IFSA 2005),
July 28-31, 2005, Beijing, China.
[27] Tru H. Cao, Dat T. Huynh, 2005. “Approximate knowledge graph Retrieval: Measures
and Realization”. Book Chapter in Sanchez, E. (Ed.): Fuzzy Logic and the Semantic Web.
Elsevier Science, to appear.
[28] Tru H. Cao, Hai T. Do, Bao T. N. Pham, Tuyen N. Huynh and Duy Q. Vu, 2005.
“Conceptual Graphs for Knowledge Querying in VN-KIM. Proceedings of the 13
th
International Conference on Conceptual Structures, July 18-22, 2005, Kassel, Germany, to
appear.
[29] Winkler W. E., 1999. “The state of recordlinkage and current research problems”.
Statistics of Income Division, Internal Revenue Service Publication R99/04. Available
from http://www.census.gov/srd/www/byname.html(Last visited: June 2005).
[30] Wu Z. and Palmer M., 1994. “Verb Semantics and Lexical Selection”. Proceedings of
the 32
nd
Annual Meeting of the Association for Computational Linguistics, Las Cruces,
New Mexico, USA, pp. 133-138.
[31] Yao H. and Etzkorn L., 2004. “Conversion from the Conceptual Graph (CG) Model to
the Resource Description Framework (RDF) Model”. Contributions of the 12
th
International Conference on Conceptual Structures, pp. 98-114.