Luận văn thạc sĩ optimisation des arbres de decision basee sur recherche a voisinage variable

Luận văn thạc sĩ: 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. Nghiên cứu phương pháp mới, nâng cao hiệu quả và độ chính xác của cây quyết định.

• Tác giả: Dang, Cong, Kien
• Trường học: Institut de la Francophonie 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: Thèse
• Năm xuất bản: 2006

Tóm tắt

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

Luận văn thạc sĩ khoa học máy tính với chủ đề "Optimisation des arbres de décision basée sur recherche à voisinage variable" trình bày một cách tiếp cận đột phá trong lĩnh vực học máy. Trọng tâm của nghiên cứu là áp dụng một metaheuristic tiên tiến, cụ thể là thuật toán VNS (Variable Neighborhood Search), để cải thiện chất lượng của các mô hình cây quyết định. Các thuật toán xây dựng cây quyết định truyền thống như ID3, C4.5, và CART thường dựa trên phương pháp tham lam (greedy). Cách tiếp cận này chọn lựa quy tắc phân nhánh tốt nhất tại mỗi nút một cách cục bộ, điều này không đảm bảo cây cuối cùng đạt được cấu trúc tối ưu toàn cục. Do đó, một cây quyết định được xây dựng theo cách này có thể bị kẹt ở một điểm tối ưu cục bộ, làm giảm độ chính xác và khả năng tổng quát hóa. Luận văn này xem xét quá trình xây dựng cây như một bài toán tối ưu hóa tổ hợp (combinatorial optimization). Từ đó, tác giả đề xuất sử dụng kỹ thuật tìm kiếm theo vùng lân cận thay đổi để khám phá không gian lời giải một cách hệ thống và thoát khỏi các điểm tối ưu cục bộ. Mục tiêu chính là giảm thiểu tỷ lệ lỗi phân loại trên tập dữ liệu học, qua đó nâng cao độ chính xác của mô hình. Nghiên cứu không chỉ dừng lại ở việc đề xuất thuật toán mà còn thực hiện các thử nghiệm chi tiết trên các bộ dữ liệu chuẩn của UCI để chứng minh tính hiệu quả. Đây là một đóng góp quan trọng, mở ra hướng đi mới cho việc cải tiến thuật toán cây quyết định trong bối cảnh khai phá dữ liệu hiện đại.

1.1. Giới thiệu cây quyết định trong học máy và vai trò

Cây quyết định là một trong những mô hình phân lớp phổ biến nhất trong học máy (machine learning) và khai phá dữ liệu (data mining). Ưu điểm chính của nó là tính dễ diễn giải; các quy tắc được biểu diễn dưới dạng cây đồ thị, giúp con người dễ dàng hiểu được logic đằng sau mỗi quyết định. Mỗi nút trong của cây đại diện cho một bài kiểm tra trên một thuộc tính, mỗi nhánh là kết quả của bài kiểm tra đó, và mỗi nút lá đại diện cho một nhãn lớp. Cây quyết định trong học máy được ứng dụng rộng rãi trong nhiều lĩnh vực như chẩn đoán y khoa, thẩm định tín dụng, và marketing. Tuy nhiên, hiệu suất của một cây quyết định phụ thuộc rất lớn vào cấu trúc của nó, bao gồm việc lựa chọn thuộc tính tại mỗi nút và cách xác định các quy tắc phân nhánh. Việc xây dựng một cây tối ưu là một bài toán thuộc lớp NP-khó, do đó các heuristic optimization được sử dụng để tìm kiếm các giải pháp gần tối ưu.

1.2. Metaheuristic và tiềm năng trong tối ưu hóa tổ hợp

Metaheuristic là một tập hợp các chiến lược và kỹ thuật cấp cao được thiết kế để tìm kiếm, tạo ra hoặc lựa chọn một giải thuật heuristic có khả năng tìm ra lời giải tốt cho các bài toán tối ưu hóa phức tạp. Không giống như các heuristic cụ thể cho từng bài toán, metaheuristic cung cấp một khung làm việc chung có thể áp dụng cho nhiều vấn đề khác nhau. Các kỹ thuật nổi bật bao gồm Simulated Annealing, Tabu Search, Genetic Algorithms và Variable Neighborhood Search (VNS). Trong bối cảnh tối ưu hóa tổ hợp, nơi không gian lời giải thường rất lớn và rời rạc, metaheuristic đóng vai trò quan trọng trong việc tránh bị mắc kẹt tại các điểm tối ưu cục bộ. Luận văn này khai thác sức mạnh của thuật toán VNS để cải thiện các giải pháp cây quyết định ban đầu, vốn được tạo ra bởi các thuật toán tham lam.

