تعلم شجرة القرار

جزء من سلسلة عن
التعلم الآلي واستخراج البيانات
النماذج التعلم تحت الإشراف التعلم غير الخاضع للإشراف التعلم شبه الخاضع للإشراف التعلم الذاتي التعلم التعزيزي التعلم الفوقي التعلم عبر الإنترنت التعلم الدفعي التعلم المنهجي التعلم المبني على القواعد الذكاء الاصطناعي الرمزي العصبي الهندسة العصبية التعلم الآلي الكمومي
المشاكل تصنيف النمذجة التوليدية الانحدار التجميع تخفيض الأبعاد تقدير الكثافة كشف الشذوذ تنظيف البيانات التعلم الآلي التلقائي قواعد الجمعية التحليل الدلالي التنبؤ المنظم هندسة المميزات ميزة التعلم تعلم الترتيب الاستدلال النحوي التعلم الأنطولوجيا التعلم المتعدد الوسائط
التعلم الخاضع للإشراف ( التصنيف  • الانحدار ) Apprenticeship learning Decision trees Ensembles Bagging Boosting Random forest k-NN Linear regression Naive Bayes Artificial neural networks Logistic regression Perceptron Relevance vector machine (RVM) Support vector machine (SVM)
Clustering BIRCH CURE Hierarchical k-means Fuzzy Expectation–maximization (EM) DBSCAN OPTICS Mean shift
Dimensionality reduction Factor analysis CCA ICA LDA NMF PCA PGD t-SNE SDL
Structured prediction Graphical models Bayes net Conditional random field Hidden Markov
Anomaly detection RANSAC k-NN Local outlier factor Isolation forest
Artificial neural network Autoencoder Deep learning Feedforward neural network Recurrent neural network LSTM GRU ESN reservoir computing Boltzmann machine Restricted GAN Diffusion model SOM Convolutional neural network U-Net LeNet AlexNet DeepDream Neural radiance field Transformer Vision Mamba Spiking neural network Memtransistor Electrochemical RAM (ECRAM)
Reinforcement learning Q-learning SARSA Temporal difference (TD) Multi-agent Self-play
Learning with humans Active learning Crowdsourcing Human-in-the-loop RLHF
Model diagnostics Coefficient of determination Confusion matrix Learning curve ROC curve
Mathematical foundations Kernel machines Bias–variance tradeoff Computational learning theory Empirical risk minimization Occam learning PAC learning Statistical learning VC theory
Journals and conferences ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Related articles Glossary of artificial intelligence List of datasets for machine-learning research List of datasets in computer vision and image processing Outline of machine learning
v t e

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

تُسمى نماذج الأشجار حيث يمكن للمتغير المستهدف أن يأخذ مجموعة منفصلة من القيم بأشجار التصنيف ؛ في هياكل الأشجار هذه، تمثل الأوراق تسميات الفئة وتمثل الفروع اقترانات الميزات التي تؤدي إلى تسميات الفئة هذه. تُسمى أشجار القرار حيث يمكن للمتغير المستهدف أن يأخذ قيمًا مستمرة (عادةً أرقامًا حقيقية ) بأشجار الانحدار . بشكل عام، يمكن توسيع مفهوم شجرة الانحدار ليشمل أي نوع من الكائنات المجهزة باختلافات زوجية مثل التسلسلات الفئوية. ^[1]

تُعد أشجار القرار من بين خوارزميات التعلم الآلي الأكثر شيوعًا نظرًا لسهولة فهمها وبساطتها. ^[2]

في تحليل القرار، يمكن استخدام شجرة القرار لتمثيل القرارات وصنع القرار بصريًا وبشكل واضح . في استخراج البيانات ، تصف شجرة القرار البيانات (ولكن يمكن أن تكون شجرة التصنيف الناتجة مدخلاً لصنع القرار).

تعلم شجرة القرار هو أسلوب يستخدم عادة في استخراج البيانات. ^[3] والهدف هو إنشاء نموذج يتنبأ بقيمة متغير مستهدف بناءً على العديد من متغيرات الإدخال.

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

يتم بناء الشجرة عن طريق تقسيم مجموعة المصدر ، التي تشكل العقدة الجذرية للشجرة، إلى مجموعات فرعية - والتي تشكل الأبناء الخلفاء. يعتمد التقسيم على مجموعة من قواعد التقسيم بناءً على ميزات التصنيف. ^[4] تتكرر هذه العملية على كل مجموعة فرعية مشتقة بطريقة متكررة تسمى التقسيم المتكرر . تكتمل التكرار عندما تحتوي المجموعة الفرعية في العقدة على جميع القيم نفسها للمتغير المستهدف، أو عندما لا يضيف التقسيم قيمة إلى التنبؤات. تُعد عملية الاستحثاث من أعلى إلى أسفل لأشجار القرار (TDIDT) ^[5] مثالاً على خوارزمية الجشع ، وهي حتى الآن الاستراتيجية الأكثر شيوعًا لتعلم أشجار القرار من البيانات. ^[6]

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

