Hướng dẫn Phân loại Cây quyết định trong Python

Thuật toán Cây quyết định

Cây quyết định là một cấu trúc dạng cây giống sơ đồ luồng, trong đó một nút bên trong biểu diễn một đặc trưng (hoặc thuộc tính), nhánh biểu diễn một quy tắc quyết định, và mỗi nút lá biểu diễn một kết quả.

Nút trên cùng trong cây quyết định được gọi là nút gốc. Nó học cách phân hoạch dựa trên giá trị thuộc tính. Cây được phân hoạch theo cách đệ quy gọi là phân hoạch đệ quy. Cấu trúc giống sơ đồ luồng này giúp bạn đưa ra quyết định. Việc trực quan hóa như một sơ đồ luồng dễ dàng mô phỏng cách tư duy của con người. Đó là lý do cây quyết định dễ hiểu và dễ diễn giải.

Thuật toán cây quyết định. Hình: Abid Ali Awan

Cây quyết định là một loại thuật toán ML hộp trắng. Nó chia sẻ logic ra quyết định bên trong, điều mà không có ở các thuật toán kiểu hộp đen như mạng nơ-ron. Thời gian huấn luyện của nó nhanh hơn so với thuật toán mạng nơ-ron.

Độ phức tạp thời gian của cây quyết định là hàm của số lượng bản ghi và thuộc tính trong dữ liệu. Cây quyết định là phương pháp phi phân phối hay phi tham số, không phụ thuộc vào giả định về phân phối xác suất nền của dữ liệu. Cây quyết định có thể xử lý dữ liệu chiều cao với độ chính xác tốt.

Thuật toán Cây quyết định hoạt động như thế nào?

Ý tưởng cơ bản đằng sau bất kỳ thuật toán cây quyết định nào như sau:

1. Chọn thuộc tính tốt nhất bằng Thước đo Lựa chọn Thuộc tính (ASM) để tách các bản ghi.
2. Biến thuộc tính đó thành một nút quyết định và chia nhỏ tập dữ liệu thành các tập con nhỏ hơn.
3. Bắt đầu xây cây bằng cách lặp lại quy trình này một cách đệ quy cho mỗi nút con cho đến khi một trong các điều kiện khớp:
   • Tất cả bộ dữ liệu con thuộc cùng một giá trị thuộc tính.
   • Không còn thuộc tính nào nữa.
   • Không còn mẫu nào nữa.

Thước đo Lựa chọn Thuộc tính

Thước đo lựa chọn thuộc tính là một heuristic để chọn tiêu chí tách giúp phân hoạch dữ liệu theo cách tốt nhất có thể. Nó còn được gọi là quy tắc tách vì giúp xác định điểm ngắt cho các bộ dữ liệu tại một nút đã cho. ASM cung cấp xếp hạng cho từng đặc trưng (hoặc thuộc tính) bằng cách giải thích tập dữ liệu đã cho. Thuộc tính có điểm cao nhất sẽ được chọn làm thuộc tính tách. Với thuộc tính có giá trị liên tục, cần xác định cả các điểm tách cho nhánh. Các thước đo phổ biến nhất là Information Gain, Gain Ratio và Gini Index.

Information gain

Claude Shannon đã phát minh ra khái niệm entropy, đo độ nhiễu (impurity) của tập đầu vào. Trong vật lý và toán học, entropy được hiểu là độ ngẫu nhiên hay độ nhiễu trong một hệ. Trong lý thuyết thông tin, nó chỉ độ nhiễu trong một nhóm ví dụ. Information gain là mức giảm entropy. Information gain tính hiệu giữa entropy trước khi tách và entropy trung bình sau khi tách tập dữ liệu dựa trên các giá trị thuộc tính đã cho. Thuật toán cây quyết định ID3 (Iterative Dichotomiser) sử dụng information gain.

Trong đó Pi là xác suất một bộ dữ liệu bất kỳ trong D thuộc lớp Ci.

Trong đó:

• Info(D) là lượng thông tin trung bình cần để xác định nhãn lớp của một bộ dữ liệu trong D.

• |Dj|/|D| đóng vai trò là trọng số của phân hoạch thứ j.

• InfoA(D) là lượng thông tin kỳ vọng cần để phân loại một bộ dữ liệu từ D dựa trên việc phân hoạch theo A.

