Politechnika Łódzka



Pobieranie 6.5 Mb.
Strona42/54
Data29.10.2017
Rozmiar6.5 Mb.
1   ...   38   39   40   41   42   43   44   45   ...   54

Algorytmy Skalaka


Skalak (1994) przedstawił dwa algorytmy redukcji — oryginalność obu polega na ich skrajnej prostocie. Pierwsza metoda (RMHC), używająca techniki określanej w litera­turze poświęconej sztucznej inteligencji mianem random mutation hill climbing („wspinaczka po wzgórzu z losowymi mutacjami”), wybiera losowo h próbek ze zbioru odniesienia i estymuje jakość takiego zbioru na pełnym zbiorze odniesienia z użyciem reguły 1-NN. Następnie w pętli wykonywanych jest m1 tzw. mutacji. Mutacja polega na wylosowaniu jednej próbki z aktualnego zbioru zredukowanego oraz jednej próbki z tej części zbioru odniesienia, która nie należy do aktualnego zbioru zredukowanego. Jeśli zamiana tych próbek (tj. odrzucenie pierwszej i dodanie drugiej) prowadzi do polepszenia jakości klasyfikacji regułą 1-NN opartą na zbiorze zredukowanym, to muta­cja zostaje przyjęta. Jeśli nie, wówczas mutację należy odrzucić, czyli powrócić do poprzedniego zbioru zredukowanego. Metoda Skalaka nie gwarantuje zgodności zbioru zredukowanego ze zbiorem oryginalnym, co więcej: w praktyce zwykle wygenerowany zbiór jest od zgodności odległy. Należy zauważyć, że algorytm zależny jest od dwóch wybranych przez użytkownika parametrów: h i m1. Liczba mutacji m1 mieści się zazwyczaj w przedziale 100–1000 (zbyt duża wartość może prowadzić do przeuczenia).

Autor rozprawy użył algorytmu redukcji RMHC do segmentacji barwnej jąder komórkowych w cytologicznych obrazach mikroskopowych (Bieniecki, Grabowski i in., 2002). Pomimo prawie 20-krotnego stopnia redukcji zbioru odniesienia, wizualny efekt segmentacji barwnej przy użyciu zbioru zredukowanego tylko nieznacznie różnił się od wyniku segmentacji przy użyciu pełnego zbioru odniesienia i reguły 1-NN, co w danym zastosowaniu było w pełni satysfakcjonujące.

W pracy (Grabowski, 2002c) zmodyfikowano algorytm RMHC. Modyfikacja polega na kontynuacji uczenia wg przedstawionej procedury. Następny krok polega mianowicie na próbie tworzenia nowych (sztucznych) prototypów w zbiorze zreduko­wanym metodą błądzenia przypadkowego (ang. random walk). Konkretnie, wykonuje się w pętli m2 mutacji polegających na przesunięciu losowej próbki z aktualnego zbioru zredukowanego na jednej losowej cesze o +/– 0,5 (znak jest również losowany). Jeśli takie przesunięcie poprawia jakość estymowaną na zbiorze uczącym, to mutacja zostaje zaakceptowana. Warto zwrócić uwagę, że wartość 0,5 jest połową odchylenia standardowego dla każdej znormalizowanej cechy.

Druga z metod Skalaka (1994) jest jeszcze prostsza: m-krotnie losuje się h próbek ze zbioru uczącego i ostatecznie wybiera ten zbiór zredukowany, który osiągnął najwyższą jakość na zbiorze uczącym. I tu parametry (m i h) są zadawane przez użytkownika. W testach na kilku zbiorach UCI przeprowadzonych w oryginalnej pracy, oba algorytmy osiągały porównywalną jakość i jednocześnie średnio wyższą niż jakość 1-NN z pełnym zbiorem odniesienia, mimo iż zadany stopień redukcji był skrajnie wysoki.


Oprócz opisanych algorytmów, w literaturze pojawiło się wiele innych metod redukcji. Jedną z najwcześniejszych propozycji jest iteracyjny algorytm Swongera ICA (Iterative Condensation Algorithm) (1972). W metodzie tej stosuje się naprzemiennie cykle usu­wania oraz dołączania próbek. Wynikowy zbiór zredukowany jest zgodny ze zbiorem oryginalnym.

Algorytm VSM (Variable Similarity Metric), zaproponowany w pracy (Lowe, 1995), jest złożonym systemem uczenia, dokonującym m. in. redukcji zbioru odniesie­nia (w uproszczeniu: usuwane są próbki posiadające najbliższych sąsiadów tylko z jed­nej klasy) oraz ważenia cech.

Podobną do użytej w schemacie VSM ideę redukcji zastosowano w pracy (Wu i in., 2002), osiągając kilkakrotne przyspieszenie klasyfikacji regułą k-NN przy zacho­waniu wyjściowej jakości na bardzo dużych i wysokowymiarowych zbiorach dotyczą­cych rozpoznawania pisma ręcznego.

Algorytm Shrink (Kibler i Aha, 1987) jest pewną modyfikacją algorytmu Gatesa; niestety, mniej odporną na szum niż jego pierwowzór.

