Luận án tiến sĩ phát triển một số phương pháp rút gọn thuộc tính trong bảng quyế

Tổng quan về luận án

Trong kỷ nguyên bùng nổ thông tin và khoa học dữ liệu lớn (Big Data), việc xử lý các bảng dữ liệu có số lượng chiều thuộc tính khổng lồ nhưng lại tồn tại các giá trị bị khuyết thiếu (missing values) đặt ra thách thức toán học và tin học sâu sắc. Rút gọn thuộc tính (Attribute Reduction hay Feature Selection) đóng vai trò là giai đoạn tiền xử lý then chốt nhằm loại bỏ các thông tin dư thừa, nhiễu loạn mà vẫn bảo toàn năng lực phân loại của hệ thống tri thức. Luận án tiến sĩ toán học chuyên ngành Cơ sở toán học cho tin học (mã số: 9460110) với đề tài "Phát triển một số phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp cận Filter-Wrapper" của Nghiên cứu sinh Nguyễn Bá Quảng, dưới sự hướng dẫn khoa học của PGS. TS Nguyễn Long Giang và TS Ngô Trọng Mại (Viện Khoa học và Công nghệ quân sự, 2021), đại diện cho một công trình nghiên cứu tiên phong, giải quyết toàn diện bài toán tối ưu hóa không gian thuộc tính trên các hệ thông tin không hoàn hảo.

                  ┌────────────────────────────────────────────────────────┐
                  │ Bảng quyết định không đầy đủ (IDS = <U, C ∪ {d}>)       │
                  │ (Dữ liệu lớn, giá trị khuyết thiếu '*')               │
                  └──────────────────────────┬─────────────────────────────┘
                                             │
                       ┌─────────────────────┴─────────────────────┐
                       ▼                                           ▼
         ┌───────────────────────────┐               ┌───────────────────────────┐
         │ Bảng quyết định CỐ ĐỊNH   │               │ Bảng quyết định ĐỘNG      │
         └─────────────┬─────────────┘               └─────────────┬─────────────┘
                       │                                           │
         ┌─────────────▼─────────────┐               ┌─────────────▼─────────────┐
         │ Độ đo Khoảng cách Phủ mới │               │  Công thức Cập nhật       │
         │ trên Quan hệ Dung sai     │               │  Khoảng cách Gia tăng     │
         └─────────────┬─────────────┘               └─────────────┬─────────────┘
                       │                                           │
         ┌─────────────▼─────────────┐               ┌─────────────▼─────────────┐
         │ Thuật toán Filter-Wrapper │               │ 04 Thuật toán Gia tăng    │
         │ IDS_FW_DAR                │               │ IDS_IFW_{AO, DO, AA, DA}  │
         └─────────────┬─────────────┘               └─────────────┬─────────────┘
                       │                                           │
                       └─────────────────────┬─────────────────────┘
                                             ▼
                  ┌────────────────────────────────────────────────────────┐
                  │ HIỆU NĂNG VƯỢT TRỘI TRÊN BENCHMARK UCI                │
                  │ - Cực tiểu hóa số thuộc tính rút gọn                  │
                  │ - Nâng cao độ chính xác phân lớp (Classification Acc)  │
                  │ - Cắt giảm đột phá thời gian tính toán gia tăng       │
                  └────────────────────────────────────────────────────────┘

Khoảng trống nghiên cứu (Research Gap) cốt lõi được luận án xác định xuất phát từ hai hạn chế nền tảng trong y văn quốc tế:

1. Hầu hết các thuật toán rút gọn thuộc tính trên bảng quyết định không đầy đủ (Incomplete Decision Tables - IDS) dựa trên mô hình tập thô dung sai (Tolerance Rough Set Model - TRSM) trước đây như công trình của Kryszkiewicz (1998), Meng và cộng sự (2009), Qian và cộng sự (2011), hay Xie và cộng sự (2018) đều thuần túy vận hành theo tiếp cận Filter. Tiếp cận này chọn thuộc tính độc lập với thuật toán học máy phân lớp, dẫn đến việc tập rút gọn thu được chưa tối ưu về số lượng chiều và chưa cực đại hóa được độ chính xác phân lớp (Classification Accuracy).
2. Khi cơ sở dữ liệu biến động động (Dynamic Datasets) thông qua việc bổ sung/loại bỏ đối tượng hoặc thuộc tính, các thuật toán không gia tăng truyền thống buộc phải tái tính toán toàn cục từ đầu trên toàn bộ bảng dữ liệu $O(|U|^2 \cdot |C|)$, gây bùng nổ chi phí tính toán và tắc nghẽn bộ nhớ. Các thuật toán gia tăng đã công bố như của Shu và cộng sự (2014, 2015), Ma và cộng sự (2016), hay Wang và cộng sự (2019) chỉ dừng lại ở tiếp cận Filter đơn thuần hoặc chỉ xử lý trên bảng quyết định đầy đủ theo lý thuyết tập thô mờ (Fuzzy Rough Sets).

Nhằm khỏa lấp khoảng trống này, luận án tập trung giải quyết 3 câu hỏi nghiên cứu và hệ giả thuyết khoa học:

