Zmniejszanie wymiarowości przestrzeni poprzez selekcje cech

W przypadku selekcji cech, dokonuje się wyboru możliwie najmniejszego podzbioru zbioru cech wejściowych \((d<p)\), tak aby zoptymalizować pewną funkcję kryterialną

\[\{x_{i_1},\ldots,x_{i_d}\}=\mathop{\rm argmax}_{d, i_d}\left(J\left(\{x_i|i=1,\ldots p\}\right)\right).\]

Ponieważ przeszukiwanie wszystkich podzbiorów przestrzeni cech jest w praktyce zadaniem niemożliwym do zrealizowania, dlatego też dla realizacji zadania selekcji cech ustala się funkcję kryterialną oceniającą ,,dobroć’’ wybranych cech oraz odpowiednią strategię przeszukiwania. Jako funkcję kryterialną często wykorzystuje się miary informacyjne oceniające stopień separowalności klas i wybierające te cechy, które mogą to zapewnić. W tym przypadku każda cecha oceniana jest osobno. Na tej podstawie powstaje ranking, z którego wybieramy cechy z najwyższych miejsc. Metody bazujące na takim podejściu nazywamy filtrami. Przykładami najczęściej stosowanych filtrów są filtry bazujące na korelacji, takie jak: t-test, algorytm RelieF; filtry bazujące na rozkładach prawdopodobieństwa takie jak: miara Kołmogorowa, miara Bayesa, Kullbacka-Leiblera, Jeffreysa-Matusita, czy filtry bazujące na entropii takie jak miara Mantrasa, miara J. Innym podejściem jest wykorzystanie klasyfikatora w procesie oceny podzbioru cech. Mówimy wówczas o wrapperach. Często spotykane jest na przykład zastosowanie metody RFE wraz z klasyfikatorem SVM, lub klasyfikatora kNN wraz z metodą leave-one-out do oceny jego sprawności. Procedura selekcji cech z wykorzystaniem klasyfikatora jest uzależniona od liczebności zbiorów oraz od rodzaju wybranego klasyfikatora. Ze względu na rodzaj strategii przeszukiwania wyróżnia się algorytmy wykładnicze takie jak przeszukiwanie wyczerpujące oraz branch & bound, sekwencyjnego dodawania lub usuwania cech w procesie przeszukiwania jak Sequential Forward Selection (SFS), Sequential Backward Selection (SBS), Sequential Floating Forward Selection (SFFS) czy algorytmy stochastyczne.

Algorytmy sekwencyjne

W algorytmach sekwencyjnych dokonuje się sekwencyjnego dodawania lub usuwania cech w procesie przeszukiwania. Takie algorytmy zazwyczaj uzyskują rozwiązania stanowiące minima lokalne. Przykładami w tej grupie algorytmów są sekwencyjne selekcja postępująca, ang. sequential forward selection (SFS), sekwencyjne selekcja wsteczna, ang. sequential backward selection (SBS) oraz sequential floating forward/backward selection (SFFS/SFBS). W przypadku metody SFS algorytm startuje od pustego zbioru cech \(A_0=\emptyset\) i w każdym kolejnym kroku dodaje jedną, najbardziej znaczącą cechę \(a^+\) tzn

\[A_{k+1}=A_k \cup a^+.\]

Dodawana cecha maksymalizuje pewną funkcję kryterialną \(J\) a dokładnie powoduje największy przyrost wartości funkcji kryterialnej \(J\)

\[a^+ = \mathop{\rm argmax}_{a\notin A_k}\left(J(A_k\cup a)\right)\]

Najczęściej wartością funkcji kryterialnej jest sprawność klasyfikatora na dotychczas znalezionym podzbiorze cech wraz z dodaną nową cechą. Algorytm SFS kończy działanie, gdy dodanie następnej cechy z pośród tych jeszcze nie dodanych powoduje pogorszenie wartości funkcji kryterialnej lub po osiągnięciu zamierzonej liczby cech w zbiorze. Pseudokod algorytmu SFS przedstawiony został poniżej.

Algorytm 10 Regresja SFS