تأتي البيانات في سجلات بالشكل:

${\displaystyle ({\textbf {x}},Y)=(x_{1},x_{2},x_{3},...,x_{k},Y)}$

المتغير التابع، هو المتغير المستهدف الذي نحاول فهمه أو تصنيفه أو تعميمه. يتكون المتجه من السمات وما إلى ذلك المستخدمة لهذه المهمة. ${\displaystyle Y}$${\displaystyle {\textbf {x}}}$${\displaystyle x_{1},x_{2},x_{3}}$

تنقسم أشجار القرار المستخدمة في تعدين البيانات إلى نوعين رئيسيين:

• تحليل شجرة التصنيف هو عندما تكون النتيجة المتوقعة هي الفئة (المنفصلة) التي تنتمي إليها البيانات.
• تحليل شجرة الانحدار هو عندما يمكن اعتبار النتيجة المتوقعة رقمًا حقيقيًا (على سبيل المثال سعر المنزل، أو مدة إقامة المريض في المستشفى).

مصطلح تحليل شجرة التصنيف والانحدار (CART) هو مصطلح شامل يستخدم للإشارة إلى أي من الإجراءات المذكورة أعلاه، وقد قدمه لأول مرة بريمان وآخرون في عام 1984. ^[7] الأشجار المستخدمة في الانحدار والأشجار المستخدمة في التصنيف لها بعض أوجه التشابه - ولكن أيضًا بعض الاختلافات، مثل الإجراء المستخدم لتحديد مكان الانقسام. ^[7]

بعض التقنيات، والتي غالبًا ما تسمى بأساليب المجموعة ، تقوم ببناء أكثر من شجرة قرار واحدة:

• الأشجار المعززة: بناء مجموعة تدريجيًا من خلال تدريب كل مثيل جديد للتأكيد على مثيلات التدريب التي تم نمذجتها بشكل خاطئ سابقًا. ومن الأمثلة النموذجية على ذلك AdaBoost . ويمكن استخدام هذه الأشجار في مشاكل النوع الانحداري ونوع التصنيف. ^{[8] [9]}
• لجان أشجار القرار (وتسمى أيضًا k-DT ^[10] )، وهي طريقة مبكرة تستخدم خوارزميات شجرة القرار العشوائية لتوليد أشجار متعددة مختلفة من بيانات التدريب، ثم دمجها باستخدام التصويت بالأغلبية لتوليد الناتج. ^[11]
• إن أشجار القرار المجمعة (أو المعبأة) باستخدام Bootstrap، وهي طريقة تجميع مبكرة، تبني أشجار قرار متعددة من خلال إعادة أخذ عينات متكررة من بيانات التدريب مع الاستبدال ، والتصويت على الأشجار للتنبؤ بالإجماع. ^[12]
  • مصنف الغابة العشوائية هو نوع محدد من التجميع التمهيدي
• غابة الدوران - حيث يتم تدريب كل شجرة قرار من خلال تطبيق تحليل المكونات الأساسية (PCA) أولاً على مجموعة فرعية عشوائية من ميزات الإدخال. ^[13]

حالة خاصة من شجرة القرار هي قائمة القرار ، ^[14] وهي شجرة قرار أحادية الجانب، بحيث تحتوي كل عقدة داخلية على عقدة ورقية واحدة بالضبط وعقدة داخلية واحدة بالضبط كطفل (باستثناء العقدة الأدنى، التي يكون طفلها الوحيد عقدة ورقية واحدة). على الرغم من كونها أقل تعبيرًا، إلا أن قوائم القرار أسهل في الفهم من أشجار القرار العامة بسبب ندرتها المضافة ^{[ بحاجة لمصدر ]} ، مما يسمح بفرض أساليب التعلم غير الجشعة ^[15] والقيود الرتيبة. ^[16]

تتضمن خوارزميات شجرة القرار البارزة ما يلي:

• ID3 (التقسيم التكراري 3)
• C4.5 (خليفة ID3)
• CART (شجرة التصنيف والانحدار) ^[7]
• OC1 (المصنف المائل 1). أول طريقة أنشأت تقسيمات متعددة المتغيرات عند كل عقدة. ^[17]
• الكشف التلقائي عن التفاعلات باستخدام مربع كاي (CHAID). يقوم بإجراء تقسيمات متعددة المستويات عند حساب أشجار التصنيف. ^{[18] [19] [20]}
• MARS : توسيع أشجار القرار للتعامل مع البيانات الرقمية بشكل أفضل.
• أشجار الاستدلال الشرطية. نهج قائم على الإحصائيات يستخدم الاختبارات غير المعيارية كمعايير تقسيم، مع تصحيحها للاختبارات المتعددة لتجنب الإفراط في التجهيز. يؤدي هذا النهج إلى اختيار تنبؤ غير متحيز ولا يتطلب التقليم. ^{[21] [22]}

