Tổng quan luận án

Luận án tiến sĩ chuyên ngành Khoa học máy tính (mã số 9 48 01 01) của tác giả Đỗ Thị Lan Anh, thực hiện dưới sự hướng dẫn khoa học của PGS. TS Trịnh Đình Thắng 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 (năm 2020), mang tiêu đề: "Khai phá luật quyết định trên mô hình dữ liệu dạng khối".

Tính cấp thiết và khoảng trống nghiên cứu

Khai phá dữ liệu là một khâu trọng yếu trong tiến trình phát hiện tri thức từ cơ sở dữ liệu. Nhóm bài toán trọng tâm trong lĩnh vực này bao gồm: phân lớp, dự đoán, luật kết hợp và phân cụm. Trong đó, khai phá luật quyết định thuộc nhóm bài toán phân lớp đối tượng, đã được nghiên cứu rộng rãi trên mô hình cơ sở dữ liệu quan hệ và các mô hình mở rộng như datacube, kho dữ liệu, mô hình đa chiều. Tuy nhiên, các kỹ thuật khai phá luật trên mô hình quan hệ chỉ phản ánh mối quan hệ giữa các đối tượng tại một thời điểm tĩnh cố định.

Trong nhiều lĩnh vực thực tế như y tế (chẩn đoán và theo dõi diễn biến điều trị bệnh), thương mại (theo dõi hành vi mua bán theo chu kỳ), hay quản trị nhân sự, dữ liệu luôn vận động và biến đổi theo một tiến trình thời gian, giai đoạn hoặc khoảng cách. Trên mô hình quan hệ truyền thống, khi một giá trị thuộc tính thay đổi (ví dụ mức độ sốt của bệnh nhân biến đổi), giá trị cũ sẽ bị ghi đè, làm mất đi thông tin về lịch sử diễn biến. Năm 1998, Nguyễn Xuân Huy và Trịnh Đình Thắng đã đề xuất mô hình dữ liệu dạng khối – một mô hình mở rộng từ mô hình dữ liệu quan hệ bằng cách tích hợp thêm trục chỉ số $id$ (đại diện cho thời gian, giai đoạn...). Mặc dù mô hình khối đã được xây dựng về mặt lý thuyết đại số quan hệ, việc khai phá luật quyết định trên mô hình này vẫn chưa được giải quyết đầy đủ, đặc biệt là khi cơ sở dữ liệu có sự biến động về tập giá trị thuộc tính hoặc tập đối tượng.

Mục tiêu nghiên cứu

Luận án xác định mục tiêu tổng quát là tìm kiếm các mối quan hệ (luật quyết định) từ các nhóm đối tượng được phân hoạch theo quan hệ tương đương trên mô hình khối, giải quyết ba bài toán cụ thể:

  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 dữ liệu.
  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 hoặc làm thô 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 (bổ sung hoặc loại bỏ phần tử khỏi khối).

Giả thuyết nghiên cứu

Luận án đặt ra bốn giả thuyết nghiên cứu cần chứng minh và thực nghiệm:

  1. Đề xuất các khái niệm hình thức, chứng minh các mệnh đề và tính chất nền tảng để thiết lập mô hình khai phá luật trên khối và trên từng lát cắt của khối.
  2. Đề xuất thuật toán tính ma trận độ hỗ trợ (Sup), từ đó suy dẫn ma trận độ chính xác (Acc), ma trận độ phủ (Cov) để trích xuất các luật quyết định có ý nghĩa trên khối.
  3. Xây dựng 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 (làm mịn, làm thô), phân tích độ phức tạp thuật toán và tiến hành cài đặt thực nghiệm.
  4. Xây dựng mô hình bổ sung và loại bỏ phần tử trên khối quyết định; đề xuất hai phương pháp tính gia tăng (phương pháp gia tăng ma trận Acc, Cov và phương pháp gia tăng ma trận Sup); tính toán độ phức tạp lý thuyết và thực nghiệm đối sánh hiệu năng của hai phương pháp.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Luật quyết định và các độ đo liên quan (độ hỗ trợ, độ chính xác, độ phủ).
  • Phạm vi nghiên cứu: Mô hình cơ sở dữ liệu dạng khối và các lát cắt sinh ra từ trục chỉ số $id$.
  • Phương pháp nghiên cứu: Kết hợp nghiên cứu lý thuyết (xây dựng mô hình toán học, thiết lập định lý, mệnh đề, thuật toán) và nghiên cứu thực nghiệm (cài đặt phần mềm kiểm thử trên bộ dữ liệu mẫu).

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

Luận án đã hệ thống hóa các công trình nghiên cứu liên quan theo hai nhóm không gian nghiên cứu: quốc tế và Việt Nam.

