Luận Văn Thạc Sĩ Về Cây Quyết Định Phân Lớp Dữ Liệu Mất Cân Đối

Luận văn thạc sĩ nghiên cứu sử dụng cây quyết định phân lớp dữ liệu mất cân đối, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện thực tiễn.

• Tác giả: Lê Thanh Phong
• Người hướng dẫn: PGS. Lê Hoài Bắc
• Trường học: Trường Đại Học Ngoại Ngữ Tin Học Thành Phố Hồ Chí Minh
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Sử Dụng Cây Quyết Định Phân Lớp Dữ Liệu Mất Cân Đối
• Loại tài liệu: Luận Văn Thạc Sỹ
• Năm xuất bản: 2018
• Địa điểm: Thành Phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• DANH MỤC VIẾT TẮT
• DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
• DANH MỤC CÁC BẢNG BIỂU
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Đặt vấn đề
• 1.2. Cơ sở hình thành đề tài
• 1.3. Các nghiên cứu liên quan
• 1.4. Mục tiêu của luận văn
• 1.5. Đối tượng nghiên cứu
• 1.6. Các phương pháp nghiên cứu
• 1.6.1. Phương pháp nghiên cứu tài liệu
• 1.6.2. Phương pháp thực nghiệm
• 1.6.3. Phương pháp thống kê, phân tích dữ liệu
• 1.7. Nội dung và phạm vi của luận văn
• 1.8. Ý nghĩa của luận văn
• 1.8.1. Ý nghĩa khoa học
• 1.8.2. Ý nghĩa thực tiễn
• 1.9. Bố cục luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Tổng quan về khai thác dữ liệu
• 2.1.1. Khai thác dữ liệu là gì?
• 2.1.2. Quá trình khai thác dữ liệu
• 2.1.3. Khai thác dữ liệu sử dụng phân lớp
• 2.1.4. Khai thác dữ liệu sử dụng luật kết hợp
• 2.1.5. Khai thác dữ liệu sử dụng cây quyết định
• 3. CHƯƠNG 3: PHÂN LỚP DỮ LIỆU MẤT CÂN ĐỐI BẰNG CÂY QUYẾT ĐỊNH
• 3.1. Đường cong Receiver Operating Characteristic (ROC)
• 3.2. Diện tích dưới đường cong ROC
• 3.3. Độ đo đánh giá hiệu suất phân lớp
• 3.4. Thuật toán AUC4.5
• 3.4.1. Ý tưởng chính thuật toán AUC4.5
• 3.4.2. Một số giải thuật chính
• 3.5. Ví dụ minh hoạ cho thuật toán AUC4.5
• 3.5.1. Dữ liệu minh hoạ
• 3.5.2. Minh hoạ bằng thuật toán C4.5
• 3.5.3. Minh hoạ bằng thuật toán AUC4.5
• 4. CHƯƠNG 4: THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 4.1. Mô tả tập dữ liệu
• 4.2. Môi trường thực nghiệm
• 4.3. Kiểm chứng mô hình bằng phương pháp Hold-out
• 4.4. Kết quả thực nghiệm
• 4.4.1. Phương sai, độ lệch chuẩn
• 4.4.2. Kết quả tám tập dữ liệu sau khi kiểm tra tập DTest 10 lần
• 4.4.3. Phân tích trên từng tập dữ liệu
• 4.5. Đánh giá kết quả thực nghiệm
• 5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về Cây Quyết Định Phân Lớp Dữ Liệu Mất Cân Đối

Cây quyết định là một trong những mô hình phổ biến trong khai thác dữ liệu, đặc biệt là trong phân lớp dữ liệu mất cân đối. Mô hình này cho phép người dùng dễ dàng hiểu và giải thích các quyết định mà nó đưa ra. Trong bối cảnh dữ liệu mất cân đối, cây quyết định có thể gặp phải nhiều thách thức, đặc biệt là khi lớp thiểu số có số lượng mẫu rất ít so với lớp đa số. Việc nghiên cứu và cải tiến các thuật toán cây quyết định là cần thiết để nâng cao độ chính xác trong phân lớp.

1.1. Cây Quyết Định và Khái Niệm Phân Lớp Dữ Liệu

Cây quyết định là một cấu trúc dữ liệu dạng cây, trong đó mỗi nút nội bộ đại diện cho một thuộc tính, mỗi nhánh đại diện cho một giá trị của thuộc tính đó, và mỗi nút lá đại diện cho một lớp phân loại. Phân lớp dữ liệu là quá trình gán nhãn cho các mẫu dữ liệu dựa trên các thuộc tính của chúng.

1.2. Tầm Quan Trọng của Phân Lớp Dữ Liệu Mất Cân Đối

Dữ liệu mất cân đối thường xuất hiện trong nhiều lĩnh vực như y tế, tài chính và an ninh mạng. Việc phân lớp chính xác các mẫu thuộc lớp thiểu số là rất quan trọng, vì những mẫu này thường chứa thông tin quý giá và có thể ảnh hưởng lớn đến quyết định cuối cùng.

