Politechnika Łódzka


Specyfika zagadnienia i problemy pokrewne



Pobieranie 6.5 Mb.
Strona22/54
Data29.10.2017
Rozmiar6.5 Mb.
1   ...   18   19   20   21   22   23   24   25   ...   54

2.1. Specyfika zagadnienia i problemy pokrewne


Jeśli w zbiorze odniesienia niektóre cechy są zbędne, to działają jak szum, pogarszając jakość klasyfikacji. W przypadku asymptotycznym (zbiór o nieskończonej liczności) skończona liczba nawet czysto losowych cech nie może pogorszyć jakości. Dla skończonych zbiorów uczących pokazano jednak (Langley i Iba, 1993), że liczba próbek w zbiorze musi rosnąć w tempie wykładniczym, aby zachować jakość klasy­fikacji w przypadku, gdy dodawane są zbędne cechy.

Można wyróżnić dwa typy zbędnych cech: nieistotne (ang. irrelevant) i nadmia­rowe (ang. redundant). Cechy nieistotne to cechy nieskorelowane z etykietami klas. Cechy nadmiarowe zaś, to cechy, których wartości można wyliczyć z wartości pozostałych cech. Dla przykładu, jeśli pewna cecha jest dokładnym powtórzeniem innej, tj. dla każdego elementu zbioru wartości tych dwu cech są jednakowe, to oczywiście jedną z tych cech można uznać za nadmiarową. Jest to najprostszy przypa­dek nadmiarowości, ale nie jedyny. Przykładowo dana cecha może być iloczynem dwóch innych cech.

Selekcja cech polega tradycyjnie na wybraniu możliwie dobrego podzbioru cech z pełnego zestawu wejściowego. Przez „dobry” podzbiór cech można rozumieć zestaw nie zawierający opisanych wyżej cech zbędnych. Warto wspomnieć, że istnieją także (nieliczne) podejścia, w których na wyjściu nie otrzymujemy podzbioru cech (Domin­gos, 1997; Bay, 1998). Najczęstszym schematem jest sekwencyjny przegląd zestawów cech według pewnej strategii (np. dodając po jednej — losowej lub w szczególny sposób wybranej — cesze) i ocena jakości każdego zestawu.

Rozważane zagadnienie ma długą historię i było przedmiotem licznych badań; do klasycznych prac można zaliczyć m. in. (Fu, 1968) i (Mucciardi i Gose, 1971). Spośród bardziej oryginalnych koncepcji należy wymienić takie podejścia do selekcji cech, jak użycie algorytmów genetycznych (Brill i in., 1992; Vafaie i De Jong, 1992 i in.), teorii informacji (Koller i Sahami, 1996; Singh i Provan, 1996), wykorzystanie wymiaru fraktalnego (Traina i in., 2000) czy łączenie selekcji cech i redukcji zbioru odniesienia (Skalak, 1994). Rozważano także selekcję cech symbolicznych (Baim, 1988; Rauber i Steiger-Garção , 1993).

Alternatywną dla selekcji cech fazą uczenia jest ważenie cech (ang. feature weighting). W najprostszej wersji polega ono na przypisaniu każdej cesze wartości z przedziału [0, 1], będącej mnożnikiem danej cechy przy liczeniu odległości (Kelly i Davis, 1991; Salzberg, 1991; Lee, 1994; Mohri i Tanaka, 1994; Lowe, 1995). Należy zauważyć, że jeśli dopuszczamy tylko wagi 0 i 1, to proces ten sprowadza się do klasycznej selekcji cech. Istnieją także bardziej złożone schematy, w których wagi przypisywane są z uwzględnieniem kontekstu. I tak postulowano m. in. wprowadzenie osobnej wagi dla każdej występującej w zbiorze odniesienia wartości każdej z cech (Stanfill i Waltz, 1986; Nosofsky i in., 1989) lub osobnej wagi dla każdej cechy w obrębie każdej klasy (Aha, 1989). Najbardziej złożone algorytmy używają osobnych wag dla każdej cechy każdej próbki zbioru, więc można je uznać za w pełni kontekstowe. W tej klasie algorytmów wagi dobierane są na etapie uczenia (Aha i Goldstone, 1992) lub klasyfikacji (Atkeson i in., 1997; Hastie i Tibshirani, 1996). Ważenie cech znacząco poszerza przestrzeń poszukiwań, więc potencjalnie umożliwia lepsze przetworzenie zbioru niż klasyczna selekcja cech. Niestety, w praktyce ryzyko przeuczenia parametrów jest duże. Jest to zjawisko stale występu­jące w zagadnieniach przetwarzania obrazów. Podobne założenia (i podobne niebezpie­czeństwa) kryją się w eksperymentach z funkcją odległości dobieraną do danego zadania.

