ED-4.2-m07-1.0-Slajd20
Algorytm konstrukcji drzewa (1)
Przejdźmy obecnie do przedstawienia algorytmu konstrukcji drzewa decyzyjnego. Prezentowany na slajdzie algorytm konstruuje binarne drzewo decyzyjne. Nie jest to algorytm ogólny, gdyż niektóre algorytmy klasyfikacji metodą indukcji drzew decyzyjnych konstruują drzewa decyzyjne, które nie są binarne, niemniej algorytm ten dobrze ilustruje mechanizm konstrukcji drzewa decyzyjnego. Podstawową procedurą prezentowanego algorytmu jest procedura Make Tree(Training Data D), której argumentem wejściowym jest cały zbiór danych treningowych D. Procedura Make Tree wywołuje procedurę Partition, której na początku parametrem wejściowym jest zbiór danych treningowych D. Budowa drzewa rozpoczyna się od pojedynczego węzła/wierzchołka zwanego korzeniem (root N node) reprezentującego treningową bazę danych D. Jeśli wszystkie krotki w D należą do tej samej klasy C, wówczas, węzeł N staje się liściem z etykietą C, i algorytm kończy swoje działanie. W przeciwnym razie, zbiór atrybutów A jest sprawdzany zgodnie z metodą selekcji podziału (split selection) SS i wybierany jest atrybut podziału zwany „best-split”. Atrybut podziału partycjonuje/dzieli zbiór treningowy D na zbiór oddzielnej klasy próbek S1, S2, ... Sv, gdzie Si=1,..,v zawiera wszystkie próbki ze zbioru D razem z punktem podziału. Gałąź, z etykietą Vi, jest tworzona dla każdej wartości ai atrybutu podziału, i dla każdej gałęzi Vi przydzielony jest zbiór próbek. Procedura partycjonowania jest powtarzana rekurencyjnie dla każdego węzła/wierzchołka potomka, przez co jest formowane drzewo decyzyjne dla każdej partycji przykładów. Procedura się kończy gdy każda z partycji jest „czysta” (zawiera dane należące wyłącznie do jednej klasy) lub liczba elementów partycji dostatecznie mała (spada poniżej pewnego zadanego progu).
