Precyzyjny podział na potrzeby klasyfikacji binarnej z funkcjami liczbowymi

W tej jednostce poznasz najprostszy i najpopularniejszy algorytm podziału, który tworzy warunki w postaci featureit 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 n zawiera funkcję liczbową i etykietę binarną "orange" "blue". Formalnie określamy zbiór danych D jako:

D={(xi,yi)}i[1,n]

gdzie:

  • xi to wartość funkcji liczbowej w R (zestawie prawdziwych liczb).
  • yi to wartość etykiety klasyfikacji binarnej w {orange, blue}.

Naszym celem jest znalezienie wartości progowej t (próg), która pozwoli podzielić przykłady D w grupach T(rue) i F(alse) zgodnie z warunkami xit, np. bardziej oddalonych etykiet, np. t blue i t.

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).

Trzy diagramy. Wysoki entropia pokazuje dużo kombinacji dwóch różnych klas. Schemat niskich wpisów obrazuje 2 różne klasyki. Diagram entropijny nie zawiera połączenia 2 różnych klas, czyli brak entropii tylko w 1 klasie.

Rysunek 8. Trzy różne poziomy entropii.

 

Formalnie chcemy znaleźć warunek, który zmniejsza ważoną sumę entropii rozkładów etykiet w T i F. Odpowiedni wynik to wzrost informacji, czyli różnica między entropią D&#39 a entropią {T,F}. Różnica ta nosi nazwę wzrostu informacji.

Poniższy diagram pokazuje nieprawidłowy podział, przy czym entropia pozostaje wysoka, a informacje tracą ważność:

Dwa diagramy, z których dwa są niemal identyczne w 2 różnych klasach.

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):

Dwa diagramy. Jeden diagram składa się z około 95% klasy pomarańczowej i 5% klasy niebieskiej. Drugi diagram odpowiada około 95% klasy niebieskiej i 5% klasy pomarańczowej.

Rysunek 10. Dobry podział pozwala zmniejszyć entropię etykiety.

 

Oficjalnie:

T={(xi,yi)|(xi,yi)D with xit}F={(xi,yi)|(xi,yi)D with xi<t}R(X)=|{x|xX and x=pos}||X|H(X)=plogp(1p)log(1p) with p=R(X)IG(D,T,F)=H(D)|T||D|H(T)|F||D|H(F)

gdzie:

  • IG(D,T,F) to zysk z informacji wynikowy z podziału D na T i F.
  • H(X) to entropia zbioru przykładów X.
  • |X| to liczba elementów w zestawie X.
  • t to wartość progowa.
  • pos 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.
  • R(X) to współczynnik dodatnich wartości etykiet w przykładach: X.
  • D 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ą x. Poniższa wartość pokazuje różne wartości progowe t (oś X):

  1. Histogram funkcji x.
  2. Stosunek "niebieski" przykładów w zbiorach D, T i F zgodnie z wartością progową.
  3. Entropia w D, T i F.
  4. Przyrost informacji – delta entropii między D a {T,F} ważoną według liczby przykładów.

Cztery rzędy
wartości progowych w porównaniu z innymi parametrami. Lista poniżej przedstawia
podsumowanie każdego z tych działek.

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 T zawiera przykłady etykiet "blue" (do 35% w progu 35).
    • Zestaw F zawiera uzupełniający deficyt słów kluczowych „"blue"” (tylko 8% dla progu 35).

    &"współczynnik niebieskich etykiet i wykresów "entropy&quot 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 F lub T stają się puste, a drugi zawiera cały zbiór danych i wskazuje entropię równą tej, która wynosi D. Wartość informacji może wynosić 0 także wtedy, gdy H(T) = H(F) = H(D). W przypadku wartości 60 obie wartości $&; ilość to jednocześnie

Wartości proponowane dla t w zestawie rzeczywistych wartości (R) są nieskończone. Jednak z ukończoną liczbą przykładów istnieje tylko skończona liczba podziałów w wynikach D i F. Dlatego w testach sprawdza się tylko ograniczona liczba wartości t.

Klasycznym podejściem jest sortowanie wartości xi w kolejności rosnącej xs(i), tak aby:

xs(i)xs(i+1)

Następnie przetestuj t 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:

X={xs(i)+xs(i+1)2|xs(i)xs(i+1)}

Czas złożoności tego algorytmu wynosi O(nlogn) z n 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:

O(mnlog2n)

gdzie:

  • m to liczba funkcji.
  • n 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.