Cây quyết định được giải thích

May 08 2022
Trong bài đăng này, chúng ta sẽ thảo luận về một mô hình học máy thường được sử dụng được gọi là cây quyết định. Cây quyết định được ưa thích cho nhiều ứng dụng, chủ yếu là do khả năng giải thích cao, nhưng cũng do việc thiết lập và huấn luyện tương đối đơn giản và thời gian thực hiện dự đoán với cây quyết định khá ngắn.

Trong bài đăng này, chúng ta sẽ thảo luận về một mô hình học máy thường được sử dụng được gọi là cây quyết định . Cây quyết định được ưa thích cho nhiều ứng dụng, chủ yếu là do khả năng giải thích cao, nhưng cũng do việc thiết lập và huấn luyện tương đối đơn giản và thời gian thực hiện dự đoán với cây quyết định khá ngắn. Cây quyết định là tự nhiên đối với dữ liệu dạng bảng và trên thực tế, chúng hiện dường như hoạt động tốt hơn mạng nơ-ron về loại dữ liệu đó (trái ngược với hình ảnh). Không giống như mạng nơ-ron, cây không yêu cầu chuẩn hóa đầu vào, vì quá trình đào tạo của chúng không dựa trên gốc gradient và chúng có rất ít tham số để tối ưu hóa. Họ thậm chí có thể đào tạo trên dữ liệu có giá trị bị thiếu, nhưng ngày nay phương pháp này ít được khuyến khích hơn và các giá trị bị thiếu thường được áp dụng.

Trong số các trường hợp sử dụng nổi tiếng cho cây quyết định là hệ thống đề xuất (tùy chọn phim được dự đoán của bạn là gì dựa trên các lựa chọn trước đây của bạn và các tính năng khác, ví dụ: tuổi, giới tính, v.v.) và công cụ tìm kiếm.

Quá trình dự đoán trong cây bao gồm một chuỗi so sánh các thuộc tính (tính năng) của mẫu với các giá trị ngưỡng đã học trước. Bắt đầu từ ngọn (gốc của cây) và đi xuống (về phía lá, vâng, đối diện với cây ngoài đời), trong mỗi bước, kết quả của phép so sánh sẽ xác định xem mẫu đi sang trái hay phải trên cây, và bằng cách đó - xác định bước so sánh tiếp theo. Khi mẫu của chúng ta đạt đến một lá (một nút kết thúc) - quyết định, hoặc dự đoán, được đưa ra, dựa trên lớp đa số trong lá.

Hình 1 cho thấy quá trình này với vấn đề phân loại các mẫu Iris thành 3 loài (lớp) khác nhau dựa trên chiều dài và chiều rộng của cánh hoa và đài hoa.

Ví dụ của chúng tôi sẽ dựa trên bộ dữ liệu Iris nổi tiếng (Fisher, RA “Việc sử dụng nhiều phép đo trong các vấn đề phân loại” Hàng năm về Ưu sinh, 7, Phần II, 179–188 (1936)). Tôi đã sửa đổi các tính năng của một trong các lớp và giảm kích thước tập hợp tàu, để trộn các lớp một chút và làm cho nó thú vị hơn.

Hình 1 Một cây quyết định được đào tạo trên một tập hợp tàu đã sửa đổi của tập dữ liệu Iris.

Chúng ta sẽ tìm hiểu chi tiết về cây này sau. Bây giờ, chúng tôi sẽ kiểm tra nút gốc và nhận thấy rằng tập hợp đào tạo của chúng tôi có 45 mẫu, được chia thành 3 lớp như sau: [13, 19, 13]. Thuộc tính 'class' cho chúng ta biết nhãn mà cây sẽ dự đoán cho mẫu này nếu nó là một lá - dựa trên lớp đa số trong nút. Ví dụ: nếu chúng tôi không được phép chạy bất kỳ phép so sánh nào, chúng tôi sẽ ở trong nút gốc và dự đoán tốt nhất của chúng tôi sẽ là lớp Veriscolor, vì nó có 19 mẫu trong tập huấn luyện, so với 13 mẫu cho hai lớp còn lại. Nếu chuỗi so sánh của chúng ta dẫn chúng ta đến chiếc lá thứ hai từ trái sang, thì dự đoán của mô hình, một lần nữa, sẽ là Veriscolor, vì trong tập huấn luyện có 4 mẫu của lớp đó đạt đến lá này, so với chỉ 1 mẫu của lớp Virginica và không có mẫu của lớp Setosa.

Cây quyết định có thể được sử dụng cho các bài toán phân loại hoặc hồi quy. Hãy bắt đầu bằng cách thảo luận về vấn đề phân loại và giải thích cách hoạt động của thuật toán đào tạo cây.

Việc thực hành:

Hãy xem cách chúng ta đào tạo một cây bằng sklearn và sau đó thảo luận về cơ chế.

Tải xuống tập dữ liệu:

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import OneHotEncoder
iris = load_iris()
X = iris['data']
y = iris['target']
names = iris['target_names']
feature_names = iris['feature_names']
# One hot encoding
enc = OneHotEncoder()
Y = enc.fit_transform(y[:, np.newaxis]).toarray()
# Modifying the dataset
X[y==1,2] = X[y==1,2] + 0.3
# Split the data set into training and testing
X_train, X_test, Y_train, Y_test = train_test_split(
    X, Y, test_size=0.5, random_state=2)
# Decreasing the train set to make things more interesting
X_train = X_train[30:,:]
Y_train = Y_train[30:,:]

# Visualize the data sets
import matplotlib
import matplotlib.pyplot as plt
plt.figure(figsize=(16, 6))
plt.subplot(1, 2, 1)
for target, target_name in enumerate(names):
    X_plot = X[y == target]
    plt.plot(X_plot[:, 0], X_plot[:, 1], linestyle='none', marker='o', label=target_name)
plt.xlabel(feature_names[0])
plt.ylabel(feature_names[1])
plt.axis('equal')
plt.legend();
plt.subplot(1, 2, 2)
for target, target_name in enumerate(names):
    X_plot = X[y == target]
    plt.plot(X_plot[:, 2], X_plot[:, 3], linestyle='none', marker='o', label=target_name)
plt.xlabel(feature_names[2])
plt.ylabel(feature_names[3])
plt.axis('equal')
plt.legend();

      
                
Fig.2 Visualization of the modified Iris dataset.

plt.figure(figsize=(16, 6))
plt.subplot(1, 2, 1)
for target, target_name in enumerate(names):
    X_plot = X_train[Y_train[:,target] == 1]
    plt.plot(X_plot[:, 0], X_plot[:, 1], linestyle='none', marker='o', label=target_name)
plt.xlabel(feature_names[0])
plt.ylabel(feature_names[1])
plt.axis('equal')
plt.legend();
plt.subplot(1, 2, 2)
for target, target_name in enumerate(names):
    X_plot = X_train[Y_train[:,target] == 1]
    plt.plot(X_plot[:, 2], X_plot[:, 3], linestyle='none', marker='o', label=target_name)
plt.xlabel(feature_names[2])
plt.ylabel(feature_names[3])
plt.axis('equal')
plt.legend();

      
                
Fig.3 — Just the (reduced) train set.

from sklearn import tree
import graphviz
iristree = tree.DecisionTreeClassifier(max_depth=3, criterion='gini', random_state=0)
iristree.fit(X_train, enc.inverse_transform(Y_train))
feature_names = ['sepal length', 'sepal width', 'petal length', 'petal width']
dot_data = tree.export_graphviz(iristree, out_file=None, 
                      feature_names=feature_names,  
                      class_names=names,
                      filled=True, rounded=True,  
                      special_characters=True)  
graph = graphviz.Source(dot_data)
display(graph)

Hãy xem độ chính xác phân loại của mô hình này trên bộ xe lửa, tiếp theo là bộ thử nghiệm:

from sklearn.metrics import precision_score
from sklearn.metrics import recall_score
iristrainpred = iristree.predict(X_train)
iristestpred = iristree.predict(X_test)
# train precision:
display(precision_score(enc.inverse_transform(Y_train), iristrainpred.reshape(-1,1), average='micro', labels=[0]))
display(precision_score(enc.inverse_transform(Y_train), iristrainpred.reshape(-1,1), average='micro', labels=[1]))
display(precision_score(enc.inverse_transform(Y_train), iristrainpred.reshape(-1,1), average='micro', labels=[2]))
>>> 1.0
>>> 0.9047619047619048
>>> 1.0
# test precision:
display(precision_score(enc.inverse_transform(Y_test), iristestpred.reshape(-1,1), average='micro', labels=[0]))
display(precision_score(enc.inverse_transform(Y_test), iristestpred.reshape(-1,1), average='micro', labels=[1]))
display(precision_score(enc.inverse_transform(Y_test), iristestpred.reshape(-1,1), average='micro', labels=[2]))
>>> 1.0
>>> 0.7586206896551724
>>> 0.9473684210526315

Và bây giờ đến lý thuyết - làm thế nào để một cái cây đào tạo?

Nói cách khác - nó chọn các tính năng và ngưỡng tối ưu để đưa vào mỗi nút như thế nào?

Tạp chất Gini

Giống như trong các mô hình học máy khác, cơ chế đào tạo cây quyết định cố gắng giảm thiểu một số tổn thất do lỗi dự đoán trên tập đoàn tàu gây ra. Chỉ số tạp chất Gini (theo tên nhà thống kê người Ý Corrado Gini ) là một thước đo tự nhiên cho độ chính xác của phân loại.

Hình 4 - Hai mục tiêu đào tạo phổ biến cho cây: Gini và entropy. P (ci) là xác suất để chọn ngẫu nhiên một mẫu ci loại trong tổng thể. n là số lớp.

Gini cao tương ứng với một quần thể không đồng nhất (lượng mẫu tương tự từ mỗi lớp) trong khi Gini thấp chỉ ra một quần thể đồng nhất (tức là nó bao gồm chủ yếu từ một lớp duy nhất)

Giá trị Gini tối đa có thể có phụ thuộc vào số lớp: trong một bài toán phân loại với các lớp C, giá trị Gini tối đa có thể là 1–1 / C (khi các lớp có dân số đồng đều). Gini tối thiểu là 0 và nó đạt được khi toàn bộ quần thể được bao gồm một lớp duy nhất.

Chỉ số tạp chất Gini đo xác suất lỗi phân loại nếu việc phân loại được thực hiện một cách ngẫu nhiên.

Tại sao?

Vì xác suất để chọn ngẫu nhiên một mẫu từ lớp ci là p (ci) . Sau khi chọn điều đó, xác suất để dự đoán sai lớp là (1-p (ci)) . Nếu chúng ta tính tổng p (ci) * (1-p (ci)) trên tất cả các lớp, chúng ta sẽ nhận được công thức cho tạp chất Gini trong Hình 4.

Với chỉ số Gini làm mục tiêu, cây chọn trong mỗi bước đặc điểm và ngưỡng phân chia quần thể theo cách làm giảm tối đa Gini trung bình có trọng số của hai quần thể kết quả (hoặc tăng tối đa tính đồng nhất trung bình có trọng số của chúng). Nói cách khác, lôgic đào tạo là giảm thiểu xác suất sai sót khi phân loại ngẫu nhiên trong hai quần thể kết quả, với trọng số càng nhiều thì quần thể con càng lớn.

Và có - cơ chế xem xét tất cả các giá trị mẫu và chia chúng theo tiêu chí để kiểm tra Gini kết quả.

Từ định nghĩa này, chúng ta cũng có thể hiểu tại sao các giá trị ngưỡng luôn là giá trị thực tế được tìm thấy trên ít nhất một trong các mẫu tàu - không có lợi khi sử dụng một giá trị nằm trong khoảng cách giữa các mẫu vì sự phân tách kết quả sẽ giống hệt nhau.

Một số liệu khác thường được sử dụng để huấn luyện cây là entropy (xem công thức trong Hình 4).

Sự hỗn loạn

Trong khi chiến lược Gini nhằm mục đích giảm thiểu lỗi phân loại ngẫu nhiên trong bước tiếp theo, thì chiến lược tối thiểu hóa entropy nhằm mục đích tối đa hóa mức thu được thông tin .

Thu được thông tin

Nếu không có kiến ​​thức trước về cách một dân số được chia thành 10 lớp, chúng tôi giả định rằng nó được chia đều cho chúng. Trong trường hợp này, chúng ta cần trung bình 3,3 câu hỏi có / không để tìm ra phân loại của một mẫu (bạn có phải là lớp 1–5 không? Nếu không - bạn có phải là lớp 6–10 không? V.v.). Điều này có nghĩa là entropy của tổng thể là 3,3 bit.

nhưng bây giờ hãy giả sử rằng chúng tôi đã làm điều gì đó (giống như một sự phân chia thông minh) để cung cấp cho chúng tôi thông tin về sự phân bố dân số và bây giờ chúng tôi biết rằng 50% số mẫu ở loại 1, 25% ở loại 2 và 25% số mẫu ở lớp 3. Trong trường hợp này entropy của tổng thể sẽ là 1,5 - chúng ta chỉ cần 1,5 bit để mô tả một mẫu ngẫu nhiên. (Câu hỏi đầu tiên - bạn có phải là lớp 1 không? Trình tự sẽ kết thúc ở đây 50% thời gian. Câu hỏi thứ hai - bạn có phải là lớp 2 không? Và không cần câu hỏi nào nữa - vì vậy trung bình 50% * 1 + 50% * 2 = 1,5 câu hỏi ). Thông tin mà chúng tôi thu được có giá trị 1,8 bit.

Giống như Gini, giảm thiểu entropi cũng phù hợp với việc tạo ra một quần thể đồng nhất hơn, vì các quần thể đồng nhất có entropy thấp hơn (với cực điểm của quần thể một lớp có entropy 0 - không cần hỏi bất kỳ câu hỏi có / không).

Gini hay Entropy?

Hầu hết các nguồn đều khẳng định rằng sự khác biệt giữa hai chiến lược là không đáng kể (thực sự - nếu bạn cố gắng đào tạo một cây entropy về vấn đề chúng tôi vừa giải quyết - bạn sẽ nhận được chính xác các phân chia giống nhau). Thật dễ hiểu tại sao: trong khi Gini tối đa hóa giá trị kỳ vọng của xác suất lớp, thì entropy tối đa hóa giá trị kỳ vọng của xác suất lớp log. Nhưng xác suất log là một hàm tăng đơn điệu của xác suất, vì vậy chúng thường hoạt động khá giống nhau. Tuy nhiên, quá trình tối thiểu hóa entropi có thể chọn một cấu hình khác với Gini, khi quần thể mất cân bằng cao . Ví dụ: trong tập dữ liệu Hacide trong ROSE(Ví dụ về lấy mẫu quá mức ngẫu nhiên, Lunadron et al. 2021) có 1000 mẫu đào tạo - 980 thuộc về lớp 0 và 20 đến lớp 1. Giả sử cây có thể chọn ngưỡng sẽ phân tách nó theo ví dụ a hoặc ví dụ b trong Hình 5. Chúng tôi lưu ý rằng cả hai ví dụ đều tạo ra một nút có dân số lớn bao gồm chủ yếu là tầng lớp đa số và nút thứ hai có dân số nhỏ bao gồm chủ yếu là tầng lớp thiểu số.

Trong trường hợp như vậy, độ dốc của hàm log ở các giá trị nhỏ sẽ thúc đẩy tiêu chí entropy thanh lọc nút có dân số lớn, mạnh hơn tiêu chí Gini. Vì vậy, nếu chúng ta tính toán, chúng ta sẽ thấy rằng tiêu chí Gini sẽ chọn phân tách a , và tiêu chí entropy sẽ chọn phân tách b .

Điều này có thể dẫn đến sự lựa chọn khác về tính năng / ngưỡng. Không nhất thiết phải tốt hơn hay tệ hơn - điều này phụ thuộc vào mục tiêu của chúng ta.

Hình 5 Có thể có hai phần tách dữ liệu không cân bằng cao (ví dụ từ bộ dữ liệu Hacide, ROSE).

Lưu ý rằng ngay cả trong các vấn đề với các quần thể cân bằng ban đầu, các nút thấp hơn của cây phân loại thường sẽ có các quần thể không cân bằng cao.

Kết thúc khóa đào tạo

Khi một đường dẫn trong cây đạt đến giá trị độ sâu được chỉ định hoặc khi nó chứa tổng thể Gini / entropy bằng không, nó sẽ ngừng đào tạo. Khi tất cả các con đường ngừng đào tạo, cây đã sẵn sàng.

Một thực tế phổ biến là hạn chế độ sâu của cây. Một cách khác là hạn chế số lượng mẫu trong một lá (không cho phép số lượng mẫu ít hơn một ngưỡng). Cả hai phương pháp này đều được thực hiện để ngăn chặn việc trang bị quá nhiều trên xe lửa.

Cây hồi quy

Bây giờ chúng ta đã tìm hiểu chi tiết về việc huấn luyện cây phân loại, sẽ rất đơn giản để hiểu cây hồi quy: Các nhãn trong bài toán hồi quy là liên tục chứ không rời rạc (ví dụ: hiệu quả của một liều thuốc nhất định, được đo bằng% các trường hợp). Đào tạo về loại vấn đề này, cây hồi quy cũng phân loại, nhưng các nhãn được tính toán động như giá trị trung bình của các mẫu trong mỗi nút. Ở đây, người ta thường sử dụng sai số bình phương trung bình hoặc số đo Chi bình phương làm mục tiêu để tối thiểu hóa, thay vì Gini và entropy.

© Copyright 2021 - 2022 | vngogo.com | All Rights Reserved