Metody redukcji wymiarowości przestrzeni cech¶

Mimo, że zagadnienie klasyfikacji nadzorowanej jest szeroko opisywane w literaturze, nowe rzeczywiste zbiory danych powodują, że ten temat nadal nie jest zamknięty i wciąż pojawiają się nowe wyzwania. Jednym z nich bez wątpienia jest klasyfikację obiektów w przestrzeniach o wysokim wymiarze, w których każdy obiekt opisywany jest przez dziesiątki, setki a nawet tysiące atrybutów. Zbiory wysokowymiarowe, coraz częściej spotykane w rzeczywistych problemach, nastręczają trudności w ich analizowaniu. Problemy te wynikają z faktu, iż w przestrzeni wysokowymiarowej podobieństwa obiektów zbliżają się do siebie. Z tego powodu, żeby dokonać poprawnego podziału zbioru testowego na klasy potrzebna jest znacznie większa liczba obiektów. Spełnienie tego warunku niejednokrotnie jest nie możliwe. Okazuje się bowiem, że aby zapewnić taką samą dokładność klasyfikacji jak w przypadku przestrzeni o mniejszym wymiarze, liczba próbek musi rosnąć wykładniczo wraz ze wzrostem wymiaru przestrzeni cech. Zjawisko takie jest w literaturze określane jako przekleństwo wymiarowości (por. [Duda2000]). Dlatego też poprawna klasyfikacja obiektów, wykorzystując pełen zbiór atrybutów, może być niemożliwa. Ponadto duża liczba cech w wektorze cech powoduje wzrost liczby parametrów koniecznych do oszacowania, a co za tym idzie złożoność klasyfikatora. Zwiększa się również niebezpieczeństwo przeuczenia i wynikający z tego spadek zdolności uogólniających klasyfikatora. Z tego powodu dąży się do zmniejszenia wymiarowości przestrzeni cech. Wynika to z faktu, iż obiekty są na ogół dobrze zarysowane po wyborze do ich opisu jedynie pewnego podzbioru atrybutów. Problemem jednak jest identyfikacja takiego podzbioru atrybutów, przy użyciu, którego algorytm klasyfikacji dokona poprawnej klasyfikacji obiektów zbioru testowego do poszczególnych klas. Identyfikacji podzbioru atrybutów można dokonać poprzez selekcję pewnej liczby atrybutów bądź też przez stworzenie nowych atrybutów w oparciu o zbiór atrybutów opisujących dany obiekt. Zadanie to nazywamy odpowiednio problemem selekcji bądź ekstrakcji cech (por. [Guyon2006]).

Szczególnym przykładem zbiorów danych wysokowymiarowych są zbiory zawierające dane biologiczne pochodzące z mikromacierzy DNA. Pozwalają one mierzyć poziomy ekspresji nawet dziesiątek tysięcy genów dla każdej próbki jednocześnie.

W przypadku klasyfikacji tego typu danych zasadniczym problemem jest niewielka liczba próbek. Ich liczba na ogól nie przekracza kilkudziesięciu, a każda z nich może być opisywana za pomocą tysięcy genów. Dotychczasowe badania ([Nguyen2002], [Nguyen2004]) wskazują, że klasyfikacji próbek pod kątem identyfikacji jednostki chorobowej można dokonać efektywnie dysponując jedynie niewielkim podzbiorem genów, których poziomy ekspresji znacznie korelują z etykietami klasowymi. Dlatego też głównym problemem w klasyfikacji próbek pochodzących z mikromacierzy DNA jest zredukowanie liczby genów do tych, które biorą udział w procesach odpowiedzialnych za wystąpienie danej jednostki chorobowej. Geny takie nazywamy informatywnymi. Ich identyfikacja jest ważnym ale niełatwym zadaniem. Zawodzenie klasycznych metod klasyfikacji obiektów na podstawie pełnego zbioru atrybutów tłumaczy fakt, iż w procesach komórkowych bierze udział nieliczna grupa genów, ponadto jeden i ten sam gen może być elementem kilku ścieżek genowych odpowiadających za różne procesy komórkowe. Może zaistnieć również i taka sytuacja, gdy dany gen nie należy do żadnej ścieżki genowej. Stanowi on wówczas w danym zbiorze szum. Z tych powodów zasadna jest nie tyle selekcja odpowiednich genów, co stworzenie nowych atrybutów będących pewną kombinacją oryginalnych atrybutów (genów). Pozwala to na wykrycie ukrytych zależności pomiędzy grupą genów a daną jednostką chorobową, niemożliwych do wychwycenia poprzez selekcję cech.

Dane mikromacierzowe są jedynie przykładem. Obrazują one podstawowe problemy występujące w zadaniu klasyfikacji danych wysokowymiarowych. Takie trudności występują również w przypadku innych rzeczywistych zbiorów danych wysokowymiarowych. Przykładem może być tutaj zadanie kategoryzacji tekstu.