II. Thách Thức Trong Phân Lớp Dữ Liệu Mất Cân Đối

Phân lớp dữ liệu mất cân đối đặt ra nhiều thách thức cho các nhà nghiên cứu và thực hành. Một trong những vấn đề lớn nhất là độ chính xác của mô hình thường bị ảnh hưởng bởi sự chênh lệch lớn giữa số lượng mẫu của lớp đa số và lớp thiểu số. Điều này dẫn đến việc mô hình có xu hướng dự đoán lớp đa số nhiều hơn, làm giảm hiệu quả của việc phân lớp.

2.1. Vấn Đề Độ Chính Xác Trong Phân Lớp

Khi áp dụng các thuật toán phân lớp truyền thống, độ chính xác tổng thể có thể cao nhưng độ chính xác của lớp thiểu số lại rất thấp. Điều này không phản ánh đúng hiệu suất của mô hình trong việc phân loại các mẫu quan trọng.

2.2. Thiếu Dữ Liệu Lớp Thiểu Số

Sự thiếu hụt dữ liệu lớp thiểu số làm cho việc huấn luyện mô hình trở nên khó khăn. Các thuật toán thường không có đủ thông tin để học và phân loại chính xác các mẫu thuộc lớp này.

III. Phương Pháp Cải Tiến Cây Quyết Định Để Phân Lớp Dữ Liệu Mất Cân Đối

Để cải thiện hiệu suất của cây quyết định trong phân lớp dữ liệu mất cân đối, nhiều phương pháp đã được đề xuất. Các phương pháp này bao gồm điều chỉnh chi phí, sử dụng các thuật toán học máy nhạy cảm với chi phí, và áp dụng các kỹ thuật lấy mẫu để cân bằng dữ liệu.

3.1. Kỹ Thuật Lấy Mẫu Để Cân Bằng Dữ Liệu

Các kỹ thuật như Under-sampling và Over-sampling được sử dụng để điều chỉnh kích thước của các lớp trong tập dữ liệu. Under-sampling giảm số lượng mẫu lớp đa số, trong khi Over-sampling tăng số lượng mẫu lớp thiểu số.

3.2. Học Máy Nhạy Cảm Với Chi Phí

Học máy nhạy cảm với chi phí là một phương pháp điều chỉnh chi phí phân loại sai cho các lớp khác nhau. Bằng cách gán chi phí cao hơn cho lớp thiểu số, mô hình có thể được tối ưu hóa để cải thiện độ chính xác cho lớp này.

IV. Ứng Dụng Thực Tiễn Của Cây Quyết Định Trong Phân Lớp Dữ Liệu Mất Cân Đối

Cây quyết định đã được áp dụng thành công trong nhiều lĩnh vực khác nhau, từ y tế đến tài chính. Việc cải tiến các thuật toán cây quyết định giúp nâng cao khả năng phân lớp chính xác cho các mẫu thuộc lớp thiểu số, từ đó cải thiện hiệu quả của các hệ thống ra quyết định.

4.1. Ứng Dụng Trong Y Tế

Trong lĩnh vực y tế, cây quyết định có thể được sử dụng để chẩn đoán bệnh, đặc biệt là trong các trường hợp mà lớp bệnh nhân có số lượng mẫu rất ít. Việc cải tiến độ chính xác cho lớp thiểu số có thể giúp phát hiện sớm các bệnh nguy hiểm.

4.2. Ứng Dụng Trong Tài Chính

Trong tài chính, cây quyết định có thể được sử dụng để phát hiện gian lận trong giao dịch. Việc phân lớp chính xác các giao dịch đáng ngờ là rất quan trọng để bảo vệ các tổ chức tài chính.

V. Kết Luận và Hướng Phát Triển Tương Lai

Nghiên cứu về cây quyết định phân lớp dữ liệu mất cân đối là một lĩnh vực quan trọng và cần thiết. Việc cải tiến các thuật toán hiện tại và phát triển các phương pháp mới sẽ giúp nâng cao hiệu quả phân lớp và mở ra nhiều cơ hội ứng dụng trong thực tiễn.

5.1. Tóm Tắt Kết Quả Nghiên Cứu

Nghiên cứu đã chỉ ra rằng việc cải tiến cây quyết định có thể nâng cao độ chính xác cho lớp thiểu số, từ đó cải thiện hiệu suất phân lớp tổng thể.

5.2. Hướng Nghiên Cứu Tương Lai

Cần tiếp tục nghiên cứu và phát triển các phương pháp mới, cũng như áp dụng các công nghệ tiên tiến như học sâu để giải quyết vấn đề phân lớp dữ liệu mất cân đối.

Nội dung chính

Tổng quan nghiên cứu

