Khái niệm cây quyết định
| Trong lĩnh vực học máy, 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ình minh họa
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 đó. 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 . Quá trình này được lặp lại một cách đệ qui cho mỗi tập con dẫn xuất. Quá trình đệ qui 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 (dependant variable) y là biến mà chúng ta cần tìm hiểu, phân loại hay tổng quát hóa. x1, x2, x3 ... là các biến sẽ giúp ta thực hiện công việc đó
Cây quyết định còn có hai tên khác:
- Cây hồi quy (Regression tree) ước lượng các hàm giá 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ụ: ước tính giá một ngôi nhà hoặc khoảng thời gian một bệnh nhân nằm viện.
- Cây phân loại (Classification tree), 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ụ: Ta có dữ liệu (training data) về 10 đối tượng (người). Mỗi đối tượng được mô tả bởi 4 thuộc tính là Gender, Car Ownership, Travel Cost/Km, Income Level và 1 thuộc tính phân loại (category attribute) là Transportation mode. Trong đó thuộc tính Gender có kiểu binary, thuộc tính Car Ownership có kiểu Quantitative integer (0,1), Travel Cost/Km và Income Level có kiểu dữ liệu Ordinal.
Tranining data cho biết sự lựa chọn về loại phương tiện vận chuyển (car, bus, train) của khách dựa vào 4 thuộc tính đã cho (xem bảng).
Bảng 1
Dựa vào Training Data ở trên, chúng ta có thể tạo ra cây quyết định như sau
Hình 1: Ví dụ cây quyết đình
Chú ý rằng trong cây quyết định trên, thuộc tính “Income Level” không xuất hiện trong cây bởi vì dựa vào training data đã cho, thuộc tính “Travel Cost/Km” sẽ sinh ra cây quyết định tốt dùng để phân loại tốt hơn “Income Level”
Làm sao để sử dụng cây quyết định trong dự đoán lớp của các dữ liệu chưa biết ?
Mục đích chính của cây quyết định là dùng để dự đoán lớp (xác định lớp) của các đối tượng chưa biết (unseen data). Giả sử rằng ta có dữ liệu về 3 người với các giá trị dữ liệu đã biết về các thuộc tính Gender, Car Ownership, Travel Cost/Km, Income Level. Tuy nhiên ta chưa biết họ sẽ chọn phương tiện vận chuyển nào (Car, Bus, Train). Nhiệm vụ của chúng ta là sử dụng cây quyết định đã tạo ra để dự đoán (predict) Alex, Buddy và Cherry sẽ chọn phương tiện vận chuyển nào dựa vào 4 thuộc tính của họ. Dữ liệu dưới đây còn được gọi là Testing Data.
Bảng 2
Chúng ta bắt đầu từ node gốc của cây (root node) từ thuộc tính Travel Cost/Km, ta thấy rằng nếu Travel Cost/Km là Expensive thì người đó sẽ chọn phương tiện là Car. Nếu Travel Cost/Km là standard thì họ sẽ chọn phương tiện vận chuyển là Train. Nếu Travel Cost/Km là Cheap thì cây quyết định cần tới giá trị của trường Gender của người đó, nếu Gender là Male thì chọn Bus, nếu giới tính là Female thì cây quyết định cần kiểm tra xem người đó có sử hữu bao nhiêu xe hơi (Car Ownership). Nếu số xe hơi sở hữu là 0 thì người đó sẽ chọn xe Bus, nếu số xe hơi sở hữu là 1 thì người đó sẽ chọn Train.
Theo cây quyết định trên, các luật (Series of Rules) được sinh ra từ cây quyết định dùng để dự đoán như sau:
Rule 1 : If Travel cost/km is expensive then mode = car
Rule 2 : If Travel cost/km is standard then mode = train
Rule 3 : If Travel cost/km is cheap and gender is male then mode = bus
Rule 4 : If Travel cost/km is cheap and gender is female and she owns no car then mode = bus
Rule 5 : If Travel cost/km is cheap and gender is female and she owns 1 car then mode = train
Dựa vào các luật này, việc dự đoán lớp cho các dữ liệu chưa biết (unseen data hay Testing data) rất đơn giản. Trong ví dụ này, Alex có giá trị của thuộc tính Travel Cost/Km là Standard nên sẽ chọn phương tiện là Train (Rule 2) mà không cần quan tâm đến các thuộc tính khác của Alex. Buddy có giá trị của thuộc tính Travel Cost/Kmlà Cheap và Gender của anh ta là Male nên anh ta sẽ chọn Bus (Rule 3). Cheery cũng có giá trị thuộc tính Travel Cost/Km làCheap nhưng Gender là Female và sở hữu 1 xe hơi cho nên theo cây quyết định trên (Rule 5) cô ta sẽ chọn phương tiện là Train.
Kết quả phân lớp bằng cây quyết định như sau:
Bảng 3
Cây quyết định là một phương pháp phân lớp rất hiệu quả và dễ hiểu. Tuy nhiên có một số chú ý khi sử dụng cây quyết định trong xây dựng các mô hình phân lớp như sau:
Hiệu của phân lớp của cây quyết định (Series of Rules) phụ thuộc rất lớn vào training data. Chẳng hạn cây quyết định được tạo ra bởi chỉ giới hạn 10 samples training data trong ví dụ trên thì hiệu quả ứng dụng cây quyết định để dự đoán các trường hợp khác là không cao (thường training data phải đủ lớn và tin cậy) và vì vậy ta không thể nói rằng tập các luật (Series of Rules) được sinh ra bở cây quyết định trên là tập luật tốt nhất.
Một số thuật toán học cây quyết định tiêu biểu
Có rất nhiều thuật toán phân lớp như ID3, J48, C4.5, CART (Classification and Regression Tree),… Việc chọn thuật toán nào để có hiệu quả phân lớp cao tuy thuộc vào rất nhiều yếu tố, trong đó cấu trúc dữ liệu ảnh hưởng rất lớn đến kết quả của các thuật toán. Chẳng hạn như thuật toán ID3 và CART cho hiệu quả phân lớp rất cao đối với các trường dữ liệu số (quantitative value) trong khi đó các thuật toán như J48, C4.5 có hiệu quả hơn đối với các dữ liệu Qualititive value (ordinal, Binary, nominal).
Một số tool demo thuật toán Cây quyết định
1. weka: Tool được sử dụng phổ biến, hoàn toàn miễn phí, được viết bằng Java
2. Clus: Tool mới xây dựng, hoàn toàn miễn phí, được viết bằng Java
St
