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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:129

Thêm vào BST

Báo xấu

29
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài nghiên cứu nhằm 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 LUẬN ÁN TIẾN SĨ MÁY TÍNH Hà Nội – Năm 2020
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. PGS. TS Trịnh Đình Thắng Hà Nội – Năm 2020
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
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
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.1 Định nghĩa khai phá dữ liệu 9 1.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.2.1 Hệ thông tin 10 1.2.2 Quan hệ không phân biệt được 11 1.2.3 Bảng quyết định 13 1.2.5 Luật quyết định 14 1.3 Mô hình dữ liệu dạng khối 16 1.3.1 Khối, lược đồ khối 16 1.3.2 Lát cắt 18 1.3.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.1 Khối thông tin 22 2.1.2 Quan hệ không biệt được 25 2.1.3 Khối quyết định 26 2.1.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.3.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.3.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.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.3.4 Thuật toán khai phá luật quyết định trên khối có giá trị thuộc tính
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.5.1 Minh họa bài toán sinh luật quyết định trên khối 62 2.5.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.2.1 Bổ sung đối tượng x vào khối quyết định 74 3.2.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.10 Thực nghiệm 103 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
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
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
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
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 ….[6], [7], [8], [9], [10], [11]. 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... [12], [13], [14], [15], [16], [17], [18], [19]. 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
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.[20] Giả sử sau khi khai phá ta có luật C3 → D3 trên bảng quyết định thì luật này có ý nghĩa như sau: tất cả nhóm bệnh nhân có các triệu chứng là sốt độ 3, ho độ 2, sổ mũi độ 1 thì kết luận nhóm bệnh nhân này sốt virut ở mức 3. Có nghĩa là luật tìm được ở đây chỉ cho ta thấy được triệu chứng và kết luận bệnh tại một thời điểm. Trên thực tế, việc điều trị bệnh là một quá trình cần thời gian theo dõi dài ngày từ ngày đầu nhập viện, đến ngày ra viện. Mặt khác, mỗi khi mức độ sốt thay đổi thì người quản lí cập nhật mức sốt mới cho bệnh nhân đó, như vậy mức sốt cũ mất đi mà thay bằng mức sốt mới. Tình trạng tương tự với các thuộc tính: ho và sổ mũi của bệnh nhân. Do đó, với bảng trên người quản lí muốn theo dõi được quá trình diễn biến của các triệu chứng bệnh hoặc việc tìm ra trong số ngày bệnh nhân nằm viện thì ngày nào sốt cao nhất, ngày nào mức độ ho giảm mạnh nhất, … là một công việc khó khăn. Tuy nhiên, trong mô hình dữ liệu dạng khối thì việc này lại trở nên đơn giản hơn. Giả sử xây dựng Khối bệnh nhân gồm các thuộc tính chỉ số điều kiện là: Sốt (A1), Ho (A2), Sổ mũi (A3) và thuộc tính chỉ số quyết định là phác đồ điều trị: PĐĐT (A4) và Sốt VR (A5), trục id = {x, y, z, t} tương ứng với số ngày theo dõi nằm viện.
3 Hình 1.1: Minh họa Khối Bệnh nhân Với dữ liệu được theo dõi trên Khối Bệnh nhân: khi một bệnh nhân có sự thay đổi về các triệu chứng bệnh, ta bổ sung ngày đó vào trục thời gian và khối sinh một lát cắt mới, ứng với ngày vừa bổ sung để người quản lí cập nhật thông tin (trục thời gian có thể tính theo ngày, giờ, … tùy theo yêu cầu chẩn đoán). Đồng thời, giả sử sau khi khai phá trên Khối tìm được luật có dạng: Ci → Dj với Ci là các lớp tương đương điều kiện trên khối, Dj là các lớp tương đương quyết định trên khối. Ví dụ cụ thể tìm được luật là C3 → D4 trên khối, luật này sẽ có ý nghĩa như sau: tất cả các nhóm bệnh nhân có tập các triệu trứng qua 4 ngày (sốt ngày 1 độ 3, ho ngày 1 độ 2, sổ mũi ngày 1 độ 3, sốt ngày 2 độ 3, ho ngày 2 độ 1, …., sốt ngày 4 độ 0, ho ngày 4 độ 1, sổ mũi ngày 4 độ 0) sử dụng phác đồ điều trị 1 thì cho kết quả bệnh thuyên giảm dần từ ngày thứ nhất đến ngày thứ 4 (sốt vi rút ngày 1 độ 3, ngày 2 độ 2, ngày 1 độ 1, ngày 4 độ 0). Như vậy luật tìm được trên khối cho ta thấy được quá trình đáp ứng của bệnh với phác đồ điều trị nào là phù hợp (thông qua tiến trình thay đổi của triệu chứng bệnh) Với những dạng bài toán như trên, không chỉ xảy ra trong lĩnh vực y tế, mà cả trong giáo dục, quản trị kinh doanh, …. Do đó, việc nghiên cứu bài toán tìm luật quyết định trên khối để hỗ trợ cho các nhà quản lí là điều cần thiết.
4 2. Tổng quan tình hình nghiên cứu liên quan đến luận án a) Các nghiên cứu trên thế giới Các nghiên cứu về bài toán khai phá luật trên các mô hình quan hệ, mô hình mở rộng của mô hình quan hệ cũng đã được nhiều nhóm tác giả nghiên cứu và đưa ra trong các năm vừa qua. Ngoài ra, việc nghiên cứu về bài toán khai phá luật trong các trường hợp giá trị dữ liệu thay đổi hoặc tập đối tượng thay đổi cũng được quan tâm. Năm 1995, nhóm tác giả Shan và Ziarko đã đưa ra một phương pháp để tìm tất cả các luật quyết định chắc chắn dựa trên học gia tăng. Tuy nhiên, thuật toán có một hạn chế là chưa xem xét đến việc tìm các luật trong bảng quyết định không nhất quán [21]. Mục tiêu để giải quyết vấn đề trên, năm 1998, tác giả Bian [22] đã đề xuất thuật toán cải tiến trên cơ sở thuật toán của Shan và Ziarko, thuật toán sử dụng ma trận quyết định mở rộng để giải quyết vấn đề dữ liệu không nhất quán. Tuy vậy, cả hai thuật toán trên vẫn tồn tại một hạn chế đó là các thuật toán không đưa ra được các luật quyết định không chắc chắn và các độ đo của luật như độ chính xác, độ phủ không được cập nhật đồng thời. Năm 2002, nhóm tác giả Tong và An [23] đã sử dụng thuật toán mới dựa vào ma trận quyết định để học gia tăng các luật quyết định trên cơ sở đưa ra bảy trường hợp có thể xảy ra khi một đối tượng mới được bổ sung. Tuy nhiên, trường hợp loại bỏ đối tượng ra khỏi bảng dữ liệu vẫn chưa được nhóm tác giả đề cập đến. Năm 2009, tác giả Liu [24] đã đề xuất mô hình và thuật toán để phát hiện ra các luật quyết định khi bổ sung và loại bỏ đối tượng ra khỏi bảng dữ liệu dựa trên việc tính toán gia tăng ma trận độ chính xác và ma trận độ phủ làm cơ sở để sinh các luật quyết định. Thuật toán của Liu phải sử dụng nhiều không gian bộ nhớ và thời gian tính toán do phải lưu và cập nhật lại nhiều lần đối với cả ma trận độ chính xác và ma trận độ phủ. Năm 2010, tác giả Chen [25] đã đề nghị một thuật toán gia tăng để cập nhật các xấp xỉ của một khái niệm (một lớp tương đương quyết định) khi làm mịn các giá trị của một thuộc tính điều kiện. Tuy nhiên, vấn đề làm thế nào để sinh các luật quyết định có ý nghĩa khi các giá trị hiện có của một thuộc tính thay đổi cũng chưa được đề cập.
5 Các nghiên cứu trên chủ yếu tập trung khai phá dữ liệu trên mô hình quan hệ. Trên thế giới cũng đã có một số nghiên cứu về khai phá dữ liệu trên các mô hình dữ liệu đa chiều. [26], [27], [28], [29], [30], [31], [32], [33], [34], [35], [36], [37], Năm 1997, Kamber cùng các đồng nghiệp [38] là nhóm đầu tiên đưa ra các vấn đề khai thác luật kết hợp từ dữ liệu đa chiều. Các luật kết hợp đa chiều được khai thác từ các mức đơn chiều. Quá trình khai thác này sẽ xem xét trên khối dữ liệu (data cube), độ hỗ trợ và độ tin cậy được tính dựa theo tham số Count. Năm 1998, Zhu đưa ra vấn đề khai phá luật kết hợp từ khối dữ liệu theo ba nhóm: liên chiều (inter-dimensional), nội chiều (intra- dimensional), và luật kết hợp lai. Luật kết hợp intra - dimensional bao gồm các vị từ lặp lại từ một chiều đơn, trong khi các luật kết hợp inter-dimensional được khai thác từ nhiều chiều và không lặp lại các vị từ trong mỗi chiều [39]. Năm 2000, Chen cùng các cộng sự đưa ra nghiên cứu về khai thác luật kết hợp nội chiều (intra - dimensional) bằng cách thêm các đặc trưng từ các chiều khác ở nhiều mức [40]. Tuy nhiên, việc sử dụng các luật kết hợp trong phương pháp này chỉ cho phép áp dụng trên các truy vấn dữ liệu của Web mà chưa được ứng dụng trên các lĩnh vực khác. Năm 2003, luật kết hợp mở rộng đã được đề xuất trong [41] bởi Nestorov và Juki'c. Các tác giả đã khai thác các luật kết hợp từ kho dữ liệu bằng cách sử dụng sức mạnh xử lý SQL của chính kho dữ liệu mà không cần sử dụng một công cụ khai thác dữ liệu nào khác. Họ tập trung vào khai thác các luật kết hợp từ cơ sở dữ liệu giao dịch và không đưa ra số bậc của chiều và tính toán các tham số của khối lập phương như độ hỗ trợ và độ tin cậy. Năm 2005, Tjioe và Taniar [42] cũng đề xuất một phương pháp khai phá luật kết hợp trong kho dữ liệu dựa vào việc tổ chức dữ liệu đa chiều. Phương pháp của họ có thể trích xuất các luật kết hợp từ nhiều chiều ở nhiều mức bằng cách tập trung vào việc tổng hợp dữ liệu theo tham số COUNT theo bốn thuật toán: VAvg, HAvg, WMAvg, và ModusFilter. Năm 2006, trong [43], các tác giả Riadh Ben và Sabine Loudcher đã nghiên cứu việc khai thác luật kết hợp liên chiều (inter-dimensional) từ khối lập phương. Các tác giả đã đưa ra một tập các quy tắc cho phép tính toán độ hỗ trợ và độ tin cậy của luật kết hợp dựa trên bất kì tham số nào của khối lập phương chứ không chỉ dựa trên
6 tham số Count truyền thống. Các tác giả còn đưa ra hai tiêu chí đánh giá luật là Lift và Loevinger. Các tiêu chí này được đánh giá là thể hiện được mối liên quan của các luật một cách chính xác hơn so với các tham số độ tin cậy và độ hỗ trợ. Năm 2015, các tác giả Volker, Wolfram và Mathias đã nghiên cứu việc tích hợp khai phá dữ liệu trên mô hình dữ liệu đa chiều bằng cách “khoan” sâu từng chiều dữ liệu để tìm ra các tri thức có ích. Phương pháp này có một số hạn chế như việc chưa xây dựng được mô hình lí thuyết cho việc khai phá trên dữ liệu đa chiều, và việc tìm tri thức theo từng chiều thì tính tổng quát của luật tìm được chưa được xác định [44]. Năm 2017, nhóm tác giả Omar và Mohamed đã đề xuất một mẫu thử đa tiêu chí MCA tích hợp trên OLAP để giải quyết vấn đa tiêu chí của dữ liệu đa chiều. Tuy nhiên, phương pháp này chỉ dừng lại ở giải quyết tính đa chiều của dữ liệu mà chưa đưa ra được phương pháp tìm luật [45]. Năm 2018, các tác giả Viktor, Nataliia và Sergiy đã đưa ra nghiên cứu về việc khai phá dữ liệu sự kiện mạng trên khối không gian – thời gian (data cube). Việc sử dụng phương pháp này cho phép thực hiện việc phân tích thống kê và phát hiện các cụm thời gian có ý nghĩa thống kê trong dữ liệu [46]. Năm 2019, tác giả Hanen Brahmi đã đưa ra một hướng tiếp cận phương pháp khai phá dữ liệu trong khối datacube bẳng cách phân cấp thứ nguyên đặc trưng của khối này theo các hướng rồi tổng hợp các luật thu được. Cũng giống như phương pháp của các tác giả Volker, Wolfram và Mathias đã đề cập ở trên, phương pháp này cũng chưa xác định được mô hình lí thuyết cho việc khai phá trên dữ liệu đa chiều và tính tổng quan của luật tìm được [47]. b) Các nghiên cứu ở Việt Nam Tại Việt Nam, đã có nhiều tác giả, nhóm tác giả quan tâm, nghiên cứu, đề xuất các giải pháp khác nhau nhằm giải quyết bài toán khai phá tri thức trên bảng dữ liệu của mô hình quan hệ và mô hình mở rộng của mô hình quan hệ. Năm 2008, tác giả Nguyễn Hữu Trọng [48] đã đề xuất một thuật toán để khai phá các luật kết hợp khi bảng dữ liệu được gia tăng theo chiều dọc và sử dụng kỹ thuật cây quyết định để sinh các luật khi bảng được gia tăng theo chiều ngang.
7 Năm 2012, tác giả Nguyễn Long Giang [49] đã đề xuất một thuật toán rút gọn thuộc tính trong hệ thông tin không đầy đủ và bảng quyết định không đầy đủ sử dụng metric. Cũng trong năm này, tác giả Nguyễn Quang Khanh [50] đề cập đến vấn đề khai phá luật quyết định trong bảng dữ liệu có tập các giá trị thuộc tính thay đổi. Năm 2017, tác giả Cao Chính Nghĩa [51] đã đề xuất các phương pháp rút gọn thuộc tính trực tiếp trên bảng quyết định miền giá trị thực và sinh luật quyết định mờ. 3. Mục tiêu, đối tượng và phương pháp nghiên cứu Trong thực tế với khối dữ liệu có tập đối tượng lớn, việc tìm ra mối quan hệ giữa toàn bộ tập đối tượng là khá khó khăn. Chính vì vậy, mục đích của bài toán là tìm ra mối quan hệ (các luật quyết định) từ các nhóm đối tượng nhỏ hơn, cụ thể là các lớp đối tượng chia theo quan hệ tương đương. Với mục đích như trên, mục tiêu của luận án tập trung giải quyết ba bài toán là: - 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. Đối tượng nghiên cứu chính của luận án là luật quyết định. Phạm vi nghiên cứu là mô hình khối. Phương pháp nghiên cứu của luận án: nghiên cứu lý thuyết và nghiên cứu thực nghiệm. 4. Giả thuyết nghiên cứu Với những lí do và mục tiêu đã đề cập ở trên, luận án mong muốn đạt được các giả thuyết nghiên cứu như sau: - Đề xuất các khái niệm, chứng minh các mệnh đề, tính chất để xây dựng được mô hình khai phá luật trên khối và lắt cắt của khối. - Đề xuất một số thuật toán tính ma trận độ hỗ trợ, từ đó tính ma trận độ chính xác, ma trận độ phủ và suy ra các luật quyết định có ý nghĩa trên khối. - Xây dựng được thuật toán tìm luật quyết định trên khối trong trường hợp giá trị thuộc tính chỉ số thay đổi, tính toán độ phức tạp và cài đặt thực nghiệm
8 - Xây dựng được mô hình bổ sung và loại bỏ các phần tử trên khối quyết định, đề xuất hai phương pháp tìm luật trên khối khi tập đối tượng thay đổi là phương pháp tính gia tăng ma trận độ chính xác, độ phủ và phương pháp tính gia tăng ma trận độ hỗ trợ. Tính toán được độ phức tạp của các thuật toán đề xuất và thực nghiệm so sánh hai phương pháp đề xuất. 5. 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. 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 đưa ra thuật toán khai phá luật quyết định trên khối. Đồng thời đề xuất các kết quả nghiên cứu về việc làm thô, làm mịn các giá trị của thuộc tính chỉ sổ điều kiện hoặc quyết định. Từ đó tìm các luật quyết định trên khối và lát cắt và cài đặt thử nghiệm 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; đưa ra hai phương pháp tính gia tăng của các ma trận độ đo Acc, Cov, Supp. Từ đó tìm các luật quyết định trên khối quyết định và lát cắt khi tập đối tượng thay đổi và cài đặt thử nghiệm.
9 CHƯƠNG 1. MỘT SỐ KIẾN THỨC CƠ SỞ Nội dung của chương này trình bày những kiến thức cơ sở về khai phá dữ liệu, khai phá luật quyết định, mô hình dữ liệu dạng khối. Đây là những kiến thức nền tảng cho những nghiên cứu của các chương sau trong luận án. 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,.. [52], [53]. Quá trình khai phá dữ liệu trải qua ba bước [52], [53]: Bước 1: Lọc dữ liệu hay gọi là tiền xử lý. Khi dữ liệu được thu thập từ nhiều nguồn khác nhau nên có thể có những sự sai sót, dư thừa và trùng lặp. Lọc dữ liệu là cắt bỏ những dư thừa để dữ liệu được định dạng thống nhất. Dữ liệu sau khi lọc và chỉnh sửa sẽ nhỏ hơn, xử lý nhanh chóng hơn. Bước 2: Khai phá dữ liệu, là công việc chính, sử dụng các thuật toán khác nhau để khai phá các kiến thức tiềm ẩn trong dữ liệu. Bước 3: Hậu xử lý, là quá trình ước lượng kết quả khai phá theo yêu cầu của người dùng. Nhiều kỹ thuật khai phá dữ liệu được ứng dụng cho một nguồn dữ liệu, các kỹ thuật khác nhau cho các kết quả có thể khác nhau. Các kết quả được ước lượng bởi những tiêu chí đánh giá nào đó, nếu cuối cùng kết quả không thỏa mãn yêu cầu, chúng ta phải làm lại với kỹ thuật khác cho đến khi có kết quả mong muốn. 1.1.2. Một số kỹ thuật khai phá dữ liệu Trong khai phá dữ liệu, các bài toán có thể phân thành bốn loại chính [52]: - Phân lớp (Classification): Là bài toán thông dụng nhất trong khai phá dữ liệu. Với một tập các dữ liệu huấn luyện cho trước và sự huấn luyện của con người, các giải thuật phân loại sẽ học ra bộ phân loại (classifier) dùng để phân các dữ liệu mới vào một trong những lớp (còn gọi là loại) đã được xác định trước. Nhận dạng cũng là một bài toán thuộc kiểu phân lớp. - Dự đoán (Prediction): Với mô hình học tương tự như bài toán phân lớp, lớp bài toán dự đoán sẽ học ra các bộ dự đoán. Khi có dữ liệu mới đến, bộ dự đoán sẽ dựa trên thông tin đang có để đưa ra một giá trị số học cho hàm cần dự đoán. Bài toán
10 tiêu biểu trong nhóm này là dự đoán giá sản phẩm để lập kế hoạch trong kinh doanh. - Luật kết hợp (Association Rule): Các giải thuật tìm luật kết hợp tìm kiếm các mối liên kết giữa các phần tử dữ liệu, ví dụ như nhóm các món hàng thường được mua kèm với nhau trong siêu thị. - Phân cụm (Clustering): Các kỹ thuật phân cụm sẽ nhóm các đối tượng dữ liệu có tính chất giống nhau vào cùng một nhóm. Có nhiều cách tiếp cận với những mục tiêu khác nhau trong phân cụm. Các tài liệu [44, 49] giới thiệu khá đầy đủ và chi tiết về các cách tiếp cận trong phân cụm. Các kỹ thuật trong bài toán này thường được vận dụng trong vấn đề phân hoạch dữ liệu tiếp thị hay khảo sát sơ bộ các dữ liệu. 1.2. Khai phá luật quyết định 1.2.1. Hệ thông tin Một cách phi hình thức, một hệ thông tin là một tập dữ liệu được cho dưới dạng bảng, trong đó mỗi hàng biểu diễn thông tin về một đối tượng, mỗi cột biểu diễn thông tin về một thuộc tính của các đối tượng trong tập dữ liệu. Một cách hình thức, hệ thông tin được định nghĩa như sau: Định nghĩa 1.1 [54], [55]. (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 =  Va a A 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. Với mỗi u  U, a  A, dùng ký hiệu u(a) thay cho f(u,a) để biểu thị giá trị của đối tượng u tại thuộc tính a; rõ ràng là u(a)  Va với mọi u  U. Với một tập con các thuộc tính B = {b1, b2, …, bk}  A, ký hiệu bộ các giá trị {u(bi)|biB} là u(B), với hai đối tượng u, vU, viết u(B) = v(B) nếu u(bi) = v(bi) i = 1..k.. Nếu uU, aA mà giá trị hàm thông tin f(u,a) không xác định thì hệ thông tin S được gọi là hệ thông tin không đầy đủ (Uncompleted Information System), ngược lại S được gọi là hệ thông tin đầy đủ (Completed Information System) [56].
11 Ví dụ 1.1 Cho hệ thông tin trong Bảng 1.2 khi đó ta có: Tập các đối tượng U = {u1, u2, …, u7}. Tập các thuộc tính A = {Năm sinh, Điểm, Kết quả}. Tập giá trị của thuộc tính độ tuổi, số buổi và kết quả là: V Năm sinh = {1989, 1998, 2008} V Điểm = {0, 50, 75} V Kết quả = {Đỗ, Trượt}. Hàm f được biểu thị bằng giá trị tương ứng tại điểm giao của mỗi hàng - đối tượng với mỗi cột - thuộc tính, ví dụ f(u1, Năm sinh) = 1998, f(u2, Điểm) = 0. U Năm sinh Điểm Kết quả u1 1998 50 Đỗ u2 1989 0 Trượt u3 2008 50 Đỗ u4 1989 0 Trượt u5 2008 0 Trượt u6 1998 75 Đỗ u7 1998 0 Trượt Bảng 1.2. Một ví dụ về hệ thông tin 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: