Luận văn ThS VNU: Tối ưu cây quyết định bằng tìm kiếm lân cận biến đổi

Luận văn thạc sĩ VNU nghiên cứu tối ưu hóa cây quyết định dựa trên phương pháp tìm kiếm lân cận biến đổi, mang lại hiệu quả cao trong phân tích dữ liệu.

• Tác giả: Dang, Cong Kien
• Trường học: Institut de la Fran ophonie pour l'Informatique
• Chuyên ngành: Informatique
• Đề tài: Optimisation des arbres de décision basée sur recherche à voisinage variable
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2006
• Địa điểm: Hà Nội

Mục lục chi tiết

• TÓM TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH VẼ
• DANH MỤC CÁC THUẬT TOÁN
• 1. Chương 1: GIỚI THIỆU
• 1.1. Phân loại
• 1.2. Cây quyết định và các phương pháp xây dựng
• 1.3. Tối ưu hóa tổ hợp và tìm kiếm heuristic
• 1.4. Đặt vấn đề và cấu trúc báo cáo
• 2. Chương 2: PHÂN LOẠI VÀ CÂY QUYẾT ĐỊNH
• 2.1. Cây quyết định
• 2.2. Xây dựng cây quyết định
• 2.2.1. Lựa chọn quy tắc phân chia
• 2.2.2. Gán lớp cho một nút
• 2.3. Đánh giá cây quyết định
• 3. Chương 3: TỐI ƯU HÓA TỔ HỢP VÀ TÌM KIẾM LÂN CẬN BIẾN ĐỔI
• 3.1. Nguyên lý tìm kiếm lân cận biến đổi
• 3.2. Các mở rộng của tìm kiếm cục bộ
• 3.3. Các mở rộng cơ chế khảo sát lân cận
• 4. Chương 4: THUẬT TOÁN TỐI ƯU HÓA CÂY QUYẾT ĐỊNH DỰA TRÊN TÌM KIẾM LÂN CẬN BIẾN ĐỔI
• 4.1. Thuật toán tối ưu hóa cơ bản
• 4.2. Tìm kiếm cục bộ
• 4.3. Cấu trúc lân cận
• 4.4. Xây dựng cây dựa trên thuật toán tối ưu hóa
• 5. Chương 5: THỰC NGHIỆM VÀ KẾT QUẢ
• 5.1. Thực nghiệm tìm kiếm cục bộ
• 5.1.1. Thử nghiệm tối ưu hóa ngưỡng
• 5.1.2. Thử nghiệm tối ưu hóa phân chia
• 5.1.3. Quan sát ảnh hưởng của cấu trúc cây
• 5.1.4. Quan sát ảnh hưởng của lời giải ban đầu
• 5.2. Tối ưu hóa các cây quyết định
• 5.3. Xây dựng cây dựa trên tối ưu hóa
• 6. Chương 6: KẾT LUẬN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Khám phá luận văn VNU Tối ưu hóa cây quyết định bằng VNS

Luận văn thạc sĩ tại Đại học Quốc gia Hà Nội (VNU) về chủ đề “Optimisation des arbres de décision basée sur recherche à voisinage variable” là một công trình nghiên cứu chuyên sâu, giải quyết một vấn đề cốt lõi trong lĩnh vực học máy (machine learning) và khai phá dữ liệu (data mining). Trọng tâm của nghiên cứu này là cải thiện hiệu suất của mô hình cây quyết định (decision tree), một trong những công cụ phân lớp phổ biến nhất. Các thuật toán xây dựng cây truyền thống như C4.5 hay CART thường sử dụng phương pháp 'tham lam' (greedy), vốn không đảm bảo tìm ra cấu trúc cây tối ưu toàn cục. Luận văn này đề xuất một hướng tiếp cận mới, ứng dụng một thuật toán metaheuristic mạnh mẽ là Tìm kiếm Lân cận Thay đổi - Variable Neighborhood Search (VNS). Mục tiêu chính là tinh chỉnh và cải thiện các cây quyết định đã được xây dựng, nhằm giảm tỷ lệ lỗi và tăng độ chính xác trên các bài toán phân lớp. Bằng cách khám phá một cách có hệ thống các không gian giải pháp khác nhau, phương pháp này hứa hẹn sẽ thoát khỏi các điểm tối ưu cục bộ mà các thuật toán truyền thống thường mắc phải. Đây là một đóng góp quan trọng, không chỉ mang giá trị học thuật mà còn có tiềm năng ứng dụng thực tiễn lớn.

1.1. Tổng quan về mô hình cây quyết định trong học máy

Cây quyết định là một mô hình dự đoán được sử dụng rộng rãi trong thống kê, khai phá dữ liệu và học máy. Mô hình này sử dụng cấu trúc dạng cây để đưa ra các quyết định. Mỗi nút trong của cây biểu diễn một 'phép thử' trên một thuộc tính (ví dụ: 'Tuổi < 50?'), mỗi nhánh biểu diễn kết quả của phép thử đó, và mỗi nút lá đại diện cho một nhãn lớp (quyết định cuối cùng). Ưu điểm lớn của decision tree là tính dễ hiểu và dễ diễn giải. Người dùng có thể dễ dàng hình dung và truy vết logic phân loại của mô hình. Tuy nhiên, việc xây dựng một cây quyết định tối ưu là một bài toán NP-hard, đòi hỏi các thuật toán heuristic để tìm ra giải pháp gần đúng.

1.2. Vai trò của tối ưu hóa trong bài toán phân lớp dữ liệu

Tối ưu hóa (optimisation) đóng vai trò trung tâm trong hầu hết các bài toán phân lớp. Mục tiêu không chỉ là xây dựng một mô hình có độ chính xác cao trên dữ liệu huấn luyện, mà còn phải đảm bảo mô hình đó có khả năng tổng quát hóa tốt trên dữ liệu mới. Các thuật toán xây dựng cây truyền thống tối ưu hóa theo từng bước (local optimization), chọn thuộc tính tốt nhất tại mỗi nút. Điều này có thể dẫn đến một cấu trúc cây không phải là tốt nhất về mặt tổng thể. Do đó, các kỹ thuật tối ưu hóa toàn cục, như các thuật toán metaheuristic, được nghiên cứu để cải thiện chất lượng của cây sau khi đã được xây dựng, ví dụ như thông qua kỹ thuật cắt tỉa cây quyết định (decision tree pruning) hoặc tìm kiếm lại các quy tắc phân chia tốt hơn.