II. Hạn chế của thuật toán ID3 C4

Các thuật toán xây dựng cây quyết định kinh điển như thuật toán ID3, C4.5, CART đều tuân theo một nguyên tắc chung: chiến lược chia để trị (divide and conquer) kết hợp với thuật toán tham lam (greedy). Tại mỗi bước, thuật toán sẽ chọn một thuộc tính và một ngưỡng phân chia sao cho độ lợi thông tin (information gain) hoặc chỉ số Gini được tối đa hóa. Quyết định này chỉ tối ưu cho bước hiện tại mà không xem xét đến ảnh hưởng của nó lên các bước phân chia sau này. Hệ quả là, quy trình này không đảm bảo tạo ra cây quyết định có hiệu suất tốt nhất trên toàn cục. Đây chính là vấn đề tối ưu cục bộ. Một cây quyết định bị sa vào điểm tối ưu cục bộ có thể có cấu trúc phức tạp hơn cần thiết hoặc tỷ lệ lỗi cao hơn so với một cây được tối ưu hóa toàn cục. Một thách thức khác liên quan trực tiếp là hiện tượng quá khớp (overfitting). Cây quyết định được xây dựng để phù hợp một cách hoàn hảo với dữ liệu huấn luyện có thể sẽ hoạt động kém trên dữ liệu mới. Mặc dù các kỹ thuật cắt tỉa cây quyết định (pruning) được phát triển để giải quyết vấn đề này, bản chất tham lam của quá trình xây dựng cây vẫn là một hạn chế cố hữu. Luận văn này nhận diện rõ ràng những thách thức này và đề xuất một phương pháp hậu xử lý, sử dụng decision tree optimization dựa trên VNS để tinh chỉnh lại cấu trúc cây đã được xây dựng, nhằm tìm kiếm một giải pháp tốt hơn trong không gian lời giải.

2.1. Phân tích thuật toán tham lam greedy trong xây dựng cây

Thuật toán tham lam là một phương pháp tiếp cận đơn giản nhưng mạnh mẽ, trong đó quyết định tối ưu cục bộ được đưa ra ở mỗi giai đoạn với hy vọng sẽ tìm ra được lời giải tối ưu toàn cục. Trong việc xây dựng cây quyết định, điều này có nghĩa là tại mỗi nút, thuật toán sẽ duyệt qua tất cả các thuộc tính và các điểm chia có thể để tìm ra quy tắc phân nhánh giúp giảm độ bất định (impurity) nhiều nhất. Mặc dù hiệu quả về mặt tính toán, chiến lược này có nhược điểm lớn. Một lựa chọn tốt ở bước hiện tại có thể dẫn đến các cây con có cấu trúc không tối ưu ở các bước sau. Ví dụ, một thuộc tính ít quan trọng hơn có thể được chọn nếu nó mang lại lợi ích tức thời cao hơn, trong khi một thuộc tính khác có thể tạo ra một cấu trúc cây tổng thể cân bằng và chính xác hơn. Bản chất "thiển cận" này là nguyên nhân chính khiến các thuật toán truyền thống không thể đảm bảo tìm ra cây quyết định tối ưu toàn cục.

2.2. Rủi ro quá khớp overfitting và thách thức cắt tỉa cây

Quá khớp (overfitting) là một trong những vấn đề nghiêm trọng nhất trong học máy. Nó xảy ra khi mô hình học thuộc các chi tiết và nhiễu trong dữ liệu huấn luyện đến mức làm ảnh hưởng tiêu cực đến hiệu suất của mô hình trên dữ liệu mới. Đối với cây quyết định, quá khớp thường biểu hiện dưới dạng một cây quá lớn và phức tạp. Để đối phó, các kỹ thuật cắt tỉa cây quyết định (pruning) được áp dụng. Có hai loại cắt tỉa chính: pre-pruning (dừng xây dựng cây sớm) và post-pruning (xây dựng cây đầy đủ rồi cắt bỏ các nhánh không cần thiết). Tuy nhiên, cả hai phương pháp đều có những thách thức riêng. Pre-pruning có thể dừng quá sớm, bỏ lỡ các cấu trúc hữu ích. Post-pruning, mặc dù thường hiệu quả hơn, vẫn phụ thuộc vào chất lượng của cây ban đầu được tạo ra bởi thuật toán tham lam. Do đó, việc cải tiến thuật toán cây quyết định không chỉ dừng lại ở cắt tỉa mà còn cần một phương pháp tối ưu hóa cấu trúc cơ bản.