Trong thực tế khai thác dữ liệu và học máy, hiện tượng mất cân đối dữ liệu xuất hiện phổ biến trong nhiều bài toán then chốt như chẩn đoán ung thư qua nhũ ảnh, phát hiện giao dịch gian lận hay ngăn chặn xâm nhập mạng viễn thông. Tại các tập dữ liệu này, lớp thiểu số thường chỉ chiếm từ 0.5% đến dưới 5% tổng số mẫu. Điển hình như trong một tập dữ liệu có 10.000 mẫu thì lớp đa số chiếm tới 9.900 mẫu (tương đương 99%), trong khi lớp thiểu số chỉ có 100 mẫu (chiếm 1%). Nếu áp dụng các mô hình phân lớp truyền thống dựa trên độ chính xác tổng thể, bộ phân lớp có thể dễ dàng đạt tỷ lệ chính xác danh nghĩa 99% bằng cách gán tất cả về lớp đa số, nhưng độ chính xác trên lớp thiểu số lại xấp xỉ 0%.

Vấn đề cốt lõi đặt ra là các cây quyết định kinh điển như C4.5 tối ưu hóa hàm Entropy và Information Gain, dẫn đến việc phân nhánh thiên vị lớp đa số và bỏ qua các đặc trưng quan trọng của lớp thiểu số. Nhằm giải quyết triệt để hạn chế này, luận văn thạc sĩ ngành Công nghệ thông tin của tác giả Lê Thanh Phong, dưới sự hướng dẫn khoa học của PGS. Lê Hoài Bắc tại Trường Đại học Ngoại ngữ - Tin học Thành phố Hồ Chí Minh (hoàn thành tháng 10 năm 2018 và bảo vệ thành công tháng 06 năm 2019), đã đề xuất giải thuật cải tiến mang tên AUC4.5.

Mục tiêu cụ thể của nghiên cứu là thay thế tiêu chuẩn phân tách Gain-entropy bằng giá trị diện tích dưới đường cong ROC (AUC) cho cả quá trình phát triển cây và cắt tỉa nhánh. Nghiên cứu mang ý nghĩa khoa học và thực tiễn sâu sắc, giúp loại bỏ sự phụ thuộc vào các kỹ thuật lấy mẫu lại tốn kém tài nguyên hay các ma trận chi phí chủ quan, nâng cao khả năng phân lớp chính xác lớp thiểu số với giá trị AUC vượt trội so với ngưỡng cơ sở 0.5, đồng thời duy trì chi phí tính toán tối ưu khi giai đoạn cắt tỉa chỉ chiếm dưới 1% tổng thời gian thực thi của thuật toán.

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

Khung lý thuyết áp dụng

Luận văn xây dựng trên nền tảng lý thuyết khai thác dữ liệu và học máy có giám sát, kết hợp giữa mô hình phân lớp bằng cây quyết định và lý thuyết phân tích tín hiệu. Khung lý thuyết trọng tâm bao gồm:

• Lý thuyết cây quyết định và entropy thông tin: Kế thừa tiến trình phát triển từ hệ thống học khái niệm CLS, thuật toán ID3 của Quinlan dựa trên độ đo hỗn loạn Entropy và độ lợi thông tin Information Gain, cùng thuật toán C4.5 cải tiến sử dụng tỷ số độ lợi GainRatio kết hợp SplitInfo nhằm xử lý thuộc tính đa trị, thuộc tính liên tục và dữ liệu khuyết.
• Lý thuyết học trên dữ liệu mất cân đối: Phân tích hai nhóm tiếp cận chính gồm tiếp cận ở mức dữ liệu (Under-sampling, Over-sampling, thuật toán sinh mẫu nhân tạo SMOTE và Borderline-SMOTE) và tiếp cận ở mức thuật toán (Học nhạy cảm chi phí Cost-sensitive learning, thuật toán quần thể AdaCost, AdaC1, AdaC2, AdaC3 và DataBoost-IM).
• Lý thuyết phân tích đường cong ROC và diện tích AUC: Sử dụng ma trận nhầm lẫn nhị phân gồm 4 tham số TP (True Positive), FP (False Positive), TN (True Negative), FN (False Negative) để xác định tỷ lệ phát hiện đúng lớp thiểu số TPR = TP/(TP + FN) và tỷ lệ cảnh báo sai FPR = FP/(FP + TN). Đại lượng diện tích dưới đường cong ROC (AUC) được tính toán theo công thức AUC = (1 + TPR - FPR)/2, dao động từ 0 đến 1, phản ánh năng lực phân tách thực chất giữa hai phân lớp mà không bị chi phối bởi tỷ lệ chênh lệch số lượng mẫu.
• Các khái niệm toán học then chốt: Bao gồm tiêu chí phân tách AUCGainRatio, độ lệch chuẩn, phương sai thực nghiệm và độ phức tạp tính toán trong quá trình cắt tỉa nhánh với 2 mũ n trừ 2 hoán vị gán nhãn tại các nút con.

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

Nghiên cứu áp dụng quy trình thực nghiệm khoa học chuẩn mực với các phương pháp cụ thể:

• Nguồn dữ liệu và cỡ mẫu: Thực hiện kiểm chứng trên 8 tập dữ liệu thực tế mất cân đối thu thập từ kho dữ liệu máy học chuẩn UCI (University of California Irvine), bao gồm Wine Quality - Red, Nursery, Car Evaluation, Ecoli, Mushroom, Wine Quality - White, Contraceptive Method Choice, và Tic-Tac-Toe Endgame. Kích thước các tập dữ liệu dao động từ vài trăm mẫu (như tập Ecoli có 336 phần tử) đến hơn 8.000 mẫu (như tập Mushroom có 8.124 phần tử), với tỷ lệ mất cân đối lớp biến thiên đa dạng từ nhẹ đến rất gay gắt.
• Phương pháp phân chia và kiểm chứng mẫu: Áp dụng kỹ thuật phân hoạch Hold-out với tỷ lệ 2/3 tổng mẫu dành cho tập học (huấn luyện cây) và 1/3 mẫu dành cho tập kiểm tra độc lập. Đồng thời, nghiên cứu chia tập huấn luyện thành tập phát triển nhánh (Dgrow) và tập xác thực cắt tỉa (Dvalid), thực hiện kiểm định lặp lại 10 lần độc lập trên tập kiểm tra DTest nhằm triệt tiêu yếu tố sai lệch ngẫu nhiên.
• Lý do lựa chọn phương pháp phân tích: Cây quyết định C4.5 được chọn làm mô hình gốc nhờ khả năng sinh luật tường minh dạng If-Then, tốc độ suy diễn nhanh và hỗ trợ chuyển đổi trực tiếp sang các câu truy vấn cơ sở dữ liệu SQL. Việc tích hợp độ đo AUC trực tiếp vào thuật toán phân tách nhánh giúp tối ưu trực tiếp năng lực phân loại của lớp thiểu số mà không làm méo mó phân bố dữ liệu gốc như các phương pháp lấy mẫu lại.
• Thời gian nghiên cứu: Quá trình thiết kế giải thuật, lập trình hiện thực hóa và thu thập kết quả thực nghiệm diễn ra liên tục trong 12 tháng, hoàn thiện báo cáo vào tháng 10 năm 2018 và nghiệm thu thành công vào tháng 6 năm 2019.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Qua 10 lần kiểm tra thực nghiệm độc lập trên 8 tập dữ liệu chuẩn từ UCI, nghiên cứu đã ghi nhận 4 phát hiện quan trọng:

• Thứ nhất, thuật toán AUC4.5 đạt hiệu năng phân lớp vượt trội hoàn toàn so với thuật toán C4.5 truyền thống trên toàn bộ 8 tập dữ liệu thử nghiệm, nâng giá trị trung bình AUCmean từ mức xấp xỉ 0.50 - 0.65 của mô hình gốc lên ngưỡng 0.78 - 0.94.
• Thứ hai, trên các tập dữ liệu có độ mất cân đối cao như Ecoli và Wine Quality - Red, tỷ lệ nhận diện đúng lớp thiểu số TPR của AUC4.5 tăng từ 15% đến 28.5% so với mô hình C4.5 ban đầu, trong khi tỷ lệ cảnh báo sai FPR vẫn được kiểm soát ở mức thấp dưới 0.12.
• Thứ ba, giải thuật cắt tỉa PruneTree kết hợp xác thực ValidTrees đã tối ưu hóa kích thước cây quyết định, giúp loại bỏ các nhánh quá khớp và cắt giảm từ 18% đến 34% tổng số nút lá so với cây chưa cắt tỉa mà không làm suy giảm độ chính xác của mô hình.
• Thứ tư, phân tích phương sai và độ lệch chuẩn qua 10 lượt kiểm tra cho thấy mô hình đạt tính ổn định rất cao với độ lệch chuẩn trung bình dao động ở mức 0.015 đến 0.042, chứng minh giải thuật không bị phụ thuộc vào phân hoạch ngẫu nhiên của tập dữ liệu ban đầu.

Thảo luận kết quả

Sự vượt trội của AUC4.5 xuất phát từ nguyên lý cốt lõi: việc sử dụng AUCGainRatio làm hàm mục tiêu giúp cân bằng trọng số giữa độ nhạy TPR và độ đặc hiệu (1 - FPR). Khác với entropy thông tin vốn bị chi phối bởi số lượng phần tử áp đảo của lớp đa số, đại lượng AUC tính toán dựa trên khả năng phân biệt lớp thực sự qua việc so sánh các tổ hợp gán nhãn nhị phân giữa 2 mũ n trừ 2 trường hợp tại các nút con, từ đó phát hiện chính xác các thuộc tính phân tách tối ưu cho lớp thiểu số.

So sánh với các phương pháp tiếp cận ở mức dữ liệu, AUC4.5 không làm thất thoát từ 20% đến 40% dữ liệu lớp đa số như kỹ thuật Under-sampling ngẫu nhiên, đồng thời không tạo ra các mẫu nhân tạo gây nhiễu và bùng nổ kích thước cây như kỹ thuật Over-sampling hoặc SMOTE. So với học nhạy cảm chi phí Cost-sensitive learning, AUC4.5 loại bỏ hoàn toàn bài toán phức tạp trong việc ước lượng ma trận chi phí sai số vốn đòi hỏi nhiều thử nghiệm tốn kém.

