Tổng quan luận án

Khai phá dữ liệu là một lĩnh vực nghiên cứu trong khoa học máy tính và công nghệ thông tin, thu hút sự tham gia của các nhà khoa học thông qua các hội thảo chuyên ngành quốc tế như KDD (Hội nghị quốc tế về khai phá dữ liệu lần thứ 26 được tổ chức tại California, Mỹ vào tháng 8 năm 2020), ICDE, IEEE ICDM, CIKM, SIAM SDM, PKDD, PAKDD. Trong bốn nhóm bài toán cơ bản của khai phá dữ liệu bao gồm phân lớp, dự đoán, luật kết hợp và phân cụm, bài toán khai phá luật quyết định thuộc nhóm bài toán phân lớp đối tượng. Các nghiên cứu truyền thống về luật quyết định chủ yếu được thực hiện trên mô hình cơ sở dữ liệu quan hệ hoặc một số mô hình mở rộng như datacube, kho dữ liệu và dữ liệu đa chiều. Tuy nhiên, các kỹ thuật khai phá trên mô hình quan hệ chỉ cho phép tìm ra các tri thức, quy luật tại một thời điểm cố định. Trong thực tế, nhiều lĩnh vực như y tế (chẩn đoán và theo dõi phác đồ điều trị bệnh nhân dài ngày), quản trị bán lẻ (theo dõi diễn biến mua sắm theo chu kỳ tại siêu thị) hay quản lý nhân sự đòi hỏi phải theo dõi dữ liệu theo một tiến trình thời gian, giai đoạn hoặc khoảng cách.

Mô hình dữ liệu dạng khối (block model) do hai tác giả Nguyễn Xuân Huy và Trịnh Đình Thắng đề xuất năm 1998 đã mở rộng mô hình quan hệ bằng cách bổ sung trục chỉ số id, cho phép lưu trữ và quan sát dữ liệu theo quá trình biến đổi. Mặc dù mô hình này đã được xây dựng về mặt lý thuyết đại số và cài đặt thực nghiệm, việc nghiên cứu cơ chế khai phá luật quyết định trực tiếp trên mô hình khối và trên các lát cắt của khối vẫn chưa được giải quyết một cách hoàn chỉnh, đặc biệt trong các bối cảnh dữ liệu có sự biến động. Khoảng trống nghiên cứu được luận án xác định là việc thiếu vắng các mô hình toán học và thuật toán khai phá luật quyết định theo tiến trình trên khối, cũng như các kỹ thuật cập nhật tri thức gia tăng khi giá trị thuộc tính hoặc tập đối tượng thay đổi theo thời gian mà không cần phải thực hiện tính toán lại toàn bộ dữ liệu từ đầu.

Mục tiêu nghiên cứu của luận án tập trung giải quyết ba bài toán:

  1. Tìm các luật quyết định trên khối và trên lát cắt của khối.
  2. 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 (tách một giá trị thành hai giá trị mới) hoặc làm thô (gộp hai giá trị thành một giá trị mới) giá trị thuộc tính.
  3. 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ự biến động của tập đối tượng, cụ thể là khi bổ sung hoặc loại bỏ phần tử của khối.

Luận án đặt ra bốn giả thuyết nghiên cứu cụ thể:

  1. Đề 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.
  2. Đề 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.
  3. 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 tính toán và cài đặt thực nghiệm.
  4. 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 gồm 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 độ 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 này.

Đố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 giới hạn trên mô hình cơ sở dữ liệu dạng khối.

Tổng quan tài liệu và vị trí của luận án

Các công trình nghiên cứu liên quan đến bài toán khai phá luật quyết định và luật kết hợp được tác giả phân tích theo hai nhóm không gian nghiên cứu: các nghiên cứu trên thế giới và các nghiên cứu tại Việt Nam.