III. Giải pháp VNS Tìm kiếm theo vùng lân cận thay đổi ưu việt

Tìm kiếm theo vùng lân cận thay đổi (Variable Neighborhood Search - VNS) là một metaheuristic được thiết kế để giải quyết các bài toán tối ưu hóa tổ hợp một cách hiệu quả. Nguyên tắc cốt lõi của VNS dựa trên một ý tưởng đơn giản nhưng mạnh mẽ: 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 có thể không phải là tối ưu cục bộ đối với một cấu trúc lân cận khác. Thuật toán VNS hoạt động bằng cách khám phá một cách có hệ thống các vùng lân cận ngày càng xa so với lời giải hiện tại để thoát khỏi các thung lũng tối ưu cục bộ. Quá trình này bao gồm ba bước chính: (1) Rung (Shaking): Tạo ra một lời giải ngẫu nhiên trong vùng lân cận thứ k của lời giải hiện tại. (2) Tìm kiếm cục bộ (Local Search): Áp dụng một thuật toán tìm kiếm cục bộ để cải thiện lời giải vừa được tạo ra. (3) Di chuyển (Move): Nếu lời giải mới tốt hơn lời giải hiện tại, cập nhật lời giải và quay lại vùng lân cận đầu tiên (k=1); nếu không, chuyển sang vùng lân cận tiếp theo (k=k+1). Phương pháp này cho phép khám phá không gian lời giải một cách đa dạng, kết hợp giữa việc tìm kiếm sâu (intensification) thông qua các local search algorithms và tìm kiếm rộng (diversification) thông qua việc thay đổi cấu trúc lân cận. Trong luận văn, VNS được áp dụng để tối ưu hóa cây quyết định, trong đó mỗi "lời giải" là một cấu trúc cây cụ thể.

3.1. Nguyên tắc cốt lõi của thuật toán VNS Variable Neighborhood Search

Nguyên tắc nền tảng của Variable Neighborhood Search algorithm đến từ ba quan sát thực nghiệm: (1) Một điểm tối ưu cục bộ theo một cấu trúc lân cận chưa chắc đã là tối ưu cục bộ theo cấu trúc lân cận khác. (2) 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ể. (3) Đối với nhiều bài toán, các điểm tối ưu cục bộ thường nằm gần nhau. Dựa trên những quan sát này, VNS không chỉ thực hiện tìm kiếm trong một vùng lân cận cố định mà thay đổi các vùng lân cận một cách linh hoạt. Bằng cách "rung" lời giải hiện tại để tạo ra một điểm khởi đầu mới trong một vùng lân cận xa hơn, thuật toán có khả năng nhảy qua các rào cản ngăn cách các vùng hấp dẫn khác nhau trong không gian tìm kiếm, từ đó tăng cơ hội tìm thấy điểm tối ưu toàn cục.

3.2. So sánh VNS với các thuật toán tìm kiếm cục bộ khác

So với các local search algorithms truyền thống chỉ hoạt động trong một cấu trúc lân cận duy nhất, VNS có ưu thế vượt trội trong việc tránh các điểm tối ưu cục bộ. Các thuật toán như Hill Climbing thường dừng lại ngay khi không tìm thấy lời giải tốt hơn trong vùng lân cận ngay lập tức. Trong khi đó, các metaheuristic khác như Simulated Annealing cho phép chấp nhận các lời giải tệ hơn một cách ngẫu nhiên để thoát khỏi tối ưu cục bộ, nhưng việc lựa chọn tham số (ví dụ: nhiệt độ) có thể phức tạp. Tabu Search sử dụng bộ nhớ (tabu list) để tránh quay lại các lời giải đã xét. VNS nổi bật nhờ sự đơn giản trong ý tưởng và triển khai. Nó không yêu cầu nhiều tham số phức tạp để tinh chỉnh, chủ yếu chỉ cần định nghĩa một tập hợp các cấu trúc lân cận và một thủ tục tìm kiếm cục bộ, làm cho nó trở thành một công cụ mạnh mẽ và linh hoạt cho bài toán decision tree optimization.