Các nghiên cứu quốc tế

Nghiên cứu khai phá luật và học gia tăng trên mô hình quan hệ:

  • Shan và Ziarko (1995) đề xuất phương pháp tìm luật quyết định chắc chắn dựa trên học gia tăng, nhưng có hạn chế là chưa xử lý được 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 ma trận quyết định mở rộng để xử lý dữ liệu không nhất quán, song chưa xử lý được luật không chắc chắn và không cập nhật đồng thời độ chính xác và độ phủ.
  • Tong và An (2002) dùng ma trận quyết định để học gia tăng luật khi có đối tượng mới bổ sung dựa trên 7 trường hợp, nhưng chưa xem xét trường hợp loại bỏ đối tượng.
  • Liu (2009) xây dựng thuật toán phát hiện luật khi bổ sung và loại bỏ đối tượng dựa trên tính toán gia tăng ma trận độ chính xác và ma trận độ phủ; hạn chế là chiếm dụng nhiều bộ nhớ và thời gian tính toán do phải duy trì cập nhật cả hai ma trận.
  • Chen (2010) đề xuất thuật toán gia tăng cập nhật xấp xỉ một khái niệm khi làm mịn giá trị thuộc tính điều kiện, nhưng chưa giải quyết bài toán sinh luật hoàn chỉnh khi giá trị thuộc tính thay đổi.

Nghiên cứu khai phá dữ liệu trên mô hình đa chiều và kho dữ liệu:

  • Kamber cùng cộng sự (1997) là nhóm đầu tiên nghiên cứu khai thác luật kết hợp đa chiều từ khối dữ liệu (data cube) 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: liên chiều (inter-dimensional), nội chiều (intra-dimensional) và luật kết hợp lai.
  • Chen cùng cộng sự (2000) khai thác luật kết hợp nội chiều bằng cách bổ sung đặc trưng từ các chiều khác ở nhiều mức trên 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ách tận dụng năng lực xử lý SQL sẵn có của kho dữ liệu.
  • Tjioe và Taniar (2005) trích xuất luật kết hợp đa chiều dựa trên tổng hợp dữ liệu theo tham số Count qua bốn thuật toán: VAvg, HAvg, WMAvg và ModusFilter.
  • Riadh Ben và Sabine Loudcher (2006) khai thác luật kết hợp liên chiều từ khối lập phương, đưa ra hai tiêu chí đánh giá luật là Lift và Loevinger thay vì chỉ dùng Count.
  • Volker, Wolfram và Mathias (2015) khai phá dữ liệu đa chiều bằng kỹ thuật "khoan sâu" từng chiều, nhưng chưa có mô hình lý thuyết tổng quát cho toàn khối.
  • Omar và Mohamed (2017) đề xuất mẫu thử đa tiêu chí MCA tích hợp trên OLAP.
  • Viktor, Nataliia và Sergiy (2018) khai phá dữ liệu sự kiện mạng trên khối không gian – thời gian để phân tích thống kê và phát hiện cụm thời gian.
  • Hanen Brahmi (2019) tiếp cận khối datacube bằng cách phân cấp thứ nguyên đặc trưng theo các hướng rồi tổng hợp luật, nhưng cũng chưa xây dựng được mô hình lý thuyết hoàn chỉnh.

Các nghiên cứu tại Việt Nam

  • Nguyễn Hữu Trọng (2008) đề xuất thuật toán khai phá luật kết hợp khi bảng dữ liệu gia tăng theo chiều dọc và dùng cây quyết định khi bảng gia tăng theo chiều ngang.
  • Nguyễn Long Giang (2012) đề xuất 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 khai phá luật quyết định trong bảng dữ liệu có tập 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ực tiếp trên bảng quyết định miền giá trị thực và sinh luật quyết định mờ.

Khoảng trống luận án lựa chọn giải quyết

Các công trình trước đây chủ yếu dừng lại ở mô hình quan hệ hai chiều tĩnh hoặc các khối dữ liệu đa chiều (data cube) với thao tác tổng hợp dữ liệu OLAP đơn thuần. Vấn đề khai phá luật quyết định hình thức dựa trên quan hệ tương đương (theo lý thuyết tập thô) trên mô hình dữ liệu dạng khối có trục chỉ số $id$ chưa từng được xây dựng đồng bộ. Luận án lựa chọn giải quyết khoảng trống này bằng cách xây dựng mô hình toán học cho khối quyết định, thiết lập thuật toán khai phá luật trên khối và lát cắt, đồng thời giải quyết triệt để bài toán biến động dữ liệu (khi thuộc tính làm mịn/thô hoặc tập đối tượng tăng/giảm) thông qua kỹ thuật tính toán gia tăng tối ưu.

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

