الفهم بالتنفيذ: شجرة القرار

صورة المؤلف

العديد من نماذج التعلم الآلي المتقدمة مثل الغابات العشوائية أو خوارزميات تعزيز التدرج مثل XGBoost أو CatBoost أو LightGBM (وحتى التشفير التلقائي!) على عنصر مشترك حاسم: شجرة القرار!

بدون فهم أشجار القرار ، من المستحيل فهم أي من خوارزميات التعبئة المتقدمة أو خوارزميات تعزيز التدرج المذكورة أعلاه أيضًا ، وهو عار لأي عالم بيانات! لذا ، دعونا نزيل الغموض عن الإجراءات الداخلية لشجرة القرار من خلال تنفيذ واحدة في بايثون.

في هذه المقالة ، سوف تتعلم

• لماذا وكيف تقسم شجرة القرار البيانات ،
• اكتساب المعلومات ، و
• كيفية تنفيذ أشجار القرار في Python باستخدام NumPy.

يمكنك العثور على الرمز على جيثب الخاص بي.

من أجل عمل تنبؤات ، تعتمد أشجار القرار على شق مجموعة البيانات إلى أجزاء أصغر بطريقة متكررة.

صورة المؤلف

في الصورة أعلاه ، يمكنك رؤية مثال واحد على الانقسام - يتم فصل مجموعة البيانات الأصلية إلى جزأين. في الخطوة التالية ، يتم تقسيم كلا الجزأين مرة أخرى ، وهكذا. يستمر هذا حتى يتم استيفاء نوع من معيار الإيقاف ، على سبيل المثال ،

• إذا نتج عن الانقسام أن يكون الجزء فارغًا
• إذا تم الوصول إلى عمق عودي معين
• إذا (بعد الانقسامات السابقة) تتكون مجموعة البيانات فقط من عدد قليل من العناصر ، مما يجعل المزيد من التقسيمات غير ضرورية.

كيف نجد هذه الانقسامات؟ ولماذا نهتم حتى؟ هيا نكتشف.

التحفيز

لنفترض أننا نريد حل أ ثنائي مشكلة التصنيف التي نصنعها بأنفسنا الآن:

import numpy as np
np.random.seed(0) X = np.random.randn(100, 2) # features
y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)

تبدو البيانات ثنائية الأبعاد كما يلي:

صورة المؤلف

يمكننا أن نرى أن هناك فئتين مختلفتين - الأرجواني في حوالي 75٪ والأصفر في حوالي 25٪ من الحالات. إذا قمت بتغذية هذه البيانات إلى شجرة القرار صنف، هذه الشجرة لديها الأفكار التالية في البداية:

"هناك نوعان مختلفان من التصنيفات ، وهو أمر فوضوي للغاية بالنسبة لي. أريد التخلص من هذه الفوضى عن طريق تقسيم البيانات إلى جزأين - يجب أن تكون هذه الأجزاء أنظف من البيانات الكاملة من قبل. " - الشجرة التي اكتسبت وعيها

وهكذا تفعل الشجرة.

صورة المؤلف

تقرر الشجرة عمل انقسام تقريبًا على طول x-محور. هذا له تأثير أن الجزء العلوي من البيانات أصبح الآن مثاليًا نظيف ، مما يعني أنك تجد فقط فئة واحدة (أرجواني في هذه الحالة) هناك.

ومع ذلك ، فإن الجزء السفلي لا يزال فوضوي، أكثر فوضوية من ذي قبل بمعنى ما. كانت نسبة الفصل في السابق حوالي 75:25 في مجموعة البيانات الكاملة ، ولكن في هذا الجزء الأصغر تكون حوالي 50:50 ، وهي مختلطة قدر الإمكان

 ملحوظة: هنا ، لا يهم أن يتم فصل اللونين الأرجواني والأصفر بشكل جيد في الصورة. فقط amout الخام من تسميات مختلفة في جزأين العد.

صورة المؤلف

ومع ذلك ، هذا جيد بما يكفي كخطوة أولى للشجرة ، وهكذا تستمر. في حين أنه لن يخلق انقسامًا آخر في الأعلى ، نظيف بعد الآن ، يمكنه إنشاء انقسام آخر في الجزء السفلي لتنظيفه.

