Tổng quan luận án

Trong bối cảnh phát triển của công nghệ thông tin và khoa học dữ liệu, các cơ sở dữ liệu thực tế không ngừng gia tăng về dung lượng cũng như số lượng chiều thuộc tính. Hiện tượng bùng nổ số lượng thuộc tính gây suy giảm hiệu năng và gia tăng độ phức tạp tính toán đối với các thuật toán khai phá dữ liệu và học máy. Rút gọn thuộc tính (Attribute Reduction hay Feature Selection) đóng vai trò là bước tiền xử lý dữ liệu nhằm loại bỏ các thuộc tính dư thừa, không liên quan, qua đó bảo toàn năng lực phân lớp và nâng cao chất lượng mô hình.

Khoảng trống nghiên cứu được tác giả xác định xuất phát từ hai hạn chế cốt lõi của các công trình hiện hữu:

  1. Các phương pháp rút gọn thuộc tính theo lý thuyết tập thô truyền thống và tập thô dung sai chủ yếu thực hiện trên các bảng quyết định đã qua bước rời rạc hóa dữ liệu. Quá trình rời rạc hóa làm mất mát thông tin về sự khác biệt ban đầu giữa các đối tượng trong dữ liệu gốc, từ đó làm suy giảm độ chính xác phân lớp. Ngược lại, các phương pháp tiếp cận tập thô mờ xử lý trực tiếp trên bảng quyết định gốc phần lớn đều được xây dựng theo hướng tiếp cận lọc (filter). Tập rút gọn tìm được theo hướng tiếp cận lọc chỉ thỏa mãn điều kiện bảo toàn độ đo lý thuyết mà chưa được tối ưu về số lượng thuộc tính và độ chính xác phân lớp của mô hình học máy.
  2. Trong thực tế, các bảng quyết định thường có kích thước lớn và biến động liên tục (bổ sung hoặc loại bỏ đối tượng). Các thuật toán không gia tăng truyền thống buộc phải tính toán lại tập rút gọn trên toàn bộ bảng dữ liệu sau mỗi lần biến động, dẫn đến chi phí thời gian tính toán rất lớn. Trong khi đó, các thuật toán gia tăng theo tiếp cận tập thô mờ đã công bố vẫn chủ yếu dựa trên tiếp cận lọc thuần túy và chưa giải quyết trường hợp loại bỏ tập đối tượng.

