\chapter{Selekcja i optymalizacja prototypów dla reguł najbliższego sąsiada} \label{chap:ProtoSel}
Problem selekcji i optymalizacji prototypów dla algorytmu \kNN jest niezmiernie istotny,
gdyż bezpośrednio wpływa na uzyskaną zdolność uogólniania algorytmu, jednocześnie
zmniejszając jego złożoność obliczeniową. Problem ten w dużo większym stopniu dotyczy
metod reguł prototypowych, gdyż transparentność modelu jest uzyskiwana właśnie poprzez
reprezentację danych w postaci minimalnego zbioru prototypów gwarantujących dużą zdolność
generalizacji.\\
Problem znajdowania optymalnej reprezentacji danych w postaci wektorów referencyjnych
można podzielić na ich selekcję i optymalizację. Pierwsza grupa metod (selekcja)
charakteryzuje się wyborem prototypów bezpośrednio jako wektorów zbioru treningowego,
podczas gdy metody optymalizacji zajmują się optymalizacją położenia wektorów
prototypowych poprzez minimalizację pewnego kryterium. W przypadku metod
optymalizacji nie jest wymagane by położenie prototypu odpowiadało konkretnemu
przypadkowi ze zbioru treningowego. W metodach optymalizacji dają się wyznaczyć dwie
główne strategie - optymalizacja bezpośrednia, gdzie minimalizacji podlega bezpośrednio
błąd klasyfikacji danych oraz optymalizacja pośrednia, gdzie wykorzystuje się algorytmy
nienadzorowanej analizy danych, jak metody analizy skupień (klasteryzacji).\\
Inną możliwością podziału metod znajdywania prototypów jest podział na metody
przyrostowe, w których rozpoczyna się poszukiwanie wektorów wzorcowych od pustego zbioru
$\BP =  \emptyset$ dodając do niego nowe przypadki maksymalizujące pewne kryterium oraz
metody redukcyjne. Rozpoczynają one działanie od pełnego zbioru prototypów $\BP=\BT$
usuwając z niego wektory zbędne, które nie wpływają na poprawę generalizacji algorytmu.
Cechą charakterystyczną metod przyrostowych jest fakt, iż zawiera się w niej cała grupa
metod optymalizacji.\\
 W niniejszej rozprawie algorytmy doboru optymalnego zbioru wektorów referencyjnych
  podzielono według pierwszego kryterium na algorytmy selekcji
prototypów, algorytmy klasteryzacji danych służące do wyboru przypadków referencyjnych
oraz metody optymalizacji w znaczeniu optymalizacji bezpośredniej.

\section{Metody selekcji prototypów} \label{sec:InstanceSel}
Rodzina algorytmów selekcji prototypów jest pierwszą grupą metod użytych w celu polepszenia
jakości klasyfikacji algorytmu \kNN. W systemach reguł prototypowych ma ona
kilka istotnych właściwości bardzo przydatnych podczas interpretacji
wyników. Jak już zostało wspomniane powyżej, metody selekcji wybierają wektory
referencyjne spośród elementów zbioru treningowego, co oznacza że zbiór wybranych prototypów
stanowi podzbiór realnych przypadków, które wystąpiły w przeszłości. Ma to szczególne
znaczenie dla pewnych zastosowań w tym medycznych, gdzie prototyp stanowi konkretny przykład pacjenta
z określonym schorzeniem lub prawnych w prawie precedensowym, gdzie wybrany prototyp
jest konkretną sprawą, która miała miejsce w przeszłości.\\
W metodach selekcji prototypów można wyznaczyć dwa główne zadania, kondensacji danych -
metody, w których usuwane są wektory ,,wewnętrzne'', leżące daleko od granicy decyzji nie mające
wpływu na jakość klasyfikacji oraz metody filtrów lub edycji
usuwające wektory odstające (ang. outliers) \cite{Duin_ProtoSel}.
Metody selekcji prototypów stosowane w praktyce zawierają często obydwa typy algorytmów, usuwając zarówno
wektory odstające, jak i kondensując dane, co w znaczny sposób wpływa na uzyskaną jakość
rezultatów.\\
Ze względu na nieciągłość funkcji decyzyjnej klasyfikatora \kNN najczęściej
stosowanym rozwiązaniem są metody przeszukiwania. W literaturze problem selekcji
wektorów referencyjnych był studiowany przez wiele ośrodków naukowych, dlatego też
poniżej zamieszczono listę najpopularniejszych metod pomijając wiele z nich jak
Variable Similarity Metric zaproponowaną przez Lowe, Model Class Selection Brodleya,
Typical Instance Based Learning stanowiącą pomysł Zanga, RISE Domingosa \cite{Domingos-RI_IBL}
i wiele innych jak \cite{Oommen-RecProSel}. Wiele metod selekcji prototypów, w szczególności bazujących na algorytmach
genetycznych/ ewolucyjnych można znaleźć również na stronach projektu Keel \cite{Keel}
%-------------------------------------------------------
\subsection{Metoda ENN}
Pierwszym bardzo skutecznym i prostym algorytmem selekcji prototypów jest zaproponowana
przez Wilsona \cite{P-Wilson-EkNN} reguła edycji ENN (ang. editing nearest neighbor rule).
Metoda ta usuwa wszystkie wektory stanowiące szum w zbiorze danych treningowych. Dla
każdego wektora wyznaczanych jest $k$ najbliższych sąsiadów spośród zbioru $\bf{T}$,
które użyte są do głosowania. Jeżeli wynikiem głosowania $k$ sąsiadów jest błędna klasa,
wówczas wektor taki zostaje oznaczony do usunięcia $\BP=\bf{T}\setminus\bf{\bar{T}}$,
gdzie $\bf{\bar{T}}$ jest zbiorem wektorów przeznaczonych do usunięcia. Rezultatem
działania tego algorytmu jest więc usunięcie wektorów odstających oraz wektorów
brzegowych, a jedyną wartością nastawną jest $k$ (autor zaleca $k=3$). Działanie algorytm przedstawia schemat \reff{fi:alg-ENN}.
\begin{algorithm}
\begin{algorithmic}
\REQUIRE $\BT$
\STATE $m \leftarrow \mathop{sizeof}(\BT)$;\\
\STATE $rem_i \leftarrow 0$;\\
\FOR{$i=1 \ldots m$}
\STATE $\bar{C}(\Bx_i)=$\kNN$\left({ (\BT \setminus \Bx_i),\Bx_i}\right)$; \\
\IF {$C(\Bx_i) \ne \bar{C}(\Bx_i)$}
\STATE $rem_i=1;$
\ENDIF
\ENDFOR \\
\FOR{$i=1 \ldots m$}
\IF{$rem_i==1$}
\STATE $\BT = \BT \setminus \Bx_i$
\ENDIF
\ENDFOR
\RETURN $\BP$
\end{algorithmic}
\caption{Schemat algorytmu ENN}
\label{fi:alg-ENN}
\end{algorithm}
%-------------------------------------------------------
\subsection{Modyfikacje algorytmu ENN}
Modyfikacją algorytmu ENN jest metoda RENN (ang. repeated $ENN$), gdzie algorytm ENN jest wielokrotnie
powtarzany aż do momentu, w którym żaden z wektorów nie jest już usuwany w wyniku
działania algorytmu ENN (schemat \reff{fi:alg-RENN}). Kolejną modyfikacją jest algorytm $All$ \kNN, gdzie porównywane są wyniki dla różnych wartości parametru $k$. Obydwie te metody zostały zaproponowane
przez Tomeka i opisane w \cite{P-Tomek-eNN}.
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$
	$flaga \leftarrow \TRUE$
	\WHILE{falga}
		\STATE $flaga \leftarrow \FALSE$
		\STATE $\bar{\BP}=$ENN$(\BP,\BT)$
		\IF{$\bar{\BP} \ne \BP$}
			\STATE $flaga \leftarrow \TRUE$
		\ENDIF
	\ENDWHILE
	\RETURN $\BP$
\end{algorithmic}
\caption{Schemat algorytmu RENN}
\label{fi:alg-RENN}
\end{algorithm}
%-------------------------------------------------------
\subsection{Metoda kondensacyjna CNN}
Algorytm CNN (ang. condensed nearest neighbor rule) jest pierwszą metodą kondensacyjną
zaproponowaną przez Harta \cite{P-Hart-CNN} w 1967 roku. Metoda ta należy do grupy
przyrostowych. Rozpoczyna ona od losowo wybranego wektora jako prototypu $\BP$, następnie w
pętli klasyfikuje pozostałe przypadki i jeżeli któryś zostaje błędnie sklasyfikowany przez
aktualny zbiór prototypów jest on do niego dodawany $\BP=\BP\cup\Bx$. Procedura ta
jest powtarzana aż wszystkie wektory zostają sklasyfikowane poprawnie.\\
Wynikiem działania CNN jest mała liczba wektorów referencyjnych, mniejsza niż w
algorytmach z serii ENN. Wadą tego rozwiązania jest jednak występowanie wszystkich
wektorów odstających i brzegowych, co nie wpływa na poprawę generalizacji modelu
wynikowego. Inną wadą rozwiązania CNN jest losowa inicjalizacja algorytmu. Powoduje to, że
wielokrotny start może prowadzić do nieporównywalnych zbiorów wynikowych, na co również
wpływa losowa kolejność prezentacji wektorów podczas procesu uczenia. Działanie algorytmu przedstawia schemat \reff{fi:alg-CNN}.
\begin{algorithm}
\begin{algorithmic}
\REQUIRE $\BT$
\STATE $m \leftarrow \mathop{sizeof}(\BT)$
\STATE $\Bp_1 \leftarrow \Bx_1$
\STATE $flaga \leftarrow \TRUE$
\WHILE{flaga}
\STATE $flaga \leftarrow \FALSE$
\FOR{$i=1 \ldots m$}
\STATE $\bar{C}(\Bx_i)=$\kNN$(\BP,\Bx_i)$
\IF{$\bar{C}(\Bx_i) \ne C(\Bx_i)$}
\STATE $\BP \leftarrow \BP \cup \Bx_i$;
\STATE $\BT \leftarrow \BT \setminus \Bx_i$
\STATE $flaga \leftarrow \TRUE$
\ENDIF
\ENDFOR
\ENDWHILE
\RETURN $\BP$
\end{algorithmic}
\caption{Schemat algorytmu CNN}
\label{fi:alg-CNN}
\end{algorithm}