• Research Question 1 (RQ1): Làm thế nào để thiết lập một không gian metric khoảng cách mới trên các phủ dung sai nhằm phản ánh chính xác mức độ phân biệt của các thuộc tính trong điều kiện dữ liệu khuyết thiếu? $\rightarrow$ Hypothesis 1 (H1): Độ đo khoảng cách mới giữa các phủ sẽ thiết lập được độ quan trọng thuộc tính phi tuyến, đóng vai trò là hàm heuristic hiệu quả cho giai đoạn lọc (Filter).
• Research Question 2 (RQ2): Cơ chế kết hợp Filter-Wrapper nào cho phép vừa giảm thiểu số lượng thuộc tính rút gọn, vừa bảo toàn và nâng cao độ chính xác của các bộ phân lớp học máy? $\rightarrow$ Hypothesis 2 (H2): Chiến lược Filter sinh các tập ứng viên xấp xỉ kết hợp Wrapper thẩm định bằng bộ phân lớp sẽ loại bỏ triệt để các thuộc tính "dư thừa cục bộ" mà phương pháp Filter đơn thuần không thể phát hiện.
• Research Question 3 (RQ3): Làm thế nào để xây dựng các công thức toán học cập nhật gia tăng ma trận dung sai và độ đo khoảng cách khi bảng quyết định biến động theo cả chiều dọc (đối tượng) và chiều ngang (thuộc tính)? $\rightarrow$ Hypothesis 3 (H3): Các định lý cập nhật gia tăng cục bộ trên phần sai khác $\Delta U$ và $\Delta C$ sẽ giảm độ phức tạp thời gian tính toán từ bậc đa thức cao xuống tiệm cận tuyến tính mà không làm suy giảm chất lượng tập rút gọn.

Khung lý thuyết của luận án tích hợp chặt chẽ giữa Lý thuyết tập thô kinh điển (Classical Rough Set Theory - Pawlak, 1982), Mô hình tập thô dung sai (Tolerance Rough Set Model - Kryszkiewicz, 1998), Lý thuyết tính toán hạt (Granular Computing) và Khung lựa chọn đặc trưng lai ghép Filter-Wrapper (Kohavi & John, 1997). Đóng góp đột phá của luận án được định lượng thông qua việc cắt giảm từ 20% đến 50% số lượng thuộc tính so với các thuật toán Filter kinh điển (POS-R, INF-R, NEW-R), đồng thời cải thiện độ chính xác phân lớp trên các tập dữ liệu thực nghiệm chuẩn từ kho dữ liệu UCI Machine Learning Repository (bao gồm Audiology, Soybean-large, Congressional Voting Records, Arrhythmia, Anneal, Advertisements).

Literature Review và Positioning

Lịch sử phát triển của lý thuyết tập thô bắt đầu từ công trình nền tảng của Z. Pawlak (1982, 1991), dựa trên quan hệ tương đương (Equivalence Relation - thỏa mãn tính phản xạ, đối xứng và bắc cầu) để phân hoạch không gian đối tượng $U$ thành các lớp không phân biệt được (Indiscernibility Classes). Tuy nhiên, quan hệ tương đương đòi hỏi thông tin tuyệt đối đầy đủ. Khi áp dụng vào các bảng quyết định không đầy đủ $IDS = \langle U, C \cup {d} \rangle$, nơi tồn tại các giá trị chưa xác định ký hiệu là '*', quan hệ tương đương bị phá vỡ.

Để khắc phục, Kryszkiewicz (1998, 1999) đã mở rộng quan hệ tương đương thành quan hệ dung sai (Tolerance Relation) $SIM(P)$, loại bỏ tính chất bắc cầu: $$(u, v) \in SIM(P) \iff \forall a \in P, ; a(u) = a(v) \lor a(u) = '' \lor a(v) = ''$$ Quan hệ này hình thành một hệ phủ (Covering) $\mathcal{K}(P) = U/SIM(P) = {S_P(u) \mid u \in U}$, trong đó $S_P(u)$ là lớp dung sai chứa đối tượng $u$.

                              ┌────────────────────────────────────────┐
                              │  Lý thuyết Tập thô Pawlak (1982)       │
                              │  - Quan hệ tương đương (Phân hoạch)    │
                              │  - Giả định dữ liệu đầy đủ 100%        │
                              └───────────────────┬────────────────────┘
                                                  │ (Mở rộng quan hệ)
                                                  ▼
                              ┌────────────────────────────────────────┐
                              │  Tập thô Dung sai Kryszkiewicz (1998)  │
                              │  - Quan hệ dung sai SIM(P) (Hệ phủ)    │
                              │  - Xử lý trực tiếp missing value '*'   │
                              └───────────────────┬────────────────────┘
                                                  │
                 ┌────────────────────────────────┴────────────────────────────────┐
                 │                                                                 │
                 ▼                                                                 ▼
┌────────────────────────────────────────┐                       ┌────────────────────────────────────────┐
│  Các phương pháp FILTER truyền thống   │                       │  Khoảng trống nghiên cứu (GAPS)        │
│  - Miền dương: Meng (2009), Hu (2017)  │                       │  1. Filter đơn thuần: Chưa tối ưu hóa  │
│  - Ma trận phân biệt: Ma, Giang (2013) │                       │     kích thước và độ chính xác         │
│  - Entropy thông tin: Dai, Sun (2013)  │                       │  2. Thiếu cơ chế gia tăng động 4 chiều │
│  - Độ không nhất quán: Xie (2018)      │                       │     (Add/Del Objects, Add/Del Attr)    │
└──────────────────┬─────────────────────┘                       └──────────────────┬─────────────────────┘
                   │                                                                │
                   └──────────────────────────────┬─────────────────────────────────┘
                                                  │ (Định vị & Đột phá)
                                                  ▼
                              ┌────────────────────────────────────────┐
                              │  ĐÓNG GÓP ĐỘT PHÁ CỦA LUẬN ÁN          │
                              │  - Độ đo khoảng cách phủ tối ưu        │
                              │  - Kiến trúc lai Filter-Wrapper        │
                              │  - Hệ 04 thuật toán gia tăng toàn diện │
                              │    IDS_FW_DAR & IDS_IFW_{AO,DO,AA,DA}  │
                              └────────────────────────────────────────┘

Trong suốt hai thập kỷ qua, y văn học thuật thế giới hình thành nhiều trường phái rút gọn thuộc tính trên bảng quyết định không đầy đủ theo tiếp cận Filter:

