Chuyên Đề Seminar Cơ sở Tri Thức

ĐH CNTT Tp HCM Seminar Cơ sở Tri Thức

LỜI NÓI ĐẦU
Những đồ thị là một khái niệm mạnh hữu ích cho những nhiệm vụ khác nhau trong khoa học và kỹ thuật. Trong những ứng dụng như sự nhận dạng và sự phục hồi thông tin, đối tượng đồng dạng là một vấn đề quan trọng. Nếu những đồ thị được sử dụng cho sự biểu diễn đối tượng, rồi là vấn đề của việc xác định sự giống nhau của những đối tượng quay vào trong vấn đề của sự so sánh đồ thị.
Một trong nhiều dạng thức so sánh đồ thị chung nhất bao gồm đồ thị và sự dò tìm đồ thị con đồng dạng, sự trích ra đồ thị con chung cực đại và dung sai đồ thị. Một số giải pháp cho tất cả những nhiệm vụ này đã được đề xướng trong tài liệu, nhưng mọi thứ hứng chịu độ phức tạp tính toán cao của sự so sánh đồ thị vốn có. Một vấn đề bổ sung xuất hiện trong những ứng dụng ở đây một đồ thị đầu vào sẽ được so sánh phù hợp với tới đồ thị đơn khác trong toàn bộ cơ sỡ dữ liệu của những đồ thị so sánh dưới một dạng thức đã cho. Nếu cơ sở dữ liệu lớn, sự so sánh tuần tự của đồ thị đầu vào với mỗi đồ thị từ cơ sở dữ liệu việc sử dụng những cách tiếp cận truyền thống trở nên không thể làm được.
Hai chiến lược cơ bản đã được phát triển. Chiến lược thứ nhất nhằm mục tiêu xác định vai trò thành viên trong một loại của đồ thị đầu vào dựa trên một cây quyết định phân loại các mẫu. Chiến lược thứ hai dựa trên ý kiến về phép phân loại. Phép phân loại này chỉ xác định một đồ thị mẫu đầu vào có thuộc về một loại nào đó hay không?
Trong seminar này, sự so sánh của những đồ thị đầu vào với cơ sở dữ liệu của những đồ thị được học. Những dạng thức lấy lại khác nhau, tức là là đồng dạng đồ thị, đồng dạng đồ thị con, và dung sai đồ thị, sự so sánh được xem xét. Cách tiếp cận theo đuổi được dựa trên so sánh những vector đặc trưng đã được rút từ những đồ thị. Ý tưởng sẽ sử dụng những đặc tính mà có thể được tính toán nhanh từ một đồ thị. Đưa ra một số tiềm năng lớn của những đặc tính như vậy. Sự so sánh các vector đặt trưng của đồ thị, quan trọng là tiết kiệm thời gian trong tính toán có thể thực hiện nhanh hơn trong những đồ thị phức tạp làm nổi bật sự trích ra và nhánh ngang, quyết định so sánh tới một đồ thị đầy đủ.
MỤC LỤC
LỜI NÓI ĐẦU 1
MỤC LỤC 2
Chương I 4
TỔNG QUAN 4
I.1 Giới thiệu 4
I.1.1 Những đồ thị và đồ thị thích ứng 4
I.1.2 Sử dụng cây quyết định và cơ sở dữ liệu 5
Chương II 7
CƠ SỞ LÝ THUYẾT VÀ PHƯƠNG PHÁP NGHIÊN CỨU 7
II.1 LÝ THUYẾT ĐỒ THỊ 7
II.1.1 Định nghĩa và chú thích: 7
II.2 GIẢI THUAT TÌM KIEM NHÁNH CÂY 11
II.2.2 Phân loại bằng Phương pháp tìm kiếm nhánh cây: 11
II.3 Chuẩn tách: 13
II.3.1 Chuẩn lợi ích: 13
II.3.2 Chuẩn tỷ số lợi ích: 14
II.4 Phép mở rộng Rainforest cho tập dữ liệu lớn: 15
Chương III 17
NỘI DUNG NGHIÊN CỨU VÀ KẾT QUẢ 17
III.1 SỬ DỤNG ĐỒ THỊ DỮ LIỆU CÓ CHỌN LỌC NHỮNG VECTORS ĐẶT TRƯNG 17
III.1.1 Những đặt trưng Đồ thị 18
III.1.2 Thuật toán lọc Vector đặt trưng 19
III.1.3 Thuật toán lọcVector đặt trưng mở rộng 19
III.2 CÂY QUYET ĐỊNH CUA ĐO THỊ LỌC CƠ SỞ DỮ LIEU 20
III.2.1 Lọc Cây Quyết Định 20
III.2.2 Đồ thị đồng dạng cây quyết định 20
III.2.3 Đồ thị nhánh 21
III.2.4 Đồ thị con đồng dạng cây quyết định 22
III.2.5 Giới thiệu phần cây đồng dạng của đồ thị 23
III.2.6 Cây đồ thị đồng dạng đường ngang 23
III.2.7 “Cây đồ thị con đồng dạng” Nhánh ngang 24
III.2.8 Lọc kết hợp 24
III.2.9 Những lỗi có thể bỏ qua của cây quyết định 25
III.2.10 Cây quyết định dẫn xuất error-tolerant 25
III.2.11 Decision Tree Traversal 26
III.2.12 Conclusions 29
Chương IV 30
KẾT QUẢ THỬ NGHIỆM 30
IV.1 TẬP DỮ LIỆU ĐỒ THỊ 30
IV.2 CƠ SỠ DỮ LIỆU ĐO THỊ LỌC NGHIÊN CỨU THỰC HIỆN 31
IV.2.1 Sự Lọc Vector Đặt trưng Những kết luận 31
IV.3 LỌC BANG CAY QUYET ĐỊNH 32
Chương V 35
KẾT LUẬN VÀ KIẾN NGHỊ 35
V.1 Những kết luận 35
V.1.1 Lọc cơ sở dữ liệu 35
V.1.2 Ghép chính xác dựa trên kết quả lọc 35
V.1.3 Sơ đồ lọc cơ sở dữ liệu 36
V.1.4 Lọc vectơ đặc tính 37
V.2 Hướng phát triển 40
TÀI LIỆUTHAM KHẢO 43