تم اختراع ID3 وCART بشكل مستقل في نفس الوقت تقريبًا (بين عامي 1970 و1980) ^{[ بحاجة لمصدر ]} ، إلا أنهما يتبعان نهجًا مشابهًا لتعلم شجرة القرار من تدريب الثنائيات.

وقد تم اقتراح الاستفادة من مفاهيم نظرية المجموعة الضبابية لتحديد نسخة خاصة من شجرة القرار، والمعروفة باسم شجرة القرار الضبابية (FDT). ^[23] في هذا النوع من التصنيف الضبابي، يرتبط متجه الإدخال عمومًا بفئات متعددة، ولكل منها قيمة ثقة مختلفة. كما تم مؤخرًا التحقيق في مجموعات معززة من FDTs، وقد أظهرت أداءً مماثلًا لأداء المصنفات الضبابية الأخرى عالية الكفاءة. ^[24]${\displaystyle {\textbf {x}}}$

عادةً ما تعمل الخوارزميات المستخدمة في بناء أشجار القرار من أعلى إلى أسفل، وذلك باختيار متغير في كل خطوة يقسم مجموعة العناصر على أفضل نحو. ^[6] وتستخدم الخوارزميات المختلفة مقاييس مختلفة لقياس "الأفضل". وتقيس هذه المقاييس عمومًا تجانس المتغير المستهدف داخل المجموعات الفرعية. وفيما يلي بعض الأمثلة. وتُطبق هذه المقاييس على كل مجموعة فرعية مرشحة، ويتم الجمع بين القيم الناتجة (على سبيل المثال، المتوسط) لتوفير مقياس لجودة التقسيم. واعتمادًا على المقياس الأساسي، قد يختلف أداء الخوارزميات الاستدلالية المختلفة لتعلم شجرة القرار بشكل كبير. ^[25]

يمكن استخدام مقياس بسيط وفعال لتحديد الدرجة التي تتفوق بها النتائج الإيجابية الحقيقية على النتائج الإيجابية الكاذبة (انظر مصفوفة الارتباك ). يتم تعريف هذا المقياس، "تقدير صحة النتائج الإيجابية"، أدناه:

${\displaystyle E_{P}=TP-FP}$

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

ميزة مصفوفة الارتباك

الفصل المتوقع الصف الفعلي	سرطان	غير سرطاني
سرطان	8	3
غير سرطاني	2	5

هنا يمكننا أن نرى أن قيمة TP ستكون 8 وقيمة FP ستكون 2 (الأرقام المسطرة في الجدول). عندما نقوم بإدخال هذه الأرقام في المعادلة، نتمكن من حساب التقدير: . وهذا يعني أن استخدام التقدير على هذه الميزة سيجعلها تحصل على درجة 6. ${\displaystyle E_{p}=TP-FP=8-2=6}$

ومع ذلك، تجدر الإشارة إلى أن هذا الرقم هو مجرد تقدير. على سبيل المثال، إذا كان لكل من ميزتين قيمة FP تبلغ 2 بينما كانت إحدى الميزتين لها قيمة TP أعلى، فسيتم تصنيف هذه الميزة أعلى من الأخرى لأن التقدير الناتج عند استخدام المعادلة سيعطي قيمة أعلى. قد يؤدي هذا إلى بعض عدم الدقة عند استخدام المقياس إذا كانت بعض الميزات تحتوي على عينات أكثر إيجابية من غيرها. لمكافحة هذا، يمكن للمرء استخدام مقياس أكثر قوة يُعرف باسم الحساسية والذي يأخذ في الاعتبار نسب القيم من مصفوفة الارتباك لإعطاء معدل الإيجابية الحقيقي الفعلي (TPR). يظهر الفرق بين هذه المقاييس في المثال أدناه:

ميزة مصفوفة الارتباك الفصل المتوقع الصف الفعلي سرطان غير سرطاني سرطان 8 3 غير سرطاني 2 5	مصفوفة الارتباك للميزة ب الفصل المتوقع الصف الفعلي سرطان غير سرطاني سرطان 6 2 غير سرطاني 2 8
${\displaystyle E_{p}=TP-FP=8-2=6}$ ${\displaystyle TPR=TP/(TP+FN)=8/(8+3)\approx 0.73}$	${\displaystyle E_{p}=TP-FP=6-2=4}$ ${\displaystyle TPR=TP/(TP+FN)=6/(6+2)=0.75}$

