Trong lý thuyết quyết định, một cây quyết định là một đồ thị những quyết định và những kết quả có khả năng của chúng (bao gồm cả giá phải trả và độ rủi ro) được sử dụng để tạo ra một đường đi tới đích [4]. Cây quyết định là một dạng đặc biệt của cấu trúc cây được xây dựng để trợ giúp việc ra quyết định. Trong lĩnh vực học máy, cây quyết định là một mô hình dự đoán, có nghĩa là từ việc quan sát các item để rút ra kết luận về giá trị đích của item đó. Mỗi nút bên trong tương đương với một biến, mỗi cung đi tới một nút con tương ứng với giá trị có thể của biến đó. Các là tương ứng với giá trị đích được dự đoán cho các biến. Kỹ thuật học máy sử dụng việc xây dựng cây quyết định trên tập dữ liệu được gọi là học cây quyết định hay đơn giản chỉ là cây quyết định. Học cây quyết định cũng là một phương pháp rất thông dụng trong khai phá dữ liệu. Trong đó cây quyết định mô tả cấu trúc cây mà ở đó các lá đại diện cho các lớp và các nhánh cây biểu diễn sự kết hợp của các đặc trưng dẫn dắt tới việc phân lớp. Một cây quyết định có thể được học bằng cách chia tập nguồn thành các tập con dựa trên giá trị các thuộc tính kiểm tra [4], [5]. Quá trình này được lặp lại trên từng tập con thu được. Quá trình đệ quy sẽ kết thúc khi không thể chia tiếp được nữa hoặc khi từng phần tử của tập con được gán với một lớp đơn. Cây quyết định được mô tả bằng cách tính toán xác suất có điều kiện. Cây quyết định cũng có thể được mô tả như là một kỹ thuật tính toán và hỗ trợ toán học, kỹ thuật này hỗ trợ việc mô tả, phân loại và khái quát tập dữ liệu đưa vào. Dữ liệu đưa vào dạng ghi có dạng: (x, y) = (x1, x2, … ,xk, y ) Biến phụ thuộc y là biến mà chúng ta cố gắng để biết, phân lớp hay tổng quát hóa, còn các biến x1, x2,… là các biến giúp ta thực hiện công việc đó. Trong bài toán phân lớp văn bản, x là vector đặc trưng, y là phân lớp cần tìm. So với các phương pháp khác trong Data Mining, phương pháp cây quyết định có những ưu điểm nổi bất như: - Rất dễ hiểu và dễ giải thích: mọi người đều có thể hiểu mô hình cây quyết định qua một số giải thích tổng quát ban đầu. - Dữ liệu dùng cho cây quyết định chỉ là những dữ liệu căn bản hoặc có thể không cần thiết. Một số kỹ thuật khác có thể đòi hỏi dữ liệu chuẩn, tạo các biến giả và loại bỏ đi các giá trị trống. - Có khả năng xử lý cả dữ liệu thực và dữ liệu mập mờ. Một số kỹ thuật khác chỉ sử dụng những tập dữ liệu đặc biệt chẳng hạn như mạng nơron có thể chỉ sử dụng các biến là số. - Có thể kiểm chứng mô hình bằng cách thử thống kê. - Có khả năng thực hiện tốt đối với dữ liệu lớn trong thời gian ngắn: một lượng lớn dữ liệu có thể được phân tích bằng máy tính cá nhân trong thời gian ngắn đủ để người sử dụng đưa ra quyết định dựa trên sự phân tích đó. Tuy nhiên sử dụng phương pháp cây quyết định có thể xảy ra hiện tượng overfit, tức là tồn tại một giả thuyết h phù hợp với tập ví dụ huấn luyện nhưng tiên đoán không chính xác bằng giả thuyết h’ ít phù hợp với tập ví dụ huấn luyện hơn so với h. Để giải quyết vấn đề này chúng ta phải dùng cách chặt bớt cây (pruning), bỏ bớt đi các nhánh dữ liệu nhiễu và dư thừa… Một vấn đề khác nữa của phương pháp cây quyết định là sự không an định của thuật toán. Tức là, dù chỉ 1 sự thay đổi nhỏ như thêm đỉnh, giảm đỉnh, thêm noise, ... thì kết quả của thuật toán sẽ khác đi rất nhiều. Với những ưu, khuyết điểm như thế, cây quyết định cũng không phải là 1 phương pháp thường được sử dụng trong bài toán phân loại văn bản. |
 | |
|
|