Tổng quan luận án

Trong khai phá dữ liệu và phát hiện tri thức từ các tập dữ liệu quy mô lớn, sự gia tăng nhanh chóng về dung lượng dữ liệu và số lượng thuộc tính đặt ra nhiều thách thức đối với hiệu năng thực thi của các mô hình học máy. Rút gọn thuộc tính (còn gọi là rút gọn chiều hay rút gọn đặc trưng) là bước tiền xử lý dữ liệu cơ bản nhằm loại bỏ các thuộc tính dư thừa, không cần thiết để nâng cao tốc độ tính toán, giảm độ phức tạp mô hình và cải thiện độ chính xác phân lớp.

Trong các ứng dụng thực tế, dữ liệu thu thập thường thiếu giá trị trên miền giá trị của các thuộc tính, tạo thành các bảng quyết định không đầy đủ. Để xử lý trực tiếp bảng quyết định không đầy đủ mà không cần điền giá trị thiếu, mô hình tập thô dung sai đã được phát triển thông qua việc mở rộng quan hệ tương đương thành quan hệ dung sai. Tuy nhiên, các phương pháp rút gọn thuộc tính theo mô hình tập thô dung sai hiện hành chủ yếu áp dụng tiếp cận filter truyền thống, trong đó tập thuộc tính rút gọn chỉ bảo toàn độ đo toán học độc lập với thuật toán học máy, khiến số lượng thuộc tính và độ chính xác phân lớp chưa đạt mức tối ưu. Đồng thời, khi dữ liệu biến động (bổ sung hoặc loại bỏ đối tượng, thuộc tính), các thuật toán tĩnh buộc phải tính toán lại trên toàn bộ bảng quyết định, dẫn đến chi phí thời gian rất lớn.

Luận án tiến sĩ toán học 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", chuyên ngành Cơ sở toán học cho tin học (mã số 9 46 01 10), do nghiên cứu sinh Nguyễn Bá Quảng thực hiện 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 tại Viện Khoa học và Công nghệ quân sự (Hà Nội, 2021), tập trung giải quyết các khoảng trống nghiên cứu trên.

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

Luận án xác định hai mục tiêu nghiên cứu cụ thể:

  1. Đề xuất thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai nhằm giảm thiểu số lượng thuộc tính của tập rút gọn (từ đó giảm độ phức tạp của mô hình) và cải thiện độ chính xác của mô hình phân lớp.
  2. Đề xuất các thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ thay đổi theo tiếp cận tập thô dung sai nhằm giảm thiểu số lượng thuộc tính của tập rút gọn và cải thiện độ chính xác của mô hình phân lớp so với các thuật toán gia tăng khác.

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

  • Đối tượng nghiên cứu: Bảng quyết định không đầy đủ, mô hình tập thô dung sai, các phương pháp rút gọn thuộc tính và các phương pháp gia tăng rút gọn thuộc tính theo tiếp cận tập thô dung sai.
  • Phạm vi nghiên cứu: Các 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 tập thô dung sai trong hai trạng thái: bảng quyết định cố định và bảng quyết định thay đổi (bổ sung/loại bỏ tập đối tượng, bổ sung/loại bỏ tập thuộc tính).

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

Các hướng nghiên cứu nền tảng và liên quan

Lý thuyết tập thô do Pawlak (1982) đề xuất dựa trên quan hệ tương đương để xử lý tính không chắc chắn trong bảng quyết định đầy đủ. Đối với bảng quyết định không đầy đủ, Kryszkiewicz (1998) đã mở rộng quan hệ tương đương thành quan hệ dung sai (có tính phản xạ, đối xứng nhưng không có tính bắc cầu) và xây dựng mô hình tập thô dung sai.

