الگوریتم CART چیست؟ راهنمای درختان طبقه‌بندی و رگرسیون

الگوریتم CART یا Classification And Regression Trees یکی از روش‌های شناخته‌شده برای ساخت درخت تصمیم در یادگیری ماشین است. این الگوریتم می‌تواند هم برای طبقه‌بندی و هم برای رگرسیون استفاده شود و با تقسیم مکرر داده‌ها به زیرمجموعه‌های کوچک‌تر، ساختار یک درخت تصمیم را ایجاد می‌کند.

در CART، در هر مرحله تلاش می‌شود بهترین ویژگی و بهترین نقطه تقسیم انتخاب شود تا زیرمجموعه‌های حاصل تا حد امکان همگن باشند. برای مسائل طبقه‌بندی معمولاً از شاخص جینی (Gini Impurity) استفاده می‌شود، در حالی که در مسائل رگرسیون معیارهایی مانند مجموع مربعات خطا (SSE) یا Mean Squared Error برای ارزیابی تقسیم‌ها به کار می‌روند.

سادگی، قابلیت تفسیر و امکان استفاده برای هر دو نوع مسئله باعث شده است CART یکی از پایه‌های بسیاری از روش‌های درختی در یادگیری ماشین باشد.

الگوریتم CART چیست؟

CART یک روش برای ساخت درخت تصمیم دودویی است که داده‌های آموزشی را به صورت بازگشتی به دو زیرمجموعه تقسیم می‌کند. در هر گام، الگوریتم تمام یا بخشی از تقسیم‌های ممکن را بررسی کرده و تقسیم مناسب‌تری را بر اساس تابع هزینه انتخاب می‌کند.

نام CART از عبارت Classification And Regression Trees گرفته شده است، زیرا یک چارچوب واحد برای ساخت درخت در هر دو مسئله Classification و Regression ارائه می‌دهد.

درخت طبقه‌بندی و درخت رگرسیون چه تفاوتی دارند؟

الگوریتم CART با توجه به نوع متغیر هدف می‌تواند برای دو نوع مسئله استفاده شود:

درخت طبقه‌بندی (Classification Tree)

اگر متغیر هدف شامل کلاس‌های مشخص باشد، از درخت طبقه‌بندی استفاده می‌شود. هدف مدل این است که هر نمونه جدید را در یکی از کلاس‌های موجود قرار دهد.

برای مثال، یک بانک می‌تواند از درخت طبقه‌بندی برای پیش‌بینی اینکه یک تراکنش مشکوک است یا عادی استفاده کند.

در این حالت CART معمولاً با استفاده از معیارهایی مانند Gini Impurity تلاش می‌کند تقسیم‌هایی ایجاد کند که نمونه‌های هر گره را تا حد امکان به یک کلاس نزدیک کنند.

درخت رگرسیون (Regression Tree)

اگر متغیر هدف یک مقدار عددی پیوسته باشد، از درخت رگرسیون استفاده می‌شود.

برای مثال، می‌توان از درخت رگرسیون برای پیش‌بینی قیمت خانه، میزان فروش، درآمد یا تقاضای یک محصول استفاده کرد.

در این حالت، CART به دنبال تقسیم‌هایی است که خطای پیش‌بینی مقادیر عددی در زیرمجموعه‌های حاصل را کاهش دهند.

ساختار درخت تصمیم در CART

درخت تصمیم ساخته‌شده توسط CART از چند بخش اصلی تشکیل می‌شود:

• گره ریشه (Root Node): نقطه شروع درخت و شامل کل داده‌های آموزشی است.
• گره داخلی (Internal Node): نقطه‌ای که در آن داده‌ها بر اساس یک ویژگی و یک شرط مشخص تقسیم می‌شوند.
• شاخه (Branch): مسیر اتصال گره‌ها و نمایش‌دهنده نتیجه یک شرط یا تقسیم است.
• گره برگ (Leaf Node): نقطه پایانی درخت که خروجی نهایی مدل در آن تعیین می‌شود.

یکی از ویژگی‌های مهم CART این است که هر تقسیم به دو شاخه منتهی می‌شود؛ به همین دلیل ساختار آن دودویی (Binary Tree) است.

الگوریتم CART چگونه کار می‌کند؟

فرایند ساخت درخت در CART را می‌توان به صورت یک فرایند تقسیم بازگشتی در نظر گرفت. الگوریتم از مجموعه داده آموزشی شروع می‌کند و در هر مرحله بهترین تقسیم ممکن را پیدا می‌کند.

