Trong bài học ngày hôm nay chúng ta sẽ tìm hiểu về một ML model phi tuyến tính (non-linear) có thể sử dụng cho cả bài toán phân loại (classification) và hồi quy (regression) đó là cây quyết định - Decision tree.
Định nghĩa về Decision tree
Decision tree là một dạng công cụ giúp hỗ trợ cho việc đưa ra quyết định dựa trên mô hình cây (tree-like model) quyết định và hệ quả. Trong decision tree, chúng ta sẽ có các nút (node) của cây chứa các phép so sánh trên một thuộc tính (attribute) và kết quả của phép so sánh này sẽ dẫn đến các nhánh (branch) hệ quả khác nhau. Hệ quả cuối cùng của một nhánh (branch) được gọi là lá (leaf), nó sẽ biểu thị nhóm (class) tương ứng của cá thể (instance) trong bài toán phân loại (classification), hay một giá trị số trong bài toán hồi quy (regression).
Ví dụ
Xét một ví dụ như sau, tập huấn luyện (training set) của chúng ta như mô tả trong hình bên dưới có 10 cá thể (instance) với 3 biến không phụ thuộc (independent variable) đó là hoàn tiền (refund), tình trạng hôn nhân (marital status), thu nhập chịu thuế (taxable income). Biến phụ thuộc (dependent variable) ở đây là có gian lận (cheat) thuế hay không ?
Source: cs.wmich.edu
Dựa vào dữ liệu của tập huấn luyện (training set) trên, chúng ta có thể xây dựng một Decision tree như sau:
Source: cs.wmich.edu
Trong hình trên các ô màu vàng chính là nút (node) của cây, các ô màu xanh là lá (leaf).
Giờ chúng ta sẽ sử dụng Decision tree này để phân loại một cá thể (instance) trong tập kiểm thử (test set) nhé. Cá thể (instance) trong tập kiểm thử (test set) của chúng ta có số liệu như sau:
Source: cs.wmich.edu
Ứng từng giá trị của cá thể (instance) trên vào Decision tree đã xây dựng, chúng ta sẽ có được suy luận (deduction) rằng cá thể (instance) này không gian lận (cheat) thuế.
Source: cs.wmich.edu
Để xây dựng được một Decision tree như trên, trong quá trình huấn luyện (training) ML model, quá trình quy nạp (induction) cây sẽ diễn ra và nó dựa trên chiến lược tham lam (greedy strategy). Trong chiến lược tham lam (greedy strategy) chúng ta sẽ phân nhánh cây dựa trên các phép so sánh trên các thuộc tính (attribute) sao cho các phân nhánh phải tối ưu nhất theo tiêu chuẩn đặt ra. Vậy chúng ta sẽ đưa ra các điều kiện so sánh để phân nhánh như nào và tiêu chuẩn để đánh giá phân nhánh ra sao ?
Phân nhánh cây
Đối với điều kiện so sánh để phân nhánh, chúng ta sẽ dựa trên 2 yếu tố sau:
- Loại thuộc tính: kiểu số (numerical value), kiểu phân loại (categorical value)
- Loại phân nhánh: Phân nhánh nhị phân, đa phân nhánh
Trong ví dụ ở bên trên chúng ta có các biến không phụ thuộc (independent variable) là hoàn tiền (refund) và tình trạng hôn nhân (marital status) là kiểu phân loại (categorical value). Biến hoàn tiền (refund) do đặc thù chỉ có 2 loại đó là Yes và No nên nó chỉ có thể phân nhánh nhị phân như sau:
Tuy nhiên đối với biến tình trạng hôn nhân (marital status) chúng ta có tới 3 loại đó là: độc thân (Single), đã kết hôn (Married), đã ly dị (Divorced). Do đó chúng ta có thể phân nhánh theo cả dạng nhị phân bằng cách gộp các loại lại sao cho thành 2 phân loại lớn, hay đa phân nhánh theo từng loại. Hình dưới đây sẽ minh họa các cách phân nhánh cho biến này, trong đó hình bên trái là phân nhánh nhị phân (Gộp 2 loại Single và Divorced thành 1 phân loại lớn) , bên phải là đa phân nhánh.
Ngoài 2 biến trên, tập dữ liệu (dataset) của chúng ta còn có 1 biến không phụ thuộc (Independent variable) dạng số (numerical value) đó là thu nhập chịu thuế (taxable income). Đối với các biến thuộc dạng này chúng ta có 2 phương án xử lý như sau:
- Rời rạc hóa dữ liệu (discretization): theo dạng tĩnh (static) trong đó coi mỗi giá trị là một loại (category), theo dạng động (dynamic) trong đó chia khoảng (interval) giá trị toàn cục ra thành từng khoảng (interval) nhỏ hơn, mỗi khoảng (interval) nhỏ này sẽ là một loại (category).
- Phân định nhị phân (binary decision): Đặt ra một giá trị trong khoảng (interval) giá trị toàn cục làm ngưỡng (threshold), các giá trị của biến sẽ được so sánh nhỏ hơn hoặc lớn hơn bằng để phân nhánh.
Hình dưới đây sẽ minh họa về 2 cách phân nhánh cho biến thu nhập chịu thuế (taxable income), trong đó hình bên trái là sử dụng phương pháp rời rạc hóa dữ liệu (discretization) theo dạng động (dynamic) và bên phải sử dụng phương pháp phân định nhị phân (binary decision):
Chỉ số vấy bẩn
Sau khi đã phân nhánh được thành công, chúng ta cần đánh giá các phân nhánh để xem mức độ tối ưu của nó. Theo chiến lược tham lam (greedy strategy) chúng ta sẽ chọn phân nhánh có tình đồng nhất (homogeneous) cao và có độ vấy bẩn (impurity) thấp. Xét ví dụ trên đối với biến hoàn tiền (refund), khi phân nhánh theo hai loại Yes và No chúng ta thu được kết quả như sau:
Trong đó C0 là biểu thị của nhóm (class) No và C1 là biểu thị của nhóm (class) Yes ở biến phụ thuộc (dependent variable) gian lận thuế (Cheat).
Có thể thấy với nhánh Yes, các cá thể (instance) trong tập huấn luyện (training set) đều đồng nhất với nhau thuộc về cùng nhóm (class) C0. Tuy nhiên với nhánh No lại ngược lại, các cá thể không đồng nhất với nhau, tỷ lệ các thể thuộc về 2 nhóm (class) C0 và C1 gần như bằng nhau. Khi có một cá thể (instance) mới nếu như nó có giá trị ở biến hoàn tiền (refund) là Yes, chúng ta có thể khẳng định chắc chắn nó không gian lận thuế. Mặt khác nếu cá thể (instance) này có giá trị ở biến hoàn tiền (refund) là No, chúng ta khó có thể khẳng định được nó có gian lận thuế hay không.
Như vậy độ vấy bẩn chính là tiêu chuẩn để đánh giá một phân nhánh. Để tính độ vấy bẩn (impurity) của một phân nhánh, chúng ta có thể sử dụng 3 chỉ số như sau:
- Gini index
- Entropy
- Misclassification error
Gini index
Gini index được tính theo công thức sau:
$Gini\:index = 1 - \sum_{i=1}^{n}(P_{i}^{2})$
Trong đó n tương ứng với số nhóm (class) của biến phụ thuộc (dependent variable), $P_{i}$ tương ứng với xác suất (probability) của nhóm i.
Lấy ví dụ về kết quả phân nhánh theo loại Yes ở biến hoàn tiền (Refund) chúng ta sẽ tính được Gini index như sau:
$Gini\:index = 1 - (\frac{3}{3})^{^{2}} - (\frac{0}{3})^{^{2}} = 0$
Gini index kết quả phân nhánh theo loại No:
$Gini\:index = 1 - (\frac{4}{7})^{^{2}} - (\frac{3}{7})^{^{2}} = 0.49$
Entropy
Entropy được tính theo công thức sau:
$Entropy = - \sum_{i=1}^{n}(P_{i} \times log_{2}(P_{i}))$
Lấy ví dụ về kết quả phân nhánh theo loại Yes ở biến hoàn tiền (refund) chúng ta sẽ tính được Entropy như sau:
$Entropy = -(\frac{3}{3} \times log_{2}(\frac{3}{3})) - (\frac{0}{3} \times log_{2}(\frac{0}{3})) = 0$
Entropy kết quả phân nhánh theo loại No:
$Entropy = -(\frac{4}{7} \times log_{2}(\frac{4}{7})) - (\frac{3}{7} \times log_{2}(\frac{3}{7})) = 0.985$
Misclassification error
Misclassification error được tính theo công thức sau:
$Misclassification\:error = 1 -\underset{i}{max}(P_{i})$
Lấy ví dụ về kết quả phân nhánh theo loại Yes ở biến hoàn tiền (refund) chúng ta sẽ tính được Misclassification error như sau:
$Misclassification\:error = 1 -max(\frac{3}{3}, \frac{0}{3}) = 1 - 1 = 0$
Misclassification error kết quả phân nhánh theo loại No:
$Misclassification\:error = 1 -max(\frac{4}{7}, \frac{3}{7}) = 1 - 0.57 = 0.43$
Một cách tổng quan chúng ta có biểu đồ cho 3 chỉ số mô tả độ vấy bẩn (impurity) theo xác suất của 2 nhóm (class) như sau:
Source: cs.wmich.edu
Có thể thấy cả 3 chỉ số đều có chung điểm cực tiểu đó là ở 0, biểu thị độ vấy bẩn (impurity) thấp nhất tương ứng với các kết quả tính được theo phân nhánh loại Yes ở biến hoàn tiền (refund) đã tính ở trên. Gini index và Misclassification error có chung cực đại đó là ở mức 0.5 biểu thị độ vấy bẩn (impurity) cao nhất, trong khi đó Entropy lại cực đại ở mức 1.
Xét trên mặt tính toán, Entropy do trong công thức tính sử dụng $log$ nên tốc độ tính toán sẽ chậm hơn 2 chỉ số trên. Nhưng Entropy với lợi thế về biên độ lớn hơn (từ 0 cho đến 1) sẽ cho độ váy bẩn (impurity) chi tiết hơn đặc biệt là so với Misclassification error.
Điều kiện dừng
Khi quy nạp (induction) cây, Decision tree model sẽ dựa trên 3 điều kiện như sau để dừng việc phát triển cây:
- Dừng mở rộng nút (node) khi tất cả các cá thể (instance) đã thuộc về một nhóm (class)
- Dừng mở rộng nút (node) khi tất các các thế (instace) đều có chung một thuộc tính (attribute)
- Các điều kiện dừng sớm (Early termination) được đặt ra trước khi quy nạp (induction) nhằm tránh xảy ra hiện tượng quá vừa vặn (overfit) như số cá thế (instance) tối thiểu khi phân nhánh, mức độ cải thiện các chỉ số vấy bẩn (impurity),…
Kết
Như vậy trong bài học này chúng ta đã tìm hiểu về cây quyết định - Decision tree và cách xây dựng nó. Đặc tính của Decision tree model nằm ở việc nó có thể phân loại được ngay cả với các cá thể (instance) có giá trị ngoại biên và với cây quyết định nhỏ chúng ta có thể dễ dàng giải thích các quyết định như ví dụ trong bài. Ở bài học sau chúng ta sẽ thực hành triển khai xây dựng một Decision tree model bằng Python, các bạn hãy đón đọc nhé 💪
-
Previous
[Thực Hành] Bài 10 Phân loại Naïve Bayes - Naïve Bayes classifier -
Next
[Thực Hành] Bài 12 Cây quyết định - Decision Tree