فرادرس
درخت های مدل (Model Trees) — راهنمای کاربردی
«درخت تصمیم» (Decision Tree) ابزار قدرتمندی برای «یادگیری نظارت شده» (Supervised Learning) در «یادگیری ماشین» (Machine Learning) است. از این ابزار برای تقسیم داده‌ها در «جزیره‌های» مجزا به صورت بازگشتی (با تقسیم ویژگی‌ها) استفاده می‌شود. هدف از این کار، کاهش «زیان وزنی کلی» (Overall Weighted Loss) از «برازش» (Fit) روی «مجموعه آموزش» (Training Set) است. آنچه به طور متداول در «دسته‌بندی» (Classification) درخت تصمیم مورد استفاده قرار می‌گیرد، «دسته‌بند مدل» (Modal Classifier) با «زیان اندیس جینی» (Gini Index Loss) و همچنین، «بازگشت به میانگین» (Mean Regression) با زیان L2 برای رگرسیون درخت تصمیم است. نکته دیگری که باید به آن توجه کرد این است که درخت تصمیم در اصل می‌تواند هر مدلی را، شامل «رگرسیون خطی» (Linear Regression)، «رگرسیون لوجستیک» (Logistic Regression) و «شبکه‌های عصبی» (Neural Networks) در طول روال تقسیم بگیرد. هدف از این مطلب، معرفی مبحثی عمومی‌تر از درخت تصمیم است که «درخت های مدل» (Model Trees) نامیده می‌شود و امکان ساخت درخت تصمیم را از هر مدل انتخابی فراهم می‌کند (به جای داشتن رویکرد CART استاندارد).
در تصویر بالا، شماتیک استفاده از یک مدل درخت رگرسیون خطی برای «برازش» (Fit) مجموعه آموزش یک‌بُعدی به منظور پیدا کردن بخش‌هایی از مجموعه آموزش که با یک خط راست به خوبی برازش می‌شوند، ارائه شده است. در ادامه و پیش از عمیق‌تر شدن در این بحث که چرا درخت‌های مدل مفید وحائز اهمیت هستند، کد کامل پیاده‌سازی درخت‌های مدل ارائه می‌شود.
ساخت درخت های مدل
در الگوریتم CART (درخت دسته‌بندی و رگرسیون)، یک درخت با تقسیم‌بندی بازگشتی داده‌های آموزش ساخته می‌شود. در مدل مذکور، آستانه‌های برش ویژگی در نظر گرفته می‌شوند که از این جمله می‌توان به این مورد اشاره کرد که تقسیم داده‌ها موجب کاهش زیان وزنی کلی تا حد امکان شود. با تخصیص یک تابع زیان به مدل رگرسیون/دسته‌بندی، به هر یک از «گره‌های» (Nodes) درخت، یک مدل تخصیص داده می‌شود که مفهوم درخت‌های مدل را ایجاد می‌کند. پیاده‌سازی آن در ادامه انجام شده است.
برای بصری‌سازی سریع چگونگی آنکه یک مدل می‌تواند اثبات کند که از درخت CART متداول مفیدتر است، می‌توان مجموعه داده آموزش یک‌بُعدی ارائه شده در زیر را در نظر گرفت که تلاش می‌شود یک مدل رگرسیون خطی برای آن برازش داده شود (این دقیقا درخت مدل با عمق مساوی سفر یا همان depth=0 است). برازش، همانطور که انتظار می‌رفت ضعیف است، زیرا داده آموزش از یک چندجمله‌ای مرتبه چهارم تولید شده است، اما اگر تقسیم داده‌ها به بخش x را در نظر بگیرید که با افزایش عمق درخت مدل رگرسیون خطی انجام می‌شود، می‌توان یک مجموعه از رگرسورهای خطی را ساخت که به درستی بخش‌های مجزا را برازش می‌کنند (depth=1, 2, 3, 4, 5). بنابراین، یک مدل به خوبی آموزش دیده، بدون نیاز به دانش صریح زیاد از پیچیدگی اساسی توزیع داده‌های آموزش ارائه می‌شود.
همچنین، می‌توان نتایج حاصل از برازش مجموعه یک‌بُعدی آموزش با استفاده از مدل درخت رگرسیون را با رگرسور درخت تصمیم پیش‌فرض کتابخانه «سایکیت‌لِرن» (Scikit Learn) که از بازگشت به میانگین استفاده می‌کند، مقایسه کرد. در نمودار زیر، می‌توان به خوبی مشاهده کرد که رگرسور درخت تصمیم درخت تصمیم در depth=5 هنوز یک مدل خوب نیست، زیرا در تقلا برای ثبت تغییرپذیری X در داده‌ها است. این در حالی است که درخت مدل هم‌اکنون قادر به ثبت بخش زیادی از توزیع آموزش در عمقی کمتر از پنج است.
کاربرد
در زیر، پارامترهای درخت مدل برای تنظیم پیش از اجرای کد ارائه شده‌اند.
model: mean_regr, linear_regr, logistic_regr, svm_regr, modal_clf
max_depth: 1, 2, 3, 4, …
min_samples_leaf: 1, 2, 3, 4, …
search_type: “greedy”, “grid”, “adaptive”
n_search_grid: تعداد نقاط جست‌و‌جوی Grid یکتا (تنها در صورتی فعال می‌شود که search_type = grid یا search_type = adaptive.)
verbose: True, False
کد مربوط به ساخت درخت مدل
کد زیر را باید در فایلی با عنوان run_model_tree و البته پسوند py. ذخیره کرد. شایان توجه است که در کدهای ارائه شده در این قسمت، از کتابخانه‌های «نام‌پای» (NumPy)، «پانداس» (Pandas)، «سایکیت‌لرن» (Scikit Learn)، «سای‌پای» (SciPy) و «گراف‌ویز» (Graphviz) استفاده شده است. این کدها توسط «انسون ونگ» (Anson Wong) نوشته شده‌اند.
"""
model_tree.py (author: Anson Wong / git: ankonzoid)
Given a classification/regression model, this code builds its model tree.
"""
import os, pickle, csv
from src.ModelTree import ModelTree
from src.utils import load_csv_data, cross_validate
def main():
# ====================
# Settings
# ====================
mode = "regr" # "clf" / "regr"
save_model_tree = True # save model tree?
save_model_tree_predictions = True # save model tree predictions/explanations?
cross_validation = True # cross-validate model tree?
# ====================
# Load data
# ====================
data_csv_data_filename = os.path.join("data", "data_clf.csv")
X, y, header = load_csv_data(data_csv_data_filename, mode=mode, verbose=True)
# *********************************************
#
# Insert your models here!
#
# All models must have the following class instantiations:
#
# fit(X, y)
# predict(X)
# loss(X, y, y_pred)
#
# Below are some ready-for-use regression models:
#
# mean regressor (models/mean_regr.py)
# linear regressor (models/linear_regr.py)
# logistic regressor (lmodels/ogistic_regr.py)
# support vector machine regressor (models/svm_regr.py)
# decision tree regressor (models/DT_sklearn_regr.py)
# neural network regressor (models/DT_sklearn_regr.py)
#
# as well as some classification models:
#
# modal classifier (models/modal_clf.py)
# decision tree classifier (models/DT_sklearn_clf.py)
#
# *********************************************
from models.mean_regr import mean_regr
from models.linear_regr import linear_regr
from models.logistic_regr import logistic_regr
from models.svm_regr import svm_regr
from models.DT_sklearn_regr import DT_sklearn_regr
from models.modal_clf import modal_clf
from models.DT_sklearn_clf import DT_sklearn_clf
# Choose model
model = linear_regr()
# Build model tree
model_tree = ModelTree(model, max_depth=4, min_samples_leaf=10,
search_type="greedy", n_search_grid=100)
# ====================
# Train model tree
# ====================
print("Training model tree with '{}'...".format(model.__class__.__name__))
model_tree.fit(X, y, verbose=True)
y_pred = model_tree.predict(X)
explanations = model_tree.explain(X, header)
loss = model_tree.loss(X, y, y_pred)
print(" -> loss_train={:.6f}\n".format(loss))
model_tree.export_graphviz(os.path.join("output", "model_tree"), header,
export_png=True, export_pdf=False)
# ====================
# Save model tree results
# ====================
if save_model_tree:
model_tree_filename = os.path.join("output", "model_tree.p")
print("Saving model tree to '{}'...".format(model_tree_filename))
pickle.dump(model, open(model_tree_filename, 'wb'))
if save_model_tree_predictions:
predictions_csv_filename = os.path.join("output", "model_tree_pred.csv")
print("Saving mode tree predictions to '{}'".format(predictions_csv_filename))
with open(predictions_csv_filename, "w") as f:
writer = csv.writer(f)
field_names = ["x", "y", "y_pred", "explanation"]
writer.writerow(field_names)
for (x_i, y_i, y_pred_i, exp_i) in zip(X, y, y_pred, explanations):
field_values = [x_i, y_i, y_pred_i, exp_i]
writer.writerow(field_values)
# ====================
# Cross-validate model tree
# ====================
if cross_validation:
cross_validate(model_tree, X, y, kfold=5, seed=1)
# Driver
if __name__ == "__main__":
main()
پس از آنکه پارامترها تنظیم شدند، می‌توان دستور زیر را اجرا کرد.
python3 run_model_tree.py
این کد، داده‌ها را بارگذاری می‌کند و درخت مدل را آموزش می‌دهد. خروجی کد یک شماتیک نمودار درخت، درخت مدل آموزش دیده و پیش‌بینی‌های آموزش درخت مدل است. همچنین، «اعتبارسنجی متقابل» (Cross Validate) مدل نیز انجام می‌شود. متن stdout حاصل از اجرای کد باید به صورت زیر باشد.
Loading data from 'input/data_clf.csv' (mode=regr)...
header=['x1', 'x2', 'x3', 'x4', 'y']
X.shape=(1372, 4)
y.shape=(1372,)
len(y_classes)=2
Training model tree with 'linear_regr'...
max_depth=4, min_samples_leaf=10, search_type=greedy...
node 0 @ depth 0: loss=0.033372, j_feature=1, threshold=-1.862400, N=(339,1033)
node 1 @ depth 1: loss=0.016889, j_feature=0, threshold=0.234600, N=(209,130)
node 3 @ depth 2: loss=0.006617, j_feature=0, threshold=-0.657670, N=(195,14)
*leaf 5 @ depth 3: loss=0.000000, N=195
*leaf 6 @ depth 3: loss=0.004635, N=14
node 4 @ depth 2: loss=0.010361, j_feature=0, threshold=0.744280, N=(13,117)
*leaf 7 @ depth 3: loss=0.000000, N=13
*leaf 8 @ depth 3: loss=0.000000, N=117
node 2 @ depth 1: loss=0.023927, j_feature=2, threshold=-1.544300, N=(346,687)
node 9 @ depth 2: loss=0.014254, j_feature=1, threshold=5.202200, N=(149,197)
node 11 @ depth 3: loss=0.007080, j_feature=0, threshold=2.017700, N=(139,10)
*leaf 13 @ depth 4: loss=0.000000, N=139
*leaf 14 @ depth 4: loss=0.003821, N=10
*leaf 12 @ depth 3: loss=0.000000, N=197
node 10 @ depth 2: loss=0.018931, j_feature=0, threshold=0.559390, N=(377,310)
node 15 @ depth 3: loss=0.020929, j_feature=3, threshold=-1.566800, N=(154,223)
*leaf 17 @ depth 4: loss=0.010759, N=154
*leaf 18 @ depth 4: loss=0.020452, N=223
node 16 @ depth 3: loss=0.002916, j_feature=1, threshold=-0.045533, N=(23,287)
*leaf 19 @ depth 4: loss=0.016037, N=23
*leaf 20 @ depth 4: loss=0.000000, N=287
-> loss_train=0.004876
Saving model tree diagram to 'output/model_tree.png'...
Saving model tree to 'output/model_tree.p'...
Saving mode tree predictions to 'output/model_tree_pred.csv'
Cross-validating (kfold=5, seed=1)...
[fold 1/5] loss_train=0.00424305, loss_validation=0.011334
[fold 2/5] loss_train=0.00373604, loss_validation=0.0138225
[fold 3/5] loss_train=0.00249428, loss_validation=0.00959152
[fold 4/5] loss_train=0.00207239, loss_validation=0.0103934
[fold 5/5] loss_train=0.00469358, loss_validation=0.010235
-> loss_train_avg=0.003448, loss_validation_avg=0.011075
در دایرکتوری output، می‌توان مدل ساخته شده را یافت (output/model_tree.p). یک بصری‌سازی از درخت ساخته شده موجود است (output/model_tree.png). فایل model_tree_pred.csv شامل پیش‌بینی‌های درخت مدل و توصیفات «پیشمایش درخت» (Tree-Traversal) است.
x,y,y_pred,explanation [ 3.6216 8.6661 -2.8073 -0.44699],0,0.0,"['x2 = 8.666100 > -1.862400', 'x3 = -2.807300 <= -1.544300', 'x2 = 8.666100 > 5.202200']" [ 4.5459 8.1674 -2.4586 -1.4621],0,0.0,"['x2 = 8.167400 > -1.862400', 'x3 = -2.458600 <= -1.544300', 'x2 = 8.167400 > 5.202200']" [ 3.866 -2.6383 1.9242 0.10645],0,0.0,"['x2 = -2.638300 <= -1.862400', 'x1 = 3.866000 > 0.234600', 'x1 = 3.866000 > 0.744280']" ...
آزمودن
برای حصول اطمینان از اینکه پیاده‌سازی درخت به درستی کار می‌کند، می‌توان تابع تست را نیز اجرا کرد. کد تابع تست به صورت زیر است و باید آن را در یک فایل با عنوان run_tests و پسوند py. ذخیره کرد.
"""
run_tests.py (author: Anson Wong / git: ankonzoid)
Runs 3 tests to make sure our model tree works as expected.
"""
import os, csv
import numpy as np
import matplotlib.pyplot as plt
from src.utils import load_csv_data
from src.ModelTree import ModelTree
def main():
# ====================
# Run sanity checks on model tree before training (using our own data)
# 1) Reproduce model result on depth-0 model tree
# 2) Reproduce sklearn DecisionTreeRegressor result using mean regression + mse
# 3) Reproduce sklearn DecisionTreeClassifier result using modal class + gini loss
# ====================
run_tests(ModelTree, os.path.join("data", "data_clf.csv"))
# ====================
# For 1D polynomial data using a model tree with linear regression model
# ====================
# Generate 1D polynomial data and save as a csv
func = lambda x: (x-1)*(x-4)*(x-8)*(x-8)
data_csv_data_filename = os.path.join("data", "data_poly4_regr.csv")
generate_csv_data(func, data_csv_data_filename, x_range=(0, 10), N=500)
# Read generated data
X, y, header = load_csv_data(data_csv_data_filename, mode="regr", verbose=True)
assert X.shape[1] == 1
# Train different depth model tree fits and plot results
from models.mean_regr import mean_regr
plot_model_tree_fit(mean_regr(), X, y)
from models.linear_regr import linear_regr
plot_model_tree_fit(linear_regr(), X, y)
# ********************************
#
# Side functions
#
# ********************************
def plot_model_tree_fit(model, X, y):
output_filename = os.path.join("output", "test_{}_fit.png".format(model.__class__.__name__))
print("Saving model tree predictions plot y vs x to '{}'...".format(output_filename))
plt.figure(figsize=(20, 10))
figure_str = "23"
for depth in range(6):
# Form model tree
print(" -> training model tree depth={}...".format(depth))
model_tree = ModelTree(model, max_depth=depth, min_samples_leaf=10,
search_type="greedy", n_search_grid=100)
# Train model tree
model_tree.fit(X, y, verbose=False)
y_pred = model_tree.predict(X)
# Plot predictions
plt.subplot(int(figure_str + str(depth + 1)))
plt.plot(X[:, 0], y, '.', markersize=5, color='k')
plt.plot(X[:, 0], y_pred, '.', markersize=5, color='r')
plt.legend(['data', 'fit'])
plt.title("depth = {}".format(depth))
plt.xlabel("x", fontsize=15)
plt.ylabel("y", fontsize=15)
plt.grid()
plt.suptitle('Model tree (model = {}) fits for different depths'.format(model.__class__.__name__), fontsize=25)
plt.savefig(output_filename, bbox_inches='tight')
plt.close()
def generate_csv_data(func, output_csv_filename, x_range=(0, 1), N=500):
x_vec = np.linspace(x_range[0], x_range[1], N)
y_vec = np.vectorize(func)(x_vec)
with open(output_csv_filename, "w") as f:
writer = csv.writer(f)
field_names = ["x1", "y"]
writer.writerow(field_names)
for (x, y) in zip(x_vec, y_vec):
field_values = [x, y]
writer.writerow(field_values)
def run_tests(ModelTree, data_csv_filename):
print("Running model tree tests...")
eps = 1E-6 # tolerance for test acceptance
X, y, header = load_csv_data(data_csv_filename, mode="regr")
# Test 1
print(" [1/3] Checking depth-0 model tree...")
from models.linear_regr import linear_regr
model = linear_regr()
MTR_0 = ModelTree(model, max_depth=0, min_samples_leaf=20,
search_type="greedy", n_search_grid=100)
loss_model = experiment(model, X, y)
loss_MTR_0 = experiment(MTR_0, X, y)
print(" -> loss(linregr)={:.6f}, loss(MTR_0_linregr)={:.6f}...".format(loss_model, loss_MTR_0))
if np.abs(loss_model - loss_MTR_0) > eps:
exit("err: passed test 1!")
else:
print(" -> passed test 1!")
# Test 2
print(" [2/3] Reproducing DecisionTreeRegressor sklearn (depth=20) result...")
from models.mean_regr import mean_regr
MTR = ModelTree(mean_regr(), max_depth=20, min_samples_leaf=10,
search_type="greedy", n_search_grid=100)
from models.DT_sklearn_regr import DT_sklearn_regr
DTR_sklearn = DT_sklearn_regr(max_depth=20, min_samples_leaf=10)
loss_MTR = experiment(MTR, X, y)
loss_DTR_sklearn = experiment(DTR_sklearn, X, y)
print(" -> loss(MTR)={:.6f}, loss(DTR_sklearn)={:.6f}...".format(loss_MTR, loss_DTR_sklearn))
if np.abs(loss_MTR - loss_DTR_sklearn) > eps:
exit("err: passed test 2!")
else:
print(" -> passed test 2!")
# Test 3
print(" [3/3] Reproducing DecisionTreeClassifier sklearn (depth=20) result...")
from models.modal_clf import modal_clf
MTC = ModelTree(modal_clf(), max_depth=20, min_samples_leaf=10,
search_type="greedy", n_search_grid=100)
from models.DT_sklearn_clf import DT_sklearn_clf
DTC_sklearn = DT_sklearn_clf(max_depth=20, min_samples_leaf=10)
loss_MTC = experiment(MTC, X, y)
loss_DTC_sklearn = experiment(DTC_sklearn, X, y)
print(" -> loss(MTC)={:.6f}, loss(DTC_sklearn)={:.6f}...".format(loss_MTC, loss_DTC_sklearn))
if np.abs(loss_MTC - loss_DTC_sklearn) > eps:
exit("err: passed test 3!")
else:
print(" -> passed test 3!")
print()
def experiment(model, X, y):
model.fit(X, y) # train model
y_pred = model.predict(X)
loss = model.loss(X, y, y_pred) # compute loss
return loss
# Driver
if __name__ == "__main__":
main()
این کد، نتایج مدل اصلی را در درخت مدل عمق صفر مجددا تولید می‌کند. همچنین، پیاده‌سازی دسته‌بند درخت تصمیم پیش‌فرض کتابخانه سایکیت‌لرن (DecisionTreeClassifier) را با استفاده از دسته‌بندی مدل با «زیان ناخالص کلاس جینی» (Gini class impurity loss) بازتولید می‌کند. در عین حال، پیاده‌ساز رگرسور درخت تصمیم پیش‌فرض کتابخانه sklearn را (DecisionTreeRegressor) با استفاده از بازگشت به میانگین با «زیان میانگین مربعات خطا» (mean squared error loss) مجددا تولید می‌کند. در نهایت، نمودار پیش‌بینی‌های درخت مدل برای چندجمله‌ای مرتبه چهارم را در عمق‌های مختلف درخت با استفاده از درخت مدل رگرسیون (output/test_linear_regr_fit.png) و درخت‌های مدل رگرسیون میانگین (output/test_mean_regr_fit.png) تولید می‌کند.
هدف درخت مدل چیست؟
فرض می‌شود که کاربر داده‌های آموزش پیچیده‌ای دارد و به یک مدل ساده برای برازش این مجموعه داده فکر می‌کند (مانند رگرسیون خطی یا رگرسیون لجستیک). مخصوصا اگر مدل ساده‌ای که کاربر به آن فکر می‌کند دارای پیچیدگی کمی باشد، شانس خوبی وجود دارد که مدل به خودی خود روی داده‌ها دچار «کم‌برازش» (Underfit) شود. اگرچه امید در این نقطه از بین نمی‌رود. هدف از درخت مدل ساخت یک سلسله مراتب درخت تصمیم از مدل ساده به عنوان تلاشی برای برازش چندین بخش کوچک‌تر از مجموعه داده‌ها است (با استفاده از بخش‌بندی ویژگی‌ها) که در آن مدل کلی به خوبی با مجموعه آموزش کامل برازش می‌شود.
برای نشان دادن صریح مفید بودن ساخت یک مدل درخت نسبت به یک درخت تصمیم معمول، می‌توان مثال بیان شده در بالا را در نظر گرفت. یک چند جمله‌ای یک‌بُعدی مرتبه چهارم مفروض است و تفاوت بین آموزش دادن یک رگرسور درخت مدل رگرسیون خطی با عمق کم و رگرسور درخت تصمیم پیش‌فرض کتابخانه سایکیت‌لرن در تصاویر ارائه شده در زیر قابل مشاهده هستند. این تصاویر پیش‌تر نیز ارائه شده بودند، ولیکن برای درک بهتر مطلب، تصاویر مجددا در این قسمت آورده می‌شوند.
در شکل اول، برازش‌های درخت مدل رگرسیون خطی برای داده‌ها ترسیم شده و عمق درخت افزایش داده شده و در نهایت در عمق پنج به خوبی برای داده‌ها برازش پیدا کرده است (برای مثال ۰، ۱ و ۲). برازش به گونه‌ای بوده که مدل به طور حریصانه‌ای در تلاش برای کاهش زیان با پوشش دادن بخش بزرگی از چند جمله‌ای است، به‌گونه‌ای که از دور به نظر می‌رسد یک خط هستند. با رسیدن به عمق ۴ و ۵، درخت مدل به خوبی وابستگی-x داده‌ها را چنانکه از چندجمله‌ای مرتبه چهارم انتظار می‌رود پیدا کرده است.
از سوی دیگر، در شکل دوم، برازش رگرسور درخت تصمیم پیش‌فرض کتابخانه سایکیت‌لرن پایتون رسم شده است. همانطور که از تصویر مشهود است، حتی در عمق‌های بالا نیز مدل همچنان در برازش ضعیف عمل می‌کند زیرا نمی‌تواند به خوبی وابستگی-x داده‌ها را ثبت کند. دلیل آنچه بیان شد این است که درخت تصمیم سایکیت‌لرن، از رگرسیون میانگین استفاده می‌کند (که به متغیر x توجهی ندارد و فقط به y اهمیت می‌دهد). بنابراین، راهکار (بدون استفاده از روش‌های ترکیبی) وادار کردن درخت به عمیق‌تر شدن برای نزدیک‌تر شدن در برآورد(بهبود برآوردها) است. به عنوان نکته آخر لازم به ذکر است که درخت‌های مدل به لحاظ مفهومی به شیوه‌ای مشابه با درخت تصمیم مرسوم ساخته می‌شوند، بدین معنا که درخت‌های مدل ممکن است از همان نواقصی رنج ببرند که درخت تصمیم دارد و از این جمله می‌توان به «بیش‌برازش» (OverFitting) به ویژه هنگامی که از مدل‌های پیچیده استفاده می‌شود اشاره کرد.
اگر نوشته بالا برای شما مفید بوده، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزش‌های آمار، احتمالات و داده‌کاوی
- آموزش‌های داده کاوی یا Data Mining در متلب
- مجموعه آموزش‌های مدل‌سازی، برازش و تخمین
- داده کاوی (Data Mining) — از صفر تا صد
- زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
- یادگیری علم داده (Data Science) با پایتون — از صفر تا صد
^^
