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

تعمل الخوارزميات الخاصة بإنشاء أشجار من أعلى لأسفل، عن طريق اختيار متغير في كل خطوة تقسم مجموعة العناصر على أفضل نحو. تستخدم خوارزميات مختلفة مقاييس مختلفة لقياس «الأفضل». تعتمد معظم الأشجار على إنتروبيا أو مؤشر جيني (بالإنجليزية: Gini index)‏ لتقسيم البيانات. تعتمد العديد من الأشجار المعروفة، مثل C4.5 و ID3،[2][3] على الانتروبيا. يتم تعريف الانتروبي على النحو التالي:

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

حيث p1 ، p2 ،... هي الكسور التي تضيف ما يصل إلى 1 وتمثل النسبة المئوية لكل تصنيف (أو فئة) موجودة في العقدة الفرعية الناتجة عن انقسام في الشجرة و يسمى المتغير I_E كسب المعلومات.[4]

ولحساب شوائب جيني لمجموعة من العناصر مع J تصانيف، افترض i∈ {1,2 ،... ، J} ، ودع p_i هو جزء صغير من العناصر المسمى تصنيف i في المجموعة.[4]

${\displaystyle \operatorname {I} _{G}(p)=\sum _{i=1}^{J}p_{i}\sum _{k\neq i}p_{k}=\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}}$

• بوابة علم الحاسوب