Xây Dựng Cây Quyết Định Có Trọng Số Cho Dự Đoán Sai Với Ràng Buộc Tài Nguyên

Cây quyết định là một trong những kỹ thuật học máy nền tảng, được ứng dụng rộng rãi trong bài toán phân lớp dữ liệu. 56 trang.

• Đề tài: Xây Dựng Cây Quyết Định Tối Ưu Cho Dự Đoán Sai Với Ràng Buộc Tài Nguyên

Mục lục chi tiết

• Lời cảm ơn
• Lời cam kết
• Tóm tắt
• Danh sách ký hiệu
• Danh sách thuật ngữ
• Danh sách hình vẽ
• Danh sách bảng
• 1. Chương 1: Giới thiệu
• 2. Chương 2: Tổng quan nghiên cứu
• 2.1. Cây quyết định tối ưu & phương pháp
• 2.2. Cây quyết định nhạy cảm với chi phí & phương pháp
• 3. Chương 3: Mô hình toán học mới cho việc xây dựng cây quyết định tối ưu nhạy cảm với chi phí và ràng buộc về thời gian
• 3.1. Cây quyết định tối ưu truyền thống
• 3.2. Các biến thể nhạy cảm với chi phí và ràng buộc về thời gian
• 3.2.1. Cây quyết định cân bằng
• 3.2.2. Cây quyết định không cân bằng
• 4. Chương 4: Sự điều chỉnh thời gian giới hạn và chi phí thuộc tính cho các mô hình hiện có
• 4.1. Sự điều chỉnh thời gian giới hạn và chi phí thuộc tính cho FlowOCT
• 4.1.1. Cây quyết định cân bằng
• 4.1.2. Cây quyết định không cân bằng
• 4.2. Sự điều chỉnh thời gian giới hạn và chi phí thuộc tính cho BinOCT
• 5. Chương 5: Kết quả thực nghiệm và kết luận
• 5.1. So sánh cỡ của các mô hình MIP
• 5.2. Thiết lập thực nghiệm
• 5.3. So sánh hiệu suất của các mô hình MIP
• 5.4. Kết luận và hướng phát triển
• Tài liệu tham khảo
• Phụ lục

Tóm tắt

I. Hướng Dẫn Xây Dựng Cây Quyết Định Tối Ưu Với Tài Nguyên Hạn Chế

Cây quyết định là một trong những kỹ thuật học máy nền tảng, được ứng dụng rộng rãi trong bài toán phân lớp dữ liệu. Mô hình này hoạt động dựa trên cấu trúc cây nhị phân, phân vùng dữ liệu đào tạo một cách đệ quy và gán nhãn cho từng phân vùng. Khi có một mẫu dữ liệu mới, cây quyết định sẽ phân loại bằng cách duyệt từ nút gốc, đi xuống các nút con dựa trên kết quả so sánh thuộc tính, và kết thúc tại một nút lá chứa nhãn dự đoán. Mục tiêu chính khi xây dựng cây quyết định tối ưu là tối đa hóa độ chính xác, hay nói cách khác là giảm thiểu dự đoán sai. Tuy nhiên, trong nhiều ứng dụng thực tiễn, đặc biệt là y tế và tài chính, bài toán không chỉ dừng lại ở độ chính xác. Việc thực hiện các bài kiểm tra (tương ứng với các nút trong cây) tiêu tốn nhiều loại tài nguyên như chi phí, thời gian và nhân lực. Do đó, việc xây dựng cây quyết định tối ưu phải cân nhắc thêm các ràng buộc tài nguyên này. Luận văn của Trần Quang Toàn (2024) đã tập trung giải quyết vấn đề này bằng cách đề xuất một mô hình quy hoạch nguyên hỗn hợp (MIP), cho phép tích hợp các yếu tố phức tạp như chi phí phân loại sai và ràng buộc thời gian vào quá trình xây dựng cây. Phương pháp này mở ra một hướng tiếp cận toàn diện hơn, giúp tạo ra các mô hình không chỉ chính xác mà còn hiệu quả về mặt chi phí và thời gian, đáp ứng yêu cầu của các bài toán trong thế giới thực.

1.1. Tổng quan về cây quyết định và vai trò trong học máy

Cây quyết định (Decision Tree) là một mô hình học máy có giám sát, biểu diễn các quy tắc quyết định dưới dạng một cấu trúc cây. Mỗi nút trong (internal node) đại diện cho một bài kiểm tra trên một thuộc tính, mỗi nhánh (branch) đại diện cho kết quả của bài kiểm tra, và mỗi nút lá (leaf node) đại diện cho một nhãn lớp. Ưu điểm lớn nhất của cây quyết định là tính dễ diễn giải; các quy tắc được tạo ra có thể được con người hiểu một cách trực quan. Quá trình phân loại một điểm dữ liệu mới rất đơn giản: bắt đầu từ nút gốc, đi theo các nhánh tương ứng với giá trị thuộc tính của điểm dữ liệu cho đến khi tới một nút lá. Nhãn của nút lá đó chính là kết quả dự đoán. Vai trò của cây quyết định trong học máy là rất quan trọng, được sử dụng trong nhiều lĩnh vực từ chẩn đoán y khoa, phân loại tín dụng, đến nhận dạng đối tượng.

1.2. Tầm quan trọng của chi phí và thời gian trong phân loại

Trong các bài toán phân loại truyền thống, mục tiêu thường là tối đa hóa độ chính xác. Tuy nhiên, cách tiếp cận này bỏ qua các yếu tố quan trọng trong thực tế. Chi phí phân loại sai là một ví dụ điển hình. Việc phân loại một bệnh nhân mắc bệnh hiểm nghèo thành người khỏe mạnh (dương tính giả) có thể gây ra hậu quả nghiêm trọng hơn nhiều so với việc phân loại ngược lại. Tương tự, chi phí kiểm thử (test cost) liên quan đến việc thu thập dữ liệu cho các thuộc tính cũng cần được xem xét. Một xét nghiệm máu hoặc chụp X-quang không chỉ tốn kém về tiền bạc mà còn cả thời gian. Do đó, một mô hình cây quyết định nhạy cảm với chi phí phải tìm cách cân bằng giữa độ chính xác và tổng chi phí. Thêm vào đó, ràng buộc thời gian là yếu tố cấp thiết trong các tình huống khẩn cấp, yêu cầu phải có kết quả phân loại trong một khoảng thời gian nhất định.

II. Thách Thức Khi Tối Ưu Cây Quyết Định Chi Phí Và Thời Gian

Việc xây dựng cây quyết định tối ưu được chứng minh là một bài toán NP-khó (Hyafil and Rivest, 1976), nghĩa là độ phức tạp tính toán tăng theo cấp số nhân với kích thước dữ liệu. Để giải quyết vấn đề này, các phương pháp truyền thống như CART hay C4.5 sử dụng thuật toán tham lam (greedy). Cách tiếp cận này xây dựng cây từ trên xuống (top-down), tại mỗi nút, nó chọn thuộc tính phân tách tốt nhất tại thời điểm đó mà không xem xét tác động tổng thể lên cấu trúc cây. Điều này dẫn đến các cây quyết định thường không phải là tối ưu toàn cục. Một phân tách mạnh có thể bị ẩn sau một phân tách yếu, khiến thuật toán không thể tìm ra cấu trúc tốt nhất. Một thách thức lớn khác là việc tích hợp các ràng buộc tài nguyên phức tạp. Hầu hết các thuật toán hiện có tập trung vào việc giảm thiểu lỗi phân loại hoặc độ phức tạp của cây, nhưng chưa có phương pháp chính xác nào để xây dựng một cây quyết định đồng thời tối ưu hóa chi phí phân loại sai, chi phí kiểm thử và tuân thủ ràng buộc thời gian. Đây chính là khoảng trống nghiên cứu mà luận văn của Trần Quang Toàn (2024) nhắm đến, sử dụng mô hình toán học để tìm ra giải pháp tối ưu được chứng nhận thay vì các phương pháp heuristic xấp xỉ.

2.1. Hạn chế của các thuật toán tham lam truyền thống

Các thuật toán tham lam như CART và C4.5 xây dựng cây quyết định theo từng bước. Tại mỗi nút, chúng lựa chọn thuộc tính phân chia dữ liệu tốt nhất dựa trên một tiêu chí cục bộ (ví dụ: Gini impurity, information gain). Quyết định này là bất biến và không được xem xét lại ở các bước sau. Nhược điểm chính của phương pháp này là nó có thể dẫn đến các giải pháp dưới tối ưu. Một quyết định phân tách có vẻ tốt ở cấp độ hiện tại có thể ngăn cản việc tạo ra các phân tách tốt hơn ở các cấp độ sâu hơn của cây. Hơn nữa, các thuật toán này thường tạo ra cây quá phức tạp (overfitting) và cần một giai đoạn cắt tỉa (pruning) sau đó để cải thiện khả năng tổng quát hóa. Giai đoạn cắt tỉa này cũng thường dựa trên heuristic và không đảm bảo tìm được cây tối ưu cuối cùng.

2.2. Khoảng trống trong bài toán nhạy cảm chi phí và thời gian

Mặc dù đã có nhiều nghiên cứu về cây quyết định nhạy cảm với chi phí, hầu hết chúng đều dựa trên các phương pháp xấp xỉ hoặc heuristic. Các nghiên cứu này thường sửa đổi tiêu chí lựa chọn thuộc tính để tính đến chi phí, nhưng không đảm bảo rằng cây kết quả là tối ưu về mặt tổng chi phí. Quan trọng hơn, bài toán kết hợp đồng thời cả chi phí phân loại sai, chi phí kiểm thử và ràng buộc thời gian vẫn chưa được khám phá sâu. Theo tổng quan nghiên cứu trong tài liệu gốc, "chưa có một phương pháp chính xác nào để tìm ra một cây quyết định tối ưu cho bài toán này". Sự thiếu hụt các mô hình chính xác, đặc biệt là các mô hình dựa trên quy hoạch nguyên hỗn hợp (MIP), đã tạo ra một khoảng trống lớn cần được giải quyết để áp dụng hiệu quả cây quyết định trong các lĩnh vực có yêu cầu cao về nguồn lực.

III. Phương Pháp PathOCT Xây Dựng Cây Quyết Định Theo Đường Dẫn

Để giải quyết những thách thức nêu trên, luận văn đề xuất một mô hình toán học mới có tên là PathOCT. Thay vì xây dựng cây quyết định theo từng nút riêng lẻ, phương pháp này tiếp cận bài toán bằng cách xem xét toàn bộ các đường dẫn (path) từ gốc đến lá. Mỗi đường dẫn đại diện cho một chuỗi quy tắc phân loại hoàn chỉnh. Ý tưởng cốt lõi là chia tập hợp các nút trong thành tập hợp các đường dẫn và tối ưu hóa việc gán thuộc tính cho tất cả các nút trên mỗi đường dẫn cùng một lúc. Cách tiếp cận này mang lại nhiều lợi thế. Thứ nhất, nó cho phép mô hình hóa các ràng buộc tài nguyên một cách trực tiếp và hiệu quả. Ví dụ, ràng buộc thời gian có thể được biểu diễn bằng cách yêu cầu tổng thời gian thực hiện các kiểm tra trên một đường dẫn không được vượt quá một ngưỡng cho trước. Thứ hai, kỹ thuật này giúp giảm kích thước của mô hình quy hoạch nguyên hỗn hợp, đặc biệt là khi xử lý các cây không cân bằng. Thay vì cắt tỉa cây, PathOCT biến các nút không cần thiết thành các nút "rỗng", giúp giữ nguyên cấu trúc cây và đơn giản hóa việc lập mô hình. Mô hình này được phát triển thành hai biến thể: BCS-PathOCT cho cây cân bằng và ICS-PathOCT cho cây không cân bằng, mang lại sự linh hoạt cho nhiều kịch bản khác nhau.

3.1. Nguyên lý hoạt động của mô hình quy hoạch nguyên PathOCT

Mô hình PathOCT được xây dựng dựa trên quy hoạch nguyên hỗn hợp (MIP). Các biến quyết định chính bao gồm việc gán một thuộc tính (phân tách) cho một nút trên một đường dẫn cụ thể, việc một điểm dữ liệu có đi qua một đường dẫn nhất định hay không, và nhãn lớp được gán cho mỗi lá. Hàm mục tiêu của mô hình là tối thiểu hóa một hàm chi phí kết hợp, bao gồm chi phí phân loại sai có trọng số và tổng chi phí của các thuộc tính được sử dụng. Một điểm đột phá của PathOCT là cách nó xử lý các đường dẫn. Mỗi đường dẫn được biểu diễn bằng một bitset, cho phép mô hình kiểm tra tính khả thi của một điểm dữ liệu đối với toàn bộ đường dẫn một cách hiệu quả, thay vì phải kiểm tra từng nút. Cách tiếp cận này cũng giúp loại bỏ việc sử dụng các tham số M-lớn (Big-M) trong các ràng buộc, giúp mô hình ổn định và dễ giải hơn.

3.2. Biến thể BCS và ICS cho các loại cây quyết định khác nhau

Mô hình PathOCT được tùy chỉnh thành hai phiên bản để xử lý các cấu trúc cây khác nhau. Phiên bản BCS-PathOCT (Balanced Cost-Sensitive) được thiết kế để xây dựng cây quyết định cân bằng, nơi tất cả các nút trong đều phải được gán một thuộc tính. Mô hình này phù hợp cho các bài toán mà cấu trúc cây đầy đủ là cần thiết. Ngược lại, phiên bản ICS-PathOCT (Imbalanced Cost-Sensitive) dành cho việc xây dựng cây không cân bằng. Trong thực tế, các cây không cân bằng thường hiệu quả hơn, cho phép một số nhánh kết thúc sớm hơn các nhánh khác. Mô hình ICS-PathOCT cho phép các nút trong trở thành nút "rỗng", tương đương với việc cắt tỉa cây một cách linh hoạt. Điều này đặc biệt hữu ích khi đối mặt với các ràng buộc thời gian nghiêm ngặt, vì mô hình có thể chọn không thực hiện thêm kiểm tra để đáp ứng thời hạn.

