Tóm tắt Luận án Tiến sĩ Toán học: Rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai

1<br /> <br /> BỘ GIÁO DỤC VÀ ĐÀO TẠO<br /> <br /> VIỆN HÀN LÂM KHOA HỌC<br /> VÀ CÔNG NGHỆ VIỆT NAM<br /> <br /> HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ<br /> <br /> ……..….***…………<br /> <br /> VŨ VĂN ĐỊNH<br /> <br /> RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH<br /> KHÔNG ĐẦY ĐỦ THEO TIẾP CẬN TẬP THÔ DUNG SAI<br /> <br /> Chuyên ngành: Cơ sở toán học cho tin học<br /> Mã số: 62.46.01.10<br /> <br /> TÓM TẮT NLUẬN ÁN TIẾN SĨ TOÁN HỌC<br /> <br /> HÀ NỘI - 2016<br /> <br /> 2<br /> <br /> Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ Viện Hàn lâm Khoa học và Công nghệ Việt Nam<br /> <br /> Người hướng dẫn khoa học 1: GS.TS Vũ Đức Thi<br /> Người hướng dẫn khoa học 2: PGS.TS Ngô Quốc Tạo<br /> <br /> Phản biện 1: …<br /> Phản biện 2: …<br /> Phản biện 3: ….<br /> <br /> Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại<br /> Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công<br /> nghệ Việt Nam vào hồi … giờ .. ’, ngày … tháng … năm 2016<br /> <br /> Có thể tìm hiểu luận án tại:<br /> - Thư viện Học viện Khoa học và Công nghệ<br /> - Thư viện Quốc gia Việt Nam<br /> <br /> 1<br /> <br /> MỞ ĐẦU<br /> 1. Tính cấp thiết của luận án<br /> Lý thuyết tập thô do Pawlak đề xuất vào những năm đầu thập niên tám<br /> 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<br /> 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<br /> chắn. Trong các bài toán thực tế, các bảng quyết định thường thiếu giá trị<br /> trên miền giá trị thuộc tính. Trên bảng quyết định không đầy đủ,<br /> Kryszkiewicz đã mở rộng quan hệ tương đương trong lý thuyết tập thô<br /> truyền thống thành quan hệ dung sai và đề xuất mô hình tập thô dung sai<br /> nhằm trích lọc luật trực tiếp không qua bước xử lý giá trị thiếu. Các<br /> phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ theo<br /> tiếp cận tập thô dung sai trong những năm gần đây là: phương pháp dựa<br /> trên miền dương, phương pháp sử dụng hàm quyết định suy rộng, phương<br /> pháp sử dụng lượng thông tin, phương pháp sử dụng metric, phương pháp<br /> sử dụng hàm phân bố (distribution reduct), phương pháp sử dụng hàm ấn<br /> định (assignment reduct), phương pháp sử dụng ma trận phân biệt, phương<br /> pháp sử dụng ma trận dung sai. Trên cơ sở tổng kết các nghiên cứu liên<br /> quan đến các phương pháp rút gọn thuộc tính luận án đặt ra các vấn đề cần<br /> nghiên cứu như sau:<br />  Có thể nói rằng tập rút gọn chính là kết quả của một phương pháp rút<br /> gọn thuộc tính. Trong bảng quyết định nhất quán, các công bố đã chỉ ra<br /> tập rút gọn của phương pháp dựa trên miền dương, tập rút gọn của phương<br /> pháp sử dụng hàm quyết định suy rộng, tập rút gọn sử dụng hàm phân bố,<br /> phương pháp sử dụng hàm ấn định, là có định nghĩa độ đo tương đương<br /> nhau. Tuy nhiên trên bảng quyết định không nhất quán, các tập rút gọn<br /> của các phương pháp là khác nhau và theo tài liệu hiện có mà tác giả biết<br /> thì chưa có nghiên cứu liên quan đến việc so sánh các tập rút gọn làm cơ<br /> sở để so sánh, đánh giá các phương pháp rút gọn thuộc tính.<br />  Việc so sánh, đánh giá các phương pháp rút gọn thuộc tính thường<br /> dựa trên hai tiêu chuẩn: độ phức tạp thời gian của thuật toán heuristic tìm<br /> tập rút gọn và khả năng phân lớp của tập rút gọn. Từ việc tổng kết các<br /> phương pháp rút gọn thuộc tính, tác giả thấy rằng nếu cùng sử dụng một<br /> đơn vị tính toán cơ sở trong tập thô dung sai (lực lượng các lớp dung sai)<br /> thì độ phức tạp thời gian các thuật toán heuristic của các phương pháp là<br /> gần như nhau (độ phức tạp thời gian đa thức). Do đó, việc so sánh, đánh<br /> giá các phương pháp đều sử dụng tiêu chuẩn khả năng phân lớp (độ hỗ trợ<br /> của tập luật) của tập rút gọn. Về mặt định tính, tập rút gọn bảo toàn khả<br /> năng phân lớp của bảng quyết định. Về mặt định lượng, tập rút gọn bảo<br /> <br /> 2<br /> <br /> toàn độ chắc chắn của tập luật quyết định. Tập rút gọn của phương pháp<br /> nào có độ hỗ trợ của tập luật cao (luật quyết định phủ nhiều đối tượng) thì<br /> có khả năng phân lớp cao. Do đó, khả năng phân lớp được tính bằng độ hỗ<br /> trợ của tập luật. Các tác giả đã đưa ra độ chắc chắn, độ nhất quán và độ hỗ<br /> trợ của tập luật quyết định trên bảng quyết định không đầy đủ. Tuy nhiên,<br /> các tác giả chưa nghiên cứu sự thay đổi của các độ đo này trên các tập rút<br /> gọn của các phương pháp rút gọn thuộc tính, do đó các độ đo này không<br /> đánh giá được khả năng phân lớp của tập rút gọn và đòi hỏi phải có độ<br /> chắc chắn, độ hỗ trợ mới để đánh giá khả năng phân lớp của tập rút gọn,<br /> làm cơ sở để so sánh, đánh giá các phương pháp rút gọn thuộc tính.<br />  Hướng nghiên cứu rút gọn thuộc tính đã đạt được một số kết quả nhất<br /> định. Tuy nhiên, việc nghiên cứu và tìm kiếm các phương pháp mới vẫn<br /> đòi hỏi nhiều nỗ lực nghiên cứu nhằm phong phú thêm các phương pháp<br /> rút gọn thuộc tính. Trên cơ sở đó, lựa chọn các phương pháp phù hợp để<br /> giải quyết các bài toán trong thực tiễn.<br /> 2. Mục tiêu nghiên cứu của luận án<br /> 1) Trong bảng quyết định nhất quán, các công bố đã chỉ ra tập rút<br /> gọn của phương pháp trên là tương đương nhau. Tuy nhiên trên bảng<br /> quyết định không nhất quán, các tập rút gọn của các phương pháp là khác<br /> nhau và theo tài liệu hiện có mà tác giả biết thì chưa có nghiên cứu liên<br /> quan đến việc so sánh các tập rút gọn để so sánh, đánh giá các phương<br /> pháp rút gọn.<br /> 2) Việc so sánh, đánh giá các phương pháp rút gọn thuộc tính<br /> thường dựa trên hai tiêu chuẩn: độ phức tạp thời gian của thuật toán<br /> heuristic tìm tập rút gọn và khả năng phân lớp của tập rút gọn. Tác giả<br /> thấy rằng nếu cùng sử dụng một đơn vị tính toán cơ sở trong tập thô dung<br /> sai thì độ phức tạp thời gian các thuật toán heuristic của các phương pháp<br /> là như nhau (độ phức tạp thời gian đa thức). Do đó, việc so sánh, đánh giá<br /> các phương pháp đều sử dụng tiêu chuẩn khả năng phân lớp của tập rút<br /> gọn(độ hỗ trợ của tập luật). Về mặt định tính, tập rút gọn bảo toàn khả<br /> năng phân lớp của bảng quyết định. Về mặt định lượng, tập rút gọn bảo<br /> toàn độ chắc chắn của tập luật quyết định. Tập rút gọn của phương pháp<br /> nào có độ hỗ trợ của tập luật cao thì có khả năng phân lớp cao. Do đó, khả<br /> năng phân lớp được tính bằng độ hỗ trợ của tập luật. Trong các nghiên cứu<br /> trước, các tác giả đã đưa ra độ chắc chắn, độ nhất quán và độ hỗ trợ của<br /> tập luật quyết định trên bảng quyết định không đầy đủ. Tuy nhiên, các tác<br /> giả chưa nghiên cứu sự thay đổi của các độ đo này trên các tập rút gọn của<br /> các phương pháp rút gọn thuộc tính, do đó các độ đo này không đánh giá<br /> <br /> 3<br /> <br /> được khả năng phân lớp của tập rút gọn và đòi hỏi phải có độ chắc chắn,<br /> độ hỗ trợ mới để đánh giá khả năng phân lớp của tập rút gọn, làm cơ sở để<br /> so sánh, đánh giá các phương pháp rút gọn thuộc tính.<br /> 3) Hướng nghiên cứu rút gọn thuộc tính đã đạt được một số kết quả<br /> nhất định. Tuy nhiên, việc nghiên cứu và tìm kiếm các phương pháp mới<br /> vẫn đòi hỏi nhiều nỗ lực nghiên cứu nhằm phong phú thêm các phương<br /> pháp rút gọn thuộc tính. Trên cơ sở đó, lựa chọn các phương pháp phù hợp<br /> để giải quyết các bài toán trong thực tiễn.<br /> 3. Các nội dung nghiên cứu chính của luận án<br /> Chương 1 trình bày các khái niệm cơ bản về mô hình tập thô dung sai<br /> dựa trên quan hệ dung sai trong hệ thông tin không đầy đủ<br /> Chương 2 trình bày hai kết quả chính. Thứ nhất là kết quả phân nhóm<br /> các phương pháp rút gọn thuộc tính dựa vào kết quả nghiên cứu mối liên hệ<br /> giữa các tập rút gọn. Thứ hai là đề xuất các độ đo mới đánh giá hiệu năng<br /> tập luật quyết định và nghiên cứu sự thay đổi giá trị các độ đo này trên các<br /> tập rút gọn nhằm so sánh, đánh giá các nhóm phương pháp rút gọn thuộc<br /> tính trên tiêu chuẩn khả năng phân lớp của tập rút gọn (độ hỗ trợ).<br /> Chương 3 trình bày ba kết quả chính. Thứ nhất là chọn tập tối tượng<br /> đại diện cho bài toán rút gọn thuộc tính nhằm giảm thiểu số đối tượng (dữ<br /> liệu), Thứ hai là đề xuất phương pháp mới rút gọn thuộc tính sử dụng hàm<br /> quan hệ và so sánh, thử nghiệm phương pháp với các phương pháp đã có<br /> trên các bộ số liệu UCI. Thứ ba là đề xuất phương pháp mới rút gọn thuộc<br /> tính sử dụng lượng thông tin mở rộng và so sánh, thử nghiệm phương pháp<br /> với các phương pháp đã có trên các bộ số liệu UCI.<br /> Chương 1. CÁC KHÁI NIỆM CƠ BẢN<br /> Chương này trình bày một số khái niệm cơ bản trong mô hình tập thô<br /> mở rộng dựa trên quan hệ dung sai, trên các hệ thông tin không đầy đủ.<br /> 1.1.<br /> <br /> Hệ thông tin không đầy đủ<br /> <br /> Hệ thông tin là một cặp IS  U , A trong đó U là tập hữu hạn, khác rỗng<br /> các đối tượng; A là tập hữu hạn, khác rỗng các thuộc tính. Mỗi thuộc tính<br /> a  A xác định một ánh xạ: a : U  Va với Va là tập giá trị của thuộc tính<br /> a A.<br /> Với hệ thông tin IS  U , A , nếu tồn tại u U và a  A sao cho a  u  chứa<br /> giá trị thiếu (missing value) thì IS được gọi là hệ thông tin không đầy đủ,<br /> <br />