%\subsection{Selective Nearest Neighbor Rule}
%Selective Nearest Neighbor Rule (SNN) stanowi rozwinięcie algorytmu CNN. Kryterium
%zaproponowane przez Rittera w metodzie SNN bazuje na selekcji prototypów, które spełniają
%warunek, iż każdy wektor treningowy musi być bliżej prototypu $\BP$ pochodzącego z tej
%samej klasy co on sam. Rezultatem końcowym algorytmu jest najmniejszy zbiór $\BP$
%spełniający opisane kryterium. Ogólnie wyniki działania algorytmu SNN może
%scharakteryzować jako bardziej dokładne niż CNN z mniejszą liczbą wektorów
%referencyjnych.
%-------------------------------------------------------
\subsection{Metody redukcyjne RNN oraz DROP1-5}
Gates zaproponował algorytm RNN (ang. reduced nearest neighbor rule), którego zasada działania
jest również podobna do CNN, z tą jednak różnicą, że jest to algorytm należący do grupy
redukcyjnych. Rozpoczyna on od pełnego zbioru wektorów referencyjnych $\BP=\bf{T}$ i
usuwa nieużyteczne wektory ze zbioru $\BP$. Kryterium użytym przez Gatesa jest nie
pogarszanie wyników klasyfikacji zbioru $\BT$. Algorytm ten jest niestety obliczeniowo
bardziej kosztowny niż CNN w procesie uczenia, jednakże jego wynikiem jest mniejszy
rozmiar $\BP$, co przynosi wymierne korzyści w procesie klasyfikacji przypadków testowych.
Inną zaletą tego algorytmu jest usuwanie wektorów odstających, a wynikowy zbiór
prototypów stanowi zbiór wektorów brzegowych stanowiących, leżących bezpośrednio blisko
granicy.\\
Algorytm DROP stanowi natomiast grupę metod, zaś ich nazwa pochodzi od rozwinięcia skrótu {\it decremental reduction optimization procedure} i jest rozwinięciem metod RT1-3 (ang. reduction
technique) zaproponowanych przez Wilsona i Martineza
\cite{Martinez-InstancePrunTech,Martinez-ReductionTechniq}. \\
Pierwszy z algorytmów - Drop1 jest bardzo podobny do algorytmu RNN z tą różnicą, iż
dokładność jest walidowana na zbiorze $\BP$ w zamian za $\BT$, jak to miało miejsce w
oryginale. Algorytm ten usuwa zarazem wektory odstające, jak i szum - jednak wadą tego
rozwiązania była możliwość usuwania całych klastrów danych lub w skrajnych przypadkach
całych klas. Dlatego też autorzy zaproponowali modyfikację nazwaną Drop2, która
porządkowała kolejność prezentacji wektorów w zależności od odległości do najbliższego
wroga (najbliższego wektora z przeciwną etykietą klasy) oraz wrócili do walidacji
dokładności algorytmu realizowanej na pełnym zbiorze treningowym $\BT$.\\
W metodzie Drop3 Wilson i Martinez zastosowali dodatkowo filtr poprzedzający proces
kondensacji danych w postaci algorytmu ENN. Dzięki takiemu rozwiązaniu zredukowana
została liczba prototypów oraz zmniejszono tendencję do przeuczania sie systemu. Kolejny
algorytm Drop4 dodatkowo poprawiał zdolności generalizacji modelu poprzez modyfikację
algorytmu ENN tak, by sprawdzał czy filtracja danego wektora nie wpłynie negatywnie na
klasyfikację pozostałych przypadków. Ostatni z algorytmów Drop5 jest bardzo podobny do
algorytmu Drop2 z tą jednak różnicą, iż zamieniona została strategia porządkowania
wektorów od najbliższego przeciwnika do najdalszego. Taka strategia spowodowała
wygładzenie granicy decyzji, usuwając w pierwszej kolejności wektory leżące bezpośrednio
na granicy pomiędzy klasami.

%-------------------------------------------------------
\subsection{Metody GE oraz RNG}
Obydwa algorytmy stanowią rozwinięcie metod kondensacji danych pozostawiając jedynie
wektory aktywnie tworzące granicę decyzji pomiędzy klasami. Bazują one na diagramach
Voronoi, które jednoznacznie definiują granicę pomiędzy poszczególnymi prototypami.
Obydwa te algorytmy wybierają jedynie te wektory, które sąsiadują w sensie Voronoi
 z wektorami z przeciwnych klas, dzięki czemu granica decyzji pozostaje niezmieniona
 w stosunku do oryginalnego algorytmu 1NN.\\
Głównym problemem występującym przy wykorzystaniu diagramów Voronoi jest złożoność
obliczeniowa. Algorytmy GE (ang. gabriel editing) ma złożoność rzędu $O(n^3)$ i bazuje na sprawdzeniu dla każdej pary zbioru prototypów $\Bp_a$ i $\Bp_b$ zależności  \reff{eq:RE}.
\be
  \mathop{\mbox{\Large{$\forall$}}}\limits_{a\ne b\ne c} D^2(\Bp_a,\Bp_b)>D^2(\Bp_a,\Bp_c)+D^2(\Bp_b,\Bp_c)
  \label{eq:RE}
\ee
Podobnie algorytm RNG (ang. relative neighborhood graph) \cite{P-Poulsen-ProxGraphs} dla każdej pary wektorów  $\Bp_a$ oraz $\Bp_b$ posługuje się zależnością \reff{eq:RNG}.
\be
	\mathop{\mbox{\Large{$\forall$}}}\limits_{a\ne b\ne c} D(\Bp_a,\Bp_b)\ge \max(D(\Bp_a,\Bp_c),D(\Bp_b,\Bp_c))
  \label{eq:RNG}
\ee

%-------------------------------------------------------
\subsection{Metoda IBL}
IBL (ang. instance base learning) \cite{Aha-IBL} stanowi ogólne podejście do problemu
eksploracji danych składające się z pięciu różnych metod. IB1 jest metodą bazową będącą
podstawą do dalszych rozwiązań. Jest to algorytm \kNN, w którym zaimplementowano narzędzia
do analizy brakujących wartości oraz jako wstępne przetwarzanie danych dodano moduł
normalizacji atrybutów ciągłych. W algorytmie IB2 (bazując na IB1) zastosowano podobne
podejście do CNN z tą jednak różnicą, że realizowane jest pojedyncze przejście przez
zbiór danych treningowych. Kolejną modyfikacją jest algorytm IB3, będący również
algorytmem przyrostowym jak IB2 - jednakże zastosowano w nim zasadę ,,zaczekaj i sprawdź''
(ang. wait and see), aby wyznaczyć zbiór wektorów, które będą gwarantowały poprawną
klasyfikację i które należy zachować jako prototypy $\BP$. W celu wyznaczenia
akceptowalnych przypadków referencyjnych w algorytmie IB3 posłużono się przedziałem
ufności zdefiniowanym jako:

\be \label{eq:IBL3} AC_{up|low}=\frac{{p + {{z^2 } \mathord{\left/
 {\vphantom {{z^2 } {2n \pm z\sqrt {{{p(1 - p)} \mathord{\left/
 {\vphantom {{p(1 - p)} n}} \right.
 \kern-\nulldelimiterspace} n} + {{z^2 } \mathord{\left/
 {\vphantom {{z^2 } {4n^2 }}} \right.
 \kern-\nulldelimiterspace} {4n^2 }}} }}} \right.
 \kern-\nulldelimiterspace} {2n \pm z\sqrt {{{p(1 - p)} \mathord{\left/
 {\vphantom {{p(1 - p)} n}} \right.
 \kern-\nulldelimiterspace} n} + {{z^2 } \mathord{\left/
 {\vphantom {{z^2 } {4n^2 }}} \right.
 \kern-\nulldelimiterspace} {4n^2 }}} }}}}{{1 + {{z^2 } \mathord{\left/
 {\vphantom {{z^2 } n}} \right.
 \kern-\nulldelimiterspace} n}}}
\ee %%
gdzie $p$ oznacza prawdopodobieństwo sukcesu w $n$ próbach, natomiast $z$ jest poziomem
ufności.\\
Wg. założeń algorytmu prototyp jest akceptowalny, jeżeli dolna granica jego dokładności (z
poziomem ufności 0.9) jest większa niż górna granica częstości występowania jego klasy
oraz prototyp jest usuwany, jeżeli górna granica jego dokładności jest niższa (ze
współczynnikiem ufności 0.7) niż dolna granica częstości występowania jego klasy.\\
Dokładna analiza algorytmów IB1-3 dokonana przez autora D.Aha wskazała na małą dokładność
uzyskiwaną przy analizie danych zawierających dużą liczbę cech, dlatego też autor
zaproponował dodatkowe dwa algorytmy IB4 oraz IB5 mające rozwiązać ten problem.\\
Ogólne podejście IBL rozwijane przez Aha znalazło szerokie zainteresowanie również wśród
innych autorów i doczekało się wielu modyfikacji, w tym zaproponowany przez Wilsonsa i
Martineza algorytm Integrated Instance-Based Learning \cite{Martinez-IBL}, gdzie autorzy
dodali narzędzia automatycznego doboru parametrów i ważenia decyzji lub podejście
Hullermeier, gdzie w oryginalnym algorytmie wykorzystano teorię posybilistyczną
(ang. possibilistic theory) \cite{Hullermeier-PossIBL}

%\subsection{RISE}
%RISE Domingos'a \cite{Domingos-RI_IBL}
%-------------------------------------------------------
%\subsection{Weighted Instance Typicality Search}
%Weighted Instance Typicality Search (WITS) jest algorytmem zaproponowanym przez Morringa
%i Martineza \cite{Martinez-WITS}. W prezentowanym algorytmie autorzy połączyli ze sobą
%techniki ważenia i redukcji prototypów, bazujące na stosunku podobieństwa
%wewnątrzklasowego i miedzyklasowego zwanego {\it typowością} (ang. typicality). Podobieństwo
%wewnątrzklasowe wektora $\Bp$ definiowane jest jako średnie dopełnienie odległości
%$(1-D\left({\Bp,\Bx}\right))$ wektora $\Bp$, do wszystkich wektorów $\Bx$ należących do
%tej samej klasy co $\Bp$, zaś podobieństwo międzyklasowe liczone jest podobnie z tą
%różnicą, że średnie dopełnienie odległości liczona jest do wektorów $\Bx$ z klasy przeciwnej niż $\Bp$.
%Wartość {\it typowości} ma pewne specjalne cechy - mianowicie wektory leżące w pobliżu
%centrów klas mają duże wartości typowości, podczas gdy leżące na granicy pomiędzy klasami
%mają małe wartości, natomiast najmniejsze wartości odpowiadają wektorom odstającym. Cecha
%ta została użyta przez autorów do porządkowania procesu szukania prototypów. Początkowo
%wektory są sortowane począwszy od najbardziej typowych osobno dla każdej z klas, a
%następnie analizowana jest ich przydatność jako prototypów. Jeżeli dany wektor zostaje
%błędnie sklasyfikowany przez aktualny zbiór $\BP$, a nie był jeszcze rozważany jako
%potencjalny prototyp jest on dodawany do $\BP$, po czym algorytm WITS próbuje określić
%optymalną wagę dla tego prototypu. W ostatnim kroku sprawdzane jest kryterium zdolności
%generalizacji algorytmu. Mikrokod programu przedstawia schemat \reff{fi:alg-Wits}
%\begin{algorithm}
%\begin{algorithmic}
%\REQUIRE $\BT$
%\STATE $m \leftarrow sizeof(\BT)$
%\STATE $Tip \leftarrow Typicality(\BT)$ \COMMENT{Inicjalizacja wartości typowości}
%\STATE ${\bf sBT} \leftarrow sort(Tip)$ \COMMENT{Sortuj wektory $\BT$ w zależności od typowości}
%\FOR{$i=1 \ldots m$}
%	\STATE $Untraind_i \leftarrow 1$
%\ENDFOR \COMMENT{Oznacz wektory nie użyte do uczenia}
%\WHILE{($Acc($\kNN$(\BP,{\bf sBT})) < 100\%)$ lub $sum(Untrained)==0$} 
%	\STATE ${\bf nP} \leftarrow AddInstanceToSolution(\BP,\BT_Untrained,)$ \COMMENT{Dodaj nowy wektor do rozwiązań}
%	\STATE ${\bf nP} \leftarrow SetNewInstanceWeights({\bf nP})$ \COMMENT{Określ wagi prototypów}
%	\IF{not $PassGeneralization({\bf nP})$} 
%		\STATE $Untrained \leftarrow MarkInstancesTrained()$ \COMMENT{Oznacz wektory jako nieużyteczne}
%	\ELSE	
%		\STATE $\BP \leftarrow {\bf nP}$	\COMMENT{Zapamiętaj rozwiązanie}
%	\ENDIF
%\ENDWHILE
%\RETURN{$\BP$}
%\end{algorithmic}
%\caption{Schemat algorytmu WITS}
%\label{fi:alg-Wits}
%\end{algorithm}
%-------------------------------------------------------
\subsection{Metody selekcji losowej, genetycznej i ewolucyjnej} \label{SubSec:RandGenSel} 
Duża grupa metod selekcji prototypów bazuje na metodach stochastycznego przeszukiwania,
czego najprostszym przykładem są algorytmy selekcji losowej i Monte Carlo
\cite{Kunch-NPC-ProtoSel,Kunch-Book,Skalak-ProtoSelRMHC,Duin_ProtoSel} występujące w
dwóch typowych formach. Obydwie formy bazują na skończonej liczbie iteracji $\it{z}$, w
których niezależnie losowanych jest $l$ prototypów, a jako funkcja celu używany jest błąd
klasyfikacji klasyfikatora \kNN (zwykle $k=1$).\\
 Typowe podejścia do problemu losowania determinujące wspomniane dwie formy można opisać jako:
\begin{itemize}
\item prototypy losowane jednocześnie z całego zbioru treningowego (schemat \reff{fi:alg-MC1})
\item prototypy losowane niezależnie z każdej z klas z osobna, co determinuje konieczność określenia
$l_{1..c}$ niezależnych wartości liczby prototypów osobno dla każdej klasy (schemat \reff{fi:alg-MC2})
\end{itemize}

\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$, $l$, $maxit$
	\FOR{$i=1 \ldots maxit$}
		\STATE ${\bf tP} \leftarrow Rand(\BT,l)$
		\STATE $tacc \leftarrow Acc(1NN({\bf tP},\BT))$
		\IF{$tacc > acc$}
			\STATE $acc \leftarrow tacc$
			\STATE $\BP \leftarrow {\bf tP}$
		\ENDIF
	\ENDFOR
	\RETURN $\BP$
\end{algorithmic}
  \caption{Algorytm Monte Carlo w wersji typu 1}
  \label{fi:alg-MC1}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$, ${\bf l}$, $maxit$
	\FOR{$i=1 \ldots maxit$}
		\STATE ${\bf tP}=\emptyset$
		\FOR{$j=1\ldots c$}
			\STATE ${\bf tP} \leftarrow {\bf tP} \cup Rand(\BT_{C_j},l_j)$
		\ENDFOR
		\STATE $tacc \leftarrow Acc(1NN({\bf tP},\BT))$
		\IF{$tacc > acc$}
			\STATE $acc \leftarrow tacc$
			\STATE $\BP \leftarrow {\bf tP}$
		\ENDIF
	\ENDFOR
	\RETURN $\BP$
\end{algorithmic}
 \caption{Algorytm Monte Carlo w wersji typu 2}
 \label{fi:alg-MC2}
\end{algorithm}
Innym przykładem metod stochastycznych jest algorytm Random Mutation Hill Climbing
zaproponowany przez Skala \cite{Skalak-ProtoSelRMHC}. W podejściu tym każdy prototyp zakodowany jest w postaci podłańcuchów binarnych o długości $\log_2m$, a całkowita długość łańcuch binarnego dla $l$ prototypów wynosi więc $l \log_2n$. Podczas każdej iteracji algorytmu
wspinaczki następuje permutacja jednego bitu. Wynikiem działania jest więc zbiór bitów reprezentujący $l$ prototypów dający największe dopasowanie, definiowane jako dokładność klasyfikatora 1NN. Uproszczoną budowę algorytmu przedstawia schemat \reff{fi:alg-RMHC}.

\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$, $l$, $maxit$
	\STATE $m \leftarrow sizeof(\BT)$
	\STATE $st \leftarrow Bin(l\log_2m)$ 
	\STATE $SetBit()$
	\FOR{$i=1\ldots maxit$}
		\STATE ${\bf tBP} \leftarrow GetProto(\BT,st)$
		\STATE $tacc \leftarrow Acc(1NN({\bf tBP},\BT))$
		\IF{$tacc>acc$}
			\STATE $acc \leftarrow tacc$
			\STATE $\BP \leftarrow {\bf tBP}$
		\ENDIF
		\STATE $st \leftarrow PermuteBit(st)$
	\ENDFOR
	\RETURN $\BP$
\end{algorithmic}
 \caption{Schemat algorytmu RMHC}
 \label{fi:alg-RMHC}
\end{algorithm}


Problemem selekcji prototypów metodami genetycznymi i ewolucyjnymi zajmowało się wielu
autorów, gdzie na uwagę zasługuje Keel Project, na którego stronach internetowych
\cite{Keel} można znaleźć dużą rodzinę wspomnianych metod. Zagadnienie to było również
poruszane w pracach Kunchevy m.in. \cite{Kunch-NPC-ProtoSel}, gdzie badania autorki
wskazują, iż w problemach analizy małych zbiorów danych proste metody selekcji losowej
przewyższają dokładnością bardziej zaawansowane metody genetyczne.
%-------------------------------------------------------
\subsection{Encoding Length}
Bardzo ciekawym rozwiązaniem selekcji wektorów referencyjnych jest algorytm zaproponowany
przez Cameron Jonesa \cite{CamJones-ELH}. Prace tego autora skoncentrowane były na
poprawieniu algorytmu Ahy IB3 oraz Skali Random Mutation Hill Climbing (RMHC) w skrócie opisane w rozdziale \ref{SubSec:RandGenSel} przy wykorzystaniu heurystyki Encoding Length Heuristic (ELH) - szczegóły heurystyki zostały opisane w rozdziale \ref{sec:NumOfProto}. Heurystyka ELH została tutaj użyta jako funkcja dopasowania, która łączy w sobie dokładność klasyfikacji z liczbą prototypów. Główną bazą
algorytmu była metoda IB3, gdzie po wstępnej selekcji zbiór $\BP$ był oczyszczany
metodami zachłannego przeszukiwania wykorzystując ELH do oceny prototypów, tak by zbiór wynikowy zawierał
jedynie istotne wektory prototypowe (algorytm nazwany Pre/All, zwany również przez Wilsona i Martineza ELGrow). Inną modyfikacją był algorytm Explore rozszerzający Pre/All poprzez RMHC jako końcowy etap przetwarzania.\\
Na uwagę zasługuje fakt, iż metoda ta przez wielu autorów
\cite{Martinez-ReductionTechniq,CamJones-ELH,Norb-ProtoSel1} była oceniana jako jedna z
najlepszych, gwarantując bardzo mały zbiór prototypów z maksymalnie dużą dokładnością
klasyfikacji.

%-------------------------------------------CLUSTERING ----------------------------------

\section{Metody klasteryzacji w poszukiwaniu prototypów} \label{sec:ProtoSel-clust}
Powszechnie stosowanymi metodami znajdywania wektorów referencyjnych opisywanymi między innymi
\cite{Kunch-NPC-ProtoSel,P-Chang-kNN,Kunch-Book,Blachnik-CFCM,Blachnik-FuzzyProto,Duin_ProtoSel}
są różne metody analizy skupień zwane również metodami klasteryzacji. W odróżnieniu od
metod selekcji prototypów opisanych w poprzednim rozdziale \ref{sec:InstanceSel}, metody
klasteryzacji znajdują prototypy nie będące przypadkami wektorów zbioru treningowego.\\
%
Grupowanie danych jest dużą niezależną dziedziną rodziny problemów inteligencji
obliczeniowej, łączącą różne podejścia do problemu klasteryzacji. Ogólnie metody te można
podzielić na kilka grup:
\begin{itemize}
 \item Modele Gaussowskie
 \item Metody rozmytej i posibilstycznej klasteryzacji
 \item Sieci neuronowe (Samoorganizujące się mapy Kohonena)
 \item Metody hierarchiczne
\end{itemize}
Modele Gaussowskie wywodzą się z ogólnej probabilistycznej teorii Bayesa i należą do
grupy metod parametrycznej estymacji rozkładów prawdopodobieństwa. Najczęściej stosowanym
rozwiązaniem jest tutaj odwzorowywanie rozkładu danych (ich rozkładu prawdopodobieństwa
$p(x)$) przy pomocy kombinacji rożnych rozkładów normalnych
\cite{B-Duda-Hart,B-Webb-Book}.\\
Alternatywnym rozwiązaniem równie często spotykanym są metody bazujące na teorii zbiorów
rozmytych oraz teorii posibilistycznej. Najlepszym przykładem tych metod jest rozmyty
algorytm C-średnich (ang. fuzzy C-means - FCM) oraz posibilistyczny algorytm C-średnich
(Possibilistic C-means - PCM) \cite{B-Rutkowski-MetodyTechniki,B-Kruse-FuzzyClust}.
Obydwa te algorytmy w wersjach podstawowych szukają zbiorowisk danych poprzez kombinacje
Gaussowskich funkcji przynależności pokrywających każdy z atrybutów. Porównanie wyżej
opisanych metod klasteryzacji zawarte w pracy Fenga \cite{C-Feng-OverClust} wskazuje, iż
rezultaty uzyskane z obydwu rodzin metod (rozmytych i probabilistycznych) dają
porównywalne rezultaty, zaś wadą obydwu metod jest problem
inicjalizacji algorytmów.\\
Innym powszechnie stosowanym narzędziem pozwalającym na poszukiwanie zgrupowań danych są
metody kwantyzacji wektorów (ang. vector quantization - VQ) lub samoorganizujące się sieci
Kohonena (ang. self organizing maps - SOM) \cite{Kohonen-SOM-Book} należące do rodziny sieci
neuronowych. Obydwie grupy metod bazują na zasadach ,,zwycięzca bierze wszystko'' (ang. winner
takes all - WTA) lub zwycięzca bierze większość (ang. winner takes most WTM)
\cite{B-Ossowski-SieciNeuron}. Przydatność obydwu opisanych metod do problemu uczenia
klasyfikatora \kNN była testowana m.in. przez Kuncheve i Bezdeka \cite{P-Kunch-21methods} dając wyniki
porównywalne z innymi metodami selekcji prototypów.\\
Ostatnią grupę metod klasteryzacji stanowią metody hierarchiczne, które posiadają bardzo
istotną cechę, gwarantującą jednoznaczność rozwiązania. Metody hierarchiczne bazują na
budowie drzewa - dendogramów, łącząc stopniowo leżące najbliżej siebie wektory w jeden
klaster. Problem łączenia wektorów w klastry jest w opisywanej metodzie niezależną
kwestią wpływającą na kształt uzyskanych zbiorowisk. Metody hierarchiczne były jednymi z
pierwszych metod poszukiwania prototypów, czego przykładem może być algorytm  Changa
\cite{P-Chang-kNN} z 1974 roku. Metoda ta rozpoczynała od pełnego zbioru prototypów
$\BP=\BT$ i iteracyjnie łączyła pary najbliżej siebie leżących wektorów z $\BP$
zamieniając je pojedynczym przypadkiem wyznaczanym jako ważona średnia lub jak w
zmodyfikowanym algorytmie Changa (ang. modified chang method - MCA) wyznaczając położenie
zwykłą średnią. Algorytm Changa był rozwijany również przez innych, czego wynikiem był
uogólniony algorytm Changa (ang. generalized MCA) wykorzystujący prawdziwy aglomeracyjny
algorytm hierarchicznego grupowania \cite{P-Ferri-GMCA}.\\
%
%
Pękalska i inni w \cite{Duin_ProtoSel}, jak również Kunchewa
\cite{Kunch-Book,Kunch-GNPC} przedstawiają dwa różne podejścia do znajdowania prototypów
przy wykorzystaniu ogólnych metod klasteryzacji - grupowanie danych całego zbioru
treningowego z pominięciem informacji o klasach nazywane również klasteryzacją z
powtórnym etykietowaniem (ang. clustering and relabeling) oraz klasteryzacją każdej z klas
niezależnie. Kunchewa w \cite{Kunch-PrePost} nazywa również wspomniane metody odpowiednio
metodami uczenia nadzorowanego finalnego
(ang. post-supervised) i uczenia nadzorowanego poprzedzającego (ang. pre-supervised).\\
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$, $l$ 
	\ENSURE $l>c$
	\STATE ${\bf Cl} \leftarrow Cluster(\BT,l)$
	\STATE $\BP \leftarrow \emptyset$
	\FOR{i=1\ldots l}
		\STATE $\Bp_i \leftarrow {\rm mean}({\bf cl}_i)$
		\STATE $C(\Bp_i) \leftarrow \arg\max(C({\bf cl}_i))$
		\STATE $\BP \leftarrow \BP \cup \Bp_i$
	\ENDFOR 
	\RETURN $\BP$