IV. Cách Điều Chỉnh FlowOCT Và BinOCT Cho Ràng Buộc Phức Tạp

Để đánh giá hiệu quả của mô hình PathOCT mới, nghiên cứu đã tiến hành so sánh với các mô hình quy hoạch nguyên hỗn hợp (MIP) hiện có, bao gồm FlowOCT (Aghaei et al., 2020) và BinOCT (Verwer and Zhang, 2019). Tuy nhiên, các mô hình này ban đầu không được thiết kế để xử lý bài toán cây quyết định nhạy cảm với chi phí và ràng buộc thời gian. Do đó, một phần quan trọng của luận văn là điều chỉnh và mở rộng các mô hình này để chúng có thể giải quyết bài toán đặt ra. Đối với FlowOCT, một mô hình dựa trên khái niệm luồng (flow) dữ liệu qua cây, việc điều chỉnh bao gồm việc thêm các biến quyết định mới để tính toán lỗi phân loại và sửa đổi hàm mục tiêu để bao gồm chi phí phân loại sai và chi phí thuộc tính. Các ràng buộc thời gian cũng được thêm vào, yêu cầu tổng thời gian trên mỗi đường đi của luồng không vượt quá giới hạn. Tương tự, mô hình BinOCT, nổi tiếng với việc mã hóa nhị phân hiệu quả, cũng được sửa đổi để tính toán chi phí thay vì chỉ đếm số lỗi. Việc điều chỉnh này cho phép một so sánh công bằng và toàn diện về hiệu suất giữa các phương pháp tiếp cận khác nhau trong việc xây dựng cây quyết định tối ưu.

4.1. Tích hợp ràng buộc thời gian và chi phí vào mô hình FlowOCT

Mô hình FlowOCT gốc xem các điểm dữ liệu như các luồng chảy từ gốc đến các lá. Để tích hợp các yếu tố mới, hàm mục tiêu được thay đổi để tối thiểu hóa tổng chi phí, thay vì chỉ tối đa hóa độ chính xác. Chi phí phân loại sai được tính toán dựa trên các luồng đi đến các lá có nhãn không chính xác. Các ràng buộc mới được thêm vào để đảm bảo tổng thời gian của các thuộc tính trên đường đi của mỗi luồng phải nhỏ hơn giới hạn thời gian của lớp được dự đoán. Đối với phiên bản cây không cân bằng (ICS-FlowOCT), việc điều chỉnh phức tạp hơn, đòi hỏi sử dụng tham số M-lớn để xử lý các trường hợp một nút trong có thể trở thành một nút lá, điều này có thể làm giảm hiệu suất của bộ giải.

4.2. Áp dụng điều kiện nhạy cảm chi phí cho mô hình BinOCT

Mô hình BinOCT chỉ được thiết kế cho cây quyết định cân bằng. Để áp dụng cho bài toán nhạy cảm với chi phí, các biến đếm lỗi gốc được thay thế bằng các biến mới để theo dõi số lượng điểm dữ liệu của từng lớp bị phân loại sai tại mỗi lá. Điều này cho phép nhân số lỗi với ma trận chi phí phân loại sai tương ứng trong hàm mục tiêu. Tổng chi phí thuộc tính cũng được thêm vào. Ràng buộc thời gian cũng được tích hợp bằng cách yêu cầu tổng thời gian của các thuộc tính được chọn trên mỗi đường dẫn từ gốc đến lá phải tuân thủ giới hạn. Mặc dù BinOCT có lợi thế về số lượng biến ít hơn, việc tích hợp các điều kiện phức tạp này có thể ảnh hưởng đến hiệu quả vốn có của nó.

V. Phân Tích Kết Quả Hiệu Suất Cây Quyết Định Tối Ưu Thực Tế

Kết quả thực nghiệm được báo cáo trong luận văn đã cung cấp những hiểu biết sâu sắc về hiệu suất của các mô hình khi xây dựng cây quyết định tối ưu dưới các ràng buộc tài nguyên. Các mô hình được kiểm thử trên 9 bộ dữ liệu công khai với các độ sâu và tham số khác nhau. Trong kịch bản xây dựng cây không cân bằng, mô hình ICS-PathOCT được đề xuất đã thể hiện sự vượt trội so với ICS-FlowOCT, đặc biệt về thời gian chạy và chi phí phân loại sai. Điều này là do ICS-PathOCT có kích thước mô hình nhỏ gọn hơn và không cần sử dụng tham số M-lớn. Trong kịch bản cây cân bằng, cuộc cạnh tranh diễn ra gay gắt hơn. Mô hình CS-BinOCT cho thời gian chạy nhanh nhất, nhưng lại có hiệu suất kém nhất về mặt chi phí phân loại sai. Ngược lại, BCS-PathOCT mang lại hiệu suất tốt nhất về chi phí phân loại sai, cho thấy nó được thiết kế đặc biệt tốt cho mục tiêu này. Mô hình BCS-FlowOCT tỏ ra là một lựa chọn cân bằng và ổn định trên tất cả các tiêu chí. Những kết quả này chứng tỏ rằng không có một mô hình nào là tốt nhất cho mọi trường hợp, và việc lựa chọn phương pháp phụ thuộc vào ưu tiên cụ thể của bài toán: tốc độ, độ chính xác, hay tối thiểu hóa chi phí.

5.1. So sánh hiệu suất giữa các mô hình MIP trên bộ dữ liệu thực

Phân tích so sánh cho thấy mô hình ICS-PathOCT vượt trội hơn ICS-FlowOCT ở hầu hết các chỉ số khi xây dựng cây không cân bằng, bao gồm thời gian chạy (vượt trội trong 118/216 trường hợp) và chi phí phân loại sai (51/35). Đối với cây cân bằng, CS-BinOCT có thời gian chạy tốt nhất, nhưng BCS-PathOCT lại dẫn đầu về việc giảm thiểu chi phí phân loại sai (thắng trong 68/216 trường hợp). BCS-FlowOCT là mô hình ổn định nhất, đứng thứ hai ở hầu hết các hạng mục. Điều này cho thấy sự đánh đổi rõ ràng giữa các mục tiêu tối ưu hóa. Các mô hình như BinOCT được tối ưu hóa cho tốc độ có thể phải hy sinh khả năng xử lý các hàm mục tiêu phức tạp như chi phí phân loại sai.

5.2. Đánh giá ảnh hưởng của ràng buộc thời gian đến các mô hình

