<jupyter_start><jupyter_text>Decision tree learning**Decision tree** là một trong những model thú vị nếu như chúng ta quan tâm đến khả năng suy luận. Giống như cái tên "decision tree" của nó, ta có thể nghĩ ngay đến model này có thể chia nhỏ dữ liệu của chúng ta bằng cách đưa ra quyết định dựa trên việc hỏi một chuỗi các câu hỏi.Xem xét một ví dụ mà ta sử dụng decision tree để quyết định hành động trong ngày:![img](dt1.png)Dựa trên những đặc tính trong dữ liệu training của mình, một mô hình cây quyết định học chuỗi những câu hỏi để suy luận ra nhãn class label cho những mẫu đó. Mặc dù trong hình trên mô tả concept của decision tree là dựa trên biến categoricals variables, concept tương tự được áp dụng nếu như features của chúng ta là số thực, giống như dữ liệu Iris dataset. Ví dụ, ta có thể định nghĩa giá trị cut-off value dựa trên thuộc tính **sepal width** bằng câu hỏi nhị phân: "Có phải sepal width $\geq$ 2.8cm?"Sử dụng thuật toán quyết định này, ta bắt đầu tại giá trị root của cây và chia dữ liệu dựa trên thằng thuộc tính cho chúng ta giá trị **information gain (IG)** tức độ lợi thông tin là lớn nhất, giá trị này sẽ được giới thiệu cụ thể ở phần sau. Trong toàn bộ quá trình, ta lặp lại bước chia này tại mỗi một node con (child node) cho đến node lá là trong sạch, tức độ nhiễu thông tin không còn nữa, và tại đó ta có thể chắc chắn class là gì. Trong thực tế, điều này có thể dẫn đến một cây với rất nhiều node, và dễ dấn đến chuyện overfitting. Do vậy, chúng ta cần phải tỉa **prune** cây bằng cách thiết lập một số giới hạn cho cái chiều sâu tối đa của cây.  Maximizing IG - getting the most bang for your buckĐể chia node dưới dạng chọn thông tin có lợi nhất, ta cần định nghĩa một hàm mục tiêu cần tối ưu trong tree learning algorithm. Ở đây, hàm mục tiêu của ta là cực đại giá trị IG tại mỗi lần chia, hàm IG được định nghĩa như sau:  ![al](https://latex.codecogs.com/gif.latex?IG%28D_%7Bp%7D%2C%20f%29%3DI%28D_%7Bp%7D%29%20-%20%5Csum_%7Bj%3D1%7D%5E%7Bm%7D%5Cfrac%7BN_%7Bj%7D%7D%7BN_%7Bp%7D%7DI%28D_%7Bj%7D%29) Với f là **feature** mà chúng ta muốn thực hiện chia tại nó; $D_{p} và D_{j}$ là dữ liệu của parent và node con thứ jth; I là là độ đo **impurity** (độ đo tạp chất); $N_{p}$ là số lượng dữ liệu train tại node cha; và $N_{j}$ là số lượng của các mẫu trong node con thứ jth. Như chúng ta thấy, hàm độ lợi thông tin đơn giản chỉ là hiệu của **impurify - độ tạp chất** của node cha và tổng các **độ đục** của các thằng con của nó - độ đục của các node con càng nhỏ thì độ lợi nó tăng lên. Tuy nhiên, để đơn giản và giảm thiêu không gian trạng thái, phần lớn các thư viện (bao gồm sklearn) chỉ cài đặt cây quyết định nhị phân thôi. Điều đó có nghĩa là mỗi node cha được chia thành hai node con, $D_{left}$ và $D_{right}$, tức là công thức ở trên trở thành: ![](https://latex.codecogs.com/gif.latex?IG%28D_%7Bp%7D%2C%20f%29%3DI%28D_%7Bp%7D%29%20-%20%5Cfrac%7BN_%7Bleft%7D%7D%7BN_%7Bp%7D%7DI%28D_%7Bleft%7D%29%20-%5Cfrac%7BN_%7Bright%7D%7D%7BN_%7Bp%7D%7DI%28D_%7Bright%7D%29) Ba loại độ đo dùng để đo độ tạp chất thường được sử dụng trong binary decision tree là **Gini impurity**($I_{G}$), **entropy**($I_{H}$) và **classification error** ($I_{E}$). Giờ ta bắt đầu với định nghĩa của **entropy** cho tất cả các **non-empty** classes (p(i|t) $\neq$ 0) - tức là xác suất để tồn tại một thực thể t khi có i là có tồn tại: ![](https://latex.codecogs.com/gif.latex?I_%7BH%7D%28t%29%20%3D%20-%20%5Csum%20p%28i%7Ct%29log_%7B2%7Dp%28i%7Ct%29) Ở đây, p(i|t) là tỉ lệ mẫu thuộc về class i đối với một node cụ thể cho trước t. Do đó cái Entropy bằng 0 nếu như tất cả các mẫu trong node đó cùng thuộc vào một mẫu class chung, và cực đại sẽ bẳng 1 nếu như ta có một uniform class distribution (xác suất của các class mà thuộc vào các lớp là chia đều cho nhau). Ví dụ, trong phân loại nhị phân, gía trị của entropy sẽ bằng 0 nêú như p(i=1|t) = 1 hoặc là p(i=0|t) = 0. Nếu như class được phân phối đều với p(i=1|t)=0.5 thì lúc đó entropy có giá trị là 1. Do đó, chúng ta có thể nói rằng tiêu chí entropy cố gắng tối đa hóa thông tin lẫn nhau trong cây.Độ đo tạp chất **Gini impurty** có thể được hiểu là một tiêu chí đánh giá để tối thiểu hóa xác suất phân loại sai (misclassification): ![](https://latex.codecogs.com/gif.latex?I_%7BG%7D%28t%29%3D%5Csum_%7Bi%3D1%7D%5E%7Bc%7Dp%28i%7Ct%29%281%20-%20p%28i%7Ct%29%29%20%3D%201%20-%20%5Csum_%7Bi%3D1%7D%5E%7Bc%7Dp%28i%7Ct%29%5E%7B2%7D) Tương tự như như entropy, Gini impurity nó đạt tối đa nếu như các class bị trộn hoàn hảo, ví dụ trong phân loại nhị phân (c = 2): ![](https://latex.codecogs.com/gif.latex?I_%7BG%7D%28t%29%3D%201%20-%20%5Csum_%7Bi%3D1%7D%5E%7B2%7D0.5%5E%7B2%7D%3D0.5) Tuy nhiên, trong thực tế, cả Gini impurity và entropy nó trả ra kết quả tương tự nhau, và đôi khi là không nên dành quá nhiều thời gian để đánh giá cây sử dụng các tiêu chí đánh giá độ đục khác nhau, thay vào đó là thực nghiệm với những thuật toán cắt tỉa.Một tiêu chí đo độ đục nữa là **classification error**: ![](https://latex.codecogs.com/gif.latex?I_%7BE%7D%28t%29%3D%201%20-%20max%28p%28i%7Ct%29%29) Đây là một tiêu chí đánh giá có ích nhưng không được khuyến khích dùng trong việc phát triển cây phân tích, bởi vì nó không có được linh hoạt khi thay đổi xác suất của các class trong mỗi node. Ta có thể minh họa điều này bằng cách xem xét 2 trường hợp phân chia class trong hình bên dưới:  ![](E.png) Ta bắt đầu với tập dataset $D_{p}$ ở node cha, gồm 40 mẫu thuộc lớp 1 và 40 mẫu thuộc lớp 2, ta bắt đầu chia chúng thành 2 lớp con, $D_{left}$ và $D_{right}$. Độ lợi thông tin mà chúng ta sử dụng classification error như là tiêu chí chia (splitting criterion) sẽ là như nhau ($IG_{E}$ = 0.25) trong cả 2 trường hợp A và B: ![](pr1.png) Tuy nhiên, chỉ số **Gini** sẽ ưu tiên dùng hơn vì nó tính ra được giá trị độ lợi thông tin trong trường hợp cách chia B($IG_{G}$ = 0.1666) so với lại A($IG_{G}$ = 0.125): ![](pr2.png) Tương tự đối với khi chúng ta sử dụng tiêu chí đánh giá là hàm **Entropy** trong trường hợp B ($IG_{H}$ = 0.31) so với kịch bản A ($IG_{J}$ = 0.19) ![](pr3.png) Để so sánh 3 loại độ đo tính trong suốt này, ta sẽ vẽ chỉ số impurty cho khoảng xác suất [0, 1] đối với class 1. Chú ý là ta bổ sung thêm phiên bản scaled của thằng entropy(entropy/2) để quan sát được thằng **Gini impurity** và phương thức đo trung bình giữa 2 thằng **entropy** và **classification error**. Code như phía bên dưới:<jupyter_code>import matplotlib.pyplot as plt
import numpy as np


def gini(p):
    return p * (1 - p) + (1 - p) * (1 - (1 - p))


def entropy(p):
    return - p*np.log2(p) - (1 - p)*np.log2((1 - p))


def error(p):
    return 1 - np.max([p, 1 - p])


x = np.arange(0.0, 1.0, 0.01)
ent = [entropy(p) if p != 0 else None for p in x]
sc_ent = [e * 0.5 if e else None for e in ent]
err = [error(i) for i in x]
fig = plt.figure()
ax = plt.subplot(111)
for i, lab, ls, c in zip([ent, sc_ent, gini(x), err], ['Entropy', 'Entropy(scaled)', 'Gini impurity', 'Missclassification'
                                                                                                      'error'],
                         ['-', '-', '--', '-.'],
                         ['black', 'lightgray', 'red', 'green', 'cyan']):
    line = ax.plot(x, i, label=lab, linestyle=ls, lw=2, color=c)

ax.legend(loc='upper center', bbox_to_anchor=(0.5, 1.15), ncol=5, fancybox=True, shadow=False)
ax.axhline(y=0.5, linewidth=1, color='k', linestyle='--')
ax.axhline(y=1.0, linewidth=1, color='k', linestyle='--')
plt.ylim([0, 1.1])
plt.xlabel('p(i=1)')
plt.ylabel('impurity index')
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11186037286790956, 'fraction_numerical': 0.04389792410419146, 'mean_word_length': 3.775252525252525, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '140792', 'license': 'MIT', 'n_tokens_mistral': 4263, 'n_tokens_neox': 4140, 'n_words': 1232, 'path': 'Chap3/Decision Tree .ipynb', 'repo_name': 'Nacriema/PythonMLAndDLBook', 'size': '7563'}