Overview về Decision Tree

Thuật toán Decision Tree là một trong những thuật toán phân loại cơ bản nhất của Machine Learning và với việc sử dụng các thư viện hỗ trợ, ứng dụng Decision Tree trong thực tế trở nên vô cùng đơn giản, gói gọn trong vài dòng code. Ta có thể xem xét ví dụ sử dụng Python và thư viện scikit-learn ở dưới đây:

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
iris = load_iris()
clf = DecisionTreeClassifier(criterion='entropy', max_depth=3, random_state=17)
clf = clf.fit(iris.data, iris.target)

Chỉ với 5 dòng code, một model DecisionTree đã được train để phân loại với tập data Iris có sẵn của scikit-learn. DecisionTree là một whitebox model, ta có thể dễ dàng nhìn được cấu trúc dữ liệu bên trong và logic để phân loại data của nó. Có thể hình dung cấu trúc dữ liệu của DecisionTree như sau.

Decision Node thể hiện một rule để phân nhánh data theo một thuộc tính (có thể hiểu là một rule áp dụng lên feature của data), mỗi nhánh từ Decision Node là kết quả phân nhánh theo rule đó, Leaf Node là kết quả phân loại cuối cùng. Ta có thể hình dung rõ ràng hơn với graph thể hiện cụ thể một model Decision Tree đã được train ở dưới đây:

Để xây dựng cấu trúc cây ở trên, thuật toán Decision Tree đơn giản sẽ bao gồm các bước sau:

  • Chọn lựa thuộc tính của data để chia data sử dụng Attribute Selection Measures(ASM: Chỉ số đánh giá lựa chọn thuộc tính )
  • Tạo descision node với feature và điều kiện ở trên.
  • Phân nhánh data tạo các child node và lặp lại tiến trình ở trên cho đến khi một trong các điều kiện sau thoả mãn, ta sẽ có leaf node:
    • Tất cả data của node đều thoả mãn điều kiện của decision node.
    • Không có feature với điều kiện nào có thể được chọn nữa.
    • Không còn data nào thoả mãn điều kiện của decision node.

Bài viết hôm nay sẽ tập trung giới thiệu về các ASM, chỉ số đánh giá thuộc tính. Bằng việc phân tích dữ liệu đầu vào, ASM đưa ra ranking cho các thuộc tính của data, sau đó lựa chọn thuộc tính tốt nhất làm điểm để chia nhánh dữ liệu. Nếu sử dụng scikit-learn thì chỉ số này có thể được cài đặt bằng cách thay đổi giá trị của biến criterion như ví dụ code ở trên. Scikit-learn hộ trỡ 2 giá trị cho biến criterion là gini và entropy tương ứng với hai chỉ số là gini impurity và information gain.

Entropy và information gain

Entropy là một khái niệm khá thông dụng được dùng trong nhiều lĩnh vực vật lý, toán học v..v.. Trong lĩnh vực xử lý thông tin, nhà toán học Claude Shannon đã đưa ra khái niệm information entropy (Shannon entropy). Shannon entropy thể hiện mức độ hỗn loạn hay độ nhiễu của data. Với một hệ thống với N trạng thái có thể xảy ra thì công thức của Shannon entropy sẽ như ở dưới:

$$\Large S = -\sum_{i=1}^{N}p_i \log_2{p_i}$$

Trong đó \(p_i\) là xác suất trạng thái thứ \(i\) xuất hiện ở trong hệ thống. Giá trị entropy càng cao thì độ hỗn loạn của hệ thống càng cao, còn nếu càng thấp thì hệ thống càng có trật tự. Và một hệ thống có trật tự cũng tương đương với việc data được phân nhánh một cách chuẩn chỉ.

Ta có thể xem xét một ví dụ đơn giản. Có 20 viên bi, được xếp theo thứ tự như sau, có 9 viên màu xanh, 11 viên màu đỏ (o là màu xanh, x là màu đỏ).

x o o o o x x x x  o  o  o  o  x  x  x  x  x  x  o
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Bài toán là dự đoán màu của viên bi dựa vào thứ tự sắp xếp. Nếu không để ý tới thứ tự thì xác suất ta lấy được viên màu xanh là \(p_1=\frac{9}{20}\), màu đỏ là \(p_2=\frac{11}{20}\). Entropy ban đầu của tập data sẽ có giá trị là \(S_0 = -\frac{9}{20}\log_2{\frac{9}{20}}-\frac{11}{20}\log_2{\frac{11}{20}} \approx 1\).
Nếu ta tiếp tục chia tập các viên bi thành 2 nhóm khác nhau theo tiêu chí chia là thứ tự nhỏ hơn hoặc bằng 13 là 1 nhóm, các viên bi còn lại vào một nhóm:

          x o o o o x x x x  o  o  o  o  x  x  x  x  x  x  o
          1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
                                   |
                                 x <= 13
                               /         \
x o o o o x x x x  o  o  o  o              x  x  x  x  x  x  o
1 2 3 4 5 6 7 8 9 10 11 12 13             14 15 16 17 18 19 20