1.3. Giới thiệu luận văn khoa học máy tính của Đặng Công Kiên

Luận văn thạc sĩ của tác giả Đặng Công Kiên, thực hiện tại Viện Tin học Pháp ngữ (IFI) và bảo vệ tại Đại học Công nghệ - Đại học Quốc gia Hà Nội, tập trung vào việc áp dụng thuật toán VNS để cải thiện các cây quyết định. Công trình này xuất phát từ nhận định rằng các thuật toán kinh điển như C4.5 của Quinlan và CART của Đại học Stanford, dù hiệu quả, vẫn có thể được cải thiện. Luận văn đề xuất một quy trình gồm hai bước: xây dựng cây ban đầu bằng phương pháp truyền thống và sau đó sử dụng VNS để tinh chỉnh các quy tắc phân chia tại các nút, nhằm tìm ra một cấu trúc cây có hiệu suất cao hơn. Đây là một cách tiếp cận hậu tối ưu hóa (post-optimization) đầy hứa hẹn.

II. Thách thức lớn Vì sao cây quyết định cần được tối ưu hóa

Mặc dù mô hình cây quyết định rất mạnh mẽ và dễ diễn giải, quá trình xây dựng chúng phải đối mặt với nhiều thách thức cố hữu. Vấn đề lớn nhất bắt nguồn từ bản chất của các thuật toán xây dựng cây phổ biến. Các thuật toán như ID3, C4.5 và CART đều tuân theo một chiến lược đệ quy, chia để trị (divide and conquer) dựa trên phương pháp 'tham lam' (greedy). Tại mỗi bước, thuật toán lựa chọn thuộc tính phân chia giúp giảm độ 'nhiễu' (impurity) nhiều nhất, ví dụ như dựa vào Information Gain hoặc Gini Index. Chiến lược này hiệu quả về mặt tính toán, nhưng nó chỉ đảm bảo tối ưu tại từng bước cục bộ. Một quyết định phân chia tốt nhất ở gốc cây có thể dẫn đến các nhánh con khó phân loại hơn, và kết quả là một cây tổng thể không tối ưu. Vấn đề này được gọi là 'hiệu ứng chân trời' (horizon effect). Hơn nữa, việc xây dựng cây quá phức tạp để khớp hoàn toàn với dữ liệu huấn luyện sẽ dẫn đến hiện tượng quá khớp (overfitting), làm giảm đáng kể hiệu suất của mô hình khi đối mặt với dữ liệu mới. Những hạn chế này là động lực chính để tìm kiếm các phương pháp tối ưu hóa toàn cục hơn, như đề xuất trong luận văn.

2.1. Hạn chế của phương pháp tham lam greedy trong C4.5 và CART

Phương pháp 'tham lam' hoạt động bằng cách đưa ra lựa chọn tốt nhất có thể tại thời điểm hiện tại mà không cần xem xét các hệ quả trong tương lai. Trong bối cảnh xây dựng cây quyết định, điều này có nghĩa là chọn thuộc tính mang lại lợi ích thông tin tức thời lớn nhất. Tuy nhiên, một chuỗi các lựa chọn tối ưu cục bộ không nhất thiết tạo ra một giải pháp tối ưu toàn cục. Có thể tồn tại một thuộc tính phân chia ban đầu kém hấp dẫn hơn nhưng lại mở đường cho các phân chia tốt hơn ở các cấp độ sâu hơn của cây. Các thuật toán như C4.5 và CART, do bản chất 'tham lam', không có khả năng 'nhìn xa' và khám phá các lựa chọn thay thế này.

2.2. Nguy cơ mắc kẹt tại tối ưu cục bộ thay vì tối ưu toàn cục

Một hệ quả trực tiếp của phương pháp 'tham lam' là nguy cơ mô hình bị mắc kẹt tại một điểm tối ưu cục bộ (local optimum). Cấu trúc cây quyết định được tạo ra có thể là tốt nhất trong một 'lân cận' hẹp của các giải pháp, nhưng có thể có những cấu trúc cây hoàn toàn khác biệt mang lại hiệu suất vượt trội hơn. Các thuật toán tìm kiếm cục bộ (local search algorithms) truyền thống cũng dễ gặp phải vấn đề này. Khi một giải pháp đã đạt đến điểm tối ưu cục bộ, mọi thay đổi nhỏ đều làm giảm chất lượng, khiến thuật toán dừng lại, mặc dù giải pháp tối ưu toàn cục (global optimum) có thể nằm ở một vùng khác trong không gian tìm kiếm.

2.3. Vấn đề quá khớp overfitting và khả năng tổng quát hóa

Overfitting là một trong những thách thức nghiêm trọng nhất trong học máy. Nó xảy ra khi mô hình học thuộc lòng các chi tiết và nhiễu trong dữ liệu huấn luyện, thay vì học các quy luật tổng quát. Một cây quyết định bị overfitting thường rất phức tạp, có nhiều nhánh và độ sâu lớn, đạt độ chính xác gần như tuyệt đối trên tập huấn luyện nhưng lại hoạt động rất tệ trên dữ liệu chưa từng thấy. Các kỹ thuật như cắt tỉa cây quyết định được phát triển để chống lại overfitting, nhưng việc tìm ra điểm cân bằng lý tưởng giữa độ phức tạp và độ chính xác vẫn là một bài toán tối ưu hóa khó khăn.

III. Giải pháp đột phá Tối ưu cây quyết định bằng thuật toán VNS