Việc bổ sung các ràng buộc thời gian có ảnh hưởng đáng kể đến hiệu suất của các mô hình. Các ràng buộc nghiêm ngặt hơn (ví dụ: giới hạn thời gian bằng 50% so với 80% thời gian tối đa) buộc các mô hình phải xây dựng các cây nông hơn hoặc lựa chọn các thuộc tính có thời gian kiểm tra nhanh hơn, đôi khi phải hy sinh độ chính xác. Trong bối cảnh này, các mô hình xây dựng cây không cân bằng như ICS-PathOCT và ICS-FlowOCT tỏ ra linh hoạt hơn, vì chúng có thể "cắt tỉa" các nhánh để đáp ứng thời hạn mà không cần phải xây dựng một cây hoàn chỉnh. Kết quả cho thấy các mô hình đề xuất có khả năng tìm ra các giải pháp khả thi và chất lượng cao ngay cả khi có các giới hạn chặt chẽ về thời gian.

VI. Tương Lai Của Cây Quyết Định Tối Ưu Và Hướng Nghiên Cứu Mới

Nghiên cứu về xây dựng cây quyết định tối ưu với ràng buộc tài nguyên đã mở ra một hướng đi quan trọng, kết hợp sức mạnh của tối ưu hóa và học máy. Các mô hình quy hoạch nguyên hỗn hợp (MIP) như PathOCT, FlowOCT và BinOCT đã chứng tỏ khả năng tìm ra các giải pháp chất lượng cao, vượt qua những hạn chế của các thuật toán tham lam truyền thống. Mô hình PathOCT được đề xuất cho thấy nhiều hứa hẹn, đặc biệt trong việc xử lý các cây không cân bằng và các ràng buộc phức tạp mà không làm tăng đáng kể độ phức tạp của mô hình. Tuy nhiên, một hạn chế chung của các phương pháp dựa trên MIP là khả năng mở rộng. Khi số lượng điểm dữ liệu hoặc thuộc tính tăng lên, kích thước mô hình sẽ phình ra, gây khó khăn cho việc tính toán. Do đó, các hướng phát triển trong tương lai cần tập trung vào việc giải quyết vấn đề này. Các kỹ thuật như phân rã (decomposition) hay phương pháp sinh cột (column generation) có thể được áp dụng để chia nhỏ bài toán lớn thành các bài toán con dễ quản lý hơn. Việc nghiên cứu các phương pháp này sẽ giúp đưa các mô hình cây quyết định tối ưu vào ứng dụng thực tiễn trên các bộ dữ liệu quy mô lớn, thúc đẩy sự phát triển của học máy có trách nhiệm và hiệu quả.

6.1. Tổng kết ưu và nhược điểm của các phương pháp đề xuất

Ưu điểm chính của các phương pháp dựa trên MIP là khả năng tìm ra giải pháp tối ưu được chứng minh và tính linh hoạt trong việc mô hình hóa các ràng buộc phức tạp như chi phí phân loại sai và ràng buộc thời gian. Mô hình PathOCT nổi bật với thiết kế nhỏ gọn cho cây không cân bằng. Tuy nhiên, nhược điểm lớn nhất là độ phức tạp tính toán. Các mô hình này phụ thuộc nhiều vào hiệu quả của các bộ giải MIP (như CPLEX) và thời gian chạy có thể tăng nhanh khi độ sâu của cây hoặc kích thước dữ liệu tăng. Ngược lại, các thuật toán tham lam truyền thống nhanh hơn nhiều nhưng không đảm bảo tính tối ưu.

6.2. Hướng phát triển tiềm năng để giải quyết các bài toán lớn

Để khắc phục hạn chế về khả năng mở rộng, các nghiên cứu trong tương lai có thể khám phá một số hướng đi. Thứ nhất, áp dụng các kỹ thuật phân rã như Benders decomposition để giảm kích thước mô hình. Thứ hai, sử dụng các phương pháp sinh cột để chỉ tạo ra các biến cần thiết một cách linh động, thay vì định nghĩa tất cả ngay từ đầu. Một hướng khác là kết hợp các phương pháp chính xác với heuristic. Ví dụ, sử dụng một thuật toán tham lam để nhanh chóng tìm ra một giải pháp tốt ban đầu, sau đó sử dụng mô hình MIP để cải thiện giải pháp đó trong một vùng lân cận giới hạn. Những hướng đi này hứa hẹn sẽ làm cho việc xây dựng cây quyết định tối ưu trở nên khả thi hơn cho các ứng dụng công nghiệp quy mô lớn.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên trí tuệ nhân tạo và phân tích dữ liệu lớn, hơn 70% các quyết định chẩn đoán lâm sàng trong y tế và thẩm định rủi ro tài chính phụ thuộc vào các mô hình phân lớp có khả năng giải thích cao. Cây quyết định (Decision Tree) là một trong những công cụ học máy phổ biến nhất nhờ cấu trúc trực quan dạng cây nhị phân. Tuy nhiên, các thuật toán quy nạp truyền thống như CART hay C4.5 áp dụng chiến lược tìm kiếm tham lam (greedy approach), chỉ tối ưu cục bộ tại từng nút phân nhánh mà không xét đến toàn bộ tác động của cây hoàn chỉnh. Điều này dẫn đến sự thiếu hụt nghiêm trọng khi bài toán thực tế đòi hỏi tối ưu hóa đa mục tiêu: vừa phải giảm thiểu chi phí phân loại sai, vừa phải đáp ứng các ràng buộc khắt khe về thời gian và ngân sách kiểm thử thuộc tính.

Luận văn thạc sĩ ngành Khoa học máy tính của tác giả Trần Quang Toàn, thực hiện tại Trường Đại học Phenikaa và bảo vệ vào tháng 04/2024 dưới sự hướng dẫn của TS. Vũ Đức Minh và PGS. Hà Minh Hoàng, đã giải quyết triệt để bài toán tối ưu tổ hợp phức tạp này. Đề tài tập trung xây dựng mô hình quy hoạch nguyên tuyến tính hỗn hợp (Mixed-Integer Programming - MIP) mới mang tên PathOCT nhằm thiết lập cây quyết định tối ưu toàn cục. Nghiên cứu tích hợp trực tiếp các hàm chi phí kiểm thử, ma trận chi phí phân loại sai bất đối xứng và giới hạn thời gian phản hồi cho từng nhãn lớp. Được kiểm nghiệm trên 9 bộ dữ liệu chuẩn quốc tế với 216 cấu hình thử nghiệm, công trình mang lại giải pháp cân bằng hoàn hảo giữa độ chính xác dự đoán, chi phí vận hành và thời gian thực thi, mở ra hướng ứng dụng đột phá cho các hệ thống y tế khẩn cấp và tài chính tự động.

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

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng vững chắc của lý thuyết tối ưu hóa tổ hợp và học máy nhạy cảm chi phí:

1. Lý thuyết Cây quyết định tối ưu (Optimal Classification Trees - OCT): Kế thừa nghiên cứu kinh điển của Hyafil và Rivest (1976) chứng minh việc xây dựng cây quyết định tối ưu là bài toán NP-khó, cùng với bước đột phá của Bertsimas và Dunn (2017) trong việc áp dụng mô hình quy hoạch nguyên hỗn hợp để tìm cây tối ưu toàn cục thay vì dựa vào các bước cắt tỉa tham lam.
2. Lý thuyết Học máy nhạy cảm với chi phí (Cost-Sensitive Learning): Tiếp cận theo các nguyên lý của Turney (1995) và Ling cùng cộng sự (2004), phân định rõ hai nhóm chi phí thực tế gồm chi phí thực hiện kiểm thử thuộc tính và chi phí thiệt hại do phân loại sai. Trong y tế, việc phân loại sai ca dương tính thành âm tính gây hậu quả nghiêm trọng hơn rất nhiều so với trường hợp ngược lại.
3. Mô hình Quy hoạch nguyên tuyến tính hỗn hợp (MIP): Sử dụng hệ thống biến nhị phân để mô hình hóa cấu trúc cây, đường dẫn từ gốc tới lá và các điều kiện rẽ nhánh logic.

Khung lý thuyết của luận văn định nghĩa rõ 4 khái niệm trung tâm: Cây quyết định cân bằng (BCS - Balanced Cost Sensitive), Cây quyết định không cân bằng (ICS - Imbalanced Cost Sensitive), Chi phí kiểm thử thuộc tính và Ràng buộc thời gian giới hạn của nhãn dự đoán.

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

Nghiên cứu sử dụng phương pháp định lượng thực nghiệm, kết hợp mô hình hóa toán học và giải thuật tối ưu hóa chính xác:

• Nguồn dữ liệu và Cỡ mẫu: Thực nghiệm được tiến hành trên 9 bộ dữ liệu chuẩn từ kho dữ liệu máy học UCI với quy mô từ 101 mẫu (bộ dữ liệu Zoo) đến 1.728 mẫu (bộ dữ liệu Car Evaluation), số lượng thuộc tính dao động từ 6 đến 16 và số lượng ngưỡng phân tách từ 6 đến 194. Lý do lựa chọn 9 bộ dữ liệu này là để bao phủ đa dạng các đặc tính: dữ liệu nhị phân, đa lớp, dữ liệu y tế (Diabetes, Heart, Diagnosis) và dữ liệu xã hội học.
• Phương pháp chọn mẫu và Thiết lập kiểm thử: Áp dụng phương pháp phân chia dữ liệu ngẫu nhiên 5 lần lặp với tỷ lệ 75% cho tập huấn luyện (training) và 25% cho tập kiểm thử (testing). Mỗi bộ dữ liệu được khảo sát qua 120 trường hợp thử nghiệm (instances), tương ứng với các độ sâu cây từ 2 đến 5 và các tham số phạt phức tạp lần lượt là 0.25, 0.50 và 0.75.
• Phương pháp phân tích và Công cụ triển khai: Luận văn lập trình toàn bộ mô hình toán học bằng ngôn ngữ C++, sử dụng bộ giải thương mại IBM ILOG CPLEX chạy trên hệ thống phần cứng chip AMD Ryzen với 16GB RAM. Mỗi bài toán được thiết lập thời gian chạy tối đa là 60 phút (3.600 giây). Phương pháp phân tích dựa trên sự so sánh trực tiếp 4 chỉ số hiệu năng: chi phí phân loại sai, độ chính xác ngoài mẫu, thời gian tính toán và giá trị hàm mục tiêu.

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

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

Quá trình thực nghiệm đối sánh mô hình đề xuất PathOCT với các mô hình tiên tiến hàng đầu thế giới hiện nay như FlowOCT của Aghaei và cộng sự (2020) cùng BinOCT của Verwer và Zhang (2019) đã mang lại các kết quả nổi bật:

1. Hiệu năng vượt trội của mô hình cây không cân bằng (ICS-PathOCT): Trong các kịch bản ràng buộc thời gian nghiêm ngặt, ICS-PathOCT vượt trội hơn hẳn mô hình ICS-FlowOCT về khả năng giảm thiểu chi phí phân loại sai trên 51 trường hợp thử nghiệm, trong khi ICS-FlowOCT chỉ chiếm ưu thế ở 35 trường hợp.
2. Độ chính xác và Giá trị hàm mục tiêu tối ưu: Trên tổng số 216 điểm dữ liệu trung bình phân tích, mô hình ICS-PathOCT đạt độ chính xác tương đương hoặc nhỉnh hơn ICS-FlowOCT trong 130 trên 216 trường hợp, đồng thời vượt trội về giá trị hàm mục tiêu tối ưu ở 122 trên 216 trường hợp.
3. Kiểm soát chi phí phân loại sai trong cây cân bằng (BCS-PathOCT): Mặc dù mô hình CS-BinOCT có tốc độ giải nhanh nhất nhưng lại ghi nhận mức chi phí phân loại sai cao hơn từ 15% đến 25% do cấu trúc ban đầu vốn chỉ tập trung tối đa hóa độ chính xác đơn thuần. Ngược lại, BCS-PathOCT duy trì hiệu quả kiểm soát chi phí thiệt hại phân loại sai tốt nhất trên toàn bộ tập kiểm thử.
4. Giảm thiểu kích thước mô hình: Bằng kỹ thuật biểu diễn bitset theo đường dẫn, số lượng ràng buộc trong ICS-PathOCT giảm hơn 30% so với ICS-FlowOCT, loại bỏ hoàn toàn việc sử dụng tham số Big-M gây lỏng biên quy hoạch tuyến tính.

Thảo luận kết quả

Các kết quả thực nghiệm được tổng hợp và biểu diễn chi tiết thông qua các biểu đồ phân bố hiệu suất (tương ứng Hình 5.1 và Hình 5.2 trong luận văn) cùng hệ thống bảng số liệu thống kê 216 cấu hình tham số. Dữ liệu cho thấy rõ nguyên nhân mô hình PathOCT đạt hiệu quả cao là nhờ cơ chế biến các nút không phân nhánh thành "nút rỗng" (empty nodes) thay vì cắt tỉa vật lý. Cơ chế này giúp giữ nguyên hình thái cây hoàn chỉnh, cho phép gán trực tiếp các thuộc tính kiểm thử có độ trễ lớn nhưng mang lại giá trị phân lớp cao mà không làm vi phạm ngưỡng thời gian tổng thể của toàn bộ đường dẫn.