Cơ sở lý thuyết và các khái niệm nền tảng

Luận án kế thừa và phát triển hai nền tảng tảng lý thuyết: Lý thuyết tập thô (Rough Set Theory) của Z. Pawlak áp dụng trong hệ thông tin, và Lý thuyết mô hình dữ liệu dạng khối do Nguyễn Xuân Huy và Trịnh Đình Thắng khởi xướng (1998).

  1. Hệ thông tin và Bảng quyết định:

    • Hệ thông tin là 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 các thuộc tính, $V$ là miền giá trị, $f: U \times A \to V$ là hàm thông tin.
    • Quan hệ không phân biệt được với $P \subseteq A$: $$IND(P) = {(u, v) \in U \times U \mid \forall a \in P, u(a) = v(a)}$$ Quan hệ $IND(P)$ xác định một phân hoạch trên $U$, ký hiệu $U/P$, gồm các lớp tương đương $[u]_P$.
    • Bảng quyết định là hệ thông tin đặc biệt $DS = (U, C \cup D)$ với $C \cap D = \emptyset$, trong đó $C$ là tập thuộc tính điều kiện, $D$ là tập thuộc tính quyết định.
    • Luật quyết định có dạng $C_i \to D_j$ với $C_i \in U/C, D_j \in U/D$.
    • Các độ đo cơ bản:
      • Độ 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 được gọi là chắc chắn nếu $Acc(C_i, D_j) = 1$; không chắc chắn nếu $0 < Acc(C_i, D_j) < 1$; và có ý nghĩa nếu $Acc(C_i, D_j) \ge \alpha$ và $Cov(C_i, D_j) \ge \beta$ (với $\alpha, \beta \in (0, 1)$ là các ngưỡng cho trước).

  2. Mô hình dữ liệu dạng khối:

    • Lược đồ khối có dạng $R = (id; A_1, A_2, ..., A_n)$, trong đó $id$ là tập chỉ số hữu hạn khác rỗng, $A_i$ là các thuộc tính với miền giá trị $dom(A_i)$.
    • Khối $r(R)$ là tập hữu hạn các phần 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$.
    • Lát cắt của khối tại điểm $x \in id$ là khối $r(R_x)$ với $R_x = ({x}; A_1, A_2, ..., A_n)$. Thuộc tính $x(i) = (x, A_i)$ được gọi là thuộc tính chỉ số.
    • Đại số quan hệ trên khối gồm 9 phép toán hình thức: Phép hợp ($r \cup s$), phép giao ($r \cap s$), phép trừ ($r - s$), 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$ hay $r * s$), và phép chia ($r \div s$).