Nhóm bên trái có 8 viên xanh và 5 viên đỏ nên nó giá trị entropy \(S_1 = -\frac{5}{13}\log_2{\frac{5}{13}}-\frac{8}{13}\log_2{\frac{8}{13}} \approx 0.96\).
Nhóm bên phải có 1 viên xanh và 5 viên đỏ nên nó có giá trị entropy \(S_2 = -\frac{1}{7}\log_2{\frac{1}{7}}-\frac{6}{7}\log_2{\frac{6}{7}} \approx 0.6\).
Ta nhận thấy entropy của mỗi nhóm sau khi chia đều giảm so với entropy ban đầu của hệ thống. Gía trị entropy thể hiện mức độ hỗn loạn của hệ thống, do đó khi entropy giảm hệ thống có trật tự hơn hay có thể nói có nhiều thông tin hơn. Do vậy, độ giảm của entropy được gọi là information gain và có công thức như sau:

$$\Large IG(Q) = S_O - \sum_{i=1}^{q}\frac{N_i}{N}S_i$$

Trong đó:
\(IG\) là giá trị information gain
\(Q\) là điều kiện để chia data
\(q\) là số nhóm sau khi chia
\(N_i\) là số lượng data của mỗi nhóm

Áp dụng với ví dụ các viên bi ở trên, information gain sau khi chia thanh 2 nhóm với điều kiện thứ tự \(x <= 13\) sẽ là:

$$ \Large IG(x \leq 13) = S_0 - \frac{13}{20}S_1 - \frac{7}{20}S_2 \approx 0.16.$$

Nếu ta tiếp tục chia nhánh nhóm các viên bi, cho tới khi mỗi nhóm chỉ có duy nhất một loại bi thì lúc đó entropy của các nhóm này sẽ đều là 0 (Do \(\log_2{1} = 0\). Vậy là ta đã có được các Leaf Node và một Decision Tree dùng để dự đoán màu của viên bi theo thứ tự, dù là model này đã overfit cứng với tập viên bi được cung cấp.
Trong ví dụ ở đây, ta chọn điều kiện để chia nhóm các viên bi một cách ngẫu nhiên, nhưng trong thực tế khi training Decision Tree, điều kiện chia sẽ được chọn sao cho giá trị information gain sau khi chia là lớn nhất.

Gini Impurity

Đơn giản hơn so với Entropy và information gain, Gini Impurity là chỉ số thể hiện mức độ phân loại sai khi ta chọn ngẫu nhiên một phần tử từ tập data. Gini Impurity có công thức như sau:

$$G = \sum\limits_k p_k * (1 - p_k)^2 = 1 - \sum\limits_k (p_k)^2$$

Trong đó:
\(G\) là giá trị Gini Impurity
\(k\) số các lớp có trong tập data
\(p_k\) là xác suất mà một phần tử ngẫu nhiên thuộc lớp \(k\)

Quay lại ví dụ chọn bi ở phần trên, Gini impurity ban đầu của tập data sẽ là \(G_0 = 1 - (\frac{9}{20})^2 - (\frac{11}{20})^2 \approx 0.5 \)

Cho nhóm 1: \(G_1 = 1 - (\frac{5}{13})^2 - (\frac{8}{13})^2 \approx 0.47 \)

Cho nhóm 2: \(G_2 = 1 - (\frac{1}{7})^2 - (\frac{6}{7})^2 \approx 0.24 \)

Ta thấy, giá trị Gini Impurity sau khi chia của mỗi nhóm đều nhỏ hơn so với giá trị ban đầu => Sau khi chia nhóm mức độ phân loại sai của hệ thống đã giảm. Độ giảm của Gini Impurity được gọi là Gini Gain và có công thức tính tương tự như information gain, chỉ khác là ta sẽ sử dụng giá trị Gini Impurity thay vì Entropy:

$$\Large GG(Q) = G_O - \sum_{i=1}^{q}\frac{N_i}{N}G_i$$

Với ví dụ chọn bi, Gini Gain sau khi chia nhóm lần đầu sẽ là:

$$ \Large GG(x \leq 13) = G_0 - \frac{13}{20}G_1 - \frac{7}{20}G_2 \approx 0.11$$

Cũng tương tự như với khi sử dụng Entropy, Gini Impurity của một Leaf Node sẽ là 0 và khi training Decision Tree, điều kiện được chọn để chia nhóm cũng sẽ được chọn sao cho giá trị Gini Gain là lớn nhất

Kết luận

Trong thực tế qua kiểm nghiệm thì việc chọn Entropy hay Gini Impurity cũng sẽ không ảnh hưởng nhiều đến kết quả dự đoán của Decision Tree. Do đó khi tuning parameter, ta có thể bỏ qua việc tuning parameter này.
Nhưng dù sao thì hi vọng bài viết đã đem lại cho người đọc thêm kiến thức để hiểu rõ hơn về Decision Tree cũng với các chỉ số phân chia nhánh xây dựng Tree của nó.

References