Ćwiczenia 4
Operacje genetyczne - algorytm wczesnego stopu
Zadanie do wykonania:
" Zaimplementuj w dowolnym języku programowania, algorytm wczesnego stopu
bazujący na genetycznych operacjach krzyżowania i mutacji. W procesie klasyfikacji
użyj algorytmu k-NN dla k=5. Celem zadania jest znalezienie pokolenia obiektów
treningowych, które daje maksymalne wyniki klasyfikacji systemu testowego (TST)
przy jednocześnie jak największym wyniku klasyfikacji systemu walidacyjnego TST-
valid.
" W załączniku ćwiczenia znajdują się pliki:
TRN.txt - system treningowy, który będzie modyfikowany operacjami genetycznymi
TST.txt - system testowy, na podstawie którego kolejne systemy treningowe będą
akceptowane lub nie.
TSTvalid.txt - system testowy walidacyjny, za pomocą którego będziemy mogli za-
stosować algorytm wczesnego stopu.
" Wyniki accuracy klasyfikacji systemu TST oraz TSTvalid z kolejnych pokoleń
systemów treningowych przedstaw na wykresie zaznaczając punkt stopu.
Teoria do ćwiczeń:
Operacja krzyżowania:
W sensie systemu decyzyjnego jest mechanizmem polegającym na wytwarzaniu z
pewnych ustalonych części dwóch losowych obiektów nowego obiektu potomnego.
W naszym ćwiczeniu przyjmujemy, że operacja krzyżowania jest postaci,
Dzielimy dwa losowe obiekty systemu decyzyjnego na części,
1 2 3 8 1 5 1
5 4 2 1 7 8 2
i wytwarzamy z nich dwa obiekty potomne postaci,
1 2 3 1 7 8 1
5 4 2 8 1 5 2
Operacja mutacji:
Przyjmujemy, że mutacja obiektów to zamiana miejscami losowych atrybutów pary
losowych obiektów. Przyjmijmy, że wylosowaliśmy dwa obiekty postaci
1 2 3 8 1 5 1
5 4 2 1 7 8 2
wylosowaliśmy atrybut numer 3 i zamieniamy miejscami wartości 3 oraz 2 otrzymu-
jąc obiekty,
1 2 2 8 1 5 1
5 4 3 1 7 8 2
Operacje krzyżowania i mutacji stosowane są z myślą utworzenia obiektów potom-
nych w systemie decyzyjnym treningowym o cechach lepszych od obiektów pierwot-
nych w sensie lepszej efektywności w klasyfikacji danych testowych.
Wykonanie zadania krok po kroku,
Procedurę zaczynamy od klasyfikacji metodą 5-nn systemu TST i TSTvalidate za
pomocą systemu treningowego pierwotnego. Otrzymany wynik accuracy z pierwszej
klasyfikacji systemu TST będzie naszą wyjściową jakością klasyfikacji, na podstawie
której oceniany będzie kolejny system treningowy.
Następnie modyfikujemy obiekty systemu treningowego metodami genetycznymi,
wykonujemy ustaloną ilość operacji krzyżowania i mutacji tak aby efekt modyfika-
cji miał wpływ na jakość klasyfikacji TST. Sprawdzamy, czy dana seria modyfikacji
zwiększa accuracy klasyfikacji TST, jeżeli tak, zmodyfikowane obiekty są zapisywane
na stałe do systemu treningowego, a obiekty pierwotne usuwane. Ostatecznie wyko-
nujemy klasyfikacje TST oraz TSTvalid za pomocą nowego systemu treningowego
TRN1.
Operacje modyfikacji i klasyfikacji są kontynuowane do momentu gdy accuracy kla-
syfikacji systemu walidacyjnego TSTvalid zaczyna się regularnie zmniejszać.
Finalnym krokiem zadania jest sporządzenie wykresów accuracy dla TST i TSTvalid
z całego procesu uczenia i zaznaczenie na wykresie TSTvalid orientacyjnego punktu
stopu.
Idea wczesnego stopu polega na tym, że przestajemy tworzyć kolejne pokolenia
systemu treningowego w momencie, gdy przy wzroście klasyfikacji systemu TST,
klasyfikacja TSTvalidate zaczyna istotnie maleć. Zatrzymujemy uczenie klasyfikato-
ra w obszarze maksymalnego accuracy systemu walidacyjnego. Przykładowy wykres
wymagany w ćwiczeniu jest postaci,