Truy hồi thơng tin theo thực thể có tên

Lời cảm ơn

Trước hết, tôi xin gởi lời biết ơn chân thành sâu sắc đến Thầy PGS.TS. Cao Hoàng Trụ,
người đã tận tình hướng dẫn, định hướng cho tơi từ phương pháp nghiên cứu khoa học đến
cách thức trình bày vấn đề. Sự tận tình chỉ dẫn của Thầy đã giúp tơi hoàn thành tốt luận văn
này.
Xin chân thành cảm ơn NCS. Nguyễn Thanh Hiên, ThS. Huỳnh Tấn Đạt, KS. Hồng
Trung Dũng, các bạn trong lớp cao học MT2005 đã giúp đỡ tơi trong suốt q trình làm luận
văn.
Tơi xin gởi lời cảm ơn đến các tác giả của các bài báo mà tôi đã sử dụng để nghiên cứu
và tham khảo trong luận văn tốt nghiệp này.
Con xin cảm ơn Ba Mẹ đã động viên, khuyến khích và tạo điều kiện cho con hồn
thành 2 năm học tại trường.

Ngơ Minh Vương

Trang 1


Truy hồi thơng tin theo thực thể có tên

Tóm tắt

Xử lý thơng tin dựa trên từ khóa chỉ quan tâm đến ngữ nghĩa từ vựng trong tài liệu, do
đó nó quan tâm chủ yếu đến những gì xuất hiện trong tài liệu hơn là ý nghĩa chính của tài liệu.
Trong khi đó, các ngữ nghĩa cấp độ ngơn ngữ của các tài liệu được xác định bởi các thực thể có
tên (NE) và các mối quan hệ của chúng. NE và các mối quan hệ của chúng cấu thành nội dung
chính của các tài liệu. Trong luận văn này, chúng tôi đề xuất một kiến trúc tổng quát cho truy
hồi thông tin theo NE. Kiến trúc này đáp ứng cho cả 3 đặc điểm của các NE là tên, kiểu và

định danh. Đặc biệt chúng tôi giới thiệu sự mở rộng của mơ hình khơng gian vectơ dựa trên từ
khóa truyền thống (VSM) thành mơ hình khơng gian vectơ dựa trên NE (NE-VSM). Và mở
rộng mơ hình tương tự ngữ nghĩa dựa trên từ khóa (SSM) thành mơ hình tương tự ngữ nghĩa
dựa trên NE (NE-SSM). Trong đó các vectơ được định nghĩa cho các không gian trên NE, cụ
thể là các tên, các kiểu, các bộ đôi tên-kiểu, các định danh và các bộ ba tên-kiểu-định danh của
NE được thay thế cho từ khóa. Chúng tơi đã hiện thực sáu mơ hình dựa trên NE thuộc hai
nhóm chính là NE-VSM và NE-SMM cho việc tìm kiếm thơng tin với các kết quả thực nghiệm
đã được xem xét và thảo luận.

Ngô Minh Vương

Trang 2


Truy hồi thơng tin theo thực thể có tên

Abstract

Keyword-based information processing only deals with the word-level semantics
of texts, hence mainly by what appear in texts rather than what the texts convey.
Meanwhile, the object-level semantics of texts are determined by named entities (NE)
and their relations, which constitute the main and eventual contents of the texts. In this
paper, we propose a general framework for NE-based information processing, taking into
account all the three features of named entities, namely, their names, types, and
identifiers. In particular, we extend the traditional keyword-based vector space model
(VSM) to NE-based vector space model (NE-VSM). And extend keyword-based
semantic similarity model (SSM) to NE-based semantic similarity model (NE-SSM).
Therein, vectors are defined over spaces of entity names, types, name-type pairs, and
identifiers (or name-type-id triples), instead of keywords. We have implemented and
applied six NE-based models of two main groups which are NE-VSM and NE-SSM to

document searching with experimental results presented and discussed.

Ngô Minh Vương

Trang 3


Truy hồi thơng tin theo thực thể có tên

Mục lục

Lời cảm ơn .................................................................................................................. 1
Tóm tắt

.................................................................................................................. 2

Abstract

.................................................................................................................. 3

Danh mục các hình....................................................................................................... 6
Danh mục các bảng ...................................................................................................... 7
Chương 1: Phát biểu vấn đề..................................................................................... 8
Chương 2: Các lý thuyết được áp dụng ................................................................ 12
2.1 Mơ hình truy hồi thơng tin theo từ khóa .......................................................................12
2.2 Hệ thống chú thích ngữ nghĩa của KIM........................................................................16
2.3 Các độ đo giữa các chuỗi và giữa các kiểu ...................................................................21

Chương 3: Các cơng trình liên quan ..................................................................... 26
3.1 Mơ hình truy hồi thông tin dựa trên WordNet ..............................................................26

3.2 Mở rộng vectơ tài liệu bằng khám phá mối quan hệ tiềm ẩn........................................31
3.3 Mơ hình truy hồi thơng tin dựa trên Ontology..............................................................35

Chương 4: Truy hồi thơng tin theo thực thể có tên ............................................. 37
4.1 Tài liệu được chú thích bởi các thực thể có tên ............................................................38
4.2 Kiến trúc của truy hồi thơng tin ....................................................................................40
4.3 Độ tương tự giữa các thành phần của thực thể có tên...................................................41
4.4 Mơ hình truy hồi dựa trên thực thể có tên tổng quát.....................................................43
4.5 Gia tăng sự thể hiện của vectơ tài liệu và vectơ truy vấn .............................................46
4.6 Các mơ hình NE-VSM và NE-SSM .............................................................................48

Chương 5: Hiện thực và các kết quả thực nghiệm............................................... 50
5.1 Hiện thực chương trình .................................................................................................50
5.2 So sánh giữa mơ hình NE-VSM có mở rộng tài liệu và Google ..................................51
5.3 So sánh giữa các mơ hình NE-VSM và các mơ hình NE-SSM ....................................56

Ngơ Minh Vương

Trang 4


Truy hồi thơng tin theo thực thể có tên

Chương 6: Kết luận................................................................................................. 61
6.1 Các đóng góp của cơng trình ........................................................................................61
6.2 Hướng mở rộng.............................................................................................................62

Phụ lục 1: Giao diện trang web ................................................................................ 63
Phụ lục 2: Giới thiệu Lucene.................................................................................... 64
7.1 Tổng quan về Lucene....................................................................................................64

