- NGHIÊN CỨU CÁC TẬP RÚT GỌN VÀ LUẬT TRONG BẢNG QUYẾT ĐỊNH THEO TIẾP CẬN LÝ THUYẾT TẬP THÔ. - LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN. - Ngành: Công nghệ thông tin. - Chuyên ngành: Hệ thống thông tin Mã số: 60.48.05. - TỔNG QUAN VỀ LÝ THUYẾT TẬP THÔ. - Hệ thông tin. - Mô hình tập thô. - Error! Bookmark not defined.. - Bảng quyết định. - Tập rút gọn và tập lõi. - RÚT GỌN THUỘC TÍNH VÀ TRÍCH LỌC LUẬT TRONG BẢNG. - QUYẾT ĐỊNH THEO TIẾP CẬN TẬP THÔ. - Rút gọn thuộc tính và trích lọc luật trong bảng quyết định. - Tổng kết, phân nhóm các phương pháp rút gọn thuộc tính. - Luật quyết định và các độ đo đánh giá hiệu năng ...Error! Bookmark not defined.. - Lựa chọn, so sánh, đánh giá các phương pháp rút gọn thuộc tính. - Bookmark not defined.. - Xây dựng phương pháp rút gọn thuộc tính trong bảng quyết định sử dụng khoảng cách Error! Bookmark not defined.. - Độ đo khoảng cách. - Xây dựng khoảng cách giữa hai tri thức và các tính chất. - Phương pháp rút gọn thuộc tính sử dụng khoảng cách ...Error! Bookmark not defined.. - Phân nhóm phương pháp rút gọn thuộc tính sử dụng khoảng cách. - THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ Error! Bookmark not defined.. - Thuật toán tìm tập rút gọn sử dụng entropy Liang ...Error! Bookmark not defined.. - Một số kết quả thử nghiệm. - Kết quả thử nghiệm thuật toán tìm tập rút gọn sử dụng khoảng cách. - Kết quả thử nghiệm về trích lọc luật theo tiếp cận tập thô. - Tập thô Rough Set. - Hệ thông tin Information System. - Bảng quyết định Decision Table. - Rút gọn thuộc tính Attribute Reduction. - Tập rút gọn Reduct. - Luật quyết định Decision Rule. - Khoảng cách Distance. - Bảng thông tin về bệnh cúm. - Bảng quyết định về bệnh cúm. - Các phương pháp rút gọn thuộc tính trong tài liệu [1]Error! Bookmark not defined.. - Bảng quyết định về các xe hơi. - Bảng quyết định minh họa thuật toán tìm tập rút gọnError! Bookmark not defined.. - Kết quả thực hiện Thuật toán ELBAR và Thuật toán DBARError! Bookmark not defined.. - Tập rút gọn của Thuật toán ELBAR và Thuật toán DBARError! Bookmark not. - Kết quả thực hiện Thuật toán ELBAK và Thuật toán DBAKError! Bookmark not defined.. - Tập rút gọn tốt nhất của bộ số liệu Soybean-smallError! Bookmark not defined.. - Các luật phân lớp trên bảng quyết định rút gọn sử dụng tập thô. - Lý thuyết tập thô - do Zdzislaw Pawlak [7] đề xuất vào những năm đầu thập niên tám mươi của thế kỷ hai mươi - được xem là công cụ hữu hiệu để giải quyết các bài toán phân lớp, phát hiện luật…chứa dữ liệu không đầy đủ, không chắc chắn.. - Từ khi xuất hiện, lý thuyết tập thô đã được sử dụng hiệu quả trong các bước của quá trình khai phá dữ liệu và khám phá tri thức, bao gồm tiền xử lý số liệu, khai phá dữ liệu và đánh giá kết quả thu được. - Rút gọn thuộc tính và trích lọc luật quyết định (luật phân lớp) là hai ứng dụng chính của lý thuyết tập thô trong khai phá dữ liệu.. - Rút gọn thuộc tính thuộc giai đoạn tiền xử lý dữ liệu còn trích lọc luật thuộc giai đoạn khai phá dữ liệu. - Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa nhằm tìm tập con nhỏ nhất của tập thuộc tính điều kiện (tập rút gọn) mà bảo toàn thông tin phân lớp của bảng quyết định. - Dựa trên tập rút gọn thu được, việc sinh luật và phân lớp đạt hiệu quả cao nhất.. - Trong hai thập kỷ trở lại đây, chủ đề nghiên cứu về rút gọn thuộc tính trong bảng quyết định theo tiếp cận lý thuyết tập thô đã thu hút đông đảo cộng đồng nghiên cứu về tập thô tham gia [1]. - Có rất nhiều phương pháp rút gọn thuộc tính khác nhau đã được đề xuất sử dụng các độ đo khác nhau. - Các phương pháp điển hình được tổng kết trong tài liệu [1] là: phương pháp dựa trên miền dương, phương pháp dựa trên ma trận phân biệt, các phương pháp sử dụng độ đo entropy trong lý thuyết thông tin, các phương pháp sử dụng độ đo trong tính toán hạt, các phương pháp sử dụng độ đo khoảng cách…. - Với mong muốn tổng hợp các kết quả nghiên cứu về các phương pháp rút gọn thuộc tính trong bảng quyết định theo tiếp cận tập thô, trên cơ sở đó xây dựng phương pháp sử dụng một độ đo mới (độ đo khoảng cách), luận văn đặt ra hai mục tiêu chính sau đây:. - 1) Tổng hợp các phương pháp rút gọn thuộc tính và trích lọc luật trong bảng quyết định theo tiếp cận lý thuyết tập thô trong tài liệu [1, 2], bao gồm:. - Phân nhóm các phương pháp rút gọn thuộc tính và mối liên hệ giữa các phương pháp dựa vào định nghĩa tập rút gọn.. - Trích lọc luật trong bảng quyết định, bao gồm: luật quyết định và các độ đo đánh giá hiệu năng, sự thay đổi các độ đo đánh giá hiệu năng trên các tập rút gọn và đánh giá các phương pháp dựa trên tiêu chuẩn chất lượng phân lớp (độ hỗ trợ) của tập luật.. - 2) Xây dựng và thử nghiệm phương pháp rút gọn thuộc tính sử dụng độ đo khoảng cách, bao gồm: đề xuất độ đo khoảng cách và xây dựng công thức tính khoảng cách giữa hai tập thuộc tính. - định nghĩa tập rút gọn và độ quan trọng của thuộc tính dựa trên khoảng cách. - xây dựng thuật toán heuristic tìm một tập rút gọn tốt nhất sử dụng khoảng cách. - phân nhóm và đánh giá phương pháp sử dụng khoảng cách với các phương pháp đã có và thử nghiệm phương pháp trên các bộ số liệu mẫu từ kho dữ liệu UCI [12].. - Đối tượng nghiên cứu của luận văn là các bảng quyết định với kích thước trung bình và kích thước lớn.. - Phạm vi nghiên cứu của luận văn tập trung vào bài toán rút gọn thuộc tính ở bước tiền xử lý số liệu và trích lọc luật ở bước khai phá dữ liệu trong quá trình khai phá dữ liệu và khám phá tri thức.. - Phương pháp nghiên cứu của luận văn là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. - Về nghiên cứu lý thuyết: các mệnh đề được chứng minh chặt chẽ dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. - Về nghiên cứu thực nghiệm: luận văn thực hiện cài đặt các thuật toán, chạy thử nghiệm thuật toán với các bộ số liệu lấy từ kho dữ liệu UCI [12], so sánh và đánh giá kết quả thực nghiệm so với kết quả nghiên cứu lý thuyết, từ đó kết luận tính đúng đắn của kết quả nghiên cứu.. - Chương 1 trình bày các khái niệm cơ bản về lý thuyết tập thô của Pawlak [8]. - được sử dụng trong chương 2 và chương 3.. - Chương 2 trình bày hai nội dung chính, thứ nhất là tổng kết các công bố về các phương pháp rút gọn thuộc tính và trích lọc luật, bao gồm phân nhóm các phương pháp rút gọn thuộc tính, luật quyết định và các độ đo đánh giá hiệu năng, sự thay đổi các độ đo đánh giá hiệu năng trên các tập rút gọn của các phương pháp, đánh giá các phương pháp dựa vào chất lượng phân lớp (độ hỗ trợ) của tập luật. - Thứ hai là xây dựng phương pháp rút gọn thuộc tính sử dụng khoảng cách, bao gồm xây dựng độ đo khoảng cách, định nghĩa tập rút gọn và độ quan trọng của thuộc tính dựa trên khoảng cách, xây dựng thuật toán heuristic tìm một tập rút gọn tốt nhất sử dụng khoảng cách. - phân nhóm và đánh giá phương pháp sử dụng khoảng cách với các phương pháp đã có.. - Chương 3 trình bày kết quả thử nghiệm và đánh giá phương pháp sử dụng khoảng cách trên các bộ số liệu mẫu từ kho dữ liệu UCI [12] nhằm sáng tỏ các kết quả nghiên cứu về lý thuyết.. - Chương này trình bày các khái niệm cơ bản về lý thuyết tập thô do Pawlak [8]. - Các khái niệm cơ bản này là kiến thức nền tảng để sử dụng cho các chương sau của luận văn.. - Hệ thông tin là công cụ biểu diễn tri thức dưới dạng một bảng dữ liệu gồm p cột ứng với p thuộc tính và n hàng ứng với n đối tượng. - Một cách hình thức, hệ thông tin được định nghĩa như sau.. - Hệ thông tin là IS. - A là tập hữu hạn, khác rỗng các thuộc tính.. - A , ta ký hiệu giá trị thuộc tính a tại đối tượng u là a u. - A là một tập con các thuộc tính thì ta ký hiệu bộ các giá trị b u i. - Xét hệ thông tin IS. - Mỗi tập con các thuộc tính P A xác định một quan hệ hai ngôi trên U, ký hiệu là IND P. - thì hai đối tượng u và v không phân biệt được bởi các thuộc tính trong P. - [1] Nguyễn Long Giang, “Khai phá dữ liệu theo tiếp cận lý thuyết tập thô”, Luận án Tiến sĩ Toán học, Viện Công Nghệ Thông Tin, 2012.. - [2] Nguyễn Long Giang, Phạm Hoàng Tuyên, Nghiên cứu sự thay đổi giá trị các độ đo đánh giá hiệu năng tập luật quyết định trên các tập rút gọn, Kỷ yếu Hội thảo Quốc gia lần thứ XV “Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông”, Hà Nội Tr