Phương pháp nghiên cứu thực tế

  • Phương pháp định tính và hình thức hóa toán học: Thiết lập các định nghĩa cho khối thông tin, khối quyết định, lát cắt khối quyết định; chứng minh bằng toán học các mệnh đề phân rã lớp tương đương, các định lý bảo toàn phân hoạch và quy tắc biến đổi ma trận khi làm mịn/thô giá trị thuộc tính.
  • Phương pháp thuật toán và định lượng: Xây dựng giải thuật dựa trên cấu trúc ma trận (Sup, Acc, Cov). Đánh giá hiệu năng thông qua độ phức tạp thuật toán lý thuyết và thời gian chạy thực tế (tính bằng mili giây).
  • Nguồn tư liệu và dữ liệu thực nghiệm: Dữ liệu theo dõi lâm sàng bệnh nhân sốt virut tại Khoa Nhi A – Bệnh viện Bạch Mai cơ sở 2 gồm 12 nhóm đối tượng qua 4 ngày theo dõi ($id = {x, y, z, t}$), cùng cơ sở dữ liệu thực nghiệm kiểm chứng thời gian chạy của các thuật toán đề xuấ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 1 thiết lập khung tri thức nền tảng phục vụ cho các đề xuất cốt lõi của luận án:

  • Trình bày định nghĩa và quy trình khai phá dữ liệu gồm ba bước: Lọc dữ liệu (tiền xử lý), khai phá dữ liệu, và hậu xử lý. Phân tích bốn lớp bài toán: Phân lớp, dự đoán, luật kết hợp và phân cụm.
  • Hệ thống hóa lý thuyết về hệ thông tin và quan hệ không phân biệt được. Trình bày Thuật toán 1.1 để xác định các lớp tương đương của quan hệ $IND(P)$ thông qua việc sắp xếp tập đối tượng $U$ theo thứ tự từ điển với độ phức tạp tính toán $O(k|U|\log|U|)$, trong đó $k = |P| \le |A|$.
  • Trình bày cấu trúc bảng quyết định, định nghĩa luật quyết định $C_i \to D_j$, cùng công thức tính ma trận độ hỗ trợ, độ chính xác, độ phủ. Nêu rõ tiêu chuẩn phân loại luật chắc chắn, không chắc chắn và luật có ý nghĩa theo các ngưỡng tối thiểu $\alpha, \beta$.
  • Giới thiệu mô hình dữ liệu dạng khối do Nguyễn Xuân Huy và Trịnh Đình Thắng đề xuất: Định nghĩa khối, lát cắt của khối tại một điểm chỉ số, và hệ thống 9 phép toán đại số quan hệ trên 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 2 mở rộng các khái niệm khai phá dữ liệu từ bảng phẳng lên mô hình khối và giải quyết bài toán biến động giá trị thuộc tính:

  1. Xây dựng hệ thống khái niệm trên mô hình khối:

    • Khối thông tin: $IB = (U, A, V, f)$ với $U$ là không gian đối tượng, $A = \bigcup_{i=1}^n \bigcup_{x \in id} x(i)$ là tập các thuộc tính chỉ số. Lát cắt khối thông tin tại $x$ là $IB_x = (U, A_x, V_x, f_x)$.
    • Khối quyết định: $DB = (U, C \cup D)$ trong đó tập thuộc tính chỉ số được phân chia thành tập điều kiện $C = \bigcup_{i=1}^k \bigcup_{x \in id} x(i)$ và tập quyết định $D = \bigcup_{i=k+1}^n \bigcup_{x \in id} x(i)$. Lát cắt khối quyết định tại $x$ là $DB_x = (U, C_x \cup D_x, V_x, f_x)$.
    • Quan hệ giữa khối và lát cắt (Mệnh đề 2.1): Luận án chứng minh rằng mọi lớp tương đương trên khối thực chất là giao của các lớp tương đương trên các lát cắt: $$C_i = \bigcap_{x \in id} C_{x_{p_x}}, \quad D_j = \bigcap_{x \in id} D_{x_{q_x}}$$
    • Mệnh đề 2.2: Chứng minh các ma trận độ chính xác $Acc$ và độ phủ $Cov$ hoàn toàn có thể tính toán trực tiếp từ ma trận độ hỗ trợ $Sup$: $$Acc(C_i, D_j) = \frac{Sup(C_i, D_j)}{\sum_{k=1}^g Sup(C_i, D_k)}, \quad Cov(C_i, D_j) = \frac{Sup(C_i, D_j)}{\sum_{p=1}^m Sup(C_p, D_j)}$$
    • Mệnh đề 2.3: Chứng minh nếu luật $C_i \to D_j$ có ý nghĩa trên khối quyết định thì nó cũng là luật quyết định có ý nghĩa trên một lát cắt bất kỳ tại $x \in id$ khi thực hiện làm mịn cảm sinh.

  2. Thuật toán khai phá luật trên khối và lát cắt (MDLB):

    • Đầu vào: Khối quyết định $DB = (U, C \cup D)$, các ngưỡng $\alpha, \beta$.
    • Đầu ra: Tập các luật quyết định có ý nghĩa $C_i \to D_j$.
    • Tiến trình 4 bước: (1) Sắp xếp từ điển để tìm phân hoạch $U/C = {C_1, ..., C_m}$ và $U/D = {D_1, ..., D_g}$; (2) Tính ma trận $Sup(C_i, D_j) = |C_i \cap D_j|$ trên khối và trên lát cắt; (3) Tính ma trận $Acc$ và $Cov$; (4) Lọc và xuất các luật thỏa mãn $Acc \ge \alpha$ và $Cov \ge \beta$.

  3. Biến đổi ma trận Sup khi làm mịn và làm thô giá trị thuộc tính:

    • Làm mịn thuộc tính (tách 1 giá trị thành 2 giá trị mới $w, y$): Định lý 2.2 và các Hệ quả 2.3, 2.4 chứng minh rằng một dòng (đối với thuộc tính điều kiện) hoặc một cột (đối với thuộc tính quyết định) trong ma trận $Sup$ sẽ được tách làm hai dòng/cột mới. Giá trị mới được cập nhật bằng cách tính cho một lớp, lớp còn lại suy dẫn qua phép trừ với giá trị cũ: $Sup(C_q, D_j) = Sup(C_s, D_j) - Sup(C_p, D_j)$.
    • Làm thô thuộc tính (gộp 2 giá trị $w, y$ thành 1 giá trị mới $z$): Định lý 2.1 và các Hệ quả 2.1, 2.2 chứng minh rằng hai dòng (hoặc hai cột) tương ứng trong ma trận $Sup$ sẽ được cộng dồn lại thành một dòng (hoặc một cột) duy nhất: $Sup(C_s, D_j) = Sup(C_p, D_j) + Sup(C_q, D_j)$.
    • Đề xuất thuật toán MDLB_VAC để cập nhật luật khi giá trị thuộc tính thay đổi mà không cần quét lại toàn bộ cơ sở dữ liệu từ đầu.

  4. Ví dụ thực nghiệm y tế: Sử dụng dữ liệu theo dõi bệnh nhân sốt virut tại Khoa Nhi A – Bệnh viện Bạch Mai cơ sở 2, với 5 thuộc tính: Sốt ($A_1$), Ho ($A_2$), Sổ mũi ($A_3$), Phác đồ điều trị ($A_4$), Mức sốt virut ($A_5$), trục $id = {x, y, z, t}$ đại diện cho 4 ngày theo dõi. Dữ liệu gồm 12 nhóm đối tượng $o_1$ đến $o_{12}$ với tổng số lượng thực tế là 904 lượt bệnh nhân. Luận án minh họa chi tiết quá trình phân hoạch ra các lớp tương đương $U/C = {C_1, ..., C_5}$ và $U/D = {D_1, ..., D_5}$, tính toán ma trận $Sup$, và trích xuất luật theo diễn tiến điều trị qua các ngày.