1. Trường phái Miền dương mở rộng (Generalized Positive Region): Meng và cộng sự (2009), Peng và cộng sự (2010), Qian và cộng sự (2011), Hu và cộng sự (2017) định nghĩa tập rút gọn bảo toàn miền dương $POS_C(d)$. Hạn chế của hướng tiếp cận này là miền dương có xu hướng bị co hẹp nghiêm trọng khi tỷ lệ giá trị thiếu tăng cao, khiến việc đánh giá độ quan trọng của thuộc tính bị sai lệch.
2. Trường phái Ma trận phân biệt và Hàm phân biệt (Discernibility Matrix): Xu và cộng sự (2009), Tan và cộng sự (2010), Zou và cộng sự (2012), Vũ Văn Định và Nguyễn Long Giang (2013), Ma và cộng sự (2017) chuyển bài toán rút gọn thành việc tìm tập phủ cực tiểu của ma trận phân biệt. Nhược điểm chí mạng là độ phức tạp không gian lưu trữ ma trận $O(|U|^2)$, không khả thi với dữ liệu quy mô lớn.
3. Trường phái Entropy thông tin mở rộng (Information Entropy): Sun và cộng sự (2012), Dai và cộng sự (2013), Xu và cộng sự (2013), Yue và cộng sự (2015), Tao và cộng sự (2017) sử dụng độ bất định thông tin để định hướng tìm kiếm. Mặc dù có tính tổng quát cao, chi phí tính toán phân bố xác suất có điều kiện trên các lớp dung sai giao nhau là vô cùng đắt đỏ.
4. Trường phái Độ không nhất quán (Inconsistency Degree): Điển hình là nghiên cứu quốc tế của Xie và cộng sự (2018) với thuật toán NEW-R, chứng minh tính vượt trội so với thuật toán POS-R (Meng et al., 2009) và INF-R (Dai et al., 2013). Tuy nhiên, NEW-R vẫn giam mình trong không gian tìm kiếm đơn tầng của Filter.

Về phương diện tính toán gia tăng (Incremental Computing), các nghiên cứu của Shu và cộng sự (2012, 2013, 2014, 2015), Ma và cộng sự (2016), Wang và cộng sự (2019), Zhang và cộng sự (2019) chủ yếu chỉ tập trung vào trường hợp bổ sung hoặc loại bỏ đối tượng đơn lẻ dựa trên ma trận phân biệt hoặc miền dương.

Định vị của luận án: Luận án của Nguyễn Bá Quảng đã định vị chính xác tại giao điểm giữa Mô hình tập thô dung sai, Độ đo khoảng cách metric giữa các hệ phủ, Kiến trúc kết hợp Filter-Wrapper và Tính toán gia tăng đa chiều. Công trình so sánh đối chuẩn trực tiếp với 2 nghiên cứu quốc tế tiêu biểu:

• Nghiên cứu 1: Thuật toán NEW-R của Xie và cộng sự (2018) trên tạp chí International Journal of Approximate Reasoning. Luận án chứng minh tiếp cận Filter-Wrapper của mình vượt qua giới hạn độ chính xác tĩnh của NEW-R nhờ bước đánh giá đóng gói (Wrapper).
• Nghiên cứu 2: Thuật toán gia tăng IARM-I và UARA trong các công trình quốc tế của nhóm tác giả Trung Quốc (Shu et al., 2014, 2015; Jing et al., 2018). Luận án chứng minh hệ thuật toán IDS_IFW_AO và IDS_IFW_AA không những duy trì thời gian thực thi tương đương mà còn tạo ra tập rút gọn có lực lượng nhỏ hơn và độ chính xác phân lớp vượt trội.

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án đã mở rộng và làm sâu sắc thêm nền tảng toán học của Lý thuyết tập thô dung sai thông qua các đóng góp lý thuyết căn bản:

1. Mở rộng lý thuyết không gian Metric trên Hệ phủ dung sai: Luận án mở rộng khái niệm khoảng cách từ không gian phân hoạch tương đương (Pawlak, 1982) sang không gian các hệ phủ dung sai $\mathcal{COVER}(U)$ sinh bởi $U/SIM(P)$. Bằng cách định nghĩa độ đo khoảng cách chuẩn hóa giữa hai hệ phủ $K_P = U/SIM(P)$ và $K_Q = U/SIM(Q)$, luận án chứng minh chặt chẽ các tiên đề metric: tính không âm, tính đối xứng, và bất đẳng thức tam giác suy rộng trên cấu trúc đại số của các lớp dung sai.
2. Hình thức hóa khái niệm Tập rút gọn xấp xỉ ứng viên (Candidate Approximate Reducts): Luận án tái định nghĩa khái niệm tập rút gọn không chỉ là tập thuộc tính tối thiểu bất biến đơn lẻ, mà là một không gian các siêu phẳng con (subspaces) tối ưu cục bộ trong pha Filter, tạo tiền đề toán học vững chắc cho pha Wrapper thực hiện tối ưu hóa đa mục tiêu (Multi-objective Optimization): cực tiểu hóa số chiều $\min |R|$ và cực đại hóa độ chính xác phân lớp $\max \text{Acc}(R)$.
3. Thiết lập hệ định lý Cập nhật gia tăng động (Dynamic Incremental Update Theorems): Luận án chứng minh 4 hệ định lý toán học xác lập mối quan hệ giải tích giữa ma trận dung sai cũ $M(P)$ và ma trận dung sai mới $M'(P)$ khi không gian đối tượng hoặc thuộc tính thay đổi:
   • Định lý bổ sung tập đối tượng $\Delta U$: Xác định biến thiên khoảng cách $\Delta D(P, d)$ dựa trên việc phân rã ma trận khối: $$M'(P) = \begin{pmatrix} M(P) & M_{U,\Delta U}(P) \ M_{\Delta U,U}(P) & M_{\Delta U,\Delta U}(P) \end{pmatrix}$$
   • Định lý loại bỏ tập đối tượng $\Delta U$: Xác định tính triệt tiêu của các phần tử dung sai cục bộ mà không cần duyệt lại toàn bộ tập $U \setminus \Delta U$.
   • Định lý bổ sung tập thuộc tính $\Delta C$: Sự thu hẹp đơn điệu của các lớp dung sai: $S_{P \cup \Delta C}(u) = S_P(u) \cap S_{\Delta C}(u)$, tương ứng với phép nhân Hadamard ma trận dung sai: $M(P \cup \Delta C) = M(P) \odot M(\Delta C)$.
   • Định lý loại bỏ tập thuộc tính $\Delta C$: Sự giãn nở có kiểm soát của hệ phủ dung sai.

       ┌────────────────────────────────────────────────────────────────────────┐
       │                 KIẾN TRÚC FILTER-WRAPPER TỔNG QUÁT                     │
       └───────────────────────────────────┬────────────────────────────────────┘
                                           │
 ┌─────────────────────────────────────────┴─────────────────────────────────────────┐
 │                                                                                   │
 │  GIAI ĐOẠN 1: FILTER (Dựa trên Độ đo Khoảng cách Phủ Dung sai)                   │
 │  ┌─────────────────────────────────────────────────────────────────────────────┐  │
 │  │ 1. Khởi tạo tập rỗng R = ∅                                                  │  │
 │  │ 2. Xây dựng ma trận dung sai M(P) qua quan hệ SIM(P)                        │  │
 │  │ 3. Tính độ đo khoảng cách Dis(P, d) và độ quan trọng Sig(a, R, d)           │  │
 │  │ 4. Chiến lược Heuristic Top-Down: Lần lượt kết nạp a* có Sig cao nhất       │  │
 │  │ 5. Sinh tập danh sách các ứng viên rút gọn xấp xỉ: CAND = {R_1, R_2, ..., R_k}│ │
 │  └──────────────────────────────────────┬──────────────────────────────────────┘  │
 │                                         │                                         │
 └─────────────────────────────────────────┼─────────────────────────────────────────┘
                                           │
 ┌─────────────────────────────────────────┴─────────────────────────────────────────┐
 │                                         ▼                                         │
 │  GIAI ĐOẠN 2: WRAPPER (Thẩm định Đóng gói bằng Bộ phân lớp Học máy)               │
 │  ┌─────────────────────────────────────────────────────────────────────────────┐  │
 │  │ 1. Duyệt qua từng tập con ứng viên R_i ∈ CAND                               │  │
 │  │ 2. Huấn luyện và Đánh giá chéo K-Fold (K=10) trên Bộ phân lớp (SVM/KNN/C4.5)│  │
 │  │ 3. Tính hàm mục tiêu: Score(R_i) = Accuracy(R_i) - λ * (|R_i| / |C|)         │  │
 │  │ 4. Lựa chọn tập rút gọn tối ưu toàn cục R* = argmax Score(R_i)              │  │
 │  └──────────────────────────────────────┬──────────────────────────────────────┘  │
 │                                         │                                         │
 └─────────────────────────────────────────┼─────────────────────────────────────────┘
                                           │
                                           ▼
                 ┌──────────────────────────────────────────────────┐
                 │ TẬP RÚT GỌN TỐI ƯU CUỐI CÙNG (Optimal Reduct R*)  │
                 │ (Cực tiểu số chiều, Cực đại hóa độ chính xác)    │
                 └──────────────────────────────────────────────────┘

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp nhuần nhuyễn 3 trụ cột lý thuyết: Lý thuyết tập thô dung sai (Kryszkiewicz) + Lý thuyết thông tin khoảng cách Metric + Mô hình học máy đóng gói Wrapper (Kohavi & John).

• Pha 1 (Filter Phase - Khám phá nhanh không gian hạt): Sử dụng ma trận dung sai $M(P) = (p_{ij})_{n \times n}$ để biểu diễn quan hệ $SIM(P)$. Khoảng cách giữa hệ phủ $U/SIM(P)$ và phân hoạch quyết định $U/d$ được lượng hóa. Thuộc tính có độ quan trọng cục bộ $\text{Sig}(a, P, d) = \text{Dis}(P, d) - \text{Dis}(P \cup {a}, d)$ lớn nhất sẽ được thêm vào theo chiến lược Heuristic Top-down, tạo ra một danh sách ngắn các tập con thuộc tính xấp xỉ có chất lượng cao $\mathcal{CAND} = {R_1, R_2, \dots, R_k}$.
• Pha 2 (Wrapper Phase - Tối ưu hóa hiệu năng thực thi): Sử dụng các thuật toán phân lớp chuẩn mực (như Support Vector Machine - SVM, $K$-Nearest Neighbors - KNN, C4.5 Decision Tree, Naive Bayes) làm hàm mục tiêu đánh giá trực tiếp trên các tập ứng viên $R_i \in \mathcal{CAND}$. Thuật toán chọn ra tập rút gọn $R^$ thỏa mãn điều kiện: $$R^ = \arg\max_{R_i \in \mathcal{CAND}} \left( \text{Accuracy}_{\text{Classifier}}(R_i) \right) \quad \text{với} \quad |R^*| \le |R_i|$$
• Điều kiện biên (Boundary Conditions): Bảng quyết định $IDS = \langle U, C \cup {d} \rangle$ có miền giá trị quyết định $V_d$ phải xác định và đầy đủ (không chứa missing value trên nhãn quyết định $d$), trong khi tập thuộc tính điều kiện $C$ có thể chứa tỷ lệ giá trị thiếu tự do.

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Luận án tuân thủ nghiêm ngặt quan điểm nhận thức luận thực chứng (Positivism) kết hợp chủ nghĩa duy lý toán học (Mathematical Rationalism). Thiết kế nghiên cứu bao gồm hai trục chính: Chứng minh diễn dịch toán học (Deductive Mathematical Proofs) và Thực nghiệm quy nạp diện rộng (Inductive Empirical Benchmarking).

                    ┌────────────────────────────────────────────────────────┐
                    │               THIẾT KẾ PHƯƠNG PHÁP NGHIÊN CỨU           │
                    └───────────────────────────┬────────────────────────────┘
                                                │
         ┌──────────────────────────────────────┴──────────────────────────────────────┐
         │                                                                            │
         ▼                                                                            ▼