Thuộc tính A có information gain cao nhất, Gain(A), được chọn làm thuộc tính tách tại nút N().

Gain ratio

Information gain thiên lệch với những thuộc tính có nhiều kết quả. Nghĩa là nó ưu tiên thuộc tính có số lượng giá trị phân biệt lớn. Ví dụ, hãy xét một thuộc tính định danh duy nhất như customer_ID, có info(D) bằng 0 do phân hoạch thuần khiết. Điều này tối đa hóa information gain và tạo ra phân hoạch vô ích.

C4.5, một cải tiến của ID3, dùng phần mở rộng của information gain gọi là gain ratio. Gain ratio xử lý vấn đề thiên lệch bằng cách chuẩn hóa information gain thông qua Split Info. Triển khai bằng Java của thuật toán C4.5 được gọi là J48, có sẵn trong công cụ khai phá dữ liệu WEKA.

Trong đó:

• |Dj|/|D| đóng vai trò là trọng số của phân hoạch thứ j.
• v là số giá trị rời rạc trong thuộc tính A.

Gain ratio được định nghĩa là

Thuộc tính có gain ratio cao nhất được chọn làm thuộc tính tách (Nguồn).

Chỉ số Gini

Một thuật toán cây quyết định khác là CART (Classification and Regression Tree) sử dụng phương pháp Gini để tạo các điểm tách.

Trong đó pi là xác suất một bộ dữ liệu trong D thuộc lớp Ci.

Chỉ số Gini xem xét tách nhị phân cho mỗi thuộc tính. Bạn có thể tính tổng có trọng số của độ nhiễu của mỗi phân hoạch. Nếu một tách nhị phân trên thuộc tính A chia dữ liệu D thành D1 và D2, chỉ số Gini của D là:

Với thuộc tính có giá trị rời rạc, tập con cho chỉ số gini nhỏ nhất sẽ được chọn làm thuộc tính tách. Với thuộc tính có giá trị liên tục, chiến lược là chọn từng cặp giá trị kề nhau làm điểm tách có thể, và chọn điểm có chỉ số gini nhỏ hơn làm điểm tách.

Thuộc tính có chỉ số Gini nhỏ nhất được chọn làm thuộc tính tách.

Xây dựng Bộ phân loại Cây quyết định trong Scikit-learn

Nhập các thư viện cần thiết

Trước tiên, hãy tải các thư viện cần thiết.

# Load libraries
import pandas as pd
from sklearn.tree import DecisionTreeClassifier # Import Decision Tree Classifier
from sklearn.model_selection import train_test_split # Import train_test_split function
from sklearn import metrics #Import scikit-learn metrics module for accuracy calculation

Tải dữ liệu

Hãy tải bộ dữ liệu Pima Indian Diabetes cần thiết bằng hàm đọc CSV của pandas. Bạn có thể tải bộ dữ liệu trên Kaggle để làm theo.

col_names = ['pregnant', 'glucose', 'bp', 'skin', 'insulin', 'bmi', 'pedigree', 'age', 'label']
# load dataset
pima = pd.read_csv("diabetes.csv", header=None, names=col_names)

pima.head()

Chọn đặc trưng

Ở đây, bạn cần chia các cột đã cho thành hai loại biến: biến phụ thuộc (hoặc biến mục tiêu) và biến độc lập (hoặc biến đặc trưng).

#split dataset in features and target variable
feature_cols = ['pregnant', 'insulin', 'bmi', 'age','glucose','bp','pedigree']
X = pima[feature_cols] # Features
y = pima.label # Target variable

Chia tách dữ liệu

Để hiểu hiệu năng mô hình, chia tập dữ liệu thành tập huấn luyện và tập kiểm tra là một chiến lược tốt.

Hãy chia tập dữ liệu bằng hàm train_test_split(). Bạn cần truyền ba tham số: đặc trưng, mục tiêu và kích thước tập kiểm tra.

# Split dataset into training set and test set
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=1) # 70% training and 30% test

Xây dựng mô hình cây quyết định

Hãy tạo mô hình cây quyết định bằng Scikit-learn.

# Create Decision Tree classifer object
clf = DecisionTreeClassifier()