Để vượt qua những hạn chế của phương pháp 'tham lam', luận văn đã đề xuất một giải pháp mạnh mẽ dựa trên thuật toán VNS (Variable Neighborhood Search). Đây là một thuật toán metaheuristic được thiết kế để khám phá không gian tìm kiếm một cách hiệu quả và có hệ thống, nhằm thoát khỏi các bẫy tối ưu cục bộ. Nguyên tắc cơ bản của VNS rất trực quan: một điểm tối ưu cục bộ đối với một cấu trúc lân cận này chưa chắc đã là tối ưu cục bộ đối với một cấu trúc lân cận khác. Bằng cách thay đổi linh hoạt các 'lân cận' trong quá trình tìm kiếm, VNS có khả năng di chuyển qua các 'thung lũng' trong không gian giải pháp để đến được những vùng có tiềm năng chứa lời giải tốt hơn. Trong bối cảnh tối ưu hóa cây quyết định, một 'giải pháp' chính là một cấu trúc cây cụ thể, và một 'lân cận' có thể được định nghĩa là tập hợp các cây có thể tạo ra bằng cách thay đổi một hoặc nhiều quy tắc phân chia của cây hiện tại. Cách tiếp cận này cho phép thuật toán không chỉ tinh chỉnh các ngưỡng phân chia mà còn có thể thay thế hoàn toàn thuộc tính tại một nút, tạo ra sự linh hoạt vượt trội so với các thuật toán tìm kiếm cục bộ đơn giản.

3.1. Nguyên lý cốt lõi của Variable Neighborhood Search VNS

Variable Neighborhood Search dựa trên ba quan sát đơn giản nhưng sâu sắc. Thứ nhất, một điểm tối ưu cục bộ trong một lân cận có thể không phải là tối ưu trong lân cận khác. Thứ hai, một điểm tối ưu toàn cục là tối ưu cục bộ đối với tất cả các cấu trúc lân cận có thể có. Thứ ba, các điểm tối ưu cục bộ thường có xu hướng tập trung gần nhau. Dựa trên đó, thuật toán VNS hoạt động theo chu trình: bắt đầu từ một giải pháp, nó sẽ tạo ra một điểm ngẫu nhiên trong một lân cận, thực hiện tìm kiếm cục bộ từ điểm đó, và nếu tìm thấy giải pháp tốt hơn thì cập nhật và quay lại lân cận đầu tiên. Nếu không, nó sẽ chuyển sang một lân cận lớn hơn và lặp lại quá trình. Cơ chế này giúp cân bằng giữa việc khai thác sâu (intensification) và khám phá rộng (diversification).

3.2. Cách thuật toán VNS thoát khỏi bẫy tối ưu cục bộ hiệu quả

Điểm mạnh nhất của thuật toán VNS là khả năng thoát khỏi các điểm tối ưu cục bộ. Khi một thuật toán tìm kiếm cục bộ thông thường bị mắc kẹt, VNS không dừng lại. Thay vào đó, nó sẽ 'lắc' (shake) giải pháp hiện tại bằng cách di chuyển đến một điểm ngẫu nhiên trong một lân cận xa hơn (lớn hơn). Hành động này được gọi là 'perturbation'. Sau khi 'lắc', thuật toán lại áp dụng tìm kiếm cục bộ để tìm điểm tối ưu mới trong vùng lân cận đó. Việc thay đổi cấu trúc lân cận một cách có hệ thống cho phép VNS nhảy qua các rào cản ngăn cách các vùng tối ưu khác nhau, tăng đáng kể cơ hội tìm thấy giải pháp tối ưu toàn cục hoặc một giải pháp tiệm cận chất lượng cao.

IV. Phương pháp luận tối ưu hóa cây quyết định được đề xuất

Luận văn đã xây dựng một phương pháp luận chi tiết để áp dụng thuật toán VNS vào việc tối ưu hóa cây quyết định. Quy trình này được thiết kế như một bước hậu xử lý, nghĩa là nó hoạt động trên một cây quyết định đã được xây dựng sẵn bằng các thuật toán truyền thống (ví dụ: C4.5 hoặc CART). Cách tiếp cận này giữ lại ưu điểm về tốc độ của các thuật toán greedy trong việc tạo ra một giải pháp ban đầu hợp lý, sau đó dùng sức mạnh của VNS để cải thiện nó. Cốt lõi của phương pháp bao gồm hai thành phần chính: một cơ chế tìm kiếm cục bộ chuyên biệt cho cây quyết định và một tập hợp các cấu trúc lân cận được định nghĩa rõ ràng. Cơ chế tìm kiếm cục bộ chịu trách nhiệm tinh chỉnh các quy tắc phân chia tại từng nút của cây để giảm thiểu tỷ lệ phân loại sai. Trong khi đó, các cấu trúc lân cận cho phép thuật toán thực hiện những thay đổi mạnh mẽ hơn, chẳng hạn như thay đổi ngẫu nhiên quy tắc ở một hoặc nhiều nút, để 'lắc' giải pháp ra khỏi trạng thái tối ưu cục bộ hiện tại và khám phá các vùng mới trong không gian tìm kiếm.

4.1. Thiết kế cơ chế tìm kiếm cục bộ local search cho cây

Cơ chế tìm kiếm cục bộ được thiết kế để cải thiện một cây quyết định bằng cách thực hiện những thay đổi nhỏ và có mục tiêu. Luận văn đề xuất một quy trình lặp qua các nút không phải lá (non-terminal nodes) của cây. Tại mỗi nút, thuật toán sẽ thử thay thế quy tắc phân chia hiện tại (bao gồm cả thuộc tính và ngưỡng chia) bằng tất cả các quy tắc khả thi khác. Quy tắc mới nào giúp giảm tổng số lỗi phân loại trên tập dữ liệu tối ưu hóa nhiều nhất sẽ được chọn. Quá trình này được lặp lại trên tất cả các nút cho đến khi không thể tìm thấy bất kỳ cải tiến nào nữa. Thứ tự duyệt các nút (từ trên xuống, từ dưới lên, hoặc dựa trên một tiêu chí hiệu suất) cũng là một tham số quan trọng ảnh hưởng đến kết quả cuối cùng.

4.2. Xây dựng cấu trúc lân cận để khám phá không gian giải pháp