Mimo, że zagadnienie klasyfikacji nadzorowanej jest szeroko opisywane w literaturze, nowe rzeczywiste zbiory danych powodują, że ten temat nadal nie jest zamknięty i wciąż pojawiają się nowe wyzwania. Jednym z nich bez wątpienia jest klasyfikację obiektów w przestrzeniach o wysokim wymiarze, w których każdy obiekt opisywany jest przez dziesiątki, setki a nawet tysiące atrybutów. Zbiory wysokowymiarowe, coraz częściej spotykane w rzeczywistych problemach, nastręczają trudności w ich analizowaniu. Problemy te wynikają z faktu, iż w przestrzeni wysokowymiarowej podobieństwa obiektów zbliżają się do siebie. Z tego powodu, żeby dokonać poprawnego podziału zbioru testowego na klasy potrzebna jest znacznie większa liczba obiektów. Spełnienie tego warunku niejednokrotnie jest nie możliwe. Okazuje się bowiem, że aby zapewnić taką samą dokładność klasyfikacji jak w przypadku przestrzeni o mniejszym wymiarze, liczba próbek musi rosnąć wykładniczo wraz ze wzrostem wymiaru przestrzeni cech. Zjawisko takie jest w literaturze określane jako przekleństwo wymiarowości (por. [Duda2000]). Dlatego też poprawna klasyfikacja obiektów, wykorzystując pełen zbiór atrybutów, może być niemożliwa. Ponadto duża liczba cech w wektorze cech powoduje wzrost liczby parametrów koniecznych do oszacowania, a co za tym idzie złożoność klasyfikatora. Zwiększa się również niebezpieczeństwo przeuczenia i wynikający z tego spadek zdolności uogólniających klasyfikatora. Z tego powodu dąży się do zmniejszenia wymiarowości przestrzeni cech. Wynika to z faktu, iż obiekty są na ogół dobrze zarysowane po wyborze do ich opisu jedynie pewnego podzbioru atrybutów. Problemem jednak jest identyfikacja takiego podzbioru atrybutów, przy użyciu, którego algorytm klasyfikacji dokona poprawnej klasyfikacji obiektów zbioru testowego do poszczególnych klas. Identyfikacji podzbioru atrybutów można dokonać poprzez selekcję pewnej liczby atrybutów bądź też przez stworzenie nowych atrybutów w oparciu o zbiór atrybutów opisujących dany obiekt. Zadanie to nazywamy odpowiednio problemem selekcji bądź ekstrakcji cech (por. [Guyon2006]).

Szczególnym przykładem zbiorów danych wysokowymiarowych są zbiory zawierające dane biologiczne pochodzące z mikromacierzy DNA. Pozwalają one mierzyć poziomy ekspresji nawet dziesiątek tysięcy genów dla każdej próbki jednocześnie.

W przypadku klasyfikacji tego typu danych zasadniczym problemem jest niewielka liczba próbek. Ich liczba na ogól nie przekracza kilkudziesięciu, a każda z nich może być opisywana za pomocą tysięcy genów. Dotychczasowe badania ([Nguyen2002], [Nguyen2004]) wskazują, że klasyfikacji próbek pod kątem identyfikacji jednostki chorobowej można dokonać efektywnie dysponując jedynie niewielkim podzbiorem genów, których poziomy ekspresji znacznie korelują z etykietami klasowymi. Dlatego też głównym problemem w klasyfikacji próbek pochodzących z mikromacierzy DNA jest zredukowanie liczby genów do tych, które biorą udział w procesach odpowiedzialnych za wystąpienie danej jednostki chorobowej. Geny takie nazywamy informatywnymi. Ich identyfikacja jest ważnym ale niełatwym zadaniem. Zawodzenie klasycznych metod klasyfikacji obiektów na podstawie pełnego zbioru atrybutów tłumaczy fakt, iż w procesach komórkowych bierze udział nieliczna grupa genów, ponadto jeden i ten sam gen może być elementem kilku ścieżek genowych odpowiadających za różne procesy komórkowe. Może zaistnieć również i taka sytuacja, gdy dany gen nie należy do żadnej ścieżki genowej. Stanowi on wówczas w danym zbiorze szum. Z tych powodów zasadna jest nie tyle selekcja odpowiednich genów, co stworzenie nowych atrybutów będących pewną kombinacją oryginalnych atrybutów (genów). Pozwala to na wykrycie ukrytych zależności pomiędzy grupą genów a daną jednostką chorobową, niemożliwych do wychwycenia poprzez selekcję cech.

Dane mikromacierzowe są jedynie przykładem. Obrazują one podstawowe problemy występujące w zadaniu klasyfikacji danych wysokowymiarowych. Takie trudności występują również w przypadku innych rzeczywistych zbiorów danych wysokowymiarowych. Przykładem może być tutaj zadanie kategoryzacji tekstu.