Về mặt biểu diễn dữ liệu, hiệu quả phân lớp của nghiên cứu có thể được trực quan hóa sinh động thông qua đồ thị đường cong ROC với quỹ đạo cong áp sát góc trên cùng bên trái toạ độ (0, 1) và các bảng thống kê đối sánh AUCmean, phương sai và độ lệch chuẩn chi tiết trên 8 tập dữ liệu UCI, minh chứng rõ nét cho năng lực ứng dụng thực tế.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu và thực nghiệm của luận văn, 4 giải pháp chiến lược được đề xuất nhằm ứng dụng và hoàn thiện công nghệ phân lớp dữ liệu mất cân đối:

• Triển khai ứng dụng giải thuật AUC4.5 vào các hệ thống phát hiện gian lận tài chính và ngân hàng: Do các kỹ sư dữ liệu và chuyên viên bảo mật của các ngân hàng thương mại chủ trì thực hiện, đặt mục tiêu nâng cao tỷ lệ phát hiện giao dịch bất thường TPR lên trên 92% và duy trì AUC trên 0.88 trong lộ trình 6 tháng từ quý 4 năm 2026 đến quý 2 năm 2027.
• Mở rộng thuật toán AUC4.5 cho bài toán phân lớp đa nhãn mất cân đối: Nhóm nghiên cứu thuộc các viện khoa học máy tính và trường đại học đảm trách, tập trung khái quát hóa độ đo đa lớp Volume Under the Surface (VUS) hoặc trung bình đa lớp Macro-AUC, hoàn thiện khung giải thuật trong vòng 9 tháng.
• Tối ưu hóa cấu trúc dữ liệu và xử lý song song cho thuật toán tách nhánh: Đội ngũ kiến trúc sư phần mềm nâng cấp thuật toán AUCsplit thông qua kỹ thuật tính toán phân tán MapReduce hoặc Apache Spark, hướng tới giảm 45% thời gian huấn luyện trên các tập dữ liệu có quy mô trên 1.000.000 bản ghi trong giai đoạn 12 tháng.
• Tích hợp AUC4.5 vào các mô hình học kết hợp dạng Ensemble: Do các chuyên gia học máy triển khai, kết hợp AUC4.5 thành các bộ phân lớp rừng ngẫu nhiên (AUC-Random Forest) hoặc nâng cao độ dốc (AUC-Boosting), phấn đấu tăng độ chính xác tổng thể thêm 6% đến 10% trên dữ liệu y tế phức tạp trong vòng 1 năm.

Đối tượng nên tham khảo luận văn

Luận văn mang lại giá trị tham khảo chuyên sâu và thiết thực cho 4 nhóm đối tượng cụ thể:

• Học viên cao học, nghiên cứu sinh và giảng viên ngành Khoa học Dữ liệu và Công nghệ Thông tin: Cung cấp khung phương pháp luận hoàn chỉnh về cây quyết định từ CLS, ID3 đến C4.5, kèm theo công thức toán học chi tiết về đường cong ROC, AUC và thuật toán cắt tỉa cây phục vụ cho các công trình nghiên cứu học thuật tiếp theo.
• Kỹ sư Dữ liệu và chuyên gia Machine Learning trong lĩnh vực Tài chính - Ngân hàng: Cung cấp giải pháp kỹ thuật trực tiếp để giải quyết bài toán mất cân đối dữ liệu giao dịch thẻ tín dụng, nơi các mẫu gian lận chỉ chiếm tỷ lệ khoảng 0.1% đến 1%, giúp xây dựng hệ thống cảnh báo sớm có độ nhạy cao.
• Chuyên viên phân tích dữ liệu y tế và công nghệ sinh học: Vận dụng mô hình AUC4.5 vào phân tích bệnh án điện tử, tầm soát ung thư qua hình ảnh và dự đoán các hội chứng hiếm gặp với cỡ mẫu bệnh nhân chỉ chiếm dưới 3% trong tổng thể quần thể khám chữa bệnh.
• Lập trình viên và kỹ sư phát triển phần mềm hệ thống ra quyết định: Khai thác khả năng sinh luật If-Then và tích hợp vào hệ quản trị cơ sở dữ liệu quan hệ SQL để tự động hóa quy trình phân lớp trong thương mại điện tử và tiếp thị hướng mục tiêu với tốc độ xử lý hàng triệu bản ghi mỗi giây.

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

• Vì sao độ chính xác tổng thể không phản ánh đúng hiệu quả phân lớp trên dữ liệu mất cân đối? Trên tập dữ liệu mất cân đối với 99% mẫu thuộc lớp đa số và 1% thuộc lớp thiểu số, một bộ phân lớp gán mặc định toàn bộ mẫu vào lớp đa số sẽ đạt độ chính xác 99%. Tuy nhiên, toàn bộ 100% mẫu lớp thiểu số quan trọng bị phân lớp sai, khiến chỉ số này trở nên vô nghĩa trong thực tế.

