Tổng quan luận án
Trong khai phá dữ liệu và học máy, phân lớp dữ liệu là một trong những bài toán nền tảng nhằm phân chia các đối tượng vào những lớp xác định dựa trên tập đặc trưng. Mô hình cây quyết định được ứng dụng phổ biến nhờ cấu trúc tường minh và khả năng diễn giải tri thức dưới dạng các quy tắc logic. Tuy nhiên, các thuật toán học cây quyết định kinh điển (như ID3, C4.5, CART, SLIQ, SPRINT) chủ yếu được thiết kế trên tập dữ liệu rõ và thuần nhất. Trong thực tế, các kho dữ liệu nghiệp vụ thường xuyên tồn tại thông tin không chắc chắn, khái niệm mờ (như trẻ, rất trẻ, già, cao, thấp, lương khá, kinh tế chưa tốt) và sự kết hợp không thuần nhất giữa giá trị số với giá trị ngôn ngữ.
Lý thuyết tập mờ truyền thống của L. Zadeh tiếp cận vấn đề này thông qua các hàm thuộc, song tồn tại hạn chế nội tại: các hàm thuộc không so sánh được với nhau, việc gán nghĩa phụ thuộc ý kiến chủ quan của chuyên gia, quá trình xấp xỉ ngôn ngữ gây sai số lớn và thiếu cơ sở đại số để bảo toàn cấu trúc thứ tự tự nhiên của ngôn ngữ. Khi áp dụng vào cây quyết định, các phương pháp cây quyết định mờ (Fuzzy ID3, Fuzzy SLIQ) hay cây quyết định ngôn ngữ (LDT, LID3) thường làm bùng nổ số lượng nhánh tại các nút (phân chia đa phân), làm tăng chiều rộng hoặc chiều sâu cây, dẫn đến hiện tượng quá khớp (overfitting) và giảm độ chính xác dự đoán trên tập kiểm tra. Tiếp cận đại số gia tử (Hedge Algebra - ĐSGT) do N. Cat Ho và N. Wechler khởi xướng đã giải quyết được tính thứ tự ngữ nghĩa, song các phương pháp định lượng ngữ nghĩa theo điểm trước đây vẫn gặp khó khăn khi xử lý các giá trị ngôn ngữ ngoại lai (nằm ngoài miền trị $[Min, Max]$ của dữ liệu rõ) và sự đan xen tại các điểm phân chia mờ.
Từ những khoảng trống nghiên cứu trên, luận án tiến sĩ chuyên ngành Công nghệ thông tin thực hiện đề tài "Phân lớp dữ liệu bằng cây quyết định mờ dựa trên đại số gia tử".
Mục tiêu nghiên cứu của luận án gồm 2 mục tiêu chính:
- Xây dựng mô hình học phân lớp dữ liệu bằng cây quyết định mờ và phương pháp trích chọn đặc trưng để chọn tập mẫu huấn luyện cho quá trình học phân lớp. Đề xuất phương pháp xử lý giá trị ngôn ngữ của các thuộc tính chưa thuần nhất dựa vào đại số gia tử.
- Đề xuất các thuật toán học bằng cây quyết định mờ cho bài toán phân lớp nhằm đạt hiệu quả trong dự đoán và đơn giản đối với người dùng.
Mục tiêu tối ưu hóa của mô hình cây quyết định mờ $S: D \to Y$ được phát biểu dưới dạng toán học nhằm thỏa mãn đồng thời hai hàm mục tiêu:
- $f_h(S) \to \max$: Tối đa hóa khả năng dự đoán chính xác của mô hình cây quyết định trên tập dữ liệu kiểm tra.
- $f_n(S) \to \min$: Tối thiểu hóa số lượng nút trên cây kết quả nhằm đảm bảo tính đơn giản, dễ biểu diễn và dễ hiểu cho người dùng.
Đối tượng và phạm vi nghiên cứu:
- Đối tượng nghiên cứu: Mô hình học phân lớp bằng cây quyết định mờ, lý thuyết đại số gia tử, cấu trúc thứ tự và độ đo tính mờ của các giá trị ngôn ngữ, phương pháp trích chọn tập mẫu đặc trưng, các thuật toán học cây quyết định trên tập dữ liệu chứa thuộc tính mờ và không thuần nhất.
- Phạm vi nghiên cứu: Khai phá dữ liệu trên các kho dữ liệu nghiệp vụ; thử nghiệm và đối sánh thuật toán trên các bộ dữ liệu chuẩn không chứa giá trị mờ (Northwind) và các bộ dữ liệu chứa thuộc tính mờ (Mushroom, Adult).
Tổng quan tài liệu và vị trí của luận án
Luận án đã hệ thống hóa các công trình nghiên cứu liên quan đến lý thuyết tập mờ, đại số gia tử và các giải thuật cây quyết định:
- Lý thuyết tập mờ và biến ngôn ngữ: L. Zadeh (1965, 1975, 1979) đặt nền móng cho lý thuyết tập mờ, khái niệm phân hoạch mờ và biến ngôn ngữ $(X, T(X), U, R, M)$. Các tác giả Dubois, Prade, Mariana, Ishibuchi, Herrera, Yakun Hu tiếp tục phát triển ứng dụng trong điều khiển mờ, cơ sở dữ liệu mờ và khai phá dữ liệu mờ.
- Lý thuyết đại số gia tử: N. Wechler và N. Cat Ho (1990, 1993, 2007) đề xuất tiếp cận đại số cho miền giá trị của biến ngôn ngữ, xây dựng các cấu trúc đại số gia tử tuyến tính, đại số gia tử đầy đủ, hàm định lượng ngữ nghĩa và độ đo tính mờ. Hướng nghiên cứu này được mở rộng trong lập luận mờ, cơ sở dữ liệu mờ và phân lớp mờ bởi các công trình của N. Cat Ho, Lan và cộng sự.
- Cây quyết định kinh điển (dữ liệu rõ):
- Hướng tiếp cận dựa trên Entropy và tỷ lệ lợi ích thông tin (Gain Ratio): J. R. Quinlan, Breiman L., Friedman J., Shou-Hsiung Cheng, Yi Yang với các thuật toán ID3, C4.5, C5.0.
- Hướng tiếp cận dựa trên hệ số Gini và tỷ lệ Gini (Gini Split Index): Manish Mehta, Jorma Rissanen, Rakesh Agrawal, Narasimha Prasad, Mannava Munirathnam Naidu, Zhihao Wang, Junfang Wang, Yonghua Huo, Hongze Qiu, Haitang Zhang với các thuật toán CART, SLIQ, SPRINT.
- Cây quyết định mờ và cây quyết định ngôn ngữ:
- Kết hợp tập mờ và cây quyết định: A. Abraham, James F. Peters, S. Moustakidis, Daveedu Raju Adidela, Jaya Suma với các thuật toán Fuzzy ID3, Fuzzy SLIQ, Fuzzy HSM.
- Cây quyết định ngôn ngữ (Linguistic Decision Tree - LDT): Suzan Kantarci-Savas, Efendi Nasibov, Zengchang Qin, Jonathan Lawry, Yongchuan Tang với các thuật toán LID3 Uniform, LID3 Entropy, LID3 Percentile.
- Khoảng trống nghiên cứu luận án lựa chọn giải quyết:
- Các thuật toán học quy nạp rõ (C4.5, SLIQ, SPRINT) thường bỏ qua bản ghi chứa giá trị ngôn ngữ hoặc phụ thuộc vào việc gán nhãn thủ công của chuyên gia; cách chia $k$-phân cố định trên thuộc tính rời rạc gây bùng nổ số nút (cây dàn trải theo chiều ngang), còn chia nhị phân thuần túy theo Gini làm tăng độ sâu và chi phí tính toán.
- Cây quyết định ngôn ngữ (LID3) thiếu cấu trúc thứ tự giữa các giá trị ngôn ngữ nên phải phân chia đa phân tại các nút mờ, không áp dụng được cơ chế phân chia nhị phân linh hoạt.
- Tiếp cận ĐSGT theo phương pháp định lượng điểm trước đây chỉ xử lý các giá trị ngôn ngữ cùng mức gia tử, bỏ qua các giá trị khác mức; khó dự đoán khi có sự đan xen tại điểm chia mờ; và phụ thuộc chặt vào việc tồn tại miền trị $[Min, Max]$ của dữ liệu rõ, không xử lý được các giá trị ngôn ngữ ngoại lai.
- Thiếu một giải pháp tự động lọc bỏ các thuộc tính gây nhiễu, thuộc tính khóa, thuộc tính ghi nhớ và phụ thuộc hàm trước khi huấn luyện cây.
Cơ sở lý thuyết và phương pháp nghiên cứu
Cơ sở lý thuyết
Luận án vận dụng các cơ sở lý thuyết toán học và khoa học máy tính:
-
Lý thuyết tập mờ và phân hoạch mờ:
- Tập mờ $A$ trên vũ trụ $V \neq \emptyset$ được xác định bởi hàm thuộc $\mu_A(x): V \to [0, 1]$.
- Tập mờ hữu hạn biểu diễn dạng $A = \sum_{i=1}^n \frac{\mu_A(x_i)}{x_i}$; vô hạn biểu diễn dạng $A = \int_V \frac{\mu_A(x)}{x}$.
- Phân hoạch mờ $\Phi = {A_1, A_2, \dots, A_p}$ trên $V = [a, b] \subset \mathbb{R}$ thỏa mãn các điều kiện về điểm nhân $\mu_{A_k}(m_k) = 1$, tính liên tục ngoài đoạn $[m_{k-1}, m_{k+1}]$ bằng 0 và mọi điểm đều có độ thuộc khác không vào ít nhất một lớp.
- Biến ngôn ngữ là bộ 5 thành phần $(X, T(X), U, R, M)$ với tính phổ quát và tính độc lập ngữ cảnh của gia tử và liên từ.
-
Đại số gia tử (Hedge Algebra):
- Cấu trúc ĐSGT tuyến tính: $\mathcal{X} = (X, G, H, \le)$, trong đó $G = {0, c^-, W, c^+, 1}$ với $c^-$ là phần tử sinh âm, $c^+$ là phần tử sinh dương, $W$ là phần tử trung hòa; $H = H^+ \cup H^-$ là tập các gia tử dương ($H^+$) và gia tử âm ($H^-$).
- ĐSGT tuyến tính đầy đủ bổ sung hai toán tử cận trên đúng $\lceil x \rceil = \sup H(x)$ và cận dưới đúng $\lfloor x \rfloor = \inf H(x)$.
- Độ dài hạng từ $x \in X$, ký hiệu $l(x)$ hoặc $|x|$: $|c^+| = |c^-| = 1$; $|hx'| = 1 + |x'|$ với mọi $h \in H$.
- Hàm định lượng ngữ nghĩa $v: X \to [0, 1]$, hàm đo tính mờ $fm: X \to [0, 1]$ thỏa mãn:
$$\sum_{i=-q, i \neq 0}^p fm(h_i c) = fm(c)$$
$$\mu(h) = \frac{fm(hx)}{fm(x)}$$
- Hàm dấu $Sign(x) \in {-1, 0, 1}$ xác định tính tương thích hoặc nghịch hướng của các gia tử liên tiếp.
- Khái niệm khoảng mờ $I(x) = [\lfloor x \rfloor, \lceil x \rceil] \subseteq [0, 1]$ với độ dài $|I(x)| = fm(x)$. Phân hoạch mức $k$: $P_k = {I(x) : x \in X_k}$. Mối tương quan đối sánh khoảng mờ khi xét giao đoạn $|I(y) \cap I(x)| \ge |I(y)| / \ell$.
-
Lý thuyết phân lớp và cây quyết định:
- Phát biểu hình thức: Cho tập thuộc tính $U = {A_1, A_2, \dots, A_m}$, tập nhãn lớp $Y = {y_1, y_2, \dots, y_n}$, tập mẫu $D = A_1 \times \dots \times A_m$. Xây dựng cây quyết định đóng vai trò ánh xạ $S: D \to Y$.
- Thuộc tính mờ $A_i$ có miền trị $Dom(A_i) = D_{A_i} \cup LD_{A_i}$, gồm miền giá trị kinh điển $D_{A_i}$ và miền giá trị ngôn ngữ $LD_{A_i}$.
- Công thức Entropy của tập $D$ đối với thuộc tính quyết định $Y$:
$$E(Y, D) = \sum_{i=1}^n -p_i \log_2 p_i$$
- Entropy khi phân lớp trên thuộc tính $A_i$ chia $D$ thành $m$ tập con $D_1, \dots, D_m$:
$$E(A_i, D) = \sum_{j=1}^m \frac{|D_j|}{|D|} E(D_j)$$
- Lợi ích thông tin: $Gain(A_i, D) = E(Y, D) - E(A_i, D)$.
- Tỷ lệ lợi ích thông tin: $GainRatio(A_i, D) = \frac{Gain(A_i, D)}{SplitInfo(A_i, D)}$.
- Hệ số Gini của tập $D$:
$$Gini(D) = 1 - \sum_{i=1}^n p_i^2$$
- Tỷ lệ hệ số Gini khi chia tách tập $D$ thành $D_1, D_2$:
$$Gini(D)_{Split} = \frac{|D_1|}{|D|} Gini(D_1) + \frac{|D_2|}{|D|} Gini(D_2)$$
Phương pháp nghiên cứu
- Phương pháp nghiên cứu tài liệu, tổng hợp và hệ thống hóa: Khảo cứu các công bố khoa học về cây quyết định và đại số gia tử; phân tích các hạn chế của mô hình ID3, C4.5, SPRINT, SLIQ và các mô hình cây quyết định mờ/ngôn ngữ.
- Phương pháp mô hình hóa và hình thức hóa toán học: Xây dựng các định nghĩa, mệnh đề, định lý về thuộc tính riêng biệt, thuộc tính ghi nhớ, phụ thuộc hàm, đối sánh khoảng mờ và khoảng mờ lớn nhất; thiết kế các thuật toán MixC4.5, MixC4.5*, HAC4.5, HAC4.5*.
- Phương pháp thực nghiệm khoa học: Cài đặt chương trình thử nghiệm bằng ngôn ngữ Java trên nền tảng Eclipse Mars Release 4.50; môi trường phần cứng máy tính CPU Intel Core i5-2450 @ 2.50 GHz, RAM 4GB, hệ điều hành 64-bit.
Nguồn tư liệu và dữ liệu thực nghiệm
- Cơ sở dữ liệu mẫu nghiệp vụ DIEUTRA (khảo sát sử dụng máy tính xách tay của nhân viên).
- Cơ sở dữ liệu Northwind: Tập dữ liệu kinh điển không chứa giá trị mờ, gồm 2.155 bản ghi trích từ các bảng Customers, Products, Orders, OrderDetails; sử dụng các tập huấn luyện 1.000 và 1.500 bản ghi, tập kiểm tra 500 bản ghi.
- Cơ sở dữ liệu Mushroom: Tập dữ liệu sinh học gồm 8.000 bản ghi, 23 thuộc tính (trong đó có 2 thuộc tính mờ là Population và Habitat); sử dụng tập huấn luyện 5.000 bản ghi, tập kiểm tra 500 và 1.000 bản ghi.
- Cơ sở dữ liệu Adult: Bộ dữ liệu chuẩn có chứa thông tin mờ dùng để thử nghiệm và đối sánh các giải thuật dựa trên khoảng mờ.
Nội dung chính theo từng chương
Chương 1: Cơ sở lý thuyết về đại số gia tử và tổng quan phân lớp dữ liệu bằng cây quyết định
Chương 1 hệ thống hóa cơ sở lý thuyết và tổng quan tình hình nghiên cứu bài toán phân lớp:
- Lý thuyết tập mờ và biến ngôn ngữ: Phân tích bản chất của thông tin mờ, cấu trúc biến ngôn ngữ 5 thành phần, phép gán ngữ nghĩa $M$ từ giá trị ngôn ngữ sang tập mờ trên không gian tham chiếu $U$. Chỉ ra hạn chế của hàm thuộc khi không thể so sánh trực tiếp các giá trị ngôn ngữ và sự phụ thuộc vào tính chủ quan của chuyên gia.
- Đại số gia tử và các hàm đo: Trình bày cấu trúc đại số gia tử tuyến tính đầy đủ $\mathcal{X} = (X, G, H, \le, \lceil \cdot \rceil, \lfloor \cdot \rfloor)$, định nghĩa gia tử âm/dương, tính tương thích, độ dài hạng từ. Trình bày các định lý về thứ tự ngữ nghĩa tự nhiên của các hạng từ trong ĐSGT, hàm định lượng ngữ nghĩa $v(x)$, hàm đo tính mờ $fm(x)$, hàm dấu $Sign(x)$, hàm ngược $v^{-1}_k(a)$ theo phân hoạch mức $k$, và cấu trúc phân hoạch của khoảng mờ $I(x) = [\lfloor x \rfloor, \lceil x \rceil]$.
- Bài toán phân lớp dữ liệu bằng cây quyết định rõ: Trình bày 3 giai đoạn của quá trình học cây (tạo cây đệ quy, cắt tỉa cây, kiểm định cây kết quả). Phân tích chi tiết các kỹ thuật chọn thuộc tính dựa trên Entropy, Gain, GainRatio (họ thuật toán ID3, C4.5) và chỉ số Gini, GiniSplitIndex (họ thuật toán CART, SLIQ, SPRINT).
- Hiện tượng quá khớp và cây dàn trải: Định nghĩa cây dàn trải là cây tồn tại nút có số nhánh phân chia lớn hơn chiều cao của cây. Phân tích nguyên nhân gây quá khớp do dữ liệu nhiễu, số mẫu nhỏ hoặc phân chia $k$-phân quá mức trên thuộc tính rời rạc.
- Phân lớp dữ liệu bằng cây quyết định mờ: Phát biểu bài toán phân lớp mờ tổng quát $S: D \to Y$ với miền thuộc tính chứa cả giá trị rõ và giá trị ngôn ngữ $Dom(A_i) = D_{A_i} \cup LD_{A_i}$. Thiết lập hai hàm mục tiêu $f_h(S) \to \max$ và $f_n(S) \to \min$.
- Đánh giá các hướng tiếp cận cây quyết định mờ hiện nay:
- Tiếp cận tập mờ (Fuzzy ID3, Fuzzy SLIQ): Khắc phục việc bỏ qua dữ liệu mờ nhưng gặp hạn chế do hàm thuộc không so sánh được, sai số xấp xỉ lớn.
- Tiếp cận cây quyết định ngôn ngữ (LDT, LID3): Gây phân chia đa phân theo chiều ngang, tăng nguy cơ quá khớp, không áp dụng được phân chia nhị phân.
- Tiếp cận ĐSGT theo điểm: Khắc phục việc so sánh ngữ nghĩa, nhưng chỉ áp dụng trên cùng một mức gia tử, khó dự đoán khi có sự đan xen ở điểm phân chia mờ và phụ thuộc vào miền trị $[Min, Max]$ của dữ liệu rõ có sẵn.
Chương 2: Phân lớp dữ liệu bằng cây quyết định mờ theo phương pháp đối sánh điểm mờ dựa trên đại số gia tử
Chương 2 tập trung phân tích sự ảnh hưởng của tập mẫu huấn luyện, đề xuất phương pháp chọn mẫu đặc trưng và xây dựng thuật toán MixC4.5:
-
Phân tích sự ảnh hưởng của tập mẫu huấn luyện:
- Thuộc tính có giá trị riêng biệt ($D^$):* Thuộc tính rời rạc $A_i$ thỏa mãn $|A_i| > (m - 1) \times |Y|$ (với $m$ là số thuộc tính, $|Y|$ là số lớp quyết định). Luận án chứng minh: Nếu tạo nút ứng với thuộc tính riêng biệt thì cây sinh ra là cây dàn trải.
- Thuộc tính ghi nhớ ($D_G$): Thuộc tính mà giữa các phần tử không sánh được với nhau. Luận án chứng minh: Loại bỏ thuộc tính ghi nhớ ra khỏi tập mẫu không làm thay đổi cây quyết định thu được do $Gain(A_i, D)$ không xác định.
- Thuộc tính khóa: Luận án chứng minh nếu tập mẫu chứa thuộc tính khóa thì cây quyết định luôn bị quá khớp tại nút đó vì $E(A_i, D) = 0$ và $Gain(A_i, D)$ đạt cực đại nhưng giá trị mang tính duy nhất, không có khả năng dự đoán.
- Ảnh hưởng của phụ thuộc hàm: Luận án chứng minh: Nếu có phụ thuộc hàm $A_i \to A_j$ và $A_i$ được chọn làm nút phân tách thì mọi nút con sẽ không nhận $A_j$ làm nút phân tách; lượng thông tin $Gain(A_i, D) \ge Gain(A_j, D)$. Hệ quả: Nếu $A_1 \to A_2$ mà $A_1$ không phải là khóa thì $A_2$ bị loại khỏi tập mẫu huấn luyện.
-
Thuật toán tìm tập huấn luyện đặc trưng từ dữ liệu mẫu:
- Duyệt loại bỏ các thuộc tính thuộc nhóm Khóa và Ghi nhớ: $D = D \setminus {A_i}$.
- Duyệt kiểm tra các cặp phụ thuộc hàm: Nếu $A_i \to A_j$ (hoặc ngược lại) với thuộc tính vế trái không phải là khóa, loại bỏ thuộc tính phụ thuộc ra khỏi $D$.
- Độ phức tạp tính toán của thuật toán là $O(m^2)$ với $m$ là số thuộc tính.
-
Thuật toán MixC4.5:
- Cơ chế hoạt động: Kết hợp linh hoạt cơ chế phân chia của C4.5 và SPRINT dựa trên ngưỡng $k = (m - 1) \times |Y|$.
- Với thuộc tính liên tục: Phân chia nhị phân theo ngưỡng $T$ có $Gain$ lớn nhất theo C4.5.
- Với thuộc tính rời rạc: Nếu lực lượng $|A_i| < k$, phân chia $k$-phân theo C4.5; nếu $|A_i| \ge k$, chuyển sang phân chia nhị phân theo giá trị có $Gain$ lớn nhất theo SPRINT.
- Độ phức tạp của thuật toán: $O(m^2 \cdot n) + O(m \cdot n^2 \log n)$ (trong đó $m$ là số thuộc tính, $n$ là số bản ghi).
-
Xử lý giá trị ngôn ngữ ngoại lai và thuần nhất dữ liệu:
- Đưa ra khái niệm giá trị ngôn ngữ ngoại lai là các giá trị ngôn ngữ có giá trị thực nằm ngoài miền trị $[Min, Max]$ của dữ liệu rõ hiện có.
- Đề xuất thuật toán thuần nhất miền trị dựa trên ĐSGT và thuật toán FMixC4.5 cho tập huấn luyện mờ.
-
Dữ liệu và kết quả thực nghiệm đối sánh thuật toán:
| STT |
Tên trường (CSDL Northwind) |
Lực lượng |
Kiểu thuộc tính |
Miền trị |
| 1 |
Customers.CompanyName |
91 |
Rời rạc |
- |
| 2 |
Customers.ContactName |
91 |
Rời rạc |
- |
| 3 |
Customers.ContactTitle |
12 |
Rời rạc |
- |
| 4 |
Customers.City |
69 |
Rời rạc |
- |
| 5 |
Customers.Region |
19 |
Rời rạc |
- |
| 6 |
Customers.Phone |
91 |
Rời rạc |
- |
| 7 |
Products.ProductName |
77 |
Rời rạc |
- |
| 8 |
Products.SupplierID |
29 |
Rời rạc |
- |
| 9 |
Products.CategoryID |
8 |
Rời rạc |
- |
| 10 |
Products.QuantityPerUnit |
70 |
Rời rạc |
- |
| 11 |
Products.UnitPrice |
62 |
Liên tục |
[2.5, 263.5] |
| 12 |
Products.UnitsInStock |
51 |
Liên tục |
[0, 125] |
| 13 |
Products.UnitsOnOrder |
10 |
Liên tục |
[0, 100] |
| 14 |
Products.ReorderLevel |
7 |
Liên tục |
[0, 30] |
| 15 |
Products.Discontinued |
2 |
Logic |
- |
| 16 |
Orders.CustomerID |
89 |
Rời rạc |
- |
| 17 |
Orders.EmployeeID |
9 |
Liên tục |
[1, 9] |
| 18 |
Orders.OrderDate |
480 |
Rời rạc |
- |
| 19 |
Orders.RequiredDate |
454 |
Rời rạc |
- |
| 20 |
Orders.ShippedDate |
388 |
Rời rạc |
- |
| 21 |
Orders.Freight |
79 |
Liên tục |
[0.02, 890.78] |
| 22 |
Orders.ShipCity |
70 |
Rời rạc |
- |
| 23 |
Orders.ShipRegion |
20 |
Rời rạc |
- |
| 24 |
OrderDetails.ProductID |
77 |
Liên tục |
[1, 77] |
| 25 |
OrderDetails.UnitPrice |
116 |
Liên tục |
[2, 263.5] |
| 26 |
OrderDetails.Quantity |
55 |
Liên tục |
[1, 130] |
| 27 |
OrderDetails.Discount |
11 |
Liên tục |
[0, 0.25] |
| STT |
Tên trường (CSDL Mushroom) |
Lực lượng |
Kiểu thuộc tính |
Miền trị |
| 1 |
Bruises |
2 |
Rời rạc |
- |
| 2 |
Capshape |
6 |
Rời rạc |
- |
| 3 |
CapSurface |
4 |
Rời rạc |
- |
| 4 |
CapColor |
10 |
Rời rạc |
- |
| 5 |
Odor |
9 |
Rời rạc |
- |
| 6 |
GillAttachment |
2 |
Rời rạc |
- |
| 7 |
GillSpacing |
2 |
Rời rạc |
- |
| 8 |
GillSize |
2 |
Rời rạc |
- |
| 9 |
GillColor |
12 |
Rời rạc |
- |
| 10 |
StalkShape |
2 |
Rời rạc |
- |
| 11 |
StalkRoot |
5 |
Rời rạc |
- |
| 12 |
StalkSurfaceAboveRing |
4 |
Rời rạc |
- |
| 13 |
StalkSurfaceBelowRing |
4 |
Rời rạc |
- |
| 14 |
StalkColorAboveRing |
9 |
Logic |
- |
| 15 |
StalkColorBelowRing |
9 |
Rời rạc |
- |
| 16 |
VeilType |
9 |
Rời rạc |
- |
| 17 |
VeilColor |
4 |
Rời rạc |
- |
| 18 |
RingNumber |
3 |
Rời rạc |
- |
| 19 |
RingType |
5 |
Rời rạc |
- |
| 20 |
SporePrintColor |
9 |
Rời rạc |
- |
| 21 |
Population |
62 |
Mờ |
Rõ: [1, 50] |
| 22 |
Habitat |
126 |
Mờ |
Rõ: [20, 90] |
| 23 |
Classes |
2 |
Logic |
- |
Kết quả thực nghiệm so sánh thuật toán MixC4.5 trên CSDL Northwind và Mushroom:
Bảng so sánh kết quả huấn luyện với 1.000 mẫu trên CSDL Northwind (kiểm tra trên 500 mẫu):
- C4.5: Thời gian 1.25s, Tổng số nút 27, Độ chính xác 81.2%
- SLIQ: Thời gian 3.82s, Tổng số nút 45, Độ chính xác 80.4%
- SPRINT: Thời gian 2.15s, Tổng số nút 31, Độ chính xác 83.6%
- MixC4.5: Thời gian 1.84s, Tổng số nút 23, Độ chính xác 86.8%
Bảng so sánh kết quả huấn luyện với 1.500 mẫu trên CSDL Northwind (kiểm tra trên 500 mẫu):
- C4.5: Thời gian 1.98s, Tổng số nút 39, Độ chính xác 82.4%
- SLIQ: Thời gian 5.46s, Tổng số nút 61, Độ chính xác 81.0%
- SPRINT: Thời gian 3.12s, Tổng số nút 43, Độ chính xác 84.2%
- MixC4.5: Thời gian 2.65s, Tổng số nút 31, Độ chính xác 88.6%
Bảng so sánh kết quả trên CSDL Mushroom (5.000 mẫu huấn luyện):
- C4.5: Thời gian 4.12s; Độ chính xác (500 mẫu kiểm tra) 91.2%; Độ chính xác (1.000 mẫu kiểm tra) 90.4%
- SLIQ: Thời gian 11.35s; Độ chính xác (500 mẫu kiểm tra) 89.6%; Độ chính xác (1.000 mẫu kiểm tra) 88.8%
- SPRINT: Thời gian 6.48s; Độ chính xác (500 mẫu kiểm tra) 92.4%; Độ chính xác (1.000 mẫu kiểm tra) 91.8%
- MixC4.5: Thời gian 5.12s; Độ chính xác (500 mẫu kiểm tra) 95.8%; Độ chính xác (1.000 mẫu kiểm tra) 95.2%
Chương 3: Phương pháp huấn luyện cây quyết định mờ cho bài toán phân lớp dữ liệu dựa trên đối sánh khoảng mờ
Chương 3 giải quyết bài toán tối ưu hóa đồng thời $f_h(S) \to \max$ và $f_n(S) \to \min$ dựa trên lý thuyết khoảng mờ của ĐSGT:
- Phương pháp đối sánh dựa trên khoảng mờ: Luận án xây dựng cơ chế đối sánh ngữ nghĩa dựa trên sự giao thoa giữa các khoảng mờ $I(x)$ thay vì quy đổi về một điểm số cố định, cho phép định lượng các giá trị của thuộc tính không thuần nhất khi chưa xác định được biên $[Min, Max]$ của tập huấn luyện.
- Thuật toán HAC4.5: Sử dụng quan hệ đối sánh khoảng mờ để lựa chọn điểm phân tách tại các nút mờ, hướng tới mục tiêu tối đa hóa độ chính xác dự đoán ($f_h(S) \to \max$).
- Khái niệm khoảng mờ lớn nhất và thuật toán HAC4.5*: Đề xuất khái niệm khoảng mờ lớn nhất để gộp các nhánh mờ có độ đo tương đồng, giảm thiểu sự phân nhánh dư thừa, từ đó đạt được mục tiêu kép: tăng độ chính xác ($f_h(S) \to \max$) và thu gọn kích thước cây ($f_n(S) \to \min$).
- Thực nghiệm và đánh giá: Cài đặt thử nghiệm các thuật toán HAC4.5 và HAC4.5* trên cơ sở dữ liệu Mushroom và Adult, đối sánh về thời gian huấn luyện, số lượng nút của cây kết quả và tỷ lệ phân lớp chính xác.
Kết quả và những đóng góp mới
Đóng góp về mặt khoa học và lý luận
- Xây dựng mô hình học phân lớp dữ liệu bằng cây quyết định mờ linh hoạt từ tập mẫu huấn luyện. Đề xuất phương pháp trích chọn đặc trưng dựa trên các tính chất toán học của thuộc tính khóa, thuộc tính ghi nhớ và phụ thuộc hàm nhằm loại bỏ nhiễu và hạn chế sự phụ thuộc vào chuyên gia khi chuẩn bị dữ liệu.
- Đề xuất phương pháp xử lý và thuần nhất giá trị ngôn ngữ của các thuộc tính không thuần nhất dựa trên bản chất đại số gia tử, giải quyết được bài toán định lượng cho các giá trị ngôn ngữ ngoại lai nằm ngoài miền $[Min, Max]$ của dữ liệu rõ.
- Thiết lập hệ hàm mục tiêu hình thức ($f_h(S) \to \max$, $f_n(S) \to \min$), đưa ra khái niệm đối sánh khoảng mờ và khoảng mờ lớn nhất; đề xuất các thuật toán MixC4.5, MixC4.5*, HAC4.5 và HAC4.5*, góp phần hoàn thiện lý thuyết học quy nạp cây quyết định mờ.
Đóng góp về mặt thực tiễn
- Minh chứng khả năng ứng dụng hiệu quả của lý thuyết đại số gia tử trong bài toán khai phá dữ liệu thực tế trên các kho dữ liệu nghiệp vụ có cấu trúc hỗn hợp.
- Cung cấp các giải thuật cây quyết định có độ chính xác dự đoán cao hơn và số nút cây nhỏ hơn so với C4.5, SLIQ, SPRINT trên các tập dữ liệu thực nghiệm.
- Kết quả luận án đóng vai trò tài liệu tham khảo chuyên sâu cho sinh viên đại học, học viên cao học và nghiên cứu sinh chuyên ngành Công nghệ thông tin trong lĩnh vực khai phá dữ liệu và trí tuệ nhân tạo.
Danh mục công trình khoa học đã công bố của tác giả
Các kết quả nghiên cứu trong luận án được công bố trong 7 công trình khoa học:
- 01 bài báo tại Tạp chí Khoa học và Công nghệ - Trường Đại học Khoa học Huế.
- 01 bài báo tại Tạp chí Khoa học Đại học Huế.
- 01 bài báo tại Kỷ yếu Hội thảo quốc gia Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR).
- 02 bài báo tại Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ thông tin và Truyền thông (Tạp chí Thông tin, Khoa học và Công nghệ - Bộ Thông tin và Truyền thông).
- 01 bài báo tại Tạp chí Tin học và Điều khiển học (Journal of Computer Science and Cybernetics).
- 01 bài báo quốc tế tại International Journal of Research in Engineering and Science (IJRES).
Hạn chế và hướng nghiên cứu tiếp
Hạn chế
- Quá trình thực nghiệm của luận án tập trung trên các cơ sở dữ liệu mẫu chuẩn (Northwind, Mushroom, Adult).
- Chi phí tính toán của thuật toán MixC4.5 khi rơi vào trường hợp thuộc tính vượt ngưỡng $k$ phải duyệt nhị phân theo SPRINT có độ phức tạp $O(m \cdot n^2 \log n)$, đòi hỏi tài nguyên tính toán lớn hơn so với C4.5 thuần túy.
Hướng nghiên cứu tiếp
- Mở rộng thử nghiệm các thuật toán MixC4.5* và HAC4.5* trên các kho dữ liệu nghiệp vụ thực tế có quy mô lớn hơn (Big Data) và các luồng dữ liệu thời gian thực (Data Streams).
- Nghiên cứu tối ưu hóa hiệu năng tính toán của thuật toán đối sánh khoảng mờ trên môi trường tính toán song song và phân tán.
Giá trị tham khảo
Luận án có giá trị tham khảo chuyên môn đối với:
- Nghiên cứu sinh, học viên cao học, sinh viên ngành Công nghệ thông tin, Khoa học dữ liệu, Trí tuệ nhân tạo: Tham khảo mô hình toán học của đại số gia tử, phương pháp tính toán độ đo tính mờ, hàm định lượng ngữ nghĩa và kỹ thuật thiết kế giải thuật phân lớp cây quyết định.
- Giảng viên và nhà nghiên cứu: Sử dụng làm tài liệu giảng dạy chuyên đề khai phá dữ liệu mờ, logic mờ và lập luận xấp xỉ.
- Kỹ sư phát triển hệ thống và chuyên viên phân tích dữ liệu: Vận dụng thuật toán trích chọn mẫu đặc trưng ($O(m^2)$) để tiền xử lý kho dữ liệu nghiệp vụ, và áp dụng cơ chế phân chia ngưỡng linh hoạt của thuật toán MixC4.5 để giảm hiện tượng quá khớp trong các bài toán dự đoán thực tế.
Câu hỏi thường gặp
1. Cơ chế xác định ngưỡng phân chia $k$ trong thuật toán MixC4.5 được thiết lập như thế nào?
Ngưỡng $k$ được xác định bằng công thức $k = (m - 1) \times |Y|$, trong đó $m$ là số thuộc tính của tập dữ liệu và $|Y|$ là số lớp của thuộc tính quyết định. Nếu lực lượng của thuộc tính rời rạc $|A_i| < k$, thuật toán áp dụng phân chia $k$-phân theo C4.5 nhằm tận dụng ưu điểm tốc độ xử lý nhanh; nếu $|A_i| \ge k$, thuật toán chuyển sang phân chia nhị phân theo giá trị có $Gain$ lớn nhất theo SPRINT để ngăn chặn tình trạng cây dàn trải theo chiều ngang gây quá khớp.
2. Tại sao các thuộc tính khóa, thuộc tính ghi nhớ và phụ thuộc hàm lại bị loại bỏ trong giai đoạn chọn tập mẫu đặc trưng?
Thuộc tính khóa làm cho mỗi phân hoạch chỉ chứa 1 bộ dữ liệu, khiến $E(A_i, D) = 0$ và $Gain$ đạt cực đại giả tạo, tạo ra cây dàn trải và quá khớp hoàn toàn mà không có khả năng dự đoán. Thuộc tính ghi nhớ không thể so sánh giữa các phần tử nên không tính được $Gain$. Đối với phụ thuộc hàm $A_i \to A_j$, lượng thông tin nhận được trên $A_i$ luôn lớn hơn hoặc bằng $A_j$, và khi đã phân tách theo $A_i$ thì $Gain$ trên $A_j$ tại các nút con bằng 0, do đó $A_j$ trở nên dư thừa.
3. Phương pháp đối sánh khoảng mờ trong ĐSGT giải quyết nhược điểm gì của phương pháp định lượng điểm?
Phương pháp định lượng điểm quy toàn bộ một đoạn giá trị thực về một điểm giá trị ngôn ngữ tương ứng và thường chỉ áp dụng cho các giá trị có cùng mức gia tử, dẫn đến sai số lớn và khó dự đoán khi có sự đan xen tại điểm chia mờ. Phương pháp đối sánh khoảng mờ dựa trên các đoạn con $I(x) = [\lfloor x \rfloor, \lceil x \rceil]$, cho phép đối sánh ngữ nghĩa liên tục trên toàn không gian, xử lý bình đẳng các giá trị ngôn ngữ khác mức gia tử và không phụ thuộc vào việc xác định trước miền trị $[Min, Max]$ của dữ liệu rõ.
4. Hai hàm mục tiêu $f_h(S)$ và $f_n(S)$ trong bài toán phân lớp dữ liệu mờ có mối quan hệ như thế nào?
Hai hàm mục tiêu này có xu hướng nghịch biến và đòi hỏi sự thỏa hiệp trong tối ưu hóa: $f_h(S)$ đánh giá khả năng dự đoán chính xác của cây ($f_h(S) \to \max$), còn $f_n(S)$ đo lường số lượng nút trên cây ($f_n(S) \to \min$). Khi giảm số nút $f_n(S)$, mô hình trở nên đơn giản hơn nhưng nguy cơ mất tri thức và tăng sai số phân lớp; ngược lại, khi cây có quá nhiều nút, tính cá thể tăng cao dẫn đến hiện tượng quá khớp và suy giảm độ chính xác $f_h(S)$ trên tập kiểm tra.
5. Cấu hình thực nghiệm và kết quả đo đạc độ chính xác của thuật toán MixC4.5 trên CSDL Northwind ra sao?
Chương trình thực nghiệm được cài đặt bằng Java trên môi trường Eclipse Mars Release 4.50 (CPU Intel Core i5-2450 @ 2.50 GHz, RAM 4GB, hệ điều hành 64-bit). Với 1.500 mẫu huấn luyện trên CSDL Northwind (kiểm tra trên 500 mẫu), MixC4.5 đạt độ chính xác 88.6% với tổng số 31 nút trong thời gian 2.65 giây, vượt trội hơn so với C4.5 (82.4%, 39 nút, 1.98s), SLIQ (81.0%, 61 nút, 5.46s) và SPRINT (84.2%, 43 nút, 3.12s).
Kết luận
Luận án đã giải quyết bài toán phân lớp dữ liệu mờ và dữ liệu không thuần nhất thông qua việc kết hợp mô hình cây quyết định với lý thuyết đại số gia tử. Tác giả đã xây dựng thuật toán chọn tập mẫu huấn luyện đặc trưng với độ phức tạp $O(m^2)$, thiết kế giải thuật MixC4.5 kết hợp ngưỡng phân chia linh hoạt giữa C4.5 và SPRINT, đồng thời đề xuất các thuật toán HAC4.5 và HAC4.5* dựa trên đối sánh khoảng mờ và khoảng mờ lớn nhất. Các kết quả thực nghiệm trên các bộ dữ liệu Northwind, Mushroom và Adult đã chứng minh tính hiệu quả của các giải thuật đề xuất trong việc nâng cao độ chính xác dự đoán, kiểm soát hiện tượng quá khớp và tối ưu hóa số lượng nút trên cây quyết định.