7.2 Cấu trúc đánh chỉ mục theo từ khóa của Lucene ..........................................................64

Tài liệu tham khảo ..................................................................................................... 68

Ngô Minh Vương

Trang 5


Truy hồi thơng tin theo thực thể có tên

Danh mục các hình

Hình 2-1: Một phần của các cây phân cấp trong ontology ........................................................ 18
Hình 2-2: Ontology và cơ sở tri thức trong KIM....................................................................... 19
Hình 2-3: Lưu đồ rút trích ngữ nghĩa của KIM† ([25]) ............................................................. 20
Hình 2-4: Tổ chức và nhận diện thực thể có tên từ GATE ........................................................ 20
Hình 3-1: Lưu đồ Precision-recall của SSM và VSM† [31]...................................................... 31
Hình 3-2: Sơ đồ truy hồi thông tin dựa trên ontology † [30]..................................................... 36
Hình 4-1: Kiến trúc của hệ thống truy hồi trong tin dựa trên NE .............................................. 41
Hình 5-1: Kiến trúc của đánh chỉ mục theo NE cho tài liệu ...................................................... 50
Hình 5-2: Tìm kiếm theo mơ hình VSM_ED cho các kiểu thực thể ........................................ 53
Hình 5-3: Tìm kiếm theo Google cho các kiểu thực thể............................................................ 53
Hình 5-4: Tìm kiếm theo mơ hình VSM_ED cho các cặp tên và kiểu thực thể ........................ 54
Hình 5-5: Tìm kiếm theo Google cho các cặp tên và kiểu thực thể........................................... 54
Hình 5-6: Tìm kiếm theo mơ hình VSM_ED cho các tên thực thể AND các kiểu thực thể...... 55
Hình 5-7: Tìm kiếm theo Google cho các tên thực thể AND các kiểu thực thể ........................ 56
Hình 5-8: Tìm kiếm theo mơ hình VSM_ED cho các kiểu thực thể ......................................... 57
Hình 5-9: Tìm kiếm theo mơ hình SSM_ED cho các kiểu thực thể .......................................... 57
Hình 5-10: Tìm kiếm theo mơ hình VSM_ED&DQ cho các kiểu thực thể .............................. 58

Hình 5-11: Tìm kiếm theo mơ hình SSM_ED&DQ cho các kiểu thực thể ............................... 58
Hình 5-12: Tìm kiếm theo mơ hình VSM_ED&EQ cho các tên thực thể
AND các kiểu thực thể............................................................................................. 59
Hình 5-13: Tìm kiếm theo mơ hình SSM_ED&EQ cho cho các tên thực thể
AND các kiểu thực thể............................................................................................. 60
Hình PL 1: Giao diện trang web: nhập truy vấn ........................................................................ 63
Hình PL 2: Giao diện trang web: chọn mơ hình tìm kiếm......................................................... 63
Hình PL 3: Sự tích hợp tiêu biểu một ứng dụng với Lucene† [12] ........................................... 65
Hình PL 4: Chi tiết cấu trúc bên trong định dạng đánh chỉ mục của Lucene† [12] .................. 66
Ngô Minh Vương

Trang 6


Truy hồi thơng tin theo thực thể có tên

Danh mục các bảng

Bảng 3-1: Ví dụ của vectơ truy vấn ban đầu.............................................................................. 30
Bảng 3-2: Vectơ truy vấn được phân bổ lại trọng số (re-weighting)......................................... 30
Bảng 3-3: Vectơ truy vấn được mở rộng (expansion) chỉ đối với tập đồng nghĩa .................... 30
Bảng 5-1: Đánh giá Precision và Recall của Google................................................................. 51

Ngô Minh Vương

Trang 7


Truy hồi thơng tin theo thực thể có tên


Chươ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 tồn cầu. Nhu cầu khai
thác thơng tin trên Internet là rất lớn, theo bản báo cáo đầu năm 2006 của hãng eMarketer 1 ,
hơn 1 tỷ người truy cập Internet tính đến cuối năm 2005. Trong số này tới 845 triệu (xấp xỉ
85%) sử dụng Internet với tần suất thường xuyên. 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ả.
Dữ liệu được lưu trữ trên Web là bán cấu trúc, đa phần các thông tin này được thể hiện
dưới dạng ngôn ngữ tự nhiên, chỉ phù hợp cho con người đọc hiểu, và các hệ thống truy hồi
thông tin hiện nay sử dụng từ khóa để liệt kê và truy hồi các tài liệu. Trong một ý nghĩa hạn
hẹp, một từ khóa là một từ hoặc một nhóm các từ liên quan với nhau. Trong dạng tổng quát
hơn, một từ khóa là bất kỳ từ nào xuất hiện trong văn bản của một tài liệu trong bộ lưu trữ. Rất
nhiều ngữ nghĩa trong tài liệu hoặc yêu cầu của người sử dụng bị mất khi chúng ta biểu diễn
văn bản của nó thành một tập các từ khóa. Hơn nữa, việc so trùng giữa một tài liệu và yêu cầu
của người sử dụng được tiếp cận trong không gian rất mơ hồ của từ khóa. Vì vậy, khơng có gì
ngạc nhiên khi các tài liệu được truy hồi theo yêu cầu của người sử dụng thơng qua một tập các
từ khóa là thường xun không liên quan với nhau.
Nhu cầu cần khai thác thông tin trên Internet một cách hiệu quả là thực sự chính đáng,
nhưng các mơ hình truy xuất thơng tin theo từ khóa bị hạn chế. Nên việc nghiên cứu và đề xuất
các giải pháp truy tìm thơng tin ngữ nghĩa để máy tính có thể hỗ trợ con người khai thác một
cách có hiệu quả hơn nguồn thơng tin trên Internet (và các kho tài liệu điện tử khác) là một
việc làm mang lại lợi ích to lớn và thiết thực.

1




Ngô Minh Vương

Trang 8