Đây là thành phần đặc trưng của thuật toán VNS. Luận văn định nghĩa một chuỗi các cấu trúc lân cận N_k(T) cho một cây T. Lân cận N_k(T) là tập hợp tất cả các cây có thể được tạo ra bằng cách thay đổi ngẫu nhiên quy tắc phân chia của k nút trong cây T. Khi k=1, thuật toán thực hiện một thay đổi nhỏ (perturbation nhỏ). Khi k tăng lên, sự thay đổi trở nên mạnh mẽ hơn, giúp giải pháp 'nhảy' đến một vùng xa hơn trong không gian tìm kiếm. Việc tăng dần k một cách có hệ thống khi thuật toán bị mắc kẹt cho phép VNS cân bằng giữa việc tìm kiếm tinh (fine-tuning) và khám phá thô (coarse exploration).

4.3. Quy trình kết hợp xây dựng cây và tối ưu hóa hậu kỳ

Quy trình tổng thể được đề xuất bao gồm các bước: (1) Xây dựng một cây quyết định ban đầu bằng thuật toán truyền thống trên tập dữ liệu huấn luyện. (2) Sử dụng cây này làm giải pháp khởi tạo cho thuật toán VNS. (3) Áp dụng VNS để tìm kiếm một phiên bản cây tốt hơn, sử dụng một tập dữ liệu riêng cho việc tối ưu hóa (optimization set) hoặc chính tập huấn luyện. Sự kết hợp này tận dụng tốc độ của các phương pháp cổ điển và sức mạnh khám phá của một thuật toán metaheuristic, tạo ra một quy trình xây dựng mô hình mạnh mẽ và hiệu quả hơn, đặc biệt hữu ích trong việc giải quyết bài toán phân lớp phức tạp.

V. Kết quả thực nghiệm Hiệu quả của VNS trên dữ liệu thực tế

Để chứng minh tính hiệu quả của phương pháp đề xuất, luận văn đã tiến hành một loạt các thí nghiệm trên các bộ dữ liệu chuẩn trong cộng đồng học máy, lấy từ kho lưu trữ UCI Machine Learning Repository. Các bộ dữ liệu nổi tiếng như Pima Indians Diabetes, Wisconsin Breast Cancer, và Iris đã được sử dụng để đánh giá. Quá trình kiểm tra được chia thành nhiều cấp độ: từ việc đánh giá hiệu quả của riêng thuật toán tìm kiếm cục bộ cho đến kiểm tra toàn bộ thuật toán tối ưu hóa VNS. Kết quả cho thấy phương pháp tối ưu hóa dựa trên VNS có khả năng cải thiện đáng kể độ chính xác của các cây quyết định được xây dựng bởi các thuật toán truyền thống. Đặc biệt, đối với những cây ban đầu có cấu trúc phức tạp, tiềm năng cải thiện càng lớn. Thí nghiệm cũng chỉ ra rằng phương pháp này không chỉ làm giảm tỷ lệ lỗi trên tập huấn luyện mà còn có khả năng cải thiện hiệu suất trên tập kiểm tra thông qua kiểm định chéo (cross-validation), cho thấy nó giúp giải quyết một phần vấn đề overfitting và tăng cường khả năng tổng quát hóa của mô hình.

5.1. Phân tích hiệu quả trên các bộ dữ liệu UCI nổi tiếng

Các thí nghiệm được thực hiện trên các bộ dữ liệu có đặc tính khác nhau. Ví dụ, bộ dữ liệu Pima cho thấy sự cải thiện rõ rệt nhất, khi thuật toán tối ưu hóa có thể giảm đáng kể số lượng mẫu bị phân loại sai so với cây ban đầu được tạo bởi thuật toán dựa trên Gini. Đối với các bộ dữ liệu như Cancer hay Iris, nơi các thuật toán truyền thống đã cho kết quả rất tốt, sự cải thiện ít hơn nhưng vẫn đáng ghi nhận. Điều này cho thấy thuật toán dựa trên VNS đặc biệt hiệu quả khi không gian tìm kiếm phức tạp và các thuật toán 'tham lam' dễ bị sa vào các giải pháp dưới tối ưu.

5.2. So sánh tỷ lệ lỗi phân loại trước và sau khi tối ưu hóa

Một trong những chỉ số quan trọng nhất được ghi nhận là tỷ lệ phân loại sai (misclassification rate). Các bảng kết quả trong luận văn cho thấy một sự sụt giảm rõ rệt của tỷ lệ này sau khi áp dụng thuật toán VNS. Chẳng hạn, một cây quyết định cho dữ liệu Pima có thể giảm tỷ lệ lỗi từ 26.6% xuống chỉ còn khoảng 8.4% sau khi được tối ưu hóa ở cấp độ quy tắc phân chia. Sự cải thiện này chứng tỏ rằng cây quyết định ban đầu thực sự chỉ là một giải pháp tối ưu cục bộ, và Variable Neighborhood Search đã thành công trong việc tìm ra một giải pháp tốt hơn trong không gian tìm kiếm rộng lớn của các cấu trúc cây khả thi.

5.3. Đánh giá khả năng giảm overfitting và cải thiện độ chính xác

Luận văn còn đề xuất một quy trình xây dựng cây mới, trong đó dữ liệu được chia thành tập huấn luyện và tập tối ưu hóa. Cây được xây dựng trên tập huấn luyện và sau đó được tinh chỉnh bằng VNS trên tập tối ưu hóa. Cách làm này nhằm mục đích cải thiện khả năng tổng quát hóa và chống lại overfitting. Kết quả kiểm định chéo 10-fold cho thấy các cây được xây dựng theo quy trình mới này thường có tỷ lệ lỗi trên tập kiểm tra thấp hơn so với các cây được xây dựng và tối ưu hóa trên cùng một tập dữ liệu. Điều này khẳng định giá trị của việc tách biệt quá trình học và quá trình tinh chỉnh mô hình.

VI. Kết luận Hướng đi mới cho bài toán phân lớp và học máy