\end{algorithmic}
 \caption{Metoda klasteryzacji z powtórnym etykietowaniem}
 \label{fi:CluRel}
\end{algorithm}
Pierwsza z metod może zostać przedstawiona jak na schemacie \reff{fi:CluRel}.
gdzie krok 4 może w zależności od wybranego rozwiązanie zostać zrealizowany jako
etykietowanie ostre lub rozmyte. W etykietowaniu ostrym klasa, do której należy prototyp
określana jest jako pojedyncza wartość uzyskana poprzez większościowe głosowanie
wszystkich wektorów należących do danego klastra. W podejściu drugim - rozmytym
etykietowaniu - każdy prototyp związany jest z każdą z klas $c$ poprzez odpowiedni wektor
wag $\Bw=\left[{w_1,w_2,\ldots,w_c}\right]$, w którym $w_i$ jest wagą $i$-tej klasy. Wagi
dla poszczególnych klas są z reguły definiowane jako $m^{l_j}_{c_i}/m^{l_j}$,%$\fracS{m^{l_j}_{c_i}}{m^{l_j}}$,
gdzie $m^{l_j}_{c_i}$ oznacza liczbę wektorów znajdujących się w klastrze $l_j$
przypisanych do $c_i$, a $m^{l_j}$ jest całkowitą liczbą wektorów zawartych w klastrze
$l_j$. Przedstawione {\it rozmyte} rozwiązanie ma pewną istotną wadę związaną ze
złożonością procesu wnioskowania, co w znaczny sposób redukuje transparentność systemu
ograniczając użyteczność tej metody w systemach reguł prototypowych.\\
Druga metoda niezależnej klasteryzacji jest dużo bardziej praktyczna, upraszczając proces
wnioskowania, często również gwarantując większą dokładność systemu. Algorytm tej metody
przedstawia schemat \reff{fi:SepClu}

\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$, $\bf {l}$
	\STATE $\BP \leftarrow \emptyset$ 
	\FOR{i=1\ldots c}
		\STATE ${\bf Cl} \leftarrow Cluster(\BT_{C_i},l_i)$
		\STATE $\Bp \leftarrow {\rm mean}({\bf Cl}_i)$
		\STATE $C(\Bp) \leftarrow i$
		\STATE $\BP \leftarrow \BP \cup \Bp$
	\ENDFOR 
	\RETURN $\BP$
\end{algorithmic}
  \caption{Metoda niezależnego grupowania klas}
  \label{fi:SepClu}
\end{algorithm}

Wadą wykorzystania klasteryzacji do pozyskania prototypów jest, podobnie jak w przypadku
części metod stochastycznych, konieczność określenia liczby prototypów. Problem ten jest
niezmiernie istotny i w znaczący sposób wpływa na przejrzystość zbudowanego modelu. W
szczególności dotyczy przypadku niezależnego grupowania, gdyż wymaga określenia $c$
niezależnych parametrów osobno dla każdej z klas. Kwestia optymalizacji liczby prototypów
została opisana w rozdziale \ref{sec:NumOfProto}. Ogólnie jednak należy zauważyć bardzo dobre
wyniki uzyskiwane z opisanych metod, charakteryzujące się oczekiwanym balansem pomiędzy
dokładnością a liczbą prototypów. Bardzo częstym rozwiązaniem jest również stosowanie
metod klasteryzacji jako wstępnej inicjalizacji poprzedzającej nadzorowaną optymalizację
położenia prototypów. Przykładowe wyniki porównawcze można znaleźć w \cite{Blachnik-CFCM}.\\

\section{Nowa metoda poszukiwania prototypów\\ bazująca na warunkowym grupowaniu\\ danych} \label{sec:CFCM}
Wyznaczanie położenia prototypów poprzez klasyczne metody klasteryzacji pomija sporą część
informacji o wzajemnym położeniu klas, co w znacznym stopniu ogranicza możliwości
 uzyskanego klasyfikatora, zmniejszając zarówno jego zdolność uogólniania, jak i
transparentność. Analiza położenia prototypów wskazuje, iż częstym rezultatem jest
nadmiarowa liczba wektorów, które nie biorą udziału w procesie klasyfikacji. Przykładem
tego jest rys.(\ref{fi:FCM-CFCM}a), gdzie jeden z prototypów jest bezużyteczny, nie wpływając na wynik klasyfikacji. Częściowym rozwiązaniem takiego problemu mogą być metody bazujące na diagramach Voronoi (jak GE lub RNG \cite{Norb-ProtoSel1} ) usuwające zbędne prototypy. Innym
rozwiązaniem są tutaj metody semi-nadzorowanej klasteryzacji, charakteryzujące się możliwością wykorzystania informacji o względnym rozkładzie klas (rys.(\ref{fi:FCM-CFCM}b)).
 \bfig
    \subfigure[Selekcja prototypów algorytmem FCM]{\epsfig{figure=pic/fcm.eps,width=7.5cm}}
    \subfigure[Selekcja prototypów algorytmem CFCM]{\epsfig{figure=pic/cfcm.eps,width=7.5cm}}
    %
  \caption{Porównanie wyników selekcji prototypów metodami grupowania typu FCM oraz CFCM}
%
  \label{fi:FCM-CFCM}
\efig
%
Ogólna grupa metod klasteryzacji warunkowej wykorzystuje zewnętrzną zmienną zdefiniowaną
dla każdego wektora wejściowego, tworząc tak zwany kontekst grupowania opisujący siłę
oddziaływania pomiędzy wektorem wejściowym a pewnym zewnętrznym parametrem. Warunkowe
(kontekstowe) grupowanie było rozwijane przez wielu autorów w tym m.in. przez W. Pedrycza
\cite{C-Pedrycz-FuzzySets-KD,C-Pedrycz-CFCM} i J. Łęskiego
\cite{C-Leski-GWCFCM,C-Leski-OWGCPC}, a znalazło zastosowanie również w problemach
uczenia radialnych sieci neuronowych \cite{L-Pedrycz-CFCM-RBF}.\\
Rozwiązanie wykorzystujące warunkową klasteryzację do poszukiwania prototypów
dla systemów reguł prototypowych zostało zaproponowane przez autora i innych w
\cite{Blachnik-CFCM} i bazuje na algorytmie warunkowego rozmytego grupowania c-średnich
(ang. Conditional Fuzzy C-means - CFCM). Jednak, co należy podkreślić może zostać również wykorzystane do dowolnej
innej metody realizującej kontekstowe grupowanie danych.

\subsection{Algorytm warunkowego rozmytego grupowania c-średnich}
Jedną z podstawowych metod kontekstowego grupowania danych jest algorytm warunkowego
rozmytego grupowania c-średnich (ang. conditional fuzzy C-means CFCM), który bazuje na
minimalizacji funkcji kosztu zdefiniowanej jako \reff{eq:CFCM-Cost}.
%
\be \label{eq:CFCM-Cost} %
J_j ({\bf{U},{\BP}}) = \sum\limits_{i = 1}^{l_i} {\sum\limits_{k =
1}^{m_j} {\left( {u_{ik} } \right)^p \left\| {\Bx_k  - \Bp_i } \right\|_A^2 } } %
\ee
%
gdzie $l_j$ oznacza liczbę klastrów (prototypów) wyznaczonych dla danej klasy $j$, 
 $m_j$ to liczba wektorów treningowych z tej klasy ($m=\sum_j m_j$), $c$ to całkowita liczba klas, $p>1$ to parametr określający stopień rozmycia, zaś $\bf{U}=(u_{ik})$ jest macierzą o rozmiarach $c\times m_j$, której elementy
$u_{ik }\in [0,1]$ określają stopień przynależności $k$-tego wektora do $i$-tego klastra.
Aby rozwiązać tak zdefiniowaną funkcję kosztu konieczne jest by macierz $\bf{U}$
spełniała trzy kryteria:\\
1$^{o}$ każdy wektor $x_{k}$ przynależy do $i$-tego klastra w stopniu z przedziału [0,1]:

\be \mathop{\mbox{\LARGE$\forall$}}\limits_{1 \le i \le c}
\mathop{\mbox{\LARGE$\forall$}}\limits_{1 \le k \le m} u_{ik}  \in [0,1] \ee
%
2$^{o}$ suma stopni przynależności $k$-tego wektora $x_{k}$ do wszystkich klastrów równa
jest wartości kontekstu $f_{k}$

\be \mathop{\mbox{\LARGE$\forall$}}\limits_{1 \le k \le m} \sum\limits_{i = 1}^c {u_{ik}
= f_k } \ee
%
3$^{o}$ żaden klaster nie jest pusty

\be \mathop{\mbox{\LARGE$\forall$}}\limits_{1 \le i \le c} 0 < \sum\limits_{k = 1}^m
{u_{ik}  < m} \ee
%
Przedstawiona funkcja celu \reff{eq:CFCM-Cost} z uwzględnieniem opisanych warunków jest
iteracyjnie minimalizowana zgodnie z formułami \reff{eq:CFCM-P-min} \reff{eq:CFCM-U-min}:

\be \label{eq:CFCM-P-min}
\mathop{\mbox{\LARGE$\forall$}}\limits_{1 \le i \le c} \Bp_i  =
{\sum\limits_{k = 1}^m {(u_{ik} )^p \Bx_k } \left[{ \sum\limits_{k = 1}^m {(u_{ik} )^p }}\right]^{-1} }
\ee

\be \label{eq:CFCM-U-min}
\mathop{\mbox{\LARGE$\forall$}}\limits_{1 \le i \le c \atop 1 \le k \le m}
u_{ik}  = {{f_k } \left[{\sum\limits_{j = 1}^c {\left( {\frac{{\left\| {\Bx_k  - \Bp_i } \right\|}}{{\left\| {\Bx_k  - \Bp _j } \right\|}}} \right)}^{2/\left( {p - 1} \right)} }\right]^{-1}}
\ee
%
%{
%\begin{array}{*{20}c}
%\vspace*{-10mm}_{1 \le i \le c}  \\
%_{1 \le k \le m}  \\
%\end{array}}
\subsection{Kontekst grupowania} %_
W metodach prototypowych bazujących na algorytmie \kNN najlepszymi wektorami
referencyjnymi $\BP$ są wektory leżące w pobliżu granicy między klasami, dzięki czemu
możliwe jest zbudowanie optymalnej granicy decyzji z minimalną liczbą prototypów.
Założenie to prowadzi do wniosku, iż algorytm grupowania powinien być skoncentrowany na
klasteryzacji podprzestrzeni leżącej w pobliżu granicy międzyklasowej. Wymagane jest więc
stworzenie takiej wartości $f_k$, która spełni powyższe wymagania. \\
Możliwym rozwiązaniem, opisanym  przez autora w \cite{Blachnik-CFCM}
jest zależność \reff{eq:CFCM-Fk1}
%
 \be \label{eq:CFCM-Fk1}
%
w_k  = {{\sum\limits_{j,C(\Bx_j) = C(\Bx_k)}
{\left\| {\Bx_k - \Bx_j } \right\|} ^2 } \left[{\sum\limits_{l,C(\Bx_l) \ne C(\Bx_k)} {\left\| {\Bx_k  - \Bx_l } \right\|} ^2 }\right]^{-1}}
%
\ee
%
gdzie uzyskana wartość parametru $w_k$ wymaga normalizacji, aby rezultat był określony w
przedziale [0,1] \reff{eq:CFCM-norm}