Đối với các nghiên cứu trên thế giới:

  • Shan và Ziarko (1995) công bố phương pháp học gia tăng để tìm tất cả các luật quyết định chắc chắn; hạn chế của công trình này là chưa xét đến các bảng quyết định không nhất quán.
  • Bian (1998) cải tiến thuật toán của Shan và Ziarko bằng cách sử dụng ma trận quyết định mở rộng để xử lý dữ liệu không nhất quán; tuy vậy, thuật toán chưa đưa ra được các luật không chắc chắn và không cập nhật đồng thời các độ đo độ chính xác, độ phủ.
  • Tong và An (2002) áp dụng ma trận quyết định để học gia tăng luật quyết định dựa trên việc phân loại 7 trường hợp khi bổ sung một đối tượng mới, nhưng chưa giải quyết trường hợp loại bỏ đối tượng.
  • Liu (2009) xây dựng mô hình và giải thuật phát hiện luật quyết định khi bổ sung và loại bỏ đối tượng 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ủ; nhược điểm của giải pháp này là đòi hỏi không gian bộ nhớ lớn và thời gian tính toán cao do phải cập nhật đồng thời cả hai ma trận qua nhiều lần lặp.
  • Chen (2010) đề xuấ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 khi làm mịn giá trị của thuộc tính điều kiện, song chưa đưa ra phương pháp sinh các luật quyết định có ý nghĩa khi giá trị thuộc tính biến đổi.
  • Về khai phá trên dữ liệu đa chiều và data cube: Kamber và cộng sự (1997) nghiên cứu khai thác luật kết hợp từ dữ liệu đa chiều dựa trên tham số Count; Zhu (1998) phân loại luật kết hợp từ khối dữ liệu thành ba nhóm gồm liên chiều (inter-dimensional), nội chiều (intra-dimensional) và luật lai; Chen và cộng sự (2000) khai thác luật nội chiều trên các truy vấn Web; Nestorov và Juki'c (2003) khai thác luật kết hợp mở rộng từ kho dữ liệu bằng câu lệnh SQL nhưng không đưa ra số bậc của chiều và các tham số khối; Tjioe và Taniar (2005) đề xuất khai phá luật kết hợp theo tham số COUNT với bốn thuật toán VAvg, HAvg, WMAvg và ModusFilter; Riadh Ben và Sabine Loudcher (2006) khai thác luật liên chiều trên khối lập phương dựa trên tiêu chí Lift và Loevinger; Volker, Wolfram và Mathias (2015) khai phá dữ liệu đa chiều bằng kỹ thuật khoan sâu (drill-down) từng chiều nhưng thiếu mô hình lý thuyết tổng quát; Omar và Mohamed (2017) đề xuất mẫu thử đa tiêu chí MCA trên OLAP nhưng dừng lại ở xử lý đa chiều mà chưa tìm luật; Viktor, Nataliia và Sergiy (2018) khai phá sự kiện mạng trên khối không gian - thời gian; Hanen Brahmi (2019) tiếp cận khối datacube bằng phân cấp thứ nguyên đặc trưng nhưng cũng chưa xác định được mô hình lý thuyết hoàn chỉnh.

Đối với các nghiên cứu tại Việt Nam:

  • Nguyễn Xuân Huy và Trịnh Đình Thắng (1998) đề xuất mô hình dữ liệu dạng khối mở rộng từ mô hình quan hệ thông qua trục chỉ số id.
  • Nguyễn Hữu Trọng (2008) đề xuất thuật toán khai phá luật kết hợp khi dữ liệu gia tăng theo chiều dọc và sử dụng cây quyết định khi gia tăng theo chiều ngang.
  • Nguyễn Long Giang (2012) nghiên cứu thuật toán rút gọn thuộc tính trong hệ thông tin và bảng quyết định không đầy đủ sử dụng metric.
  • Nguyễn Quang Khanh (2012) nghiên cứu bài toán khai phá luật quyết định trong bảng dữ liệu có giá trị thuộc tính thay đổi.
  • Cao Chính Nghĩa (2017) đề xuất phương pháp rút gọn thuộc tính trên bảng quyết định miền giá trị thực và sinh luật quyết định mờ.
Nhóm nghiên cứu Tác giả và năm Trọng tâm nghiên cứu Hạn chế ghi nhận trong văn bản
Quan hệ / Gia tăng Shan và Ziarko (1995) Học gia tăng luật quyết định chắc chắn Chưa xét bảng quyết định không nhất quán
Quan hệ / Gia tăng Bian (1998) Ma trận quyết định mở rộng Không xét luật không chắc chắn, không cập nhật đồng thời độ đo
Quan hệ / Gia tăng Tong và An (2002) Bảy trường hợp khi thêm đối tượng Chưa giải quyết bài toán loại bỏ đối tượng
Quan hệ / Gia tăng Liu (2009) Gia tăng ma trận độ chính xác và độ phủ Tiêu tốn bộ nhớ và thời gian tính toán lớn
Quan hệ / Biến đổi thuộc tính Chen (2010) Cập nhật xấp xỉ khi làm mịn thuộc tính Chưa giải quyết việc sinh luật có ý nghĩa khi giá trị thay đổi
Đa chiều / Kho dữ liệu Kamber và cs (1997) Luật kết hợp đa chiều từ đơn chiều Dựa trên khối dữ liệu và tham số Count truyền thống
Đa chiều / Kho dữ liệu Volker, Wolfram, Mathias (2015) Khoan sâu từng chiều dữ liệu Chưa xây dựng mô hình lý thuyết, chưa rõ tính tổng quát của luật
Đa chiều / Kho dữ liệu Hanen Brahmi (2019) Phân cấp thứ nguyên đặc trưng Chưa có mô hình lý thuyết hoàn chỉnh cho khai phá dữ liệu đa chiều
Khối / Bảng tại Việt Nam Nguyễn Xuân Huy, Trịnh Đình Thắng (1998) Đề xuất mô hình dữ liệu dạng khối Đặt nền tảng lý thuyết đại số và cấu trúc, chưa nghiên cứu khai phá luật
Khối / Bảng tại Việt Nam Nguyễn Quang Khanh (2012) Khai phá luật khi thuộc tính thay đổi Nghiên cứu trên bảng dữ liệu quan hệ thông thường

