Luận án khai phá luật quyết định trên mô hình dữ liệu dạng khối - Nghiên cứu lý thuyết và ứng dụng

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 LUẬN ÁN TIẾN SĨ MÁY TÍNH Hà Nội – Năm 2020 luan an 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 LUẬN ÁN TIẾN SĨ MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. TS Trịnh Đình Thắng Hà Nội – Năm 2020 luan an i LỜI CẢM ƠN Lời đầu tiên, cho phép tác giả xin bày tỏ lòng biết ơn sâu sắc và chân thành tới PGS. TS Trịnh Đình Thắng, người thầy đã tận tình hướng dẫn, chỉ bảo cho tác giả trong suốt quá trình học tập, nghiên cứu và hoàn thành luận án này. Tác giả xin chân thành cảm ơn tới tập thể các thầy cô giáo, các nhà khoa học thuộc: Viện Công nghệ Thông tin – viện Hàn lâm Khoa học và Công nghệ Việt Nam, Khoa Công nghệ Thông tin – Học viện Khoa học và Công nghệ, viện Công nghệ Thông tin – trường Đại học Sư phạm Hà Nội 2 đã giúp đỡ về chuyên môn và tạo điều kiện thuận lợi cho tác giả trong suốt thời gian học tập và nghiên cứu.

Cuối cùng, tác giả xin gửi tới gia đình, người thân, bạn bè lời cảm ơn chân thành nhất vì đã ủng hộ, đồng hành, là chỗ dựa vững chắc và là động lực giúp tác giả hoàn thành luận án này. Tác giả luận án Đỗ Thị Lan Anh luan an ii LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự hướng dẫn khoa học của PGS. TS Trịnh Đình Thắng. Các kết quả được viết chung với các đồng tác giả đã được sự chấp thuận của các tác giả trước khi đưa vào luận án.