\be \label{eq:CFCM-norm}
%
{{w_k  = \left( {w_k^  - \mathop {\min }\limits_k \left( {w_k^{} } \right)} \right)}
{\left( {\mathop {\max }\limits_k \left( {w_k^{} } \right) - \mathop {\min }\limits_k \left( {w_k^{} } \right)} \right)}^{-1}}
%
\ee

%Inną możliwą miarą pozwalającą wyznaczyć kontekst, a nie wymagającą normalizacji jest
%miara w której sumy z równania \reff{eq:CFCM-Fk1} zostają zastąpione średnią, innymi słowy 
%opisana jako \reff{eq:CFCM-Fk2} wywodząca się z {\it typowości}.
%
%
% \be \label{eq:CFCM-Fk2}
%
%w_k^{}  = {\mathop{\rm{mean}}\limits_{j,C(\Bx_j) = C(\Bx_k )}
% \left({{\left\| {\Bx_k - \Bx_j } \right\|} ^2 }\right) \mathord{\left/
% {\vphantom {{\mathop{mean}\limits_{j,C(\Bx_j) = C(\Bx_k )}
%  {\left\| {\Bx_k  - \Bx_j } \right\|} ^2 }
% {\mathop{mean}\limits_{l,C(\Bx_l) \ne C(\Bx_k)}
%  {\left\| {\Bx_k  - \Bx_l } \right\|} ^2 }}} \right. \kern-\nulldelimiterspace}
%  {\mathop{\rm{mean}}\limits_{l,C(\Bx_l) \ne C(\Bx_k)}
%  \left({{\left\| {\Bx_k  - \Bx_l } \right\|} ^2 }\right)}}
%
%\ee
%
Parametr $w_k$ określa zatem położenie wektora względem jego sąsiadów i po znormalizowaniu
 przyjmuje wartości bliskie 0 dla wektorów treningowych w pobliżu
dużych jednorodnych środków klas, zaś bliskie 1 dla wektorów $x_k$ leżących daleko od
przedstawicieli tej samej klasy, lecz blisko wektorów klasy przeciwnej. Innymi
słowy duże wartości $w_k$ odpowiadają położeniu w pobliżu granicy, a maksymalne występują dla wektorów odstających.\\
Tak zdefiniowany znormalizowany parametr $x_k$ wymaga filtracji określającej interesujący
nas obszar klasteryzacji, stanowiący kontekst grupowania dla algorytmu CFCM. Filtracja
jest często interpretowana również jako
 przypisywanie rozmytej wartości lingwistycznej do zmiennej $w_k$ w znaczeniu zbiorów rozmytych. W metodzie
 opisanej przez autora użyto filtra Gaussowskiego \reff{eq:CFCM-Filter}

\be \label{eq:CFCM-Filter}
%
f_k  = \exp \left( {\frac{-({w_k  - \mu })^2}{{\sigma ^2 }}} \right)
%
\ee
%
gdzie parametr $\mu $ określa położenie przestrzeni klasteryzacji, zaś $\sigma $ to
szerokość tego obszaru. \\
Przeprowadzone badania wskazały, iż najlepszymi wartościami
filtra są $\mu =0.6-0.8$ i $\sigma =0.6-0.9$, determinując poprawne działanie algorytmu
dla szerokiej skali problemów.

%----------------------------PROTOTYPE OPTIMIZATION---------------------------

\section{Optymalizacja położenia prototypów}
Nadzorowana optymalizacja położenia prototypów dla reguł prototypowych klasyfikatora \kNN jest istotnym elementem procesu uczenia. Standardowe metody selekcji, jak i optymalizacji z wykorzystaniem algorytmów grupowania nie są w stanie uzyskać tak optymalnego położenia prototypów, jakie możliwe jest do uzyskania z wykorzystaniem w pełni nadzorowanej optymalizacji gradientowej dobierającej położenie prototypów tak by zminimalizować pewną funkcję kosztu, najczęściej przedstawianą jako błąd klasyfikacji. Najpowszechniej stosowanym rozwiązaniem jest tu grupa algorytmów Learning Vector Quantization (LVQ) zaproponowanych przez Kohonena \cite{Kohonen-SOM-Book}. \\
Algorytm LVQ należy do grupy metod sieci neuronowych i ma istotną wadę (podobnie jak większość metod sieci neuronowych) - jest bardzo czuły na inicjalizację wag, w tym przypadku rozumianą jako inicjalizację położenia prototypów. Wada ta istotnie wpływa na powtarzalność uzyskiwanych rezultatów, dlatego też bardzo dobrą praktyką metod LVQ jest inicjalizacja położenia prototypów poprzez metody selekcji lub klasteryzacji danych. 
Takie rozwiązanie było analizowane m.in. przez Jankowskiego i Grochowskiego w \cite{Norb-InstanceSelLVQ}, dając bardzo dobre rezultaty. Inną istotną wadą oryginalnego algorytmu LVQ jest brak zdolności określania optymalnej liczby prototypów, co pociąga za sobą konsekwencje manualnego określania liczby neuronów (prototypów).\\
Klasyczny algorytm LVQ bazuje na zasadzie ,,zwycięzca bierze wszystko'' i wykorzystuje metodę optymalizacji zbliżoną do gradientowej, gdyż optymalizowana funkcja celu jest nieciągła. Podstawowy algorytm LVQ doczekał się wielu modyfikacji - sam Kohonen zaproponował cztery wersje algorytmu oznaczone LVQ1, LVQ2 (LVQ2.1), LVQ3 oraz OLVQ, a w literaturze spotykać można szereg innych wersji działających w trybie wsadowym (ang. batch) lub ciągłym (ang. online), uwzględniających ważenie cech oraz szereg innych właściwości \cite{Karayiannis-LVQa,Karayiannis-LVQb,Karayiannis-LVQc,Karayiannis-LVQd,Cataron-EGLVQ}.\\

\subsection{Algorytmy rodziny LVQ}
\paragraph{LVQ1} jest algorytmem bazowym dla całej grupy, który iteracyjnie optymalizuje 
położenie wektorów referencyjnych, zwanych również wektorami kodującymi (ang. codebook vectors).\\
Proces uczenia może przebiegać w dwóch trybach: wsadowym, gdy aktualizacja wektorów kodujących odbywa się po prezentacji całego zbioru uczącego oraz w trybie ciągłym, gdy po prezentacji pojedynczego wektora treningowego następuje modyfikacja położenia najbliższego prototypu zgodnie z formułą \reff{eq:lvq1}.
%
\be \label{eq:lvq1}
\begin{array}{l}
 {\bf{p}}_i\left({z + 1}\right)  = {\bf{p}}_i\left({z}\right)  - \alpha \left( z \right)\left( {{\bf{x}}_j  - {\bf{p}}_i\left({z}\right) } \right) \\
 {\bf{p}}_i\left({z + 1}\right)  = {\bf{p}}_i\left({z}\right)  + \alpha \left( z \right)\left( {{\bf{x}}_j  - {\bf{p}}_i\left({z}\right) } \right) \\
 \end{array}
\ee
%
\be \label{eq:lvq-cost}
 %i=\mathop{argmin}\limits_{a=1\ldots l}\left({\left\|{\Bx_j-\Bp_a}\right\|}\right)
i=\arg\min\limits_{a=1\ldots l}\left({\left\|{\Bx_j-\Bp_a}\right\|}\right)
\ee
%
gdzie $i$ oznacza najbliższy prototyp do $j$-tego wektora trenującego $\Bx$ według zależności \reff{eq:lvq-cost},  $\alpha \left( i \right)$ jest współczynnikiem uczenia - monotonicznie malejącą funkcją przyjmującą wartości pomiędzy $[0,1]$, a $z$ oznacza aktualną iterację.\\
Przeprowadzona w ramach prac innych badaczy analiza porównawcza oraz wyniki eksperymentów wskazują, iż uczenie w trybie ciągłym jest bardziej stabilne i mniej odporne na wektory odstające \cite{B-Ossowski-SieciNeuron}. %

\paragraph{LVQ 2 (2.1)} jest bardziej zaawansowanym algorytmem, który optymalizuje jednocześnie dwa wektory kodujące z przeciwnych klas, leżące najbliżej danego wektora treningowego. Jeżeli w bezpośrednim sąsiedztwie danego wektora treningowego obydwa najbliższe prototypy są z tej samej klasy, algorytm pozostawia je bez zmian.
Modyfikacja położenia prototypów odbywa się zgodnie z procedurą LVQ1, jednakże modyfikacja obydwu prototypów naraz prowadzi do uzyskania lokalnej optymalności w sensie Bayesowskim. \\
Algorytm LVQ2.1 posiada drobną modyfikację w stosunku do swego poprzednika, polegającą na uwzględnieniu tylko takich wektorów $\Bx$, które trafiają do okna o względnej szerokości $w$ zdefiniowanego jako \reff{eq:lvq2-window}.
\be \label{eq:lvq2-window} %
\min \left({\frac{d_1}{d_2},\frac{d_2}{d_1}}\right)>s \hbox{ ; }s=\frac{1-w}{1+w} %
\ee
%
gdzie $d_1$ i $d_2$ oznaczają odległości pomiędzy wektorem $\Bx$ a dwoma najbliższymi prototypami $\Bp$. W praktycznych zastosowaniach algorytmu LVQ2.x stosuje się przetwarzanie kaskadowe, gdzie działanie tej metody poprzedzone jest optymalizacją zrealizowaną w oparciu o LVQ1.

\paragraph{LVQ3} jest kolejnym rozszerzeniem metod rodziny LVQ, w którym analizowana jest sytuacja wystąpienia dwóch najbliższych prototypów do danego wektora treningowego, wszystkich o jednakowych etykietach. Proces adaptacji położenia prototypów odbywa się wówczas według zależności \reff{eq:lvq3}.
%
\be \label{eq:lvq3}
 {\bf{p}}_i\left({z + 1}\right)  = {\bf{p}}_i\left({z}\right)  + \varepsilon\alpha \left( z \right)\left( {{\bf{x}}_j  - {\bf{p}}_i\left({z}\right) } \right)
\ee %
gdzie $\varepsilon$ jest stałą zależną od szerokości okna $w$, która przyjmuje wartości pomiędzy 0.1 a 0.5. Rezultatem, a zarazem celem algorytmu LVQ3 jest zapewnienie nie tylko poprawnej klasyfikacji danych, ale również odtworzenie rozkładu punktów w klasach.

\paragraph{OLVQ1} jest ostatnim algorytmem z serii podstawowych metod zaproponowanych przez Kohonena. Modyfikacja zaproponowana w tej metodzie polega na uniezależnieniu współczynnika uczenia osobno dla każdego z prototypów - zależność \reff{eq:olvq1}. Według założeń, taka modyfikacja powinna prowadzić do przyspieszenia zbieżności algorytmu. 
%
\be \label{eq:olvq1}
\begin{array}{l}
 {\bf{p}}_i\left({z + 1}\right)  = {\bf{p}}_i\left({z}\right)  - \alpha_i \left( z \right)\left( {{\bf{x}}_j  - {\bf{p}}_i\left({z}\right) } \right) \\
 {\bf{p}}_i\left({z + 1}\right)  = {\bf{p}}_i\left({z}\right)  + \alpha_i \left( z \right)\left( {{\bf{x}}_j  - {\bf{p}}_i\left({z}\right) } \right) \\
 \end{array}
\ee %
Odpowiednio $\alpha_i\left({z}\right)$ oznacza współczynnik uczenia przypisany do $i$-tego wektora kodującego w iteracji $z$.

%-------------------------------------