Redukcja w złożonym systemie MCS (Model Class Selection), przedstawionym przez Brodley (1993), usuwa obiekt q z oryginalnego zbioru, o ile w większości przypadków jego klasa nie zgadza się z klasą obiektów, dla których q jest jednym z k najbliższych sąsiadów. Idea ta ma na celu eliminację szumu.

Oryginalne założenie przyświecało autorowi schematu TIBL (Typical Instance Based Learning) (Zhang, 1992). Algorytm ten pozostawia w zbiorze zredukowanym próbki położone blisko środka klastra, a nie brzegowe, jak bywa w przypadku większości innych metod. Obok znacznej odporności na szum i często dużego stopnia redukcji, TIBL ma też wady, do których przede wszystkim trzeba zaliczyć problemy przy skomplikowanych granicach decyzyjnych oraz konieczność modyfikacji proce­dury, gdy choć jedna klasa w zadaniu zajmuje więcej niż jeden spójny region w przestrzeni.

Dwie metody bardzo agresywnej redukcji przedstawił Cameron-Jones (1995). ELGrow (Encoding Length Grow) używa skomplikowanej heurystycznej miary opisują­cej, jak dobrze zbiór zredukowany oddaje powierzchnie decyzyjne zbioru oryginalnego. Próbki ze zbioru są usuwane, jeśli zmniejsza to wartość funkcji kosztu. ELGrow jest wrażliwy na kolejność próbek na wejściu. Druga metoda Camerona-Jonesa, Explore, zaczyna od procedury ELGrow, a następnie próbuje ulepszyć zbiór przy pomocy szeregu mutacji analogicznych do pierwszego z opisanych algorytmów Skalaka.

Niektóre metody modyfikują zbiór prototypów, zamiast jedynie dokonywania selekcji. Pierwszym algorytmem tego typu była metoda Changa (1974), w której sąsia­dujące próbki zostają scalane, jeśli nie narusza to kryterium zgodności. Nowo powstałe prototypy mogą podlegać dalszemu scalaniu, przy czym każdy nowy obiekt jest środkiem ciężkości wszystkich elementów składowych. Jest to de facto aglomera­tywny algorytm klasteryzacji (Murtagh, 1985). Poważną wadą algorytmu Changa jest jednak bardzo wysoki koszt czasowy uczenia.

Bezdek i in. (1998) zmodyfikowali sposób łączenia prototypów w propozycji Changa, osiągając w swoim algorytmie MCA (Modified Chang Algorithm) nieco mniejsze zbiory zredukowane przy jednoczesnym przyspieszeniu uczenia.

Mollineda i in. (2000) rozwinęli ideę Changa, m. in. przez uogólnienie jej do niemal dowolnej metody przyrostowego budowania klastrów. Ubocznym efektem metody jest także znaczne przyspieszenie uczenia. Podobnie jak jego pierwowzory, jest to algorytm zachowujący zgodność zbioru zredukowanego. Algorytm ten umożliwia zredukowanie pełnego zbioru Iris do 9 lub 11 prototypów (w zależności od wersji liczenia odległości między klastrami), co należy uznać za bardzo dobry wynik. Niestety, niełatwo na razie o rzetelną ocenę tego algorytmu, gdyż oprócz zbioru Iris jedynym jeszcze rzeczywistym zbiorem danych, dla którego autorzy podali wyniki, jest zbiór DNA zawierający wyłącznie cechy binarne, a zatem zbiór, który trudno uznać za reprezentatywny dla szerszej klasy praktycznych zadań.



Kilka klasycznych technik formalnie można zaliczyć do redukcji, choć ich głównym celem nie jest zmniejszenie zbioru uczącego, a poprawa jakości, zwłaszcza przy klasyfikacji jednym najbliższym sąsiadem. Mówi się też, iż są to filtry odszumia­jące i w praktyce opisane niżej algorytmy często wykorzystuje się przed zasadniczym algorytmem redukcji (np. w pracy (Kuncheva, 2001)). Wilson (1972) odrzucał te próbki ze zbioru uczącego, które były źle klasyfikowane przez swoich k najbliższych sąsiadów (ENN — Edited Nearest Neighbor); najczęściej przyjmuje się lub . Tomek (1976b) zaproponował dwie wersje odszumiania: iteracyjne powtarzanie ENN aż do momentu, gdy nic nie można odrzucić (nieraz w literaturze używa się określenia metody: RENN — Repeated Edited Nearest Neighbor) oraz „All k-NN”. Algorytm All k-NN każdą próbkę ze zbioru uczącego klasyfikuje przy pomocy i 1, 2, ..., k sąsiadów. Jeśli dla choć jednej wartości i dana próbka jest źle klasyfiko­wana, to zostaje oznaczona flagą i na końcu procedury usunięta. Wszystkie z przedsta­wionych metod oferują nieznaczne zmniejszenie zbioru uczącego, przeważnie nie prze­kraczające 20%–30%, ale niejednokrotnie poprawiają jakość późniejszej klasyfi­kacji.

