Machine Learning - Thuật toán Decision Tree CART

Machine Learning Decision Tree CART là gì ?

Thuật toán Machine Learning Decision Tree CART (Classification And Regression Tree) là thuật toán phân loại và hồi quy hay còn gọi là thuật toán cây quyết định trong Machine Learning. Thuật toán Decision Tree CART thuộc loại thuật toán học có giám sát (Supervised Learning).Nó được dùng cho cả bài toán về phân loại (Classification) và hồi quy (Regression).

Thuật toán Decision Tree CART có sơ đồ giống như cấu trúc cây để hiển thị các dự đoán là kết quả của một loạt các phân tích dự đoán trên đặc tính.Nó bắt đầu với một nút gốc và kết thúc bằng một quyết định của các nút lá.

Thuật toán Decision Tree CART là một cây nhị phân được xây dựng bằng cách tách nút thành 2 nút con và lặp đi lặp lại.

Cây quyết định Decision Tree là gì?

Chúng ta có thể hiểu cây quyết định một cách đơn giản là một đồ thị có hình dạng giống như cây và nó có hướng được sử dụng để cho việc ra quyết định. Ví dụ bạn cần đưa ra quyết định của mình có nên đi chơi hay không khi phụ thuộc vào các yếu tố như thời tiết, nhiệt độ, đổ ẩm, gió…

Các thuật toán cây quyết định Decision Tree:

Có các thuật toán cây quyết định (Decision Tree) như: ID3, C4.5, CART, CHAID, và Regression Trees.

Các thuật toán phân loại (Classification algorithm):

Có nhiều thuật toán phân loại như: Decistion Tree, Random Forest, Naive Bayes, KNN, Logistic Regression, SVM.Thuật toán Decision Tree CART là thuộc thuật toán phân loại (Classification algorithm).

Các khái niệm và thuật ngữ trong thuật toán cây quyết định Decision Tree:

Root Node (Nút gốc): Là nút bắt đầu của cây quyết định, từ nút này bắt đầu phân chia theo các đặc tính khác nhau.

Parent Node (Nút cha): Là nút mà có các nút con bên dưới.

Child Node (Nút con): Là nút mà có nút cha.

Decision Nodes (Nút quyết định): Là các nút mà chúng ta nhận được sau khi chia tách nút.

Leaf Nodes (Nút lá): Là các nút mà không thể chia tách thêm được, nút này còn gọi là nút cuối.

Sub-tree (Cây con): Là một phần nhỏ của đồ thị, nó tương tự như một phần con của cây quyết định Decision Tree.

Pruning (Cắt tỉa): Không có gì thay đổi hay ảnh hưởng khi chúng ta cắt giảm một số nút để không bị overfitting.

Gini index : Chỉ số Gini dùng để xác định mức độ phân tách của cây quyết định.Nó là một chỉ số dùng để đo và đánh giá việc phân chia ở node điều kiện có tốt hay không.Nó dùng để tính độ lệch Gini của nốt cha với tổng các giá trị Gini có đánh trọng số của các node con.

Công thức tính chỉ số Gini :

Làm thế nào để xây dựng một cây quyết định?

Để xây dựng cây quyết định chúng ta cần phải tính chỉ số Gini cho mỗi đặc tính.

Bây giờ chúng ta sẽ đi tìm hiểu về thuật toán Decision Tree CART bằng ví dụ cụ thể sau đây.

Giả sử chúng ta có tập dữ liệu trong file Weather_dataset-data.csv như sau:

Day	Outlook	Temperature	Humidity	Wind	Go-Play
1	Sunny	Hot	High	Weak	No
2	Sunny	Hot	High	Strong	No
3	Overcast	Hot	High	Weak	Yes
4	Rain	Mild	High	Weak	Yes
5	Rain	Cool	Normal	Weak	Yes
6	Rain	Cool	Normal	Strong	No
7	Overcast	Cool	Normal	Strong	Yes
8	Sunny	Mild	High	Weak	No
9	Sunny	Cool	Normal	Weak	Yes
10	Rain	Mild	Normal	Weak	Yes
11	Sunny	Mild	Normal	Strong	Yes
12	Overcast	Mild	High	Strong	Yes
13	Overcast	Hot	Normal	Weak	Yes
14	Rain	Mild	High	Strong	No

Như các bạn có thể thấy danh sách tập dữ liệu trên có các đặc tính: Outlook (thời tiết), Temperature(Nhiệt độ), Humidity (Độ ẩm), Wind(Gió).

Yêu cầu bài toán là hãy dự đoán quyết định đi chơi hay không dựa vào các đặc tính thời tiết.

Để giải quyết cho bài toán này chúng ta cần xây dựng cây quyết định Decision Tree.

Sử dụng hàm DecisionTreeClassifier trong thư viện sklearn để tạo cây quyết định Decision Tree.

Xây dựng cây quyết định Decision Tree sử dụng thư viện sklearn trong python.

Ví dụ

import pandas
from sklearn import tree
from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt

#Load dữ liệu từ file csv
df = pandas.read_csv("Weather_dataset-data.csv")

#Chuyển đổi kiểu dữ liệu sang kiểu số
d = {'Sunny': 0, 'Overcast': 1, 'Rain': 2}
df['Outlook'] = df['Outlook'].map(d)

d= {'Hot': 0,'Mild': 1,'Cool': 2}
df['Temperature'] = df['Temperature'].map(d)

d= {'High': 0,'Normal': 1}
df['Humidity'] = df['Humidity'].map(d)

d= {'Weak': 0,'Strong': 1}
df['Wind'] = df['Wind'].map(d)

d = {'Yes': 1, 'No': 0}
df['Go-Play'] = df['Go-Play'].map(d)

#Các đặc tính, đối tượng
features = ['Outlook', 'Temperature', 'Humidity', 'Wind']

X = df[features]
y = df['Go-Play']

#Tạo cây quyết định Decistion Tree
dtree = DecisionTreeClassifier()
dtree = dtree.fit(X, y)

#Vẽ cây quyết định Decision Tree
tree.plot_tree(dtree, feature_names=features)
plt.show()