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 $\mathrm{feature}_i \geq t$ 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 = \{(x_i,y_i)\}_{i\in[1,n]}$$

gdzie:

• $x_i$ to wartość funkcji liczbowej w $\mathbb{R}$ (zestawie prawdziwych liczb).
• $y_i$ 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 $x_i \geq t$, 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).

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ść:

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:

\[\begin{eqnarray} T & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \ge t \} \\[12pt] F & = & \{ (x_i,y_i) | (x_i,y_i) \in D \ \textrm{with} \ x_i \lt t \} \\[12pt] R(X) & = & \frac{\lvert \{ x | x \in X \ \textrm{and} \ x = \mathrm{pos} \} \rvert}{\lvert X \rvert} \\[12pt] H(X) & = & - p \log p - (1 - p) \log (1-p) \ \textrm{with} \ p = R(X)\\[12pt] IG(D,T,F) & = & H(D) - \frac {\lvert T\rvert} {\lvert D \rvert } H(T) - \frac {\lvert F \rvert} {\lvert D \rvert } H(F) \end{eqnarray}\]

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.

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 ($\mathbb{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 x_i w kolejności rosnącej x_s(i), tak aby:

$$ x_{s(i)} \leq x_{s(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 = \left\{ \frac {x_{s(i)} + x_{s(i + 1)}} {2} \lvert x_{s(i)} \ne x_{s(i+1)} \right\} $$

Czas złożoności tego algorytmu wynosi $\mathcal{O} ( n \log n) $ 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:

$$ \mathcal{O} ( m n \log^2 n ) $$

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.