\subsection{Modyfikacje algorytmów LVQ}
\paragraph{LVQ-TC} jest metodą zaproponowaną przez Ordorico w \cite{Odorico-LVQTC}, w której modyfikacja położenia prototypu zależy nie tylko od wzajemnej odległości pomiędzy prototypem a wektorem treningowym, ale również od historii prototypu. Według autora, historia prototypu definiowana jest jako niezależna dla każdego z wektorów referencyjnych liczba modyfikacji jego położenia, określająca osobno ilość nagród i kar. Ostateczna postać modyfikacji prototypu przybiera wówczas formę \reff{eq:lvqtc}.
%
\be \label{eq:lvqtc} %
  {\bf{p}}_i\left({z + 1}\right)  = {\bf{p}}_i\left({z}\right)  + \frac{\alpha \left( z
  \right)}{{\sum\bf{q}}_i}\left( {{\bf{x}}_j  - {\bf{p}}_i\left({z}\right) } \right)  %
\ee %
gdzie $\sum{\bf{q}}_i$ oznacza ilość modyfikacji $i$-tego prototypu (suma wszystkich modyfikacji $i$-tego wektora ; ${\bf{q}}_i=\left[{q_1,q_2,\ldots,q_c}\right]^T$ jest liczba modyfikacji zrealizowanych  poprzez wektory z k-tej klasy). Jednocześnie autor zaproponował kryterium oczyszczające - usuwające zbędne prototypy, porównując liczbę modyfikacji $q_i$ ze stałą $Q$, określającą minimalną liczbę modyfikacji. Jeżeli prototyp nie był dostatecznie często modyfikowany jest on usuwany. Kolejnym rozszerzeniem algorytmu jest powtórne etykietowanie występujące w sytuacji, gdy prototyp $i$ był w większości modyfikowany przez wektory z klasy $k$ i jeżeli $k>Q$ - wówczas prototypowi takiemu przypisywana jest etykieta z klasy $k$, a on sam umiejscawiany jest w środku wektorów z klasy $k$, które wpływały na jego przesunięcie.

\paragraph{Algorytm DSM} (ang. decision surface mapping) \cite{P-Kunch-21methods} jest prostą modyfikacją algorytmu LVQ, w której położenie prototypu jest modyfikowane jedynie poprzez nałożenie kary. Innymi słowy autorzy Geva
and Sitte sugerują, by na zmianę położenia prototypu wpływały jedynie wektory błędnie klasyfikowane. DSM często prowadzi do lepszych rezultatów klasyfikacji niż tradycyjny algorytm LVQ, jednakże metoda ta wydaje się być mniej stabilna.\\
W przedstawionych wynikach rozprawy użyto kolejnej modyfikacji, w której zostały określone dwa niezależne współczynniki uczenia osobno dla nagradzania i karania, dzięki czemu możliwe stało się uzyskanie kompromisu pomiędzy stabilnością a dokładnością klasyfikacji. Najczęściej przyjętą zależnością pomiędzy współczynnikiem kary a nagrody jest $\alpha_{kary}=2\alpha_{nagrody}$

\paragraph{Dynamic LVQ} \cite{P-LVQ_PhD_Bermejo} charakteryzuje się możliwością automatycznego doboru liczby prototypów. Algorytm realizowany jest w dwóch krokach, w pierwszym uruchamiany jest klasyczny algorytm LVQ, zaś w drugim dodawany jest nowy prototyp. Obydwa te kroki wykonywane są do momentu zatrzymania opadania funkcji kosztu (definiowanej jako liczba błędów). Każdy nowy prototyp umiejscawiany jest w obszarze Voronoi, wynikającym z obecnego rozkładu prototypów, w którym rejestrowana jest największa liczba błędów. Położenie nowego prototypu wyznaczane jest wówczas jako średnia błędnie klasyfikowanych wektorów należących do tego obszaru Voronoi pochodzących z klasy $C_i$ \reff{eq:DLVQ}.
\be \label{eq:DLVQ}%
    {\bf{p}}=\frac{1}{h_{C_i}}\sum\limits_{k=1}^{h_{C_i}} {\bf{x}}_k
\ee %
gdzie $h_{C_i}$ to liczba błędnie klasyfikowanych wektorów z klasy $C_i$.\\
 Jako ostatni krok uruchamiany jest algorytm oczyszczania usuwający te prototypy, które nie biorą udziału w klasyfikacji.
 %

%----------------------------------NUMBER OF PROTOTYPES-------------------------------

 \section{Wyznaczanie optymalnej liczby\\ prototypów} \label{sec:NumOfProto}
W systemach reguł prototypowych przejrzystość modelu jest uzyskiwana m.in. poprzez możliwie jak najmniejszą liczbę prototypów. Jednakże proces selekcji lub ekstrakcji prototypów wymaga optymalizacji wielokryterialnej, gdzie niezbędny jest kompromis pomiędzy dokładnością modelu a liczbą prototypów oraz liczbą cech. Typowy proces wyznaczania położenia prototypów dla reguł prototypowych typu \kNN jest szeregowym procesem przetwarzania o dwóch lub trzech krokach. W pierwszym etapie wyznaczane jest wstępne położenie prototypów, jako rezultat systemów selekcji lub klasteryzacji. Następnie, w kroku drugim położenie prototypów podlega  optymalizacji by zwiększyć zdolność dyskryminacji klas. Krok trzeci, nie zawsze stosowany, służy oczyszczeniu zbioru prototypów poprzez usunięcie zbędnych wektorów referencyjnych nie biorących udziału w klasyfikacji. Ostatni etap realizowany jest zwykle metodami kondensacji danych (CNN, RNN) lub metodami bazującymi na diagramach Voronoi (GE, RNG)\cite{Norb-ProtoSel1}, w taki sposób by usunąć wektory wewnętrzne-redundantne.\\ 
Część z metod redukcji zbioru wektorów referencyjnych pozwala na automatyczny dobór ich liczby. Dla szeregu jednak metod bazujących na grupowaniu, algorytmach genetycznych czy też metodach optymalizacji niezbędne jest manualne określenie liczby wektorów prototypowych. \\
Niektóre metody selekcji prototypów bazujące na algorytmach genetycznych posiadają tak skonstruowaną funkcję celu, która zawiera informację o jakości klasyfikacji w stosunku do liczby wektorów referencyjnych, pozwalając jednocześnie na ich automatyczny dobór. Podobnie często stosowaną praktyką w przypadku niezależnej klasteryzacji klas jest wykorzystanie metody optymalizacji doboru liczby klastrów, opisywane między innymi w pracy Stąpor \cite{B-Stapor-Book} oraz Bischopa \cite{B-Bishop-PatRecBook}. Jednak rezultaty uzyskiwane tą drogą są dalekie od optymalnych. Powodem tego jest brak bezpośredniej korelacji jakości grupowania oraz dokładności klasyfikacji, czego przykładem może być rys.\reff{fi:FCM-CFCM}. Dlatego też w zagadnieniu tym stosowane są algorytmy przeszukiwania. Najczęściej problem ten dotyczy metod, w których konieczna jest równoległa optymalizacja liczby prototypów dla każdej z klas z osobna. \\
 Pewną alternatywą optymalizacji liczby prototypów jest zaproponowany przez autora {\it algorytm wyścigu} (ang. racing algorithm) \cite{Blachnik-CFCM} pozwalający na wielokrotne przyspieszenie optymalizacji liczby prototypów, przy możliwym minimalnym spadku jakości klasyfikacji.\\ 
Osobnym, acz bardzo istotnym problemem jest walidacja modelu zabezpieczająca przed przeuczeniem. Częściowo realizuje się to poprzez metody statystycznej kontroli złożoności lub weryfikację w oparciu o walidację krzyżową - dokładniej temat ten będzie analizowany w rozdziale \ref{cha:FSiMS}.

%------------------------------------------------------------------

\subsection{Algorytmy przeszukiwania}
Typowe algorytmy przeszukiwania można podzielić na tzw. nienadzorowane, ślepe metody przeszukiwania (jak metody szukania wszerz lub wgłąb) oraz metody nadzorowane, heurystyczne (jak przeszukiwanie metodą wspinaczki, wiązką lub inne). Zagadnienie optymalizacji liczby prototypów jest typowym problemem optymalizacji heurystycznej, czego przykładem może być praca \cite{P-Kunch-21methods}.\\
 Najczęściej stosowanym rozwiązaniem jest algorytm wspinaczki (ang. hill-climbing), którego zastosowanie do optymalizacji liczby prototypów można przedstawić w postaci schematu \reff{fi:HillClimb}, gdzie PNN$({\bf l})$ to prototypowy algorytm \kNN o ${\bf l}$ prototypach, a $Validate(M,\BT)$ to funkcja walidująca model $M$ w oparciu o zbiór $\BT$.  
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$, $\bf {l}$
	\ENSURE ${\bf l} \leftarrow [1,1,\ldots ,1]$
	\STATE $acc \leftarrow Validate($P\kNN$({\bf l}),\BT) $
	\STATE $flaga \leftarrow \TRUE$
	\STATE ${\bf tlb} \leftarrow {\bf l}$
	\WHILE{$flaga$}
		\STATE $flaga \leftarrow \FALSE$
		\FOR{i=1\ldots c}
			\STATE $tla_i \leftarrow l_i+1$
			\STATE $tacc \leftarrow Validate($PNN$({\bf tla}),\BT) $
			\IF{tacc>acc}
				\STATE $flaga \leftarrow \TRUE$
				\STATE $acc \leftarrow tacc$
				\STATE ${\bf tlb} \leftarrow {\bf tla}$
			\ENDIF
		\ENDFOR
		\STATE ${\bf l} \leftarrow {\bf tlb}$
	\ENDWHILE
	\RETURN ${\bf l}$
\end{algorithmic}
  \caption{Optymalizacja liczby prototypów metodą wspinaczki}
  \label{fi:HillClimb}
\end{algorithm}

Metoda ta niestety nie gwarantuje znalezienia globalnego optymalnego rozwiązania, jednakże ze względu na dużą prostotę i szybkość jest powszechnie stosowana. Metoda przeszukiwania wiązką jest również często stosowana, pozwalając na pełniejsze przeszukanie, co pozwala często na uzyskiwanie lepszych rezultatów oraz uniknięcie ekstremów lokalnych. Jej wadą jest jednak dużo większy nakład obliczeniowy oraz większe zapotrzebowanie na zasoby systemowe, co dla dużych problemów badawczych stanowi poważne ograniczenie.
%------------------------------------------------------------------