في هذا المثال، كان تقدير الميزة أ 6 وTPR حوالي 0.73 بينما كان تقدير الميزة ب 4 وTPR 0.75. يوضح هذا أنه على الرغم من أن التقدير الإيجابي لبعض الميزات قد يكون أعلى، إلا أن قيمة TPR الأكثر دقة لتلك الميزة قد تكون أقل عند مقارنتها بميزات أخرى لها تقدير إيجابي أقل. بناءً على الموقف ومعرفة البيانات وأشجار القرار، قد يختار المرء استخدام التقدير الإيجابي لحل سريع وسهل لمشكلته. من ناحية أخرى، من المرجح أن يفضل المستخدم الأكثر خبرة استخدام قيمة TPR لترتيب الميزات لأنها تأخذ في الاعتبار نسب البيانات وجميع العينات التي كان يجب تصنيفها على أنها إيجابية.

شوائب جيني ، مؤشر جيني للتنوع ، ^[26] أو مؤشر جيني-سيمبسون في أبحاث التنوع البيولوجي، سمي على اسم عالم الرياضيات الإيطالي كورادو جيني ويستخدمه خوارزمية CART (شجرة التصنيف والانحدار) لأشجار التصنيف. تقيس شوائب جيني عدد المرات التي يتم فيها تصنيف عنصر تم اختياره عشوائيًا من مجموعة بشكل غير صحيح إذا تم تصنيفه عشوائيًا ومستقلًا وفقًا لتوزيع العلامات في المجموعة. يصل إلى أدنى حد له (صفر) عندما تقع جميع الحالات في العقدة في فئة هدف واحدة.

بالنسبة لمجموعة من العناصر ذات الفئات والترددات النسبية ، فإن احتمال اختيار عنصر يحمل تسمية هو ، واحتمال تصنيف هذا العنصر بشكل خاطئ هو . يتم حساب شوائب جيني عن طريق جمع حاصل ضرب أزواج هذه الاحتمالات لكل تسمية فئة: ${\displaystyle J}$${\displaystyle p_{i}}$${\displaystyle i\in \{1,2,...,J\}}$${\displaystyle i}$${\displaystyle p_{i}}$${\displaystyle \sum _{k\neq i}p_{k}=1-p_{i}}$

${\displaystyle \operatorname {I} _{G}(p)=\sum _{i=1}^{J}\left(p_{i}\sum _{k\neq i}p_{k}\right)=\sum _{i=1}^{J}p_{i}(1-p_{i})=\sum _{i=1}^{J}(p_{i}-p_{i}^{2})=\sum _{i=1}^{J}p_{i}-\sum _{i=1}^{J}p_{i}^{2}=1-\sum _{i=1}^{J}p_{i}^{2}.}$

إن شوائب جيني هي أيضًا مقياس نظري للمعلومات وتتوافق مع إنتروبيا تساليس مع معامل التشوه ، والذي يرتبط في الفيزياء بنقص المعلومات في الأنظمة غير المتوازنة وغير الشاملة والمبددة والكمية. بالنسبة للحد، يتم استعادة إنتروبيا بولتزمان-جيبس أو شانون المعتادة. بهذا المعنى، فإن شوائب جيني ليست سوى اختلاف في مقياس الإنتروبيا المعتاد لأشجار القرار. ${\displaystyle q=2}$${\displaystyle q\to 1}$

تستخدمه خوارزميات إنشاء الشجرة ID3 و C4.5 وC5.0. يعتمد اكتساب المعلومات على مفهوم الإنتروبيا ومحتوى المعلومات من نظرية المعلومات .

يتم تعريف الإنتروبيا على النحو التالي

${\displaystyle \mathrm {H} (T)=\operatorname {I} _{E}\left(p_{1},p_{2},\ldots ,p_{J}\right)=-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}}$

حيث هي كسور يصل مجموعها إلى 1 وتمثل النسبة المئوية لكل فئة موجودة في العقدة الفرعية التي تنتج عن انقسام في الشجرة. ^[27]${\displaystyle p_{1},p_{2},\ldots }$

$${\displaystyle \overbrace {IG(T,a)} ^{\text{information gain}}=\overbrace {\mathrm {H} (T)} ^{\text{entropy (parent)}}-\overbrace {\mathrm {H} (T\mid a)} ^{\text{sum of entropies (children)}}}$$${\displaystyle =-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}-\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

المتوسط ​​على القيم الممكنة لـ ، ${\displaystyle A}$

