Tóm tắt. Một trong những phương pháp nhằm tăng hiệu quả của việc lập
luận trên các ontology lớn là tách ontology lớn thành nhiều ontology nhỏ.
Khi đó, thay vì lập luận trên ontology lớn ban đầu, người ta có thể thực
hiện trên các ontology nhỏ. Trong bài báo này, chúng tôi nghiên cứu kỹ
thuật phân tách một ontology trong logic mô tả dựa vào các giải thuật phân
tách đồ thị. Chúng tôi tập trung vào các đặc trưng cú pháp của các axioms
của ontology. Cách tiếp cận nhằm phân tách ontology thành nhiều ontology
thành phần sao cho chúng phân biệt nhất có thể. Chúng tôi phân tích các
giải thuật và khám phá các tham số phân tách mà ảnh hưởng đến hiệu quả
của việc tính toán và lập luận. Các tham số này gồm số lượng các khái
niệm và vai trò chung trong các cặp ontology thành phần, kích cỡ của mỗi
ontology thành phần và cấu trúc của phép phân tách. Chúng tôi đề xuất
một phương pháp phân tách ontology tự động dựa vào lát cắt tối thiểu và
tiến hành thử nghiệm trên một phần của các TBox như Vedaall, tambis, .
trong hệ thống FaCT, và đưa ra một số kết quả đánh giá.
13 trang |
Chia sẻ: thanhle95 | Lượt xem: 507 | Lượt tải: 1
Bạn đang xem nội dung tài liệu Phân tách ontology trong logic mô tả dựa vào kỹ thuật phân tách đồ thị, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
JOURNAL OF SCIENCE OF HNUE
FIT., 2011, Vol. 56, pp. 59-71
PHÂN TÁCH ONTOLOGY TRONG LOGIC MÔ TẢ DỰA VÀO KỸ
THUẬT PHÂN TÁCH ĐỒ THỊ
Phạm Thị Anh Lê(∗), Đoàn Thị Quế
Khoa Công nghệ Thông tin - Đại học Sư phạm Hà Nội
(∗)Email: lepta@hnue.edu.vn
Tóm tắt. Một trong những phương pháp nhằm tăng hiệu quả của việc lập
luận trên các ontology lớn là tách ontology lớn thành nhiều ontology nhỏ.
Khi đó, thay vì lập luận trên ontology lớn ban đầu, người ta có thể thực
hiện trên các ontology nhỏ. Trong bài báo này, chúng tôi nghiên cứu kỹ
thuật phân tách một ontology trong logic mô tả dựa vào các giải thuật phân
tách đồ thị. Chúng tôi tập trung vào các đặc trưng cú pháp của các axioms
của ontology. Cách tiếp cận nhằm phân tách ontology thành nhiều ontology
thành phần sao cho chúng phân biệt nhất có thể. Chúng tôi phân tích các
giải thuật và khám phá các tham số phân tách mà ảnh hưởng đến hiệu quả
của việc tính toán và lập luận. Các tham số này gồm số lượng các khái
niệm và vai trò chung trong các cặp ontology thành phần, kích cỡ của mỗi
ontology thành phần và cấu trúc của phép phân tách. Chúng tôi đề xuất
một phương pháp phân tách ontology tự động dựa vào lát cắt tối thiểu và
tiến hành thử nghiệm trên một phần của các TBox như Vedaall, tambis, ...
trong hệ thống FaCT, và đưa ra một số kết quả đánh giá.
1. Mở đầu
Các nghiên cứu về ontology dựa vào Logic mô tả (DLs) trước đây thường
tập trung vào các nhiệm vụ như thiết kế ontology, phát triển ontology, tích hợp
ontology,. . . Xuất phát từ ý tưởng muốn xử lý một cách hiệu quả với các ontology
lớn, thay vì tích hợp các ontology chúng tôi xem xét bài toán phân tách ontology.
Phân tách một ontology lớn thành nhiều ontology nhỏ và thực hiện lập luận trên
các ontology nhỏ. Có nhiều phương pháp phân tách ontology nhằm phục vụ các yêu
cầu khác nhau. Mục đích chính của chúng tôi là làm thế nào để chọn được một phép
phân tách "tốt". Một phép phân tách được gọi là "tốt" nếu nó bảo toàn thông tin,
bảo toàn các kết quả lập luận [5] và làm tăng hiệu quả của việc lập luận. Việc phân
tích các giải thuật lập luận đã gợi ý cho chúng tôi đề xuất những tham số này: số
lượng các khái niệm và vai trò trong các ánh xạ ngữ nghĩa giữa các thành phần phân
tách, kích thước của mỗi ontology thành phần và cấu trúc của đồ thị phân tách.
59
Phạm Thị Anh Lê và Đoàn Thị Quế
Trong bài báo trình bày một phương pháp phân tách dựa vào lát cắt tối thiểu,
phương pháp này sử dụng cấu trúc đồ thị để biểu diễn ontology. Nội dung nghiên
cứu chính bao gồm: Giới thiệu về DLs và biểu diễn cơ sở tri thức trong DLs; Mô
tả cách biểu diễn ontology bởi đồ thị vô hướng (đồ thị ký hiệu) và định nghĩa một
phép phân tách phủ (overlap decomposition) của một TBox, các tiêu chuẩn cho một
phép phân tách tốt và thuật toán phân tách dựa vào lát cắt tối thiểu; Thảo luận
về phương pháp và minh họa thuật toán phân tách bởi một ví dụ nhỏ; Kết luận và
hướng phát triển của bài báo.
2. Nội dung nghiên cứu
2.1. Biểu diễn ontology trong Logic mô tả
2.1.1. Logic mô tả
Logic mô tả (Description Logics - DLs) là một họ các ngôn ngữ hình thức biểu
diễn tri thức dựa trên logic (logic-based Knowledge Representation). DLs biểu diễn
tri thức thuật ngữ của một miền ứng dụng bằng cách định nghĩa các khái niệm (gọi
chung là thuật ngữ - terminology), sau đó sử dụng các khái niệm này để đặc tả các
thuộc tính của đối tượng hay của cá thể trong miền ứng dụng (mô tả thế giới).
Trong các ngôn ngữ DLs thì miền ứng dụng được xem là các cá thể có thể gộp
nhóm thành các lớp, được gọi là các “tên khái niệm” (concept names); và các tính
chất hay thuộc tính của các cá thể là các quan hệ hai ngôi, được gọi là các “tên vai
trò” (role names). Ví dụ, các khái niệm STUDENT (minh họa một lớp các sinh viên),
PERSON (minh họa lớp người), PUBLICATION (minh họa lớp các công trình), vai
trò hasPub (có công trình) thể hiện quan hệ giữa PERSON và PUBLICATION
2.1.2. Biểu diễn tri thức trong Logic mô tả
Hình 1. Cấu trúc hệ thống
biểu diễn tri thức dựa trên Logic mô tả
Một hệ thống biểu diễn tri thức
(Knowledge Representation system -
KR system) dựa trên Logic mô tả cung
cấp cơ chế lập luận, các chương trình
ứng dụng trên cơ sở tri thức. Cấu trúc
hệ thống được mô tả như sau: Cơ sở
tri thức trong DLs gồm hai thành phần
phân biệt là tri thức nội hàm (inten-
sional knowledge) hay tri thức chung về
miền ứng dụng - gọi là TBox (Termino-
logical Box) và tri thức mở rộng (exten-
sional knowledge) hay tri thức cụ thể về
các đối tượng riêng biệt trong miền - gọi
là ABox (Assertional Box):
60
Phân tách ontology trong logic mô tả dựa vào kỹ thuật phân tách đồ thị
• TBox (ký hiệu T) bao gồm các từ vựng (vocabulary), được biểu diễn dưới dạng
thuật ngữ (terminology) mô tả những đặc điểm chung của các khái niệm. Mối
quan hệ giữa các khái niệm là quan hệ bao hàm.
• ABox (ký hiệu: A) bao gồm các tri thức mở rộng, biểu diễn dưới dạng các
khẳng định (assertions), mô tả từng cá thể thuộc miền ứng dụng. Các cá thể
được định danh theo khái niệm trong TBox.
Từ vựng bao gồm các khái niệm (concepts) và các vai trò (roles). Ngoài các
khái niệm nguyên tử (atomic concepts) và các vai trò nguyên tử (atomic roles) thì
các ngôn ngữ Logic mô tả đều cho phép người dùng xây dựng các khái niệm và vai
trò phức tạp - gọi là các tiên đề (axioms).
Tiên đề là một biểu diễn về mối quan hệ giữa các khái niệm và các vai trò.
Tiên đề dùng để giới thiệu tên cho các khái niệm (vai trò) mới hoặc để khẳng định
về quan hệ bao hàm giữa các khái niệm (vai trò). Một cách tổng quát, tiên đề có
các dạng:
1. A ∨ C đặc tả khái niệm nguyên tử
2. A ≡ C định nghĩa khái niệm
3. C ∨D bao hàm khái niệm tổng quát (General Concept Inclusion - GCI)
4. C ≡ D đẳng thức khái niệm
5. R ∨ S bao hàm vai trò
6. R ≡ S đẳng thức vai trò
Trong đó: A là một tên khái niệm (concept names); C,D là các biểu diễn khái
niệm (concept expressions); R, S là các vai trò. Tiên đề dạng 1, 3, và 5 gọi là các
bao hàm (inclusions) còn tiên đề dạng 2, 4, và 6 gọi là các đẳng thức (equalities).
Lưu ý rằng, các tiên đề dạng C ≡ D tương đương với hai tiên đề C ∨D và D ∨ C.
Do vậy, tiên đề dạng 1, 2 và 4 có thể đưa về dạng 3, tiên đề dạng 6 có thể đưa về
dạng 5. Trong phạm vi bài báo chúng tôi chỉ xem xét các tiên đề khái niệm (dạng
1, 2, 3 và 4) và dạng tổng quát nhất là các GCI [2].
Ví dụ: Một người phụ nữ (Woman) có thể được định nghĩa là một người
(Person) có giới tính là nữ (Female) như sau: Woman ≡ Person ∪ Female.
Định nghĩa khái niệm (concept definition) là một đẳng thức mà vế trái là một
khái niệm nguyên tử được định nghĩa, vế phải là mô tả khái niệm phức tạp.
Ví dụ: Mother ≡ Woman ∪ ∃ hasChild. Person là một định nghĩa trong đó
Mother là tên tượng trưng cho mô tả phức tạp ở vế phải.
Tên tượng trưng còn được dùng như dạng rút gọn (abbreviation) trong các
mô tả khác, ví dụ nếu đã định nghĩa Father (tương tự Mother) thì Parent được định
nghĩa là: Parent ≡ Mother t Father.
Sau đây là một ví dụ về TBox mô tả các quan hệ gia đình (Hình 2):
61
Phạm Thị Anh Lê và Đoàn Thị Quế
Woman Person ∪ Female
Man ≡ Person ∪ ¬ Woman
Mother ≡ Woman ∪ ∃ hasChild.Person
Father ≡ Man ∪∃ hasChild.Person
Parent ≡ Father t Mother
Grandmother ≡ Mother ∪ ∃ hasChild.Parent
Wife ≡ Woman ∪ ∃ hasHusband.Man
MotherWithoutDaughter ≡ Mother ∪ ∀ hasChild. ¬ Woman
Hình 2. TBox Tfam với các khái niệm trong quan hệ gia đình
Các khái niệm nguyên tử trong TBox T được chia thành hai tập hợp là tập
các ký hiệu tên NT (name symbols) xuất hiện ở vế trái và tập các ký hiêu cơ sở BT
(base symbols) xuất hiện ở vế phải của các tiên đề. Các ký hiệu tên thường gọi là
các khái niệm được định nghĩa (defined concepts) còn các ký hiệu cơ sở thường gọi
là các khái niệm nguyên tử (primative concepts).
Việc lập luận cũng sẽ được thực hiện trên cả hai thành phần TBox và ABox.
Các dịch vụ lập luận trên hai thành phần cũng khác nhau. Trong phạm vi bài báo
này chúng tôi chỉ xem xét cơ sở tri thức ở mức TBox. Vì vậy, việc phân tách ontology
sẽ được thực hiện trên TBox.
2.2. Phân tách TBox
2.2.1. Cách tiếp cận dựa vào cú pháp
a. Đặc điểm phân tách
Mục đích của chúng tôi là tách tập hợp các GCI trong TBox ban đầu thành
nhiều tập GCI trong các TBox nhỏ sao cho chúng là độc lập và có số lượng các GCI
là cân bằng. Sau đó, các TBox này được biểu diễn bởi một TBox phân tán và việc
lập luận được thực hiện trên TBox phân tán. Trong bài báo này, chúng tôi chỉ xem
xét các thuật toán phân tách TBox dựa trên cách tiếp cận cú pháp, tức là dựa vào
các cấu trúc của GCI.
Các khái niệm và vai trò của ontology ban đầu sẽ được duy trì sau khi thực
hiện phân tách. Chúng tôi đề xuất kỹ thuật phân tách dựa vào đồ thị. Sau đây xét
trường hợp đơn giản nhất, phân tách một TBox thành hai TBox nhỏ hơn.
Chúng tôi định nghĩa phép phân tách một TBox và biểu diễn các TBox kết
quả như một TBox phân tán (gồm các TBox và các ánh xạ ngữ nghĩa giữa chúng).
Phương pháp phân tách lựa chọn bằng việc xem xét khía cạnh lập luận logic trên
phép phân tách. Chúng tôi cần trả lời các câu hỏi sau:
- Tiêu chuẩn cụ thể cho một phép phân tách tốt là gì ?
62
Phân tách ontology trong logic mô tả dựa vào kỹ thuật phân tách đồ thị
- Một phép phân tách như vậy có thể được tính toán hiệu quả như thế nào ?
Các câu hỏi này cũng được đưa ra với bài toán phân đoạn ảnh và phân cụm
dữ liệu. Trong trường hợp DLs tổng quát, mục đích của chúng tôi là không giảm độ
phức tạp tính toán, mà các kết quả lập luận trên ontology ban đầu được bảo toàn
với các ontology phân tách.
Theo phân tích tính toán của các thuật toán lập luận dựa vào phân tách
ontology cung cấp một metric để xác định các tham số phân tách mà ảnh hưởng
đến tính toán của chúng tôi: kích thước phần chung giữa các TBox thành phần,
kích thước của mỗi TBox thành phần, và cấu trúc của đồ thị phân tách. Mục đích
của chúng tôi là tối thiểu hóa sự liên kết giữa các TBox khác nhau và tối đa hóa
sự liên kết trong mỗi TBox sau phân tách. Hơn nữa, các TBox này phải duy trì các
tính chất phân tách được đề cập trong [5]. Các tham số này gợi ý cho chúng tôi giải
thuật tham lam thực hiện phân tách ontology.
b. Định nghĩa phép phân tách
Với cách tiếp cận này, chúng tôi xét các TBox với các tập ký hiệu tên khái
niệm và tên vai trò nguyên tử trong các tiên đề.
Một TBox T trong ngôn ngữ L được phân rã thành tập các ký hiệu . Phép
phân tách T thành T1, . . . ,Tn sao cho các TBox T1, . . . ,Tn được thiết lập bởi L
và các ký hiệu được lấy từ
∑
,T1[..[Tn = T
2.2.2. Biểu diễn TBox bởi đồ thị ký hiệu
Trong phần này, chúng tôi biểu diễn TBox như một đồ thị kề vô hướng. Cho
một TBox T với N axioms:
- Trước hết, khai triển tất cả các axioms trong TBox đã cho thành các biểu
thức mà chỉ bao gồm các khái niệm và vai trò nguyên tử (primitive concepts and
roles). Ký hiệu Ex(Ai) là tập tất cả các khái niệm và vai trò nguyên tử xuất hiện
trong axiom Ai.
- Mỗi khái niệm (vai trò) nguyên tử được gọi là một ký hiệu.
Định nghĩa 2.1. (Đồ thị ký hiệu - symbol graph): Một đồ thị G = (V,E), trong
đó V là tập các đỉnh và E là tập các cung, được gọi là đồ thị ký hiệu nếu mỗi đỉnh
v ∈ V là một ký hiệu, một cung (vi, vj) ∈ E nếu vi, vj xuất hiện trong cùng một tiên
đề (axiom).
Định nghĩa 2.2. (Đồ thị phân tách): Một phép phân tách đồ thị Gp = (Vp, Ep) là
một đồ thị liên thông của các đồ thị thành phần (đồ thị con) Gi. Mỗi đỉnh v ∈ Vp là
một đồ thị thành phần Gi, mỗi cung eij = (vi, vj) ∈ Ep là một tập các ký hiệu chung
giữa Gi và Gj.
63
Phạm Thị Anh Lê và Đoàn Thị Quế
2.2.3. Phân tách dựa vào lát cắt tối thiểu
Trước hết, chúng tôi nhắc lại một số khái niệm trong lý thuyết đồ thị [3] sẽ
được sử dụng trong các phần tiếp theo của bài báo.
Định nghĩa 2.3. Cho đồ thị vô hướng G = (V,E), với |V | = n, |E| = m. Cho
x, y ∈ V , x gọi là đỉnh láng giềng của y (và y là đỉnh láng giềng của x) nếu
(x, y) ∈ E. Tập các đỉnh láng giềng của x là N(x) = {y 6= x|(x, y) ∈ E}. Với
X ⊆ Y,N(X) = ∪x∈XN(x). Bậc của một đỉnh là lực lượng của tập hợp các đỉnh
láng giềng của nó.
Định nghĩa 2.4. (Lát cắt đỉnh tối thiểu -(a, b) - minimal vertex separators): Một
tập hợp đỉnh S được gọi là lát cắt đỉnh -(a, b) nếu {a, b} ⊂ V \ S và mọi đường đi
nối a và b trong G đều đi qua ít nhất 1 đỉnh trong S. Nếu S là một lát cắt đỉnh -
(a, b) và nó không chứa một lát cắt đỉnh - (a, b) khác thì S được gọi là lát cắt đỉnh
tối thiểu -(a, b).
Hai đỉnh a, b được nói là kề nhau nếu có 1 cung nối a và b trong G. Cho a, b
là các đỉnh không kề nhau. Nếu S là một lát cắt −(a, b) tối thiểu mà chỉ chứa các
láng giềng của a thì S được gọi là gần với a.
Định nghĩa 2.5. (thành phần liên thông - connectivity): Cho N(a, b) là lực lượng
nhỏ nhất của một lát cắt đỉnh - (a, b). Thành phần liên thông của đồ thị G là N(a, b)
tối thiểu cho mọi cặp a, b ∈ V và a, b không kề nhau.
Định nghĩa 2.6. (Đồ thị đầy đủ - Cliques): Một đồ thị đầy đủ là một đồ thị mà
tập cung bao gồm tất cả các cung giữa các cặp đỉnh của đồ thị. Ký hiệu K[S] là đồ
thị đầy đủ xây dựng trên các đỉnh của S.
Định nghĩa 2.7. (đồ thị đầy đủ cực đại - maximum cliques): Một đồ thị cực đại
đầy đủ trong đồ thị G là một đồ thị đầy đủ G[S] mà không có tập đỉnh S ⊃ S với
G[S] là một đồ thị đầy đủ. Tập hợp các đồ thị đầy đủ tối thiểu của G được biểu thị
bởi KG.
Định nghĩa 2.8. (Đồ thị liên thông): Một đồ thị G là liên thông nếu với mỗi cặp
đỉnh (u, v) tồn tại một đường đi từ u đến v. Nếu G là không liên thông thì một đồ
thị con liên thông C của G được gọi là một thành phần liên thông (cực đại) nếu
không tồn tại một đồ thị con liên thông C của G sao cho C là một đồ thị con của
C ′.
Lát cắt đỉnh tối thiểu có thể định nghĩa cách khác như sau: S là một lát cắt
tối thiểu của đồ thị G = (V,E) nếu và chỉ nếu có hai thành phần liên thông khác
nhau của G[V − S] sao cho mỗi đỉnh của S có một đỉnh láng giềng trong cả hai
thành phần này. Định nghĩa này như một bổ đề đã được chứng minh trong [4].
64
Phân tách ontology trong logic mô tả dựa vào kỹ thuật phân tách đồ thị
Nếu S là một lát cắt −a, b tối thiểu mà chỉ chứa các láng giềng của a thì S
được gọi là gần với a.
Giải thuật.
Chúng tôi trình bày một giải thuật đệ qui sử dụng thuật toán của Even [9] để
tìm các tập đỉnh mà tách một đồ thị thành các phần. Giải thuật trả kết quả là một
tập đỉnh xác định sự phân tách các đồ thị con. Giải thuật lấy đầu vào là đồ thị ký
hiệu G = (V,E) của một TBox. Các bước của thuật toán được mô tả toám tắt như
sau:
Input: G = (V,E)
Output: đồ thị liên thông Gp = (Vp, Ep)
Method:
- Tìm tập các lát cắt đỉnh tối thiểu của G:
+ Chọn một cặp đỉnh không kề nhau (a, b) tùy ý và tính tập các lát cắt
−ab tối thiểu
+ Lặp quá trình này trên mọi cặp đỉnh không kề nhau x, y
- Tìm lát cắt đỉnh tối thiểu toàn cục S∗ giữa tất cả các đỉnh trong G
- Tách G bởi S∗ thành hai đồ thị con G1, G2, với S∗ được chứa trong cả G1 và
G2.
- Tạo một đồ thị vô hướng Gp = (Vp, Ep), với Vp = G1, G2 và Ep = S∗
Thuật toán tìm các lát cắt đỉnh tối thiểu.
Dưới đây mô tả một thuật toán liệt kê tất cả các lát cắt đỉnh (a, b) tối thiểu
từ một cặp đỉnh a, b không kề nhau theo kiểu tìm kiếm ưu tiên chiều rộng (breadth
first search - BFS).
procedure separators (G, a, b, T,Q)
input: Đồ thị G và hai đỉnh a không kề b
Tập hợp T gồm các lát cắt đỉnh (a, b) tối thiểu S
output: Tập Q gồm tất cả các lát cắt đỉnh (a, b) tối thiểu trong đồ thị G
begin
T := Ø
65
Phạm Thị Anh Lê và Đoàn Thị Quế
for each S ∈ T do
begin
Xác định Ca ;
{Ca là thành phần liên thông của G[V − S] có chứa a}
for each x ∈ S không kề với a do
begin
Xác định ∆;
{ là lát cắt đỉnh (x, a) tối thiểu trong Ca(x) gần với x}
Xác định Ca;
{Ca là thành phần liên thông của đồ thị G[Ca −∆] chứa a}
Xác định N ;
{N là tập các đỉnh trong S mà không có đỉnh kề trong Ca}
S∗ := (S ∪∆) \N ;
T := T ∪ {S∗}
{Bổ sung S∗ vào T nếu T chưa có S∗}
end for
end for;
Q := Q ∪ T ;
Separators (G, a, b, T,Q)
end.
2.3. Đánh giá và thực nghiệm
Để đơn giản chúng tôi đưa ra một ví dụ minh họa cho các thuật toán trên:
Xét một phần TBox Tfam (Hình 2) mô tả các quan hệ gia đình gồm 8 tiên đề được
ký hiệu lần lượt A1, A2, ..., A8, và ký hiệu các khái niệm và vai trò nguyên tử của
Tfam như sau:
66
Phân tách ontology trong logic mô tả dựa vào kỹ thuật phân tách đồ thị
Grandmother: C1 Person: C7
Parent: C2 Wife: C8
Father: C3 Man: C9
Mother: C4 Female: C10
MotherWithoutDaughter: C5 hasChild: R1
Woman: C6 hasHusband: R2
(A1) : C6 ≡ C7 ∪ C10 (A5) : C2 ≡ C3 † C4
(A2) : C9 ≡ C7 ∪ ¬C6 (A6) : C1 ≡ C4 ∪ ∃R1.C2
(A3) : C3 ≡ C9∃R1.C7 (A7) : C8 ≡ C6 ∪ ∃R2.C9
(A4) : C4 ≡ C6∃R1.C7 (A8) : C5 ≡ C4 ∪ ∀R1.¬C6
Hình 3. Tfam biểu diễn dưới dạng ký hiệu
Tập các khái niệm và vai trò nguyên tử trong Tfam là:
Ex(Tfam) = {C1;C2;C3;C4;C5;C6; ;C7;C8;C9;C10;R1;R2}
.
Số các khái niệm và vai trò nguyên tử trong Tfam là: |Ex(Tfam| = 12.
Biểu diễn cơ sở tri thức bằng đồ thị.
Tfam (Hình 3) có thể được biểu diễn bằng một đồ thị kề vô hướng, trong đó
các đỉnh của đồ thị này ứng với các ký hiệu, các cạnh của đồ thị nối hai đỉnh ứng
với hai ký hiệu thuộc cùng một tiên đề. Do đó mỗi tiên đề sẽ được biểu diễn như
một clique.
Hình 4. Đồ thị ký hiệu biểu diễn TBox Tfam trước phân tách
67
Phạm Thị Anh Lê và Đoàn Thị Quế
Hình 5. Giao diện chọn một cặp đỉnh để tìm lát cắt tối thiểu
Hình 6. Kết quả tìm tổng số lát cắt
và tất cả các lát cắt tối thiểu của một cặp đỉnh
Hình 7. Các lát cắt của đồ thị tìm được sau khi loại bỏ trùng lặp
68
Phân tách ontology trong logic mô tả dựa vào kỹ thuật phân tách đồ thị
Hình 8a. Kết quả chia đồ thị ký hiệu
của Tfam với lát cắt tối thiểu S∗ = {C6, C9}
Hình 8b. Kết quả chia đồ thị ký hiệu
của Tfam với lát cắt tối thiểu S∗ = {C6, C7}
Nếu dựa trên tiêu chí cân bằng số tiên đề giữa các TBox thành phần thì
S∗ = {C3, R1C6, C7}.
Dùng S∗ để chia ta thu được hai nhóm ký hiệu là {C3, R1, C6, C7, C1, C2, C4, C5}
và {C3, R1, C6, C7, C8, C9, C10, R2}. Do đó ta nhận được hai TBox con tương ứng
sau: T1 = {A4, A5, A6, A8} và T2 = {A1, A2, A3, A7}. Số các ký hiệu trong S∗ là
|S∗| = |{C3, R1C6, C7}| = 4. Lực lượng của hai TBox lần lượt là N1 = 4;N2 = 4.
Khi đó đồ thị ký hiệu của Tfam sau khi phân tách sẽ có hình ảnh như sau:
69
Phạm Thị Anh Lê và Đoàn Thị Quế
Hình 8c. Kết quả chia đồ thị ký hiệu
của Tfam với lát cắt tối thiểu S∗ = {C3, R1, C6, C7}
Kết quả chia đồ thị ký hiệu của Tfam với lát cắt tối thiểu S∗ = {C3, R1C6, C7}
Các TBox kết quả T1 và T2 nhận được sau khi thực hiện phân tách áp dụng
kỹ thuật phân tách đồ thị dựa vào lát cắt tối thiểu bảo toàn tất cả các khái niệm,
vai trò và tiên đề của Tfam ban đầu. Ngoài ra, T1 và T2 thỏa mãn các tiêu chí phân
tách đã đặt ra.
Chúng tôi đã áp dụng thuật toán tách đồ thị dựa vào lát cắt tối thiểu. Phương
pháp này trả ra kết quả thỏa mãn các tính chất đưa ra. Tất cả các khái niệm, vai
trò, và các tiên đề đều được bảo toàn qua phép phân tách. Quan hệ giữa chúng được
biểu diễn bởi các cung trong đồ thị ký hiệu liên thông. Phương pháp này tối thiểu
hóa ký hiệu dùng chung giữa các đồ thị phân tách đảm bảo tính chất các TBox
phân tách là độc lập. Tuy nhiên, để nhận được các TBox kết quả, đòi hỏi phải có
kỹ thuật chuyển các đồ thị thu được sau phép phân tách thành tập các tập hợp tiên
đề cho các TBox tương ứng.
3. Kết luận
Các phương pháp phân tách TBox của chúng tôi đều nhằm mục đích là giảm
số lượng các CGI, đây là một trong những nhân tố chủ yếu gây nên độ phức tạp
cho các thuật toán lập luận. Phương pháp phân tách TBox dựa vào lát cắt tối thiểu
mới chỉ xét các tiên đề dưới khía cạnh cú pháp, tức là chỉ xét cấu trúc của các tiên
đề. Chúng tôi xét trường hợp đơn giản nhất, xem các khái niệm và vai trò nguyên
tử có vai trò như nhau trong các tiên đề. Tuy nhiên, trong thực tế thì chúng có ý
nghĩa khác nhau, chẳng hạn các mô tả khái niệm Ct D và C ∪D sẽ được biểu diễn
bởi cùng một đồ thị ký hiệu, mặc dù ý nghĩa của chúng là khác nhau. Do đó, chúng
70
Phân tách ontology trong logic mô tả dựa vào kỹ thuật phân tách đồ thị
tôi sẽ tiếp tục nghiên cứu các phương pháp phân tách ontology có tính đến m