Khi so sánh với các nghiên cứu trước đây, mô hình FlowOCT tuy có độ nới lỏng quy hoạch tuyến tính mạnh nhưng khi bổ sung ràng buộc thời gian và chi phí, việc phát sinh thêm biến chỉ thị và tham số Big-M đã làm tăng đột biến không gian tìm kiếm, dẫn đến thời gian giải bị kéo dài. Trong khi đó, PathOCT duy trì số lượng biến số ở mức tối thiểu, giúp bộ giải CPLEX dễ dàng tìm ra nghiệm tối ưu toàn cục. Trong ứng dụng y tế thực tế, việc tối ưu hóa này giúp giảm đáng kể tỷ lệ chẩn đoán sai các bệnh lý nguy hiểm (như đái tháo đường hay bệnh tim mạch) trong khi vẫn đảm bảo hoàn thành chuỗi xét nghiệm trước thời hạn quy định.

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

Nhằm chuyển hóa các kết quả nghiên cứu học thuật thành giá trị ứng dụng thực tiễn trong y tế và công nghệ thông tin, luận văn đề xuất 4 giải pháp trọng tâm:

1. Tích hợp mô hình ICS-PathOCT vào Hệ thống hỗ trợ ra quyết định lâm sàng (CDSS): Triển khai thử nghiệm thuật toán tại các khoa cấp cứu và chẩn đoán hình ảnh của các bệnh viện đa khoa nhằm cắt giảm từ 20% đến 30% chi phí xét nghiệm không cần thiết, hoàn thành mục tiêu trong giai đoạn quý 1 đến quý 2 năm 2025. Chủ thể thực hiện là Ban Giám đốc bệnh viện phối hợp với các chuyên gia tin học y tế.
2. Phát triển thuật toán phân rã toán học quy mô lớn: Nghiên cứu ứng dụng kỹ thuật phân rã Benders (Benders Decomposition) hoặc phương pháp sinh cột (Column Generation) để mở rộng khả năng xử lý của mô hình lên các bộ dữ liệu lớn hơn 10.000 bản ghi, đảm bảo thời gian hội tụ dưới 300 giây vào quý 3 năm 2025. Chủ thể thực hiện là nhóm nghiên cứu Tối ưu hóa tại các trường đại học và viện nghiên cứu.
3. Chuẩn hóa danh mục ma trận chi phí và thời gian xét nghiệm: Xây dựng cơ sở dữ liệu số hóa đồng bộ về thời gian thực hiện và chi phí kinh tế của từng loại xét nghiệm cận lâm sàng theo định mức của Bộ Y tế trong quý 2 đến quý 4 năm 2025. Chủ thể thực hiện là Phòng Quản lý chất lượng bệnh viện và Kỹ sư dữ liệu.
4. Xây dựng phần mềm đóng gói mã nguồn mở với giao diện trực quan: Đóng gói thư viện C++ kết hợp API Python để các bác sĩ và nhà phân tích dữ liệu có thể dễ dàng thiết lập cây quyết định tối ưu theo thời gian thực trước quý 4 năm 2025. Chủ thể thực hiện là các doanh nghiệp khởi nghiệp công nghệ y tế (HealthTech).

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

Công trình luận văn thạc sĩ này là tài liệu tham khảo chuyên sâu và giá trị đối với 4 nhóm đối tượng:

1. Nhà nghiên cứu và Học viên cao học ngành Khoa học máy tính, Vận trù học: Khai thác chi tiết cách thiết lập mô hình MIP, kỹ thuật biểu diễn đường dẫn bitset và các phương pháp chứng minh tính tối ưu để phát triển các thuật toán học máy giải tích mới.
2. Kỹ sư Trí tuệ nhân tạo và Nhà khoa học dữ liệu trong lĩnh vực Y tế: Ứng dụng mô hình để xây dựng các giải pháp chẩn đoán bệnh tự động có khả năng giải thích cao (Explainable AI - XAI), đáp ứng đồng thời tiêu chuẩn an toàn bệnh nhân và giới hạn ngân sách bảo hiểm y tế.
3. Bác sĩ chuyên khoa, Trưởng khoa Xét nghiệm và Nhà quản trị bệnh viện: Tham khảo phương pháp luận tối ưu hóa chuỗi quy trình xét nghiệm cận lâm sàng, nâng cao hiệu suất sử dụng thiết bị y tế và giảm thời gian chờ đợi của bệnh nhân trong các ca cấp cứu.
4. Chuyên gia Phân tích rủi ro trong Tài chính và Ngân hàng: Áp dụng cây quyết định nhạy cảm chi phí để thiết kế hệ thống thẩm định tín dụng và phát hiện gian lận giao dịch với thời gian phản hồi dưới 5 giây.

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

1. Mô hình PathOCT khác biệt như thế nào so với các thuật toán cây quyết định truyền thống như CART? Các thuật toán như CART sử dụng phương pháp tham lam đệ quy, chỉ tối ưu việc phân nhánh tại từng nút cục bộ mà không đảm bảo cây tạo ra là tối ưu toàn cục. PathOCT sử dụng quy hoạch nguyên hỗn hợp (MIP), xem xét đồng thời mọi đường dẫn từ gốc đến lá, giúp tối ưu hóa toàn diện độ chính xác và giảm thiểu chi phí trên toàn bộ cấu trúc cây.

2. Tại sao cần tích hợp đồng thời ràng buộc thời gian và chi phí phân loại sai trong mô hình? Trong các trường hợp khẩn cấp như chẩn đoán bệnh tim mạch hay xét nghiệm dịch bệnh, kết quả bắt buộc phải có trước một thời hạn nhất định. Đồng thời, việc bỏ sót ca bệnh nặng (âm tính giả) gây thiệt hại lớn hơn nhiều so với việc chẩn đoán nhầm (dương tính giả), đòi hỏi mô hình phải tính toán trọng số thiệt hại bất đối xứng.

3. Cơ chế biểu diễn bitset trong PathOCT mang lại lợi thế kỹ thuật gì? Cơ chế bitset biểu diễn từng đường dẫn từ gốc tới lá dưới dạng chuỗi bit nhị phân cố định, cho phép kiểm tra sự tương thích của điểm dữ liệu trực tiếp qua phép so sánh tham số. Kỹ thuật này giúp loại bỏ hoàn toàn các tham số Big-M phức tạp, làm chặt biên quy hoạch tuyến tính và tăng tốc độ giải của phần mềm CPLEX.

4. Mô hình có thể xử lý các bộ dữ liệu quy mô lớn trong thời gian bao lâu? Với các bộ dữ liệu quy mô dưới 2.000 mẫu và độ sâu cây từ 2 đến 5, mô hình giải quyết tối ưu trong vòng dưới 60 phút trên máy tính đơn nhân. Đối với các tập dữ liệu cực lớn, việc kết hợp thêm các kỹ thuật phân rã toán học sẽ giúp duy trì thời gian giải tối ưu ở mức vài phút.

5. Lợi ích nổi bật của cây quyết định không cân bằng (ICS-PathOCT) là gì? Cây quyết định không cân bằng cho phép tồn tại các nút rỗng trên từng nhánh, tạo sự linh hoạt tối đa khi gán các thuộc tính đắt đỏ hoặc tốn nhiều thời gian vào các nhánh quan trọng mà không làm vi phạm giới hạn thời gian chung của toàn bộ cây, mang lại độ chính xác cao hơn cây cân bằng.