IV. Cải tiến thuật toán cây quyết định Quy trình tối ưu hóa

Luận văn này đề xuất một thuật toán cụ thể để tối ưu hóa cây quyết định dựa trên khung làm việc của VNS. Thuật toán này không xây dựng cây từ đầu mà tập trung vào việc cải thiện một cây quyết định đã có sẵn, thường là kết quả từ một thuật toán truyền thống như C4.5. Cấu trúc tổng thể của cây (số lượng nút và cách kết nối) được giữ nguyên, nhưng các quy tắc phân nhánh tại các nút trong được tối ưu hóa. Quy trình này bao gồm hai thành phần chính: một thuật toán tìm kiếm cục bộ mạnh mẽ và một tập hợp các cấu trúc lân cận được định nghĩa rõ ràng. Thuật toán VNS được triển khai sẽ lặp đi lặp lại việc tạo ra một cây mới (hàng xóm) bằng cách thay đổi ngẫu nhiên quy tắc phân nhánh của một hoặc nhiều nút, sau đó áp dụng tìm kiếm cục bộ để tinh chỉnh cây mới này. Nếu cây sau khi tinh chỉnh có tỷ lệ lỗi thấp hơn cây tốt nhất hiện tại, nó sẽ được cập nhật. Quá trình này được lặp lại cho đến khi không tìm thấy sự cải thiện nào sau một số lần thử nhất định. Cách tiếp cận này cho phép khám phá một không gian rộng lớn các cấu trúc cây biến thể, vượt qua những hạn chế của phương pháp tham lam ban đầu và tiến gần hơn đến một giải pháp tối ưu toàn cục.

4.1. Thiết kế thuật toán tìm kiếm cục bộ Local Search hiệu quả

Thành phần tìm kiếm cục bộ (Local Search) trong luận văn được thiết kế để tinh chỉnh một cây quyết định nhất định. Thủ tục này duyệt qua từng nút không phải là lá của cây. Tại mỗi nút, nó thử thay thế quy tắc phân nhánh hiện tại bằng tất cả các quy tắc khả thi khác (tức là thử tất cả các thuộc tính khác và các ngưỡng chia tiềm năng). Nếu một sự thay đổi nào đó dẫn đến việc giảm tổng tỷ lệ lỗi của toàn bộ cây trên tập dữ liệu tối ưu hóa, sự thay đổi đó sẽ được chấp nhận ngay lập tức, và quá trình tìm kiếm sẽ bắt đầu lại từ nút đầu tiên. Điều này đảm bảo rằng mỗi cải tiến được tận dụng ngay lập tức. Thứ tự duyệt các nút cũng được xem xét, bao gồm duyệt từ trên xuống, từ dưới lên, hoặc dựa trên một tiêu chí gọi là "Hiệu suất Phân loại" để ưu tiên các nút có khả năng cải thiện cao nhất.

4.2. Xây dựng cấu trúc lân cận Neighborhood Structure đa dạng

Cấu trúc lân cận trong bài toán này định nghĩa khái niệm "hàng xóm" của một cây quyết định. Trong luận văn, một cấu trúc lân cận cấp p (ký hiệu Np) được định nghĩa là tập hợp tất cả các cây có thể được tạo ra bằng cách thay đổi quy tắc phân nhánh của đúng p nút trong cây ban đầu. Ví dụ, một cây trong vùng lân cận N1 khác với cây gốc ở một quy tắc phân nhánh. Một cây trong vùng N2 khác ở hai quy tắc. Thuật toán VNS sẽ bắt đầu với p=1, tạo một cây ngẫu nhiên trong N1 và tối ưu hóa nó. Nếu không có cải thiện, nó sẽ tăng p lên 2, thử tạo và tối ưu hóa một cây trong N2, và cứ tiếp tục như vậy. Việc tăng dần p cho phép thuật toán thực hiện những bước nhảy ngày càng lớn trong không gian tìm kiếm, giúp nó thoát khỏi các vùng tối ưu cục bộ sâu.