Prostą i często stosowaną formą ważenia cech jest standaryzacja (normalizacja) (ang. standardization) cech. Warto zauważyć, że np. w przypadku, gdy dwie cechy przyjmujące podobne wielkości fizyczne wyrażone są w zupełnie różnych jednostkach (np. jedna w centymetrach, a druga w metrach), klasyfikator będzie niejako fawory­zował cechę o większym rozrzucie nominalnych wartości, a zatem wynik finalny będzie wypaczony. Standaryzacja polega na transformacji wszystkich cech do podob­nie szerokich przedziałów przyjmowanych wartości. Najczęściej spotyka się trzy odmiany standaryzacji (Jajuga, 1990):



  • klasyczną (po transformacji liniowej średnia wartość każdej cechy wynosi 0, a odchylenie standardowe 1);

  • medianową (analogiczna do poprzedniej, lecz wykorzystująca medianę i odchyle­nie medianowe);

  • skalującą liniowo do przedziału [0, 1].

Wadą dwu z przedstawionych metod w oryginalnej postaci, za wyjątkiem standaryzacji medianowej, jest wrażliwość na próbki znacznie różniące się (na jednej lub wielu cechach) od pozostałych (ang. outliers). „Nietypowe” próbki są często wyni­kiem błędów pozyskania danych. Dla cechy, na której pojawił się „odszcze­pieniec”, efektywny przedział dla typowych wartości będzie miał szerokość dużo mniejszą niż 1, a to oznacza, iż cecha ta będzie miała mniejszy wpływ na klasyfikację od innych. Aby pokonać ten problem, Skalak (1997) w wariancie skalującym do przedziału [0, 1] nadał nową wartość 0 (1) wszystkim wartościom mniejszym (większym) od średniej dla danej cechy o przynajmniej 3-krotną wielokrotność odchylenia standardowego dla tej cechy. Podobne rozwiązanie użyte zostało w schemacie ReMind (Cognitive Systems, Inc., 1992).

W praktyce wszystkie opisane metody standaryzacji działają zazwyczaj porównywalnie dobrze; mimo iż wartości cech rzeczywistych zbiorów bardzo często nie przyjmują rozkładu normalnego, to jednak rzadkie są sytuacje, w których np. standa­ryzacja klasyczna (wykorzystująca odchylenia standardowe wartości przyjmowanych przez cechy) prowadzi do znacznie zwiększonych błędów klasyfikacji (Aha, 1990).

Jeszcze inną techniką pokrewną selekcji cech jest wprowadzanie sztucznych cech będących kombinacjami cech danych (Matheus i Rendell, 1989; Wnek i Michalski, 1994). W ten sposób utworzone nowe atrybuty — np. różnica pewnej pary cech traktowana jako nowa cecha — mogą spowodować znaczne przyspieszenie zbieżności algorytmu klasyfikacji i/lub poprawić jego szybkość po dalszej selekcji. Przykładem niech będzie iloczyn cech 3 i 4 zbioru Iris (Fisher, 1936), uwzględniany jako jedyna cecha dla klasyfikatora. Jakość klasyfikacji jest wówczas porównywalna z jakością przy pełnym zbiorze (Gama, 1999), zaś szybkość klasyfikacji np. przy regule 1-NN wzrasta ok. 4-krotnie. Rzecz jasna, w przypadku ogólnym wybór operatora i cech, na których należy go zastosować, nie jest zadaniem łatwym.