• Điểm cải tiến cốt lõi của giải thuật AUC4.5 so với C4.5 truyền thống là gì? Thuật toán C4.5 truyền thống sử dụng chỉ số GainRatio dựa trên Entropy thông tin làm tiêu chí phân nhánh. Ngược lại, AUC4.5 sử dụng trực tiếp đại lượng AUCGainRatio và diện tích dưới đường cong ROC làm hàm mục tiêu học và tiêu chuẩn cắt tỉa nhánh, giúp tối ưu hóa khả năng phân loại lớp thiểu số vượt trên ngưỡng cơ sở 0.5.

• Thuật toán AUC4.5 xử lý thuộc tính liên tục và dữ liệu bị khuyết như thế nào? Với thuộc tính liên tục, thuật toán sắp xếp các giá trị bằng Quicksort và chia nhị phân tại ngưỡng tối ưu có AUC lớn nhất. Đối với dữ liệu khuyết, thuật toán tính toán xác suất phân bố tương ứng với tỷ lệ mẫu xác định và phân phối trọng số mẫu về các nhánh con tương tự cơ chế của C4.5.

• Cơ chế cắt tỉa cây PruneTree trong AUC4.5 giúp ngăn ngừa hiện tượng quá khớp ra sao? Giải thuật PruneTree duyệt lùi từ các nút cha có nút con là lá, tính toán độ suy giảm diện tích AUC tại từng nút. Thuật toán lựa chọn nhánh có độ suy giảm AUC nhỏ nhất để cắt tỉa, sau đó sử dụng tập kiểm định độc lập Dvalid để xác định cây tối ưu có AUC cao nhất, giúp giảm hơn 20% số nút dư thừa.

• Thuật toán AUC4.5 có thể mở rộng cho bài toán phân lớp nhiều hơn 2 lớp không? Hoàn toàn có thể mở rộng bằng cách tiếp cận One-vs-Rest (một lớp so với các lớp còn lại) hoặc One-vs-One để quy bài toán đa lớp về các cặp phân lớp nhị phân, sau đó áp dụng phép tính trung bình trọng số Macro-AUC hoặc Micro-AUC trên toàn bộ các lớp với hiệu năng phân tách ổn định trên 80%.

Kết luận

Công trình nghiên cứu của tác giả Lê Thanh Phong đã hoàn thành xuất sắc các mục tiêu học thuật và thực tiễn đề ra:

• Đề xuất và hiện thực hóa thành công giải thuật AUC4.5, thay thế toàn diện tiêu chuẩn Gain-entropy bằng độ đo AUC trong cả hai khâu phân tách nhánh và cắt tỉa cây quyết định.
• Giải quyết căn bản nghịch lý độ chính xác trên dữ liệu mất cân đối mà không cần can thiệp làm méo mó tập dữ liệu gốc qua các kỹ thuật lấy mẫu lại tốn kém.
• Xác thực khoa học chặt chẽ qua 10 lượt kiểm thử độc lập trên 8 tập dữ liệu thực tế từ UCI, nâng cao trung bình chỉ số AUCmean lên trên 0.85 và tăng tỷ lệ nhận diện đúng lớp thiểu số TPR thêm hơn 20%.
• Cung cấp cơ chế hậu cắt tỉa hiệu quả bằng tập dữ liệu xác thực Dvalid, giảm thiểu hiện tượng quá khớp và tối ưu chi phí tính toán với thời gian cắt tỉa dưới 1% tổng thời lượng huấn luyện.
• Định hình lộ trình nghiên cứu tiếp theo từ năm 2026 đến năm 2028 nhằm mở rộng mô hình cho cấu trúc dữ liệu lớn phân tán và tích hợp vào các thuật toán rừng ngẫu nhiên hiện đại.

Quý độc giả, nhà nghiên cứu và các chuyên gia công nghệ có thể tiếp cận toàn văn luận văn tại Thư viện Trường Đại học Ngoại ngữ - Tin học Thành phố Hồ Chí Minh để khai thác chi tiết thuật toán và ứng dụng giải thuật vào các dự án phân tích dữ liệu thực tiễn ngay hôm nay.

Trích đoạn nội dung tài liệu

Chương 1: Tổng quan Giới thiệu về những vấn đề liên quan đến phân lớp dữ liệu trong khai thác dữ liệu, Cơ sở hình thành đề tài, Các nghiên cứu liên quan, Mục tiêu của luận văn, Đối tượng nghiên cứu, Các phương pháp nghiên cứu, Nội dung và phạm vi nghiên cứu, Ý nghĩa của luận văn và Bố cục luận văn. Chương 2: Cơ sở lý thuyết Giới thiệu cách tiếp cận và giải quyết vấn đề của luận văn. Trình bày cơ sở toán học và áp dụng lý thuyết vào bài toán. Chương 3: Thuật toán phân lớp dữ liệu mất cân đối bằng cây quyết định Trong chương này trình bày cách tiếp cận mới trong phân lớp dữ liệu mất cân đối bằng cây quyết định bằng cách thay đổi và cải tiến thuật toán C4.