4.3. Quy trình xây dựng cây mới kết hợp phân chia dữ liệu

Để giải quyết đồng thời cả vấn đề tối ưu hóa và quá khớp, luận văn đề xuất một quy trình xây dựng cây hoàn chỉnh mới. Thay vì sử dụng toàn bộ dữ liệu huấn luyện để vừa xây dựng vừa tối ưu hóa, dữ liệu được chia thành hai phần: tập xây dựng (D_learning) và tập tối ưu hóa (D_optimizing). Đầu tiên, một cây quyết định ban đầu được xây dựng trên tập D_learning bằng thuật toán truyền thống. Sau đó, thuật toán tối ưu hóa VNS được áp dụng trên cây này, nhưng hàm mục tiêu (tỷ lệ lỗi) được tính toán trên tập D_optimizing. Chiến lược này giúp đảm bảo rằng quá trình tối ưu hóa không chỉ làm giảm lỗi trên dữ liệu đã biết mà còn cải thiện khả năng tổng quát hóa của cây trên dữ liệu mới, từ đó giảm nguy cơ quá khớp một cách hiệu quả.

V. Kết quả thực nghiệm Tối ưu hóa cây quyết định trên UCI

Để kiểm chứng 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 nổi tiếng từ kho lưu trữ UCI Machine Learning, bao gồm Pima Indians Diabetes, Wisconsin Breast Cancer, và Iris. Các thử nghiệm được chia thành ba cấp độ. Cấp độ đầu tiên kiểm tra hiệu quả của riêng thuật toán tìm kiếm cục bộ (Local Search). Kết quả cho thấy, ngay cả khi không có VNS, việc tìm kiếm cục bộ đã có thể cải thiện đáng kể tỷ lệ lỗi của các cây được xây dựng bởi C4.5 và CART, đặc biệt trên các bộ dữ liệu phức tạp như Pima. Cấp độ thứ hai kiểm tra toàn bộ thuật toán tối ưu hóa cây quyết định dựa trên VNS. Các thí nghiệm cho thấy thuật toán có thể giảm tỷ lệ lỗi học (training error) một cách nhất quán. Tuy nhiên, việc giảm lỗi học quá mức có thể dẫn đến quá khớp. Điều này dẫn đến cấp độ thử nghiệm thứ ba, kiểm tra quy trình xây dựng cây mới có phân chia dữ liệu. Sử dụng phương pháp kiểm tra chéo 10 lần (10-fold cross-validation), kết quả cho thấy quy trình mới không chỉ giảm lỗi học mà còn cải thiện tỷ lệ lỗi ước tính trên dữ liệu kiểm tra. Điều này chứng tỏ phương pháp kết hợp giữa thuật toán VNS và phân chia dữ liệu có thể tạo ra những cây quyết định vừa chính xác hơn vừa có khả năng tổng quát hóa tốt hơn so với các phương pháp truyền thống.

5.1. Phân tích hiệu quả tối ưu hóa ngưỡng và quy tắc phân nhánh

Các thử nghiệm ban đầu tập trung vào hai cấp độ của tìm kiếm cục bộ: tối ưu hóa ngưỡng (chỉ thay đổi giá trị ngưỡng, giữ nguyên thuộc tính) và tối ưu hóa quy tắc phân nhánh (thay đổi cả thuộc tính và ngưỡng). Kết quả cho thấy việc tối ưu hóa toàn bộ quy tắc phân nhánh mang lại sự cải thiện đáng kể hơn. Ví dụ, trên bộ dữ liệu Pima, tỷ lệ lỗi phân loại sai (misclassification rate) của cây ban đầu đã giảm rõ rệt sau khi áp dụng thuật toán tìm kiếm cục bộ. Điều này chứng tỏ rằng các thuật toán tham lam thường không chọn được cặp thuộc tính-ngưỡng tốt nhất từ góc độ toàn cục, và có rất nhiều không gian để cải thiện thông qua một quá trình tối ưu hóa sau đó.

5.2. Đánh giá ảnh hưởng của cấu trúc cây đến khả năng tối ưu