CHƯƠNG 3: KHAI PHÁ LUẬT QUYẾT ĐỊNH TRÊN KHỐI CÓ TẬP ĐỐI TƯỢNG THAY ĐỔI

Chương 3 giải quyết trọn vẹn bài toán khi cơ sở dữ liệu có sự biến động đối tượng (bổ sung hoặc loại bỏ):

  1. Mô hình toán học khi tập đối tượng thay đổi:

    • Khi bổ sung đối tượng $x$ vào khối: Không gian đối tượng trở thành $U' = U \cup {x}$. Đối tượng $x$ có thể thuộc về một lớp tương đương cũ (làm tăng kích thước lớp) hoặc tạo thành một lớp tương đương hoàn toàn mới.
    • Khi loại bỏ đối tượng $x$ khỏi khối: Không gian đối tượng trở thành $U' = U \setminus {x}$. Lớp chứa $x$ giảm số lượng phần tử, nếu lớp chỉ có duy nhất $x$ thì lớp đó bị xóa bỏ khỏi phân hoạch.

  2. Hai phương pháp tính toán gia tăng và thuật toán đề xuất:

    • Phương pháp 1 (Thuật toán MDLB_OSC1): Tính toán gia tăng trực tiếp trên ma trận độ chính xác ($Acc$) và ma trận độ phủ ($Cov$). Khi thêm/bớt đối tượng, thuật toán cập nhật lại mẫu số và tử số của từng ô trong cả hai ma trận $Acc$ và $Cov$, sau đó tiến hành so sánh với các ngưỡng $\alpha, \beta$ để sinh luật mới.
    • Phương pháp 2 (Thuật toán MDLB_OSC2): Tính toán gia tăng trên ma trận độ hỗ trợ ($Sup$). Vì $Sup(C_i, D_j) = |C_i \cap D_j|$, khi bổ sung hoặc loại bỏ đối tượng $x$, chỉ có duy nhất một ô $(i, j)$ trong ma trận $Sup$ tương ứng với lớp chứa $x$ bị tăng hoặc giảm 1 đơn vị (hoặc tạo dòng/cột mới). Sau khi ma trận $Sup$ được cập nhật nhanh chóng, thuật toán chỉ tính $Acc$ và $Cov$ tại các vị trí cần thiết để kết luận luật.

  3. So sánh hai phương pháp tính toán gia tăng: Luận án tổng kết sự khác biệt bản chất giữa hai phương pháp qua Bảng 3.1:

Tiêu chí so sánh Phương pháp MDLB_OSC1 (Gia tăng Acc và Cov) Phương pháp MDLB_OSC2 (Gia tăng Sup)
Đối tượng ma trận lưu trữ và cập nhật Bắt buộc phải duy trì, lưu trữ và cập nhật đồng thời cả 2 ma trận: $Acc$ và $Cov$. Chỉ duy trì và cập nhật duy nhất 1 ma trận: $Sup$.
Cơ chế tính toán phần tử Phải tính toán lại giá trị tỷ lệ phân số cho nhiều phần tử trong ma trận $Acc$ và $Cov$ mỗi khi kích thước lớp thay đổi. Chỉ cần tăng hoặc giảm giá trị số nguyên tại đúng tọa độ lớp tương ứng: $Sup(C_i, D_j) \pm 1$.
Không gian bộ nhớ Chiếm dụng dung lượng bộ nhớ lớn hơn do phải lưu trữ hai ma trận số thực. Tiết kiệm dung lượng bộ nhớ hơn (chỉ lưu trữ một ma trận số nguyên).
Thời gian tính toán trung bình Chậm hơn, chi phí xử lý biến động tỷ lệ lớn hơn. Nhanh hơn rõ rệt; ma trận $Acc$ và $Cov$ chỉ được tính cục bộ khi cần sinh luật.
  1. Kết quả thực nghiệm:
    • Thực nghiệm được tiến hành trên cơ sở dữ liệu thực nghiệm (thông số tại Bảng 3.2).
    • Biểu đồ mối quan hệ giữa số lượng luật và ngưỡng (Hình 3.5) cho thấy quy luật: Khi ngưỡng $\alpha$ và $\beta$ càng tăng thì số lượng luật quyết định có ý nghĩa càng giảm đi và ngược lại.
    • Biểu đồ so sánh thời gian thực thi (Hình 3.15) xác nhận thời gian chạy trung bình (tính bằng mili giây) của thuật toán MDLB_OSC2 luôn thấp hơn đáng kể so với thuật toán MDLB_OSC1 trong cả hai trường hợp bổ sung và loại bỏ đối tượng.

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

Đóng góp mới về mặt lý luận khoa học

  1. Thiết lập mô hình khối quyết định hình thức: Xây dựng hoàn chỉnh các định nghĩa về khối thông tin, khối quyết định, lát cắt khối quyết định, quan hệ không phân biệt được và luật quyết định trên mô hình dữ liệu dạng khối.
  2. Chứng minh mối liên hệ cấu trúc giữa khối và lát cắt: Chứng minh định lý hình thức khẳng định mọi lớp tương đương trên khối là giao của các lớp tương đương trên các lát cắt thành phần ($C_i = \bigcap_{x \in id} C_{x_{p_x}}$), và chứng minh tính bảo toàn ý nghĩa của luật quyết định từ khối xuống lát cắt khi thực hiện làm mịn cảm sinh.
  3. Hình thức hóa quy tắc chuyển đổi ma trận đo lường khi thuộc tính thay đổi: Chứng minh các định lý toán học về việc làm thô (gộp dòng/cột) và làm mịn (tách dòng/cột) trên ma trận độ hỗ trợ $Sup$, chứng minh khả năng suy dẫn trực tiếp giá trị mới thông qua giá trị cũ mà không cần quét lại dữ liệu.
  4. Xây dựng lý thuyết học gia tăng trên khối: Hình thức hóa mô hình biến động không gian đối tượng (bổ sung, loại bỏ phần tử) và chứng minh tính đúng đắn của việc cập nhật gia tăng ma trận độ hỗ trợ đơn lẻ thay vì phải cập nhật đồng thời hai ma trận độ chính xác và độ phủ.

Đóng góp mới về mặt kỹ thuật và thực tiễn

  1. Hệ thống thuật toán hoàn chỉnh: Đề xuất 4 thuật toán chuyên biệt:
    • MDLB: Thuật toán khai phá luật quyết định cơ sở trên khối và lát cắt.
    • MDLB_VAC: Thuật toán khai phá luật khi giá trị thuộc tính chỉ số thay đổi (làm mịn/thô).
    • MDLB_OSC1: Thuật toán sinh luật gia tăng thông qua ma trận $Acc$ và $Cov$.
    • MDLB_OSC2: Thuật toán sinh luật gia tăng thông qua ma trận $Sup$ (cho hiệu năng vượt trội).
  2. Giải pháp tối ưu hóa tính toán: Giảm thiểu đáng kể không gian lưu trữ và thời gian tính toán khi dữ liệu biến động nhờ cơ chế cập nhật cục bộ ma trận $Sup$.
  3. Cài đặt kiểm nghiệm: Xây dựng phần mềm thực nghiệm với giao diện trực quan (các hình từ 3.1 đến 3.14), chứng minh tính khả thi của mô hình trên dữ liệu diễn biến lâm sàng y tế.

Kiến nghị và đề xuất của tác giả

  • Ứng dụng mô hình dữ liệu dạng khối và thuật toán khai phá luật vào các hệ thống hỗ trợ ra quyết định lâm sàng tại các bệnh viện nhằm theo dõi phác đồ điều trị của bệnh nhân theo thời gian nằm viện.
  • Tích hợp các thuật toán học gia tăng MDLB_OSC2 vào các hệ thống thông tin quản lý có dữ liệu biến động liên tục (như quản lý khách hàng siêu thị, giám sát mạng) để cập nhật tri thức theo thời gian thực.

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

Dựa trên phạm vi nghiên cứu được tác giả công bố trong văn bản:

