ED-4.2-m08-1.0-Slajd18
Zysk informacyjny (1)
Inną popularną grupą algorytmów indukcji drzew decyzyjnych są algorytmy, które do oceny punktu podziału wykorzystują kryterium zysku informacyjnego. Do tej grupy algorytmów należą takie popularne algorytmy jak algorytm ID3 oraz algorytm C 4.5. W algorytmach tych punktem podziału jest cały atrybut. Problem konstrukcji drzewa decyzyjnego przy użyciu miary zysku informacyjnego może być przedstawiony następująco. Najpierw zostaje wybrany atrybut, który jest korzeniem drzewa decyzyjnego. Dla każdej wartości wybranego atrybutu tworzona jest gałąź w tym drzewie decyzyjnym, z którą będzie związany zbiór rekordów posiadający tą samą wartość wybranego atrybutu. Następnie proces partycjonowania jest powtarzany dla każdej partycji związanej z każdą gałęzią. Jeżeli wszystkie rekordy podanego węzła należą do tej samej klasy, proces partycjonowania jest zakończony, dalszy podział węzłów jest niepotrzebny. Jeżeli nie, wówczas proces partycjonowania zbioru rekordów związany z daną gałęzią jest kontynuowany. W jaki sposób wybieramy atrybut związany z punktem podziału. Taki atrybut będziemy nazywać atrybutem testowym. Jako atrybut testowy (aktualny wierzchołek drzewa decyzyjnego) wybieramy atrybut o największym zysku informacyjnym (lub największej redukcji entropii). Z teorii informacji okazuje się, że atrybut który gwarantuje największy zysk informacyjny jest to atrybut, który który minimalizuje ilość informacji niezbędnej do klasyfikacji przykładów w partycjach uzyskanych w wyniku podziału.
