Tóm tắt luận án Tiến sĩ Máy tính: Khai phá luật quyết định trên mô hình dữ liệu dạng khối

Mục tiêu của luận án tập trung giải quyết ba bài toán: Tìm các luật quyết định trên khối và trên lát cắt; tìm các luật quyết định giữa các nhóm đối tượng trên khối khi có sự thay đổi giá trị thuộc tính, cụ thể là khi làm mịn, hoặc làm thô giá trị thuộc tính; tìm các luật quyết định giữa các nhóm đối tượng trên khối khi bổ sung, loại bỏ phần tử của khối. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Tóm tắt luận án Tiến sĩ Máy tính: Khai phá luật quyết định trên mô hình dữ liệu dạng khối BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Đỗ Thị Lan Anh KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN MÔ HÌNH DỮ LIỆU DẠNG KHỐI Chuyên ngành: Khoa học máy tính Mã số: 9 48 01 01 TÓM TẮT LUẬN ÁN TIẾN SĨ MÁY TÍNH Hà Nội – Năm 2020 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. Người hướng dẫn khoa học: PGS. TS. Trịnh Đình Thắng Phản biện 1: PGS. TS. Nguyễn Hữu Quỳnh Phản biện 2: PGS. TS. Đỗ Năng Toàn Phản biện 3: PGS. TS. Phạm Văn Cường Luận án sẽ được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Học viện, họp 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 vào hồi … giờ .., ngày … tháng … năm 201…. Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam 1 MỞ ĐẦU 1. Tính cấp thiết của luận án Khai phá các luật quyết định là quá trình xác định những luật quyết định trên bảng quyết định cho trước, phục vụ cho bài toán phân lớp đối tượng. Đây là một trong những kĩ thuật khai phá dữ liệu khá phổ biến và đã được nhiều chuyên gia trong và ngoài nước nghiên cứu trên cả mô hình quan hệ và các mô hình mở rộng của mô hình quan hệ. Các nghiên cứu trên thế giới và trong nước ta đều nhằm mục đích tìm ra tri thức có ý nghĩa, cụ thể là các luật trên các mô hình dữ liệu khác nhau với các hướng nghiên cứu khác nhau. Một hướng tiếp cận với mô hình dữ liệu dạng khối của nhóm tác giả với mục đích theo dõi được các luật diễn ra trong một quá trình thay đổi theo thời gian, giai đoạn… chính là mong muốn đóng góp được của luận án. 2. Mục tiêu nghiên cứu của luận án Mục tiêu của luận án tập trung giải quyết ba bài toán: - Tìm các luật quyết định trên khối và trên lát cắt. - Tìm các luật quyết định giữa các nhóm đối tượng trên khối khi có sự thay đổi giá trị thuộc tính, cụ thể là khi làm mịn, hoặc làm thô giá trị thuộc tính. - Tìm các luật quyết định giữa các nhóm đối tượng trên khối khi bổ sung, loại bỏ phần tử của khối. 3. Bố cục của luận án Luận án gồm phần mở đầu, 3 chương tiếp theo và cuối cùng là phần kết luận. 2 Chương đầu trình bày một số khái niệm cơ sở về mô hình dữ liệu dạng khối, khai phá dữ liệu, khai phá luật quyết định và quan hệ tương đương. Chương 2 trình bày hai kết quả nghiên cứu: thứ nhất là đề xuất thuật toán MDLB để tìm các luật quyết định trên khối và lát cắt của khối. Thứ hai là đề xuất thuật toán MDLB_VAC nhằm tìm ra các luật quyết định trên khối trong trường hợp giá trị thuộc tính thay đổi. Thêm vào đó, đưa ra các nghiên cứu lí thuyết về khai phá trên khối, tính toán độ phức tạp và cài đặt thử nghiệm các thuật toán đề xuất. Chương 3 xây dựng mô hình tăng hoặc giảm tập đối tượng của khối quyết định; đề xuất hai thuật toán gia tăng MDLB_OSC1 và MDLB_OSC2 để tìm các luật quyết định trên khối quyết định khi tập đối tượng thay đổi và cài đặt thử nghiệm. CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ 1.1. Khai phá dữ liệu 1.1.1. Định nghĩa khai phá dữ liệu Khai phá dữ liệu là khâu chủ yếu trong quá trình phát hiện ra tri thức trong cơ sở dữ liệu. Quá trình này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo, ra quyết định trong kinh doanh, quản lý, các hoạt động sản xuất,… 1.1.2. Một số kỹ thuật khai phá dữ liệu - Phân lớp (Classification). - Dự đoán (Prediction). - Luật kết hợp (Association Rule). - Phân cụm (Clustering). 1.2. Khai phá luật quyết định 3 1.2.1. Hệ thông tin Định nghĩa 1.1 (Hệ thông tin) Hệ thông tin là một bộ bốn S = (U,A,V,f) trong đó U là tập đối tượng là một tập hữu hạn, khác rỗng các đối tượng (U còn được gọi là tập vũ trụ) và A là tập thuộc tính là một tập hữu hạn, khác rỗng các thuộc tính; V là tập giá trị, trong đó ???? = ∪ ???????? với ????∈???? Va là tập giá trị của thuộc tính a  A, f là hàm thông tin f : U x A→V, trong đó a  A, u  U: f(u,a)  Va. 1.2.2. Quan hệ không phân biệt được Cho hệ thông tin S = (U,A,V,f) với mỗi tập con các thuộc tính P  A, tồn tại một quan hệ hai ngôi trên U, ký hiệu là IND(P), được xác định như sau: IND(P) = {(u,v)  U x U|u(a) = v(a), a  P) IND(P) được gọi là quan hệ không phân biệt được (Indiscernibility Relation). 1.2.3. Bảng quyết định Bảng quyết định là một hệ thông tin đặc biệt trong đó tập thuộc tính ???? được chia thành hai tập khác rỗng rời nhau C và D (A= CD, CD = ) tương ứng được gọi là tập thuộc tính điều kiện C và tập thuộc tính quyết định D. Bảng quyết định được ký hiệu là: DS = (U,CD,V,f) hay đơn giản là DS = (U,CD). 1.2.4. Luật quyết định Định nghĩa 1.4 (Luật quyết định) Cho bảng quyết định DS = (U,CD), giả sử U/C = {C1,C2,…,Cm} và U/D = {D1,D2,…,Dn} là các phân hoạch được sinh bởi C, D. Với Ci  U/C, Dj  U/D một luật quyết định được biểu diễn dưới dạng: Ci → Dj , i=1..m, j=1..n. 4 1.3. Mô hình dữ liệu dạng khối 1.3.1. Khối Định nghĩa 1.8 Gọi R = (id;A1,A2,...,An) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn khác rỗng, Ai (i=1..n) là các thuộc tính. Mỗi thuộc tính Ai (i=1..n) có miền giá trị tương ứng là dom(Ai ). Một khối r trên tập R, kí hiệu r(R) gồm một số hữu hạn phần tử mà mỗi phần tử là một họ các ánh xạ từ tập chỉ số id đến các miền trị của các thuộc tính Ai, (i=1..n). Nói một cách khác: t  r(R)  t = {ti: id → dom(Ai)} i =1..n 1.3.2. L ...