Truy hồi thơng tin theo thực thể có tên
Ngày nay, Thuật ngữ “thực thể có tên” (name entity) được sử rụng rộng rãi trong các
ứng dụng rút trích thơng tin, trả lời các câu hỏi, xử lý ngôn ngữ tự nhiên. Thực thể có tên được
đề cập đến lần đầu tại Message Understanding Conferences (MUC) những năm 1990 [22].
Thực thể có tên là con người, tổ chức, nơi chốn, và những đối tượng khác được tham khảo
bằng tên. Các thực thể có tên khác về bản chất và ngữ nghĩa với các từ (word) ở chỗ chúng nói
về các cá thể, trong khi các từ nói về những cái chung như khái niệm, phân loại, quan hệ, thuộc
tính. Việc xử lý các thực thể có tên cần đến trí thức cụ thể về thế giới đang xét còn việc xử lý
các từ chỉ đòi hỏi ngữ nghĩa từ vựng và ngữ nghĩa thơng thường.
Các thực thể có tên được đề cập đến trong tài liệu có một vị trí quan trọng về mặt ngữ
nghĩa của tài liệu đó. Nên các tài liệu Web có chú thích ngữ nghĩa cho các thực thể có tên sẽ
giúp cho việc tìm kiếm và khai thác thơng tin trên đó được chính xác và hiệu quả hơn. Ví dụ
như một truy vấn về thành phố Sài Gịn thì các tài liệu đề cập đến TP.HCM hoặc Sài Gòn như
một thành phố sẽ được ưu tiên xếp trên trong danh sách tài liệu trả về, cịn các tài liệu chứa các
từ “Sài Gịn” như “Sơng Sài Gịn”, “Ngân Hàng Sài Gịn Cơng Thương” sẽ xếp cuối hoặc
khơng được trả về.
Một thực thể có tên được biểu diễn bởi bộ ba [tên, kiểu, id], trong đó id là danh hiệu, là
sự phân biệt các thực thể có tên với nhau. Cùng một tên có thể có nhiều id khác nhau, một kiểu
có nhiều tên khác nhau và một tên có thể thuộc nhiều kiểu.
Ý tưởng chính của web ngữ nghĩa là nhúng ngữ nghĩa vào trong trang web thơ, để
chúng có thể được hiểu bởi máy tính và tiện ích hơn trong việc xử lý thơng tin một cách thơng
minh. Nói một cách đại khái, ngữ nghĩa của văn bản ngơn ngữ tự nhiên có thể được phân chia
thành hai phần, hoặc hai cấp độ. Cấp độ đầu tiên là cấp độ từ được xác định bởi âm tiết và ngữ
nghĩa của từ. Cấp độ thứ hai là cấp độ đối tượng được xác định bởi thực thể có tên và các mối
quan hệ của chúng được biểu lộ trong tài liệu.

Truy hồi thông tin truyền thống chỉ quan tâm chủ yếu đến các vấn đề ở cấp độ từ, ví
như là tập trung vào mơ tả sự tương tự và các mối quan hệ giữa các từ bằng cách sử dụng
WordNet cho việc truy hồi thơng tin hiện nay ([31]). Trong khi đó, trong nhiều trường hợp và
phạm vi, các NE và các mối quan hệ của chúng tạo thành ngữ nghĩa chính cho một tài liệu,
trong khi các ngữ nghĩa ở cấp độ từ chỉ là một trong các cách thức để định nghĩa các ngữ nghĩa
Ngô Minh Vương

Trang 9


Truy hồi thơng tin theo thực thể có tên
ở cấp độ đối tượng của một tài liệu. Xa hơn, việc rút trích thơng tin đầy đủ ở cấp độ đối tượng
đang cịn là một thách thức lớn. Ví dụ trong [15] và [32] điều này chỉ được thực thi ở dạng bán
tự động, sự cố gắng tự động hoàn toàn ở [34] chỉ đạt được độ chính xác khoản 60% và cho lĩnh
vực đặc trưng nào đó.
Tuy nhiên, vẫn có ý nghĩa cho việc xử lý thông tin ngay cả chỉ có thực thể có tên được
nhận diện trong tài liệu. Ví dụ như, chúng ta có thể tìm kiếm các trang web nói đến
“Washington” như là một người, trong khi các động cơ tìm kiếm hiện tại chỉ có thể trả về bất
kỳ tài liệu nào chứa từ “Washington”, mặc dù nó có thể là tên của một tạp chí hoặc một trường
đại học. Sự thật là sự nhận diện NE đã thu hút rất nhiều nỗ lực nghiên cứu. Các hệ thống nổi
tiếng có thể được kể đến là Semtag ([6]) sử dụng các phương pháp thống kê và KIM ([16]) sử
dụng các luật so trùng mẫu.
Trong [14], các tác giả đã đề xuất là các khái niệm phải được xác định trong truy vấn trước
khi tìm kiếm, để có thể đạt được các trả lời liên quan. Ví dụ, nếu “Washington” có trong một
truy vấn thì phải xác định rõ là nó nói về một người hoặc một trường đại học. Tuy nhiên, công
việc này chủ yếu là làm tăng thêm dữ liệu để tìm kiếm các kết quả. Theo hướng tìm kiếm theo
ngữ nghĩa, KIM ([16]) là một hệ thống thông tin và tri thức dựa trên NE đã quản lý một kho dữ
liệu các tài liệu được chú thích bởi các NE. Tuy nhiên, nó chỉ bổ trợ cho việc tìm kiếm các tài
liệu theo các danh hiệu của NE.
Trong [30], VSM dựa trên từ khóa truyền thống được mở rộng với các nhãn của thực thể

là các dạng chuỗi thường xuyên nhất của các lần xuất hiện của thực thể. Tuy nhiên, nhiều giá
trị của một nhãn khơng được định nghĩa chính thức hoặc cấu trúc có hệ thống. Điều này cho
thấy có phần nào đó khơng thực tế và đặc biệt là các bí danh (alias) của thực thể khơng được
quan tâm. Trong khi đó, trong sự mở rộng VSM của [10], các mối quan hệ giữa các NE trong
các tài liệu được dùng để gia tăng trọng số của các phần tử của vectơ tài liệu, tuy nhiên chúng
cũng chỉ sử dụng tên của NE mà thơi.
Với sự trái ngược hồn tồn, trong luận văn này, chúng tôi đề xuất một cơ cấu tổ chức xử
lý thông tin dựa trên thực thể có tên hồn tồn mới, trong đó NE có thể được thể hiện tồn bộ
hoặc từng phần. Đó là vì bên cạnh những NE có thể được xác định một cách đầy đủ, một số

Ngô Minh Vương

Trang 10