2.2. Modele oceny zestawów


Wyróżnia się dwa schematy oceny zestawów cech: metody, w których jakość przeglądanych zestawów estymuje się przy użyciu tej samej reguły decyzyjnej, która będzie użyta w następnym etapie do klasyfikacji (model „wrapper”), oraz metody, gdzie przeglądane zestawy są oceniane przy pomocy innego kryterium (model „filter”). Innymi słowy, w modelu „filter” abstrahujemy od klasyfikatora używanego w danym zadaniu. Pierwsza klasa algorytmów, jak można oczekiwać, daje na ogół lepsze wyniki (John i in., 1994; Aha i Bankert, 1995), kosztem jest jednak dłuższy proces działania algorytmu. W modelu „filter” kryterium oceny jest na ogół znacznie szybsze niż ocena jakości klasyfikatora, zatem i cała sesja selekcji cech jest stosunkowo szybka — jednak inny sposób oceny zestawów cech na etapie uczenia niż na etapie klasyfikacji niemal zawsze prowadzi do znalezienia gorszego zestawu. Do najbardziej znanych algoryt­mów typu „filter” należą RELIEF (Kira i Rendell, 1992) i FOCUS (Almuallim i Diette­rich, 1991), gdzie klasyfikatorami używanymi w zadaniu są drzewa decyzyjne. W pracy (Cardie, 1993) użyto jednak filtracji dla klasyfikatora 1-NN.

W pozostałej części rozdziału rozważa się podejścia typu „wrapper”.


2.3. Pełny przegląd zestawów cech


Strategie selekcji cech na ogół w pewnym porządku przeglądają wybrane zestawy, estymują ich jakość (jak wyżej wspomniano, metodą typu „wrapper” bądź „filter”) i zwracają ten zestaw, dla którego estymowany błąd był najmniejszy. Nasuwa się pytanie: czy nie można przejrzeć wszystkich zestawów cech (oczywiście w takim przypadku kolejność przeglądania nie ma znaczenia)? Niestety, w większości przypad­ków jest to niemożliwe ze względu na czas selekcji rosnący wykładniczo z wymiarem. Przy d cechach wejściowych istnieje niepustych kombinacji cech, a zatem w praktyce pełny przegląd wykonalny jest jedynie wtedy, gdy d nie przekracza ok. 12–15. Jednakże w przypadkach, w których pełny przegląd jest możliwy, jest on zalecany (o ile (gdzie n jest licznością zbioru), gdyż w przeciwnym razie pełny przegląd zestawów cech może doprowadzić do przeuczenia).

Ponieważ w dalszej części pracy wielokrotnie pojawiają się złożoności przedsta­wianych algorytmów, warto przypomnieć, iż symbol oznacza, że koszt algorytmu, wyrażany zwykle liczbą elementarnych operacji, jest asymptotycznie ściśle ograniczony z góry iloczynem , gdzie c jest pewną stałą, zaś funkcją jednego lub więcej parametrów związanych z zadaniem (np. liczność zbioru, wymiar) lub specyfiką algorytmu (np. zadaną liczbą sąsiadów) (Aho i in., 2003). Niejednokrot­nie złożoność algorytmu w najgorszym przypadku różni się od złożoności algorytmu w przypadku średnim, i za wyjątkiem oczywistych sytuacji warto podawać obie złożo­ności.

Pobieranie 6.5 Mb.

Share with your friends:
1   ...   18   19   20   21   22   23   24   25   ...   54




©operacji.org 2020
wyślij wiadomość

    Strona główna