\subsection{Nowy {\it algorytm wyścigu} optymalizacji liczby prototypów}
Wadą algorytmów szukania jest konieczność przechodzenia poszczególnych stanów w grafie, co znacząco wpływa i determinuje koszt nakładu obliczeniowego. Najprostszą więc metodą redukcji złożoności obliczeniowej jest takie sformułowanie problemu, które redukuje liczbę węzłów lub pozwala na przeszukanie drzewa pomijając pewną liczbę węzłów i przeszukując tylko te, które rokują najlepszą poprawę funkcji celu. {\it Algorytmu wspinaczki} w procesie optymalizacji liczby wektorów referencyjnych wymaga dla każdego ze stanów wykonania $c$ (gdzie $c$ oznacza liczbę klas) procesów uczenia algorytmu bazowego (np. CFCM+LVQ) podczas, gdy dla {\it algorytm wyścigu} wymagane jest pojedyncze wywołanie uczenia.\\
Własność tę osiągnięto bazując na obserwacji, iż w algorytmach selekcji prototypów widoczna jest tendencja, w której dokładność klasyfikacji pojedynczej klasy wpływa na całkowitą dokładność klasyfikacji. Na tej podstawie można więc wysnuć wniosek, że maksymalizacja poprawy całkowitej dokładności klasyfikacji możliwa jest do osiągnięcia poprzez poprawę dokładności najgorzej klasyfikowanej klasy. Założenia takie realizowane są przez {\it algorytm wyścigu} (ang. racing algorithm) - schemat \reff{fi:RacingProtoSel}, gdzie nowy prototyp dodawany jest do klasy o najgorszej dokładności klasyfikacji. Iteracyjne dodawanie nowego prototypu do klasy o największym błędzie ($C_i^{err}$) powoduje więc wzrost jej dokładności klasyfikacji, co z kolei podnosi całkowitą zdolność dyskryminacji systemu. Przeprowadzone badania wskazują jednak, że w pewnych wyjątkowych sytuacjach uzyskane rozwiązania mogą być nieoptymalne i dodanie nowego prototypu do danej klasy może nawet obniżyć całkowitą dokładność klasyfikacji. Zjawisko takie występuje, gdy dodawanie nowego prototypu nie powoduje wzrostu dokładności klasyfikacji danej klasy, co może występować np. w przypadku klasycznych metod grupowania danych. Jednak zastosowanie {\it algorytmu wyścigu} wraz z grupowaniem warunkowym (CFCM) prowadzi do bardzo dobrych rezultatów, co dowodzą wyniki przedstawione w rozprawie. Powodem tego jest fakt, iż każdy nowo dodany wektor referencyjny bierze istotny udział w procesie klasyfikacji, poprawiając dokładność klasyfikacji klasy, do której prototyp został dodany.\\ 
W algorytmie tym błąd klasyfikacji klasy $C_i^{err}$ jest niezależnie od funkcji optymalizowanej. Zarówno dla dokładności opisanej wyrażeniami \reff{eq:ACC}, jak i \reff{eq:BACC} wybór klasy do której prototyp należy dodać określany jest jako maksymalny błąd wyrażony $C_i^{err}=\frac{m_i^{err}}{m_i}$, gdzie $m_i$ jest liczbą wektorów w klasie $i$, a $m_i^{err}$ to liczba błędów w tej klasie. Ocena błędu klasyfikacji najczęściej dokonywana jest w procesie walidacji krzyżowej.
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$, $\bf {l}$, $maxit$
	\ENSURE ${\bf l} \leftarrow [1,1,\ldots ,1]$
	\STATE $acc \leftarrow 0$
	\STATE ${\bf tl} \leftarrow {\bf l}$
	\FOR{$i=1\ldots maxit$}
		\STATE $tacc,C^{err} \leftarrow Validate($PNN$({\bf tl}),\BT) $
		\STATE $id \leftarrow \arg\max(C^{err})$
		\STATE $tl_{id} \leftarrow tl_{id} + 1$
		\IF{$tacc>acc$}
			\STATE $acc \leftarrow tacc$
			\STATE ${\bf l} \leftarrow {\bf tl}$
		\ENDIF
	\ENDFOR
	\STATE ${\bf l} \leftarrow {\bf tlb}$
	\RETURN ${\bf l}$
\end{algorithmic}
  \caption{Optymalizacja liczby prototypów algorytmem wyścigu}
  \label{fi:RacingProtoSel}
\end{algorithm}
Kolejną korzyścią {\it algorytmu wyścigu} jest omijanie ekstremów lokalnych. Typowe, proste metody przeszukiwania jak {\it algorytm wspinaczki} kończą proces optymalizacji po osiągnięciu pierwszego ekstremum, czyli w sytuacji gdy zwiększenie liczby prototypów w dowolnej z klas nie powoduje zwiększenia dokładności klasyfikacji. {\it Algorytm wyścigu} omija to ograniczenie, gdyż każdorazowo dodaje nowy prototyp do gorzej klasyfikowanej klasy.

%------------------------------------------------------------------
\subsection{Funkcje kryterialne}
%------------------------------------------------------------------
 \subsubsection{Klasyczna funkcja kryterialna}
 Najprostszą i najczęściej stosowaną funkcją kryterialną w metodach przeszukiwania oraz wyścigu jest dokładność \reff{eq:ACC} oraz dokładność zbalansowana \reff{eq:BACC}. Niestety poważną wadą tak zdefiniowanej funkcji celu jest brak informacji o stopniu skomplikowania oraz złożoności modelu. Może to prowadzić do niepotrzebnego wzrostu liczby prototypów, co negatywnie wpływa na zdolności interpretacji uzyskanych reguł.
 %------------------------------------------------------------------
 \subsubsection{Funkcje kryterialne uwzględniające liczbę prototypów}
 Alternatywnym i bardzo prostym rozwiązaniem pozbawionym powyższej słabości, a uwzględniającym liczbę prototypów jest propozycja  Kunchevy  \cite{Kunch-NPC-ProtoSel}. Metoda ta polega na liniowej kombinacji błędu klasyfikacji oraz względnej liczby prototypów \reff{eq:SearchCost}.
    
     \be \label{eq:SearchCost}
     J({\BP})=(1-\acc) + \alpha \frac{l}{m}
     \ee
 
gdzie $\alpha$ jest współczynnikiem balansu pomiędzy liczbą prototypów a dokładnością klasyfikacji. Większa wartość $\alpha$ zwiększa koszt związany z liczbą prototypów, ograniczając tym samym wpływ dokładności klasyfikacji, zaś dla $\alpha=0$ uzyskiwana jest klasyczna postać funkcji kosztu jako jedynie dokładność klasyfikacji.\\
 Inną możliwością definicji funkcji kosztu, która w większym stopniu dąży do kompromisu pomiędzy liczbą prototypów a dokładnością klasyfikacji jest \reff{eq:SearchCost2}
  \be \label{eq:SearchCost2}
     J({\BP})=(1-\acc)^2 + \left(\alpha \frac{l}{m}\right)^2
     \ee
 Dzięki takiemu zapisowi powierzchnia rozwiązań jest wypukła, co powoduje, że skrajne przypadki w których bardzo duża liczba prototypów daje niewielki wzrost dokładności lub bardzo mała liczba prototypów dająca duży błąd są karane, a znajdywane rozwiązanie to średnia liczba prototypów przy średnio małym błędzie klasyfikacji.
 %------------------------------------------------------------------
 \subsubsection{Statystyczne metody oceny złożoności}
 Interesującą funkcję kosztu do optymalizacji dokładności i liczby prototypów zaproponował w swojej pracy
 Cameron-Jones w \cite{CamJones-ELH}. Funkcja ta bazuje na wskaźniku teorioinformacyjnym - na zasadzie minimalnej długości kodu lub bardziej precyzyjnie na heurystyce {\it encoding length}. 
 Zaproponowana funkcja przyjmuje postać \reff{eq:ELH}
     \be \label{eq:ELH}
         J(m,l,m^{err})=F(l,m) + l \log_2(c)+F(m^{err},m-l) + m^{err} \log_2(c-1)
     \ee
     gdzie $F(l,m)$ jest kosztem kodowania $l$ wektorów przez $m$ instancji.
     \be \label{eq:ELH2}
         F(l,m)=\log^{*}\left({ \sum\limits_{j=0}^l \frac{m!}{j!(m-j)!}}\right)
     \ee
     gdzie $\log^{*}$ jest sumą dodatnich czynników $\log_2$.
 	Przedstawiona funkcja celu została użyta m.in. w algorytmie RMHC (ang. random mutation hill climbing)  z bardzo dobrymi rezultatami, uzyskując bardzo dobrą dokładność przy jednoczesnej małej liczbie prototypów.\\
 Innym spotykanym rozwiązaniem jest minimalizacja ryzyka strukturalnego (ang. structural risk minimization, SRM)  \cite{Vapnik-Nautre-Learning} bazująca na wymiarze VC. Przykładowe rozwiązanie uwzględniające SRM do optymalizacji zostało opisane w \cite{Crammer-MarginLVQ}.
 