Các kết quả nêu trong luận án là trung thực và chưa từng được công bố trong bất kỳ công trình nào khác. Tác giả luận án Đỗ Thị Lan Anh luan an iii MỤC LỤC Trang Danh mục các ký hiệu, các chữ viết tắt v Danh mục các bảng, hình vẽ vi MỞ ĐẦU 1 CHƯƠNG 1: MỘT SỐ KIẾN THỨC CƠ SỞ 9 1.1 Khai phá dữ liệu 9 1.1 Định nghĩa khai phá dữ liệu 9 1.2 Một số kỹ thuật khai phá dữ liệu 9 1.2 Khai phá luật quyết định 10 1.1 Hệ thông tin 10 1.2 Quan hệ không phân biệt được 11 1.3 Bảng quyết định 13 1.5 Luật quyết định 14 1.3 Mô hình dữ liệu dạng khối 16 1.1 Khối, lược đồ khối 16 1.3 Đại số quan hệ trên khối 18 1.4 Kết luận chương 1 21 CHƯƠNG 2: KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN KHỐI DỮ LIỆU CÓ GIÁ TRỊ THUỘC TÍNH THAY ĐỔI 22 2.1 Một số khái niệm xây dựng trên khối 22 2.1 Khối thông tin 22 2.2 Quan hệ không biệt được 25 2.3 Khối quyết định 26 2.4 Luật quyết định trên khối và lát cắt 28 2.2 Thuật toán khai phá luật quyết định trên khối và trên lát cắt (MDLB) 31 2.3 Khai phá luật quyết định trên khối có giá trị thuộc tính thay đổi 34 2.1 Làm mịn, thô các lớp tương đương điều kiện trên khối và trên lát cắt 40 2.2 Làm mịn, thô các lớp tương đương quyết định trên khối và trên lát cắt 44 2.3 Làm mịn cảm sinh hoàn toàn thuộc tính chỉ số trên lát cắt 48 2.4 Thuật toán khai phá luật quyết định trên khối có giá trị thuộc tính luan an iv thay đổi (MDLB_VAC) 50 2.4 Độ phức tạp của các thuật toán tính ma trận Sup trên khối và lát cắt 60 2.5 Ví dụ minh họa 62 2.1 Minh họa bài toán sinh luật quyết định trên khối 62 2.2 Minh họa bài toán sinh luật quyết định trên khối khi làm mịn, thô giá trị thuộc tính chỉ số 63 2.6 Kết luận 66 CHƯƠNG 3: KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN KHỐI CÓ TẬP ĐỐI TƯỢNG THAY ĐỔI 67 3.1 Mô hình bổ sung, loại bỏ các đối tượng trên khối và lát cắt 67 3.2 Tính toán gia tăng Acc và Cov khi bổ sung, loại bỏ đối tượng trên khối 74 3.1 Bổ sung đối tượng x vào khối quyết định 74 3.2 Loại bỏ phần tử x ra khỏi khối quyết định 77 3.3 Thuật toán sinh luật quyết định bằng phương pháp tính gia tăng ma trận Acc và Cov sau khi bổ sung, loại bỏ các phần tử (MDLB_OSC1) 78 3.4 Độ phức tạp của các thuật toán MDLB_OSC1 83 3.5 Tính toán gia tăng Sup khi bổ sung, loại bỏ đối tượng trên khối và lát cắt 86 3.6 Thuật toán sinh luật quyết định bằng phương pháp tính gia tăng ma trận Sup sau khi bổ sung và loại bỏ các đối tượng (MDLB_OSC2) 88 3.7 Độ phức tạp của các thuật toán MDLB_OSC2 96 3.8 So sánh hai phương pháp tính gia tăng 97 3.9 Ví dụ minh họa 97 3.11 Kết luận 112 KẾT LUẬN 113 DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ 114 TÀI LIỆU THAM KHẢO 115 luan an v DANH MỤC CÁC KÍ HIỆU, CÁC CHỮ VIẾT TẮT Kí hiệu, chữ viết tắt Diễn giải Acc Accuracy (Độ chính xác) Cov Coverage (Độ phủ) Sup Support (Độ hỗ trợ) IND(P) Quan hệ không phân biệt được id  id’ Tích rời rạc của hai tập chỉ số id và id’ P(r) Phép chiếu của khối r trên lược đồ con P F(r) Phép chọn của khối r theo biểu thức Boole F r  s Phép kết nối hai khối r và s IB = (U, A, V, f) Khối thông tin DB = (U, CD) Khối quyết định U/C Tập các lớp tương đương điều kiện trên khối U/D Tập các lớp tương đương quyết định trên khối U/Cx Tập các lớp tương đương điều kiện trên lát cắt tại điểm x Tập các lớp tương đương quyết định trên lát cắt tại điểm U/Dx x  Ngưỡng độ chính xác tối thiểu  Ngưỡng độ phủ tối thiểu luan an vi DANH MỤC CÁC BẢNG Trang Bảng 1.1 Bảng Bệnh nhân 2 Bảng 1.1 Một ví dụ về hệ thông tin 11 Bảng 1.2 Bảng quyết định về bệnh cúm 14 Bảng 2.1 Bảng biểu diễn khối thông tin Bệnh nhân bị sốt virut tại khoa Nhi A Bệnh viện Bạch Mai cơ sở 2 25 Bảng 3.1 Bảng so sánh hai phương pháp tính gia tăng 98 Bảng 3.2 Các thông tin cơ bản về CSDL thực nghiệm 104 luan an vii DANH MỤC CÁC HÌNH VẼ Hình 1.1 Ví dụ Khối Bệnh nhân 3 Hình 1.2 Ví dụ về khối Khách hàng 19 Hình 1.3 Minh họa lát cắt khối Khách hàng tại điểm x = 3/2019 20 Hình 2.1 Minh họa một khối thông tin bệnh nhân bị sốt virut tại Khoa Nhi A – Bệnh viện Bạch Mai cơ sở 2 24 Hình 2.2 Minh họa khối quyết định Bệnh nhân sốt vi rút 28 Hình 3.1 Menu của chương trình 105 Hình 3.2 Tìm các lớp tương đương điều kiện, quyết định 105 Hình 3.3 Ma trận Sup, Acc, Cov tìm được 106 Hình 3.4 Luật quyết định tìm được trên khối 106 Hình 3.5 Mối quan hệ giữa số lượng luật kết quả và ngưỡng min_acc, min_cov 107 Hình 3.6 Chọn giá trị làm mịn 107 Hình 3.7 Tính các ma trận Sup, Acc, Cov trước và sau khi làm mịn 108 Hình 3.8 Chọn giá trị thuộc tính làm thô 108 Hình 3.9 Tính các ma trận Sup, Acc, Cov trước và sau khi làm thô 109 Hình 3.10 Luật quyết định tìm được sau khi làm thô, mịn giá trị thuộc tính 109 Hình 3.11 Chọn đối tượng bị loại bỏ 110 Hình 3.12 Nhập đối tượng bổ sung vào khối 110 Hình 3.13 Kết quả chương trình tính gia tăng ma trận Acc, Cov và luật quyết định thu được 111 Hình 3.14 Kết quả chương trình tính gia tăng ma trận Sup và luật quyết định thu được 111 Hình 3.15 Thời gian chạy (mili giây) trung bình của hai thuật toán 112 luan an 1 MỞ ĐẦU 1. Lý do chọn đề tài Khai phá dữ liệu vẫn đang là lĩnh vực nhận được rất nhiều sự quan tâm nghiên cứu của các nhà khoa học trên thế giới. Hội nghị quốc tế về khai phá dữ liệu KDD lần thứ 26 được tổ chức tại California, Mỹ vào tháng 8 năm 2020 là một trong những hội nghị lớn và nổi tiếng hàng đầu trong lĩnh vực khai phá dữ liệu và quy tụ hàng trăm nhà khoa học tham gia [1], [2].