Zamiast usuwania zaszumionych próbek można dokonywać ich reklasyfikacji, tj. nadania nowych etykiet, np. w zgodzie z k-NN (analogia do ENN). Celem takiej ope­racji jest, rzecz jasna, poprawa jakości klasyfikacji, także w schematach połączonych z późniejszą redukcją.

Jóźwik i in. (1995) przedstawili algorytm dzielący hiperpłaszczyznami prze­strzeń na regiony, a następnie zastępujący podzbiór zbioru odniesienia z danego regionu pojedynczym prototypem. Ponieważ algorytm ten w pewnym stopniu zacho­wuje lokalną gęstość zbioru, więc można go używać nie tylko z 1-NN, ale i z k‑NN. W pracy (Chen i Jóźwik, 1996) wygenerowany zbiór zredukowany został użyty do uczenia sieci neuronowej.

Sánchez i in. (1997a) zaproponowali redukcję przy użyciu grafów Gabriela i RNG (p. Rozdz. 7). W prostszym wariancie ich algorytmu, z oryginalnego zbioru eliminuje się te próbki, których etykieta klasy różni się od etykiety dominującej wśród ich sąsiadów grafowych. Dodatkowo na tak odszumionych zbiorach zastosowano algorytm Tomeka oraz jego odpowiednik używający grafu RNG. Druga faza algorytmów Sáncheza i in. zwykle powoduje pewien spadek jakości predykcji, a zatem jest kompromisem między jakością a stopniem redukcji.

Użycie algorytmów genetycznych do redukcji zbioru odniesienia postulowała Kuncheva (1995). W następnych pracach (Kuncheva i Jain, 1999; Kuncheva, 2001) dokonano tym podejściem jednoczesnej redukcji i selekcji cech.

Wilson i Martinez przedstawili rodzinę algorytmów DROP1..5 (Wilson i Marti­nez, 1997b; 2000), będących wariacjami nt. algorytmu Gatesa. Nowości polegały zwykle na bardziej subtelnych kryteriach usuwania sąsiadów lub poprzedzeniu algorytmu filtrem odszumiającym zbliżonym do ENN. Jeszcze jedna zaprezentowana metoda redukcji, DEL, łączy podejście autorów ze wspomnianą wyżej heurystyką algorytmu ELGrow Camerona-Jonesa. W wymienionych pracach przetesto­wano proponowane algorytmy na 31 zbiorach UCI i porównano m. in. z CNN i SNN. Oprócz dobrego kompromisu między jakością klasyfikacji a wielkością zbioru uczącego, większość algorytmów Wilsona i Martineza charakteryzuje się też znaczną odpornością na przekłamania etykiet klas zbioru uczącego, czego dowiodły eksperymenty ze sztucznie dodanym szumem.



6.3. O kryterium zgodności

Wiele algorytmów redukcji, zwłaszcza starszych, gwarantuje zgodność zbioru zredukowanego ze zbiorem oryginalnym. Jest to zwykle eleganckie kryterium końca procedury generacji zbioru zredukowanego; można też oczekiwać, że przy dostatecznie dużym zbiorze odniesienia kryterium to zagwarantuje jakość klasyfikacji zreduko­wanego zbioru porównywalną ze zbiorem oryginalnym. W praktyce jednak dane zbiory odniesienia są notorycznie małe w stosunku do wymiarowości. Powstaje więc pytanie, czy zgodność jest „dobrym” kryterium przy tworzeniu zbioru zredukowanego?














































































o































o




x










o 4



















x










o 4










x 1










o



















x 1










o




x







x 2

o 3



















x







x 2

o 3



















o































o







x













o
















x













o

x




x

























x




x































o































o
































































(a)































(b)










Rys. 6.4. Dwa warianty redukcji zbioru do dwóch obiektów.
Przykład sytuacji, w której wymóg zgodności może prowadzić do przeuczenia.
Rys. 6.4 przedstawia przykład zadania dwudecyzyjnego, dla którego wybrano osobno dwa różne dwuelementowe zbiory zredukowane. W wariancie (a) są to obiekty 2 i 3, zaś w wariancie (b) — obiekty 1 i 4. Którą płaszczyznę rozdzielającą klasy zbioru uczącego należy wybrać? Tylko w wariancie (a) zachowana jest zgodność, jednak wydaje się, iż płaszczyzna (b) lepiej odpowiada hipotetycznemu rozkładowi prawdopodobieństwa. Pojedyncza odstająca od pozosta­łych (ang. outlying) próbka, którą na Rys. 6.4 jest obiekt nr 2, ma znaczący wpływ na wyuczone granice decyzyjne, o ile nałożony jest wymóg zgodności. Przykład ten poka­zuje, iż wymóg zgodności zbioru zredukowanego ze zbiorem oryginalnym może prowadzić do gorszej jakości otrzymanego zbioru niż użycie algorytmu, który nie nakłada takiego wymogu. Wyniki testów zamieszczonych w Rozdz. 6.5 potwierdzają tę hipotezę.
Pobieranie 6.5 Mb.

Share with your friends:
1   ...   38   39   40   41   42   43   44   45   ...   54




©operacji.org 2020
wyślij wiadomość

    Strona główna