Hạn chế của luận án

  • Luận án chỉ giới hạn khảo sát trên mô hình khối với các giá trị thuộc tính rời rạc; chưa giải quyết trường hợp thuộc tính có miền giá trị liên tục hoặc giá trị mờ.
  • Đối với bài toán thay đổi thuộc tính, luận án chỉ mới xem xét hai trường hợp cơ bản: tách một giá trị thành hai giá trị mới (làm mịn) và gộp hai giá trị thành một giá trị mới (làm thô), chưa xét bài toán tổng quát khi tách/gộp đồng thời nhiều giá trị phức tạp.
  • Luận án giả định khối thông tin là đầy đủ; trường hợp khối thông tin không đầy đủ (chứa dữ liệu bị thiếu hoặc rỗng) chưa được tích hợp giải quyết trong các thuật toán sinh luật.

Hướng nghiên cứu tiếp

  • Mở rộng các thuật toán khai phá luật quyết định trên khối thông tin không đầy đủ (có chứa các giá trị thuộc tính rỗng/thiếu).
  • Nghiên cứu bài toán rút gọn thuộc tính chỉ số (attribute reduction) trực tiếp trên khối quyết định nhằm loại bỏ các thuộc tính dư thừa trước khi khai phá luật.
  • Ứng dụng mô hình và thuật toán trên các tập dữ liệu thực tế có kích thước lớn hơn trong các ngành giao dịch tài chính, thương mại điện tử và viễn thông.

Giá trị tham khảo

Luận án mang lại giá trị tham khảo cụ thể cho nhiều đối tượng trong nghiên cứu và ứng dụng:

  • Đối với nghiên cứu sinh và học viên cao học ngành Khoa học máy tính, Hệ thống thông tin:
    • Luận án cung cấp một tài liệu tham khảo chuẩn mực về phương pháp mở rộng mô hình dữ liệu quan hệ sang mô hình đa chiều có trục thời gian ($id$).
    • Phần chứng minh các định lý trong Chương 2 (Mệnh đề 2.1, Định lý 2.1, 2.2) là nguồn tư liệu hữu ích về việc vận dụng lý thuyết tập thô và quan hệ tương đương vào các cấu trúc dữ liệu phức hợp.
  • Đối với giảng viên và các nhà nghiên cứu về Khai phá dữ liệu (Data Mining):
    • Tài liệu tham khảo giá trị về kỹ thuật học gia tăng (incremental learning), đặc biệt là kỹ thuật cập nhật ma trận độ hỗ trợ ($Sup$) để tối ưu hóa thời gian tính toán so với cập nhật ma trận tỷ lệ ($Acc, Cov$).
  • Đối với kỹ sư phần mềm và chuyên gia phân tích dữ liệu ứng dụng:
    • Chương 2 và Chương 3 cung cấp mã giả thuật toán chi tiết (MDLB, MDLB_VAC, MDLB_OSC1, MDLB_OSC2), có thể trực tiếp chuyển đổi thành mã nguồn để xây dựng các mô-đun phát hiện tri thức trong các hệ thống quản lý bệnh án điện tử, phân tích hành vi tiêu dùng định kỳ, hoặc quản trị nhân sự theo giai đoạn.

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

1. Điểm khác biệt căn bản giữa mô hình dữ liệu dạng khối và mô hình dữ liệu quan hệ truyền thống là gì?

Mô hình dữ liệu quan hệ chỉ lưu trữ dữ liệu phẳng tại một thời điểm cố định; khi thông tin thay đổi, giá trị mới sẽ ghi đè lên giá trị cũ khiến tiến trình lịch sử bị mất đi. Mô hình dữ liệu dạng khối (do Nguyễn Xuân Huy và Trịnh Đình Thắng đề xuất năm 1998) bổ sung thêm trục chỉ số $id$ vào lược đồ: $R = (id; A_1, A_2, ..., A_n)$. Mỗi phần tử là một họ ánh xạ từ $id$ đến miền 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 dữ liệu theo thời gian, giai đoạn hoặc khoảng cách thông qua các lát cắt tại từng điểm chỉ số $x \in id$.

2. Mối quan hệ toán học giữa lớp tương đương trên khối và lớp tương đương trên các lát cắt được xác định như thế nào?

Theo Mệnh đề 2.1 của luận án, nếu $U/C$ và $U/D$ là các phân hoạch trên toàn khối, còn $U/C_x$ và $U/D_x$ là các phân hoạch trên lát cắt tại điểm $x \in id$, thì mỗi lớp tương đương điều kiện $C_i$ và quyết định $D_j$ trên khối chính là giao của các lớp tương đương thành phần tương ứng trên tất cả các lát cắt: $$C_i = \bigcap_{x \in id} C_{x_{p_x}}, \quad D_j = \bigcap_{x \in id} D_{x_{q_x}}$$ Điều này đồng nghĩa với việc hai đối tượng thuộc cùng một lớp tương đương trên khối khi và chỉ khi chúng đồng thời thuộc cùng lớp tương đương trên tất cả các lát cắt của trục $id$.