Truy hồi thơng tin theo thực thể có tên
NE chỉ có tên hoặc kiểu. Với cơ cấu tổ chức này, chúng tơi giới thiệu sáu mơ hình thuộc hai
nhóm chính là NE-VSM và NE-SSM và ứng dụng của chúng trong việc tìm kiếm các tài liệu.
Tùy thuộc vào nhu cầu người dùng là tìm kiếm các tài liệu chứa thuật ngữ trong truy
vấn hay các tài liệu có chủ đề liên quan đến thuật ngữ trong truy vấn mà người dùng sử dụng
mơ hình tương ứng. Với dạng tìm kiếm đầu (là các mơ hình VSM_ED, VSM_ED&DQ) người
dùng có thể đưa ra một truy vấn như “Tìm các trang web về President Washington” mà không
nhận các trang không liên quan, khơng được mong chờ. Ví dụ như các trang nói về
Washington Post hoặc University of Washington, do đó độ đo precision được cải thiện. Trên
một nhánh khác, một truy vấn như “Tìm các trang web về President Washington” có thể nhận
được các trang liên quan nhưng chúng không cần thiết phải chứa từ khóa “president”, do đó độ
đo recall cũng được cải thiện. Với dạng tìm kiếm theo chủ đề (là các mơ hình VSM_ED&EQ,
SSM_ED, SSM_ED&DQ, SSM_ED&EQ), người dùng mong muốn tìm kiếm mờ các tài liệu
có liên quan đến truy vấn, do đó các tài liệu có độ liên quan cao sẽ đươc xếp trên các tài liệu
liên quan thấp.


Ngô Minh Vương

Trang 11


Truy hồi thơng tin theo thực thể có tên

Chương 2:

Các lý thuyết được áp dụng

2.1 Mơ hình truy hồi thơng tin theo từ khóa
a) Mơ hình truy hồi thơng tin tổng quát
Một giải thuật phân loại hoạt động theo các tiên đề căn bản về các khái niệm của sự liên
quan giữa các tài liệu. Sự phân biệt các tập tiên đề mang lại sự phân biệt các mơ hình truy hồi
thơng tin. Mơ hình truy hồi thơng tin hiện thực việc xác định sự tiên đốn về cái gì là liên quan,
cái gì khơng liên quan (khái niệm của sự liên quan được thực hiện bởi hệ thống) [1].
Một mơ hình IR [1] là một bộ bốn [ D, Q, F, R(qi, dj)], trong đó:
1) D là một tập hợp tài liệu trong bộ lưu trữ.
2) Q là một tập hợp các thông tin cần thiết của người sử dụng, được gọi là các truy
vấn.
3) F là một cơ cấu tổ chức (framework) cho mơ hình gồm các tài liệu, các truy vấn
và các mối liên hệ giữa chúng.
4) R(qi, dj) là một hàm phân loại, nó kết hợp một số thực với một truy vấn qi ∈ Q
và một tài liệu dj ∈ D. Sự phân loại là định nghĩa thứ tự các tài liệu có liên quan
đến truy vấn qi.
Để xây dựng một mơ hình, trước tiên chúng ta phải đề cập đến sự mô tả cho các tài liệu
và cho nhu cầu thông tin của người dùng. Để có được các mơ tả này chúng ta phải đề ra được
cơ cấu tổ chức, trong đó các mơ tả này có thể được mơ hình hóa. Cơ cấu tổ chức này cũng phải

cung cấp được khả năng để xây dựng hàm phân loại. Thí dụ, Trong mơ hình boolean cổ điển,
cơ cấu tổ chức là bao gồm các tập hợp của các tài liệu và các phép tốn chuẩn trên tập hợp đó.
Trong mơ hình xác suất cổ điển, cơ cấu tổ chức là là bao gồm các tập hợp, các phép tốn xác

Ngơ Minh Vương

Trang 12


Truy hồi thơng tin theo thực thể có tên
suất chuẩn và lý thuyết Bayes. Trong mơ hình vectơ cổ điển, cơ cấu tổ chức là bao gồm không
gian vectơ t chiều và các phép tốn đại số tuyến tính chuẩn trên vectơ.

b) Mơ hình truy hồi thơng tin theo từ khóa
Các mơ hình cơ bản trong truy hồi thơng tin xem mỗi tài liệu được mô tả bởi một tập
hợp các từ khóa. Một từ khóa là một từ mà nghĩa của nó giúp cho việc xác định chủ đề của tài
liệu. Do đó, các từ khóa là các danh từ chính bởi vì danh từ có nghĩa riêng, dễ dàng được xác
định và truy vấn. Giả sử các ký hiệu được đặt như sau:
•

ki là một từ khóa, dj là một tài liệu, và wij >=0 là một trọng số của cặp (ki, dj). Trọng số
này xác định mức độ quan trọng của từ khóa trong việc mơ tả nội dụng ngữ nghĩa của
tài liệu tương ứng, nếu ki khơng xuất hiện trong tài liệu dj thì wi,j = 0. Đặt K = {k1, …,
kt} là tập hợp của tất cả các từ khóa, với t là số lượng từ khóa trong tập dữ liệu.

•

→

Mỗi tài liệu dj được đại diện bởi vectơ d = (w1,j , w2,j, …, wt,j). Gọi gi là một hàm trả về

r
trọng số của từ khóa ki trong bất kỳ vectơ t chiều nào (ví dụ, gi( d j ) = wi,j ).

c) Mơ hình Boolean cổ điển
Trong mơ hình Boolean, các biến trọng số của từ khóa là các giá trị nhị phân, ví dụ: wi,j
→

∈ {0,1}. Một truy vấn q là biểu thức boolean truyền thống. Gọi q dnf là dạng chuẩn tuyển cho
→

→

truy vấn q và q cc là một dạng chuẩn hội bất kỳ của q dnf . Độ tương tự của một tài liệu dj với
truy vấn q là:
→ ⎛→
→
⎞ ⎛
⎛→⎞
⎛→ ⎞⎞
sim(d j , q ) = 1 if ∃ q cc ⎜ q cc ∈ q dnf ⎟ ∧ ⎜⎜ ∀k i , g i ⎜ d j ⎟ = g i ⎜ q cc ⎟ ⎟⎟
⎝
⎠ ⎝
⎝ ⎠
⎝
⎠⎠
sim(d j , q ) = 0 others

(BT 2-1)

Mơ hình boolean nói lên rằng mỗi tài liệu hoặc là liên quan hoặc là khơng liên quan.

Khơng có khái niệm khớp một phần với các tình trạng truy vấn. Ví dụ: Gọi dj là một tài liệu mà
→