صورة المؤلف

فويلا ، كل جزء من الأجزاء الثلاثة المنفصلة نظيف تمامًا ، حيث نجد فقط لونًا واحدًا (ملصق) لكل جزء.

من السهل حقًا إجراء تنبؤات الآن: إذا ظهرت نقطة بيانات جديدة ، فما عليك سوى التحقق من أي من ثلاثة أجزاء انها تقع وتعطيه اللون المقابل. هذا يعمل بشكل جيد الآن لأن كل جزء نظيف. حق سهل؟

صورة المؤلف

حسنًا ، كنا نتحدث عنه نظيف و  فوضوي البيانات ولكن حتى الآن هذه الكلمات لا تمثل سوى فكرة غامضة. من أجل تنفيذ أي شيء ، علينا أن نجد طريقة للتعريف النظافة.

إجراءات النظافة

لنفترض أن لدينا بعض الملصقات ، على سبيل المثال

y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0]
y_3 = [1, 0, 1, 1, 0, 0, 1, 0]

حدسي، y₁ هي أنظف مجموعة من الملصقات ، متبوعة بـ y₂ وثم y₃. جيد حتى الآن ، لكن كيف يمكننا وضع أرقام على هذا السلوك؟ ربما يكون أسهل ما يتبادر إلى الذهن هو ما يلي:

فقط عد عدد الأصفار وكمية الآحاد. احسب فرقهم المطلق. لجعلها أجمل ، قم بتطبيعها بقسمة طول المصفوفات.

على سبيل المثال، y₂ يحتوي على 8 إدخالات في المجموع - 6 أصفار و 2 آحاد. ومن ثم ، لدينا العرف المحدد درجة النظافة سيكون | 6 - 2 | / 8 = 0.5. من السهل حساب درجات النظافة هذه y₁ و  y₃ هي 1.0 و 0.0 على التوالي. هنا ، يمكننا أن نرى الصيغة العامة:

صورة المؤلف

هنا، لا و  ن₁ هي عدد الأصفار والآحاد على التوالي ، ن = ن + ن هو طول المصفوفة و ع = ن / ن هي الحصة من 1 تصنيفات.

المشكلة في هذه الصيغة هي أنها كذلك مصممة خصيصًا لحالة فئتين، ولكن في كثير من الأحيان نحن مهتمون بالتصنيف متعدد الفئات. إحدى الصيغ التي تعمل بشكل جيد هي قياس النجاسة جيني:

صورة المؤلف

أو الحالة العامة:

صورة المؤلف

إنه يعمل بشكل جيد لدرجة أن scikit-Learn اعتمده كإجراء افتراضي ل ه DecisionTreeClassifier فئة.

صورة المؤلف

 ملحوظة: تدابير جيني الفوضى بدلا من النظافة. مثال: إذا كانت القائمة تحتوي على فئة واحدة فقط (= بيانات نظيفة جدًا!) ، فإن جميع الحدود في المجموع هي صفر ، وبالتالي يكون المجموع صفراً. أسوأ حالة هي ظهور جميع الفئات بعدد المرات بالضبط ، وفي هذه الحالة يكون جيني 1–1 /C أين C هو عدد الفصول.

الآن بعد أن أصبح لدينا مقياس للنظافة / الفوضى ، دعونا نرى كيف يمكن استخدامه للعثور على انشقاقات جيدة.

البحث عن الانقسامات

هناك الكثير من الانقسامات التي نختار من بينها ، ولكن أيهما جيد؟ دعونا نستخدم مجموعة البيانات الأولية الخاصة بنا مرة أخرى ، جنبًا إلى جنب مع مقياس شوائب جيني.

صورة المؤلف

لن نحسب النقاط الآن ، لكن دعنا نفترض أن 75٪ أرجواني و 25٪ أصفر. باستخدام تعريف جيني ، تكون شوائب مجموعة البيانات الكاملة

صورة المؤلف

إذا قمنا بتقسيم مجموعة البيانات على طول x-المحور ، كما حدث من قبل:

صورة المؤلف

• الجزء العلوي يحتوي على شوائب جيني تبلغ 0.0 والجزء السفلي

صورة المؤلف