# Train Decision Tree Classifer
clf = clf.fit(X_train,y_train)

#Predict the response for test dataset
y_pred = clf.predict(X_test)

Đánh giá mô hình

Hãy ước lượng độ chính xác mà bộ phân loại hoặc mô hình có thể dự đoán loại giống cây trồng.

Độ chính xác có thể được tính bằng cách so sánh giá trị thực của tập kiểm tra và giá trị dự đoán.

# Model Accuracy, how often is the classifier correct?
print("Accuracy:",metrics.accuracy_score(y_test, y_pred))

Accuracy: 0.6753246753246753

Chúng ta đạt tỷ lệ phân loại 67,53%, được xem là độ chính xác tốt. Bạn có thể cải thiện độ chính xác này bằng cách tinh chỉnh các tham số trong thuật toán cây quyết định.

Trực quan hóa Cây quyết định

Bạn có thể dùng hàm export_graphviz() của Scikit-learn để hiển thị cây trong Jupyter notebook. Để vẽ cây, bạn cũng cần cài đặt graphviz và pydotplus.

pip install graphviz
pip install pydotplus

Hàm export_graphviz() chuyển bộ phân loại cây quyết định thành tệp dot, và pydotplus chuyển tệp dot này sang PNG hoặc dạng có thể hiển thị trên Jupyter.

from sklearn.tree import export_graphviz
from sklearn.externals.six import StringIO  
from IPython.display import Image  
import pydotplus

dot_data = StringIO()
export_graphviz(clf, out_file=dot_data,  
                filled=True, rounded=True,
                special_characters=True,feature_names = feature_cols,class_names=['0','1'])
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())  
graph.write_png('diabetes.png')
Image(graph.create_png())

Trong biểu đồ cây quyết định, mỗi nút bên trong có một quy tắc quyết định để tách dữ liệu. Gini, còn gọi là tỷ lệ Gini, đo độ nhiễu của nút. Bạn có thể coi một nút là thuần khi tất cả bản ghi của nó thuộc cùng một lớp; các nút như vậy được gọi là nút lá.

Ở đây, cây kết quả chưa được cắt tỉa. Cây chưa cắt tỉa này khó giải thích và không dễ hiểu. Ở phần tiếp theo, hãy tối ưu nó bằng cách cắt tỉa.

Tối ưu hiệu năng Cây quyết định

• criterion: tùy chọn (mặc định=”gini”) hoặc Chọn thước đo lựa chọn thuộc tính. Tham số này cho phép chúng ta dùng các thước đo lựa chọn thuộc tính khác nhau. Các tiêu chí được hỗ trợ là “gini” cho chỉ số Gini và “entropy” cho information gain.

• splitter: chuỗi, tùy chọn (mặc định=”best”) hoặc Chiến lược tách. Tham số này cho phép chọn chiến lược tách. Các chiến lược hỗ trợ gồm “best” để chọn tách tốt nhất và “random” để chọn tách ngẫu nhiên tốt nhất.

• max_depth: int hoặc None, tùy chọn (mặc định=None) hoặc Độ sâu tối đa của cây. Độ sâu tối đa của cây. Nếu None, các nút sẽ được mở rộng cho đến khi tất cả lá chứa ít hơn min_samples_split mẫu. Giá trị độ sâu tối đa cao gây quá khớp, còn giá trị thấp gây thiếu khớp (Nguồn).

Trong Scikit-learn, tối ưu bộ phân loại cây quyết định được thực hiện chỉ bằng tiền cắt tỉa (pre-pruning). Độ sâu tối đa của cây có thể dùng làm biến kiểm soát cho tiền cắt tỉa. Ở ví dụ sau, bạn có thể vẽ một cây quyết định trên cùng dữ liệu với max_depth=3. Ngoài các tham số tiền cắt tỉa, bạn cũng có thể thử thước đo lựa chọn thuộc tính khác như entropy.

# Create Decision Tree classifer object
clf = DecisionTreeClassifier(criterion="entropy", max_depth=3)

# Train Decision Tree Classifer
clf = clf.fit(X_train,y_train)

#Predict the response for test dataset
y_pred = clf.predict(X_test)

# Model Accuracy, how often is the classifier correct?
print("Accuracy:",metrics.accuracy_score(y_test, y_pred))
Accuracy: 0.7705627705627706