d j = (0,1,0). Tài liệu dj bao gồm các từ khóa kb nhưng sẽ không liên quan đến truy vấn
Ngô Minh Vương

Trang 13


Truy hồi thơng tin theo thực thể có tên

[q = k a ∧ (k b ∨ k c )] . Ưu điểm chính của mơ hình boolean là hình thức rõ ràng bên trong mơ
hình và sự đơn giản của nó. Nhược điểm chính là việc so khớp chính xác có thể dẫn đến việc
truy hồi được q ít hoặc q nhiều tài liệu.

d) Mơ hình xác suất cổ điển
Với một truy vấn q và một tài liệu dj trong bộ lưu trữ, mơ hình xác suất cố gắng ước
lượng xác suất mà người dùng sẽ tìm thấy tài liệu quan tâm dj. Mơ hình này giả sử rằng xác
suất của sự liên quan chỉ phụ thuộc vào truy vấn và tài liệu tương ứng. Hơn nữa, mơ hình cịn
giả sử rằng có một tập con của tất cả tài liệu mà người dùng xem như là tập các đáp ứng cho
truy vấn q, được gọi là tập các trả lời lý tưởng R. Các tài liệu có trong tập R là liên quan đến
truy vấn, còn các tài liệu khơng có trong tập R là khơng liên quan.
Trong mơ hình xác suất, các trọng số của các từ khóa thuộc kiểu nhị phân, wi,j ∈ {0,1},
wi,q ∈ {0,1}. Một truy vấn q là một tập con của các từ khóa. Gọi R là tập hợp các tài liệu liên
r
quan với truy vấn q. Gọi R là phủ định của R. Gọi P(R| d j ) là xác suất mà tài liệu dj có liên
r
quan đến truy vấn q và P( R | d j ) là xác suất mà tài liệu dj không liên quan đến truy vấn q.

( )

( )

r
P Rdj
sim( d j , q) =
r
P R dj
Sử dụng luật Bayes:

(
(

)
)

r
P d j R × P( R)
sim(d j , q) = r
P d j R × P( R )

≈ ∑ wi ,q

trong đó:

Ngơ Minh Vương

× wi , j

( )⎞⎟
( ) ⎟⎠


⎛
1 − P ki R
P (k i R )
× ⎜ log
+ log
⎜ 1 − P (k i R )
P ki R
⎝

(BT 2-2)

ni
N
P(k i R ) =
V +1
Vi +

Trang 14


Truy hồi thơng tin theo thực thể có tên
ni
N
P ki R =
N −V + 1

( )

ni − Vi +


ni : số tài liệu chứa từ khóa ki trong bộ lưu trữ.
N : tổng số tài liệu trong bộ lưu trữ.
V : là số tài liệu được truy hồi và phân loại theo mơ hình xác suất.
Vi : là số tài liệu trong V mà có chứa từ khóa ki.

e) Mơ hình vectơ cổ điển
Mơ hình vectơ cho rằng sự sử dụng các trọng số nhị phân là quá hạn chế và đề xuất một
cơ cấu tổ chức mà trong đó việc so khớp một phần là có thể được. Điều này được hiện thực
bằng cách gán các trọng số phi nhị phân cho các từ khóa trong truy vấn và trong các tài liệu.
Trong mơ hình vectơ, trọng số wi,j được kết hợp bới cặp [ki, dj] là số dương và phi nhị
phân. Các từ khóa trong truy vấn cũng có trọng số. Gọi wi,q là trọng số được kết hợp bởi cặp
→

[ki, q], và wi,q >=0. Vectơ truy vấn q = (w1,q , w2,q, …, wt,q), Vectơ của một tài liệu thứ j là
→

d j = (w1,j , w2,j, …, wt,j), với t là tổng số từ khóa trong bộ lưu trữ.

r
r
dj• q
sim (d j , q) = r
r =
dj × q

t

∑w
t


∑w
i =1

× wi ,q

i, j

i =1

2
i, j

×

t

(BT 2-3)

∑w
i =1

2
i ,q

Gọi N là tổng số tài liệu trong bộ lưu trữ, ni là số tài liệu có từ khóa ki xuất hiện, freqi,j
là tần số thơ của từ khóa ki trong tài liệu dj (là số lần từ khóa ki được đề cập trong văn bản của
tài liệu dj). Do đó tần số chuẩn hóa fi,j của từ khóa ki trong tài liệu dj được tính bởi:

f i, j =


Ngô Minh Vương

freqi , j
max l

freql , j

(BT 2-4)

Trang 15


Truy hồi thơng tin theo thực thể có tên
trong đó hàm max là được tính trên tất cả các từ khóa được đề cập trong văn bản của tài liệu dj.
Nếu từ khóa ki khơng xuất hiện trong tài liệu dj thì fi,j = 0.
Salton và Buckley [26] đề nghị cách tính các trọng số từ khóa và các trọng số truy vấn
như sau:
wi , j = f i , j × log

w i,q = 0.5 +

N
ni

(BT 2-5)

0.5 freqi ,q
max l


freql ,q

(BT 2-6)

trong đó freqi,q là tần số thơ của từ khóa ki trong truy vấn q.
Các ưu điểm chính của mơ hình vectơ là:

•

Sự sắp xếp theo thứ tự trọng số của từ khóa làm cải tiến truy hồi thơng tin.

•

Chiến lược so khớp một phần cho phép việc truy hồi các tài liệu một cách sắp xỉ với
truy vấn.

•

Cơng thức phân loại theo cosin sắp xếp các tài liệu theo cấp độ tương đồng của
chúng với truy vấn.

Nhược điểm chính của mơ hình vectơ là giả sử các từ khóa là độc lập lẫn nhau.

2.2 Hệ thống chú thích ngữ nghĩa của KIM
a) Ontology và cơ sở tri thức
Theo [13], ontology là một sự mơ hình hóa của một khái niệm hóa, được xem như là
một mơ hình trừu tượng của các hiện tượng trong thế giới thực cùng với việc xác định các khái
niệm liên quan của những hiện tượng này. Ontology là một hình thức, mơ hình hóa một cách rõ
ràng các khái niệm hóa có thể chia sẻ được. Trong [7] có bổ sung rõ hơn về ontology: một


Ngô Minh Vương

Trang 16


Truy hồi thơng tin theo thực thể có tên
ontology là một khái niệm hóa được mơ tả một cách hình thức, rõ ràng và chia sẻ được. Trong
đó:

•