Các công trình nghiên cứu về rút gọn thuộc tính trên bảng quyết định không đầy đủ theo tiếp cận tập thô dung sai đã phát triển theo nhiều nhóm độ đo:

  • Tiếp cận miền dương mở rộng: Peng và cộng sự (2010), Meng và cộng sự (2009 - thuật toán POS-R), Qian và cộng sự (2011), Xu và cộng sự (2013), Hu và cộng sự (2017).
  • Tiếp cận ma trận phân biệt và hàm phân biệt: Zhou và cộng sự (2009), Xu và cộng sự (2009), Tan và cộng sự (2010), Li 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).
  • Tiếp cận entropy thông tin mở rộng: Sun và cộng sự (2012), Dai và cộng sự (2013 - thuật toán INF-R), Xu và cộng sự (2013), Yue và cộng sự (2015), Qian và cộng sự (2015), Tao và cộng sự (2017).
  • Tiếp cận độ đo lượng thông tin và hạt thông tin: Dai và cộng sự (2010), Sai Prasad và cộng sự (2012), Xu và cộng sự (2012, 2019).
  • Tiếp cận độ đo khoảng cách: Long Giang Nguyen và Hung Son Nguyen (2013), Vũ Văn Định và cộng sự (2015).
  • Tiếp cận độ đo không nhất quán và quan hệ khác: Shu và cộng sự (2014), Zhao và cộng sự (2014), Xie và cộng sự (2018 - thuật toán NEW-R).

Đối với bài toán dữ liệu thay đổi, các nghiên cứu về thuật toán gia tăng theo tập thô truyền thống và tập thô mở rộng bao gồm: Shua và cộng sự (2019), Ma và cộng sự (2019), Wei và cộng sự (2018), Yang và cộng sự (2017), Das và cộng sự (2018), Jing và cộng sự (2016, 2017, 2018), Nguyễn Thị Lan Hương và Nguyễn Long Giang (2016), Liang và cộng sự (2014), Chen và cộng sự (2013). Trên mô hình tập thô dung sai, các nghiên cứu gia tăng tiêu biểu gồm: Li và cộng sự (2008), Zhang và cộng sự (2008, 2019), Shu và cộng sự (2012, 2013, 2014, 2015), Chen và cộng sự (2012), Liu và cộng sự (2014), Ma và cộng sự (2016), Luo và cộng sự (2017), Huyen và cộng sự (2018), Yu và cộng sự (2018), Wang và cộng sự (2019), Xie và cộng sự (2018).

Nhóm tiếp cận Các công trình tiêu biểu Đặc điểm chính
Filter trên bảng không đầy đủ cố định POS-R (Meng, 2009), INF-R (Dai, 2013), NEW-R (Xie, 2018), Vũ Văn Định & cs (2013, 2015) Dùng miền dương, entropy, ma trận phân biệt, khoảng cách; độc lập với bộ phân lớp.
Gia tăng Filter trên bảng không đầy đủ Shu & cs (2012-2015), Zhang & cs (2008, 2019), Wang & cs (2019), Xie & cs (2018) Cập nhật tập rút gọn khi thêm/bớt đối tượng hoặc thuộc tính; chưa kết hợp bộ phân lớp.
Filter-Wrapper trên bảng đầy đủ Nhóm nghiên cứu của Nguyễn Long Giang & cs (2016-2020) Áp dụng trên tập thô mờ (fuzzy rough set) cho dữ liệu đầy đủ.
Vị trí của Luận án Nguyễn Bá Quảng (2021) Xây dựng độ đo khoảng cách mới; kết hợp Filter-Wrapper cho bảng không đầy đủ ở cả dạng cố định và gia tăng (thêm/bớt đối tượng, thuộc tính).

Khoảng trống nghiên cứu luận án lựa chọn giải quyết

