خوارزمية شجرة القرار

أعاد نشره أفلاطون

المتابعون: 0

تم نشر هذه المقالة كجزء من مدونة علوم البيانات

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

المحتويات

1. ما هي شجرة القرار؟

2. مثال لشجرة القرار

3. الانتروبيا

4. اكتساب المعلومات

5. متى تتوقف عن الانقسام؟

6. كيف تتوقف عن فرط تجهيز؟

أقصى عمق
min_samples_split
min_samples_leaf
ماكس_ميزات

7. التقليم

بعد التقليم
التقليم المسبق

8. الهوامش

ما هي شجرة القرار؟

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

صورة 1

قبل معرفة المزيد عن أشجار القرار ، دعونا نتعرف على بعض المصطلحات.

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

عقد القرار - العقد التي نحصل عليها بعد تقسيم العقد الجذرية تسمى عقدة القرار

العقد الورقية - العقد التي لا يمكن فيها المزيد من الانقسام تسمى العقد الورقية أو العقد الطرفية

الشجرة الفرعية - تمامًا مثل جزء صغير من الرسم البياني يسمى الرسم البياني الفرعي وبالمثل يسمى القسم الفرعي من شجرة القرار هذه الشجرة الفرعية.

تشذيب - ليس سوى قطع بعض العقد لوقف فرط التجهيز.

صورة 2

مثال على شجرة القرار

دعونا نفهم أشجار القرار بمساعدة مثال.

صورة 3

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

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

صورة 4

هل لاحظت أي شيء في المخطط الانسيابي أعلاه؟ نرى ذلك إذا كان الطقس غائم ثم يجب أن نذهب للعب. لماذا لم ينقسم أكثر؟ لماذا توقفت عند هذا الحد؟

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

الهدف من التعلم الآلي هو تقليل عدم اليقين أو الاضطرابات من مجموعة البيانات ولهذا ، نستخدم أشجار القرار.

الآن يجب أن تفكر في كيفية معرفة ما يجب أن تكون عقدة الجذر؟ ماذا يجب أن تكون عقدة القرار؟ متى يجب أن أتوقف عن الانقسام؟ لتحديد ذلك ، يوجد مقياس يسمى "إنتروبيا" وهو مقدار عدم اليقين في مجموعة البيانات.

الكون

الانتروبيا ليست سوى عدم اليقين في مجموعة بياناتنا أو مقياس الاضطراب. اسمحوا لي أن أحاول شرح ذلك بمساعدة مثال.

افترض أن لديك مجموعة من الأصدقاء يقررون الفيلم الذي يمكنهم مشاهدته معًا يوم الأحد. هناك خياران للأفلام ، أحدهما "لوسي" والثاني هو "تيتانيك" والآن على الجميع أن يخبروا باختيارهم. بعد أن يعطي الجميع إجابتهم نرى ذلك "لوسي" تحصل على 4 أصوات و "تايتانيك" تحصل على 5 أصوات. أي فيلم نشاهده الآن؟ أليس من الصعب اختيار فيلم واحد الآن لأن الأصوات لكلا الفيلمين متساوية إلى حد ما.

هذا هو بالضبط ما نسميه الفوضى ، هناك عدد متساوٍ من الأصوات لكلا الفيلمين ، ولا يمكننا تحديد الفيلم الذي يجب أن نشاهده. كان من الأسهل بكثير أن تكون الأصوات لـ "لوسي" 8 أصوات و "تايتانيك" كانت 2. هنا يمكننا أن نقول بسهولة أن غالبية الأصوات لصالح "لوسي" وبالتالي سيشاهد الجميع هذا الفيلم.

في شجرة القرار ، يكون الناتج في الغالب "نعم" أو "لا"

معادلة الانتروبيا موضحة أدناه:

هنا ص₊ هو احتمال وجود فئة موجبة

p_- هو احتمال الطبقة السالبة

S هي مجموعة فرعية من مثال التدريب

كيف تستخدم أشجار القرار الانتروبيا؟

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

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

لنفترض أ ميزة تحتوي على 8 "نعم" و4 "لا" في البداية، بعد التقسيم الأول للعقدة اليسرى يحصل على 5 "نعم" و 2 "لا" بينما العقدة اليمنى يحصل على 3 "نعم" و 2 "لا".

ونحن نرى هنا أن الانقسام ليس طاهرا، لماذا؟ لأنه لا يزال بإمكاننا رؤية بعض الفئات السلبية في كلتا العقدتين. من أجل عمل شجرة قرار، نحتاج إلى حساب نقاء كل انقسام، وعندما تكون النقاء 100%، نجعلها على شكل عقدة ورقية.

