W tej jednostce poznasz najprostszy i najpopularniejszy algorytm podziału, który tworzy warunki w postaci w następującym ustawieniu:
- Zadanie klasyfikacji plików binarnych
- Brak wartości w przykładach
- Przykłady bez wstępnie obliczonego indeksu
Załóżmy, że zbiór przykładów zawiera funkcję liczbową i etykietę binarną "orange" "blue". Formalnie określamy zbiór danych jako:
gdzie:
- to wartość funkcji liczbowej w (zestawie prawdziwych liczb).
- to wartość etykiety klasyfikacji binarnej w {orange, blue}.
Naszym celem jest znalezienie wartości progowej (próg), która pozwoli podzielić przykłady w grupach i zgodnie z warunkami , np. bardziej oddalonych etykiet, np. blue i .
Entropia shannona jest miarą zaburzeń. W przypadku etykiety binarnej:
- Entropia Shannon jest maksymalna, gdy etykiety w przykładach są równoważone (50% niebieskiego i 50% pomarańczowy).
- Entropia Shannon ma minimalną wartość (wartość zero), gdy etykiety w przykładach są puste (100% niebieski lub 100% pomarańczowy).
Rysunek 8. Trzy różne poziomy entropii.
Formalnie chcemy znaleźć warunek, który zmniejsza ważoną sumę entropii rozkładów etykiet w i . Odpowiedni wynik to wzrost informacji, czyli różnica między entropią ' a entropią {,}. Różnica ta nosi nazwę wzrostu informacji.
Poniższy diagram pokazuje nieprawidłowy podział, przy czym entropia pozostaje wysoka, a informacje tracą ważność:
Rysunek 9. Nieprawidłowy podział nie zmniejsza entropii etykiety.
Dla kontrastu przedstawiony niżej obraz lepiej obrazuje, kiedy entropia staje się coraz słaba (a informacja staje się wysoka):
Rysunek 10. Dobry podział pozwala zmniejszyć entropię etykiety.
Oficjalnie:
gdzie:
- to zysk z informacji wynikowy z podziału na i .
- to entropia zbioru przykładów .
- to liczba elementów w zestawie .
- to wartość progowa.
- to wartość etykiety dodatniej, np. "niebieski" w powyższym przykładzie. Wybór innej etykiety na &etykietę dodatnią nie zmienia wartości entropii ani wzrostu ilości informacji.
- to współczynnik dodatnich wartości etykiet w przykładach: .
- to zbiór danych (zdefiniowany wcześniej w tej jednostce).
W tym przykładzie bierzemy pod uwagę zbiór klasyfikacji binarnej z pojedynczą funkcją liczbową . Poniższa wartość pokazuje różne wartości progowe (oś X):
- Histogram funkcji .
- Stosunek "niebieski" przykładów w zbiorach , i zgodnie z wartością progową.
- Entropia w , i .
- Przyrost informacji – delta entropii między a {,} ważoną według liczby przykładów.
Rysunek 11. Cztery fazy.
Te wykresy przedstawiają następujące kwestie:
- Na wykresie &częstotliwość wskazuje, że obserwacje są dosyć rozłożone w zakresie od 18 do 60. Szeroki zakres wartości oznacza, że w projekcie może być dużo potencjalnych podziałów. To dobre rozwiązanie do trenowania modelu.
Współczynnik "blue" w zbiorze danych wynosi ok. 25%. &Wykres niebieskiej etykiety pokazuje, że dla wartości progowych z zakresu od 20 do 50:
- Zestaw zawiera przykłady etykiet "blue" (do 35% w progu 35).
- Zestaw zawiera uzupełniający deficyt słów kluczowych „"blue"” (tylko 8% dla progu 35).
&"współczynnik niebieskich etykiet i wykresów "entropy" wskazują, że w tym zakresie progowym etykiety mogą być stosunkowo rozdzielane.
Te obserwacje potwierdzają fabułę. Uzyskujemy maksymalny przyrost informacji z wartością t~=28 dla wartości informacji o wartości ~0,074. Warunek zwracany przez funkcję podziału to 28 USD \geq 28$.
Przyrost informacji jest zawsze dodatni lub pusty. Zbiega się do zera, gdy wartość progowa zbiega się z maksymalną / minimalną wartością. W takich przypadkach lub stają się puste, a drugi zawiera cały zbiór danych i wskazuje entropię równą tej, która wynosi . Wartość informacji może wynosić 0 także wtedy, gdy = = . W przypadku wartości 60 obie wartości $&; ilość to jednocześnie
Wartości proponowane dla w zestawie rzeczywistych wartości () są nieskończone. Jednak z ukończoną liczbą przykładów istnieje tylko skończona liczba podziałów w wynikach i . Dlatego w testach sprawdza się tylko ograniczona liczba wartości .
Klasycznym podejściem jest sortowanie wartości xi w kolejności rosnącej xs(i), tak aby:
Następnie przetestuj dla każdej wartości w połowie drogi między posortowanymi wartościami po 1000 zł. Załóżmy na przykład, że masz 1000 wartości zmiennoprzecinkowych konkretnej funkcji. Po posortowaniu Załóżmy, że pierwsze 2 wartości to 8,5 i 8,7. W tym przypadku pierwsza wartość progowa do sprawdzenia będzie wynosiła 8, 6.
Formalnie bierzemy pod uwagę te wartości kandydatów:
Czas złożoności tego algorytmu wynosi z liczbą przykładów w węźle (ze względu na sortowanie wartości cech). Po zastosowaniu do drzewa decyzji algorytm podziału jest stosowany do każdego węzła i każdej cechy. Pamiętaj, że każdy węzeł otrzymuje ok. 1/2 przykładów nadrzędnych. Zgodnie z twierdzeniem nadrzędnym czas złożoności trenowania drzewa decyzyjnego za pomocą tego rozdzielacza jest taki:
gdzie:
- to liczba funkcji.
- to liczba przykładów trenowania.
W tym algorytmie wartość funkcji nie ma znaczenia, istotne są jedynie ich kolejność. Z tego powodu algorytm działa niezależnie od skali i rozkładu wartości cech. Dlatego nie musimy normalizować ani skalować funkcji liczbowych podczas trenowania drzewa decyzji.