Một số các hội nghị về khai phá dữ liệu nổi tiếng được tổ chức thường niên hàng năm trên thế giới được kể đến như: hội nghị KDD, ICDE, IEEE ICDM, CIKM, SIAM SDM, PKDD, PAKDD… Nhóm bài toán thường được nghiên cứu trong khai phá dữ liệu gồm có: Phân lớp, dự đoán, luật kết hợp và phân cụm [3], [4], [5]. Khai phá luật quyết định là một kĩ thuật nằm trong nhóm 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 mô hình cơ sở dữ liệu quan hệ và một số mô hình mở rộng của mô hình dữ liệu quan hệ như mô hình datacube, mô hình nhà kho dữ liệu, mô hình dữ liệu đa chiều …. Năm 1998, các tác giả Nguyễn Xuân Huy, Trịnh Đình Thắng đã đề xuất mô hình dữ liệu dạng khối, một mở rộng của mô hình quan hệ [9].

Mô hình này đã được xây dựng cả về lý thuyết và cài đặt thực nghiệm. Với việc đưa thêm một trục id cho phép theo dõi được sự thay đổi dữ liệu theo quá trình, cụ thể có thể là theo thời gian, giai đoạn, khoảng cách. Kết quả của bài toán khai phá luật trên mô hình quan hệ sẽ cho ta các luật hữu ích nhưng chỉ tại một thời điểm nào đó. Tuy nhiên, trong thực tế với một số vấn đề đặc thù như chuẩn đoán bệnh, theo dõi quá trình mua bán hàng trong siêu thị hay quá trình quản lí cán bộ của một cơ quan,.

Việc tìm ra các mối quan hệ (các luật) của các đối tượng trong cơ sở dữ liệu theo một quá trình sẽ giúp ích cho các chuyên gia đưa ra các quyết định chính xác hơn. Ví dụ: trong bảng quyết định Bệnh nhân dưới đây luan an 2 Sốt Ho Sổ mũi Mức Sốt VR (A1) (A2) (A3) (A4) 1 1 0 1 3 2 1 3 3 2 1 3 3 3 2 3 Bảng 1.1: Bảng Bệnh nhân Bảng này gồm các thuộc tính điều kiện là: Sốt (A1), Ho (A2), Sổ mũi (A3) và thuộc tính quyết định là Mức Sốt VR (A4). Theo định nghĩa luật quyết định trên bảng quyết định sẽ có dạng: Ci → Dj với Ci là các lớp tương đương điều kiện, Dj là các lớp tương đương quyết định.