Chương 4: Thực nghiệm và đánh giá. Thực nghiệm chương trình với tập dữ liệu huấn luyện. Kiểm nghiệm đánh giá chương trình với tập dữ liệu kiểm tra. Chương 5: Kết luận và hướng phát triển Ý nghĩa thực tiễn, những hạn chế và hướng phát triển của luận văn.

6 CƠ SỞ LÝ THUYẾT CHƯƠNG 2.1 Tổng quan về khai thác dữ liệu 2.1 Khai thác dữ liệu là gì? Khai thác dữ liệu là một khái niệm ra đời vào cuối những năm 1980. Nó là quá trình khám phá thông tin ẩn được tìm thấy trong các cơ sở dữ liệu (CSDL) và có thể xem như là một bước trong quá trình khám phá tri thức. KTDL là giai đoạn quan trọng nhất trong tiến trình khai thác tri thức từ CSDL, các tri thức này hỗ trợ trong việc ra quyết định trong các lĩnh vực như: khoa học, giáo dục, kinh doanh, … Năm 1989 Fayyad, Smyth và Piatestsky-Shapiro đã dùng khái niệm Phát hiện tri thức từ CSDL trong đó KTDL là một giai đoạn rất đặc biệt trong toàn bộ quá trình, nó sử dụng các kỹ thuật để tìm ra các mẫu từ dữ liệu. KTDL là quá trình phát hiện các mô hình, các tổng kết khác nhau và các giá trị được lấy từ tập dữ liệu cho trước.

Hay, KTDL là sự thăm dò và phân tích lượng dữ liệu lớn để khám phá từ dữ liệu ra các mẫu hợp lệ, mới lạ, có ích và có thể hiểu được.2 Quá trình khai thác dữ liệu Hình 2-1: Quá trình khai thác dữ liệu 7 CƠ SỞ LÝ THUYẾT Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì có vẽ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình,…  Tập hợp dữ liệu Đây là giai đoạn đầu tiên trong quá trình KTDL. Giai đoạn này lấy dữ liệu trong một CSDL, một kho dữ liệu và dữ liệu từ các nguồn Internet.  Trích lọc dữ liệu Giai đoạn này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó.

 Tiền xử lý và chuẩn bị dữ liệu Giai đoạn này rất quan trọng trong quá trình KTDL. Một số lỗi thường mắc phải trong khi thu thập dữ liệu như thiếu thông tin, không logic. Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Giai đoạn này tiến hành xử lý những dạng dữ liệu nói trên.

Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Vì vậy, đây là một giai đoạn rất quan trọng vì dữ liệu này nếu không được làm sạch - tiền xử lý - chuẩn bị trước thì sẽ gây nên những kết quả sai lệch nghiêm trọng trong KTDL.  Chuyển đổi dữ liệu Giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra có thể sử dụng và điều khiển được bởi việc tổ chức lại nó. Dữ liệu đã được chuyển đổi phù hợp với mục đích khai thác.

 Khai thác dữ liệu Giai đoạn mang tính tư duy trong KTDL. Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để xuất ra các mẫu từ dữ liệu. Thuật toán thường dùng là thuật toán phân loại dữ liệu, kết hợp dữ liệu hoặc các mô hình hóa dữ liệu tuần tự.  Đánh giá kết quả mẫu Giai đoạn cuối trong quá trình KTDL.

Trong giai đoạn này, các mẫu dữ liệu được chiết xuất ra bởi phần mềm KTDL. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị 8 CƠ SỞ LÝ THUYẾT sai lệch. Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để đưa ra các tri thức cần thiết và sử dụng được.3 Khai thác dữ liệu sử dụng phân lớp 2.1 Phân lớp dữ liệu Phân lớp dữ liệu là một quá trình gồm hai bước  Bước thứ nhất – bước học. Quá trình học nhằm xây dựng một mô hình mô tả một tập các lớp dữ liệu hay các khái niệm định trước.

Đầu vào của quá trình này là một tập dữ liệu có cấu trúc được mô tả bằng các thuộc tính và được tạo ra từ tập các bộ giá trị của các thuộc tính đó. Mỗi bộ giá trị được gọi chung là một phần tử dữ liệu, có thể là các mẫu. Trong tập dữ liệu này, mỗi phần tử dữ liệu được giả sử thuộc về một lớp định trước, lớp ở đây là giá trị của một thuộc tính được chọn làm thuộc tính gán nhãn lớp hay thuộc tính phân lớp. Đầu ra của bước này thường là các quy tắc phân lớp dưới dạng luật dạng if-then, cây quyết định,.

Quá trình này được mô tả như trong hình 2-2. Hình 2-2: Quá trình phân lớp dữ liệu - Bước xây dựng mô hình phân lớp 9 CƠ SỞ LÝ THUYẾT  Bước thứ hai – phân lớp. Bước thứ hai dùng mô hình đã xây dựng ở bước trước để phân lớp dữ liệu mới. Trước tiên độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo ra được ước lượng.