Khái niệm hóa là một mơ hình trừu tượng của các hiện tượng trong thế giới
cùng với việc xác định các khái niệm liên quan của những khái niệm này.

•

Rõ ràng: là các kiểu của khái niệm và các ràng buộc trong việc sử dụng chúng
được định nghĩa một cách tường minh.

•

Hình thức: là cơ sở lập luận trên ontology mà máy có thể hiểu được.

•

Chia sẽ được: là ontology sẽ đạt được các kiến thức liên ứng được chấp nhận
bởi các giao tiếp.

Ontology được biểu diễn bởi các ngôn ngữ RDF, RDFS, DAML, OIL, DAML + OIL,
OWL. Bất kỳ dạng tài liệu nào được biễu diễn bằng các ngơn ngữ trên thì có thể xem như nó là

một ontology. Ontology được sử dụng trong các lĩnh vực như biểu diễn tri thức, xử lý ngơn
ngữ tự nhiên, rút trích thơng tin, cở sở dữ liệu, quản lý tri thức, các cơ sở dữ liệu trên mạng,
thư viện điện tử, hệ thống thông tin địa lý,...
Một số ontology hiện nay:

•

Cyc: hệ thống ontology nổi tiếng và phức tạp nhất, được phát triển từ năm 1985.
Hệ thống được ví như là một bộ bách khoa tồn thư chứa tồn bộ tri thức của
lồi người.

•

WordNet: do George Miller và các đồng nghiệp phát triển. Hiện hệ thống có
khoảng 166.000 từ và các cặp ngữ nghĩa.

•

KIMO (Knowledge and Information Management Ontology): KIM của
Ontotext Lab, Bulgaria, là một trong những hệ thống chú thích ngữ nghĩa cho
các thực thể có tên.

Hiện nay, tồn tại hai quan niệm song song: một quan niệm xem cơ sở tri thức
(knowledge base) là một phần trong ontology. Một quan niệm khác thơng dụng hơn thì tách cơ
sở trí thức ra khỏi ontology, KIM là hệ thống đại diện cho quan niệm này. Trong phạm vi luận
văn này, chúng tôi xem ontology và cơ sở tri thức là 2 phần riêng biệt. Chúng ta có thể xem
ontology là một dạng rút gọn của cơ sở tri thức. Hay nói cách khác: ontology là cái tồn tại (siêu
Ngô Minh Vương

Trang 17



Truy hồi thơng tin theo thực thể có tên
kiến thức) cịn cơ sở tri thức là những cái gì mà tôi biết (kiến thức cụ thể). Và cả hai thường
được lưu trữ trong cùng một bộ lưu trữ ngữ nghĩa.

Hình 2-1: Một phần của các cây phân cấp trong ontology

Trong hệ thống KIM, ontology chứa các định nghĩa của lớp thực thể, các thuộc tính và
các mối quan hệ. Những sự mô tả ngữ nghĩa của các thực thể và những mối quan hệ giữa
chúng được giữ trong cơ sở tri thức ([16]). Chúng ta có thể xem phần chính yếu của việc biểu
diễn tri thức một cách chính qui về các thực thể có tên là một cơ sở trí thức.

Ngơ Minh Vương

Trang 18


Truy hồi thơng tin theo thực thể có tên
ABC announced Profits in Q3, planning to
build a $300M plant in Vietnam,...and more
and more text

KIM Ontology & KB

Location
Company

subtypeOf


type
ABC

subtypeOf
Country

City
type

HQ

establish

type

type

London
partOf

“11/11/2006”

UK

Vietnam

Hình 2-2: Ontology và cơ sở tri thức trong KIM

b) Rút trích thơng tin ngữ nghĩa
KIM cung cấp các dịch vụ và cấu trúc cho truy hồi, đánh chỉ mục và chú thích ngữ

nghĩa. Để có thể làm việc này một cách nhất quán, KIM thực hiện việc rút trích thơng tin dựa
trên một ontology và một cơ sở tri thức đồ sộ.
Bản chất của phương pháp rút trích thơng tin của KIM là tổ chức các thực thể vào trong
KIMO. Sự chú thích NE được phân loại vào trong các lớp của ontology. Các thực thể được xác
định bởi URI, điều này cho phép các chú thích này được liên kết với các thơng tin riêng chi tiết
trong cơ sở tri thức. Sự khó khăn về rút trích thơng tin hiện nay của KIM là việc nhận diện các
NE, đặc biệt là rút rích sự kiện, quan hệ, thuộc tính.
Tiến trình rút trích thơng tin hiện tại của KIM sử dụng ontology quan niệm trọng số để
định nghĩa các lớp thực thể. Để được thêm vào cây phân cấp, mỗi lớp được ràng buộc với các
thuộc tính thích hợp. Các kiểu quan hệ cũng được định nghĩa với các ràng buộc về phạm vi,

Ngô Minh Vương

Trang 19


Truy hồi thơng tin theo thực thể có tên
lĩnh vực. Ngôn ngữ ontology cơ bản (RDFS) xem xét các mối quan hệ và thuộc tính như là các
property, chúng cũng có thể được tổ chức trong một cây phân cấp.
KIM IE dựa nên nền GATE, thừa kế tính chính xác, tính mở rộng và sự độc lập các
nhiệm vụ cho IE và các ứng dụng xử lý ngôn ngữ tự nhiên khác của GATE. Ví dụ như các hàm
quản lý tài liệu, xử lý token, tách câu,...

Hình 2-3: Lưu đồ rút trích ngữ nghĩa của KIM† ([25])

Hình 2-4: Tổ chức và nhận diện thực thể có tên từ GATE

Ngơ Minh Vương

Trang 20



Truy hồi thơng tin theo thực thể có tên