Khoảng trống mà luận án lựa chọn giải quyết là: xây dựng hệ thống lý thuyết hình thức cho việc khai phá luật quyết định trên mô hình dữ liệu dạng khối; thiết lập mối quan hệ toán học giữa luật trên toàn khối và luật trên từng lát cắt; xây dựng các giải thuật khai phá luật gia tăng hiệu quả khi giá trị thuộc tính bị làm mịn hoặc làm thô, cũng như khi tập đối tượng tăng hoặc giảm, khắc phục tình trạng tốn bộ nhớ và thời gian tính toán của các tiếp cận trước đây.

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án dựa trên nền tảng lý thuyết tập thô (Rough Set Theory), lý thuyết hệ thông tin, bảng quyết định và mô hình cơ sở dữ liệu dạng khối:

  • Hệ thông tin: Được định nghĩa hình thức bởi bộ bốn $S = (U, A, V, f)$, trong đó $U$ là tập hữu hạn các đối tượng, $A$ là tập hữu hạn các thuộc tính, $V$ là miền giá trị của các thuộc tính, và $f: U \times A \to V$ là hàm thông tin. Hệ thông tin là đầy đủ nếu mọi $u \in U, a \in A$ đều xác định được giá trị $f(u, a)$, ngược lại là hệ không đầy đủ.
  • Quan hệ không phân biệt được: Với $P \subseteq A$, quan hệ hai ngôi $IND(P) = {(u,v) \in U \times U \mid \forall a \in P, u(a) = v(a)}$ là một quan hệ tương đương, phân hoạch tập $U$ thành các lớp tương đương ký hiệu là $U/IND(P)$ hoặc $U/P$. Lớp tương đương chứa $u$ là $[u]_P = {v \in U \mid (u,v) \in IND(P)}$. Thuật toán 1.1 trong văn bản xác định các lớp tương đương thông qua việc sắp xếp tập đối tượng theo thứ tự từ điển với độ phức tạp tính toán là $O(k|U|\log|U|)$, trong đó $k = |P|$.
  • Bảng quyết định: Là hệ thông tin đặc biệt $DS = (U, C \cup D)$, trong đó tập thuộc tính $A$ được chia thành tập thuộc tính điều kiện $C$ và tập thuộc tính quyết định $D$ ($C \cap D = \emptyset$). Phân hoạch sinh bởi $C$ và $D$ lần lượt là $U/C = {C_1, C_2, \dots, C_m}$ và $U/D = {D_1, D_2, \dots, D_n}$.
  • Luật quyết định: Luật có dạng $C_i \to D_j$ với $C_i \in U/C, D_j \in U/D$. Các độ đo định lượng gồm:
    • Độ hỗ trợ: $Sup(C_i, D_j) = |C_i \cap D_j|$.
    • Độ chính xác: $Acc(C_i, D_j) = \frac{|C_i \cap D_j|}{|C_i|}$.
    • Độ phủ: $Cov(C_i, D_j) = \frac{|C_i \cap D_j|}{|D_j|}$.
    • Luật là chắc chắn nếu $Acc(C_i, D_j) = 1$; là không chắc chắn nếu $0 < Acc(C_i, D_j) < 1$; và là luật có ý nghĩa nếu đồng thời thỏa mãn hai ngưỡng cho trước: $Acc(C_i, D_j) \ge \alpha$ và $Cov(C_i, D_j) \ge \beta$ với $\alpha, \beta \in (0, 1)$.
  • Mô hình dữ liệu dạng khối: Lược đồ khối $R = (id; A_1, A_2, \dots, A_n)$ với $id$ là tập chỉ số hữu hạn khác rỗng và $A_i$ là các thuộc tính. Một khối $r(R)$ gồm các phần tử $t$, mỗi phần tử là một họ các ánh xạ $t = {t_i: id \to dom(A_i)}_{i=1}^n$. Với mỗi $x \in id$, lát cắt của khối tại $x$ là $r(R_x)$ với $R_x = ({x}; A_1, \dots, A_n)$. Thuộc tính chỉ số được biểu diễn là $x(i) = (x, A_i)$.
  • Đại số quan hệ trên khối: Luận án sử dụng các phép toán hình thức mở rộng trên khối gồm: phép hợp ($\cup$), phép giao ($\cap$), phép trừ ($-$), tích Đề các ($r \times s$), tích Đề các theo tập chỉ số ($r \times_{id} s$), phép chiếu ($P(r)$), phép chọn ($F(r)$), phép kết nối tự nhiên ($r \bowtie s$ hoặc $r * s$) và phép chia ($r \div s$).
  • Khối quyết định: Được định nghĩa là bộ bốn $DB = (U, C \cup D, V, f)$, trong đó $C = \bigcup_{i=1}^k \bigcup_{x \in id} x(i)$ là tập thuộc tính chỉ số điều kiện và $D = \bigcup_{i=k+1}^n \bigcup_{x \in id} x(i)$ là tập thuộc tính chỉ số quyết định. Lát cắt của khối quyết định tại $x \in id$ là $DB_x = (U, C_x \cup D_x, V_x, f_x)$.