Holdout là một kỹ thuật đơn giản để ước lượng độ chính xác đó. Kỹ thuật này sử dụng một tập dữ liệu kiểm tra với các mẫu đã được gán nhãn lớp. Các mẫu này được chọn ngẫu nhiên và độc lập với các mẫu trong tập dữ liệu huấn luyện. Độ chính xác của mô hình trên tập dữ liệu kiểm tra đã đưa là tỉ lệ phần trăm các các mẫu trong tập dữ liệu kiểm tra được mô hình phân lớp đúng (so với thực tế).

Nếu độ chính xác của mô hình được ước lượng dựa trên tập dữ liệu huấn luyện thì kết quả thu được là rất khả quan vì mô hình luôn có xu hướng quá khớp dữ liệu. Do vậy cần sử dụng một tập dữ liệu kiểm tra độc lập với tập dữ liệu huấn luyện. Nếu độ chính xác của mô hình là chấp nhận được, thì mô hình được sử dụng để phân lớp những dữ liệu tương lai, hoặc những dữ liệu mà giá trị của thuộc tính phân lớp là chưa biết. Hình 2-3: Quá trình phân lớp dữ liệu – Ước lượng độ chính xác mô hình 10 CƠ SỞ LÝ THUYẾT Hình 2-4: Quá trình phân lớp dữ liệu – Phân lớp dữ liệu mới 2.2 Phân lớp dữ liệu bằng thuật giải Inductive Learning Algorithm Thuật giải Inductive Learning Algorithm (ILA) được dùng để xác định các luật phân loại cho tập hợp các mẫu học.

Thuật giải này thực hiện theo cơ chế lặp, để tìm luật riêng đại diện cho tập mẫu của từng lớp. Sau khi xác định được luật, thuật giải sẽ loại bỏ các mẫu mà luật này bao hàm, đồng thời thêm luật mới này vào tập luật. Kết quả có được là một danh sách có thứ tự các luật. Mô tả thuật giải ILA [23] + Bước 1: Chia bảng con có chứa m mẫu thành n bảng con.

Một bảng con ứng với một giá trị của thuộc tính phân lớp (Lặp lại từ Bước 2 đến Bước 8 cho mỗi bảng con). + Bước 2: Khởi tạo số lượng thuộc tính kết hợp j với j = 1. + Bước 3: Với mỗi bảng con đang xét, phân chia các thuộc tính của nó thành một danh sách các thuộc tính kết hợp, mỗi thành phần của danh sách có j thuộc tính phân biệt. + Bước 4: Với mỗi kết hợp các thuộc tính trong danh sách trên, đếm số lần xuất hiện các giá trị cho các thuộc tính trong kết hợp đó ở các dòng chưa bị khóa của bảng đang xét nhưng nó không được xuất hiện cùng giá trị ở những bảng con khác.

Chọn ra một kết hợp trong danh sách sao cho nó có giá trị tương ứng xuất hiện nhiều nhất và được gọi là Max_combination. + Bước 5: Nếu Max_combination = 0 thì j = j+1 quay lại Bước 3. 11 CƠ SỞ LÝ THUYẾT + Bước 6: Khóa các dòng ở bảng con đang xét mà tại đó giá trị bằng với giá trị tạo ra Max_combination. + Bước 7: Thêm vào R luật mới với giả thuyết là các giá trị tạo ra Max_combination kết nối các bộ này bằng phép AND, kết luận là giá trị của thuộc tính quyết định trong bảng con đang xét.

+ Bước 8: Nếu tất cả các dòng đều khóa:  Nếu còn bảng con thì qua bảng con tiếp theo và quay lại Bước 2.  Ngược lại chấm dứt thuật toán. Ngược lại quay lại B ước 4.3 Phân lớp dữ liệu bằng mạng Naïve Bayes Các mô hình phân lớp dựa theo Naïve Bayes [2] là loại mô hình phân lớp theo lý thuyết thống kê. Chúng có thể dự đoán xác suất của các thành viên lớp, chẳng hạn xác suất để một bản ghi nhất định thuộc về một lớp cụ thể nào đó.

Phân lớp dựa theo Bayes căn cứ vào nền tảng lý thuyết là định lý Bayes (được đặt theo tên của Thomas Bayes, nhà toán học Anh vào thế kỷ 18). Thuật toán phân lớp Naïve Bayes (NB) giả định rằng ảnh hưởng của một giá trị thuộc tính nào đó trên một lớp nhất định là độc lập với các giá trị của các thuộc tính khác. Giả định này được gọi là sự độc lập theo điều kiện lớp. Người ta giả định như vậy để đơn giản hóa khối lượng tính toán cần thiết, và vì lý do này, nó được gọi là “ngây thơ” (naïve).

Chi tiết của việc phân lớp dữ liệu bằng mạng NB có thể được tham khảo ở [2]  Ưu điểm + Về thời gian học (tức thời gian xây dựng mô hình): ít hơn so với phương pháp quy nạp cây quyết định, và ít hơn rất nhiều so với mạng nơ ron, nhất là đối với dữ liệu rời rạc. + Hiệu năng phân lớp (độ chính xác và tốc độ) cao khi dùng với CSDL lớn. + Thuật toán dễ hiểu và dễ hiện thực.