2.3 Các độ đo giữa các chuỗi và giữa các kiểu
a) Các độ đo giữa các chuỗi
Như đã trình bày ở chương 1, tên là một trong ba thành phần của NE và tên được biểu
diễn dưới dạng chuỗi. Thêm vào đó, một mục tiêu quan trọng của luận văn là truy hồi mờ các
tài liệu có liên quan với truy vấn. Do đó điều cần thiết là phải tiến hành nghiên cứu độ đo của
các cơng trình nghiên cứu trước đây về khoảng cách ngữ nghĩa giữa các chuỗi. Các công trình
nghiên cứu này tiếp cận theo hai hướng, gồm hướng tiếp cận dựa trên ký tự và hướng tiếp cận
dựa trên token.
Ý tưởng của cách tiếp cận dựa trên token (một nhóm các ký tự) là các chuỗi s và chuỗi t
cần đo được phân tích thành tập các token tương ứng là S và T. Độ đo giống nhau giữa hai
chuỗi được xem xét và tính tốn dựa trên sự tương tự của các token thuộc hai tập S và T này.
Và độ tương tự của 2 token được tính dựa vào độ tương tự giữa các ký tự của chúng. Tuy
nhiên, các chuỗi mà chúng ta đang xét là tên của NE nên các chuỗi này phần lớn chỉ gồm 1
hoặc 2 token. Do đó, chúng tơi đề xuất tính độ đo giữa các tên của các NE là dựa trên độ đo
giữa các ký tự.
Một lớp quan trọng của độ đo dựa trên ký tự là độ đo dựa trên khoảng cách soạn thảo.
Trong phương pháp này, khoảng cách giữa hai chuỗi s và t là được tính là chi phí tối thiểu cần
thiết cho các thao tác soạn thảo để chuyển từ chuỗi này sang chuỗi kia. Các thao tác soạn thảo
bao gồm: sao chép, chèn, thay thế, xóa. Tùy theo cách quy định đánh trọng số cho các thao tác
soạn thảo khác nhau mà ta có các độ đo khác nhau.
Phương pháp Leveinsten là một độ đo khoảng cách soạn thảo đơn giản. Trong đó, các
thao tác soạn thảo như xóa, chèn, thay thế đều có chi phí bằng 1, thao tác sao chép có chi phí
bằng 0. [24] là một sự mở rộng của độ đo Leveinsten bằng cách cho phép định nghĩa các chi
phí khác nhau cho thao tác thay thế, chèn, và xóa kí tự.
Tại [28] và [9] cũng sử dụng khái niệm khoảng cách soạn thảo trong độ đo của mình.
Trong đó, các tác giả đưa ra chi phí mới dựa trên việc định nghĩa hai loại chi phí cho thao tác


Ngô Minh Vương

Trang 21


Truy hồi thơng tin theo thực thể có tên
chèn, bao gồm một chi phí cho việc chèn kí tự đầu tiên của chuỗi và một chi phí khác cho việc
chèn các kí tự tiếp theo.
Ở [23] đưa ra một kỹ thuật so trùng đệ quy cho hai chuỗi dài s và t bằng cách chia hai
chuỗi s và t ra thành các chuỗi con s = a1...aK và t = b1...bL. Sau đó, độ đo giống nhau giữa hai
chuỗi s và t của Monge-Elkan ([23]) được định nghĩa là:

sim( s, t ) =

1
K

L

∑ max
i =1

L

j =1

sim' (ai , b j )

(BT 2-7)


Trong đó, sim’ là một độ đo tương tự thứ hai nào đó, trong cơng trình của mình, Monge-Elkan
thực hiện sim’ là độ đo của Smith-Waterman ([28]).
Một độ đo khác dựa trên ký tự là độ đo của Jaro ([18][19]). Ý tưởng của phương pháp
Jaro là độ đo được tính dựa trên số lượng và trật tự các ký tự dùng chung giữa hai chuỗi. Cho
trước các chuỗi s = a1...aK và t = b1...bL, ký tự ai trong s là được gọi là chung với t nếu tồn tại
một bj = ai trong t mà i – H <= j <= i + H, trong đó H = min (|s|, |t|)/2.
Đặt s’ = a’1...a’K’ là các ký tự có trong s mà chung với t theo thứ tự có trong s, t’ =
b’1...b’L’ là các ký tự có trong t mà chung với s theo thứ tự có trong t. Ta định nghĩa một sự
chuyển đổi vị trí cho s’, t’ là một vị trí i thỏa a’i = b’i . Gọi m là tổng số chuyển đổi để cho s’, t’
có các cặp a’i = b’i tối đa.
Đặt Ts’,t’ = m/2. Độ tương tự của hai chuỗi s và t của Jaro là:

Jaro( s, t ) =

1 ⎛⎜ s ' t ' s ' − Ts ',t ' ⎞⎟
•
+ +
⎟
t
s
3 ⎜⎝ s
⎠

(BT 2-8)

Winkler [33] đã tiến hành mở rộng độ đo của Jaro bằng cách chỉnh sửa trọng số cho
phần tiếp đầu ngữ giống nhau có trong hai chuỗi cần so sánh s và t. Đặt P là số ký tự của tiếp
đầu ngữ chung dài nhất của s và t. Đặt P’ = max(P,4). Ta có độ đo Jaro-Winkler được tính như
sau:


Ngơ Minh Vương

Trang 22


Truy hồi thơng tin theo thực thể có tên

Jaro − Winkler ( s, t ) = Jaro( s, t ) +

P'
(1 − Jaro( s, t ) )
10

(BT 2-9)

Các độ đo của Jaro và Jaro-Winkler được Cohen ([4]) đánh giá là độ đo tốt cho các
chuỗi ngắn như việc so sánh các họ và tên riêng.

b) Các độ đo giữa các kiểu (lớp)
Cơ sở tri thức chứa tất cả các NE của cơng trình được xây dựng dựa trên một ontology
tên là KIMO, là mạng phân cấp ngữ nghĩa các kiểu NE. Mỗi kiểu NE có thể là một kiểu ý niệm
hoặc một kiểu quan hệ. Theo [3] độ đo của Jiang và Conrath ([20]) được đánh giá là độ đo tốt
nhất trong hướng tiếp cận dựa trên mạng phân cấp ngữ nghĩa. Trong đó, lượng tin của một ý
niệm của phương pháp Jiang và Conrath được tính thơng qua xác suất xuất hiện của từ biểu
diễn cho ý niệm đó có trong tập ngữ liệu.
Các tác giả trong [29] cũng dựa trên ý tưởng của cách tiếp cận lai ghép của Jiang và
Conrath để đo khoảng cách ngữ nghĩa của các kiểu ý niệm và các kiểu quan hệ trong mạng
phân cấp KIMO với một biến đổi khác. Thay vì tính độ đo khoảng cách ngữ nghĩa giữa hai
kiểu thực thể dựa trên xác suất xuất hiện của các nhãn kiểu của nó trong tập ngữ liệu, [29] tính