┌──────────────────────────────────────────┐                 ┌──────────────────────────────────────────┐
│  NGHIÊN CỨU TOÁN HỌC LÝ THUYẾT           │                 │  NGHIÊN CỨU THỰC NGHIỆM ĐỐI CHUẨN        │
│  - Thiết lập Hệ tiên đề Metric Phủ       │                 │  - 06 Benchmark Datasets chuẩn từ UCI    │
│  - Xây dựng 06 Thuật toán Heuristic      │                 │  - 05 Bộ phân lớp chuẩn mực (SVM, KNN,   │
│  - Chứng minh 04 Hệ định lý Gia tăng     │                 │    C4.5, Naive Bayes, CART)              │
│  - Phân tích Độ phức tạp O(·)            │                 │  - K-fold Cross Validation (K = 10)      │
└──────────────────────────────────────────┘                 └──────────────────────────────────────────┘

1. Về mặt thuật toán tĩnh: Đề xuất thuật toán IDS_F_DAR (Filter Distance-based Attribute Reduction) và thuật toán lai ghép IDS_FW_DAR (Filter-Wrapper Distance-based Attribute Reduction).
2. Về mặt thuật toán gia tăng: Đề xuất trọn bộ 04 thuật toán thích ứng linh hoạt:
   • IDS_IFW_AO: Gia tăng khi bổ sung tập đối tượng ($\text{Add Objects}: U \leftarrow U \cup \Delta U$).
   • IDS_IFW_DO: Gia tăng khi loại bỏ tập đối tượng ($\text{Delete Objects}: U \leftarrow U \setminus \Delta U$).
   • IDS_IFW_AA: Gia tăng khi bổ sung tập thuộc tính ($\text{Add Attributes}: C \leftarrow C \cup \Delta C$).
   • IDS_IFW_DA: Gia tăng khi loại bỏ tập thuộc tính ($\text{Delete Attributes}: C \leftarrow C \setminus \Delta C$).

Quy trình nghiên cứu rigorous

Quy trình thực nghiệm được thiết kế khép kín và chuẩn hóa theo tiêu chuẩn quốc tế:

┌─────────────────────────┐
│ Dữ liệu UCI thô         │
│ (Incomplete Datasets)   │
└───────────┬─────────────┘
            │
            ▼
┌─────────────────────────┐     Phần cố định (Static Base)
│ Phân tách dữ liệu       ├─────────────────────────────────┐
│ (Data Partitioning)     │                                 │
└───────────┬─────────────┘                                 ▼
            │                                  ┌─────────────────────────┐
            │ Phần biến động (Dynamic Batch)   │ Chạy IDS_FW_DAR         │
            ▼                                  │ (Tạo Reduct gốc R_0)    │
┌─────────────────────────┐                    └────────────┬────────────┘
│ Cập nhật ma trận        │                                 │
│ dung sai gia tăng       │                                 │
└───────────┬─────────────┘                                 │
            │                                               │
            ▼                                               │
┌─────────────────────────┐                                 │
│ Thực thi IDS_IFW_AO/AA  │◄────────────────────────────────┘
│ Cập nhật R_new          │
└───────────┬─────────────┘
            │
            ▼
┌─────────────────────────┐
│ Đánh giá chéo 10-Fold   │
│ (Classification Acc &   │
│ Execution Time)         │
└─────────────────────────┘

• Giao thức thu thập và phân vùng dữ liệu: Dữ liệu từ UCI được chia tách thành phần cơ sở (Base data chiếm 70-80%) và các tập biến động gia tăng $\Delta U$ hoặc $\Delta C$ (chiếm 10-30%) để mô phỏng chính xác luồng dữ liệu biến đổi theo thời gian thực.
• Kiểm định độ tin cậy và giá trị nội/ngoại (Validity & Reliability):
  • Đánh giá chéo $10$-fold Cross-Validation được lặp lại 10 lần độc lập để loại bỏ sai số chọn mẫu ngẫu nhiên.
  • Sử dụng các kiểm định thống kê phi tham số (Non-parametric statistical tests) để khẳng định tính vượt trội có ý nghĩa của thuật toán đề xuất so với các đối thủ cạnh tranh.
  • Độ tin cậy của thuật toán được bảo đảm thông qua tính tất định (determinism) của các công thức giải tích gia tăng.

Data và phân tích

Luận án triển khai thực nghiệm toàn diện trên các tập dữ liệu thực tế nổi tiếng từ UCI Machine Learning Repository với các đặc trưng cấu trúc đa dạng:

| Bộ dữ liệu UCI | Số đối tượng ($|U|$) | Số thuộc tính ($|C|$) | Số lớp quyết định ($|V_d|$) | Tỷ lệ khuyết thiếu (%) | Lĩnh vực ứng dụng | | :--- | :---: | :---: | :---: | :---: | :--- | | Audiology | 226 | 69 | 24 | ~2.0% | Chẩn đoán y tế | | Soybean-large | 307 | 35 | 19 | ~9.5% | Nông nghiệp sinh học | | Congressional Voting | 435 | 16 | 2 | ~5.3% | Khoa học xã hội / Chính sách | | Arrhythmia | 452 | 279 | 16 | ~0.3% | Điện tâm đồ tim mạch | | Anneal | 798 | 38 | 6 | ~65.0% | Luyện kim công nghiệp | | Advertisements | 3279 | 1558 | 2 | ~0.9% | Thị giác máy tính / Web |

• Công cụ và Môi trường thực thi: Toàn bộ thuật toán được cài đặt bằng ngôn ngữ C++ và MATLAB trên hệ thống máy tính cấu hình tiêu chuẩn: Intel Core i7, 16GB RAM, hệ điều hành 64-bit.
• Các kỹ thuật đối chuẩn (Baselines): So sánh trực tiếp với các thuật toán tĩnh POS-R, INF-R, NEW-R, IDS_F_DAR và các thuật toán gia tăng tiên tiến IARM-I, UARA.
• Kiểm tra tính vững chắc (Robustness Checks): Kiểm nghiệm dưới các kịch bản kích thước bước nhảy gia tăng đối tượng $\Delta U \in {10, 20, 50, 100}$ và thuộc tính $\Delta C \in {1, 2, 5, 10}$.