Dane: zbiór uczący \(X_{train}=\{(x_i,y_i):x_i\in X, y_i\in C=\{-1,1\}\}\), \(J\) - funkcja kryterialna, \(p\) - liczba wszystkich cech

Wyniki: \(S\) - podzbiór cech

  1.  \(S=\emptyset\)
  2.  \(J_{max}=0\)
  3.  \(\mathbf{for} \ a_i\notin S \ \mathbf{do}\)
  4.  \(\qquad\) Oblicz \(J(S\cup \{a_i\})\).
  5.  \(J_{max}=\max_{1,\ldots, p}(J(S\cup\{a_i\})),\, a_{max}=\mathop{\rm argmax}_{1,\ldots, p}(J(S\cup\{a_i\}))\)
  6.  \(\mathbf{if} \ J\geq J_{max} \ \mathbf{then}\)
  7.  \(\qquad\) zakończ działanie algorytmu
  8.  \(\mathbf{else}\)
  9.  \(\qquad S=S\cup\{a_{max}\}, p=p-1\)
  10.  \(\mathbf{if} \ p=0 \ \mathbf{then}\)
  11.  \(\qquad\) zakończ działanie algorytmu
  12.  \(\mathbf{else}\)
  13.  \(\qquad\) Przejdź do pkt 4.

W odwrotny sposób działa algorytm SBS. Zaczynając od pełnego zbioru cech, w każdym kroku usuwa ze zbioru cech jedną cechę, maksymalizując pewną funkcję kryterialną \(J\). Poniżej przedstawiony jest pseudokod algorytmu SBS.

Algorytm 11 Regresja SBS

Dane: zbiór uczący \(X_{train}=\{(x_i,y_i):x_i\in X, y_i\in C=\{-1,1\}\}\), \(J\) - funkcja kryterialna, \(p\) - liczba wszystkich cech

Wyniki: \(S\) - podzbiór cech

  1.  \(S=\emptyset\)
  2.  \(J_{max}=0\)
  3.  \(\mathbf{for} \ a_i\notin S \ \mathbf{do}\)
  4.  \(\qquad\) Oblicz \(J(S\cup \{a_i\})\).
  5.  \(J_{max}=\max_{1,\ldots, p}(J(S\cup\{a_i\})),\, a_{max}=\mathop{\rm argmax}_{1,\ldots, p}(J(S\cup\{a_i\}))\)
  6.  \(\mathbf{if} \ J\geq J_{max} \ \mathbf{then}\)
  7.  \(\qquad\) zakończ działanie algorytmu
  8.  \(\mathbf{else}\)
  9.  \(\qquad S=S\cup\{a_{max}\}, p=p-1\)
  10.  \(\mathbf{if} \ p=0 \ \mathbf{then}\)
  11.  \(\qquad\) zakończ działanie algorytmu
  12.  \(\mathbf{else}\)
  13.  \(\qquad\) Przejdź do pkt 4.

Przykład 12

Rozważmy zbiór danych Iris. W zbiorze znajduje się 150 obiektów z trzech różnych gatunków irysów, a każdy z nich jest charakteryzowany przez cztery cechy: długość (w \(cm\).) listka kielicha kwiatowego, szerokość (w \(cm\)) listka kielicha kwiatowego, długość (w \(cm\)) płatka kwiatu, szerokość (w \(cm\)) płatka kwiatu. Wykorzystamy teraz algorytm SBS do redukcji wymiaru przestrzeni cech do dwóch. Jako funkcję kryterialną przyjmiemy sprawność klasyfikatora kNN dla parametru \(k=4\). Sprawność klasyfikacji będzie mierzona metodą k-krotnej walidacji krzyżowej dla parametru \(k=5\). W wyniku dziłania algorytmu SBS otrzymujemy, ze wybrany podzbiór cech skłąda się z cech o indeksach 0 i 3, tzn. są to długość (w \(cm\).) listka kielicha kwiatowego oraz szerokość (w \(cm\)) płatka kwiatu. Dla tak wybranego podzbioru cech sprawność klasyfikatora 4NN dla zbioru Iris wynosi 96%. Poniżej prezentujemy skrypt w języku python realizujący powyższą procedurę.

from mlxtend.sklearn import SBS
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris

iris = load_iris()
X = iris.data
y = iris.target

knn = KNeighborsClassifier(n_neighbors=4)

sbs = SBS(knn, k_features=2, scoring='accuracy', cv=5)
sbs.fit(X, y)

print('Indeksy wybranych cech:', sbs.indices_)
print('Sprawność klasyfikatora dla wybranego podzbioru cech:',
      sbs.k_score_)

Algorytmy SFS i SBS są często stosowane w praktyce ze względu na swoją prostotę. Maksymalizacja funkcji kryterialnej jest najbardziej kosztowną operacją tych algorytmów. W pesymistycznym przypadku należy uruchomić klasyfikator \(p(p+1)/2\) razy. Oznacza to, że całkowita złożoność tego algorytmu jest \(O(p^2)\cdot\) złożoność klasyfikatora.

W algorytmie SFS raz dodana cecha nie może zostać usunięta ze zbioru. Jest to podstawowa wada tego algorytmu, gdyż można sobie wyobrazić sytuację, w której jedna z już dodanych cech powoduje zmniejszenie możliwego przyrostu wartości funkcji kryterialnej po dodaniu innej, nowej cechy. Wadę tą usunięto w algorytmie SFFS. Algorytm SFFS wykorzystuje algorytm SFS przy dodawaniu nowej cechy do bieżącego zbioru cech. Dodatkowo po każdym przebiegu wykonuje się serię warunkowych usunięć cech z konstruowanego podzbioru cech. Poniżej przedstawiony jest schemat algorytmu SFFS.

Algorytm 12 Regresja SFFS

Dane: zbiór uczący \(X_{train}=\{(x_i,y_i):x_i\in X, y_i\in C=\{-1,1\}\}\), \(J\) - funkcja kryterialna, \(p\) - liczba wszystkich cech

Wyniki: \(S\) - podzbiór cech

  1.  \(S=\emptyset\)
  2.  \(J_{max}=0, n=0\)
  3.  \(\mathbf{for} \ a_i\notin S \ \mathbf{do}\)
  4.  \(\qquad\) Oblicz \(J(S\cup \{a_i\})\)
  5.  \(J_{max}=\max_{1,\ldots, p}(J(S\cup\{a_i\})),\, a_{max}=\mathop{\rm argmax}_{1,\ldots, p}(J(S\cup\{a_i\}))\)
  6.  \(\mathbf{if} \ J\geq J_{max} \ \mathbf{then}\)
  7.  \(\qquad\) zakończ działanie algorytmu
  8.  \(\mathbf{else}\)
  9.  \(\qquad S=S\cup\{a_{max}\}, p=p-1, n=n+1\)
  10.  \(\mathbf{for} \ a_i\in S \ \mathbf{do}\)
  11.  \(\qquad\) Oblicz \(J(S\cup \{a_i\})\)
  12.  \(J_{max}=\max_{1,\ldots, p}(J(S\cup\{a_i\})),\, a_{max}=\mathop{\rm argmax}_{1,\ldots, p}(J(S\cup\{a_i\}))\)
  13.  \(\mathbf{if} \ J\geq J_{max} \ \mathbf{and} \ p>0 \ \mathbf{then}\)
  14.  \(\qquad\) przejdź do pkt. 3
  15.  \(\mathbf{if} \ p>0 \ \mathbf{then}\)
  16.  \(\qquad\) zakończ działanie algorytmu.
  17.  \(\mathbf{else}\)
  18.  \(\qquad S=S\setminus\{a_{max}\}, p=p+1, n=n-1\)
  19.  \(\qquad\) Przejdź do pkt 4.

Po każdorazowym dodaniu cechy do szukanego podzbioru, sprawdzamy czy któraś z już wybranych cech nie pogarsza nam wartości funkcji kryterialnej \(J\). Takie postępowanie prowadzi zwykle do lepszego podzbioru cech, jednak wzrasta złożoność obliczeniowa algorytmu. Teoretycznie algorytm SFFS może w pesymistycznym przypadku może wymagać nawet wykładniczej ilość operacji maksymalizacji funkcji kryterialnej.

Następna część - Test do rozdziału