Một câu hỏi quan trọng là liệu khả năng tối ưu hóa có phụ thuộc vào kích thước và độ phức tạp của cây ban đầu hay không. Luận văn đã thực hiện các thử nghiệm bằng cách tạo ra các cây có kích thước khác nhau (được kiểm soát bởi các tham số như số lượng mẫu tối thiểu ở mỗi lá hoặc độ sâu tối đa) và sau đó tối ưu hóa chúng. Kết quả chỉ ra rằng không có một mối quan hệ tuyến tính đơn giản. Tuy nhiên, các cây lớn hơn và phức tạp hơn thường có nhiều tiềm năng để tối ưu hóa hơn, vì chúng có nhiều quy tắc phân nhánh hơn để điều chỉnh. Thí nghiệm cũng cho thấy thuật toán tối ưu hóa không nhạy cảm quá mức với chất lượng của giải pháp ban đầu; ngay cả khi bắt đầu từ một cây được tạo ngẫu nhiên (cùng cấu trúc), thuật toán vẫn có thể hội tụ về các giải pháp có chất lượng cao.

VI. Kết luận từ luận văn Tương lai của tối ưu hóa cây quyết định

Luận văn "Optimisation des arbres de décision basée sur recherche à voisinage variable" đã chứng minh một cách thuyết phục rằng việc áp dụng metaheuristic, cụ thể là thuật toán VNS, là một hướng đi hiệu quả để cải tiến thuật toán cây quyết định. Bằng cách xem việc xây dựng cây như một bài toán tối ưu hóa tổ hợp, nghiên cứu đã vượt qua được những hạn chế cố hữu của các phương pháp tham lam truyền thống. Kết quả thực nghiệm đã khẳng định rằng phương pháp đề xuất có thể tạo ra các cây quyết định với tỷ lệ lỗi thấp hơn và khả năng tổng quát hóa tốt hơn. Đóng góp chính của luận văn nằm ở việc xây dựng một thuật toán decision tree optimization hoàn chỉnh, bao gồm cả thủ tục tìm kiếm cục bộ và cấu trúc lân cận được thiết kế riêng cho cây quyết định. Hơn nữa, việc đề xuất quy trình kết hợp phân chia dữ liệu để chống quá khớp đã giải quyết được một trong những thách thức lớn nhất của mô hình này. Luận văn này không chỉ là một công trình machine learning thesis có giá trị học thuật cao mà còn mở ra nhiều hướng nghiên cứu tiềm năng trong tương lai, chẳng hạn như áp dụng VNS cho các loại cây quyết định khác (ví dụ: cây hồi quy) hoặc kết hợp VNS với các kỹ thuật học máy tiên tiến khác để tạo ra các mô hình mạnh mẽ hơn.

6.1. Tóm tắt đóng góp chính của phương pháp VNS trong luận văn

Đóng góp cốt lõi của luận văn là việc áp dụng thành công thuật toán VNS vào bài toán tối ưu hóa cây quyết định. Nghiên cứu đã chỉ ra rằng các cây quyết định được tạo bởi các thuật toán truyền thống như C4.5 không phải là tối ưu toàn cục và có thể được cải thiện đáng kể. Luận văn đã thiết kế một thuật toán tối ưu hóa hiệu quả, có khả năng thoát khỏi các điểm tối ưu cục bộ. Thêm vào đó, quy trình xây dựng cây mới, kết hợp tối ưu hóa trên một tập dữ liệu riêng biệt, đã chứng tỏ hiệu quả trong việc cân bằng giữa độ chính xác trên tập huấn luyện và khả năng tổng quát hóa, một vấn đề then chốt trong mọi ứng dụng khai phá dữ liệu thực tế.

6.2. Hướng nghiên cứu tiềm năng và phát triển trong tương lai