Phương pháp nghiên cứu kết hợp giữa nghiên cứu lý thuyết hình thức (xây dựng định nghĩa, phát biểu và chứng minh các mệnh đề, định lý, hệ quả toán học) và nghiên cứu thực nghiệm (thiết kế thuật toán, phân tích độ phức tạp thuật toán và cài đặt chương trình thử nghiệm).

Dữ liệu minh họa và thực nghiệm được trích xuất từ dữ liệu theo dõi bệnh nhân sốt vi rút tại Khoa Nhi A – Bệnh viện Bạch Mai cơ sở 2 trong 4 ngày ($id = {x, y, z, t}$ đại diện cho Ngày 1, Ngày 2, Ngày 3, Ngày 4). Tập thuộc tính đối tượng gồm $A_1$ (Sốt), $A_2$ (Ho), $A_3$ (Sổ mũi), $A_4$ (Phác đồ điều trị - PĐĐT), $A_5$ (Sốt vi rút - Sốt VR). Tập đối tượng $U$ bao gồm 12 nhóm đối tượng đại diện với tổng kích thước dữ liệu được biểu diễn thông qua thuộc tính số lượng (SL):

Nhóm đối tượng Số lượng (SL) Ngày 1 ($x$): $A_1, A_2, A_3, A_4, A_5$ Ngày 2 ($y$): $A_1, A_2, A_3, A_4, A_5$ Ngày 3 ($z$): $A_1, A_2, A_3, A_4, A_5$ Ngày 4 ($t$): $A_1, A_2, A_3, A_4, A_5$
$o_1$ 30 1, 1, 0, 1, 1 3, 1, 1, 1, 2 2, 2, 0, 1, 1 0, 1, 0, 1, 0
$o_2$ 90 3, 3, 2, 2, 3 2, 3, 2, 2, 2 1, 2, 1, 2, 1 0, 1, 0, 2, 0
$o_3$ 45 3, 2, 1, 1, 3 3, 1, 0, 1, 3 2, 0, 0, 1, 2 2, 0, 0, 1, 2
$o_4$ 60 3, 3, 2, 2, 3 2, 3, 2, 2, 2 1, 2, 1, 2, 1 0, 1, 0, 2, 0
$o_5$ 9 3, 2, 1, 3, 3 3, 1, 0, 3, 3 2, 0, 0, 3, 1 0, 0, 0, 3, 0
$o_6$ 75 1, 1, 0, 1, 1 3, 1, 1, 1, 2 2, 2, 0, 1, 1 0, 1, 0, 1, 0
$o_7$ 144 3, 1, 2, 1, 3 1, 3, 2, 1, 3 1, 2, 0, 1, 2 0, 1, 0, 1, 2
$o_8$ 24 1, 1, 0, 1, 1 3, 1, 1, 1, 2 2, 2, 0, 1, 1 0, 1, 0, 1, 0
$o_9$ 60 3, 2, 1, 3, 3 3, 1, 0, 3, 3 2, 0, 0, 3, 1 0, 0, 0, 3, 0
$o_{10}$ 150 3, 2, 1, 1, 1 3, 1, 0, 1, 2 2, 0, 0, 1, 1 0, 0, 0, 1, 0
$o_{11}$ 162 3, 3, 2, 3, 3 2, 3, 2, 3, 3 1, 2, 1, 3, 1 0, 1, 0, 3, 0
$o_{12}$ 75 3, 3, 2, 1, 3 2, 3, 2, 1, 3 1, 2, 1, 1, 2 0, 1, 0, 1, 3

Ngoài ra, luận án sử dụng ví dụ Khách hàng siêu thị gồm các thuộc tính $A_1$ (Mã KH), $A_2$ (Nước giặt), $A_3$ (Dầu gội), $A_4$ (Sữa tắm) và $id = {1/2019, 2/2019, 3/2019}$ để minh họa các thao tác hình thức trên khối và lát cắt.

Nội dung chính theo từng chương

Chương 1: Một số kiến thức cơ sở