Hầu hết các thuật toán rút gọn thuộc tính hiện có trên bảng quyết định không đầy đủ đều tuân theo cơ chế filter. Một số nghiên cứu gần đây đã đề xuất mô hình lai filter-wrapper (như công trình của nhóm tác giả hướng dẫn thực hiện trên bảng quyết định đầy đủ với lý thuyết tập thô mờ). Tuy nhiên, chưa có công trình nào phát triển mô hình kết hợp filter-wrapper sử dụng độ đo khoảng cách cho bảng quyết định không đầy đủ theo mô hình tập thô dung sai, cũng như chưa có các thuật toán gia tăng filter-wrapper giải quyết đầy đủ 4 kịch bản biến động dữ liệu: bổ sung đối tượng, loại bỏ đối tượng, bổ sung thuộc tính và loại bỏ thuộc tính.

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

Cơ sở lý thuyết

  1. Mô hình hệ thông tin và tập thô truyền thống: Hệ thông tin $IS = \langle U, A \rangle$, 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. Quan hệ không phân biệt $IND(P)$ trên $P \subseteq A$ xác định phân hoạch $U/P$. Với tập $X \subseteq U$, xấp xỉ dưới $BX$ và xấp xỉ trên $\overline{B}X$ được xác định qua các lớp tương đương.
  2. Mô hình tập thô dung sai trên hệ thông tin không đầy đủ: Hệ thông tin không đầy đủ $IIS = \langle U, A \rangle$ chứa giá trị thiếu ký hiệu là '*'. Quan hệ dung sai $SIM(P)$ được định nghĩa bởi: $$SIM(P) = {(u, v) \in U \times U \mid \forall a \in P, a(u) = a(v) \lor a(u) = '' \lor a(v) = ''}$$ Lớp dung sai của $u$ ký hiệu là $S_P(u) = {v \in U \mid (u, v) \in SIM(P)}$. Tập các lớp dung sai tạo thành một phủ $U/SIM(P)$ trên $U$.
  3. Bảng quyết định không đầy đủ ($IDS$): $IDS = \langle U, C \cup {d} \rangle$, với $C$ là tập thuộc tính điều kiện chứa giá trị thiếu và $d$ là thuộc tính quyết định (không chứa giá trị thiếu). Hàm quyết định suy rộng $\partial_P(u) = {d(v) \mid v \in S_P(u)}$.
  4. Ma trận dung sai: Biểu diễn quan hệ dung sai $SIM(P)$ dưới dạng ma trận $M(P) = (p_{ij}){n \times n}$, trong đó $p{ij} = 1$ nếu $u_j \in S_P(u_i)$ và $p_{ij} = 0$ nếu ngược lại.

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

  • Phương pháp nghiên cứu lý thuyết:
    • Phân tích toán học các độ đo khoảng cách giữa các tập hợp và giữa các phủ sinh bởi các tập thuộc tính.
    • Thiết lập các định lý, mệnh đề và chứng minh bất đẳng thức tam giác cho độ đo khoảng cách đề xuất.
    • Xây dựng các công thức toán học gia tăng để tính toán và cập nhật khoảng cách ma trận khi bảng quyết định thay đổi cấu trúc mà không phải quét lại toàn bộ dữ liệu.
  • Phương pháp nghiên cứu thực nghiệm:
    • Cài đặt các thuật toán đề xuất bằng ngôn ngữ lập trình.
    • Thực nghiệm kiểm chứng trên các bộ dữ liệu chuẩn lấy từ kho dữ liệu máy học UCI (UC Irvine Machine Learning Repository): Audiology, Soybean-large, Congressional Voting Records, Arrhythmia, Anneal, Advertisements...
    • Đánh giá định lượng dựa trên ba tiêu chí: thời gian thực thi (giây), số lượng thuộc tính của tập rút gọn, và độ chính xác phân lớp (sử dụng các bộ phân lớp học máy tiêu chuẩn).
    • So sánh đối chuẩn 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 (IARM-I, UARA).

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

Chương 1: Tổng quan về rút gọn thuộc tính theo tiếp cận tập thô dung sai

Chương 1 hệ thống hóa các kiến thức nền tảng toán học và tổng quan các hướng nghiên cứu hiện có:

  • Trình bày chi tiết lý thuyết tập thô cổ điển của Pawlak và mô hình mở rộng tập thô dung sai của Kryszkiewicz trên hệ thông tin không đầy đủ. Định nghĩa các khái niệm xấp xỉ dưới, xấp xỉ trên, miền biên, miền dương và ma trận dung sai $M(P)$.
  • Minh họa cấu trúc bảng quyết định không đầy đủ thông qua ví dụ gồm 6 đối tượng xe hơi ($u_1, \dots, u_6$) với 4 thuộc tính điều kiện $c_1$ (Đơn giá), $c_2$ (Km đã đi), $c_3$ (Kích thước), $c_4$ (Tốc độ) và thuộc tính quyết định $d$ (Gia tốc), tính toán cụ thể các lớp dung sai $S_C(u_i)$, tập xấp xỉ và hàm quyết định suy rộng $\partial_C(u_i)$ để chứng minh tính không nhất quán của bảng.
  • Phân tích quy trình rút gọn thuộc tính tổng quát gồm 4 bước: tạo lập tập con, đánh giá tập con, kiểm tra điều kiện dừng và kiểm chứng kết quả.
  • So sánh hai trường phái: filter (tính toán nhanh, dựa trên độ quan trọng của thuộc tính nhưng độc lập với mô hình phân lớp) và wrapper (dùng thuật toán phân lớp để đánh giá tập con thuộc tính, độ chính xác cao nhưng chi phí tính toán lớn).
  • Tổng hợp và phân loại hệ thống các công trình nghiên cứu về rút gọn thuộc tính tĩnh và gia tăng theo tập thô dung sai (tổng hợp qua các Bảng 1.2, 1.3, 1.4 trong luận án), chỉ rõ hạn chế của các phương pháp thuần filter và xác lập hai hướng nghiên cứu trọng tâm của luận án.

Chương 2: Thuật toán filter-wrapper tìm tập rút gọn của bảng quyết định không đầy đủ

Chương 2 tập trung vào việc xây dựng độ đo khoảng cách mới và thiết kế các thuật toán rút gọn thuộc tính cho bảng quyết định không đầy đủ cố định:

  • Xây dựng độ đo khoảng cách:
    • Khoảng cách giữa hai tập con $A, B \subseteq U$: $$d(A, B) = |A \cup B| - |A \cap B|$$ Luận án chứng minh $d(A, B)$ thỏa mãn đầy đủ các tiên đề khoảng cách (tính không âm, tính đối xứng và bất đẳng thức tam giác) thông qua biểu diễn véc-tơ đặc trưng nhị phân.
    • Khoảng cách giữa hai tập thuộc tính $P, Q \subseteq C$ (hay giữa hai phủ $U/SIM(P)$ và $U/SIM(Q)$): $$D(P, Q) = \frac{1}{n^2} \sum_{i=1}^n (|S_P(u_i) \cup S_Q(u_i)| - |S_P(u_i) \cap S_Q(u_i)|) = \frac{1}{n^2} \sum_{i=1}^n d(S_P(u_i), S_Q(u_i))$$ Chứng minh $0 \le D(P, Q) \le 1 - \frac{1}{n}$.
    • Khoảng cách giữa tập thuộc tính điều kiện $C$ và $C \cup {d}$ thông qua ma trận dung sai $M(C) = (c_{ij}){n \times n}$ và $M(d) = (d{ij}){n \times n}$: $$D(C, C \cup {d}) = \frac{1}{n^2} \sum{i=1}^n \sum_{j=1}^n (c_{ij} - c_{ij} \cdot d_{ij})$$
    • Chứng minh tính chất đơn điệu: Nếu $B \subseteq C$ thì $D(B, B \cup {d}) \ge D(C, C \cup {d})$.
  • Đề xuất các thuật toán:
    • IDS_F_DAR: Thuật toán rút gọn thuộc tính theo tiếp cận filter sử dụng độ đo khoảng cách.
    • IDS_FW_DAR: Thuật toán rút gọn thuộc tính theo tiếp cận kết hợp filter-wrapper. Giai đoạn filter sử dụng độ đo khoảng cách để tìm tập các ứng viên rút gọn xấp xỉ; giai đoạn wrapper áp dụng bộ phân lớp để đánh giá và chọn ra tập rút gọn có độ chính xác phân lớp cao nhất với số lượng thuộc tính tối thiểu.
  • Kết quả thực nghiệm: Đánh giá trên các tập dữ liệu từ kho UCI cho thấy thuật toán IDS_FW_DAR giảm đáng kể số lượng thuộc tính so với các thuật toán thuần filter (POS-R, INF-R, NEW-R, IDS_F_DAR), đồng thời duy trì và nâng cao độ chính xác phân lớp.