Mục tiêu nghiên cứu của luận án được phân định thành hai nhiệm vụ cụ thể:

  1. Nghiên cứu các thuật toán lai ghép lọc - đóng gói (filter-wrapper) tìm tập rút gọn sử dụng độ đo khoảng cách mờ cải tiến và các độ đo khác nhằm giảm thiểu số lượng thuộc tính của tập rút gọn (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. Nghiên cứu 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 sử dụng độ đo khoảng cách mờ nhằm giảm thiểu thời gian thực hiện so với các thuật toán không gia tăng, đồng thời giảm thiểu số lượng thuộc tính tập rút gọn và cải thiện độ chính xác phân lớp.

Đối tượng và phạm vi nghiên cứu của luận án:

  • Đối tượng nghiên cứu: 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ô mờ.
  • Phạm vi nghiên cứu: Bảng quyết định gốc có miền giá trị số và phân loại trong hệ thông tin; các bài toán tìm tập rút gọn tĩnh và bài toán cập nhật gia tăng khi có sự biến động (bổ sung, loại bỏ) của tập đối tượng. Kiểm chứng thực nghiệm được thực hiện trên các bộ dữ liệu chuẩn lấy từ kho dữ liệu UCI (UCI Machine Learning Repository).

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

Tổng quan tài liệu trong luận án điểm lại chi tiết các mốc phát triển lý thuyết và các nhánh nghiên cứu liên quan đến rút gọn thuộc tính:

Hướng tiếp cận nghiên cứu Các tác giả, công trình và luận án tiêu biểu Nội dung và đặc điểm chính
Lý thuyết tập thô và tập thô dung sai Z. Pawlak (1982) [101], Kryszkiewicz (1998) [62], các luận án tiến sĩ [4, 5, 6, 7, 11, 13] Đặt nền tảng xấp xỉ tập hợp dựa trên quan hệ tương đương hoặc dung sai; nghiên cứu các độ đo miền dương, ma trận phân biệt, entropy, metric theo tiếp cận filter trên dữ liệu rời rạc.
Rút gọn thuộc tính trên bảng quyết định mờ Dubois và Prade (1990, 1992) [22, 23], R. Shen và cộng sự [76, 77, 78, 79], R. B. Bhatt và cộng sự [82], R. Xu và cộng sự [40, 41] Đề xuất mô hình tập thô mờ; xây dựng thuật toán Fuzzy-Rough QUICKREDUCT và entropy Shannon mờ trên bảng quyết định mờ (giá trị là tập mờ). Độ phức tạp tính toán phân hoạch mờ ở trường hợp tổng quát là hàm mũ.
Rút gọn thuộc tính trực tiếp trên bảng quyết định gốc theo miền dương mờ Hu và cộng sự [72], Jensen và cộng sự [80], Qian và cộng sự [92], nhóm tác giả [2] Xây dựng xấp xỉ mờ, miền dương mờ ngưỡng $k$ (thuật toán FAR-VPFRS), thuật toán FA_FPR nhằm xử lý trực tiếp dữ liệu số và giảm thời gian thực thi.
Rút gọn thuộc tính sử dụng ma trận phân biệt mờ Tsang và cộng sự [34, 42], Chen và cộng sự [29, 30], He và cộng sự [69] Mở rộng ma trận phân biệt và hàm phân biệt mờ, mô hình tập thô mở rộng TL, thuật toán heuristic SPS và FRSTL tìm tập rút gọn.
Rút gọn thuộc tính sử dụng entropy mờ Hu và cộng sự [70, 71, 74, 75], Dai và cộng sự [45], Zhang và cộng sự [91], Yu và cộng sự [33], Zhao và cộng sự [55] Xây dựng entropy mờ, $\alpha$-entropy mờ khắc phục tính phản đơn điệu, độ đo Fuzzy Gain Ratio (thuật toán GAIN_RATIO_AS_FRS), thông tin tương hỗ mờ (FMIL), entropy kết hợp mờ (EMIC).
Rút gọn thuộc tính sử dụng khoảng cách mờ Nguyễn Long Giang và cộng sự [3, 8, 18], kế thừa từ [9, 10, 12, 24, 25, 57, 58, 65] và [48] Xây dựng độ đo khoảng cách Jaccard mờ, khoảng cách phân hoạch mờ ứng dụng trực tiếp trên bảng quyết định gốc.
Các mô hình tập thô mờ mở rộng khác Li và cộng sự [100], Dai và cộng sự [46, 47], Tiwari và cộng sự [14], Sheeja và cộng sự [85], Zhang và cộng sự [90], Wang và cộng sự [21, 59], Arunkumar và cộng sự [19], Tsang và cộng sự [35], Maji và cộng sự [68] Mở rộng tập thô mờ trực giác, tập thô mờ dựa trên độ phân kỳ, quan hệ mờ tham số $\theta$, phương pháp kết hợp MRMS, thuật toán RMDPS và WRMDPS.
Thuật toán gia tăng trong tập thô truyền thống và dung sai Guan [56], Liu [102], Hu và cộng sự [36, 37], Yang và cộng sự [96], Zhang và cộng sự [20], Chen và cộng sự [28], Li và cộng sự [66], Liang và cộng sự [49], Shu và cộng sự [86, 87, 88], Jing và cộng sự [95], Wang và cộng sự [38, 39], Liu và cộng sự [31], Wei và cộng sự [89], [24, 65] Cập nhật gia tăng ma trận phân biệt, miền dương, entropy khi bổ sung/loại bỏ đối tượng hoặc thuộc tính.
Thuật toán gia tăng theo tiếp cận tập thô mờ Zeng và cộng sự [15, 16], Yang và cộng sự [98, 99], Liu và cộng sự [97] Đề xuất các thuật toán FRSA-IFS-HIS-AA/AD, IUAFRS-VCAV/VDAV, IARM, V-FS-FRS-1/2, FIAR dựa trên tính toán gia tăng quan hệ mờ, quan hệ phân biệt và độ phụ thuộc mờ.

Khoảng trống nghiên cứu được luận án tập trung giải quyết gồm:

  • Khắc phục sự thiếu tối ưu về kích thước tập thuộc tính và độ chính xác phân lớp của các phương pháp filter truyền thống bằng khung tiếp cận lai ghép filter-wrapper.
  • Xây dựng công thức khoảng cách mờ có cấu trúc tính toán tối giản và hiệu quả hơn so với các công thức khoảng cách mờ trước đây.
  • Phát triển các thuật toán gia tăng filter-wrapper xử lý biến động tập đối tượng, bao gồm cả chiều bổ sung và chiều loại bỏ tập đối tượng trong mô hình tập thô mờ.

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

Khung lý thuyết và các khái niệm cơ bản

Luận án sử dụng nền tảng lý thuyết hệ thông tin và tập thô mờ với các cấu trúc toán học:

  • Hệ thông tin và bảng quyết định: Hệ thông tin được định nghĩa là cặp $IS = (U, A)$, trong đó $U = {x_1, x_2, \dots, x_n}$ là tập hữu hạn các đối tượng, $A$ là tập thuộc tính. Bảng quyết định có dạng $DS = (U, C \cup D)$ với $C$ là tập thuộc tính điều kiện, $D$ là tập thuộc tính quyết định ($C \cap D = \emptyset$).
  • Quan hệ tương đương mờ: Quan hệ $R$ xác định trên miền giá trị thuộc tính thỏa mãn ba tiên đề: phản xạ ($R(x, x) = 1$), đối xứng ($R(x, y) = R(y, x)$), và bắc cầu max-min ($R(x, z) \ge \min(R(x, y), R(y, z))$). Trên thuộc tính số $a \in C$, quan hệ mờ thường dùng là: $$R_a(x_i, x_j) = \begin{cases} 1 - 4 \times \frac{|a(x_i) - a(x_j)|}{a_{\max} - a_{\min}}, & \text{nếu } \frac{|a(x_i) - a(x_j)|}{a_{\max} - a_{\min}} \le 0.25 \ 0, & \text{trường hợp còn lại} \end{cases}$$ Trên thuộc tính định danh hoặc nhị phân, $R_a(x_i, x_j) = 1$ nếu $a(x_i) = a(x_j)$ và bằng $0$ nếu khác nhau.
  • Ma trận tương đương mờ và Phân hoạch mờ: Ma trận tương đương mờ của quan hệ $R_P$ trên tập thuộc tính $P \subseteq C$ là $M(R_P) = (p_{ij}){n \times n}$ với $p{ij} = R_P(x_i, x_j) = \min_{a \in P} R_a(x_i, x_j)$. Phân hoạch mờ $\tilde{U}/R_P = {[x_1]{R_P}, [x_2]{R_P}, \dots, [x_n]{R_P}}$ gồm các lớp tương đương mờ $[x_i]{R_P} = p_{i1}/x_1 + p_{i2}/x_2 + \dots + p_{in}/x_n$ với lực lượng $|[x_i]{R_P}| = \sum{j=1}^n p_{ij}$.
  • Tập xấp xỉ mờ, Miền dương mờ và Độ phụ thuộc mờ: Xấp xỉ dưới mờ $\underline{R_P}X$ và xấp xỉ trên mờ $\overline{R_P}X$ của tập mờ $X$ được tính thông qua các toán tử sup-inf trên phân hoạch mờ: $$\underline{R_P}X(x) = \sup_{F \in \tilde{U}/R_P} \min\left(F(x), \inf_{y \in U} \max(1 - F(y), \mu_X(y))\right)$$ Miền dương mờ $POS_{R_P}(D)(x) = \sup_{X \in U/D} \underline{R_P}X(x)$. Độ phụ thuộc mờ của tập thuộc tính điều kiện $P$ đối với thuộc tính quyết định $D$ được xác định bởi: $$\gamma_{R_P}(D) = \frac{\sum_{x \in U} POS_{R_P}(D)(x)}{|U|}$$

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

Luận án kết hợp phương pháp nghiên cứu lý thuyết và phương pháp nghiên cứu thực nghiệm:

  • Phương pháp nghiên cứu lý thuyết: Xây dựng mô hình toán học, thiết lập các định nghĩa, định lý và mệnh đề chứng minh tính đúng đắn của độ đo khoảng cách mờ cải tiến, tính bảo toàn thông tin của các tập rút gọn xấp xỉ và công thức tính toán gia tăng. Đánh giá độ phức tạp thuật toán bằng ký hiệu $O$-lớn.
  • Phương pháp nghiên cứu thực nghiệm: Cài đặt các thuật toán đề xuất và các thuật toán đối sánh bằng ngôn ngữ lập trình; tiến hành thử nghiệm trên các tập dữ liệu thực nghiệm chuẩn từ kho dữ liệu UCI (UCI Machine Learning Repository); đo lường và so sánh hai tiêu chí định lượng chính: thời gian thực thi thuật toán (tính bằng giây) và độ chính xác phân lớp (Classification Accuracy).

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ô mờ

Chương 1 cung cấp cơ sở lý thuyết tổng thể và phân tích hiện trạng nghiên cứu:

  • Trình bày có hệ thống lý thuyết tập thô của Pawlak, bao gồm quan hệ không phân biệt được $IND(P)$, xấp xỉ trên, xấp xỉ dưới, miền biên và miền dương $POS_P(Q)$.
  • Giới thiệu mô hình tập thô mờ của Dubois và Prade, thiết lập cấu trúc ma trận tương đương mờ $M(R_P)$, phân hoạch mờ $\tilde{U}/R_P$, không gian phân hoạch mờ và các phép toán hợp/giao mờ. Minh họa các bước tính toán trên Bảng 1.1 (Bảng quyết định Ví dụ 1) và Bảng 1.2 (Bảng quyết định mờ).
  • Phân tích quy trình 4 khâu của bài toán lựa chọn thuộc tính: (1) Tạo lập tập con, (2) Đánh giá tập con, (3) Kiểm tra điều kiện dừng, (4) Kiểm chứng kết quả (Hình 1.1).
  • So sánh cơ chế vận hành của hai tiếp cận filter và wrapper (Hình 1.2). Hướng tiếp cận filter lựa chọn thuộc tính độc lập với thuật toán học, có ưu điểm tốc độ nhanh nhưng không khai thác phản hồi của bộ phân lớp; hướng tiếp cận wrapper dùng chính thuật toán phân lớp để đánh giá tập thuộc tính, cho độ chính xác cao nhưng chi phí tính toán lớn.
  • Phân tích cấu trúc chung của thuật toán heuristic tìm tập rút gọn truyền thống (Thuật toán HARA) với độ phức tạp $O(|C|^2 |U|^2)$, đồng thời chỉ rõ hai tồn tại: tập rút gọn của phương pháp filter chưa tối ưu về số lượng thuộc tính và độ chính xác; các thuật toán hiện hành gặp hạn chế về thời gian khi bảng dữ liệu thay đổi kích thước.

Chương 2: Rút gọn thuộc tính trong bảng quyết định sử dụng độ phụ thuộc mờ và khoảng cách mờ

Chương 2 tập trung vào hai nội dung nghiên cứu lý thuyết và thực nghiệm:

1. Rút gọn thuộc tính sử dụng độ phụ thuộc mờ

  • Phân tích thuật toán RSAR trên tập thô truyền thống và thuật toán Fuzzy-Rough QUICKREDUCT của R. Shen. Chỉ ra vấn đề hội tụ và kích thước tập rút gọn của QUICKREDUCT theo phân tích của R. B. Bhatt [82].
  • Xây dựng thuật toán filter cải tiến F_FRSAR (Filter Fuzzy Rough Set based Attribute Reduction) dựa trên độ quan trọng của thuộc tính $SIG_B(a) = \gamma_{R_{B \cup {a}}}(D) - \gamma_{R_B}(D)$. Thuật toán thêm tuần tự các thuộc tính có độ quan trọng lớn nhất cho đến khi $\gamma_{R_B}(D) = \gamma_{R_C}(D)$, sau đó loại bỏ các thuộc tính dư thừa. Độ phức tạp tính toán của F_FRSAR được chứng minh là $O(|C|^2 |U|^2)$.
  • Minh họa từng bước tính toán của F_FRSAR trên Bảng 2.1 (Ví dụ 2 với 6 đối tượng $u_1 \dots u_6$ và 6 thuộc tính điều kiện $c_1 \dots c_6$). Kết quả thu được ma trận tương đương mờ $M(R_C)$, xác định $\gamma_{R_C}(d) = 1$, lần lượt chọn $c_4$ ($SIG_\emptyset(c_4) = 0.5556$), sau đó chọn $c_1$ ($SIG_{{c_4}}(c_1) = 0.4444$) để thu được tập rút gọn ${c_1, c_4}$ có $\gamma_{R_{{c_1, c_4}}}(d) = 1$.
  • Đề xuất thuật toán lai ghép FW_FRSAR (Filter-Wrapper Fuzzy Rough Set based Attribute Reduction). Giai đoạn filter tìm các tập rút gọn xấp xỉ $B_k$ theo ngưỡng $\alpha$. Giai đoạn wrapper áp dụng bộ phân lớp đánh giá độ chính xác trên các tập ứng viên $B_k$ để chọn ra tập có số lượng thuộc tính tối thiểu và độ chính xác phân lớp cao nhất.

2. Rút gọn thuộc tính sử dụng khoảng cách mờ

  • Xây dựng độ đo khoảng cách mờ giữa hai tập mờ và khoảng cách mờ giữa hai phân hoạch mờ $D_F(\tilde{U}/R_P, \tilde{U}/R_Q)$ trên cơ sở mở rộng độ đo khoảng cách phân hoạch trong công trình [48].
  • Phát triển thuật toán filter và thuật toán lai ghép FW_FDAR (Filter-Wrapper Fuzzy Distance based Attribute Reduction) sử dụng khoảng cách mờ.
  • Thử nghiệm trên các bộ dữ liệu mẫu UCI (Bảng 2.2 và Bảng 2.8), so sánh hiệu năng phân lớp và thời gian chạy giữa F_FRSAR, RSAR, GAIN_RATIO_AS_FRS, FW_FRSAR, FW_FDAR, FEBAR và FPDAR (Bảng 2.3, 2.4, 2.5, 2.6, 2.9, 2.10; Hình 2.1, 2.2).

Chương 3: Rút gọn thuộc tính trong bảng quyết định thay đổi sử dụng khoảng cách mờ

Chương 3 giải quyết bài toán tối ưu hóa thời gian tính toán khi bảng quyết định biến động:

  • Trường hợp bổ sung tập đối tượng: Thiết lập công thức toán học cập nhật gia tăng khoảng cách mờ khi thêm một tập đối tượng $\Delta U$ vào bảng quyết định $DS = (U, C \cup D)$. Đề xuất thuật toán gia tăng lai ghép IFW_FDAR_AdObj (Incremental Filter-Wrapper Fuzzy Distance Attribute Reduction - Add Object).
  • Thực nghiệm thuật toán bổ sung đối tượng: Thử nghiệm trên các bộ dữ liệu UCI (Bảng 3.1). Đánh giá thời gian thực hiện và độ chính xác phân lớp của IFW_FDAR_AdObj so với các thuật toán không gia tăng FW_FDAR, FEBAR (Bảng 3.2, 3.3) và các thuật toán gia tăng cùng loại IV-FS-FRS-2, IARM (Bảng 3.4, 3.5). Kết quả cho thấy thuật toán gia tăng giảm thiểu rõ rệt thời gian thực thi trong khi vẫn đảm bảo độ chính xác phân lớp.
  • Trường hợp loại bỏ tập đối tượng: Thiết lập công thức toán học cập nhật gia tăng khoảng cách mờ khi loại bỏ một tập đối tượng khỏi bảng quyết định. Đề xuất thuật toán gia tăng filter-wrapper tìm tập rút gọn tương ứng.

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

Luận án tự nêu hai nhóm đóng góp mới về mặt khoa học và kỹ thuật:

1. Đóng góp về mặt lý thuyết và thuật toán

  • Đề xuất 02 thuật toán lai ghép filter-wrapper tìm tập rút gọn của bảng quyết định theo tiếp cận tập thô mờ:
    • Thuật toán FW_FRSAR sử dụng độ phụ thuộc mờ.
    • Thuật toán FW_FDAR sử dụng độ đo khoảng cách mờ cải tiến (được xây dựng dựa trên việc mở rộng khoảng cách phân hoạch trong công trình [48]).
  • Đề xuất 02 thuật toán gia tăng lai ghép filter-wrapper tìm tập rút gọn của bảng quyết định thay đổi sử dụng độ đo khoảng cách mờ:
    • Thuật toán IFW_FDAR_AdObj cho trường hợp bổ sung tập đối tượng.
    • Thuật toán gia tăng cho trường hợp loại bỏ tập đối tượng.

2. Ý nghĩa thực tiễn và giải pháp đề xuất

  • Mô hình lai ghép filter-wrapper giải quyết được nhược điểm của các phương pháp filter truyền thống: giai đoạn lọc giúp thu hẹp nhanh không gian tìm kiếm các tập rút gọn ứng viên, giai đoạn đóng gói kiểm chứng trực tiếp bằng mô hình phân lớp để chọn tập con thuộc tính có kích thước nhỏ và độ chính xác cao.
  • Cơ chế cập nhật gia tăng khoảng cách mờ giúp loại bỏ việc tính toán lại toàn bộ dữ liệu từ đầu, giảm thiểu thời gian thực hiện, tạo điều kiện mở rộng xử lý trên các bảng dữ liệu quy mô lớn thông qua giải pháp phân chia dữ liệu thành từng phần.

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

Căn cứ vào phạm vi và nội dung trình bày trong văn bản, luận án có các hạn chế và định hướng phát triển:

  • Hạn chế:
    • Hướng nghiên cứu thuật toán gia tăng trong luận án mới tập trung giải quyết bài toán biến động theo chiều đối tượng (bổ sung và loại bỏ tập đối tượng), chưa mở rộng cho các trường hợp biến động theo chiều thuộc tính (thêm, bớt thuộc tính) hoặc thay đổi đồng thời cả đối tượng và giá trị thuộc tính trong mô hình tập thô mờ.
    • Thời gian thực hiện của giai đoạn wrapper phụ thuộc vào độ phức tạp của thuật toán phân lớp được tích hợp.
  • Hướng nghiên cứu tiếp:
    • Mở rộng các công thức tính toán gia tăng khoảng cách mờ cho trường hợp bổ sung và loại bỏ tập thuộc tính trong bảng quyết định mờ.
    • Nghiên cứu kết hợp cơ chế gia tăng filter-wrapper trên các mô hình dữ liệu phức tạp hơn như hệ thông tin không đầy đủ, dữ liệu đa nhãn hoặc dữ liệu dạng luồng (data streams).

Giá trị tham khảo

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

  • Đối với nghiên cứu sinh, học viên cao học chuyên ngành Khoa học máy tính, Hệ thống thông tin, Kỹ thuật dữ liệu: Luận án cung cấp hệ thống tài liệu tổng quan toàn diện về lý thuyết tập thô, tập thô mờ và các độ đo lựa chọn đặc trưng; là tài liệu tham khảo để phát triển các thuật toán rút gọn dữ liệu mới.
  • Đối với giảng viên và các nhóm nghiên cứu về Khai phá dữ liệu và Học máy: Phần xây dựng công thức ma trận tương đương mờ, phân hoạch mờ, miền dương mờ và kỹ thuật chứng minh độ phức tạp tính toán của thuật toán heuristic (như chứng minh độ phức tạp $O(|C|^2 |U|^2)$ của F_FRSAR) là nguồn tài liệu giảng dạy và nghiên cứu chuyên khảo hữu ích.
  • Đối với các kỹ sư xử lý dữ liệu: Khung thuật toán gia tăng IFW_FDAR_AdObj và cơ chế lai ghép filter-wrapper cung cấp giải pháp tham khảo để xây dựng các mô-đun tiền xử lý dữ liệu lớn và dữ liệu cập nhật liên tục.

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

1. Tại sao luận án tập trung vào hướng tiếp cận tập thô mờ trực tiếp trên bảng quyết định gốc thay vì tập thô truyền thống?

Lý thuyết tập thô truyền thống đòi hỏi các thuộc tính liên tục phải trải qua bước tiền xử lý rời rạc hóa dữ liệu. Quá trình rời rạc hóa này làm mất đi sự khác biệt chi tiết ban đầu giữa các đối tượng trong không gian dữ liệu gốc, dẫn đến suy giảm độ chính xác phân lớp. Tiếp cận tập thô mờ trực tiếp trên bảng quyết định gốc cho phép xây dựng quan hệ tương đương mờ dựa trên giá trị thực/số của thuộc tính, bảo toàn thông tin gốc và nâng cao độ chính xác của mô hình phân lớp.

2. Điểm hạn chế chính của các thuật toán rút gọn thuộc tính thuần filter theo tập thô mờ là gì?

Các thuật toán thuần filter lựa chọn thuộc tính hoàn toàn độc lập với thuật toán học máy sử dụng sau đó. Tập rút gọn thu được chỉ thỏa mãn điều kiện bảo toàn độ đo lý thuyết (như bảo toàn miền dương mờ hay độ phụ thuộc mờ) mà không có cơ chế phản hồi từ mô hình phân lớp. Do đó, tập rút gọn thu được chưa tối ưu về số lượng thuộc tính tối thiểu và chưa chắc đạt được độ chính xác phân lớp cao nhất.

3. Nguyên lý hoạt động của hướng tiếp cận lai ghép filter-wrapper trong luận án là gì?

Hướng tiếp cận lai ghép chia quá trình tìm kiếm thành hai giai đoạn liên hoàn:

  • Giai đoạn filter: Sử dụng độ đo lý thuyết (độ phụ thuộc mờ hoặc khoảng cách mờ) để nhanh chóng tìm ra các tập ứng viên rút gọn xấp xỉ $B_k$ theo các ngưỡng cắt $\alpha$.
  • Giai đoạn wrapper: Sử dụng trực tiếp thuật toán phân lớp để tính toán độ chính xác phân lớp trên từng tập ứng viên $B_k$, từ đó chọn ra tập rút gọn xấp xỉ có số lượng thuộc tính ít nhất và đạt độ chính xác phân lớp cao nhất.

4. Thuật toán gia tăng giải quyết bài toán bảng quyết định thay đổi như thế nào?

Khi bảng quyết định được bổ sung hoặc loại bỏ một tập đối tượng, các thuật toán không gia tăng phải tính toán lại ma trận quan hệ và độ đo trên toàn bộ bảng dữ liệu mới. Thuật toán gia tăng của luận án sử dụng các công thức cập nhật khoảng cách mờ trực tiếp dựa trên phần dữ liệu bị thay đổi, giúp điều chỉnh tập rút gọn đã có mà không cần duyệt lại toàn bộ cơ sở dữ liệu, từ đó giảm thiểu đáng kể thời gian tính toán.

5. Độ phức tạp thời gian của thuật toán F_FRSAR được tính toán như thế nào?

Với bảng quyết định có $|C|$ thuộc tính điều kiện và $|U|$ đối tượng, chi phí tính ma trận tương đương mờ $M(R_C)$ là $O(|C| |U|^2)$, chi phí tính độ phụ thuộc mờ $\gamma_{R_C}(D)$ là $O(|C| |U|^2)$. Vòng lặp tìm kiếm thuộc tính có độ quan trọng lớn nhất gồm hai vòng lặp lồng nhau theo $|C|$, mỗi bước tính độ phụ thuộc mờ mất $O(|U|^2)$, dẫn đến chi phí $O(|C|^2 |U|^2)$. Vòng lặp loại bỏ thuộc tính dư thừa cũng có độ phức tạp $O(|C|^2 |U|^2)$. Do đó, tổng độ phức tạp thời gian của thuật toán F_FRSAR là $O(|C|^2 |U|^2)$.

Kết luận

Luận án đã nghiên cứu toàn diện bài toán rút gọn thuộc tính trong bảng quyết định tĩnh và bảng quyết định thay đổi dựa trên lý thuyết tập thô mờ. Tác giả đã đề xuất các thuật toán lai ghép filter-wrapper sử dụng độ phụ thuộc mờ và độ đo khoảng cách mờ cải tiến, giúp tối ưu hóa số lượng thuộc tính và cải thiện độ chính xác phân lớp so với các phương pháp filter truyền thống. Đồng thời, luận án đã xây dựng các công thức tính toán gia tăng khoảng cách mờ và đề xuất các thuật toán cập nhật tập rút gọn khi bổ sung và loại bỏ tập đối tượng, giúp giảm thiểu chi phí thời gian tính toán trên các bảng dữ liệu quy mô lớn. Hệ thống thuật toán đề xuất đã được chứng minh chặt chẽ về mặt toán học và được kiểm chứng thực nghiệm đầy đủ trên các tập dữ liệu chuẩn UCI.