Nghiên cứu này mở ra nhiều hướng phát triển hứa hẹn. Một hướng đi tự nhiên là mở rộng phương pháp này cho các loại mô hình cây khác, chẳng hạn như cây hồi quy hoặc các mô hình học tập tập thể (ensemble learning) dựa trên cây như Random Forest và Gradient Boosting. Việc tối ưu hóa từng cây riêng lẻ trong một "rừng" có thể cải thiện hiệu suất tổng thể của mô hình. Một hướng khác là khám phá các cấu trúc lân cận và các thuật toán tìm kiếm cục bộ phức tạp hơn để tăng tốc độ hội tụ và tìm kiếm các giải pháp tốt hơn nữa. Cuối cùng, có thể nghiên cứu việc tích hợp trực tiếp heuristic optimization như VNS vào chính quá trình xây dựng cây, thay vì chỉ là một bước hậu xử lý, để tạo ra một thuật toán xây dựng cây quyết định hoàn toàn mới và ưu việt hơn.

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 TIEU LUAN MOI download : [e-mail] 2006 DANG Cong Kien ALL RIGHTS RESERVED TIEU LUAN MOI download : [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- TIEU LUAN MOI download : [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. TIEU LUAN MOI download : [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 .1 Test d'Optimisation des Seuils .2 Test d'Optimisation de Fra tionnement .3 Observation de l'inuen e de struture d'arbre .4 Observation de l'inuen e de la solution initiale .2 Optimisation des arbres de dé ision .3 Constru tion des arbre basant l'optimisation. 49 6 Con lusion 52 Bibliographie 54 5 TIEU LUAN MOI download : [e-mail] LISTE DES TABLEAUX 5.1 Résultat d'optimisation de seuil sur pima .2 Résultat d'optimisation de seuil sur an er .3 Résultat d'optimisation de seuil sur an er .4 Résultat d'optimisation de fra tionnement sur pima .5 Résultat d'optimisation de fra tionnement sur an er .6 Résultat d'optimisation de fra tionnement sur iris .7 Observation d'Inuen e de la stru ture d'arbre sur pima - optimisation de seuil .8 Observation d'Inuen e de la stru ture d'arbre sur an er - optimisation de fra tionnement .9 Observation d'Inuen e de la stru ture d'arbre sur pima - optimisation de fra tionnement .10 Observation d'Inuen e de la stru ture d'arbre sur an er - optimisation de fra tionnement.

43 6 TIEU LUAN MOI download : [e-mail] TABLE DES FIGURES 2.1 Exemple d'un arbre de dé ision .4 Distribution de 100 fois d'optimisation d'arbre aléatoire 4.1 Relation entre la taille d'arbre et la apa ité d'optimisation .6 Distribution de 100 fois d'optimisation d'arbre aléatoire 4.2 Distribution de 100 fois d'optimisation d'arbre aléatoire 4.3 Distribution de 100 fois d'optimisation d'arbre aléatoire gini an er .5 Distribution de 100 fois d'optimisation d'arbre aléatoire gini pima .8 Optimisation des arbres de BLD - taille par profondeur espèré .7 Optimisation des arbres de BLD - taille par nombre des observation .10 Optimisation des arbres de pima - taille par nombre des observations .9 Optimisation des arbres de pima - taille par nombre des observation .11 Constru tion basant partition 3-1 sans hevau hement - pima .12 Constru tion basant partition 3-1 ave hevau hement - pima .13 Constru tion basant partition 4-1 ave hevau hement - pima .14 Comparaison des résultats. 51 7 TIEU LUAN MOI download : [e-mail] LISTE DES ALGORITHMES 1 S héma de base de Constru tion d'arbre de dé ision - buildTree(S). 19 2 S héma de base de Re her he Voisinages Variables. 27 3 S héma de Re her he Voisinages Variable Réduite - RVVR.

28 4 S héma de Re her he Voisinages Des endante - RVVD. 29 5 S héma de Re her he Voisinages Variables de Dé omposition. 29 6 S héma de base de Re her he Voisinages asyméthique. 30 7 S héma de base d'alogorithme d'optimisation en basant sur RVV.

32 8 S héma de la fon tion optimizeSplitingRule(T ). 34 9 S héma de réation la Stru ture de Voisinage. 36 10 S héma de Constrution d'arbre basant l'Optimisation. 37 8 TIEU LUAN MOI download : [e-mail] Chapitre 1 INTRODUCTION Dans le monde de notre jour, la lassi ation est un des problèmes très universels dans la vie, on a besoin de lassi ation dans tous les domaines.

Pour le faire on emploie souvent l'arbre de dé ision qui est un des modèles de lassi ation ( lassi ateurs) les plus onnus et utilisés le plus largement. Cela est une des raisons pour lesquelles il y a pleins d'algorithmes, de te hniques de onstru tion d'arbre de dé ision et jusqu'à maintenant ils sont en ore un sujet dé. En général, les algorithmes de réation de lassi ateurs sont atégorisés en trois appro hes prin ipales in luant la statistique, l'apprentissage des ma hines (l'apprentissage automatique) et le réseau des neuronnes. Notez que ette lassi ation est seulement orre te dans le ontexte de problème de onstru tion des lassi ateurs.

Par exemple, en fait, le réseau des neuronnes et l'ap- prentissage des ma hines employent ee tivement des algorithmes d'apprentissage. La diéren e dans e ontexte est que, le reseau des neuronnes est le modèle uninterprétble, par ontre, les modèles basés sur d'apprentissage des ma hines sont interprétable. Selon ette lassi ation, la plupart des algorithmes de onstru tion d'arbre de dé ision sont onsidérés omme l'appro he d'apprentissage des ma hines. L'idée ommune des alogorithmes de onstru tion d'arbre de dé ision est de parti- tionner l'ensemlble des exemples (é hantillons) selon la stru ture d'un arbre tel que les partitions nales ontiennent les as de même lasse.

Autrement dit, les impuretés de partition sont zero. Chaque partition orrespond à un noeud de l'arbre. Une partition est dévisée en des sous-partitions selon une règle de fra tionnement qui est essentiel- lement une fon tion de deux variables retournant une valeur entiere représentant une bran he ou un noeud d'enfant. Le pro essus de onstru tion est alors la détermina- tion les fon tions de partition à haque noeud intérieur tel que la impureté d'arbre étant totale statistique des impuretés des partitions nales est minimisée.

L'impurité 9 TIEU LUAN MOI download : [e-mail] est égale 0 dans le as idéal. Selon l'appro he traditionnelle, par exemple CART, C4.5, pour haque noeud on hoisit une fon tion qui permet de réduire le plus l'impureté de e noeud. Du point de vue d'optimisation, e pro essus est minimisation d'impureté basant sur la re her he gloutone. Don , on n'est pas sûre que les algorithmes nous donnent les résultats les meilleurs.

Grâ e à des résultats en étude d'optimisation, on espère que la qualité d'arbre de dé ision soit améliorée , par exemple, de diminuer de taux d'erreur d'apprentissage, déminuer la taille et déminuer le taux d'erreur estimé en appliquant une te hnique de l'optimisation globale. Dans e premièr hapitre, je vais onserver des mots généraux à introduire deux domaines relatifs. L'introdu tion briève exprime aussi notre motivation de re her he qui nous aide de dénir lairement la problématique. La problématique et la stru ture du rapport sont représentées dans la se tion dernière du hapitre.1 Classi ation Selon le sens le plus large, le terme " lassi ation" aborde un pro essus se ompo- sant de deux étapes prin ipales : la onstru tion des règles de lassi ation basée sur des informations disponibles et l'utilisation des règles à prendre de dé ision ave les nouvelles observations.

Du point de vue d'utilisateur, le terme " lassi ation" implique la deuxième étape. De notre té - l'informati ien, on on entre surtout sur la première étape. Malgré que les modèles de lassi ateur sont diérents, on a essayé de proposer des ritères ommuns pour évaluer et omparer les modèles. Parmi plein des issues, l'exa titude, la vitesse, la ompréhensibilité et le temps d'apprentissage sont les issues ru iales [1℄ Il y a trois omposants prin ipaux du problème de lassi ation (problème de onstru tion un lassi ateur)[1℄ • Distribution de probabilité antérieure • Critère de séparation des lasses • Coût de mauvaise- lassi ation La plupart des te hniques onfond impli itement des les omposants.

Néamoins, théoriquement, es omposants peuvent être étudiés inviduellement et les résultats sont ombinés en la règle de lassi ation. Il y a plein des appro hes proposées pour onstru tion de lassi ateur qui sont dévisées en trois atégories prin ipales[1℄ : 10 TIEU LUAN MOI download : [e-mail] • Apprentissage des ma hines indique les méthodes qui onstruisent la règles de lassi ation basant des observations sur un ensemle des exemples ou é hantillons. • Les appro hes statistiques sont ara térisées par utilisation d'un modèle de proba- bilitique qui fournit la probabilité de haque lasse au lieu d'indiquer lairment la lasse de nouvelle observation. Les modèles typiques sont le dis riminant linéaire, le dis riminant quadratique, le dis riminant logistique et la règle de Bayess.

• Réseau des neuronnes qui, en général, est un type de l'apprentissage des ma hines.