Phân tách ontology trong logic mô tả dựa vào kỹ thuật phân tách đồ thị

Chia sẻ: Minh Minh | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

21
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong bài báo này, các tác giả đề 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á.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phân tách ontology trong logic mô tả dựa vào kỹ thuật phân tách đồ thị

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ả 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ề Hình 1. Cấu trúc hệ thống các đối tượng riêng biệt trong miền - gọi biểu diễn tri thức dựa trên Logic mô tả 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 Tf am 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 P 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∈X N(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 Tf am (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 Tf am 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. Tf am 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 Tf am là: Ex(Tf am ) = {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 Tf am là: |Ex(Tf am | = 12. Biểu diễn cơ sở tri thức bằng đồ thị. Tf am (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 Tf am 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 Tf am 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 Tf am 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 , R1 C6 , 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 , R1 C6 , 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 Tf am 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 Tf am 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 Tf am với lát cắt tối thiểu S ∗ = {C3 , R1 C6 , 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ức độ phụ thuộc của các ký hiệu vào các tiên đề dựa vào các tạo tử liên kết và ngữ nghĩa của các tiên đề. REFERENCES [1] F. Baader, I. Horrocks, and U. Sattler, 2002. Description logics as ontology lan- guages for the semantic web. In KI Kunstliche Intelligrnz. [2] F. Baader and W. Nutt, 2003. Basic Description Logics. Spinger. [3] Dieter Jungnickel, Graph, Networks and Algorithms, Spinger 1999. [4] Kirill Shoikhet and Dan Geiger, 1992. Finding optimal triangulations via minimal vertex separators. Proceedings of the 3rd International Conference, p.270-281, Cambridge, MA, October. [5] Thi Anh Le Pham, Nhan Le Thanh and Peter Sander, 2008. Decomposition-based reasoning for large knowledge bases in description logics. Integrated Computer- Aided Engineering, Vol. 15, No 1, p. 53-70. [6] Dmitry Tsarkov, Ian Horrocks, and Peter F. Patel-Schneider, 2007. Optimising terminological reasoning for expressive description logics. J. of Automated Rea- soning, To appear. [7] E. Amir and S. McIlraith, 2005. Partition-based logical reasoning for first-order and propositional theories. Artificial Intelligence, Vol. 162, pp. 49-88, February. [8] A. Berry, J.P. Bordat, and O. Cogis, 1999. Generating all the minimal separators of a graph. Workshop on Graph-theoretic Concepts in Computer Science (WG’99), Vol. 1665 of Lecture Notes in Computer Science, pp. 167-172, Spinger Verlag. [9] S. Even, 1979. Graph Algorithms. Computer Science Press. ABSTRACT Decomposing an ontology in Description Logics (DLs) based on graph partitioning algorithms In this paper, we investigate the problem of decomposing an ontology in De- scription Logics (DLs) based on graph partitioning algorithms. Also, we focus on syntax features of axioms in a given ontology. Our approach aims at decomposing the ontology into many sub ontologies that are as distinct as possible. We analyze the algorithms and exploit parameters of partitioning that influence the efficiency of computation and reasoning. These parameters are the number of concepts and roles shared by a pair of sub-ontologies, the size (the number of axioms) of each sub- ontology, and the topology of decomposition. We provide one concrete approach for automatically decomposing the ontology, that is called partitioning based on mini- mal separator. We also tested on some parts of used TBoxes as Vedaall, tambis, ... in the system FaCT and propose estimated results. 71