1. شروع با کل داده‌های آموزشی: تمام نمونه‌ها ابتدا در گره ریشه قرار می‌گیرند.
2. بررسی ویژگی‌ها: ویژگی‌های موجود در داده بررسی می‌شوند.
3. بررسی نقاط تقسیم: برای هر ویژگی، نقاط یا آستانه‌های ممکن برای تقسیم داده بررسی می‌شوند.
4. محاسبه هزینه: کیفیت هر تقسیم با معیار مناسب ارزیابی می‌شود.
5. انتخاب بهترین تقسیم: تقسیم دارای کمترین هزینه یا بیشترین کاهش ناخالصی انتخاب می‌شود.
6. تقسیم بازگشتی: همین فرایند برای گره‌های جدید ادامه پیدا می‌کند.
7. توقف یا هرس: ساخت درخت در شرایط مشخص متوقف می‌شود یا درخت ایجادشده برای جلوگیری از بیش‌برازش هرس می‌شود.

شاخص جینی در الگوریتم CART چیست؟

در مسائل طبقه‌بندی، یکی از معیارهای مهم CART برای ارزیابی کیفیت تقسیم، شاخص جینی است.

شاخص جینی میزان ناخالصی یک گره را اندازه‌گیری می‌کند. اگر تمام نمونه‌های یک گره متعلق به یک کلاس باشند، آن گره کاملاً خالص است و مقدار ناخالصی جینی آن صفر خواهد بود.

فرمول شاخص جینی به صورت زیر بیان می‌شود:

Gini = 1 − Σ p_k²

در این رابطه، p_k نسبت نمونه‌های متعلق به کلاس k در گره موردنظر است.

در نتیجه، CART در مسئله طبقه‌بندی به دنبال تقسیم‌هایی است که ناخالصی گره‌های حاصل را کاهش دهند.

معیار CART برای مسائل رگرسیون

در درخت رگرسیون، خروجی مدل یک مقدار عددی است؛ بنابراین شاخص جینی مناسب نیست. در این حالت از معیارهایی برای اندازه‌گیری خطای پیش‌بینی استفاده می‌شود.

یکی از معیارهای رایج، مجموع مربعات خطا (Sum of Squared Errors) است. الگوریتم تلاش می‌کند تقسیم‌هایی را انتخاب کند که مجموع خطای مربعات در گره‌های حاصل را کاهش دهند.

به بیان ساده، اگر تقسیم خاصی باعث شود مقادیر هدف در هر زیرمجموعه به یکدیگر نزدیک‌تر شوند، آن تقسیم برای درخت رگرسیون مناسب‌تر خواهد بود.

الگوریتم حریصانه در CART

ساخت یک درخت تصمیم بهینه در حالت کلی می‌تواند بسیار پیچیده باشد. به همین دلیل CART از یک رویکرد حریصانه (Greedy) برای ساخت درخت استفاده می‌کند.

در رویکرد حریصانه، الگوریتم در هر گره بهترین تقسیم موجود در همان مرحله را انتخاب می‌کند، بدون اینکه تمام ساختارهای احتمالی آینده درخت را به صورت کامل بررسی کند.

این فرایند به عنوان تقسیم دودویی بازگشتی (Recursive Binary Splitting) شناخته می‌شود.

برای مثال، فرض کنید هدف پیش‌بینی قیمت خانه باشد. CART ممکن است ابتدا بررسی کند که آیا تقسیم داده‌ها بر اساس متراژ، تعداد اتاق‌ها، منطقه یا سن ساختمان بهترین کاهش خطا را ایجاد می‌کند. سپس بهترین ویژگی و آستانه را انتخاب کرده و همین فرایند را برای هر زیرمجموعه ادامه می‌دهد.

معیار توقف در الگوریتم CART

اگر تقسیم کردن گره‌ها بدون محدودیت ادامه پیدا کند، درخت می‌تواند بیش از حد پیچیده شود و به جای یادگیری الگوی عمومی، جزئیات و نویز داده‌های آموزشی را یاد بگیرد. این مسئله به Overfitting منجر می‌شود.

برای کنترل رشد درخت می‌توان از معیارهای توقف مختلف استفاده کرد، از جمله:

• حداکثر عمق درخت (max_depth)
• حداقل تعداد نمونه برای تقسیم یک گره (min_samples_split)
• حداقل تعداد نمونه در یک برگ (min_samples_leaf)
• حداقل میزان کاهش ناخالصی برای انجام یک تقسیم