Phát hiện đột phá và implications

Những phát hiện then chốt

Kết quả thực nghiệm của luận án cung cấp các minh chứng định lượng thuyết phục:

  Kích thước tập rút gọn (|R|)             Thời gian thực thi gia tăng (s)
┌─────────────────────────────────┐      ┌─────────────────────────────────┐
│ NEW-R (Filter):     ████████ 14 │      │ Tái tính toán toàn cục: ████ 85s│
│ IDS_F_DAR (Filter): ███████  12 │      │ IDS_IFW_AO (Gia tăng):  █    6s │
│ IDS_FW_DAR (Lai):   ████      7 │      └─────────────────────────────────┘
└─────────────────────────────────┘      (Tốc độ tăng tốc gấp 10 - 15 lần)
(Cắt giảm 50% số chiều dư thừa)

1. Phát hiện 1 (Cực tiểu hóa số lượng thuộc tính vượt trội): Thuật toán IDS_FW_DAR tạo ra tập rút gọn có kích thước nhỏ hơn rõ rệt so với các thuật toán Filter kinh điển. Trên bộ dữ liệu phức tạp Arrhythmia (279 thuộc tính), IDS_FW_DAR rút gọn chỉ còn dưới 15 thuộc tính, trong khi NEW-R và POS-R giữ lại hơn 30 thuộc tính.
2. Phát hiện 2 (Bảo toàn và Cải thiện độ chính xác phân lớp): Dù giảm sâu số lượng thuộc tính, độ chính xác phân loại của IDS_FW_DAR trên bộ phân lớp SVM và KNN tăng từ 1.5% đến 6.8% so với việc sử dụng toàn bộ tập thuộc tính ban đầu $C$, và cao hơn các thuật toán POS-R, INF-R từ 2.0% đến 4.5%. Điều này chứng minh giai đoạn Wrapper đã loại bỏ thành công các thuộc tính nhiễu (noise features) vốn làm suy giảm biên phân cách học máy.
3. Phát hiện 3 (Đột phá về tốc độ tính toán gia tăng): Trong các kịch bản bảng quyết định thay đổi động, các thuật toán gia tăng IDS_IFW_AO và IDS_IFW_AA giảm thời gian thực thi từ 75% đến 92% so với việc thực hiện lại thuật toán IDS_FW_DAR từ đầu. Đồ thị thời gian thực thi cho thấy chi phí gia tăng chỉ tăng tuyến tính nhẹ theo kích thước lô $\Delta U$, trong khi tái tính toán toàn cục tăng vọt theo hàm bậc hai $O(|U|^2)$.
4. Phát hiện 4 (Tính tương đương toán học tuyệt đối): Luận án chứng minh bằng thực nghiệm và lý thuyết rằng tập rút gọn thu được từ thuật toán gia tăng IDS_IFW_AO hoàn toàn trùng khớp với tập rút gọn thu được từ việc tính toán toàn cục IDS_FW_DAR trên tập $U \cup \Delta U$, khẳng định không có sự suy hao chất lượng tri thức trong quá trình cập nhật cục bộ.

Implications đa chiều

• Về mặt Lý thuyết: Công trình hoàn thiện lý thuyết không gian xấp xỉ dung sai, lấp đầy khoảng cách giữa lý thuyết tập thô trừu tượng và các mô hình tối ưu hóa học máy hiện đại. Mở ra cách tiếp cận mới trong việc mô hình hóa sự bất định dữ liệu thông qua hệ metric phủ hạt thông tin.
• Về mặt Phương pháp luận: Cung cấp khung phương pháp luận mẫu mực cho việc thiết kế các thuật toán khai phá dữ liệu dòng (Data Stream Mining) trên các bảng thông tin không hoàn hảo, có khả năng chuyển giao áp dụng cho các cấu trúc dữ liệu phức tạp khác như bảng quyết định mờ (Fuzzy Decision Tables) hay bảng quyết định trực cảm (Intuitionistic Decision Tables).
• Về mặt Thực tiễn và Ứng dụng Công nghiệp:
  • Chẩn đoán y tế tự động: Giải quyết bài toán bệnh án điện tử thiếu triệu chứng xét nghiệm (như dữ liệu viêm gan, tim mạch), giúp hệ thống chuyên gia đưa ra kết luận chẩn đoán nhanh với số lượng xét nghiệm tối thiểu, tiết kiệm chi phí cho bệnh nhân.
  • Tài chính - Ngân hàng: Xử lý hồ sơ tín dụng khách hàng với nhiều trường thông tin bỏ trống, tự động cập nhật hạn mức và đánh giá rủi ro tức thời khi có dữ liệu giao dịch mới bổ sung.
  • Quốc phòng - An ninh: Phân tích dữ liệu trinh sát, nhận dạng mục tiêu quang điện tử trong môi trường tác chiến điện tử bị nhiễu loạn hoặc mất tín hiệu từng phần.

Limitations và Future Research

Mặc dù đạt được những kết quả xuất sắc, luận án cũng thẳng thắn thừa nhận các giới hạn nghiên cứu (Boundary Conditions):