Chương này trình bày các nội dung nền tảng về lý thuyết khai phá dữ liệu, luật quyết định và mô hình dữ liệu dạng khối:

  • Khái quát quy trình phát hiện tri thức gồm 3 bước: lọc dữ liệu/tiền xử lý, khai phá dữ liệu bằng các thuật toán, và hậu xử lý đánh giá kết quả theo yêu cầu người dùng. Bốn nhóm bài toán chính được phân định rõ: Phân lớp (Classification), Dự đoán (Prediction), Luật kết hợp (Association Rule) và Phân cụm (Clustering).
  • Hệ thống hóa lý thuyết bảng quyết định và luật quyết định dựa trên quan hệ không phân biệt được $IND(P)$. Trình bày thuật toán xác định các lớp tương đương trên tập thuộc tính $P$ thông qua sắp xếp thứ tự từ điển có độ phức tạp $O(k|U|\log|U|)$. Xác lập cấu trúc của các ma trận độ đo $Sup$, $Acc$, $Cov$ và định nghĩa luật có ý nghĩa theo cặp ngưỡng $(\alpha, \beta)$.
  • Trình bày mô hình cơ sở dữ liệu dạng khối do Nguyễn Xuân Huy và Trịnh Đình Thắng đề xuất: định nghĩa lược đồ khối, khối dữ liệu dưới dạng họ các ánh xạ, lát cắt $r(R_x)$ tại một điểm chỉ số $x$. Thiết lập đại số quan hệ trên khối gồm 9 phép toán: phép hợp, phép giao, phép trừ, tích Đề các, tích Đề các theo tập chỉ số ($r \times_{id} s$), phép chiếu, phép chọn, phép kết nối tự nhiên và phép chia khối.

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

Chương này giải quyết trọn vẹn bài toán khai phá luật trên khối tĩnh và khối có giá trị thuộc tính biến động (làm thô và làm mịn):

  • Đề xuất các khái niệm mở rộng: Khối thông tin $IB = (U, A, V, f)$, lát cắt khối thông tin $IB_x$, Khối quyết định $DB = (U, C \cup D, V, f)$ và lát cắt khối quyết định $DB_x$. Chỉ rõ khối dữ liệu quan hệ là trường hợp suy biến của khối thông tin khi tập chỉ số $id$ chỉ gồm một phần tử.
  • Chứng minh Mệnh đề 2.1: Mối liên hệ giữa các lớp tương đương trên toàn khối và trên các lát cắt: $C_i = \bigcap_{x \in id} C_x^{p_x}$ và $D_j = \bigcap_{x \in id} D_x^{q_x}$, với $p_x \in {1, \dots, t_x}$ và $q_x \in {1, \dots, h_x}$.
  • Chứng minh Mệnh đề 2.2: Ma trận $Acc$ và ma trận $Cov$ hoàn toàn có thể tính trực tiếp thông qua ma trận độ hỗ trợ $Sup$: $$Acc(C_i, D_j) = \frac{Sup(C_i, D_j)}{\sum_{p=1}^g Sup(C_i, D_p)}, \quad Cov(C_i, D_j) = \frac{Sup(C_i, D_j)}{\sum_{p=1}^m Sup(C_p, D_j)}$$
  • Xây dựng thuật toán MDLB (Mining Decision rules on b-Block and slices) gồm 4 bước: (1) Phân lớp tương đương điều kiện và quyết định trên khối và lát cắt bằng sắp xếp từ điển; (2) Tính ma trận $Sup$ cho khối ($Sup(C_i, D_j) = |C_i \cap D_j|$) và cho lát cắt ($Sup(C_{xt}, D_{xh}) = |C_{xt} \cap D_{xh}|$); (3) Tính các ma trận $Acc$ và $Cov$; (4) So sánh với ngưỡng $\alpha, \beta$ để kết xuất các luật quyết định có ý nghĩa $C_i \to D_j$.
  • Thiết lập cơ chế toán học cho bài toán biến đổi giá trị thuộc tính chỉ số:
    • Làm mịn (refinement): Giá trị $z$ của thuộc tính $a$ tách thành hai giá trị mới $w$ và $y$ ($Z = W \cup Y, W \cap Y = \emptyset$).
    • Làm thô (coarsening): Hai giá trị $w$ và $y$ gộp lại thành giá trị mới $z$.
    • Định lý 2.1 và Hệ quả 2.1, 2.2: Khi làm thô hai lớp điều kiện $C_p, C_q$ thành $C_s$, dòng mới trong ma trận $Sup$ là tổng hai dòng cũ: $Sup(C_s, D_j) = Sup(C_p, D_j) + Sup(C_q, D_j)$. Tương tự, khi làm thô hai lớp quyết định $D_y, D_w$ thành $D_z$, cột mới là tổng hai cột cũ: $Sup(C_i, D_z) = Sup(C_i, D_y) + Sup(C_i, D_w)$.
    • Định lý 2.2 và Hệ quả 2.3, 2.4: Khi làm mịn lớp $C_s$ thành $C_p, C_q$, dòng tương ứng trong ma trận $Sup$ tách thành hai dòng mới với $Sup(C_s, D_j) = Sup(C_p, D_j) + Sup(C_q, D_j)$. Tương tự cho việc tách cột khi làm mịn lớp quyết định.
    • Mệnh đề 2.3: Chứng minh rằng nếu luật $C_i \to D_j$ là luật có ý nghĩa trên khối thì nó cũng là luật có ý nghĩa trên một lát cắt bất kỳ của khối tại $x \in id$.
    • Mệnh đề 2.4 đến 2.10: Thiết lập tính chất làm thô và làm mịn cảm sinh một phần của các lớp tương đương trên các lát cắt $r_x$.
    • Mệnh đề 2.11 và 2.12: Chứng minh tính chất làm mịn cảm sinh hoàn toàn trên lát cắt $r_x$: $C_{xi}' = \bigcup_{j \in E} C_{j1}$ và $C_{xi}'' = \bigcup_{j \in E} C_{j2}$.
  • Xây dựng thuật toán MDLB_VAC (Mining Decision rules on Block with Value Attribute Changes) để cập nhật gia tăng các ma trận đo lường và sinh luật khi giá trị thuộc tính biến đổi mà không cần tính lại từ đầu.