Tốt, tỷ lệ phân loại tăng lên 77,05%, chính xác hơn mô hình trước.

Hãy làm cho cây quyết định của chúng ta dễ hiểu hơn một chút bằng đoạn mã sau: 

from six import StringIO
from IPython.display import Image
from sklearn.tree import export_graphviz
import pydotplus

dot_data = StringIO()
export_graphviz(clf, out_file=dot_data, 
                filled=True, 
                rounded=True, 
                special_characters=True, 
                feature_names=feature_cols,
                class_names=['0','1'])

graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
graph.write_png('diabetes.png')
Image(graph.create_png())

Ở đây, chúng ta đã hoàn thành các bước sau: 

• Nhập các thư viện cần thiết.

• Tạo một đối tượng StringIO tên là dot_data để chứa biểu diễn dạng văn bản của cây quyết định.

• Xuất cây quyết định sang định dạng dot bằng hàm export_graphviz và ghi đầu ra vào bộ đệm dot_data.

• Tạo một đối tượng đồ thị pydotplus từ biểu diễn định dạng dot của cây quyết định được lưu trong bộ đệm dot_data.

• Ghi đồ thị được tạo ra thành tệp PNG tên "diabetes.png".

• Hiển thị ảnh PNG của cây quyết định bằng đối tượng Image từ mô-đun IPython.display.

Như bạn thấy, mô hình đã được cắt tỉa này ít phức tạp hơn, dễ giải thích và dễ hiểu hơn so với biểu đồ cây quyết định trước đó.

Ưu và nhược điểm của Cây quyết định

Giờ bạn đã xây dựng và tối ưu một bộ phân loại cây quyết định, hãy tạm dừng để đánh giá một số điểm mạnh và hạn chế của thuật toán nói chung. Hiểu các đánh đổi giúp bạn quyết định khi nào cây quyết định là lựa chọn phù hợp.

Lưu ý rằng một số nhược điểm, như bất ổn phương sai, có thể được giảm nhẹ thông qua các phương pháp tổ hợp như bagging và boosting.

Cây quyết định so với Decision Stump

Trong khi suốt hướng dẫn này chúng ta làm việc với các cây quyết định đầy đủ, cũng đáng để hiểu một biến thể đơn giản hơn gọi là decision stump. Decision stump về bản chất là một cây quyết định có độ sâu tối đa bằng một — nghĩa là chỉ có một lần tách tại nút gốc và hai nút lá.

Decision stump hiếm khi được dùng như bộ phân loại độc lập do sự đơn giản của nó. Nhưng chúng có thể đóng vai trò trong các phương pháp tổ hợp, đặc biệt AdaBoost dùng decision stump làm bộ học yếu được kết hợp để tạo bộ phân loại mạnh, hoặc gradient boosting vì stump có thể được dùng làm bộ học cơ sở trong quá trình boosting.

Bạn có thể tạo một decision stump trong Scikit-learn chỉ bằng cách đặt max_depth=1:

# Create a Decision Stump
stump = DecisionTreeClassifier(max_depth=1)
stump = stump.fit(X_train, y_train)

Kết luận

Chúc mừng bạn đã đi đến cuối hướng dẫn này!

Trong hướng dẫn này, bạn đã tìm hiểu nhiều chi tiết về cây quyết định: cách chúng hoạt động, các thước đo lựa chọn thuộc tính như Information Gain, Gain Ratio và Gini Index, xây dựng mô hình cây quyết định, trực quan hóa và đánh giá trên bộ dữ liệu tiểu đường bằng gói Scikit-learn của Python. Chúng ta cũng đã thảo luận ưu, nhược điểm và cách tối ưu hiệu năng cây quyết định bằng tinh chỉnh tham số.

Hy vọng giờ đây bạn có thể sử dụng thuật toán cây quyết định để phân tích các bộ dữ liệu của riêng mình.

Nếu bạn muốn tìm hiểu thêm về Machine Learning trong Python, hãy tham khảo khóa học Machine Learning với các mô hình dựa trên cây trong Python. Ngoài ra, xem thêm Hướng dẫn Kaggle: Mô hình Machine Learning đầu tiên của bạn.