1. Chi phí thời gian của pha Wrapper: Do phải tích hợp việc huấn luyện mô hình học máy (như SVM/KNN) để đánh giá các tập ứng viên, thời gian thực thi của IDS_FW_DAR ở pha thiết lập ban đầu vẫn lớn hơn các thuật toán Filter thuần túy ($T_{\text{Filter-Wrapper}} > T_{\text{Filter}}$). Đây là sự đánh đổi tất yếu (trade-off) để đạt được độ chính xác phân loại tối ưu.
2. Giới hạn về kiểu dữ liệu: Thuật toán hiện tại tập trung xử lý dữ liệu rời rạc hoặc dữ liệu đã qua bước rời rạc hóa (Discretization). Việc xử lý trực tiếp dữ liệu số thực liên tục với giá trị thiếu mà không cần rời rạc hóa vẫn chưa được tích hợp hoàn toàn trong mô hình dung sai này.
3. Cơ chế thiếu dữ liệu: Nghiên cứu giả định các giá trị thiếu thuộc dạng ngẫu nhiên hoàn toàn (Missing Completely at Random - MCAR) hoặc ngẫu nhiên (Missing at Random - MAR), chưa tối ưu hóa riêng cho trường hợp dữ liệu thiếu không ngẫu nhiên (Missing Not at Random - MNAR).

                 ┌────────────────────────────────────────────────────────┐
                 │       CHƯƠNG TRÌNH NGHIÊN CỨU TƯƠNG LAI (10 NĂM)       │
                 └───────────────────────────┬────────────────────────────┘
                                             │
         ┌───────────────────────────────────┼───────────────────────────────────┐
         │                                   │                                   │
         ▼                                   ▼                                   ▼
┌─────────────────────────┐       ┌─────────────────────────┐       ┌─────────────────────────┐
│ HƯỚNG 1: DỮ LIỆU LỚN    │       │ HƯỚNG 2: PHỨC HỢP HÓA   │       │ HƯỚNG 3: TỰ ĐỘNG HÓA    │
│ PHÂN TÁN                │       │ MÔ HÌNH TOÁN            │       │ AUTO-ML & DEEP ROUGH    │
│ Triển khai thuật toán   │       │ Mở rộng sang Tập thô    │       │ Tích hợp trích xuất     │
│ trên Apache Spark /     │       │ Dung sai Mờ trực cảm    │       │ đặc trưng sâu với       │
│ Hadoop MapReduce song   │       │ Đa hạt (Multi-granulation│       │ tầng nơ-ron tập thô    │
│ song hóa ma trận        │       │ Intuitionistic Fuzzy)   │       │ tự thích ứng            │
└─────────────────────────┘       └─────────────────────────┘       └─────────────────────────┘

Chương trình nghiên cứu tiếp nối (Future Research Agenda):

• Phát triển phiên bản thuật toán song song hóa trên nền tảng tính toán phân tán (Apache Spark / GPU CUDA) để xử lý các bảng dữ liệu hàng triệu dòng và hàng chục nghìn cột.
• Kết hợp Lý thuyết tập thô dung sai với Mạng nơ-ron sâu (Deep Rough Neural Networks), đưa ma trận dung sai vào làm tầng lọc trọng số chú ý (Attention mechanism).
• Mở rộng thuật toán gia tăng trên các hệ bảng quyết định đa nhãn (Multi-label Decision Tables).

Tác động và ảnh hưởng

• Ảnh hưởng học thuật (Academic Impact): Công trình đóng góp trực tiếp vào dòng chảy học thuật của cộng đồng Tính toán mềm (Soft Computing) và Hội Tập thô Quốc tế (International Rough Set Society - IRSS). Các bài báo trích xuất từ luận án đã được công bố trên các tạp chí và kỷ yếu hội nghị chuyên ngành uy tín, ước tính tạo ra tiềm năng trích dẫn cao trong các nghiên cứu về xử lý dữ liệu lớn không đầy đủ.
• Chuyển đổi công nghệ công nghiệp (Industry Transformation): Cung cấp lõi thuật toán tối ưu hóa cho các hệ thống phần mềm quản trị dữ liệu (Data Cleaning & Preprocessing Tools), các nền tảng AutoML giúp tinh gọn kích thước mô hình (Model Pruning) trước khi triển khai trên các thiết bị biên (Edge Devices / IoT).
• Ý nghĩa quốc tế: Khẳng định năng lực nghiên cứu cơ bản đỉnh cao của các nhà khoa học Việt Nam trong việc giải quyết các bài toán nền tảng của trí tuệ nhân tạo, đứng ngang hàng với các nhóm nghiên cứu mạnh trên thế giới trong lĩnh vực Rough Sets và Granular Computing.

Đối tượng hưởng lợi

• Nghiên cứu sinh và Giới học giả: Kế thừa khung lý thuyết metric khoảng cách phủ dung sai và phương pháp luận chứng minh gia tăng để phát triển các đề tài mở rộng trên tập thô đa hạt (Multi-granulation Rough Sets) hoặc tập thô mờ lân cận (Neighborhood Fuzzy Rough Sets).
• Kỹ sư Trí tuệ Nhân tạo & R&D Doanh nghiệp: Sử dụng trực tiếp mã nguồn và quy trình thuật toán IDS_FW_DAR cùng hệ thuật toán gia tăng IDS_IFW_AO/AA để tích hợp vào các pipeline xử lý dữ liệu thực tế, giảm thiểu đến 50% chi phí lưu trữ và tăng tốc độ suy diễn mô hình.
• Nhà hoạch định chính sách & Quản lý Y tế, Tài chính: Tiếp cận các giải pháp ra quyết định dựa trên dữ liệu (Evidence-based Decision Making) có độ tin cậy cao, thấu hiểu tường tận nguyên nhân ngay cả trong bối cảnh thu thập dữ liệu bị gián đoạn, khiếm khuyết.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và đã mở rộng lý thuyết nào?

Đóng góp lý thuyết độc đáo nhất là việc thiết lập không gian metric khoảng cách mới trên các hệ phủ dung sai $\mathcal{COVER}(U)$, mở rộng trực tiếp Lý thuyết tập thô dung sai của Kryszkiewicz (1998) và khắc phục nhược điểm của các độ đo truyền thống (như miền dương của Pawlak hay entropy của Shannon). Luận án đã đại số hóa quan hệ dung sai thông qua phép toán trên ma trận dung sai $M(P)$, cho phép tính toán độ quan trọng thuộc tính một cách chính xác mà không phụ thuộc vào tính bắc cầu của quan hệ tương đương.

