Politechnika Łódzka


Lokalny wybór zredukowanego zbioru odniesienia



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

6.4. Lokalny wybór zredukowanego zbioru odniesienia

W Rozdz. 3.2.2 omówiono koncepcję lokalnego wyboru klasyfikatora. Jak wspomnia­no, szybkość klasyfikacji w tej klasie algorytmów jest silnie uzależniona od kryterium wybierającego lokalnie dany klasyfikator. Ponieważ celem poniższych rozważań jest skonstruowanie szybkiego klasyfikatora (dzięki redukcji szybszego niż reguła 1-NN z pełnym zbiorem odniesienia), więc należy wziąć pod uwagę kryteria bardzo szybkie.

Rozważono dwie możliwości szybkiego lokalnego wyboru klasyfikatora dla danej próbki (Grabowski, 2002c; Grabowski i Jóźwik, 2003).

Pierwszy schemat rozdziela zbiór uczący na rozłączne (możliwie skupione) podzbiory, czyli generuje klastry. W procesie uczenia szereg wygenerowanych „global­nie” klasy­fikatorów jest testowanych na próbkach należących do poszczególnych pojedynczych klastrów i z każdym klastrem kojarzony jest jeden, najlepszy dla tego klastra, klasyfika­tor. W czasie klasyfikacji dla testowej próbki wyznaczany jest najbliż­szy klaster — w sensie najbliższego środka ciężkości klastra — a następnie klasyfikacja dokonywana jest przy pomocy skojarzonego z tym klastrem klasyfikatora. Należy zaznaczyć, że klasteryzacja zbioru odniesienia była już wykorzystywana w schematach klasyfikacji (Jóźwik i Stawska, 1999; Kuncheva, 2000), ale nie łączono jej z redukcją zbioru odniesienia.



Drugi schemat dzieli na rozłączne podzbiory (regiony) nie zbiór uczący, a całą przestrzeń. Ponieważ istotna jest szybkość ustalenia przynależności danej próbki do regionu, więc postanowiono dzielić przestrzeń hiperpłasz­czyznami. Przykładowo, trzy hiperpłasz­czyzny dzielą przestrzeń na rozłącznych regionów. Podobnie jak w pierwszym schemacie, z każdym regionem jest skojarzony jeden z nauczonych wcześniej (globalnie) klasyfikatorów: mianowicie ten, który na zbiorze próbek ze zbioru uczącego należących do danego regionu przestrzeni popełnia najmniej błędów. Klasyfikacja polega na znalezieniu regionu przestrzeni, do którego należy dana próbka (przy rozcięciu przestrzeni hiperpłaszczyznami jest to w praktyce bardzo szybkie), a następnie użyciu skojarzonego z wyznaczonym regionem klasyfika­tora.

Poglądową ilustrację działania obu metod podziału zbioru przedstawia Rys. 6.5; zbiór odniesienia dzielony jest na 4 regiony.



(a) (b)


Rys. 6.5. Podział zbioru na:
(a) regiony przy pomocy płaszczyzn;
(b) klastry, np. metodą k średnich

Poniżej podano szczegóły implementacji obu schematów. W pierwszym schemacie dokonywana jest klasteryzacja zbioru odniesienia znaną metodą k średnich (MacQueen, 1967), gdzie zadana liczba klastrów . Poniżej przedstawiono formalny opis tego algorytmu.
Uczenie (L, l)

1. Wygeneruj niezależnie od siebie L klasyfikatorów D1, ..., DL przy użyciu zbioru odniesienia S zawierającego obiekty z przestrzeni X.



2. Dokonaj klasteryzacji S metodą k średnich z zadaną liczbą klastrów otrzymując klastry C1, ..., Ck. Znajdź środki ciężkości otrzymanych klastrów
i oznacz je przez gc1, ..., gck.

3. Dla każdego klastra Cj estymuj jakość klasyfikacji klasyfikatorów D1, ..., DL­


i oznacz przez Dbest(j) klasyfikator o najmniejszym błędzie w tym klastrze.

4. Zwróć gc1, ..., gck oraz Dbest(1), ..., Dbest(k).


Pobieranie 6.5 Mb.

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




©operacji.org 2020
wyślij wiadomość

    Strona główna