Buzz
Trong lý thuyết quyết định (chẳng hạn quản lý rủi ro), một cây quyết định (tiếng Anh: decision tree) là một đồ thị của các quyết định và các hậu quả có thể của nó (bao gồm rủi ro và hao phí tài nguyên). Cây quyết định được sử dụng để xây dựng một kế hoạch nhằm đạt được mục tiêu mong muốn. Các cây quyết định được dùng để hỗ trợ quá trình ra quyết định. Cây quyết định là một dạng đặc biệt của cấu trúc cây.
Giới thiệu chung
Trong lĩnh vực máy học, cây quyết định là một kiểu mô hình dự báo (predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng. Mỗi một nút trong (internal node) tương ứng với một biến; đường nối giữa nó với nút con của nó thể hiện một giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu, cho trước các giá trị của các biến được biểu diễn bởi đường đi từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định.
Học bằng cây quyết định cũng là một phương pháp thông dụng trong khai phá dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các lá đại diện cho các phân loại còn cành đại diện cho các kết hợp của các thuộc tính dẫn tới phân loại đó[1]. Một cây quyết định có thể được học bằng cách chia tập hợp nguồn thành các tập con dựa theo một kiểm tra giá trị thuộc tính [1]. Quá trình này được lặp lại một cách đệ quy cho mỗi tập con dẫn xuất. Quá trình đệ quy hoàn thành khi không thể tiếp tục thực hiện việc chia tách được nữa, hay khi một phân loại đơn có thể áp dụng cho từng phần tử của tập con dẫn xuất. Một bộ phân loại rừng ngẫu nhiên (random forest) sử dụng một số cây quyết định để có thể cải thiện tỉ lệ phân loại.
Cây quyết định cũng là một phương tiện có tính mô tả dành cho việc tính toán các xác suất có điều kiện.
Cây quyết định có thể được mô tả như là sự kết hợp của các kỹ thuật toán học và tính toán nhằm hỗ trợ việc mô tả, phân loại và tổng quát hóa một tập dữ liệu cho trước.
Dữ liệu được cho dưới dạng các bản ghi có dạng:
(x, y) = (x1, x2, x3..., xk, y)
Biến phụ thuộc (biến phụ thuộc) y là biến mà chúng ta cần nghiên cứu, phân loại hoặc tổng quát hóa. x1, x2, x3... là các biến sẽ hỗ trợ chúng ta trong công việc đó
Các loại cây quyết định
Cây quyết định còn được gọi là hai cái tên khác:
Cây hồi quy (Cây hồi quy) ước tính các hàm số có giá trị là số thực thay vì được sử dụng cho các nhiệm vụ phân loại. (ví dụ: dự đoán giá một ngôi nhà hoặc thời gian một bệnh nhân nằm viện)
Cây phân loại (Cây phân loại), nếu y là một biến phân loại như: giới tính (nam hay nữ), kết quả của một trận đấu (thắng hay thua).
Ví dụ minh họa
Chúng ta sẽ sử dụng một ví dụ để giải thích về cây quyết định:
David là quản lý của một câu lạc bộ golf nổi tiếng. Anh ta đang gặp vấn đề với việc xác định liệu các thành viên có đến chơi hay không. Có những ngày mọi người đều muốn chơi golf nhưng lại thiếu nhân viên phục vụ. Đôi khi, không rõ vì lý do gì mà không ai đến chơi, và câu lạc bộ lại có quá nhiều nhân viên.
Mục tiêu của David là tối ưu hóa số lượng nhân viên phục vụ mỗi ngày bằng cách dự đoán thời tiết để biết khi nào người ta sẽ đến chơi golf. Để làm điều này, anh ta cần hiểu tại sao khách hàng quyết định chơi và có cách nào để giải thích điều đó hay không.
Vì vậy, trong hai tuần đó, anh ta đã thu thập thông tin về:
Trong dự báo thời tiết (dự báo thời tiết) (nắng (nắng),
Và dĩ nhiên là số người đến chơi golf vào ngày đó. David thu thập được một bộ dữ liệu gồm 14 dòng và 5 cột.
Sau đó, để giải quyết vấn đề của David, đã có mô hình cây quyết định được áp dụng.
Các nhóm chơi golf khi trời nắng, nhóm chơi khi trời nhiều mây, và nhóm chơi khi trời mưa.
Kết luận đầu tiên: nếu trời nhiều mây, người ta luôn chơi golf. Và có một số người yêu thích đến mức chơi golf ngay cả khi trời mưa.
Sau đó, chúng ta tiếp tục phân nhóm những ngày nắng thành hai phần. Chúng ta nhận thấy rằng khách hàng sẽ không muốn đến sân golf nếu độ ẩm vượt quá 70%.
Cuối cùng, chúng ta chia nhóm những ngày mưa thành hai và nhận thấy rằng khách hàng không thích chơi golf khi trời có nhiều gió.
Và đây là giải pháp ngắn gọn cho vấn đề được mô tả bởi cây quyết định. David quyết định để hầu hết nhân viên nghỉ vào những ngày nắng và ẩm, hoặc những ngày mưa gió. Bởi vì hầu như không có ai chơi golf trong những ngày đó. Trong những ngày khác, khi có nhiều người đến chơi golf, anh ấy có thể thuê thêm nhân viên làm thêm để hỗ trợ công việc.
Kết luận là cây quyết định giúp chúng ta chuyển đổi một biểu diễn dữ liệu phức tạp thành một cấu trúc đơn giản hơn rất nhiều.
Các công thức
Độ thuần khiết Gini
Áp dụng trong thuật toán CART (Classification and Regression Trees). Nó dựa vào việc tính bình phương xác suất của từng loại mục tiêu trong nút. Giá trị này tiến về cực tiểu (bằng 0) khi tất cả các trường hợp trong nút chỉ thuộc về một loại mục tiêu duy nhất.
Cho y
Entropy
Dùng trong các thuật toán xây dựng cây ID3, C4.5 và C5.0. Số đo này dựa trên khái niệm entropy trong lý thuyết thông tin (lý thuyết thông tin).
Ưu điểm của cây quyết định
So với các phương pháp khai thác dữ liệu khác, cây quyết định có một số lợi ích:
- Cây quyết định dễ hiểu. Người ta có thể hiểu ngay lập tức mô hình cây quyết định sau khi được giải thích.
- Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc không cần thiết. Các kỹ thuật khác thường yêu cầu chuẩn hóa dữ liệu, tạo các biến giả (biến giả) và loại bỏ các giá trị trống.
- Cây quyết định có thể xử lý cả dữ liệu số và dữ liệu phân loại. Các kỹ thuật khác thường chỉ phù hợp với phân tích dữ liệu có một loại biến. Ví dụ, các luật liên quan chỉ có thể áp dụng cho biến tên, trong khi mạng neuron chỉ phù hợp với biến số.
- Cây quyết định là mô hình hộp trắng. Nếu có thể quan sát một tình huống cụ thể trong mô hình, ta có thể dễ dàng giải thích điều kiện đó bằng logic Boolean. Mạng neuron là một ví dụ về mô hình hộp đen, vì lời giải thích cho kết quả quá phức tạp để hiểu.
- Có thể đánh giá mô hình bằng các phương pháp thống kê. Điều này giúp ta có thể tin tưởng vào mô hình.
- Cây quyết định có thể xử lý tốt một lượng lớn dữ liệu trong thời gian ngắn. Có thể sử dụng máy tính cá nhân để phân tích các lượng dữ liệu lớn trong thời gian ngắn đủ để các nhà chiến lược đưa ra quyết định dựa trên phân tích của cây quyết định.
== nhược điểm của cây quyết định - khó giải quyết được những vấn đề có dữ liệu phụ thuộc vào thời gian liên tục - dễ xảy ra lỗi khi có quá nhiều lớp chi phí tính toán để xây dựng mô hình cây quyết định CAO
Mở rộng cây quyết định thành đồ thị quyết định
Trong cây quyết định, mọi đường đi từ nút gốc đến nút lá được tiến hành bằng các phép hội (AND). Trong đồ thị quyết định, có thể sử dụng các phép tuyển (OR) để kết nối ghép hai hay nhiều đường lại với nhau.
Phần bù của cây quyết định là phân tích hình thái học (Phân tích hình thái học).
Các nguồn tài nguyên khác
- [1] T. Menzies, Y. Hu, Khai phá dữ liệu cho những người rất bận rộn. IEEE Computer, tháng 10 năm 2003, trang 18-25.
- Phân tích cây quyết định trên mindtools.com
- J.W. Comley và D.L. Dowe, 'Minimum Message Length, MDL và Mạng Bayesian tổng quát với Ngôn ngữ Asymmetric', chương 11 Lưu trữ 2006-09-09 tại Wayback Machine (pp265–294) trong P. Grunwald, M.A. Pitt và I.J. Myung (biên tập)., Advances in Minimum Description Length: Lý thuyết và Ứng dụng Lưu trữ 2006-06-19 tại Wayback Machine, M.I.T. Press, tháng 4 năm 2005, ISBN 0262072629. (Bài báo này nghiên cứu cây quyết định trong các nốt bên trong của mạng Bayes sử dụng Minimum Message Length (MML). Phiên bản trước đó tại Comley và Dowe (2003), [1].)
- P.J. Tan và D.L. Dowe (2004), MML Inference of Oblique Decision Trees, Lecture Notes in Artificial Intelligence (LNAI) 3339, Springer-Verlag, trang 1082-1088. (Bài báo này sử dụng Minimum Message Length.)
- Eruditionhome Lưu trữ 2006-02-12 tại Wayback Machine Site thư mục lớn nhất chứa các nguồn tài nguyên trong khai phá dữ liệu