Kết luận

• Đóng góp lý thuyết: Luận văn đã đề xuất thành công mô hình toán học mới PathOCT cùng hai biến thể BCS-PathOCT và ICS-PathOCT, giải quyết triệt để bài toán xây dựng cây quyết định tối ưu có ràng buộc thời gian và nhạy cảm chi phí.
• Đột phá về giải thuật: Phát triển kỹ thuật biểu diễn đường dẫn bitset và cơ chế nút rỗng độc đáo, loại bỏ hoàn toàn các tham số Big-M và giảm tải hơn 30% số lượng ràng buộc so với các mô hình trước đây.
• Kiểm chứng thực nghiệm toàn diện: Đánh giá nghiêm ngặt trên 9 bộ dữ liệu chuẩn với 216 trường hợp thử nghiệm, chứng minh tính vượt trội về khả năng kiểm soát chi phí phân loại sai so với FlowOCT và BinOCT.
• Giá trị ứng dụng thực tiễn: Cung cấp công cụ chẩn đoán có khả năng giải thích 100%, đáp ứng trọn vẹn yêu cầu khắt khe trong y tế cấp cứu, quản trị chuỗi xét nghiệm lâm sàng và thẩm định tài chính.
• Định hướng phát triển: Nghiên cứu tiếp tục mở rộng áp dụng các phương pháp phân rã toán học nâng cao nhằm tối ưu hóa hiệu năng tính toán cho các tập dữ liệu lớn trong năm 2025.

Quý độc giả, các nhà nghiên cứu và doanh nghiệp quan tâm có thể khai thác mã nguồn và mô hình toán học từ luận văn để triển khai vào các bài toán tối ưu hóa phân loại thực tế tại đơn vị.

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

phần mở đầu, khóa luận gồm các chương chính như sau. Chương 2 nêu tổng quan các nghiên cứu có liên quan và thảo luận về các thuật toán trong việc xây dựng cây quyết định nhạy cảm với chi phí - ràng buộc về tài nguyên. Chương 3 đề xuất mô hình toán học mới và các khái niệm quan trọng cho bài toán cây quyết định tối ưu. Chương 4 trình bày về việc làm sao chúng tôi có thể thu được các mô hình đã có thông qua việc điều chỉnh các giới hạn thời gian và chi phí của các thuộc tính.

Chương 5 báo cáo kết quả thực nghiệm và kết luận; gồm có việc so sánh các kết quả giữa các mô hình, kết luận và đề xuất các hướng phát triển trong tương lai. Tran Quang Toan - 21800025 - KHMT 13 Chương 2 Tổng quan nghiên cứu Phân lớp dữ liệu là một bài toán quan trọng trong lĩnh vực trí tuệ nhân tạo, trong đó dữ liệu tương lai sẽ được dự đoán bởi các mô hình được tạo lập từ các dữ liệu huấn luyện. Một số kỹ thuật phân lớp phổ biến có thể kể đến gồm có: phân lớp dựa vào cây quyết định, bộ phân lớp Bayesian, bộ phân lớp mạng Neural và lập luận theo tình huống. Trong các phương pháp này, cây quyết định là phương pháp có khả năng biểu diễn các cấu trúc phức tạp và có hiệu quả tính toán cao, cùng với khả năng tạo ra các quy tắc phân lớp dễ hiểu.

Vì vậy, khóa luận lựa chọn xây dựng cây quyết định tối ưu để phù hợp với các ràng buộc phức tạp thường xảy ra trong các bài toán y tế mà khóa luận hướng tới.1 Cây quyết định tối ưu & phương pháp Hyafil and Rivest [1976] chỉ ra rằng bài toán xây dựng cây quyết định tối ưu chính là một bài toán tối ưu tổ hợp NP-khó với số biến quyết định theo cấp số nhân của dữ liệu đầu vào. Do là bài toán NP-khó, nhiều tác giả đã đề xuất các thuật toán xấp xỉ, tham lam hoặc tối ưu top-down trong đó có thể kể đến Breiman et al. Breiman et al. Điểm yếu của phương pháp tham lam là việc phân tách nút trong của cây quyết định được xác định một cách độc lập và cục bộ mà không xem xét tác động có thể có của các lần phân tách tiếp theo.

Vì yếu tố cục bộ, việc giảm thiểu độ sai lệch tại nút phân nhánh riêng lẻ không thể xem xét hết các các đặc điểm của bộ dữ liệu huấn luyện và do đó, có khả năng dẫn đến hiệu suất phân lớp kém với các dữ liệu thực tế. Một nhược điểm của phương pháp quy nạp từ trên xuống là cần có các quy tắc cắt tỉa cây để bỏ đi những nhánh không hiệu quả. Do các phương pháp này không thể xem xét đầy đủ các hình phạt (penalties) đối với độ phức tạp của cây, các phân tách mạnh có thể ẩn sau các phân tách yếu hơn trong khi phát triển cây. Khi hình phạt độ Tran Quang Toan - 21800025 - KHMT 14 phức tạp (complexity penalty) quá cao, sự phân tách yếu hơn đầu tiên có thể bị ngăn không cho chọn, từ đó không tạo được cây tốt hơn.

Để khắc phục nhược điểm này, quá trình huấn luyện diễn ra theo hai giai đoạn, phát triển cây càng sâu càng tốt thông qua một loạt các quyết định tham lam, sau đó cắt tỉa cây bằng cách sử dụng hình phạt độ phức tạp. Để giải quyết vấn đề phân tách mạnh bị ẩn đằng sau phân tách yếu hơn, các phương pháp heuristic thường được sử dụng, chẳng hạn như một số thiết kế cải tiến của ID3: IDX đề xuất bởi Norton [1989], LSID3 và ID3-k đề xuất bởi Esmeir and Markovitch [2007], nhằm tìm ra các phân tách mới dựa trên việc tối ưu hóa các cây sâu hơn bắt nguồn từ lá hiện tại, thay vì chỉ tối ưu hóa phân tách đơn lẻ. Tuy nhiên, trong Murthy and Salzberg [1995] các tác giả chỉ ra rằng các phương pháp này không đảm bảo sẽ tạo ra các cây có khả năng khái quát hóa tốt hơn và đồng thời tránh cái gọi là sự tiên đoán trong việc xây dựng cây quyết định. Mặc dù việc kết hợp giai đoạn xây dựng và cắt tỉa trong việc phát triển cây quyết định vốn dĩ có thể tốt hơn, nhưng điều này dẫn đến khó khăn trong việc tìm ra giải pháp tối ưu do những hạn chế thực tế về thời gian.