\section{Porównanie metod selekcji prototypów}
Niezmiernie istotną kwestią jest wybór spośród dużej grupy przedstawionych powyżej metod, tych które w największym stopniu spełniają kryteria stawiane systemom reguł prototypowych. Od algorytmów wymagane jest więc uzyskanie maksymalnej zdolność generalizacji przy minimalnej liczbie prototypów. W tym celu dokonano porównania metod selekcji i optymalizacji prototypów na realnych zbiorach danych, których opis można znaleźć w rozdziale \ref{chap:Dodatek}. W przeprowadzonych testach porównano powszechnie znane metody opisane w literaturze z zaproponowanym przez autora algorytmem wykorzystującym parę - warunkowe rozmyte grupowanie danych wraz z algorytmem LVQ o niesymetrycznych współczynnikach nagrody i kary (CFCM+LVQ). Dodatkowo dla algorytmu CFCM+LVQ zamieszczono wyniki dla dwóch  metody doboru liczby prototypów bazujących na {\it algorytmie przeszukiwania} (s-CFCM+LVQ) oraz opracowanym przez autora {\it algorytmem wyścigu} (r\-CFCM+LVQ). Wyniki porównania przedstawiono w tabeli \reff{tab:ProtoSel-Comp}. Do realizacji porównania wykorzystano wyniki prac Jankowskiego oraz Grochowskiego \cite{Norb-ProtoSel1,Norb-ProtoSel2} jak również obliczenia własne z wykorzystaniem pakietów GhostMiner \cite{Sft-Duch-GM3} oraz stworzonego przez autora systemu SBPS. Zamieszczone w tabeli wyniki są średnią dokładnością oraz odchyleniem standartowym jak również średnią względną liczbą prototypów uzyskanymi z dziesięciokrotnego testu krzyżowego. W tabeli \\
\begin{table}[htb]
\scriptsize
\begin{tabular}{|l|r@{ $\pm$ }l|r@{ $\pm$ }l|r@{ $\pm$ }l|r@{ $\pm$ }l|r@{ $\pm$ }l|r@{ $\pm$ }l|} \hline
Dane:&\multicolumn{4}{|c|}{Wyrostek robaczkowy}&\multicolumn{4}{|c|}{Rak piersi}&\multicolumn{4}{|c|}{Choroby wątroby}\\\hline
Metoda	& \multicolumn{2}{|c|}{$l/m$} & \multicolumn{2}{|c|}{1-NN} 	&  \multicolumn{2}{|c|}{$l/m$} 	& \multicolumn{2}{|c|}{1-NN} & \multicolumn{2}{|c|}{$l/m$} & \multicolumn{2}{|c|}{1-NN}\\\hline
$l=m$	& 	100.0	&	0.0	&	83.00	&	84.41	& 	100.0	&	0.0	&	94.86	&	4.16 & 	100.0	&	0.0	&	62.29	&	6.37	\\\hline
ENN	&	84.65	&	1.70	&	89.03	&	7.84	&	96.26	&	0.35	&	96.65	&	2.28 &	64.80	&	2.08	&	58.91	&	9.06	\\\hline
RENN	&	84.62	&	1.71	&	88.35	&	8.74	&	95.85	&	0.39	&	96.57	&	2.06 &	56.59	&	2.54	&	58.90	&	10.28	\\\hline
AllKNN	&	75.38	&	2.22	&	87.65	&	8.54	&	92.71	&	0.63	&	96.80	&	2.21 &	35.05	&	11.22	&	60.63	&	12.42	\\\hline
CNN	&	39.42	&	3.09	&	71.67	&	13.52	&	10.92	&	0.81	&	91.25	&	3.25 &	63.80	&	1.13	&	61.73	&	8.72	\\\hline
DROP1	&	5.88	&	1.83	&	78.02	&	22.16	&	1.47	&	0.57	&	87.56	&	15.27&	9.79	&	4.05	&	60.36	&	11.78	\\\hline
DROP2	&	7.24	&	1.63	&	83.70	&	12.02	&	3.34	&	0.79	&	94.61	&	2.87 &	25.60	&	1.54	&	60.31	&	5.04	\\\hline
DROP3	&	7.09	&	1.24	&	85.95	&	9.39	&	3.00	&	0.64	&	96.08	&	2.35 &	18.78	&	2.64	&	63.77	&	10.57	\\\hline
DROP4	&	7.28	&	1.37	&	86.02	&	10.26	&	3.32	&	0.70	&	95.75	&	2.69 &	25.35	&	1.82	&	60.58	&	5.56	\\\hline
DROP5	&	7.59	&	1.05	&	87.25	&	9.06	&	4.5	&	0.90	&	95.14	&	2.43 &	25.31	&	3.35	&	64.34	&	4.28	\\\hline
%ICF	&	5.471	&	1.53	&	87.89	&	8.63	&	2.78	&	1.06	&	92.03	&	3.98 &	20.0	&	0.0	&	61.53	&	0.0	\\\hline
GE	&	43.56	&	2.97	&	76.29	&	12.70	&	46.79	&	3.71	&	94.93	&	2.50 &	83.38	&	1.39	&	60.82	&	6.42	\\\hline
RNGE	&	36.95	&	3.10	&	78.12	&	11.78	&	10.79	&	0.71	&	95.42	&	2.04 &	75.17	&	1.04	&	61.45	&	4.02	\\\hline
IB3	&	4.539	&	2.46	&	79.30	&	14.11	&	4.27	&	0.67	&	96.14	&	2.52 &	11.11	&	1.66	&	58.51	&	5.79	\\\hline
ELH	&	15.33	&	4.55	&	87.58	&	11.85	&	3.19	&	0.66	&	91.66	&	4.53 &	47.34	&	4.95	&	62.65	&	8.97	\\\hline
ELGrow	&	1.42	&	0.62	&	80.67	&	8.82	&	0.32	&	0.0	&	92.16	&	4.11 &	0.32	&	0.00	&	57.98 &	0.89	\\\hline
Explore	&	1.63	&	0.58	&	81.89	&	8.35	&	0.32	&	0.0	&	95.13	&	2.56 &	0.45	&	0.17	&	57.38	&	2.27	\\\hline
%DEL	&	3.03  	&	1.52	&	80.59	&	12.65	&	0.88	&	0.18	&	95.02	&	3.17 &	17.20	&	0.0	&	61.53	&	0.0	\\\hline
LVQ	&	2.1	&	0.01	&	85.28	&	10.40	&	0.32	&	0.0	&	92.86	&	2.69 &	0.64	&	0.0	&	64.34	&	6.97	\\\hline
%MC1	&	2.1	&	0.01	&	86.54	&	8.62	&	0.32	&	0.0	&	94.98	&	2.65 &		&	0.0	&		&		\\\hline
RMHC	&	2.1	&	0.01	&	85.12	&	9.01	&	0.32	&	0.0	&	96.39	&	2.05 &	0.64	&	0.0	&	55.37	&	6.94	\\\hline
CFCM  &  2.1   &  0.00   &  81.06 &  17.54 &  0.37  &  0.08   &  97.37 &  1.78  &  0.81  &  0.35    & 57.08 & 5.74 \\\hline
r-CFCM+LVQ & 2.1 &  0.00  &  86.61 &  13.32 &  0.5  &  0.05    & 97.66  &  1.83  &  0.74    &  0.16   &  65.55 & 6.48 \\\hline  
s-CFCM+LVQ & 1.88&  0.00  & 84.70  &  16.20 &  0.366&  0.16    & 96.36  &  2.74  &  0.86    &  0.29   &  65.82  & 2.74 \\\hline
Dane:&\multicolumn{4}{|c|}{Choroby serca}&\multicolumn{4}{|c|}{Cukrzyca}&\multicolumn{4}{|c|}{Irysy}  \\\hline
Metoda	& \multicolumn{2}{|c|}{$l/m$} & \multicolumn{2}{|c|}{1-NN} 	&  \multicolumn{2}{|c|}{$l/m$} 	& \multicolumn{2}{|c|}{1-NN} & \multicolumn{2}{|c|}{$l/m$} & \multicolumn{2}{|c|}{1-NN}\\\hline
$l=m$	& 	100.0	&	0.0	&	74.39	&	7.55	& 	100.00  &	0.0	&	69.95	&	4.54  &	 100.00 &	0.00	&	96.28	&	4.62\\\hline
ENN 	&	80.31	&	1.24	&	79.61	&	7.59	&	73.15	&	0.99	&	74.88	&	4.24  &	95.51	&	0.87	&	94.88	&	4.80\\\hline
RENN	&	76.94	&	1.42	&	79.27	&	6.85	&	69.18	&	1.14	&	74.50	&	3.94  &	95.10	&	0.81	&	95.16	&	4.59\\\hline
AllKNN	&	62.72	&	1.86	&	78.48	&	7.25	&	54.28	&	1.16	&	74.41	&	4.60  &	92.31	&	1.11	&	94.94	&	5.12\\\hline
CNN	&	42.73	&	2.07	&	70.9	&	7.11	&	50.53	&	1.32	&	64.24	&	5.75  &	16.50	&	2.28	&	90.93	&	6.78\\\hline
DROP1	&	4.95	&	2.21	&	67.45	&	10.93	&	6.76	&	1.53	&	64.27	&	6.62  &	5.49	&	0.83	&	90.29	&	7.26\\\hline
DROP2	&	15.91	&	2.76	&	76.95	&	7.93	&	17.84	&	1.69	&	69.75	&	5.18  &	11.94	&	1.62	&	93.53	&	5.41\\\hline
DROP3	&	12.46	&	2.31	&	77.76	&	7.51	&	12.99	&	1.38	&	72.58	&	4.68  &	11.96	&	1.53	&	93.79	&	5.76\\\hline
DROP4	&	15.43	&	2.47	&	77.87	&	7.00	&	17.77	&	1.92	&	72.30	&	4.94  &	12.19	&	1.47	&	93.32	&	5.45\\\hline
DROP5	&	16.52	&	2.49	&	77.31	&	6.97	&	18.99	&	1.80	&	70.52	&	4.61  &	9.99	&	2.12	&	93.96	&	5.56\\\hline
%ICF	&	11.80	&	1.47	&	75.84	&	7.83	&	9.57	&	0.74	&	71.16	&	4.65  &	8.55	&	1.59	&	90.72	&	6.76\\\hline
GE	&	99.07	&	0.58	&	76.33	&	7.45	&	67.85	&	1.27	&	64.17	&	5.03  &	66.60	&	2.00	&	94.69	&	5.25\\\hline
RNGE	&	55.17	&	1.73	&	74.08	&	8.6	&	59.50	&	1.05	&	67.23	&	4.99  &	23.29	&	1.39	&	92.90	&	5.59\\\hline
IB3	&	11.16	&	1.90	&	76.86	&	7.15	&	7.82	&	0.97	&	69.12	&	4.99  &	18.07	&	5.45	&	94.04	&	6.35\\\hline
ELH	&	17.02	&	2.72	&	72.31	&	8.08	&	22.21	&	2.05	&	67.33	&	4.75  &	9.64	&	1.95	&	92.24	&	5.68\\\hline
ELGrow	&	0.73	&	0.09	&	73.1	&	8.31	&	0.32	&	0.15	&	69.26	&	6.22  &	2.05	&	0.41	&	88.92	&	7.31\\\hline
Explore	&	0.73	&	0.00	&	80.08	&	7.2	&	0.32	&	0.10	&	72.45	&	5.62  &	1.95	&	0.39	&	95.38	&	4.41\\\hline
%DEL	&	1.51	&	0.14	&	76.67	&	6.91	&	1.13	&	0.48	&	70.02	&	5.96  &	4.90	&	0.77	&	90.27	&	7.09\\\hline
LVQ	&	0.73	&	0.0	&	80.86	&	7.02	&	0.29	&	0.0	&	72.52	&	4.40  &	1.87	&	0.0	&	90.56	&	7.11\\\hline
MC1	&	0.73	&	0.0	&	79.0	&	8.03	&	0.29	&	0.0	&	69.78	&	4.98  &	1.87	&	0.0	&	89.63	&	7.95\\\hline
RMHC	&	0.73	&	0.0	&	79.03	&	6.29	&	0.29	&	0.0	&	70.09	&	5.70  &	1.87	&	0.0	&	89.53	&	7.70\\\hline
CFCM  &  0.9   &  0.19  &  83.47 &  6.74  &  0.29  &  0.0   &   73.32 & 6.14   &  4.37 & 1.02   &  95.33  & 6.36\\\hline
r-CFCM+LVQ &  0.97 &  0.4 &  83.12 &  5.85  &  0.51  &  0.23   & 75.52  &  3.53  &  4.13 &  0.69  &  96.00  & 5.62 \\\hline 
s-CFCM+LVQ &  0.84 &  0.29&  73.05 &   8.67 &  0.32  &  0.09   &  7683  &  4.90  &  2.60  &  0.37 &  92.67  & 5.84 \\\hline
\end{tabular}
\caption{Wyniki porównawcze różnych metod selekcji prototypów}\label{tab:ProtoSel-Comp}
\end{table}
\section{Podsumowanie wyników}
Uzyskane wyniki porównawcze wskazują na dużą skuteczność grupy algorytmów bazujących na metodzie długości kodowania (ang. encoding length), do której należą ELGrow oraz Explore - tym samym uwydatnia się ich przydatność do realizacji systemów reguł prototypowych typu \kNN. Szczególnie dobre rezultaty uzyskano algorytmem Explore, który obok małej liczby prototypów charakteryzował się dużą dokładnością. Natomiast metody ENN, RENN, AllKNN oraz CNN cechowały się bardzo dużą liczbą wyznaczonych wektorów referencyjnych, co negatywnie wpływa na zdolność interpretacji uzyskanych rezultatów. Podobne wnioski dotyczą metod GE oraz RNGE, które w porównaniu z metodami ELGrow i Explore nadal osiągają niezadawalającą liczbę wyznaczonych prototypów. W porównaniu do innych metod stosunkowo dobre rezultaty uzyskano dla metod z rodziny DROP1-5 oraz algorytmu IB3. Dodatkowym atutem tych metod jak i wspomnianych wyżej jest wybór wektorów będących realnymi przypadkami zbioru treningowego.\\
Część algorytmów z uwagi na brak wbudowanych metod optymalizacji liczby prototypów (LVQ, RMHC, MC1) posiadała na stałe zdefiniowaną liczbę prototypów równą 1 na klasę. W przypadku tych metod najlepsze rezultaty osiągnął algorytm LVQ, do wad którego należy fakt, iż znalezione prototypy nie są wektorami zbioru treningowego. Podobny problemy dotyczą również zaproponowanych w pracy algorytmów CFCM oraz CFCM+LVQ. Należy jednak podkreślić ich dużą skuteczność. Zarówno sam algorytm wykorzystujący grupowanie danych CFCM, jak i jego modyfikacja  łącząca warunkowe grupowanie danych z algorytmem LVQ (CFCM+LVQ) wykazały bardzo dużą skuteczność, co więcej dla większości zbiorów uzyskały najlepsze rezultaty. W przypadku obydwu algorytmów liczba prototypów wyznaczana była dwoma różnymi metodami (wspinaczki i wyścigu) celem ich wzajemnego porównania. Uzyskane rezultaty są podobne, jednak widoczna jest niewielka przewagą średniej dokładności klasyfikacji algorytmu wyścigu (r\_CFCM+LVQ). Zostało to jednak okupione średnio większą liczbą prototypów oraz większym rozrzutem ich liczby w poszczególnych walidacjach.
%  \begin{center}  % put inside center environment
%  \begin{tabular*}{1\textwidth}%
%     {@{\extracolsep{\fill}}cccr}
%  label hgfjh hjg  1 & label 2 & label 3 & label 4 \\
%  \hline  % put a line under headers
%  item 1  & item 2  & item 3  & item 4  \\
%  ...
%  \end{tabular*}
%  \end{center}