2. Điểm mới về phương pháp luận nghiên cứu khi so sánh với ít nhất 2 công trình quốc tế?

• So với thuật toán NEW-R của Xie và cộng sự (2018): NEW-R chỉ sử dụng độ đo không nhất quán trong pha Filter đơn lẻ. Luận án đã tích hợp cơ chế đóng gói Wrapper, sử dụng chính xác năng lực phân lớp của các mô hình học máy để tinh lọc tập ứng viên, giúp giảm thêm từ 20-40% số lượng thuộc tính dư thừa mà NEW-R bỏ sót.
• So với thuật toán gia tăng IARM-I và UARA của Shu và cộng sự (2014, 2015): Các nghiên cứu của Shu et al. chỉ giải quyết bài toán gia tăng theo tiếp cận Filter trên miền dương. Luận án đã đề xuất một hệ thống toán học toàn diện hỗ trợ cập nhật gia tăng 4 chiều (bổ sung/xóa đối tượng và thuộc tính) theo tiếp cận lai Filter-Wrapper, đảm bảo tối ưu hóa đồng thời cả thời gian thực thi và độ chính xác phân lớp.

3. Phát hiện bất ngờ nhất (Most surprising finding) có dữ liệu minh chứng?

Phát hiện bất ngờ nhất là hiện tượng nghịch lý số chiều (Dimensionality Paradox) trên tập dữ liệu Arrhythmia (UCI): Khi loại bỏ đến 94.6% số lượng thuộc tính (từ 279 thuộc tính ban đầu xuống chỉ còn 15 thuộc tính trong tập rút gọn của IDS_FW_DAR), độ chính xác phân loại của mô hình không những không suy giảm mà lại tăng thêm 6.8%. Về mặt lý thuyết, điều này chứng minh trong các bảng dữ liệu nhiều chiều khuyết thiếu, phần lớn các thuộc tính không chỉ dư thừa mà còn đóng vai trò là "nhiễu độc hại" (adversarial noise) làm sai lệch không gian phân lớp.

4. Luận án có cung cấp giao thức tái lập nghiên cứu (Replication Protocol) không?

Có. Luận án mô tả chi tiết:

• Toàn bộ giả mã (Pseudocode) chuẩn hóa của 06 thuật toán (IDS_F_DAR, IDS_FW_DAR, IDS_IFW_AO, IDS_IFW_DO, IDS_IFW_AA, IDS_IFW_DA).
• Bảng ma trận dung sai minh họa từng bước trên ví dụ số học tường minh (Bảng 1.1 về quyết định xe hơi gồm 6 đối tượng và 4 thuộc tính).
• Tên gọi chính xác và đường dẫn đến 06 bộ dữ liệu chuẩn từ kho lưu trữ quốc tế UCI Machine Learning Repository.
• Chi tiết tham số môi trường kiểm thử và phân chia tập dữ liệu huấn luyện/kiểm tra $10$-fold Cross-Validation.

5. Lộ trình nghiên cứu 10 năm (10-year Research Agenda) được vạch ra như thế nào?

Lộ trình 10 năm tập trung vào 3 giai đoạn chiến lược:

• Giai đoạn 1 (Năm 1-3): Mở rộng mô hình toán học sang Bảng quyết định dung sai mờ trực cảm đa hạt (Multi-granulation Intuitionistic Fuzzy Tolerance Rough Sets) và bảng quyết định ba chiều (Three-way Decision Tables).
• Giai đoạn 2 (Năm 4-6): Tối ưu hóa kiến trúc thuật toán phân tán trên hệ sinh thái Big Data (Apache Spark GraphX, PyTorch Tensors) nhằm xử lý thời gian thực các luồng dữ liệu IoT/Streaming Data có kích thước Terabyte.
• Giai đoạn 3 (Năm 7-10): Tích hợp sâu lý thuyết tập thô dung sai gia tăng vào mạng nơ-ron học sâu (Deep Rough Neural Networks), xây dựng các mô hình Trí tuệ nhân tạo có thể giải thích được (Explainable AI - XAI) phục vụ an ninh quốc phòng và y tế thông minh.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Bá Quảng đã hoàn thành xuất sắc các mục tiêu nghiên cứu đề ra, xác lập một dấu ấn khoa học quan trọng trong lĩnh vực Cơ sở toán học cho tin học với 6 đóng góp cốt lõi:

1. Xây dựng thành công độ đo khoảng cách mới trên hệ phủ dung sai trong bảng quyết định không đầy đủ, tạo tiền đề toán học vững chắc cho việc định lượng độ quan trọng thuộc tính.
2. Đề xuất thuật toán lai ghép đột phá IDS_FW_DAR theo tiếp cận Filter-Wrapper, khắc phục triệt để hạn chế không tối ưu của các thuật toán Filter kinh điển.
3. Xây dựng trọn bộ hệ thống lý thuyết gia tăng gồm 4 hệ định lý cập nhật khoảng cách khi bảng quyết định biến động theo cả chiều đối tượng và chiều thuộc tính.
4. Hiện thực hóa 04 thuật toán gia tăng ưu việt (IDS_IFW_AO, IDS_IFW_DO, IDS_IFW_AA, IDS_IFW_DA), giúp giảm thiểu tới hơn 80% thời gian tính toán so với các tiếp cận truyền thống.
5. Kiểm chứng thực nghiệm toàn diện trên các bộ dữ liệu chuẩn quốc tế UCI, chứng minh tính vượt trội đồng thời trên cả 3 tiêu chí: Cực tiểu hóa số lượng thuộc tính, Cực đại hóa độ chính xác phân loại và Tối ưu hóa thời gian thực thi.
6. Mở ra các hướng nghiên cứu liên ngành giá trị, kết nối chặt chẽ giữa toán học lý thuyết tập thô trừu tượng với các bài toán thực tiễn của thời đại công nghệ dữ liệu lớn và trí tuệ nhân tạo.