خوارزمية ID3

1. احسب إنتروبيا كل سمة${\displaystyle a}$من مجموعة البيانات${\displaystyle S}$.
2. قسّم ("افصل") المجموعة${\displaystyle S}$إلى مجموعات فرعية باستخدام السمة التي يتم من خلالها تقليل الإنتروبيا الناتجة بعد التقسيم ؛ أو، بشكل مكافئ، يكون كسب المعلومات أقصى ما يمكن .
3. أنشئ عقدة في شجرة القرار تحتوي على تلك السمة.
4. قم بالتكرار على المجموعات الفرعية باستخدام السمات المتبقية.

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

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

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

يتم استخدام خوارزمية ID3 من خلال التدريب على مجموعة بيانات${\displaystyle S}$لإنتاج شجرة قرار يتم تخزينها في الذاكرة . أثناء التشغيل ، تُستخدم شجرة القرار هذه لتصنيف حالات الاختبار الجديدة ( متجهات الميزات ) من خلال اجتياز شجرة القرار باستخدام ميزات البيانات للوصول إلى عقدة طرفية.

إنتروبيا${\displaystyle \mathrm {H} {(S)}}$هو مقياس لمقدار عدم اليقين في مجموعة البيانات${\displaystyle S}$(أي أن الإنتروبيا تميز مجموعة البيانات)${\displaystyle S}$).

${\displaystyle \mathrm {H} {(S)}=\sum _{x\in X}{-p(x)\log _{2}p(x)}}$

أين،

• ${\displaystyle S}$– مجموعة البيانات الحالية التي يتم حساب الإنتروبيا لها
  • يتغير هذا في كل خطوة من خطوات خوارزمية ID3، إما إلى مجموعة فرعية من المجموعة السابقة في حالة التقسيم بناءً على سمة أو إلى قسم "شقيق" من الأصل في حالة انتهاء التكرار سابقًا.
• ${\displaystyle X}$– مجموعة الفئات في${\displaystyle S}$
• ${\displaystyle p(x)}$– نسبة عدد العناصر في الفصل${\displaystyle x}$إلى عدد العناصر في المجموعة${\displaystyle S}$

متى${\displaystyle \mathrm {H} {(S)}=0}$، المجموعة${\displaystyle S}$مصنفة بشكل مثالي (أي جميع العناصر في${\displaystyle S}$(من نفس الفئة).

في خوارزمية ID3، يتم حساب الإنتروبيا لكل سمة متبقية. وتُستخدم السمة ذات أقل إنتروبيا لتقسيم المجموعة.${\displaystyle S}$في هذه المرحلة. يقيس مفهوم الإنتروبيا في نظرية المعلومات كمية المعلومات المتوقع الحصول عليها عند قياس متغير عشوائي ؛ ولذلك، يمكن استخدامه أيضًا لتحديد مدى عدم معرفة توزيع قيم هذه الكمية. الكمية الثابتة لها إنتروبيا صفرية، لأن توزيعها معروف تمامًا . في المقابل، يُعظّم المتغير العشوائي ذو التوزيع المنتظم ( سواء كان منتظمًا بشكل منفصل أو مستمر ) قيمة الإنتروبيا. لذا، كلما زادت قيمة الإنتروبيا عند عقدة ما، قلت المعلومات المعروفة عن تصنيف البيانات في هذه المرحلة من الشجرة؛ وبالتالي، زادت إمكانية تحسين التصنيف هنا.

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

اكتساب المعلومات${\displaystyle IG(A)}$هو مقياس الفرق في الإنتروبيا قبل وبعد المجموعة${\displaystyle S}$يتم تقسيمها بناءً على سمة${\displaystyle A}$بمعنى آخر، ما مقدار عدم اليقين في${\displaystyle S}$تم تخفيضها بعد تقسيم المجموعة${\displaystyle S}$على السمة${\displaystyle A}$.

${\displaystyle IG(S,A)=\mathrm {H} {(S)}-\sum _{t\in T}p(t)\mathrm {H} {(t)}=\mathrm {H} {(S)}-\mathrm {H} {(S|A)}.}$

أين،

• ${\displaystyle \mathrm {H} (S)}$– إنتروبيا المجموعة${\displaystyle S}$
• ${\displaystyle T}$– المجموعات الجزئية الناتجة عن تقسيم المجموعة${\displaystyle S}$حسب السمة${\displaystyle A}$بحيث${\displaystyle S=\bigcup _{t\in T}t}$
• ${\displaystyle p(t)}$– نسبة عدد العناصر في${\displaystyle t}$إلى عدد العناصر في المجموعة${\displaystyle S}$
• ${\displaystyle \mathrm {H} (t)}$– إنتروبيا المجموعة الجزئية${\displaystyle t}$

في خوارزمية ID3، يمكن حساب كسب المعلومات (بدلاً من الإنتروبيا) لكل سمة متبقية. وتُستخدم السمة ذات أكبر كسب معلومات لتقسيم المجموعة.${\displaystyle S}$في هذه النسخة.