این پارامترها به کنترل پیچیدگی مدل و کاهش احتمال بیش‌برازش کمک می‌کنند.

هرس درخت در CART چیست؟

هرس (Pruning) فرایند حذف بخش‌هایی از یک درخت تصمیم است که پیچیدگی مدل را افزایش می‌دهند اما ارزش پیش‌بینی قابل توجهی ایجاد نمی‌کنند.

یکی از روش‌های شناخته‌شده در CART، Cost-Complexity Pruning یا هرس بر اساس پیچیدگی هزینه است. در این روش، علاوه بر خطای مدل، پیچیدگی درخت نیز در نظر گرفته می‌شود.

ایده اصلی این است که یک درخت بسیار بزرگ لزوماً مدل بهتری نیست. گاهی حذف چند شاخه می‌تواند باعث شود مدل ساده‌تر، قابل تفسیرتر و در داده‌های جدید عملکرد بهتری داشته باشد.

آیا برای استفاده از CART به آماده‌سازی داده نیاز داریم؟

درخت‌های تصمیم نسبت به بسیاری از الگوریتم‌های دیگر به پیش‌پردازش پیچیده‌ای نیاز ندارند. برای مثال، Feature Scaling معمولاً برای CART ضروری نیست، زیرا تقسیم‌ها بر اساس شرط‌هایی روی ویژگی‌ها انجام می‌شوند.

با این حال، این موضوع به معنای بی‌نیازی کامل از آماده‌سازی داده نیست. کیفیت داده همچنان اهمیت زیادی دارد و مواردی مانند داده‌های گمشده، ویژگی‌های نامناسب، داده‌های تکراری و متغیرهای اشتباه باید بررسی شوند.

همچنین باید نوع داده‌های دسته‌ای و نحوه تبدیل آن‌ها به فرم قابل استفاده برای پیاده‌سازی موردنظر را در نظر گرفت.

مزایای الگوریتم CART

• قابل تفسیر بودن: مسیر تصمیم‌گیری درخت را می‌توان به صورت شرط‌های قابل فهم مشاهده کرد.
• استفاده برای Classification و Regression: یک چارچوب درختی می‌تواند برای هر دو نوع مسئله استفاده شود.
• نیاز کم به Feature Scaling: مقیاس‌بندی ویژگی‌ها معمولاً برای ساخت درخت ضروری نیست.
• توانایی مدل‌سازی روابط غیرخطی: درخت تصمیم برای روابطی که با یک خط یا رابطه ساده قابل توضیح نیستند نیز کاربرد دارد.
• قابلیت مدل‌سازی تعامل میان ویژگی‌ها: مسیرهای مختلف درخت می‌توانند ترکیب‌های متفاوتی از ویژگی‌ها را نشان دهند.
• امکان استخراج قواعد تصمیم: شاخه‌های درخت را می‌توان به مجموعه‌ای از قواعد شرطی تبدیل کرد.

معایب و محدودیت‌های CART

• حساسیت به تغییرات داده: تغییر کوچک در داده آموزشی می‌تواند ساختار درخت را تغییر دهد.
• خطر بیش‌برازش: درخت‌های بسیار عمیق می‌توانند نویز داده‌های آموزشی را نیز یاد بگیرند.
• ناپایداری: برخلاف برخی مدل‌ها، ساختار یک درخت منفرد ممکن است نسبت به تغییر نمونه‌های آموزشی حساس باشد.
• وابستگی به انتخاب تقسیم‌ها: استفاده از رویکرد حریصانه الزاماً بهترین درخت ممکن را تضمین نمی‌کند.
• ممکن است در برخی مسائل دقت پایین‌تری نسبت به روش‌های Ensemble داشته باشد: روش‌هایی مانند Random Forest و Gradient Boosting معمولاً برای افزایش پایداری و قدرت پیش‌بینی از چندین درخت استفاده می‌کنند.

CART چه تفاوتی با Decision Tree دارد؟

Decision Tree یک مفهوم کلی برای مدل‌های درخت تصمیم است، در حالی که CART یک روش مشخص برای ساخت درخت تصمیم است.

بنابراین بهتر است CART را یک روش مشخص برای ساخت درخت تصمیم بدانیم، نه اینکه این دو اصطلاح را کاملاً مترادف در نظر بگیریم.

CART چه تفاوتی با Random Forest دارد؟