độ đo khoảng cách ngữ nghĩa của hai kiểu thực thể dựa vào số lượng NE của thuộc hai kiểu
này có trong cơ sở tri thức của KIMO.
Do bản chất của một từ đại diện cho một kiểu NE xuất hiện trong mạng phân cấp
KIMO đóng vai trị chỉ là nhãn đại diện cho lớp ý niệm mà nó mơ tả. Do đó, chúng ta khơng
thể thực hiện việc tính xác suất xuất hiện của các nhãn kiểu trong một tập ngữ liệu như trong
phương pháp của Jiang-Conrath.
Mặt khác, do có sự phân cấp cấu trúc trong ontology nên một kiểu NE càng có nhiều
thể hiện trong cơ sở tri thức thì xác suất xuất hiện của các kiểu NE đó càng lớn và lượng tin
của nó sẽ càng ít. Những kiểu NE càng nằm gần gốc thì lượng tin của chúng càng ít do số
lượng thể hiện của chúng càng lớn. Ngược lại những kiểu NE càng nằm ở các nút lá thì chúng
càng chi tiết và lượng tin của chúng càng cao. Hay nói cách khác, xác suất xuất hiện của một
kiểu NE trong cơ sở tri thức sẽ là một hàm tính theo số lượng thể hiện của kiểu NE đó.

Ngơ Minh Vương

Trang 23


Truy hồi thơng tin theo thực thể có tên
Dựa vào những lý lận vừa nêu trên, [29] đã định nghĩa xác suất xuất hiện của một kiểu
ý niệm trong cơ sở tri thức được tính bởi cơng thức sau:
Pr(c) = Pop(c) / N

(BT 2-10)

Trong đó, Pop(c) là tổng số lượng NE của kiểu ý niệm c và N là tổng số lượng NE
trong cơ sở tri thức. Tổng số lượng NE của một kiểu ý niệm c trong cơ sở tri thức được tính
một cách đệ quy bằng số lượng NE trực tiếp của chính kiểu ý niệm c cộng với số lượng NE của
các kiểu ý niệm con của c.
Ta xét một ví dụ cụ thể như sau: giả sử ta có một kiểu ý niệm có nhãn là A trong mạng

phân cấp ontology có hai kiểu ý niệm con là B và C. Tổng số lượng NE của kiểu ý niệm B và
C trong cơ sở tri thức lần lượt là 35 và 50. Số lượng NE trực tiếp có kiểu ý niệm A trong cơ sở
trí thức là 15. Khi đó, tổng số lượng NE của kiểu ý niệm A có trong cơ sở tri thức sẽ là Pop(A)
= 15 + 35 + 50 = 100. Do đó, khoảng cách ngữ nghĩa giữa B và A là lượng tin cịn lại của B mà
khơng ở trong A và được tính là Dist(B, par(B)) = - log(Pr(B/A)) = - log(

35
).
100

Từ độ đo khoảng cách giữa một kiểu ý niệm c với ý niệm cha part(c) của nó trong mạng
phân cấp ontology là dist(c,part(c)) = -log

Pop(c )
, chúng ta nhận thấy rằng trong cách
Pop( part ( c ))

tính độ đo khoảng cách dựa trên số lượng NE, một kiểu ý niệm c sẽ càng giống với kiếu ý niệm
cha nó nếu tổng số lượng NE của ý niệm c càng lớn và gần bằng với số lượng NE của ý niệm
cha của nó là part(c). Điều này cũng tương tự như trong thế giới thực, nếu thế giới này có rất
nhiều con chim sẻ và có rất ít những con chim khác, thì chúng ta có khái niệm “con chim sẻ”
sẽ giống với khái niệm “con chim” nhiều hơn so với những khái niệm con chim khác. Ngược
lại, nếu thế giới này có rất ít con chim sẻ và có rất nhiều con chim khác, thì chúng ta sẽ có khái
niệm “con chim sẻ” sẽ ít giống với khái niệm “con chim” hơn so với những khái niệm con
chim khác.
Cũng dựa trên ý tưởng trên, do bản thân các từ đại diện cho các kiểu ý niệm chỉ là nhãn
khơng có nghĩa, nên độ đo được tính dựa trên số lượng thực thể của kiểu ý niệm có trong cơ sở

Ngô Minh Vương


Trang 24


Truy hồi thơng tin theo thực thể có tên
tri thức như là một giải pháp. Điều đó có ý nghĩa là, nếu số lượng thực thể của tri thức thay đổi
thì độ đo giữa các kiểu ý niệm cũng thay đổi.
Áp dụng cơng thức tính xác suất xuất hiện của một kiểu ý niệm theo số lượng thực thể
có trong cơ sở tri thức ở biểu thức 2-10 vào công thức tính khoảng cách ngữ nghĩa giữa 2 ý
niệm của Jiang và Conrath [20]:

dist JC (c1 , c2 ) = 2 × log Pr( LCS (c1 , c2 )) − (log Pr(c1 ) + log Pr(c2 ))

(BT 2-11)

Các tác giả trong [29] đề nghị cơng thức tính khoảng cách ngữ nghĩa giữa 2 kiểu ý niệm
c1 và c2 trong ontology (sau khi đã rút gọn) như sau:

dist JC ( c1 , c 2 ) = 2 × log Pop ( LCS ( c1 , c 2 )) − (log Pop ( c1 ) + log Pop ( c 2 ))

(BT 2-12)

Trong đó, LCS ( c1 , c2 ) là kiểu NE thấp nhất giữa 2 kiểu NE c1 và c2.
Độ đo khoảng cách ngữ nghĩa giữa hai kiểu ý niệm càng nhỏ thì độ giống nhau giữa
chúng càng lớn và ngược lại. Độ đo tương tự về ngữ nghĩa giữ hai kiểu ý niệm để bảo đảm tỉ lệ
thuộc khoảng [0, 1] được tính như sau:
simT − D (c1 , c 2 ) =

1
1 + dist (c1 , c 2 )


(BT 2-13)

Ngoài phương pháp của Trụ và Đạt đề xuất, Maedche ([21]) đã đưa ra một cách tính là
độ tương tự giữa hai khái niệm phụ thuộc vào số khái niệm UperwadConcept của chúng giống
nhau:

simM ( c1 , c2 ) =

UC ( c1 ) ∩ UC ( c2 )
UC ( c1 ) ∪ UC ( c2 )

(BT 2-14)

Trong đó UC (ci ) = UpwardConcept (ci ) = {c j | c j = ci ∨ c j = HigherConcept (ci )}

Ngô Minh Vương

Trang 25