Tổng quan luận án
Trong khai phá dữ liệu và phát hiện tri thức, sự gia tăng không ngừng về dung lượng dữ liệu và số lượng thuộc tính tạo ra rào cản kỹ thuật lớn cho các mô hình tính toán. 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à khâu tiền xử lý dữ liệu nhằm loại bỏ các thuộc tính dư thừa, không cần thiết, giúp tối ưu hóa hiệu quả thực thi của các thuật toán phân lớp. Lý thuyết tập thô do Z. Pawlak đề xuất đã chứng minh được hiệu quả trong việc xử lý các bảng quyết định đầy đủ. Tuy nhiên, dữ liệu thu thập từ các ứng dụng thực tế thường xuyên xảy ra tình trạng thiếu giá trị trên miền thuộc tính (bảng quyết định không đầy đủ - Incomplete Decision Tables, viết tắt là IDS). Nhằm giải quyết bài toán rút gọn thuộc tính trực tiếp trên IDS mà không cần áp dụng kỹ thuật tiền xử lý điền giá trị thiếu, mô hình tập thô dung sai (tolerance rough set) của Kryszkiewicz đã mở rộng quan hệ tương đương thành quan hệ dung sai.
Hiện nay, các nghiên cứu rút gọn thuộc tính theo tiếp cận tập thô dung sai phần lớn triển khai theo hướng tiếp cận filter (lọc) truyền thống. Trong tiếp cận này, tập rút gọn là tập thuộc tính tối thiểu bảo toàn một độ đo xác định, việc đánh giá độ chính xác của mô hình phân lớp chỉ được thực hiện sau khi đã tìm được tập rút gọn. Do đó, tập rút gọn tìm được chưa tối ưu đồng thời về số lượng thuộc tính và độ chính xác phân lớp. Mặt khác, trong bối cảnh dữ liệu lớn luôn biến động và cập nhật, các thuật toán tĩnh buộc phải tính toán lại từ đầu trên toàn bộ bảng quyết định, làm tăng chi phí thời gian tính toán. Hướng tiếp cận tính toán gia tăng (chỉ tính toán trên phần dữ liệu bổ sung hoặc loại bỏ) là giải pháp khắc phục vấn đề này. Tuy vậy, các thuật toán gia tăng hiện có trên bảng quyết định không đầy đủ vẫn chỉ dừng lại ở tiếp cận filter.
Mục tiêu nghiên cứu của luận án được xác định gồm hai nội dung chính:
- Đề 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 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.
- Đề 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 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.
Câu hỏi nghiên cứu trọng tâm mà luận án giải quyết là: Làm thế nào để xây dựng một độ đo khoảng cách phù hợp và thiết lập quy trình kết hợp hai pha filter-wrapper trên bảng quyết định không đầy đủ nhằm tối ưu hóa số lượng thuộc tính và độ chính xác phân lớp; đồng thời, làm thế nào để thiết lập các công thức toán học cập nhật khoảng cách gia tăng khi bảng quyết định biến động (thêm hoặc bớt đối tượng, thêm hoặc bớt thuộc tính) nhằm giảm thiểu thời gian tính toán so với việc tính lại từ đầu.
Đối tượng nghiên cứu của luận án bao gồm: 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 theo tiếp cận tập thô dung sai 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ủa luận án giới hạn trong 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, được cài đặt và kiểm chứng thực nghiệm trên các bộ dữ liệu chuẩn từ kho dữ liệu UCI (University of California, Irvine Machine Learning Repository).
Tổng quan tài liệu và vị trí của luận án
Luận án đã điểm lại và hệ thống hóa các hướng nghiên cứu về rút gọn thuộc tính theo tiếp cận tập thô dung sai trên bảng quyết định không đầy đủ cố định và bảng quyết định thay đổi.
Đối với bài toán rút gọn thuộc tính trên bảng quyết định không đầy đủ tĩnh, tác giả phân loại các công trình đã công bố theo 6 nhóm độ đo chính:
- Nhóm sử dụng miền dương mở rộng: Peng và các cộng sự (2010), Meng và các cộng sự (2009), Xu và các cộng sự (2013), Hu và các cộng sự (2017), cùng thuật toán sử dụng miền dương xấp xỉ của Qian và các cộng sự (2011).
- Nhóm sử dụng ma trận phân biệt và hàm phân biệt mở rộng: Zhou và các cộng sự (2009) dùng ma trận tương tự; Xu và các cộng sự (2009), Tan và các cộng sự (2010), Zou và các cộng sự (2012) dùng ma trận phân biệt và ma trận gán; Li và các cộng sự (2010) dùng ma trận nhị phân; Vu Van Dinh và Nguyen Long Giang (2013), Ma và các cộng sự (2017) phát triển các hàm phân biệt mở rộng.
- Nhóm sử dụng entropy thông tin mở rộng: Sun và các cộng sự (2012), Dai và các cộng sự (2013), Xu và các cộng sự (2013), Yue và các cộng sự (2015), Tao và các cộng sự (2017), và công trình sử dụng entropy tương hỗ mở rộng của Qian và các cộng sự (2015).
- Nhóm sử dụng độ đo lượng thông tin và hạt thông tin: Sai Prasad và các cộng sự (2012) dùng hạt thông tin mở rộng; Xu và các cộng sự (2012, 2019) sử dụng lượng thông tin mở rộng.
- Nhóm sử dụng độ đo khoảng cách: Long Giang Nguyen và Hung Son Nguyen (2013), Vu Van Dinh và các cộng sự (2015).
- Nhóm sử dụng các độ đo khác: Dai và các cộng sự (2010) dùng độ bao phủ; Qian và các cộng sự (2010), Meng và các cộng sự (2012); Shu và các cộng sự (2014) dùng quan hệ không phân biệt được mở rộng; Zhao và các cộng sự (2014) dùng hàm quyết định suy rộng và entropy dựa trên quan hệ dung sai lân cận; Xie và các cộng sự (2018) đề xuất thuật toán NEW-R dựa trên độ không nhất quán, cho thấy hiệu quả tốt hơn thuật toán POS-R của Meng và các cộng sự (2009) và thuật toán INF-R của Dai và các cộng sự (2013).
Tại Việt Nam, nhóm nghiên cứu liên quan đã hoàn thành một số luận án tiến sĩ: Luận án của tác giả [1] 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 đủ cố định; Luận án của tác giả [2] xây dựng các thuật toán gia tăng trên bảng quyết định đầy đủ theo hướng filter truyền thống; Luận án của tác giả [3] đề xuất hướng kết hợp filter-wrapper tìm tập rút gọn trên bảng quyết định đầy đủ dựa trên mô hình tập thô mờ (fuzzy rough set).
Đối với bài toán tính toán gia tăng tìm tập rút gọn khi bảng quyết định biến động:
- Theo tập thô truyền thống và các mô hình mở rộng, các công trình tập trung vào các tình huống: bổ sung/loại bỏ đối tượng (Hu và cs., 2005; Guan và cs., 2009; Liu và cs., 2009; Chen và cs., 2013; Liang và cs., 2014; Nguyen Thi Lan Huong và Nguyen Long Giang, 2016; Jing và cs., 2016, 2017; Hao và cs., 2017; Das và cs., 2018; Yang và cs., 2017; Wei và cs., 2018; Ma và cs., 2019; Shua và cs., 2019); bổ sung/loại bỏ thuộc tính (Li và cs., 2007; Xie và cs., 2013; Wang và cs., 2013; Janos và cs., 2016; Raza và cs., 2016; Jing và cs., 2016, 2018); đối tượng thay đổi giá trị (Chen và cs., 2013; Liu và cs., 2016; Jing và cs., 2017; Wei và cs., 2018; Yang và cs., 2019; Cai và cs., 2019); thuộc tính thay đổi giá trị (Liu và cs., 2009; Chen và cs., 2010; Wang và cs., 2013; Lang và cs., 2016, 2017; Cai và cs., 2017).
- Theo tập thô dung sai trên bảng quyết định không đầy đủ, các nghiên cứu gia tăng gồm: bổ sung/loại bỏ đối tượng (Zhang và cs., 2008; Li và cs., 2008; Shu và cs., 2012, 2013, 2015; Chen và cs., 2012; Liu và cs., 2014; Ma và cs., 2016; Luo và cs., 2017; Huyen và cs., 2018; Yu và cs., 2018; Wang và cs., 2019; Zhang và cs., 2019); bổ sung/loại bỏ thuộc tính (Shu và cs., 2014); thay đổi giá trị đối tượng (Shu và cs., 2014); thay đổi giá trị thuộc tính (Xie và cs., 2018). Gần đây, công trình của nhóm tác giả [4] đề xuất thuật toán gia tăng filter-wrapper nhưng chỉ thực hiện trên bảng quyết định đầy đủ theo tiếp cận tập thô mờ khi bổ sung tập đối tượng.
Khoảng trống nghiên cứu được luận án xác định: Hầu hết các thuật toán rút gọn thuộc tính trong bảng quyết định không đầy đủ đã công bố đều thuần túy theo tiếp cận filter, chưa khai thác cơ chế kết hợp filter-wrapper để tối ưu hóa đồng thời số lượng thuộc tính và độ chính xác phân lớp. Đồng thời, chưa có công trình nào thiết lập các thuật toán gia tăng filter-wrapper trên bảng quyết định không đầy đủ cho cả hai trường hợp biến động đối tượng và biến động thuộc tính.
Cơ sở lý thuyết và phương pháp nghiên cứu
Luận án dựa trên các cơ sở lý thuyết toán học và mô hình khai phá dữ liệu sau:
- Hệ thông tin và mô hình tập thô truyền thống: Hệ thông tin được định nghĩa là cặp $IS = \langle U, A \rangle$, trong đó $U$ là tập hữu hạn các đối tượng và $A$ là tập hữu hạn các thuộc tính. Mỗi tập thuộc tính con $P \subseteq A$ xác định quan hệ tương đương không phân biệt $IND(P) = {(u, v) \in U \times U \mid \forall a \in P, a(u) = a(v)}$, tạo nên phân hoạch $U/IND(P)$ với các lớp tương đương $[u]_P$. Tập đối tượng $X \subseteq U$ được xấp xỉ qua hai tập rõ: xấp xỉ dưới $B_X = {u \in U \mid [u]_B \subseteq X}$ và xấp xỉ trên $B^X = {u \in U \mid [u]_B \cap X \neq \emptyset}$.
- Hệ thông tin không đầy đủ và mô hình tập thô dung sai: Khi tồn tại đối tượng $u \in U$ và thuộc tính $a \in A$ sao cho giá trị $a(u)$ bị thiếu (ký hiệu là ''), hệ thông tin trở thành hệ thông tin không đầy đủ $IIS = \langle U, A \rangle$. Quan hệ dung sai $SIM(P)$ trên $U$ được định nghĩa:
$$SIM(P) = {(u, v) \in U \times U \mid \forall a \in P, a(u) = a(v) \lor a(u) = '' \lor a(v) = '*'}$$
Quan hệ $SIM(P)$ có tính phản xạ, đối xứng nhưng không có tính bắc cầu, do đó không tạo thành phân hoạch mà sinh ra một phủ $U/SIM(P)$ gồm các lớp dung sai $S_P(u) = {v \in U \mid (u, v) \in SIM(P)}$. Xấp xỉ dưới và xấp xỉ trên theo dung sai được xác định là $P_X = {u \in U \mid S_P(u) \subseteq X}$ và $P^X = {u \in U \mid S_P(u) \cap X \neq \emptyset}$.
- Bảng quyết định không đầy đủ: Định nghĩa bởi $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 duy nhất không chứa giá trị thiếu. Miền dương của $C$ đối với $d$ là $POS_C(d) = \bigcup_{X \in U/{d}} C_X$. Bảng quyết định là nhất quán khi và chỉ khi $POS_C(d) = U$.
- Ma trận dung sai: Ma trận $M(P) = (p_{ij}){n \times n}$ của quan hệ $SIM(P)$ có các phần tử $p{ij} = 1$ nếu $u_j \in S_P(u_i)$ và $p_{ij} = 0$ nếu $u_j \notin S_P(u_i)$. Đối với hai tập thuộc tính $P, Q$, ma trận dung sai trên $P \cup Q$ có dạng tích từng phần tử $s_{ij} = p_{ij} \cdot q_{ij}$.
- Khung tiếp cận kết hợp filter-wrapper: Pha filter sử dụng tiêu chuẩn độ đo bên trong để nhanh chóng lọc ra các tập con thuộc tính ứng viên; pha wrapper sử dụng thuật toán phân lớp để đánh giá trực tiếp độ chính xác của các ứng viên, từ đó lựa chọn tập rút gọn đạt độ chính xác phân lớp tối ưu với số lượng thuộc tính tối thiểu.
Phương pháp nghiên cứu kết hợp giữa lý thuyết và thực nghiệm:
- Phương pháp nghiên cứu lý thuyết: Phân tích toán học các độ đo hiện có, xây dựng độ đo khoảng cách mới giữa các tập hợp và giữa các tập thuộc tính, chứng minh các tính chất hình học và đại số (tiên đề khoảng cách, bất đẳng thức tam giác, tính đơn điệu), đồng thời dẫn xuất các công thức cập nhật gia tăng khi tập đối tượng và tập thuộc tính thay đổi.
- Phương pháp nghiên cứu thực nghiệm: Cài đặt các thuật toán đề xuất, tiến hành thử nghiệm trên các tập dữ liệu thực tế lấy từ kho UCI. Các tiêu chí so sánh gồm: thời gian tính toán (giây), số lượng thuộc tính rút gọn và độ chính xác phân lớp (tỷ lệ phần trăm).
Nguồn dữ liệu thực nghiệm: Sử dụng các bộ dữ liệu chuẩn có chứa giá trị thiếu từ UCI Machine Learning Repository, bao gồm: Audiology, Soybean-large, Congressional Voting Records, Arrhythmia, Anneal, Advertisements.
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 tập trung hệ thống hóa cơ sở lý luận về lý thuyết tập thô truyền thống và mô hình tập thô dung sai, đồng thời tổng quan các nghiên cứu liên quan đến bài toán rút gọn thuộc tính. Tác giả phân tích quy trình rút gọn thuộc tính tiêu chuẩn gồm 4 khâu: tạo lập tập con thuộc tính, đánh giá tập con, kiểm tra điều kiện dừng và kiểm chứng kết quả. Hai chiến lược heuristic phổ biến là tìm kiếm từ dưới lên (bottom-up, xuất phát từ tập rỗng và lần lượt bổ sung thuộc tính có độ quan trọng lớn nhất) và từ trên xuống (top-down, xuất phát từ tập đầy đủ và lần lượt loại bỏ thuộc tính ít quan trọng nhất).
Để minh họa cấu trúc của một bảng quyết định không đầy đủ, tác giả đưa ra Bảng 1.1 mô tả dữ liệu về 6 chiếc xe hơi ($u_1$ đến $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ô |
Đơn giá ($c_1$) |
Km đã đi ($c_2$) |
Kích thước ($c_3$) |
Tốc độ ($c_4$) |
Gia tốc ($d$) |
| $u_1$ |
Cao |
Nhiều |
Trung bình |
Thấp |
Nhanh |
| $u_2$ |
Thấp |
* |
Trung bình |
Thấp |
Nhanh |
| $u_3$ |
* |
* |
Gọn nhẹ |
Cao |
Chậm |
| $u_4$ |
Cao |
* |
Trung bình |
Cao |
Nhanh |
| $u_5$ |
* |
* |
Trung bình |
Cao |
Rất nhanh |
| $u_6$ |
Thấp |
Nhiều |
Trung bình |
* |
Nhanh |
Các lớp dung sai tương ứng của các đối tượng trên tập thuộc tính điều kiện $C$ được tính toán cụ thể:
- $S_C(u_1) = {u_1}$
- $S_C(u_2) = {u_2, u_6}$
- $S_C(u_3) = {u_3}$
- $S_C(u_4) = {u_4, u_5}$
- $S_C(u_5) = {u_4, u_5, u_6}$
- $S_C(u_6) = {u_2, u_5, u_6}$
Từ đó, ma trận dung sai $M(C)$ cấp $6 \times 6$ được thiết lập với các hàng biểu diễn vector nhị phân của từng lớp dung sai. Các tập xấp xỉ dưới đối với phân hoạch của thuộc tính quyết định $d$ gồm có: $C_X_1 = {u_1, u_2}$ (đối với nhãn "Nhanh"), $C_X_2 = {u_3}$ (đối với nhãn "Chậm"), và $C_X_3 = \emptyset$ (đối với nhãn "Rất nhanh"). Hàm quyết định suy rộng $\partial_C(u_4) = \partial_C(u_5) = \partial_C(u_6) = {\text{Nhanh}, \text{Rất nhanh}}$ chỉ ra rằng bảng quyết định trên là không nhất quán.
Phần khảo sát tài liệu của Chương 1 đã phân loại chi tiết các thuật toán 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 thành 17 nhóm nghiên cứu (Bảng 1.2), các thuật toán gia tăng theo tập thô truyền thống và mô hình mở rộng thành 43 nhóm công bố (Bảng 1.3), và các thuật toán gia tăng theo tập thô dung sai thành 13 nhóm công bố (Bảng 1.4). Qua phân tích, chương khẳng định hạn chế cốt lõi của các phương pháp trước đó là việc vận hành độc lập theo cơ chế filter, dẫn tới tập rút gọn chưa tối ưu về số lượng thuộc tính và độ chính xác phân lớp; đồng thời thiếu vắng các thuật toán gia tăng filter-wrapper trên bảng quyết định không đầy đủ.
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 trình bày đóng góp lý thuyết đầu tiên của luận án: thiết lập độ đo khoảng cách mới và thuật toán kết hợp filter-wrapper cho bảng quyết định không đầy đủ tĩnh.
Độ đo khoảng cách giữa hai tập hợp con $A, B \subseteq U$ được xây dựng:
$$d(A, B) = |A \cup B| - |A \cap B|$$
Tác giả chứng minh $d(A, B)$ thỏa mãn đầy đủ ba tiên đề của một metric khoảng cách: tính không âm và triệt tiêu khi $A = B$, tính đối xứng $d(A, B) = d(B, A)$, và bất đẳng thức tam giác $d(A, B) \le d(A, C) + d(B, C)$ thông qua phép biểu diễn tập hợp bằng vector nhị phân $n$ chiều ($V^A, V^B \in {0, 1}^n$).
Trên cơ sở đó, Mệnh đề 2.1 mở rộng độ đo này thành khoảng cách giữa hai phủ $U/SIM(P)$ và $U/SIM(Q)$ sinh bởi hai tập thuộc tính $P, Q \subseteq C$:
$$D(P, Q) = \frac{1}{n^2} \sum_{i=1}^n \left( |S_P(u_i) \cup S_Q(u_i)| - |S_P(u_i) \cap S_Q(u_i)| \right)$$
Khoảng cách $D(P, Q)$ đạt giá trị nhỏ nhất bằng 0 khi hai phủ trùng nhau ($K(P) = K(Q)$) và đạt giá trị lớn nhất là $1 - 1/n$ khi một phủ là phủ rời rạc và phủ còn lại là phủ một khối.
Thông qua ma trận dung sai $M(C) = (c_{ij}){n \times n}$ và $M(d) = (d{ij}){n \times n}$, khoảng cách giữa tập thuộc tính điều kiện $C$ và tập $C \cup {d}$ được biểu diễn dưới dạng giải tích:
$$D(C, C \cup {d}) = \frac{1}{n^2} \sum{i=1}^n \left( |S_C(u_i)| - |S_{Cd}(u_i)| \right) = \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n (c_{ij} - c_{ij} \cdot d_{ij})$$
Luận án chứng minh tính chất đơn điệu: Với mọi $B \subseteq C$, ta luôn có $D(B, B \cup {d}) \ge D(C, C \cup {d})$. Khái niệm tập rút gọn dựa trên khoảng cách được định nghĩa là tập con $B \subseteq C$ thỏa mãn $D(B, B \cup {d}) = D(C, C \cup {d})$ và không tồn tại tập con thực sự $B' \subset B$ thỏa mãn điều kiện này.
Dựa trên cơ sở toán học này, luận án đề xuất hai thuật toán:
- Thuật toán
IDS_F_DAR (Filter Distance based Attribute Reduction): Hoạt động thuần túy theo tiếp cận filter, tìm tập rút gọn tối thiểu bảo toàn độ đo khoảng cách.
- Thuật toán
IDS_FW_DAR (Filter-Wrapper Distance based Attribute Reduction): Kết hợp filter và wrapper. Trong pha filter, thuật toán sử dụng độ quan trọng của thuộc tính dựa trên khoảng cách để sinh ra các tập ứng viên rút gọn xấp xỉ; trong pha wrapper, thuật toán đưa các tập ứng viên vào bộ phân lớp nhằm đánh giá độ chính xác thực tế và lựa chọn tập rút gọn có kích thước nhỏ nhất đạt độ chính xác phân lớp cao nhất.
Kết quả thực nghiệm trên các bộ 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 trong tập rút gọn và cải thiện độ chính xác phân lớp so với thuật toán IDS_F_DAR, cũng như so với các thuật toán đối sánh khác như POS-R (dựa trên miền dương), INF-R (dựa trên entropy thông tin) và NEW-R (dựa trên độ không nhất quán).
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. Tác giả nghiên cứu và đề xuất các thuật toán cho 4 kịch bản thay đổi:
- Bổ sung tập đối tượng ($\Delta U$): Xây dựng công thức cập nhật khoảng cách gia tăng khi bảng quyết định mở rộng thành $IDS_1 = \langle U \cup \Delta U, C \cup {d} \rangle$, đề xuất thuật toán gia tăng
IDS_IFW_AO.
- Loại bỏ tập đối tượng ($\Delta U$): Xây dựng công thức cập nhật khoảng cách gia tăng khi bảng quyết định thu hẹp thành $IDS_2 = \langle U \setminus \Delta U, C \cup {d} \rangle$, đề xuất thuật toán gia tăng
IDS_IFW_DO.
- Bổ sung tập thuộc tính điều kiện ($\Delta C$): Xây dựng công thức cập nhật khoảng cách gia tăng khi bảng quyết định mở rộng không gian thuộc tính thành $IDS_1 = \langle U, (C \cup \Delta C) \cup {d} \rangle$, đề xuất thuật toán gia tăng
IDS_IFW_AA.
- Loại bỏ tập thuộc tính điều kiện ($\Delta C$): Xây dựng công thức cập nhật khoảng cách gia tăng khi loại bớt thuộc tính thành $IDS_2 = \langle U, (C \setminus \Delta C) \cup {d} \rangle$, đề xuất thuật toán gia tăng
IDS_IFW_DA.
Nguyên lý tính toán gia tăng của các thuật toán là tái sử dụng các lớp dung sai và ma trận dung sai đã tính ở bước trước, chỉ tính toán bổ sung phần giao và phần hợp liên quan đến tập đối tượng hoặc tập thuộc tính thay đổi, tránh việc quét lại toàn bộ bảng dữ liệu.
Phần thực nghiệm trong Chương 3 tập trung kiểm chứng sâu hai thuật toán gia tăng quan trọng:
- Thực nghiệm với thuật toán
IDS_IFW_AO (bổ sung đối tượng): Được thử nghiệm trên các bộ dữ liệu chuẩn từ kho UCI gồm Audiology, Soybean-large, Congressional Voting Records, Arrhythmia, Anneal, Advertisements. Tác giả tiến hành so sánh đối đầu giữa IDS_IFW_AO và thuật toán tĩnh IDS_FW_DAR (Bảng 3.4, Bảng 3.5); so sánh với thuật toán gia tăng đối tượng đã công bố là IARM-I (Bảng 3.6, Bảng 3.7); và so sánh tổng hợp cả ba thuật toán (Bảng 3.8, Bảng 3.9). Kết quả cho thấy IDS_IFW_AO giảm thiểu đáng kể thời gian thực hiện so với IDS_FW_DAR, đồng thời vượt trội IARM-I về mức độ tinh giản số lượng thuộc tính và độ chính xác phân lớp.
- Thực nghiệm với thuật toán
IDS_IFW_AA (bổ sung thuộc tính): Được thử nghiệm trên các tập dữ liệu từ kho UCI (Bảng 3.10), tiến hành so sánh với thuật toán gia tăng thuộc tính UARA về số lượng thuộc tính tập rút gọn, độ chính xác phân lớp (Bảng 3.11) và thời gian thực hiện (Bảng 3.12). Kết quả ghi nhận IDS_IFW_AA duy trì thời gian thực thi hiệu quả, thu được số thuộc tính rút gọn ít hơn và đạt độ chính xác phân lớp cao hơn.
Kết quả và những đóng góp mới
Luận án đã đạt được các đóng góp mới về mặt lý luận và thực tiễn như sau:
Về mặt lý thuyết và khoa học:
- Xây dựng một độ đo khoảng cách mới giữa hai tập hợp và phát triển thành độ đ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 toán học đầy đủ các tiên đề khoảng cách và thiết lập công thức tính khoảng cách thông qua ma trận dung sai.
- Đề xuất thuật toán
IDS_FW_DAR theo tiếp cận kết hợp filter-wrapper tìm tập rút gọn trên bảng quyết định không đầy đủ tĩnh dựa trên độ đo khoảng cách. Kết quả thực nghiệm chứng minh thuật toán giúp 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 so với các phương pháp filter thuần túy.
- Thiết lập hệ thống công thức cập nhật khoảng cách gia tăng và đề xuất 04 thuật toán gia tăng filter-wrapper trên bảng quyết định không đầy đủ thay đổi:
- Thuật toán
IDS_IFW_AO cho bài toán bổ sung tập đối tượng;
- Thuật toán
IDS_IFW_DO cho bài toán loại bỏ tập đối tượng;
- Thuật toán
IDS_IFW_AA cho bài toán bổ sung tập thuộc tính;
- Thuật toán
IDS_IFW_DA cho bài toán loại bỏ tập thuộc tính.
Bảng tổng hợp các thuật toán do luận án đề xuất:
| Ký hiệu thuật toán |
Tiếp cận xử lý |
Loại bảng quyết định |
Tình huống biến động dữ liệu |
Độ đo sử dụng |
IDS_F_DAR |
Filter |
Không đầy đủ, tĩnh |
Cố định |
Độ đo khoảng cách mới |
IDS_FW_DAR |
Filter-Wrapper |
Không đầy đủ, tĩnh |
Cố định |
Độ đo khoảng cách mới |
IDS_IFW_AO |
Gia tăng, Filter-Wrapper |
Không đầy đủ, động |
Bổ sung tập đối tượng |
Khoảng cách cập nhật gia tăng |
IDS_IFW_DO |
Gia tăng, Filter-Wrapper |
Không đầy đủ, động |
Loại bỏ tập đối tượng |
Khoảng cách cập nhật gia tăng |
IDS_IFW_AA |
Gia tăng, Filter-Wrapper |
Không đầy đủ, động |
Bổ sung tập thuộc tính |
Khoảng cách cập nhật gia tăng |
IDS_IFW_DA |
Gia tăng, Filter-Wrapper |
Không đầy đủ, động |
Loại bỏ tập thuộc tính |
Khoảng cách cập nhật gia tăng |
Về mặt thực tiễn:
Các thuật toán đề xuất cung cấp giải pháp kỹ thuật tiền xử lý dữ liệu cho các hệ thống thông tin bị thiếu giá trị mà không cần suy diễn hoặc gán nhãn nhân tạo cho giá trị thiếu. Phương pháp này có khả năng ứng dụng trong các bài toán chẩn đoán y tế (thu thập triệu chứng bệnh nhân không đầy đủ), phân tích rủi ro tài chính - ngân hàng và xử lý dữ liệu lớn biến động liên tục thông qua kỹ thuật chia nhỏ dữ liệu để cập nhật gia tăng.
Hạn chế và hướng nghiên cứu tiếp
Dựa trên phạm vi và nội dung văn bản luận án trình bày, các hạn chế và hướng nghiên cứu mở rộng gồm:
Hạn chế:
- Luận án mới chỉ tập trung kiểm chứng thực nghiệm sâu đối với hai thuật toán gia tăng khi bổ sung dữ liệu là
IDS_IFW_AO (bổ sung đối tượng) và IDS_IFW_AA (bổ sung thuộc tính). Hai thuật toán cho trường hợp loại bỏ dữ liệu (IDS_IFW_DO và IDS_IFW_DA) đã được xây dựng về mặt lý thuyết và công thức gia tăng nhưng chưa có số liệu thực nghiệm so sánh chi tiết tương ứng trong phần mục lục và danh mục bảng.
- Luận án tập trung giải quyết các biến động về cấu trúc bảng (thêm/bớt hàng, thêm/bớt cột), chưa giải quyết trường hợp giá trị của đối tượng hoặc giá trị của thuộc tính bị thay đổi (nhiễu hoặc cập nhật lại giá trị thuộc tính).
- Chi phí thời gian thực hiện của tiếp cận filter-wrapper ở giai đoạn wrapper phụ thuộc vào bộ phân lớp được lựa chọn, do đó thời gian chạy tổng thể vẫn lớn hơn so với các phương pháp thuần filter.
Hướng nghiên cứu tiếp:
- Tiếp tục triển khai thực nghiệm toàn diện, đo đạc hiệu năng của hai thuật toán loại bỏ đối tượng (
IDS_IFW_DO) và loại bỏ thuộc tính (IDS_IFW_DA) trên các bộ dữ liệu thực tế.
- Mở rộng nghiên cứu các thuật toán gia tăng filter-wrapper cho các kịch bản đối tượng thay đổi giá trị và thuộc tính thay đổi giá trị trong mô hình tập thô dung sai.
- Nghiên cứu song song hóa các thuật toán gia tăng trên các nền tảng tính toán phân tán để xử lý các bảng quyết định có kích thước quy mô lớn hơn.
Giá trị tham khảo
Luận án mang lại giá trị tham khảo chuyên môn cho các đối tượng và lĩnh vực sau:
- Đối với nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Cơ sở toán học cho tin học, Khoa học máy tính, Hệ thống thông tin: Luận án cung cấp hệ thống tài liệu tổng quan chuẩn mực tại Chương 1 với hệ thống bảng phân loại tổng hợp 17 nhóm thuật toán tĩnh và hơn 50 công trình gia tăng theo tập thô truyền thống và tập thô dung sai; cùng phương pháp chứng minh toán học chặt chẽ về metric khoảng cách và ma trận dung sai tại Chương 2.
- Đối với chuyên gia phân tích dữ liệu và kỹ sư học máy: Chương 2 và Chương 3 cung cấp mã giả thuật toán và quy trình thiết kế mô hình hai pha filter-wrapper, giúp tối ưu hóa số lượng đặc trưng đầu vào cho các mô hình phân lớp mà không làm giảm độ chính xác trên dữ liệu có giá trị thiếu.
- Đối với các cơ quan quản lý và nhà phát triển hệ thống trong y tế, tài chính: Phương pháp gia tăng trong luận án gợi mở giải pháp tiền xử lý dữ liệu lớn khi hệ thống tiếp nhận luồng dữ liệu mới định kỳ mà không cần chi phí tính toán lại từ đầu.
Câu hỏi thường gặp
-
Tại sao tác giả sử dụng mô hình tập thô dung sai thay vì mô hình tập thô truyền thống của Pawlak?
Mô hình tập thô truyền thống của Pawlak dựa trên quan hệ tương đương, vốn chỉ áp dụng được cho bảng quyết định đầy đủ. Trong thực tế, các bảng quyết định thường thiếu giá trị (chứa giá trị missing '*'). Quan hệ dung sai của Kryszkiewicz có tính phản xạ và đối xứng nhưng không có tính bắc cầu, cho phép xử lý trực tiếp các giá trị thiếu mà không cần qua khâu tiền xử lý điền giá trị nhân tạo.
-
Quy trình kết hợp filter-wrapper trong thuật toán IDS_FW_DAR hoạt động như thế nào?
Thuật toán chia thành hai pha: Pha filter đóng vai trò tìm kiếm các tập con thuộc tính ứng viên (các tập rút gọn xấp xỉ) dựa trên tiêu chuẩn độ quan trọng của thuộc tính thông qua độ đo khoảng cách; pha wrapper tiếp nhận danh sách các ứng viên này, sử dụng bộ phân lớp để đánh giá trực tiếp độ chính xác phân lớp và lựa chọn ra tập rút gọn có kích thước nhỏ nhất đạt độ chính xác cao nhất.
-
Độ đo khoảng cách giữa hai tập thuộc tính $P$ và $Q$ được định nghĩa và biểu diễn tính toán như thế nào?
Độ đo khoảng cách được định nghĩa qua công thức:
$$D(P, Q) = \frac{1}{n^2} \sum_{i=1}^n \left( |S_P(u_i) \cup S_Q(u_i)| - |S_P(u_i) \cap S_Q(u_i)| \right)$$
Khi tính khoảng cách giữa tập thuộc tính điều kiện $C$ và tập $C \cup {d}$, giá trị khoảng cách được tính trực tiếp từ ma trận dung sai:
$$D(C, C \cup {d}) = \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n (c_{ij} - c_{ij} \cdot d_{ij})$$
trong đó $c_{ij}$ và $d_{ij}$ là các phần tử nhị phân thuộc ma trận dung sai của $C$ và $d$.
-
Luận án đề xuất những thuật toán gia tăng nào và tương ứng với các tình huống biến động dữ liệu nào?
Luận án đề xuất 04 thuật toán gia tăng gồm: IDS_IFW_AO (xử lý khi bổ sung tập đối tượng), IDS_IFW_DO (xử lý khi loại bỏ tập đối tượng), IDS_IFW_AA (xử lý khi bổ sung tập thuộc tính điều kiện), và IDS_IFW_DA (xử lý khi loại bỏ tập thuộc tính điều kiện).
-
Hiệu quả của các thuật toán đề xuất được kiểm chứng qua các thuật toán đối sánh nào trên kho dữ liệu UCI?
Thuật toán tĩnh IDS_FW_DAR được đối sánh với các thuật toán filter gồm IDS_F_DAR, POS-R, INF-R và NEW-R. Thuật toán gia tăng IDS_IFW_AO được đối sánh về thời gian, số thuộc tính và độ chính xác phân lớp với thuật toán không gia tăng IDS_FW_DAR và thuật toán gia tăng IARM-I. Thuật toán gia tăng IDS_IFW_AA được đối sánh với thuật toán gia tăng UARA.
Kết luận
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 định không đầy đủ theo tiếp cận filter-wrapper" 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 trên bảng quyết định không đầy đủ thông qua việc xây dựng độ đo khoảng cách mới và mô hình kết hợp filter-wrapper. Tác giả đã thiết lập 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) xử lý linh hoạt các tình huống biến động đối tượng và thuộc tính. Các kết quả thực nghiệm trên kho dữ liệu mẫu UCI xác nhận các thuật toán đề xuất giúp giảm thiểu đáng kể số lượng thuộc tính trong tập rút gọn, cải thiện độ chính xác phân lớp và tối ưu hóa thời gian tính toán so với các thuật toán đối sánh.