یکی از اشتباهات رایج این است که CART را زیرمجموعه Random Forest بدانیم. رابطه دقیق‌تر این است که Random Forest یک روش Ensemble است که از تعداد زیادی درخت تصمیم استفاده می‌کند و در بسیاری از پیاده‌سازی‌ها درخت‌های آن بر مبنای ایده‌های CART ساخته می‌شوند.

در یک درخت CART، تنها یک درخت برای تولید پیش‌بینی استفاده می‌شود؛ بنابراین ممکن است مدل نسبت به تغییرات داده حساس باشد. Random Forest با ترکیب تعداد زیادی درخت تلاش می‌کند این ناپایداری را کاهش دهد و عملکرد عمومی مدل را بهبود دهد.

کاربردهای الگوریتم CART

پیش‌بینی ریسک اعتباری

بانک‌ها و مؤسسات مالی می‌توانند از درخت‌های تصمیم برای دسته‌بندی متقاضیان بر اساس ویژگی‌هایی مانند درآمد، سابقه اعتباری، بدهی و رفتار مالی استفاده کنند.

تشخیص تقلب

CART می‌تواند برای طبقه‌بندی تراکنش‌ها و شناسایی الگوهایی که با رفتار عادی تفاوت دارند مورد استفاده قرار گیرد.

بازاریابی و تقسیم‌بندی مشتریان

درخت‌های تصمیم می‌توانند برای پیش‌بینی احتمال خرید، پاسخ مشتری به یک کمپین یا احتمال ریزش مشتری استفاده شوند.

پیش‌بینی فروش و تقاضا

در مسائل رگرسیونی می‌توان از CART برای تخمین مقدار فروش یا تقاضا بر اساس ویژگی‌هایی مانند فصل، قیمت، منطقه و مشخصات محصول استفاده کرد.

پزشکی و زیست‌داده

درخت‌های تصمیم می‌توانند برای طبقه‌بندی نمونه‌های بالینی، پیش‌بینی یک وضعیت یا شناسایی ترکیب‌هایی از ویژگی‌ها که با یک خروجی مشخص ارتباط دارند استفاده شوند. در کاربردهای پزشکی، اعتبارسنجی آماری و تفسیر تخصصی نتایج اهمیت ویژه‌ای دارد.

نگهداری پیش‌بینانه

در محیط‌های صنعتی، داده‌های حسگرها می‌توانند برای پیش‌بینی خرابی تجهیزات یا طبقه‌بندی وضعیت دستگاه‌ها مورد استفاده قرار گیرند.

یک مثال ساده از الگوریتم CART

فرض کنید هدف ما پیش‌بینی این است که آیا یک مشتری احتمال خرید یک محصول را دارد یا خیر.

داده‌های آموزشی می‌توانند شامل ویژگی‌هایی مانند سن، تعداد خریدهای قبلی، مبلغ خرید و مدت زمان عضویت مشتری باشند.

CART ابتدا بررسی می‌کند که کدام ویژگی و کدام آستانه می‌تواند داده‌ها را به بهترین شکل به دو گروه تقسیم کند. برای مثال، ممکن است یک تقسیم بر اساس تعداد خریدهای قبلی انتخاب شود:

• تعداد خریدهای قبلی کمتر از یک آستانه مشخص → شاخه اول
• تعداد خریدهای قبلی بیشتر یا مساوی آستانه → شاخه دوم

سپس هر شاخه دوباره بررسی می‌شود و در صورت مناسب بودن، تقسیم دیگری روی آن انجام می‌گیرد. در نهایت، نمونه جدید با حرکت از ریشه تا یکی از برگ‌ها، به یک کلاس مشخص اختصاص داده می‌شود.

همین منطق در رگرسیون نیز استفاده می‌شود؛ با این تفاوت که خروجی برگ به جای یک کلاس، یک مقدار عددی را نشان می‌دهد.

پیاده‌سازی CART با Python و scikit-learn

یکی از ساده‌ترین روش‌ها برای استفاده از CART در Python، استفاده از کتابخانه scikit-learn است.

برای طبقه‌بندی می‌توان از DecisionTreeClassifier و برای رگرسیون از DecisionTreeRegressor استفاده کرد.

from sklearn.tree import DecisionTreeClassifier

model = DecisionTreeClassifier(
    criterion="gini",
    max_depth=4,
    random_state=42
)

model.fit(X_train, y_train)

predictions = model.predict(X_test)

در این مثال، معیار Gini برای ارزیابی ناخالصی گره‌های طبقه‌بندی استفاده شده و max_depth برای کنترل عمق درخت تنظیم شده است.