في المتوسط ​​، يحتوي الجزءان على شوائب جيني (0.0 + 0.5) / 2 = 0.25 ، وهو أفضل من مجموعة البيانات بأكملها 0.375 من قبل. يمكننا أيضًا التعبير عنها من حيث ما يسمى ب كسب المعلومات:

كسب المعلومات لهذا التقسيم هو 0.375 - 0.25 = 0.125.

سهل على هذا النحو. كلما زاد كسب المعلومات (أي كلما انخفضت شائبة جيني) ، كان ذلك أفضل.

ملحوظة: يمكن أن يكون الانقسام الأولي الآخر جيدًا بنفس القدر على طول المحور الصادي.

شيء مهم يجب مراعاته هو أنه مفيد وزن شوائب جيني للأجزاء بحجم الأجزاء. على سبيل المثال ، دعونا نفترض ذلك

• يتكون الجزء 1 من 50 نقطة بيانات وله شوائب جيني تبلغ 0.0 و
• الجزء 2 يتكون من 450 نقطة بيانات وله شوائب جيني 0.5 ،

يجب ألا يكون متوسط ​​شوائب جيني (0.0 + 0.5) / 2 = 0.25 بل بالأحرى 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

حسنًا ، وكيف نجد أفضل تقسيم؟ الجواب البسيط والواقعي هو:

ما عليك سوى تجربة جميع التقسيمات واختيار الجزء الذي يتمتع بأعلى قدر من المعلومات. إنها في الأساس نهج القوة الغاشمة.

لكي تكون أكثر دقة ، تستخدم أشجار القرار القياسية ينقسم على طول محاور الإحداثيات، أي سᵢ = ج لبعض الميزات i والعتبة c. وهذا يعني أن

• يتكون جزء واحد من البيانات المقسمة من جميع نقاط البيانات x مع xᵢ جو
• الجزء الآخر من كل النقاط x مع xᵢ ≥ ج.

لقد أثبتت قواعد التقسيم البسيطة هذه أنها جيدة بما يكفي في الممارسة العملية ، ولكن يمكنك بالطبع أيضًا توسيع هذا المنطق لإنشاء تقسيمات أخرى (مثل الخطوط القطرية مثل سᵢ + 2xⱼ = 3، فمثلا).

رائع ، هذه هي جميع المكونات التي نحتاجها للبدء الآن!

سنقوم بتنفيذ شجرة القرار الآن. نظرًا لأنه يتكون من عقد ، فلنعرّف ملف Node الدرجة الأولى.

from dataclasses import dataclass @dataclass
class Node: feature: int = None # feature for the split value: float = None # split threshold OR final prediction left: np.array = None # store one part of the data right: np.array = None # store the other part of the data

تعرف العقدة الميزة التي تستخدمها للتقسيم (feature) وكذلك قيمة التقسيم (value). value يستخدم أيضًا كمخزن للتنبؤ النهائي لشجرة القرار. نظرًا لأننا سنبني شجرة ثنائية ، فإن كل عقدة تحتاج إلى معرفة أطفالها الأيمن والأيسر ، كما هو مخزون في left و  right .

الآن ، لنقم بتنفيذ شجرة القرار الفعلية. أنا أجعلها متوافقة مع scikit-Learn ، ومن ثم أستخدم بعض الفصول من sklearn.base . إذا لم تكن معتادًا على ذلك ، فراجع مقالتي حول كيفية بناء نماذج متوافقة مع scikit-Learn.

دعونا ننفذ!