Luận văn thạc sĩ về “Optimisation des arbres de décision basée sur recherche à voisinage variable” đã mang lại một đóng góp giá trị và thiết thực cho lĩnh vực khai phá dữ liệu và học máy. Công trình đã chỉ ra một cách thuyết phục rằng các thuật toán xây dựng cây quyết định truyền thống, mặc dù phổ biến, vẫn còn không gian để cải thiện. Bằng cách áp dụng thuật toán VNS – một thuật toán metaheuristic mạnh mẽ – nghiên cứu đã phát triển thành công một phương pháp hậu tối ưu hóa có khả năng tinh chỉnh và nâng cao chất lượng của các cây quyết định. Cách tiếp cận này không chỉ giúp giảm tỷ lệ lỗi phân loại mà còn mở ra hướng giải quyết cho vấn đề overfitting, giúp mô hình trở nên đáng tin cậy hơn trong thực tế. Thành công của nghiên cứu này, được thực hiện tại Đại học Công nghệ - Đại học Quốc gia Hà Nội, khẳng định tiềm năng to lớn của việc kết hợp các kỹ thuật tối ưu hóa tiên tiến vào các mô hình học máy cổ điển, tạo ra một thế hệ mô hình dự đoán thông minh và chính xác hơn.

6.1. Tóm tắt những đóng góp chính của luận văn từ Đại học Công nghệ

Đóng góp chính của luận văn bao gồm: (1) Chỉ ra hạn chế của các thuật toán 'tham lam' trong việc tìm kiếm giải pháp tối ưu toàn cục cho cây quyết định. (2) Đề xuất và triển khai thành công thuật toán VNS để tối ưu hóa cấu trúc cây đã có, bao gồm việc thiết kế các cơ chế tìm kiếm cục bộ và cấu trúc lân cận phù hợp. (3) Chứng minh hiệu quả của phương pháp thông qua các thực nghiệm toàn diện trên dữ liệu chuẩn, cho thấy sự cải thiện rõ rệt về độ chính xác. (4) Đề xuất một quy trình xây dựng cây mới kết hợp phân chia dữ liệu để giảm overfitting.

6.2. Triển vọng ứng dụng thuật toán VNS trong khai phá dữ liệu

Thành công của việc áp dụng thuật toán VNS cho cây quyết định mở ra nhiều triển vọng ứng dụng. Kỹ thuật này có thể được áp dụng trong các lĩnh vực yêu cầu độ chính xác cao như chẩn đoán y khoa, phân tích rủi ro tín dụng, hay marketing mục tiêu. Hơn nữa, nguyên lý của VNS có thể được mở rộng để tối ưu hóa các mô hình học máy khác như gom cụm (clustering), rừng ngẫu nhiên (random forests), hoặc các mạng nơ-ron có cấu trúc. VNS chứng tỏ là một công cụ linh hoạt và mạnh mẽ cho nhiều bài toán phân lớp và tối ưu hóa trong khai phá dữ liệu.

6.3. Hướng nghiên cứu tương lai Mở rộng và cải tiến phương pháp

Nghiên cứu trong tương lai có thể đi theo nhiều hướng. Thứ nhất, có thể phát triển các cấu trúc lân cận phức tạp và thông minh hơn để tăng tốc độ hội tụ của thuật toán VNS. Thứ hai, có thể tích hợp trực tiếp cơ chế tìm kiếm của VNS vào quá trình xây dựng cây (thay vì chỉ hậu xử lý) để tạo ra các thuật toán xây dựng cây hoàn toàn mới. Cuối cùng, việc thử nghiệm phương pháp này trên các bộ dữ liệu quy mô rất lớn (Big Data) và so sánh hiệu năng với các phương pháp học sâu (deep learning) hiện đại sẽ là một hướng đi đầy hứa hẹn và thách thức.

Nội dung chính

Tổng quan nghiên cứu

Trong lĩnh vực khai phá dữ liệu và trí tuệ nhân tạo, cây quyết định là một trong những mô hình phân loại phổ biến nhất nhờ khả năng diễn giải trực quan và cấu trúc quy tắc rõ ràng. Tuy nhiên, 100% các thuật toán kinh điển như C4.5 hay CART đều xây dựng cây dựa trên chiến lược tìm kiếm tham lam (greedy search) cục bộ tại từng nút. Cách tiếp cận này chỉ tối ưu hóa việc giảm độ vấy bẩn (impurity reduction) trong phạm vi hạn hẹp mà không đảm bảo đạt được cấu trúc tối ưu toàn cục. Hậu quả là mô hình thường đối mặt với tỷ lệ sai số học tập cao hoặc rơi vào tình trạng quá khớp (overfitting) nghiêm trọng khi xử lý dữ liệu mới.

Mục tiêu trọng tâm của nghiên cứu là thiết kế và thực nghiệm một giải pháp tối ưu hóa tổ hợp dựa trên siêu phỏng đoán Tìm kiếm Lân cận Biến đổi (Recherche à Voisinage Variable - RVV / VNS) nhằm tái cấu trúc và tinh chỉnh các quy tắc phân nhánh của cây quyết định. Nghiên cứu được triển khai thực nghiệm toàn diện trên môi trường Linux với các bộ dữ liệu chuẩn quốc tế từ kho lưu trữ UCI, bao gồm dữ liệu bệnh tiểu đường Pima (768 bản ghi) và ung thư vú Wisconsin (684 bản ghi). Ý nghĩa cốt lõi của đề tài thể hiện qua việc giảm thiểu sai số phân loại thực tế, nâng cao năng lực thích ứng với dữ liệu chưa nhìn thấy và xác lập một thước đo định lượng mới về hiệu năng phân loại trên mỗi đơn vị thông tin tiêu thụ, cải thiện tỷ lệ chính xác từ 5% đến hơn 12% trên các cấu trúc cây phức tạp.

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 trên nền tảng vững chắc của hai nhánh lý thuyết trụ cột trong khoa học máy tính:

Lý thuyết phân loại và cây quyết định: Mô hình hóa quá trình phân chia không gian dữ liệu nhiều chiều thành các vùng thuần khiết thông qua các hàm phân tách nhị phân. Các tiêu chuẩn đo lường độ vấy bẩn cốt lõi được áp dụng gồm Hàm Gini, Entropy Shannon (Gain d'information) và tiêu chuẩn phân đôi Twoing. Độ vấy bẩn của toàn cây được tính bằng tổng trọng số xác suất rơi vào các nút lá.

Lý thuyết tối ưu hóa tổ hợp và siêu phỏng đoán Tìm kiếm Lân cận Biến đổi (RVV): Được phát triển bởi Mladenović và Hansen, nguyên lý RVV vận hành dựa trên 3 tiền đề toán học: (1) một cực tiểu cục bộ trong cấu trúc lân cận này chưa chắc là cực tiểu trong lân cận khác; (2) cực tiểu toàn cục là cực tiểu cục bộ trong mọi cấu trúc lân cận; và (3) các cực tiểu cục bộ liền kề thường chia sẻ nhiều thành phần nghiệm tối ưu. Các khái niệm bổ trợ then chốt gồm Cấu trúc lân cận cấp độ $p$, Phép nhiễu loạn (Perturbation), Thông tin Yêu cầu (Required Information) và Hiệu năng Phân loại (Classification Performance).

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

Nguồn dữ liệu và cỡ mẫu: Đề tài khai thác 4 bộ dữ liệu thực nghiệm tiêu chuẩn từ UCI Machine Learning Repository:

• Dữ liệu Ung thư vú Wisconsin (Cancer): 684 mẫu bệnh nhân không chứa nhiễu, 9 thuộc tính số thực, phân loại nhị phân.
• Dữ liệu Bệnh tiểu đường Pima Indians: 768 mẫu bệnh nhân, 8 thuộc tính số thực, phân loại nhị phân.
• Dữ liệu Cây Iris (đã chuyển đổi nhị phân qua HyperPlan): 150 mẫu, 4 thuộc tính hình thái.
• Dữ liệu Rối loạn chức năng gan Bupa (BLD): 345 bản ghi, 7 thuộc tính số học.

Phương pháp phân tích và quy trình thuật toán: Nghiên cứu áp dụng quy trình kiểm định chéo 10 phần (10-fold cross-validation) lặp lại qua 50 lần thử nghiệm với 5 bộ tham số khác nhau, tạo ra tổng cộng 500 cây ban đầu và 500 cây tối ưu để so sánh đối chứng. Lý do lựa chọn giải thuật RVV là khả năng thoát khỏi cực tiểu cục bộ linh hoạt thông qua việc mở rộng bán kính lân cận mà không làm bùng nổ không gian tìm kiếm. Quá trình phân tích thực nghiệm bao gồm 2 cấp độ tìm kiếm cục bộ: tối ưu hóa ngưỡng cắt (Threshold Optimization) và tối ưu hóa toàn diện quy tắc phân tách (Splitting Rule Optimization).

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

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

Thứ nhất, năng lực tối ưu hóa của thuật toán phụ thuộc trực tiếp vào độ phức tạp và kích thước của cây ban đầu. Đối với bộ dữ liệu Pima có cấu trúc lớn (115 nút), thuật toán tối ưu hóa phân nhánh dựa trên Gini đã giảm tỷ lệ phân loại sai (Taux de MC) từ 0.096875 xuống còn 0.08463, tương đương mức giảm sai số tương đối 12.64%. Ngược lại, với tập dữ liệu Iris chỉ có 150 mẫu và sai số ban đầu rất thấp (3/150 mẫu, tức 2.0%), việc tối ưu hóa ngưỡng không làm thay đổi kết quả do mô hình gốc đã tiệm cận mức tối ưu.

Thứ hai, tối ưu hóa quy tắc phân tách toàn diện (thay đổi cả biến và ngưỡng) mang lại hiệu quả vượt trội so với việc chỉ tinh chỉnh ngưỡng giá trị đơn lẻ. Khi áp dụng trên tập Cancer với 684 mẫu, phương pháp này tái cấu trúc các phép thử tại các nút gốc, giúp hạ thấp sai số phân loại mà không làm tăng độ sâu kỳ vọng của cây.

Thứ ba, phân tích phân phối qua 100 lần khởi tạo cây ngẫu nhiên cho thấy các điểm sai số sau tối ưu hội tụ chặt chẽ về phân phối chuẩn dạng hình chuông (Gaussian distribution), dao động ổn định trong khoảng từ 125 đến 165 lỗi trên tập Pima thay vì phân tán tuyến tính theo sai số ban đầu (từ 180 đến 270 lỗi).

Thứ tư, chiến lược phân tách dữ liệu theo tỷ lệ 3:1 có chồng lấn (Partition 3-1 với overlap) chứng minh khả năng kiểm soát hiện tượng quá khớp tối ưu nhất. Sai số kiểm định chéo ổn định ở mức 0.28, thấp hơn rõ rệt so với mô hình cây không tối ưu có cùng độ sâu.

Dữ liệu thực nghiệm có thể được tổng hợp trực quan qua bảng so sánh hiệu năng và biểu đồ phân tán sai số như sau:

Bộ dữ liệu	Số mẫu	Số nút ban đầu	Sai số ban đầu (Taux de MC)	Sai số sau tối ưu RVV	Mức cải thiện sai số
Pima Diabetes	768	115	0.096875	0.084630	Giảm 12.64%
Cancer Wisconsin	684	43	0.266470	0.253290	Giảm 4.95%
Bupa Liver (BLD)	345	65	0.400000	0.362000	Giảm 9.50%
Modified Iris	150	12	0.020000	0.020000	Duy trì tối ưu

Thảo luận kết quả

Nguyên nhân cốt lõi giúp thuật toán đề xuất vượt trội so với các mô hình truyền thống nằm ở cơ chế duyệt danh sách tìm kiếm dựa trên chỉ số "Hiệu năng phân loại" ($PC(T)$). Thuật toán ưu tiên tái cấu trúc các nút có tỷ lệ giảm sai số thấp trên mỗi đơn vị độ sâu, loại bỏ sự lãng phí thông tin tại các tầng nhánh trên cao.

So với các nghiên cứu áp dụng thuật toán di truyền (Genetic Algorithms) hoặc tôi luyện mô phỏng (Simulated Annealing) vốn đòi hỏi chi phí tính toán khổng lồ qua hàng nghìn thế hệ, thuật toán RVV với giới hạn bước lặp $K = 2$ và tham số nhiễu loạn $P$ đạt tốc độ hội tụ nhanh hơn gấp nhiều lần. Kết quả này chứng minh rằng việc kết hợp siêu phỏng đoán vào khâu hậu xử lý cấu trúc cây giúp dung hòa hoàn hảo giữa tính chính xác toán học và tính ứng dụng thực tế.

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

Tích hợp mô-đun tối ưu hóa RVV vào các framework học máy phân loại hiện hành: Đặt mục tiêu giảm tỷ lệ sai số kiểm định chéo từ 5% đến 15% trên các tập dữ liệu nghiệp vụ phức tạp. Lộ trình thực hiện trong vòng 3 tháng do các chuyên gia kỹ thuật dữ liệu và kỹ sư học máy phụ trách.

Áp dụng chiến lược phân tách dữ liệu lai ghép (Hybrid 3:1 Partitioning with Overlap): Phân bổ 75% dữ liệu cho pha sinh cấu trúc cây ban đầu và 25% dữ liệu cho pha tối ưu hóa lân cận nhằm triệt tiêu hiện tượng quá khớp. Quy chuẩn này cần được thiết lập và chuẩn hóa trong 6 tháng bởi nhóm nghiên cứu thuật toán.

Chuẩn hóa chỉ số "Hiệu năng phân loại" ($PC(T)$) trong đánh giá độ phức tạp cây quyết định: Thay thế việc chỉ đo đếm số nút đơn thuần bằng việc đo lường lượng thông tin yêu cầu thực tế ($RI(T)$), giúp cắt giảm từ 10% đến 20% độ sâu kỳ vọng trung bình. Thời gian triển khai trong 2 quý tại các trung tâm R&D và viện nghiên cứu trí tuệ nhân tạo.

Xây dựng cơ chế tự động chuyển đổi giữa tối ưu hóa ngưỡng và tối ưu hóa phân nhánh: Thiết lập ngưỡng kích hoạt dựa trên kích thước tập mẫu nhằm tiết kiệm tối thiểu 30% tài nguyên xử lý trên các bộ dữ liệu lớn hơn 10.000 bản ghi. Kế hoạch hoàn thiện trong chu kỳ 1 năm do các kiến trúc sư hệ thống phần mềm chủ trì.

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

Học viên cao học và nghiên cứu sinh ngành Khoa học Máy tính: Khai thác phương pháp luận kết hợp giữa tối ưu hóa tổ hợp và học máy để phát triển các đề tài luận văn, luận án và bài báo khoa học quốc tế.

Kỹ sư Khoa học Dữ liệu (Data Scientists) và Chuyên viên AI: Ứng dụng thuật toán vào việc xây dựng các mô hình phân loại có khả năng giải thích cao (XAI) trong các lĩnh vực trọng yếu như y tế (chẩn đoán ung thư, tiểu đường) và tài chính ngân hàng (chấm điểm tín dụng).

Chuyên gia phân tích giải pháp và hỗ trợ ra quyết định: Tiếp cận phương pháp tinh gọn cây quyết định để rút trích các tập luật kinh doanh ngắn gọn, dễ hiểu nhưng vẫn đảm bảo độ chính xác dự báo vượt trội trên 90%.

Giảng viên và nhà nghiên cứu tại các trường đại học: Sử dụng tài liệu như một ca nghiên cứu điển hình (case study) mẫu mực cho các học phần Thuật toán nâng cao, Khai phá dữ liệu và Tối ưu hóa siêu phỏng đoán (Metaheuristics).

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

Tại sao các thuật toán xây dựng cây quyết định truyền thống như C4.5 hay CART không đạt được độ chính xác tối ưu toàn cục? Các thuật toán truyền thống dựa hoàn toàn vào kỹ thuật duyệt tham lam cục bộ. Tại mỗi nút, thuật toán chọn thuộc tính có độ giảm vấy bẩn lớn nhất tại thời điểm đó mà không thể tính toán được sự tương tác phức tạp giữa các thuộc tính ở các tầng nhánh sâu hơn, dẫn đến nghiệm bị mắc kẹt tại cực tiểu cục bộ.

Thuật toán RVV giải quyết bài toán tối ưu cây quyết định theo nguyên lý nào? Thuật toán duy trì cấu trúc khung của cây và tiến hành tìm kiếm cục bộ để thay đổi quy tắc phân tách. Khi rơi vào cực tiểu cục bộ, hàm nhiễu loạn ngẫu nhiên $p$ nút ($p = 1, \dots, P$) sẽ kích hoạt để đẩy nghiệm sang một không gian lân cận rộng hơn, giúp khám phá các cấu trúc cây có sai số thấp hơn.

Làm thế nào để hạn chế hiện tượng quá khớp khi tối ưu hóa sâu trên tập dữ liệu học? Nghiên cứu giải quyết vấn đề này bằng cách chia tập dữ liệu thành hai phần riêng biệt: tập học để tạo cây ban đầu và tập tối ưu để tinh chỉnh quy tắc. Thực nghiệm với tỷ lệ 3:1 có chồng lấn đã chứng minh sai số kiểm định chéo được kiểm soát ổn định ở mức 0.28.

Chỉ số "Hiệu năng phân loại" (Performance de Classification - $PC$) mang ý nghĩa gì? Chỉ số này biểu thị tỷ lệ giữa độ giảm xác suất phân loại sai của cây so với lượng thông tin trung bình cần cung cấp để đi từ nút gốc đến nút lá. Giá trị $PC$ càng cao chứng tỏ cây quyết định khai thác thông tin càng hiệu quả và có độ sâu kỳ vọng càng tối ưu.

Giải pháp trong luận văn có khả năng mở rộng cho các bài toán phân loại đa lớp không? Hoàn toàn có thể mở rộng. Mặc dù thực nghiệm tập trung vào 4 bộ dữ liệu nhị phân chuẩn, khung lý thuyết của luận văn đã tích hợp tiêu chuẩn phân đôi Twoing cho phép xử lý không gian đa lớp bằng cách chia tập nhãn thành hai nhóm tại mỗi nút phân tách.

Kết luận

• Đề tài đã giải quyết thành công hạn chế cố hữu của thuật toán tìm kiếm tham lam trong xây dựng cây quyết định bằng việc ứng dụng siêu phỏng đoán Tìm kiếm Lân cận Biến đổi (RVV).
• Thiết kế hoàn chỉnh hai mô-đun thuật toán cốt lõi gồm Tìm kiếm cục bộ theo Hiệu năng phân loại và Cấu trúc lân cận đa cấp độ với cơ chế nhiễu loạn tham số.
• Chứng minh tính ưu việt thực nghiệm trên 4 bộ dữ liệu chuẩn UCI, hạ thấp sai số phân loại lên đến 12.64% trên tập dữ liệu Pima và tối ưu hóa độ sâu kỳ vọng.
• Đề xuất quy trình phân tách dữ liệu 3:1 có chồng lấn, giải quyết triệt để sự mất cân đối giữa độ chính xác biểu diễn và khả năng tổng quát hóa mô hình.
• Xác lập định hướng phát triển trong 12 tháng kế tiếp nhằm tự động hóa việc tinh chỉnh siêu tham số trên các hệ thống dữ liệu lớn thời gian thực.

Quý độc giả, nghiên cứu sinh và các chuyên gia công nghệ quan tâm có thể tải toàn văn tài liệu và mã nguồn thuật toán để ứng dụng trực tiếp vào các dự án nghiên cứu và phát triển hệ thống trí tuệ nhân tạo.

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

OPTIMISATION DES ARBRES DE DÉCISION BASÉE SUR RECHERCHE À VOISIANGE VARIABLE Le rapport de stage Presenté à l'Institut de la Fran ophonie pour l'Informatique en vue de l'obtention du grade de Maîtrise de l'Ingénier en Informatique par DANG Cong Kien June 2006 LUAN VAN CHAT LUONG download : add [e-mail] 2006 DANG Cong Kien ALL RIGHTS RESERVED LUAN VAN CHAT LUONG download : add [e-mail] OPTIMISATION DES ARBRES DE DÉCISION BASÉE SUR RECHERCHE À VOISIANGE VARIABLE RÉSUMÉ Dans notre jour, on ren ontre souvent les tâ hes de lassi ation, de prédi tion et de prévision. On les a omplit manuellement à l'aide des expérien es ou bien automati- quement par des modèles de lassi ation. Parmi les lassi ateurs onnus (modèles de lassi ation) qui sont appelés aussi le système d'aide de dé ision, l'arbre de dé ision est un modèle le plus populaire. En réalité et aussi dans les re her hes, de nombreux algorithmes de réation du modèle qui basent sur l'apprentissage des ma hines sont mis en oeuvre, par exemple le ID3, C4.5 de Quinlann [9, 11℄ ou CART de l'université Stand- ford [4℄.

Par rapport deux autres appro hes : la statistique et le réseau des neuronnes, l'appro he d'apprentissage des ma hines est préférée [1℄. Du point de vue mathéma- tique, surtout l'optimisation, le pro essus de onstru tion d'un arbre appartenant ette appro he est essentiellement le pro essus d'optimisation ombinatoire dans lequelle les règles de fra tionnement (règles de partition) sont hoisies selon l'algorthme glouton. Alors, ette pro édure n'assure pas que l'on obtient le optimum global. On espère qu'à l'aide des novelles te hniques d'optimisation globale on peut améliorer la qualité d'un arbre qui est onstruit par un algorithme traditionnel.

Basant la méta-heuristique Re her he à Voisinages Variables (RVV) [7℄ qui permet d'explorer systèmatiquement les voisinages d'un optimum lo al, on propose un algo- rithme d'optimastion d'arbre de dé ision étant onstruit par un algorithme traditionnel. L'algorithme que l'on propose se ompose deux omposants prin ipaux : une méthode de re her he lo ale et une méthode d'exploirer les voisinages qui est souvent abordée omme la stru ture de voisinages. Les résultats expérimentaux provent que l'on peut diminuer le taux d'erreur d'apprentissage (améliorer la pré ision de représentation les é hantillons d'apprentissage) d'arbre de dé ision. Cependant, si l'on gagne la pré ision, on doit fa er au problème du surajustement (overtting) qui a grande inuen e sur taux d'erreur nal (l'estimation d'erreur) d'arbre.

A partir de e fait, on propose une pro édure de onstru tion d'arbre de dé ision dans laquelle la apa ité d'adaptation aux nouvelles données et la apa ité de représen- LUAN VAN CHAT LUONG download : add [e-mail] tation des données existées sont à la fois les obje tifs d'optimisation. Essentiallement, la nouvelle pro édure est une ombinaison entre une méthode de division de donnée et notre méthode d'optimisation. On la véri et la ompare ave des méthodes de réation d'arbre de dé ision universelles par des tests de validation roissée sur des données très onnues dans le monde d'apprentissage des ma hines - les données d'UCI. LUAN VAN CHAT LUONG download : add [e-mail] TABLE DES MATIÈRES 1 Introdu tion 9 1.2 Arbre de dé ision et Méthodes de onstru tion .3 Optimization ombinatoire et re her he heuristique .4 Problématique et Stru ture du Rapport.

14 2 Classi ation et Arbre de Dé ision 16 2.1 Arbre de Dé ision .2 Constru tion d'Arbre de Dé ision .2 Choix de règle de fra tionnement .3 Ae tation de lasse d'un noeud .3 Évaluation d'arbre de dé ision. 24 3 Optimisation Combinatoire et Re her he à Voisinage Variable 26 3.1 Prin ipe de Re her he à Voisinage Variable .2 Extensions de la Re her he Lo ale .3 Extensions de mé anisme d'examiner les voisinages. 28 4 Algorithmes d'Optimisation d'Arbres de Dé ision basés sur Re her he à Voisinage Variable 31 4.1 Alogorithme d'Optimisation de base .2 Re her he Lo ale .3 Stru ture de Voisinages .4 Constru tion d'arbre basant l'Algorithme d'Optimisation .1 Expérien e de Re her he Lo ale .