Một số phương pháp heuristic, bao gồm tối ưu hóa tuyến tính trong Bennett [1992], tối ưu hóa liên tục trong Bennett and Blue [1996], quy hoạch động trong Cox et al. [1989]; Payne and Meisel [1977], giải thuật di truyền trong Son [1998], và các phương pháp dựa trên kỹ thuật giảm độ dốc ngẫu nhiên (stochastic gradient descent) trong Norouzi et al. [2015], được áp dụng để phát triển cây chỉ trong một bước. Tuy nhiên, việc tạo ra các cây tối ưu được chứng nhận trong thời gian thực tế bằng cách sử dụng các phương pháp heuristic vẫn còn là thách thức chưa có lời giải.

Sự phát triển của các thuật toán và phần mềm tối ưu nguyên gần đây đã dẫn đến sự xuất hiện của nhiều nghiên cứu xây dụng mô hình toán học cho bài toán cây quyết định. Các mô hình toán học cho phép linh hoạt trong việc mô hình hóa các mục tiêu và ràng buộc khác nhau, như tính công bằng và diễn giải, cũng như các ràng buộc về quy tắc phân nhánh tuyến tính. Rất nhiều phương pháp MIP gần đây đã được đề xuất trong các nghiên cứu. Tuy nhiên, do số lượng biến thường là cấp số mũ của dữ liệu huấn luyện, Các mô hình quy hoạch nguyên thường giới hạn độ sâu của cây để các phần mềm giải chúng có thể hoạt động hiệu quả.

Bertsimas and Dunn [2017] xem xét cả phân tách quyết định đơn biến và đa biến khi xây dựng cây phân loại tối ưu. Cấu trúc của cây không cố định mà được điều khiển bởi một tham số của hàm mục tiêu. Khi giá trị các tham số tăng lên, có thể sẽ dẫn đến nhiều nút lá không ứng với dữ liệu nào và một số nút trong cũng không được gán bất Tran Quang Toan - 21800025 - KHMT 15 kỳ thuộc tính nào. Do đó, kỹ thuật cắt tỉa được kết hợp ngay trong quá trình xây dựng cây thông qua mô hình MIP, được gọi là OCT, thay vì thực hiện từng bước như trong các phương pháp quy nạp từ trên xuống.

Kiểm thử cho thấy rằng OCT cung cấp mức cải thiện 1-2% về độ chính xác trên dữ liệu ngoài mẫu đối với các kiểm thử đơn biến và cải thiện 3-5% đối với các kiểm thử đa biến. Gunluk et al. [2016] đề xuất một mô hình MILP cho bài toán xây dựng cây phân loại dữ liệu có tính chất thuộc tính. Bằng cách khai thác tính chất rời rạc của dữ liệu, các quyết định có thể được xác định dựa trên tổ hợp các kiểm tra tại mỗi nút.

Một lợi thế của kỹ thuật này là số lượng biến số nguyên trong mô hình không phụ thuộc vào kích thước của dữ liệu đào tạo. Bốn cấu hình cây được đề nghị và được đánh giá bằng kỹ thuật xác thực chéo để tìm ra lựa chọn tốt nhất. Các thử nghiệm chỉ ra rằng thuật toán của họ vượt trội hơn CART về độ chính xác với các bộ dữ liệu nhỏ. Dash et al.

[2018] giới thiệu một mô hình ILP để học các quy tắc quyết định Boolean ở dạng chuẩn tắc tuyển hoặc dạng chuẩn tắc hội. Mô hình được đề xuất hoạt động như một mô hình khả diễn để phân loại thông qua phương pháp sinh cột (column generation). Các tác giả xem xét sự đánh đổi giữa độ chính xác và tính đơn giản của các quy tắc được chọn. Kết quả tính toán cho thấy phương pháp sinh cột có khả năng cạnh tranh cao với các thuật toán hiện đại khác.

Áp dụng kỹ thuật tương tự, Firat et al. [2020] sử dụng lấy mẫu ngưỡng trên các nút quyết định để xây dựng cây phân lớp nhị phân đơn biến. Cách tiếp cận của họ đánh đổi sự tối ưu để có được tốc độ xử lý các tập dữ liệu lớn chứa hàng chục nghìn hàng dữ liệu. Verwer and Zhang [2017] đề xuất một cách mã hóa hiệu quả cho việc xây dựng cả cây phân loại và cây hồi quy của các phân tách đơn biến có độ sâu cho trước.

So với Bertsimas and Dunn [2017], mô hình giảm số lượng biến quyết định từ hàm mũ sang hàm tuyến tính. Phương pháp này thu được kết quả tốt trên các cây có độ sâu tối đa là năm và các bộ dữ liệu nhỏ có kích thước tối đa 1000. Để tăng tốc quá trình học, các tác giả đề xuất trong Verwer and Zhang [2019] mô hình quy hoạch nguyên nhị phân, được gọi là BinOCT. Kết quả thực nghiệm cho thấy BinOCT vượt trội hơn mô hình toán học trong Bertsimas and Dunn [2017] trên các bộ dữ liệu mà có không quá 5000 điểm dữ liệu cả về cả độ chính xác và thời gian tính toán.

Gần đây, Aghaei et al. [2020] đề xuất mô hình MIP FlowOCT dựa trên luồng để học cây phân loại tối ưu với các thuộc tính nhị phân. Cây được chuyển sang dạng đồ thị bằng cách thêm nguồn, đích và các cạnh nối các nút của cây với đích. Các điểm dữ liệu có thể xem như luồng bắt đầu từ nguồn, đi qua nhiều nút trong và lá phù hợp, Tran Quang Toan - 21800025 - KHMT 16 sau đó đến đích.

Các tác giả chỉ ra rằng mô hình liên tục tương ứng của họ mạnh hơn so với các mô hình hiện có. Thực nghiệm cho thấy FlowOCT tốt hơn các mô hình đã có cả về chất lượng nghiệm trong mẫu và ngoài mẫu. Verhaeghe et al. [2020] đề xuất hướng tiếp cận quy hoạch ràng buộc (Constraint Programming) để giải bài toán xây dựng cây quyết định tối ưu.

Ràng buộc độ sâu tối đa và ràng buộc hỗ trợ tối thiểu được áp dụng với tìm kiếm nhánh cận (branch-and- bound search). Tuy nhiên, phương pháp này chỉ thích hợp đối với các bài toán phân loại hai lớp. Kết quả kiểm thử cho thấy phương pháp này cung cấp lời giải cạnh tranh so với BinOCT. Thuật toán DL8 được giới thiệu trong Nijssen and Fromont [2007, 2010] dựa trên một nhóm ý tưởng khác với các mô hình dựa trên MIP.

Các tác giả áp dụng kỹ thuật khai phá dữ liệu để tìm kiếm trong không gian các đường đi khả thi một cách hiệu quả và thực hiện quy hoạch động trên các đường đi đó để xây dựng cây quyết định tối ưu. Mô hình này vượt trội đáng kể so với các mô hình dựa trên MIP. Trong Aglin et al.