3. Thuật toán MDLB_VAC xử lý ma trận độ hỗ trợ (Sup) như thế nào khi một thuộc tính bị làm thô hoặc làm mịn?

  • Khi làm thô: Hai lớp tương đương điều kiện (hoặc quyết định) được gộp thành một lớp mới. Theo Định lý 2.1 và Hệ quả 2.1, hai dòng (hoặc hai cột) tương ứng trong ma trận $Sup$ sẽ được cộng dồn giá trị lại với nhau để tạo thành dòng (hoặc cột) mới: $Sup(C_s, D_j) = Sup(C_p, D_j) + Sup(C_q, D_j)$.
  • Khi làm mịn: Một lớp tương đương được tách thành hai lớp mới. Một dòng (hoặc một cột) trong ma trận $Sup$ sẽ tách thành hai dòng (hoặc hai cột). Sau khi tính giá trị $Sup$ cho lớp mới thứ nhất, giá trị cho lớp mới thứ hai được suy ra trực tiếp bằng phép trừ với giá trị cũ: $Sup(C_q, D_j) = Sup(C_s, D_j) - Sup(C_p, D_j)$ mà không cần duyệt lại dữ liệu.

4. Vì sao phương pháp cập nhật gia tăng ma trận Sup (MDLB_OSC2) lại vượt trội hơn phương pháp cập nhật ma trận Acc và Cov (MDLB_OSC1)?

Thuật toán MDLB_OSC1 buộc phải duy trì và tính toán lại đồng thời cả hai ma trận số thực $Acc$ và $Cov$ trên diện rộng mỗi khi có đối tượng thêm/bớt do mẫu số (kích thước lớp) thay đổi. Ngược lại, thuật toán MDLB_OSC2 chỉ cần cập nhật duy nhất một ma trận số nguyên $Sup$. Khi thêm hoặc bớt một đối tượng, chỉ có đúng một phần tử tại tọa độ lớp tương ứng bị thay đổi giá trị ($\pm 1$). Các ma trận $Acc$ và $Cov$ chỉ được tính toán cục bộ khi kiểm tra điều kiện ngưỡng để sinh luật, giúp tiết kiệm bộ nhớ và giảm thiểu thời gian thực thi (được chứng minh qua biểu đồ thời gian chạy Hình 3.15).

5. Ý nghĩa thực tiễn của luật quyết định khai phá trên khối được minh họa qua ví dụ bệnh nhân sốt virut ra sao?

Trên bảng phẳng quan hệ, một luật chỉ cho biết: "Bệnh nhân có triệu chứng sốt độ 3, ho độ 2, sổ mũi độ 1 thì kết luận sốt virut mức 3" tại một thời điểm khám. Trên khối dữ liệu với trục $id = {x, y, z, t}$ đại diện cho 4 ngày nằm viện, một luật quyết định khai phá được có dạng $C_3 \to D_4$, mang ý nghĩa: "Nhóm bệnh nhân có chuỗi triệu chứng biến đổi qua 4 ngày (sốt ngày 1 độ 3, ngày 2 độ 3, ngày 3 độ 2, ngày 4 độ 0...) khi áp dụng phác đồ điều trị 1 thì mức độ bệnh thuyên giảm dần từ ngày 1 đến ngày 4 (mức 3 về mức 0)". Luật này phản ánh được toàn bộ tiến trình đáp ứng điều trị thực tế của bệnh nhân theo thời gian.

Kết luận

Luận án "Khai phá luật quyết định trên mô hình dữ liệu dạng khối" của tác giả Đỗ Thị Lan Anh đã giải quyết hoàn chỉnh bài toán khai phá tri thức dạng luật phân lớp trên cấu trúc dữ liệu khối có trục chỉ số tiến trình. Bằng việc kết hợp chặt chẽ giữa lý thuyết tập thô và mô hình dữ liệu dạng khối, công trình đã xây dựng hệ thống các khái niệm hình thức, chứng minh các tính chất bảo toàn phân hoạch và đề xuất 4 thuật toán khai phá luật (MDLB, MDLB_VAC, MDLB_OSC1, MDLB_OSC2). Các kết quả lý thuyết và thực nghiệm đối sánh đã khẳng định tính ưu việt của phương pháp học gia tăng ma trận độ hỗ trợ ($Sup$) khi dữ liệu biến động về thuộc tính và đối tượng, mở ra hướng ứng dụng thiết thực trong các hệ thống hỗ trợ ra quyết định lâm sàng và phân tích dữ liệu đa chiều theo thời gian.