در مسائل رگرسیون نیز می‌توان از DecisionTreeRegressor استفاده کرد و معیار مناسب را با توجه به مسئله انتخاب کرد.

نکات مهم هنگام استفاده از CART

• عمق درخت را بدون بررسی عملکرد روی داده‌های اعتبارسنجی بیش از حد افزایش ندهید.
• از معیارهای مناسب برای ارزیابی Classification و Regression استفاده کنید.
• تنها به دقت روی داده‌های آموزشی توجه نکنید.
• از Cross-Validation برای ارزیابی مطمئن‌تر مدل استفاده کنید.
• پارامترهایی مانند max_depth و min_samples_leaf را برای کنترل پیچیدگی بررسی کنید.
• اگر یک درخت منفرد ناپایدار است، روش‌های Ensemble مانند Random Forest را نیز بررسی کنید.

مزایا و معایب CART در یک نگاه

جمع‌بندی

الگوریتم CART یکی از روش‌های مهم برای ساخت درخت تصمیم در یادگیری ماشین است که می‌تواند هم برای طبقه‌بندی و هم برای رگرسیون استفاده شود. این الگوریتم با تقسیم دودویی و بازگشتی داده‌ها تلاش می‌کند زیرمجموعه‌هایی ایجاد کند که برای پیش‌بینی مناسب‌تر و همگن‌تر باشند.

در Classification، معیارهایی مانند Gini Impurity برای انتخاب تقسیم‌ها استفاده می‌شوند و در Regression، معیارهای مبتنی بر خطا مانند SSE یا MSE کاربرد دارند. کنترل عمق درخت، تعیین حداقل تعداد نمونه‌ها و استفاده از روش‌های هرس نیز برای جلوگیری از بیش‌برازش اهمیت دارند.

CART به دلیل سادگی و قابلیت تفسیر، همچنان یکی از مفاهیم پایه‌ای مهم در یادگیری ماشین است و ایده‌های درخت تصمیم در الگوریتم‌های قدرتمندتری مانند Random Forest و برخی روش‌های Gradient Boosting نیز نقش مهمی دارند.

اگر در حال یادگیری یادگیری ماشین هستید، درک دقیق CART می‌تواند پایه مناسبی برای فهم روش‌های Ensemble و الگوریتم‌های پیشرفته‌تر مبتنی بر درخت فراهم کند.

سؤالات متداول درباره الگوریتم CART

الگوریتم CART چیست؟

CART یا Classification And Regression Trees روشی برای ساخت درخت تصمیم دودویی است که برای حل مسائل طبقه‌بندی و رگرسیون استفاده می‌شود.

تفاوت CART و Decision Tree چیست؟

Decision Tree یک مفهوم کلی برای مدل‌های درخت تصمیم است، در حالی که CART یک روش مشخص برای ساخت درخت تصمیم دودویی است که برای Classification و Regression کاربرد دارد.

شاخص جینی در CART چیست؟

شاخص جینی معیاری برای اندازه‌گیری ناخالصی گره‌ها در مسائل طبقه‌بندی است. هرچه گره خالص‌تر باشد، مقدار Gini آن کمتر است.

آیا CART برای رگرسیون هم استفاده می‌شود؟

بله. همان‌طور که از نام Classification And Regression Trees مشخص است، CART می‌تواند برای مسائل رگرسیونی نیز استفاده شود. در این حالت معیارهای مبتنی بر خطای عددی مانند SSE یا MSE برای انتخاب تقسیم‌ها کاربرد دارند.

آیا CART به نرمال‌سازی داده‌ها نیاز دارد؟

معمولاً خیر. درخت‌های تصمیم مانند مدل‌هایی که بر فاصله یا گرادیان وابسته هستند، معمولاً به Feature Scaling نیاز ندارند. با این حال، آماده‌سازی و پاکسازی داده همچنان ضروری است.

تفاوت CART و Random Forest چیست؟

CART یک درخت تصمیم منفرد می‌سازد، در حالی که Random Forest از مجموعه‌ای از درخت‌ها برای تولید یک مدل Ensemble استفاده می‌کند. Random Forest معمولاً پایداری و تعمیم بهتری نسبت به یک درخت منفرد دارد.

چگونه از بیش‌برازش در CART جلوگیری کنیم؟

می‌توان با محدود کردن عمق درخت، افزایش حداقل تعداد نمونه‌های برگ، تنظیم معیارهای توقف، استفاده از Cross-Validation و هرس درخت احتمال بیش‌برازش را کاهش داد.