للتحقق من شوائب الميزة 2 والميزة 3 ، سنأخذ المساعدة الخاصة بصيغة Entropy.

مصدر الصورة: المؤلف

للميزة 3 ،

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

تذكر دائمًا أنه كلما ارتفع الانتروبيا ، كلما قلت درجة النقاء وزادت النجاسة.

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

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

كسب المعلومات

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

الحصول على المعلومات خوارزمية شجرة القرار

إنها مجرد إنتروبيا لمجموعة البيانات الكاملة - إنتروبيا مجموعة البيانات مع إعطاء بعض الميزات.

لفهم هذا بشكل أفضل ، دعنا نفكر في مثال:
لنفترض أن مجتمعنا بأكمله يحتوي على إجمالي 30 مثيلاً. تهدف مجموعة البيانات إلى التنبؤ بما إذا كان الشخص سيذهب إلى صالة الألعاب الرياضية أم لا. لنفترض أن 16 شخصًا يذهبون إلى صالة الألعاب الرياضية و 14 شخصًا لا يذهبون

الآن لدينا ميزتان للتنبؤ بما إذا كان سيذهب إلى صالة الألعاب الرياضية أم لا.

الميزة 1 هي "الطاقة" الذي يأخذ قيمتين "عالي و منخفض"

الميزة 2 هي "التحفيز" الذي يأخذ 3 قيم "لا يوجد دافع" ، "محايد" و "شديد الدافع".

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

مصدر الصورة: المؤلف

دعنا نحسب الانتروبيا:

لمعرفة المتوسط المرجح للإنتروبيا لكل عقدة ، سنفعل ما يلي:

الآن لدينا قيمة E (الأصل) و E (الأصل | الطاقة) ، سيكون اكتساب المعلومات:

كان الانتروبيا الأصلية قريبة من 0.99 وبعد النظر إلى هذه القيمة لكسب المعلومات ، يمكننا القول أن إنتروبيا مجموعة البيانات ستنخفض بمقدار 0.37 إذا جعلنا "الطاقة" بمثابة عقدة الجذر الخاصة بنا.

وبالمثل ، سنفعل ذلك مع الميزة الأخرى "التحفيز" ونحسب اكتساب المعلومات.

مصدر الصورة: المؤلف

دعنا نحسب الانتروبيا هنا:

لمعرفة المتوسط المرجح للإنتروبيا لكل عقدة ، سنفعل ما يلي:

الآن لدينا قيمة E (الوالد) و E (الوالد | الدافع) ، اكتساب المعلومات سيكون:

نرى الآن أن ميزة "الطاقة" تعطي مزيدًا من التخفيض وهو 0.37 من ميزة "التحفيز". ومن ثم سنقوم بتحديد الميزة التي لديها أعلى مكاسب للمعلومات ثم نقوم بتقسيم العقدة بناءً على هذه الميزة.

التقسيم النهائي | خوارزمية شجرة القرار — مصدر الصورة: المؤلف

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

متى تتوقف عن الانقسام؟

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

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

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

هناك المزيد من المعلمات التشعبية مثل:

min_samples_leaf - يمثل الحد الأدنى لعدد العينات المطلوبة في العقدة الطرفية. كلما زادت العدد ، زادت إمكانية التجهيز الزائد.

ماكس_ميزات - يساعدنا في تحديد عدد الميزات التي يجب وضعها في الاعتبار عند البحث عن أفضل تقسيم.

لقراءة المزيد عن هذه المعلمات التشعبية يمكنك قراءتها هنا.

تشذيب

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

هناك طريقتان رئيسيتان للتقليم:

(i) التقليم المسبق - يمكننا التوقف عن زراعة الشجرة في وقت مبكر ، مما يعني أنه يمكننا تقليم / إزالة / قطع عقدة إذا كانت ذات أهمية منخفضة أثناء النمو الشجرة.

(الثاني) بعد التقليم - مرة واحدة لدينا الشجرة مبنية على عمقها، يمكننا البدء في تقليم العقد بناءً على أهميتها.

التعليقات الختامية

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

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

اسمحوا لي أن أعرف إذا كان لديك أي استفسارات في التعليقات أدناه.

عن المؤلف

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

أنا منفتح على التعاون والعمل.

لأي شك واستفسارات ، لا تتردد في الاتصال بي البريد إلكتروني:

تواصل معي على لينكدين: و تويتر

الوسائط الموضحة في هذه المقالة ليست مملوكة لشركة Analytics Vidhya ويتم استخدامها وفقًا لتقدير المؤلف.