Chương 3: Khai phá luật quyết định khi tập đối tượng thay đổi

Theo bố cục được trình bày trong luận án, Chương 3 tập trung giải quyết bài toán biến động tập đối tượng của khối quyết định:

  • Xây dựng mô hình toán học cho trường hợp bổ sung thêm đối tượng mới hoặc loại bỏ đối tượng hiện có ra khỏi khối quyết định.
  • Đề xuất hai phương pháp tính gia tăng để tìm luật trên khối và lát cắt khi tập đối tượng biến động:
    1. Phương pháp tính gia tăng ma trận độ chính xác ($Acc$) và ma trận độ phủ ($Cov$).
    2. Phương pháp tính gia tăng ma trận độ hỗ trợ ($Sup$).
  • Phân tích và tính toán độ phức tạp thuật toán của các phương pháp đề xuất. Cài đặt chương trình thực nghiệm để đánh giá và so sánh hiệu năng giữa hai phương pháp trên các tập dữ liệu thử nghiệm.

Kết quả và những đóng góp mới

Luận án tự nêu các đóng góp mới về mặt lý luận khoa học và thực tiễn kỹ thuật như sau:

  • Về lý luận:
    • Đã mở rộng lý thuyết bảng quyết định và hệ thông tin từ mô hình quan hệ truyền thống sang mô hình dữ liệu dạng khối, hình thức hóa các khái niệm khối thông tin, khối quyết định, lát cắt khối quyết định và các độ đo $Sup$, $Acc$, $Cov$ trên khối.
    • Thiết lập và chứng minh định lý về mối quan hệ giữa các lớp tương đương trên toàn khối và trên từng lát cắt ($C_i = \bigcap_{x \in id} C_x^{p_x}$).
    • Chứng minh tính chất bảo toàn của luật có ý nghĩa: một luật có ý nghĩa trên toàn bộ khối thì luôn là luật có ý nghĩa trên một lát cắt bất kỳ của khối tại $x \in id$.
    • Phát biểu và chứng minh hệ thống định lý, hệ quả về sự biến đổi của ma trận độ hỗ trợ $Sup$ khi thực hiện các phép toán làm thô và làm mịn giá trị thuộc tính điều kiện hoặc thuộc tính quyết định (cộng gộp hoặc tách dòng/cột tương ứng).
    • Chứng minh các cơ chế làm thô, làm mịn cảm sinh một phần và cảm sinh hoàn toàn từ khối xuống các lát cắt.
  • Về thực tiễn và thuật toán:
    • Xây dựng thuật toán MDLB cho phép khai phá luật quyết định đồng thời trên khối và trên lát cắt của khối.
    • Xây dựng thuật toán MDLB_VAC giải quyết bài toán cập nhật luật gia tăng khi giá trị thuộc tính thay đổi bằng cách tính toán cục bộ trên ma trận $Sup$ thay vì quét lại toàn bộ dữ liệu, giúp giảm chi phí tính toán.
    • Đề xuất hai phương pháp tính gia tăng khi tập đối tượng biến động (gia tăng trên ma trận $Acc, Cov$ và gia tăng trên ma trận $Sup$), thực hiện phân tích độ phức tạp và cài đặt thực nghiệm so sánh hai phương pháp.
  • Kiến nghị và giải pháp đề xuất:
    • Đề xuất ứng dụng mô hình khối và thuật toán khai phá luật trên khối vào các bài toán quản lý và chẩn đoán y tế theo dõi bệnh nhân nhiều ngày tại bệnh viện (đặc biệt là theo dõi sự đáp ứng phác đồ điều trị của các nhóm triệu chứng sốt, ho, sổ mũi qua từng ngày nằm viện).
    • Khuyến nghị ứng dụng trong quản trị thương mại tại các siêu thị nhằm theo dõi biến động sức mua của khách hàng theo chu kỳ tháng/năm, và trong công tác quản lý theo dõi quá trình phát triển cán bộ tại các cơ quan.