Chương 3: Các thuật toán gia tăng filter-wrapper tìm tập rút gọn của bảng quyết định thay đổi

Chương 3 giải quyết bài toán rút gọn thuộc tính khi bảng quyết định không đầy đủ có sự biến động dữ liệu:

  • Biến động theo tập đối tượng:
    • Thiết lập công thức toán học cập nhật khoảng cách khi bổ sung tập đối tượng $U^$ vào $U$ ($IDS_1 = \langle U \cup U^, C \cup {d} \rangle$) và khi loại bỏ tập đối tượng $U^$ khỏi $U$ ($IDS_2 = \langle U \setminus U^, C \cup {d} \rangle$).
    • Đề xuất thuật toán gia tăng IDS_IFW_AO (khi bổ sung đối tượng) và IDS_IFW_DO (khi loại bỏ đối tượng).
    • Thực nghiệm so sánh giữa IDS_IFW_AO với thuật toán tĩnh IDS_FW_DAR và thuật toán gia tăng IARM-I trên các bộ dữ liệu UCI (như Audiology, Soybean-large, Congressional Voting Records, Arrhythmia, Anneal, Advertisements) chứng minh IDS_IFW_AO giảm thiểu thời gian tính toán so với tính toán lại từ đầu và cho số thuộc tính ít hơn với độ chính xác cao hơn IARM-I.
  • Biến động theo tập thuộc tính:
    • Thiết lập công thức cập nhật khoảng cách khi bổ sung tập thuộc tính điều kiện $C^$ vào $C$ ($IDS_1 = \langle U, (C \cup C^) \cup {d} \rangle$) và khi loại bỏ tập thuộc tính $C^$ khỏi $C$ ($IDS_2 = \langle U, (C \setminus C^) \cup {d} \rangle$).
    • Đề xuất thuật toán gia tăng IDS_IFW_AA (khi bổ sung thuộc tính) và IDS_IFW_DA (khi loại bỏ thuộc tính).
    • Kết quả thực nghiệm đối sánh giữa IDS_IFW_AA và thuật toán UARA chứng minh tính ưu việt về thời gian chạy, số lượng thuộc tính rút gọn và độ chính xác phân lớp.

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

