أداة تقسيم دقيقة للتصنيف الثنائي مع ميزات رقمية

في هذه الوحدة، ستستكشف خوارزمية التقسيم البسيطة والأكثر شيوعًا، التي تنشئ شروطًا للنموذج $\mathrm{feature}_i \geq t$ في الإعداد التالي:

• مهمة تصنيف ثنائية
• بدون قيم مفقودة في الأمثلة
• بدون فهرس محسوب مسبقًا على الأمثلة

افترض مجموعة من الأمثلة عن $n$ مع ميزة رقمية وتصنيف ثنائي "orange"&&;;blue". رسميًا، دعنا نوضّح أنّ مجموعة البيانات هي $D$ على النحو التالي:

$$D = \{(x_i,y_i)\}_{i\in[1,n]}$$

المكان:

• $x_i$ هي قيمة ميزة رقمية في $\mathbb{R}$ (مجموعة الأرقام الفعلية).
• $y_i$ هي قيمة تصنيف تصنيف ثنائي باللغة {orange, blue}.

هدفنا هو الوصول إلى قيمة الحد الأدنى $t$ (الحدّ الأدنى) بحيث يقسّم المثال $D$ إلى المجموعتَين $T(rue)$ و $F(alse)$ وفقًا لشرط $x_i \geq t$.

إنتروبيا الشنون هو مقياس للاضطرابات. بالنسبة إلى التصنيف الثنائي:

• تكون قيمة دخول شانون الحد الأقصى هي عندما تكون التصنيفات في الأمثلة متوازنة (50% أزرق و50% برتقالي).
• تكون قيمة إنتروبيا شانون هي الحد الأدنى (القيمة صفر) عندما تكون التصنيفات في الأمثلة صحيحة تمامًا (100% باللون الأزرق أو 100% برتقالي).

الشكل 8. ثلاثة مستويات مختلفة للانتروبيا.

 

رسميًا، نودّ العثور على شرط يقلّل من المبلغ الأوّلي لتوزيع التوزيعات في $T$ و $F$. وتتمثل النتيجة المقابلة في مكاسب المعلومات، وهي الفرق بين القيمة الدائمة لـ $D$'s و{$T$,$F$}. ويُعرف هذا الاختلاف باسم اكتساب المعلومات.

يوضّح الشكل التالي تقسيمًا سيئًا تظل فيه القيمة العالية منخفضة، وتنخفض المعلومات بعد ذلك:

الشكل 9. ولا يؤدي التقسيم السيئ إلى تقليل كفاءة التصنيف.

 

في المقابل، يُظهر الشكل التالي تقسيمًا أفضل تؤدي إلى انخفاض مستوى الإنتروبيا (وتزداد المعلومات).

الشكل 10. ويؤدي التقسيم الجيد إلى الحد من إنتصاب التصنيف.

 

رسميًا:

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

المكان:

• $IG(D,T,F)$ هي الأرباح التي يتم تحقيقها من خلال تقسيم $D$ إلى $T$ و $F$.
• إن $H(X)$ هو إنتروبيا مجموعة الأمثلة $X$.
• $|X|$ هو عدد العناصر في المجموعة $X$.
• $t$ هي قيمة الحدّ الأدنى.
• $pos$ هي قيمة التصنيف الموجبة، على سبيل المثال، "blue" في المثال أعلاه. ولا يؤدي اختيار تصنيف آخر كتصنيف و"&إيجابي" إلى تغيير "قيمة الانتخاب" أو "اكتساب المعلومات".
• $R(X)$ هي نسبة قيم التصنيفات الإيجابية في الأمثلة على $X$.
• $D$ هي مجموعة البيانات (على النحو المحدّد سابقًا في هذه الوحدة).

في المثال التالي، نأخذ في الاعتبار مجموعة بيانات التصنيف الثنائي التي تحتوي على ميزة رقمية واحدة $x$. ويوضّح الشكل التالي قيم الحدّ الأدنى مختلفة لـ $t$ (المحور س):

1. المدرّج التكراري للميزة $x$
2. تمثّل هذه السمة نسبة &&;;;;blue"example$ في الأمثلة على $D$ و$T$ و$F$ وفقًا لقيمة الحدّ الأدنى.
3. إنتروبيا بالدولار الأمريكي، $T$ و$F$.
4. وتزيد قيمة المعلومات، أي دلتا الإنترنت بين $D$ و{$T$,$F$} بالاستناد إلى عدد الأمثلة.

الشكل 11. أربع مخططات.

 

وتوضّح هذه المخططات ما يلي:

• وتوضّح مخطّطة "&&frequency&quot: أنّ الملاحظات موزّعة بشكل نسبيّ مع التركيز عليها بين 18 و60. ويشير انتشار القيمة الكبيرة إلى أنّ هناك الكثير من الأقسام المحتملة، ما يُعدّ مفيدًا لتدريب النموذج.

• تكون نسبة التصنيف "blue;blue;quot; في مجموعة البيانات حوالى %25. تُظهر "نسبة مئوية" أو "مخطّط أزرق" لقيمة الحدّ الأدنى بين 20 و50:

  • تحتوي مجموعة $T$ على أمثلة زائدة من &"blue"quot;ملاحظتَين (ما يصل إلى% 35) على الحدّ الأدنى 35).
  • تحتوي مجموعة $F$ على عيوب تكميلية في أمثلة التصنيفات، "blue"quot; . (8% فقط من الحدّ الأدنى 35).

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

• وقد تم تأكيد هذه الملاحظة في مخطّط "&الحصول على معلومات"& نلاحظ أنّ الحد الأقصى للمعلومات التي يتم الحصول عليها هو t~=28 للحصول على قيمة اكتساب معلومات ~ 0.074. وبالتالي، سيكون الشرط الذي يعرضه المقسِّم $x \geq 28$.

• وتكون قيمة اكتساب المعلومات دائمًا موجبة أو فارغة. وتتقارب من صفر إلى أن تقترب قيمة الحد الأدنى من الحد الأقصى / الحد الأدنى للقيمة. وفي هذه الحالات، يصبح حقل $F$ أو $T$ فارغًا بينما تحتوي المجموعة الأخرى على مجموعة البيانات بالكامل وتعرض نمط إنتروبيا يساوي المجموعة في $D$. يمكن أن تكون قيمة المعلومات أيضًا صفرًا عندما $H(T)$ = $H(F)$ = $H(D)$. عند الحد الأدنى 60، تكون نِسب علامة $$$ يشيران إلى قيمة$$ وأنّ قيمة $$ لبيعها لبيع المنتجات باستخدام الملف نفسه، بالإضافة إلى $

قيم المرشح لـ $t$ في مجموعة الأرقام الحقيقية ($\mathbb{R}$) هي غير محدودة. ومع ذلك، نظرًا للعدد المحدود من الأمثلة، لا يتوفّر سوى عدد محدود من الأقسام بدءًا من $D$ إلى $T$ و $F$. ولذلك، فإن عددًا محدودًا من قيم $t$ يكون مفيدًا للاختبار.

المنهج الكلاسيكي هو ترتيب القيم x_i لزيادة الترتيب x_s(i) بحيث:

$$ x_{s(i)} \leq x_{s(i+1)} $$

بعد ذلك، اختبِر $t$ لكل قيمة في المنتصف بين قيم الترتيب المتعاقبة $x_i$. على سبيل المثال، لنفترض أن لديك 1,000 قيمة نقطة عائمة لميزة معيّنة. بعد الترتيب، لنفترض أن أول قيمتين هما 8.5 و8.7. في هذه الحالة، ستكون قيمة الحد الأدنى الأولى للاختبار هي 8.6.

رسميًا، نأخذ في الاعتبار قيم المرشح التالية لـ t:

$$ X = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

تعقيد الوقت لهذه الخوارزمية هو $\mathcal{O} ( n \log n) $ مع $n$ عدد الأمثلة في العقدة (بسبب ترتيب قيم الميزات). عند التطبيق على شجرة القرارات، يتم تطبيق خوارزمية التقسيم على كل عُقدة ولكل ميزة. لاحظ أن كل عُقدة تتلقى حوالى 1/2 من الأمثلة الرئيسية. لذلك، وفقًا للنظرية الرئيسية، فإن التعقيد الزمني لتدريب شجرة القرارات باستخدام هذا التقسيم هو:

$$ \mathcal{O} ( m n \log^2 n ) $$

المكان:

• $m$ هي عدد الميزات.
• $n$ هو عدد أمثلة التدريب.

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