Hạn chế và hướng nghiên cứu tiếp

Dựa trên phạm vi và các nội dung được công bố trong văn bản luận án, các hạn chế và hướng nghiên cứu tiếp gồm:

  • Về phạm vi biến đổi thuộc tính: Luận án chỉ giới hạn khảo sát hai trường hợp thay đổi giá trị thuộc tính là làm mịn (tách một giá trị thành hai giá trị mới) và làm thô (gộp hai giá trị thành một giá trị mới); chưa mở rộng cho trường hợp một giá trị tách thành nhiều hơn hai giá trị hoặc gộp đồng thời nhiều giá trị phức tạp.
  • Về dạng dữ liệu: Luận án tập trung vào các thuộc tính có miền giá trị rời rạc; chưa giải quyết trực tiếp trên các bảng quyết định có miền giá trị thực liên tục hoặc dữ liệu mờ (như hướng tiếp cận của Cao Chính Nghĩa năm 2017).
  • Về tính đầy đủ của dữ liệu: Khái niệm khối thông tin không đầy đủ (chứa giá trị thiếu) đã được định nghĩa hình thức ở phần cơ sở nhưng các thuật toán MDLB và MDLB_VAC chủ yếu tập trung xử lý trên khối thông tin đầy đủ; hướng nghiên cứu tiếp có thể mở rộng cơ chế cập nhật luật gia tăng trên khối dữ liệu không đầy đủ.

Giá trị tham khảo

Luận án có giá trị tham khảo cụ thể cho các nhóm đối tượng học thuật và ứng dụng:

  • Nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Khoa học máy tính, Hệ thống thông tin:
    • Có thể tham khảo Chương 1 về việc mở rộng các phép toán đại số quan hệ trên khối ($r \times_{id} s$, kết nối tự nhiên, phép chia khối).
    • Tham khảo Chương 2 về các kỹ thuật chứng minh quan hệ tương đương, phân hoạch thô/mịn và phương pháp biểu diễn độ đo thông qua ma trận đại số.
  • Các nhà nghiên cứu về kỹ thuật học gia tăng và khai phá dữ liệu lớn:
    • Kỹ thuật tính toán ma trận $Acc$ và $Cov$ gián tiếp thông qua ma trận $Sup$ (Mệnh đề 2.2) và quy tắc cộng/tách dòng, cột của ma trận $Sup$ (Hệ quả 2.1 - 2.4) là tài liệu tham khảo cho việc thiết kế các thuật toán khai phá gia tăng nhằm tiết kiệm tài nguyên bộ nhớ và thời gian CPU.
  • Kỹ sư dữ liệu và chuyên gia phân tích nghiệp vụ trong lĩnh vực y tế, bán lẻ, nhân sự:
    • Có thể tham khảo cách thiết kế cấu trúc khối dữ liệu theo trục $id$ (ngày theo dõi, chu kỳ thời gian) và cách giải nghĩa luật quyết định $C_i \to D_j$ để đánh giá hiệu quả của phác đồ điều trị hoặc hành vi tiêu dùng theo tiến trình.

Câu hỏi thường gặp

Mô hình dữ liệu dạng khối khác gì so với mô hình dữ liệu quan hệ truyền thống và mô hình data cube?

Trong mô hình dữ liệu quan hệ, dữ liệu được tổ chức dưới dạng bảng hai chiều và các luật khai phá được chỉ phản ánh mối quan hệ tĩnh tại một thời điểm xác định. Mô hình dữ liệu dạng khối đưa thêm trục chỉ số $id$ vào lược đồ $R = (id; A_1, \dots, A_n)$, trong đó mỗi phần tử là một họ ánh xạ từ $id$ đến miền giá trị của các thuộc tính, cho phép theo dõi toàn bộ tiến trình biến đổi của đối tượng theo thời gian, giai đoạn hoặc khoảng cách. Khác với mô hình data cube (chủ yếu phục vụ truy vấn phân tích trực tuyến OLAP và tổng hợp theo các độ đo thống kê đa chiều), mô hình khối xây dựng hệ thống đại số quan hệ đầy đủ và cho phép khai phá luật quyết định hình thức trên toàn bộ tiến trình cũng như trên từng lát cắt đơn lẻ.