$${\displaystyle \overbrace {E_{A}(\operatorname {IG} (T,a))} ^{\text{expected information gain}}=\overbrace {I(T;A)} ^{{\text{mutual information between }}T{\text{ and }}A}=\overbrace {\mathrm {H} (T)} ^{\text{entropy (parent)}}-\overbrace {\mathrm {H} (T\mid A)} ^{\text{weighted sum of entropies (children)}}}$$${\displaystyle =-\sum _{i=1}^{J}p_{i}\log _{2}p_{i}-\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

حيث يتم إعطاء المجموع المرجح للإنتروبيا بواسطة،

${\displaystyle {\mathrm {H} (T\mid A)}=\sum _{a}p(a)\sum _{i=1}^{J}-\Pr(i\mid a)\log _{2}\Pr(i\mid a)}$

وهذا يعني أن اكتساب المعلومات المتوقع هو المعلومات المتبادلة ، أي أن الانخفاض في إنتروبيا T في المتوسط ​​هو المعلومات المتبادلة.

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

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

لإيجاد مكسب المعلومات للتقسيم باستخدام windy ، يجب علينا أولاً حساب المعلومات الموجودة في البيانات قبل التقسيم. تحتوي البيانات الأصلية على تسع إجابات بنعم وخمس إجابات بلا.

${\displaystyle I_{E}([9,5])=-{\frac {9}{14}}\log _{2}{\frac {9}{14}}-{\frac {5}{14}}\log _{2}{\frac {5}{14}}=0.94}$

يؤدي الانقسام باستخدام الخاصية windy إلى عقدتين فرعيتين، واحدة لقيمة windy true والأخرى لقيمة windy false. في مجموعة البيانات هذه، توجد ست نقاط بيانات بقيمة windy true ، ثلاث منها لها قيمة play (حيث play هو المتغير المستهدف) yes وثلاث لها قيمة play no. تحتوي نقاط البيانات الثماني المتبقية بقيمة windy false على عقدتين لا وست عقد نعم. يتم حساب معلومات عقدة windy =true باستخدام معادلة الإنتروبيا أعلاه. نظرًا لوجود عدد متساوٍ من العقد التي تحتوي على نعم ولا في هذه العقدة، لدينا

${\displaystyle I_{E}([3,3])=-{\frac {3}{6}}\log _{2}{\frac {3}{6}}-{\frac {3}{6}}\log _{2}{\frac {3}{6}}=-{\frac {1}{2}}\log _{2}{\frac {1}{2}}-{\frac {1}{2}}\log _{2}{\frac {1}{2}}=1}$

بالنسبة للعقدة حيث windy =false، كان هناك ثماني نقاط بيانات، ست نقاط إيجابية واثنين سلبية. وبالتالي، لدينا

${\displaystyle I_{E}([6,2])=-{\frac {6}{8}}\log _{2}{\frac {6}{8}}-{\frac {2}{8}}\log _{2}{\frac {2}{8}}=-{\frac {3}{4}}\log _{2}{\frac {3}{4}}-{\frac {1}{4}}\log _{2}{\frac {1}{4}}=0.81}$

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

${\displaystyle I_{E}([3,3],[6,2])=I_{E}({\text{windy or not}})={\frac {6}{14}}\cdot 1+{\frac {8}{14}}\cdot 0.81=0.89}$

الآن يمكننا حساب مكسب المعلومات الذي تم تحقيقه عن طريق الانقسام على الميزة العاصفة .

${\displaystyle \operatorname {IG} ({\text{windy}})=I_{E}([9,5])-I_{E}([3,3],[6,2])=0.94-0.89=0.05}$

لبناء الشجرة، يجب حساب اكتساب المعلومات لكل تقسيم أول ممكن. أفضل تقسيم أول هو الذي يوفر أكبر قدر من اكتساب المعلومات. تتكرر هذه العملية لكل عقدة غير نقية حتى تكتمل الشجرة. هذا المثال مقتبس من المثال الذي ظهر في Witten et al. ^[27]

يُعرف اكتساب المعلومات أيضًا باسم مؤشر شانون في أبحاث التنوع البيولوجي.

تم تقديم تقليل التباين في CART ^[7] ، وغالبًا ما يتم استخدامه في الحالات التي يكون فيها المتغير المستهدف مستمرًا (شجرة الانحدار)، مما يعني أن استخدام العديد من المقاييس الأخرى يتطلب أولاً التقطيع قبل تطبيقها. يتم تعريف تقليل التباين لعقدة N على أنه التخفيض الإجمالي لتباين المتغير المستهدف Y بسبب الانقسام في هذه العقدة:

${\displaystyle I_{V}(N)={\frac {1}{|S|^{2}}}\sum _{i\in S}\sum _{j\in S}{\frac {1}{2}}(y_{i}-y_{j})^{2}-\left({\frac {|S_{t}|^{2}}{|S|^{2}}}{\frac {1}{|S_{t}|^{2}}}\sum _{i\in S_{t}}\sum _{j\in S_{t}}{\frac {1}{2}}(y_{i}-y_{j})^{2}+{\frac {|S_{f}|^{2}}{|S|^{2}}}{\frac {1}{|S_{f}|^{2}}}\sum _{i\in S_{f}}\sum _{j\in S_{f}}{\frac {1}{2}}(y_{i}-y_{j})^{2}\right)}$

حيث أن و و و هي مجموعة مؤشرات العينة المقسمة مسبقًا، ومجموعة مؤشرات العينة التي يكون اختبار التقسيم صحيحًا فيها، ومجموعة مؤشرات العينة التي يكون اختبار التقسيم خاطئًا فيها، على التوالي. كل من المجاميع المذكورة أعلاه هي في الواقع تقديرات تباين ، على الرغم من كتابتها في نموذج دون الإشارة مباشرة إلى المتوسط. ${\displaystyle S}$${\displaystyle S_{t}}$${\displaystyle S_{f}}$

من خلال استبدال الاختلاف بين كائنين في الصيغة أعلاه و ، فإن معيار تقليل التباين ينطبق على أي نوع من الكائنات التي يمكن حساب الاختلافات الزوجية لها. ^[1]${\displaystyle (y_{i}-y_{j})^{2}}$${\displaystyle d_{ij}}$${\displaystyle i}$${\displaystyle j}$

تم استخدام مقياس "الجودة" بواسطة CART في عام 1984، ^[28] وهو عبارة عن دالة تسعى إلى تحسين توازن قدرة الانقسام المرشح على إنشاء أطفال نقيين مع قدرته على إنشاء أطفال متساويي الحجم. تتكرر هذه العملية لكل عقدة غير نقية حتى تكتمل الشجرة. يتم تعريف الدالة ، حيث هو انقسام مرشح عند العقدة ، على النحو التالي ${\displaystyle \varphi (s\mid t)}$${\displaystyle s}$${\displaystyle t}$

${\displaystyle \varphi (s\mid t)=2P_{L}P_{R}\sum _{j=1}^{\text{class count}}|P(j\mid t_{L})-P(j\mid t_{R})|}$

حيث و هما الطفلان الأيسر والأيمن للعقدة باستخدام split ، على التوالي؛ و هما نسب السجلات في in و ، على التوالي؛ و و هما نسب سجلات الفئة في و ، على التوالي. ${\displaystyle t_{L}}$${\displaystyle t_{R}}$${\displaystyle t}$${\displaystyle s}$${\displaystyle P_{L}}$${\displaystyle P_{R}}$${\displaystyle t}$${\displaystyle t_{L}}$${\displaystyle t_{R}}$${\displaystyle P(j\mid t_{L})}$${\displaystyle P(j\mid t_{R})}$${\displaystyle j}$${\displaystyle t_{L}}$${\displaystyle t_{R}}$

لنأخذ مثالاً لمجموعة بيانات تحتوي على ثلاث سمات: المدخرات (منخفضة، متوسطة، عالية)، والأصول (منخفضة، متوسطة، عالية)، والدخل (القيمة العددية)، ومتغير هدف ثنائي لمخاطر الائتمان (جيد، سيء) و8 نقاط بيانات. ^[28] يتم تقديم البيانات الكاملة في الجدول أدناه. لبدء شجرة القرار، سنحسب القيمة القصوى لاستخدام كل ميزة للعثور على الميزة التي ستقسم العقدة الجذرية. ستستمر هذه العملية حتى تصبح جميع العناصر الفرعية نقية أو تكون جميع القيم أقل من عتبة محددة. ${\displaystyle \varphi (s\mid t)}$${\displaystyle \varphi (s\mid t)}$

عميل	الادخار	أصول	الدخل (1000 دولار)	مخاطر الائتمان
1	واسطة	عالي	75	جيد
2	قليل	قليل	50	سيء
3	عالي	واسطة	25	سيء
4	واسطة	واسطة	50	جيد
5	قليل	واسطة	100	جيد
6	عالي	عالي	25	جيد
7	قليل	قليل	25	سيء
8	واسطة	واسطة	75	جيد

لإيجاد ميزة الادخار ، نحتاج إلى ملاحظة كمية كل قيمة. تحتوي البيانات الأصلية على ثلاثة مستويات منخفضة وثلاثة مستويات متوسطة ومستوىين مرتفعين. من بين المستويات المنخفضة، كان لدى واحد مخاطر ائتمانية جيدة بينما من بين المستويات المتوسطة والمرتفعة، كان لدى 4 مستويات مخاطر ائتمانية جيدة . افترض تقسيم المرشح بحيث يتم وضع السجلات ذات المدخرات المنخفضة في الطفل الأيسر وسيتم وضع جميع السجلات الأخرى في الطفل الأيمن. ${\displaystyle \varphi (s\mid t)}$${\displaystyle s}$

${\displaystyle \varphi (s\mid {\text{root}})=2\cdot {\frac {3}{8}}\cdot {\frac {5}{8}}\cdot \left(\left|\left({\frac {1}{3}}-{\frac {4}{5}}\right)\right|+\left|\left({\frac {2}{3}}-{\frac {1}{5}}\right)\right|\right)=0.44}$

لبناء الشجرة، يجب حساب "جودة" جميع الانقسامات المرشحة للعقدة الجذرية. سيقسم المرشح ذو القيمة القصوى العقدة الجذرية، وستستمر العملية لكل عقدة غير نقية حتى اكتمال الشجرة.

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

من بين طرق استخراج البيانات الأخرى، تتمتع أشجار القرار بمزايا مختلفة:

• سهلة الفهم والتفسير. يتمكن الأشخاص من فهم نماذج شجرة القرار بعد شرح موجز. يمكن أيضًا عرض الأشجار بيانيًا بطريقة يسهل على غير الخبراء تفسيرها. ^[29]
• قادرة على التعامل مع البيانات الرقمية والفئوية . [ ^29] عادةً ما تتخصص التقنيات الأخرى في تحليل مجموعات البيانات التي تحتوي على نوع واحد فقط من المتغيرات. (على سبيل المثال، لا يمكن استخدام قواعد العلاقة إلا مع المتغيرات الاسمية بينما لا يمكن استخدام الشبكات العصبية إلا مع المتغيرات الرقمية أو الفئات المحولة إلى قيم 0-1.) كانت أشجار القرار المبكرة قادرة فقط على التعامل مع المتغيرات الفئوية، ولكن الإصدارات الأحدث، مثل C4.5، لا تحتوي على هذا القيد. ^[3]
• تتطلب القليل من تحضير البيانات. غالبًا ما تتطلب التقنيات الأخرى تطبيع البيانات. نظرًا لأن الأشجار يمكنها التعامل مع المتنبئين النوعيين، فلا توجد حاجة لإنشاء متغيرات وهمية . ^[29]
• يستخدم نموذج الصندوق الأبيض أو الصندوق المفتوح ^[3] . إذا كان من الممكن ملاحظة موقف معين في نموذج، فإن تفسير الحالة يمكن تفسيره بسهولة من خلال المنطق البولياني . على النقيض من ذلك، في نموذج الصندوق الأسود ، يكون تفسير النتائج عادةً صعب الفهم، على سبيل المثال مع الشبكة العصبية الاصطناعية .
• من الممكن التحقق من صحة النموذج باستخدام الاختبارات الإحصائية. وهذا يجعل من الممكن حساب موثوقية النموذج.
• نهج غير معياري لا يفترض بيانات التدريب أو بقايا التنبؤ؛ على سبيل المثال، لا توجد افتراضات توزيعية أو استقلالية أو تباين ثابت
• يعمل بشكل جيد مع مجموعات البيانات الكبيرة. يمكن تحليل كميات كبيرة من البيانات باستخدام موارد الحوسبة القياسية في وقت معقول.
• الدقة باستخدام النمذجة المرنة . يمكن تطبيق هذه الأساليب على أبحاث الرعاية الصحية بدقة متزايدة. ^[30]
• يعكس عملية اتخاذ القرار البشري بشكل أكثر دقة من الأساليب الأخرى. ^[29] يمكن أن يكون هذا مفيدًا عند نمذجة القرارات/السلوك البشري.
• قوي ضد التوازي الخطي، وخاصة التعزيز.
• في اختيار الميزات المضمنة . سيتم استخدام الميزات غير ذات الصلة الإضافية بشكل أقل بحيث يمكن إزالتها في عمليات التشغيل اللاحقة. يعكس التسلسل الهرمي للسمات في شجرة القرار أهمية السمات. ^[31] وهذا يعني أن الميزات الموجودة في الأعلى هي الأكثر إفادة. ^[32]
• يمكن لأشجار القرار تقريب أي دالة منطقية مثل XOR . ^[33]

• يمكن أن تكون الأشجار غير قوية للغاية. يمكن أن يؤدي التغيير الصغير في بيانات التدريب إلى تغيير كبير في الشجرة وبالتالي التنبؤات النهائية. ^[29]
• من المعروف أن مشكلة تعلم شجرة القرار المثلى هي مشكلة كاملة من نوع NP في العديد من جوانب المثالية وحتى بالنسبة للمفاهيم البسيطة. ^{[34] [35]} وبالتالي، فإن خوارزميات تعلم شجرة القرار العملية تعتمد على الاستدلالات مثل الخوارزمية الجشعة حيث يتم اتخاذ القرارات المثلى محليًا عند كل عقدة. لا يمكن لهذه الخوارزميات ضمان إرجاع شجرة القرار المثلى عالميًا. لتقليل التأثير الجشع للمثالية المحلية، تم اقتراح بعض الأساليب مثل شجرة المسافة المعلوماتية المزدوجة (DID). ^[36]
• يمكن لمتعلمي شجرة القرار إنشاء أشجار معقدة للغاية لا يمكن تعميمها جيدًا من بيانات التدريب. (يُعرف هذا بالملاءمة المفرطة . ^[37] ) تعد آليات مثل التقليم ضرورية لتجنب هذه المشكلة (باستثناء بعض الخوارزميات مثل نهج الاستدلال الشرطي، الذي لا يتطلب التقليم). ^{[21] [22]}
• لا يُضمن أن يكون متوسط ​​عمق الشجرة الذي يتم تحديده من خلال عدد العقد أو الاختبارات حتى التصنيف ضئيلاً أو صغيراً بموجب معايير التقسيم المختلفة. ^[38]
• بالنسبة للبيانات التي تتضمن متغيرات فئوية بأعداد مختلفة من المستويات، فإن اكتساب المعلومات في أشجار القرار منحاز لصالح السمات ذات المستويات الأعلى. ^[39] لمواجهة هذه المشكلة، بدلاً من اختيار السمة ذات أعلى اكتساب للمعلومات ، يمكن للمرء اختيار السمة ذات أعلى نسبة اكتساب للمعلومات بين السمات التي يكون اكتساب المعلومات فيها أكبر من متوسط ​​اكتساب المعلومات. ^[40] يؤدي هذا إلى تحيز شجرة القرار ضد النظر في السمات ذات عدد كبير من القيم المميزة، مع عدم إعطاء ميزة غير عادلة للسمات ذات اكتساب المعلومات المنخفض جدًا. بدلاً من ذلك، يمكن تجنب مشكلة اختيار المتنبئ المتحيز من خلال نهج الاستدلال الشرطي، ^{[21] أو} نهج من مرحلتين، ^[41] أو اختيار ميزة استبعاد واحدة متكيف. ^[42]

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

تتضمن أمثلة المصدر المفتوح ما يلي:

• ALGLIB ، مكتبة تحليل عددي بلغات C++ وC# وJava مع ميزات تحليل البيانات (الغابة العشوائية)
• KNIME ، منصة تحليلات البيانات وإعداد التقارير والتكامل (أشجار القرار والغابات العشوائية) مجانية ومفتوحة المصدر
• Orange ، مجموعة أدوات مفتوحة المصدر لتصور البيانات والتعلم الآلي واستخراج البيانات (غابة عشوائية)
• R (بيئة برمجية مفتوحة المصدر للحوسبة الإحصائية، والتي تتضمن العديد من تطبيقات CART مثل حزم rpart وparty وrandomForest)،
• scikit-learn (مكتبة تعلُّم آلي مجانية ومفتوحة المصدر للغة البرمجة Python ).
• Weka (مجموعة أدوات تعدين بيانات مجانية ومفتوحة المصدر، تحتوي على العديد من خوارزميات شجرة القرار)،

البرمجيات التجارية البارزة:

• ماتلاب​
• Microsoft SQL Server ، و
• رابيدماينر ،
• برنامج SAS Enterprise Miner ،
• نموذج IBM SPSS

في شجرة القرار، تستمر جميع المسارات من العقدة الجذرية إلى العقدة الورقية عن طريق الاقتران، أو AND . في رسم بياني للقرار، من الممكن استخدام عمليات الفصل (ORs) لربط مسارين آخرين معًا باستخدام الحد الأدنى لطول الرسالة (MML). ^[43] تم توسيع رسوم القرار بشكل أكبر للسماح بتعلم السمات الجديدة غير المعلنة سابقًا بشكل ديناميكي واستخدامها في أماكن مختلفة داخل الرسم البياني. ^[44] ينتج عن مخطط الترميز الأكثر عمومية دقة تنبؤية أفضل وتسجيل احتمالي لخسارة اللوغاريتم. ^{[ بحاجة لمصدر ]} بشكل عام، تستنتج رسوم القرار نماذج ذات أوراق أقل من أشجار القرار.

تم استخدام الخوارزميات التطورية لتجنب القرارات المثلى المحلية والبحث في مساحة شجرة القرار مع القليل من التحيز المسبق . ^{[45] [46]}

من الممكن أيضًا أخذ عينات من شجرة باستخدام MCMC . ^[47]

يمكن البحث عن الشجرة بطريقة تصاعدية. ^[48] أو يمكن إنشاء عدة أشجار بالتوازي لتقليل عدد الاختبارات المتوقعة حتى التصنيف. ^[38]

• جيمس، جاريث؛ ويتن، دانييلا؛ هاستي، تريفور؛ تيبشيراني، روبرت (2017). "الأساليب القائمة على الأشجار" (PDF) . مقدمة إلى التعلم الإحصائي: مع التطبيقات في R. نيويورك: سبرينغر. ص  303- 336. ISBN 978-1-4614-7137-0.

• التعلم التطوري لأشجار القرار في لغة C++
• شرح مفصل للغاية لكسب المعلومات كمعيار تقسيم