import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin class DecisionTreeClassifier(BaseEstimator, ClassifierMixin): def __init__(self): self.root = Node() @staticmethod def _gini(y): """Gini impurity.""" counts = np.bincount(y) p = counts / counts.sum() return (p * (1 - p)).sum() def _split(self, X, y): """Bruteforce search over all features and splitting points.""" best_information_gain = float("-inf") best_feature = None best_split = None for feature in range(X.shape[1]): split_candidates = np.unique(X[:, feature]) for split in split_candidates: left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] information_gain = self._gini(y) - ( len(X_left) / len(X) * self._gini(y_left) + len(X_right) / len(X) * self._gini(y_right) ) if information_gain > best_information_gain: best_information_gain = information_gain best_feature = feature best_split = split return best_feature, best_split def _build_tree(self, X, y): """The heavy lifting.""" feature, split = self._split(X, y) left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] if len(X_left) == 0 or len(X_right) == 0: return Node(value=np.argmax(np.bincount(y))) else: return Node( feature, split, self._build_tree(X_left, y_left), self._build_tree(X_right, y_right), ) def _find_path(self, x, node): """Given a data point x, walk from the root to the corresponding leaf node. Output its value.""" if node.feature == None: return node.value else: if x[node.feature] node.value: return self._find_path(x, node.left) else: return self._find_path(x, node.right) def fit(self, X, y): self.root = self._build_tree(X, y) return self def predict(self, X): return np.array([self._find_path(x, self.root) for x in X])

وهذا كل شيء! يمكنك أن تفعل كل الأشياء التي تحبها في scikit-Learn الآن:

dt = DecisionTreeClassifier().fit(X, y)
print(dt.score(X, y)) # accuracy # Output
# 1.0

نظرًا لأن الشجرة غير منتظمة ، فهي تتسع كثيرًا ، ومن هنا جاءت نتيجة القطار المثالية. ستكون الدقة أسوأ على البيانات غير المرئية. يمكننا أيضًا التحقق من شكل الشجرة عبر

print(dt.root) # Output (prettified manually):
# Node(
# feature=1,
# value=-0.14963454032767076,
# left=Node(
# feature=0,
# value=0.04575851730144607,
# left=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# ),
# right=Node(
# feature=None,
# value=1,
# left=None,
# right=None
# )
# ),
# right=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# )
# )

كصورة ، سيكون هذا:

صورة المؤلف

في هذه المقالة ، رأينا كيف تعمل أشجار القرار بالتفصيل. بدأنا ببعض الأفكار الغامضة ، ولكن البديهية ، وحولناها إلى صيغ وخوارزميات. في النهاية ، تمكنا من تنفيذ شجرة قرار من الصفر.

لكن كلمة تحذير: لا يمكن تنظيم شجرة قراراتنا بعد. عادة ، نود تحديد معلمات مثل

• أقصى عمق
• حجم الورقة
• والحصول على الحد الأدنى من المعلومات

من بين عدة آخرين. لحسن الحظ ، هذه الأشياء ليست بهذه الصعوبة في التنفيذ ، مما يجعل هذا واجبًا منزليًا مثاليًا بالنسبة لك. على سبيل المثال ، إذا حددت leaf_size=10 كمعامل ، ثم يجب عدم تقسيم العقد التي تحتوي على أكثر من 10 عينات بعد الآن. أيضا ، هذا التنفيذ ليست فعالة. عادةً ، لن ترغب في تخزين أجزاء من مجموعات البيانات في عقد ، ولكن فقط المؤشرات بدلاً من ذلك. لذا فإن مجموعة البيانات (التي يُحتمل أن تكون كبيرة) موجودة في الذاكرة مرة واحدة فقط.

الشيء الجيد هو أنه يمكنك أن تصاب بالجنون الآن باستخدام قالب شجرة القرار هذا. أنت تستطيع:

• تنفيذ انشقاقات قطرية ، أي سᵢ + 2xⱼ = 3 بدلا من مجرد سᵢ = 3 ،
• تغيير المنطق الذي يحدث داخل الأوراق ، أي يمكنك إجراء انحدار لوجستي داخل كل ورقة بدلاً من مجرد إجراء تصويت الأغلبية ، مما يمنحك شجرة خطية
• قم بتغيير إجراء التقسيم ، أي بدلاً من استخدام القوة الغاشمة ، جرب بعض التوليفات العشوائية واختر أفضلها ، مما يمنحك مصنف خارج الشجرة
• وأكثر من ذلك.

 
 
دكتور روبرت كوبلر هو عالم بيانات في Publicis Media ومؤلف في Towards Data Science.

 
أصلي. تم إعادة النشر بإذن.
 

• محتوى مدعوم من تحسين محركات البحث وتوزيع العلاقات العامة. تضخيم اليوم.
• بلاتوبلوكشين. Web3 Metaverse Intelligence. تضخيم المعرفة. الوصول هنا.
• المصدر https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree