Algoritmul ID3
Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . |
ID3 ( Iterative Dichotomiser 3 ) este un algoritm lacom pentru inducerea arborilor de decizie .
Algoritmul
Noțiuni de bază
Arborele este construit într-un mod de sus în jos folosind o politică cunoscută sub numele de divide et impera (împărțirea unei probleme în subprobleme mai mici). Algoritm:
- Începem cu un copac format doar din rădăcină, la rădăcina căreia sunt atribuite toate instanțele de antrenament.
- Se alege un atribut (algoritmul ID3 îl alege prin intermediul „câștigului informațional” și nu al raportului de câștig).
- Se creează atâtea noduri (copii ai rădăcinii), cu cât există valori posibile ale atributului ales. În acest caz, instanțele de instruire sunt atribuite copilului corespunzător
- Procedăm recursiv folosind noile noduri ca rădăcini.
Etapele definite mai sus sunt potrivite pentru majoritatea algoritmilor de inducere a arborelui decizional, modificați metoda prin care este ales atributul. Cu toate acestea, scopul este întotdeauna de a obține un arbore mic și precis.
Condiții de oprire
Algoritmul se oprește dacă:
- toate instanțele unui nod aparțin aceleiași clase, în acest caz nodul devine o frunză cu clasa atribuită corespunzătoare.
- nu mai există atribute pe care să împărțiți arborele, în acest caz nodul devine o frunză căreia i se atribuie cea mai comună clasă dintre instanțele atribuite acestuia.
Pseudo cod
Pseudocodul [1] al algoritmului ID3 pentru funcțiile booleene este raportat aici.
Exemple: = instanțe de instruire.
Target_Attribute: = atributul a cărui valoare este prezisă de arbore.
Atribute: = lista altor atribute.
ID3 (Exemple, Target_Attribute, Attributes)
Creați un nod Root.
Dacă toate exemplele sunt pozitive
returnează un copac cu un singur nod rădăcină și etichetează = +
Dacă toate exemplele sunt negative
returnează un copac cu un singur nod Rădăcină și etichetă = -
Dacă atributele sunt goale
returnează un copac cu un singur nod Rădăcină și etichetă = cea mai comună valoare Target_Auto dintre instanțele din exemple.
In caz contrar
A ← Elementul atributelor care reduce cel mai mult entropia.
Pentru fiecare valoare v a lui A,
Adăugați o nouă ramură sub Root corespunzătoare testului A = v.
Exemple (v) ← subset de exemple care au valoare v pentru A.
Dacă Exemplele (v) sunt goale
Adăugați o frunză cu etichetă = valoarea celui mai comun atribut de obiectiv dintre exemple.
In caz contrar
Adăugați subarborele ID3 sub Root (Exemple (v), Target_Attribute, Attributes - {A}).
Return Root.
Clasele sau distribuțiile de probabilitate
Alternativ, în loc să atribuiți o clasă unui nod, puteți atribui distribuția de probabilitate a atributului clasei, în raport cu instanțele atribuite acestuia. Exemplu: dacă 3 instanțe sunt atribuite ultimului nod, cu clasele da, da și respectiv nu, atribuim nodului distribuția probabilității p astfel încât p (da) = 2/3 și p (nu) = 1/3.
Proprietăți și limite
ID3 returnează un singur arbore de decizie, în concordanță cu setul de date transmis ca intrare. Nu este garantat că această soluție este singura sau că este cea optimă, deoarece ID3 poate converge chiar și la minimele locale: pentru a depăși această problemă, poate fi utilizată tehnica de backtracking , care însă nu apare în formularea originală a algoritmul.
În schimb, pentru a preveni problema depășirii , algoritmul trebuie oprit înainte ca toate atributele să fie procesate, preferând arborii de decizie mai mici ca soluții. O abordare alternativă, utilizată în algoritmul C4.5 (succesorul ID3), este tehnica post-tăiere: algoritmul nu este oprit în timpul execuției, permițând astfel și supra-montarea și numai la sfârșitul său se aplică regulile de tăiere la îmbunătățirea abilităților de generalizare.
O altă dificultate este gestionarea atributelor cu valoare continuă, cum ar fi numerele reale . ID3 nu prevede nici măcar posibilitatea de a atribui ponderi atributelor și nici nu permite atribute lipsă.
Notă
- ^ (EN) M- Tom Mitchell, Machine Learning, McGraw-Hill Science, 1 martie 1997, ISBN 0070428077 .