Đóng góp về mặt khoa học lý thuyết

  1. Xây dựng độ đo khoảng cách mới: Đề xuất độ đo khoảng cách giữa hai tập hợp và độ đo khoảng cách giữa hai tập thuộc tính (hai phủ) trong bảng quyết định không đầy đủ. Chứng minh các tính chất toán học, bất đẳng thức tam giác và biểu diễn tường minh khoảng cách thông qua các phần tử của ma trận dung sai.
  2. Phát triển thuật toán filter-wrapper trên bảng cố định: Đề xuất thuật toán IDS_F_DAR (theo tiếp cận filter) và thuật toán IDS_FW_DAR (kết hợp filter-wrapper) dựa trên độ đo khoảng cách mới cho bảng quyết định không đầy đủ, giải quyết hạn chế của các phương pháp filter truyền thống.
  3. Thiết lập lý thuyết tính toán gia tăng: Xây dựng hệ thống công thức toán học cập nhật khoảng cách khi bảng quyết định biến động theo 4 trường hợp: bổ sung đối tượng, loại bỏ đối tượng, bổ sung thuộc tính, loại bỏ thuộc tính.
  4. Phát triển 04 thuật toán gia tăng filter-wrapper:
    • IDS_IFW_AO: Thuật toán gia tăng filter-wrapper khi bổ sung tập đối tượng.
    • IDS_IFW_DO: Thuật toán gia tăng filter-wrapper khi loại bỏ tập đối tượng.
    • IDS_IFW_AA: Thuật toán gia tăng filter-wrapper khi bổ sung tập thuộc tính.
    • IDS_IFW_DA: Thuật toán gia tăng filter-wrapper khi loại bỏ tập thuộc tính.

Đóng góp về mặt thực tiễn

  • Các thuật toán đề xuất cung cấp giải pháp tiền xử lý dữ liệu cho các hệ thống cơ sở dữ liệu có giá trị thiếu, giúp giảm thiểu không gian lưu trữ và tăng tốc độ xử lý của mô hình học máy.
  • Kết quả nghiên cứu có thể ứng dụng trong các bài toán thực tế chứa dữ liệu không đầy đủ và thường xuyên cập nhật, tiêu biểu như hệ thống hỗ trợ chẩn đoán y tế (dữ liệu bệnh án thiếu triệu chứng) và phân tích dữ liệu tài chính - ngân hàng.

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

  • Hạn chế: Luận án giới hạn phạm vi nghiên cứu trên bảng quyết định không đầy đủ với một thuộc tính quyết định duy nhất ($d$) và giá trị thuộc tính quyết định là đầy đủ (không chứa giá trị '*'). Mô hình chưa khảo sát các bảng quyết định có nhiều thuộc tính quyết định (multi-label) hoặc trường hợp giá trị quyết định bị thiếu.
  • Hướng nghiên cứu tiếp:
    • Nghiên cứu mở rộng phương pháp filter-wrapper sử dụng độ đo khoảng cách cho bảng quyết định không đầy đủ trong trường hợp tập đối tượng hoặc tập thuộc tính thay đổi giá trị.
    • Phát triển các thuật toán rút gọn thuộc tính gia tăng cho các bảng quyết định đa quyết định (bảng quyết định nhiều nhãn) hoặc dữ liệu luồng (data streams).

Giá trị tham khảo

  • Đối với nghiên cứu sinh và học viên cao học: Luận án là tài liệu tham khảo chuyên sâu về lý thuyết tập thô, mô hình tập thô dung sai, các kỹ thuật xây dựng độ đo toán học và phương pháp thiết kế thuật toán gia tăng trong khai phá dữ liệu.
  • Đối với giảng viên và nhà nghiên cứu ngành Khoa học máy tính, Toán tin: Cung cấp khung lý thuyết hoàn chỉnh về tiếp cận lai filter-wrapper và cách thức biểu diễn ma trận dung sai để tối ưu hóa thời gian tính toán.
  • Đối với kỹ sư phân tích dữ liệu: Cung cấp các thuật toán cụ thể có thể áp dụng trực tiếp vào bước tiền xử lý cho các hệ thống dữ liệu thực tế có kích thước lớn và thiếu giá trị.

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

1. Sự khác biệt giữa quan hệ tương đương trong tập thô truyền thống và quan hệ dung sai trong mô hình tập thô dung sai là gì?

Quan hệ tương đương trong tập thô truyền thống (áp dụng cho bảng dữ liệu đầy đủ) thỏa mãn ba tính chất: phản xạ, đối xứng và bắc cầu, từ đó tạo ra một phân hoạch trên tập đối tượng $U$. Trong khi đó, quan hệ dung sai $SIM(P)$ trong bảng quyết định không đầy đủ chỉ thỏa mãn tính phản xạ và đối xứng, không có tính bắc cầu (do đối tượng có giá trị thiếu '*' có thể tương tự với nhiều giá trị khác nhau nhưng các giá trị đó không tương tự nhau). Do đó, quan hệ dung sai tạo ra một phủ (covering) gồm các lớp dung sai có thể giao nhau thay vì một phân hoạch rời rạc.

2. Tại sao tiếp cận kết hợp filter-wrapper lại tối ưu hơn tiếp cận filter truyền thống trong rút gọn thuộc tính?

Tiếp cận filter truyền thống chỉ chọn thuộc tính dựa trên việc bảo toàn một độ đo toán học độc lập (như miền dương, entropy hay khoảng cách) và chỉ đánh giá độ chính xác sau khi đã chọn xong, dẫn đến tập rút gọn có thể chứa thuộc tính dư thừa đối với thuật toán phân lớp. Tiếp cận kết hợp filter-wrapper chia làm hai giai đoạn: giai đoạn filter lọc ra các tập ứng viên tiềm năng (tập rút gọn xấp xỉ), sau đó giai đoạn wrapper đưa trực tiếp bộ phân lớp vào để đánh giá độ chính xác của từng ứng viên, từ đó chọn được tập thuộc tính có số lượng nhỏ nhất nhưng đạt độ chính xác phân lớp cao nhất.

3. Nguyên lý giảm thời gian tính toán của các thuật toán gia tăng (như IDS_IFW_AO, IDS_IFW_AA) là gì?

Các thuật toán gia tăng không tính toán lại toàn bộ ma trận dung sai và độ đo khoảng cách trên toàn bộ bảng dữ liệu mới. Thay vào đó, thuật toán sử dụng các công thức cập nhật toán học được chứng minh trong luận án để chỉ tính toán phần biến thiên khoảng cách sinh ra bởi tập đối tượng bổ sung/loại bỏ ($U^$) hoặc tập thuộc tính bổ sung/loại bỏ ($C^$), kế thừa kết quả tính toán trước đó để cập nhật tập rút gọn.

4. Thuật toán IDS_FW_DAR đã được so sánh với các thuật toán nào và trên nguồn dữ liệu nào?

Thuật toán IDS_FW_DAR được cài đặt và thực nghiệm đối sánh với các thuật toán filter tiêu biểu gồm POS-R (dùng miền dương), INF-R (dùng entropy thông tin), NEW-R (dùng độ không nhất quán) và IDS_F_DAR (thuật toán filter dùng khoảng cách đề xuất). Quá trình thử nghiệm thực hiện trên các bộ dữ liệu mẫu chuẩn từ kho dữ liệu máy học UCI như: Audiology, Soybean-large, Congressional Voting Records, Arrhythmia, Anneal, Advertisements...

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Bá Quảng đã giải quyết bài toán rút gọn thuộc tính trong bảng quyết định không đầy đủ thông qua việc đề xuất độ đo khoảng cách mới dựa trên ma trận dung sai và áp dụng hướng tiếp cận kết hợp filter-wrapper. Công trình đã phát triển thành công thuật toán tĩnh IDS_FW_DAR cùng hệ thống 04 thuật toán gia tăng (IDS_IFW_AO, IDS_IFW_DO, IDS_IFW_AA, IDS_IFW_DA) tương ứng với các kịch bản biến động về đối tượng và thuộc tính. Các kết quả thực nghiệm trên kho dữ liệu chuẩn UCI đã chứng minh tính hiệu quả của các thuật toán đề xuất trong việc giảm số lượng thuộc tính, nâng cao độ chính xác phân lớp và tiết kiệm thời gian tính toán khi xử lý dữ liệu biến động.