Tại sao có thể tính ma trận độ chính xác ($Acc$) và ma trận độ phủ ($Cov$) trực tiếp từ ma trận độ hỗ trợ ($Sup$)?

Theo chứng minh tại Mệnh đề 2.2 của luận án, độ chính xác $Acc(C_i, D_j)$ bằng tỷ số giữa $|C_i \cap D_j|$ và $|C_i|$. Vì tập các lớp tương đương quyết định ${D_1, \dots, D_g}$ tạo thành một phân hoạch của không gian đối tượng nên $|C_i| = \sum_{p=1}^g |C_i \cap D_p| = \sum_{p=1}^g Sup(C_i, D_p)$. Do đó, $Acc(C_i, D_j) = \frac{Sup(C_i, D_j)}{\sum_{p=1}^g Sup(C_i, D_p)}$. Tương tự, độ phủ $Cov(C_i, D_j) = \frac{Sup(C_i, D_j)}{\sum_{p=1}^m Sup(C_p, D_j)}$. Nhờ đó, thuật toán chỉ cần lưu trữ và cập nhật một ma trận duy nhất là ma trận $Sup$.

Khi hai giá trị của một thuộc tính chỉ số điều kiện được làm thô thành một giá trị mới, ma trận độ hỗ trợ biến đổi như thế nào?

Theo Hệ quả 2.1 (hệ quả của Định lý 2.1), khi hai giá trị được làm thô thì hai lớp tương đương điều kiện tương ứng $C_p$ và $C_q$ sẽ được gộp thành một lớp tương đương điều kiện mới $C_s = C_p \cup C_q$. Trong ma trận độ hỗ trợ $Sup$, hai dòng tương ứng với $C_p$ và $C_q$ được kết hợp thành một dòng mới tương ứng với $C_s$. Giá trị của mỗi phần tử trên dòng mới được tính bằng tổng giá trị của hai phần tử tương ứng trên hai dòng cũ: $Sup(C_s, D_j) = Sup(C_p, D_j) + Sup(C_q, D_j)$ với mọi $j = 1, \dots, g$.

Mối quan hệ logic giữa luật quyết định có ý nghĩa trên khối và luật trên từng lát cắt là gì?

Theo Mệnh đề 2.3, nếu một luật quyết định $C_i \to D_j$ là luật có ý nghĩa trên toàn bộ khối quyết định (tức là thỏa mãn ngưỡng $Acc \ge \alpha$ và $Cov \ge \beta$) thì nó cũng là một luật quyết định có ý nghĩa trên một lát cắt bất kỳ của khối tại điểm $x \in id$. Điều này được chứng minh dựa trên tính chất $C_i \subseteq C_x^{p_x}$ và $D_j \subseteq D_x^{q_x}$, cho thấy luật tìm được trên toàn khối bảo toàn giá trị pháp lý và ngữ nghĩa trên từng lát cắt thời gian cục bộ.

Hai phương pháp khai phá luật khi tập đối tượng thay đổi trong Chương 3 là gì?

Luận án đề xuất hai phương pháp tính gia tăng:

  1. Phương pháp tính gia tăng trực tiếp trên hai ma trận độ đo $Acc$ và $Cov$ (tương tự như hướng mở rộng từ cách tiếp cận của Liu 2009 nhưng áp dụng trên cấu trúc khối).
  2. Phương pháp tính gia tăng trên ma trận độ hỗ trợ $Sup$, sau đó áp dụng Mệnh đề 2.2 để suy ra $Acc$ và $Cov$. Thực nghiệm trong luận án cho thấy phương pháp gia tăng ma trận $Sup$ giúp tối ưu hóa không gian lưu trữ và thời gian tính toán hơn so với việc phải cập nhật song song cả hai ma trận $Acc$ và $Cov$.

Kết luận

Luận án đã giải quyết bài toán khai phá luật quyết định theo tiến trình thông qua việc mở rộng lý thuyết bảng quyết định và lý thuyết tập thô trên mô hình cơ sở dữ liệu dạng khối do Nguyễn Xuân Huy và Trịnh Đình Thắng đề xuất. Tác giả đã thiết lập hệ thống cơ sở lý thuyết toán học hoàn chỉnh, chứng minh các định lý về mối quan hệ giữa khối và lát cắt, cũng như quy luật biến đổi của ma trận độ hỗ trợ khi dữ liệu có sự thay đổi về giá trị thuộc tính và tập đối tượng. Hai thuật toán MDLB và MDLB_VAC cùng các giải pháp cập nhật gia tăng đã được đề xuất, tính toán độ phức tạp và cài đặt thực nghiệm trên dữ liệu thực tế, cung cấp một phương pháp khai phá tri thức hiệu quả cho các lĩnh vực có dữ liệu biến động theo thời gian như y tế và quản lý.