\chapter{Selekcja prototypów dla reguł prototypowych progowych} \label{chap:ProtoPTR}
\section{Wstęp}
Reguły prototypowe progowe (PTR), w odróżnieniu od reguł najbliższego sąsiada \kNN pokrywają przestrzeń danych wejściowych zbiorem wypukłych ograniczonych funkcji, bazujących na podobieństwie w oparciu o zależność $D(\Bx,\Bp)<\Theta$, gdzie $\Theta$ to wartość progu, a $\Bp$ to położenie prototypu. Taki zapis funkcji decyzyjnej pozwala na dużą łatwość interpretacji rezultatów klasyfikacji, definiując w przestrzeni wejściowej  podprzestrzenie o określonej etykiecie klasy wyjściowej, podobnie do systemów klasycznych reguł ostrych. PTR,  w zależności od doboru funkcji odległości, pozwalają na większą elastyczność w dopasowywaniu reguł do danych - możliwe nawet jest uzyskanie granicy decyzyjnej podobnej do wyników reguł \kNN czy też granicy liniowej, jeżeli wektor prototypowy $\Bp$ odsunięty jest daleko w przestrzeni wejściowej - można to zapisać jako $p_i \rightarrow \inf$ - wówczas granicę taką można traktować jako odcinkowo liniową lub jeżeli macierz wag $\BW$ ważonej funkcji odległości $D(\Bp,\Bx;\BW)$ przyjmują proporcjonalnie duże wartości dla odpowiednich składowych.\\
Z uwagi na łatwość interpretacji pożądane jest, aby wartość wyjściowa pojedynczej reguły decydowała o wyjściu całości systemu regułowego. Dlatego też do realizacji PTR stosowane są trzy różne algorytmy:
\begin{itemize}
    \item Ograniczonej energii Kulomba (ang. restricted coulomb energy, RCE)
    \item Heterogeniczne drzewa decyzji (ang. heterogeneous decision trees, HDT)
    \item Uporządkowana lista reguł prototypowych progowych (ang. ordered prototype threshold decision list, OPTDL)
\end{itemize}

\section{Algorytm RCE}
Najprostszym algorytmem, którego można użyć jako narzędzia do uzyskiwania reguł prototypowych progowych, jest algorytm RCE \cite{B-Duda-Hart} zaproponowany przez Reilly'ea, Coopera oraz Erlbauma. RCE w odróżnieniu od \kNN zamiast doboru wartości $k$ określa promień lub próg $r$ używany do predykcji. 
Sam algorytm jest bardzo prosty i można go przedstawić w postaci schematów \reff {fi:RCE1} oraz \reff{fi:RCE2} .
%
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$, $\lambda$, $\epsilon$
	\STATE $m \leftarrow {\rm sizeof}(\BT)$
	\FOR{$i=1\ldots m$}
		\STATE $th_i \leftarrow \min\limits_{C(\Bx') \neq C(\Bp_i)}\left({D(\Bp_i,\Bx')}\right)$ \COMMENT{znajdź najbliższego wroga do $\Bp_i$}
		\STATE  $th_i \leftarrow \min(th_i-\epsilon,\lambda)$ 
	\ENDFOR
	\STATE $\BP \leftarrow [\BT,th]$
	\RETURN $\BP$
\end{algorithmic}
  \caption{Algorytm RCE, funkcja ucząca } 
  \label{fi:RCE1}
\end{algorithm}
%
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\Bx$, $\BP$
	\STATE $m \leftarrow {\rm sizeof}(\BP)$
	\FOR{$i=1\ldots m$}
		\STATE ${\BP'}={\rm find}\left({D(\Bx,\Bp_i)<th_i}\right)$ \COMMENT{Znajdź wszystkie prototypy zawierające $\Bx$}
		\STATE $C(\Bx)=\max{\rm hist}(\BP')$ \COMMENT{Głosuj pośród $\BP'$ na etykietę klasy dla wektora $\Bx$}
	\ENDFOR
	\STATE 
	\RETURN $C(\Bx)$
\end{algorithmic}
 \caption{Algorytm RCE, funkcja testująca }
 \label{fi:RCE2}
\end{algorithm}

W przedstawionym algorytmie każdy prototyp ma wyznaczoną wartość progu według zależności: {\it Jeżeli
$r'<D(\Bp,\Bx_e)$ to $r=r'$ w przeciwnym razie $r=D(\Bp,\Bx_e)$} gdzie $r'$ jest stałą określającą maksymalną wartość progu określaną przez użytkownika, a $D(\Bp,\Bx_e)$ jest odległością pomiędzy wektorem prototypowym $\Bp$, a jego najbliższym wrogiem $\Bx_e$ (wektorem z przeciwnej klasy). Proces klasyfikacji polega zaś na głosowaniu wszystkich prototypów, które aktywowane są przez wektor testowy $C(\Bx)=\max \mathop{hist}\limits_i (\sum(D(\Bp,\Bx)<r \& C(\Bp)=C_i))$. W praktyce jednak powyższy algorytm jest rzadko stosowany do ekstrakcji reguł ze względu na dużą liczbę
prototypów $\BP=\BT$ co zmniejsza przejrzystość systemu. Jednak algorytm ten podobnie jak \kNN stanowi punkt wyjścia dla dużej grupy innych metod.%

%-----------------------------------------------------Hetero trees


\section{Heterogeniczne drzewa decyzji}
Standardowe drzewa decyzji, jak C4.5 \cite{B-Quinlan-C45}, CART \cite{B-Breiman-DT}
lub drzewo SSV \cite{R-Grabcz-SSV} używają jedynie pojedynczego typu testu w celu podziału danych o postaci: $T(x_i < \Theta) $, który dzieli przestrzeń wejściową w zależności od wartości cechy $x_i$ na dwie lub więcej gałęzi, pozwalając na uzyskanie zestawu reguł ostrych. Heterogeniczne drzewa decyzji przedstawione i opisane w \cite{R-Grabcz-HeteroDT}, używają co najmniej dwóch jakościowo różnych typów testów. Dodanie nowego typu testu $T(D(\Bx,\Bp_k) < \Theta_k)$ bazującego na podobieństwie do prototypów powoduje utworzenie zestawu reguł prototypowych progowych, czyli lokalnych podziałów - podprzestrzeni (dla odległości Euklidesa przyjmujących kształt hipersfer).
% W wyniku działania drzewa na danych przetransformowanych uzyskiwane są reguły prototypowe progowe. 
Proces tworzenia takiego drzewa w najprostszym przypadku zakłada, że wszystkie wektory treningowe są traktowane jako prototypy, czego wynikiem jest kwadratowa macierz odległości $D(\Bp_i,\Bp_j)$ o wymiarze $m \times m$, gdzie $m$ jest liczbą wektorów zbioru treningowego. W kolejnych etapach tworzenia drzewa następuje wybieranie tylko tych prototypów jako węzłów, które maksymalizują daną funkcję kryterialną, aż do uzyskania maksymalnej dokładności klasyfikacji. Miarą odległości mogą być tutaj dowolne funkcje mierzące odległość lub podobieństwo jak np. Gaussowskie funkcje jądrowe. Istotną cechą drzew heterogenicznych jest kombinacja tradycyjnych podziałów hiperpłaszczyznami prostopadłymi do wybranych atrybutów przestrzeni wejściowej (reguły ostre) oraz sferycznych, lokalnych podziałów wynikających z kształtu funkcji odległości (reguły prototypowe). Takie rozwiązania będące kombinacją reguł klasycznych - ostrych oraz prototypowych prowadzą do bardzo interesujących rezultatów. Choć proces poszukiwania odpowiednich prototypów staje się tutaj bardzo kosztowny, o złożoności $O(m^2)$ to korzyści są imponujące - pozwalając przykładowo na uzyskanie na zbiorze Wisconsin Breast Cancer dokładności rzędu $97.3\%$ przy najprostszym możliwym opisie danych w postaci pojedynczej regule progowej  \cite{R-Grabcz-HeteroDT}. 

%-----------------------------------------------------OPTDL
  
\section{Uporządkowana lista reguł\\ prototypowych progowych}
Rezultatem działania heterogenicznych drzew decyzji jest hierarchiczna struktura drzewiasta uzyskanych reguł. Alternatywą pozwalającą na łatwiejszą interpretację wyników jest płaska lista reguł pokrywających dane. Taka lista uzyskiwana jest poprzez zaproponowany przez autora w pracach \cite{Blachnik-PTDL2,Blachnik-PTDL1} algorytm OPTDL. W odróżnieniu od algorytmu HDT, OPTDL tworzy jedynie reguły prototypowe progowe. Dlatego też rezultatem działania tego algorytmu jest zbiór reguł prototypowych progowych w postaci zbioru prototypów, odpowiedniej metryki odległości oraz przypisanej każdemu prototypowi wartości progu ${\bf \Theta }$. Ze względu na maksymalizację zdolności generalizacji, algorytm dopuszcza możliwość wzajemnego nakrywania się reguł, dlatego też tworzona lista reguł jest uporządkowana. Do tworzenia reguł w algorytmie zastosowano kryteria stosowane w drzewach decyzji typu indeks Gini, zysk informacyjny (ang. information gain), względny zysk informacyjny (ang. information gain ratio) czy też kryterium SSV. Metoda OPTDL jest zbliżona do metod sekwencyjnego pokrywania, stopniowo pokrywając przestrzeń danych regułami prototyp-próg, zaczynając od najbardziej ogólnej reguły pokrywającej największą ilość przypadków, a kończąc na regułach szczegółowych - specjalizowanych dla małego zbioru wektorów. Ze względu na łatwość interpretacji, decyzję o etykiecie klasy wyjściowej podejmuje pojedyncza reguła. Dzięki takiemu procesowi ekstrakcji wiedzy możliwe jest pokrycie przestrzeni danych minimalną liczbą reguł oraz ułatwiony jest proces klasyfikacji poprzez testowanie reguł w odwróconej kolejności od najbardziej szczegółowej do najbardziej ogólnej (testowanie reguły następuje tylko wówczas, gdy reguła ją poprzedzająca nie jest spełniona). W algorytmie za najbardziej ogólną regułę klasyfikującą, równoważną nie spełnieniu żadnej z reguł ({\it else}) uznaje się większościowe głosowanie etykiety wektorów nie pokrytych żadną z listy reguł.  \\
 Algorytm OPTDL działa na zasadzie przeszukiwania metodą ,,pierwszy najlepszy'' (ang. best first search), gdzie przestrzeń przeszukiwań stanowi zbiór potencjalnych prototypów, czyli pełny zbiór wektorów treningowych oraz odpowiednich wartości odległości do pozostałych wektorów w zbiorze $\BT $. Dodatkowo dla ułatwienia procesu interpretacji w metodzie OPTDL dla problemów wieloklasowych stosuje się określenie kierunku reguły odpowiednio $D(\Bx,\Bp_k)<\Theta_k$ oraz $D(\Bx,\Bp_k)>\Theta_k$ określające czy reguła stanowi obszar wewnętrzny podprzestrzeni, czy też zewnętrzny (dla problemów dwuklasowych obydwa typy reguł są równoważne). \\ 
Schemat \reff{fi:TRDL-Prog} przedstawia przykładowy mikrokod funkcji realizującej proces uczenia listy reguł, gdzie dla uproszczenia założono problem dwuklasowy. Lista reguł tworzona jest dopóki nie zostanie osiągnięta maksymalna liczba reguł ($maxrul$) lub do momentu, gdy wszystkie wektory zostaną poprawnie sklasyfikowane. Następnie każdy z wektorów treningowych rozważany jest jako prototyp tworzący regułę. W tym celu wyznaczany jest wektor odległości $d$ pomiędzy rozważanym wektorem $x_i$ i pozostałymi wektorami zbioru treningowego $\BT$, a uzyskane wartości odległości są sortowane narastająco. W celu minimalizacji złożoności obliczeniowej kryterium utworzenia progu (funkcja ${\rm CalcCrit}(\cdot)$) obliczane jest jedynie dla przypadków, gdy sąsiednie w znaczeniu odległości wektory mają różne etykiety klas. Do oceny progu reguły wykorzystywane są również informacje o dotychczasowej jakości klasyfikacji wektorów $\BT$, informacje te zapisywane są w binarnym wektorze $icor\_lab$ o rozmiarze $m$, który przyjmuje wartości 1 dla wektorów błędnie sklasyfikowanych. Spośród wszystkich analizowanych wektorów $x_i$ zapamiętywany wraz z odpowiednim progiem jest ten przypadek, który maksymalizuje wartość funkcji kryterium ${\rm CalcCrit}(\cdot)$.
\begin{algorithm}
\begin{algorithmic}
	\REQUIRE $\BT$, $maxrul$
	\WHILE{$rul\_n<maxrul$ or $sum(icor\_lab)==0$}
		\FOR{$i=1\ldots m$}
			\STATE $d \leftarrow Dist(\Bx_i,\BT)$
			\STATE $d \leftarrow Sort(d)$
			\FOR{$j=1\ldots m-1$}
				\IF{$C(d_j) \ne C(d_{j+1})$}
					\STATE $t\_cri \leftarrow {\rm CalcCrit}(d_{\le j},d_{>j},icor\_lab)$
					\IF{$t\_cri>cri$}
						\STATE $th \leftarrow (d_j+d_{j+1})/2$
						\STATE $proto \leftarrow i$
						\STATE $cri \leftarrow t\_cri$
					\ENDIF
				\ENDIF
			\ENDFOR
		\ENDFOR
		\STATE $\BP \leftarrow \BP \cup [proto,th] $
		\STATE $icor\_lab \leftarrow {\rm ApplyRules}(\BP,\BT)$
		\STATE $rul\_n \leftarrow rul\_n+1$
	\ENDWHILE
	\RETURN ${\BP}$
\end{algorithmic}
  \caption{Mikrokod algorytmu OPTDL}
  \label{fi:TRDL-Prog}
\end{algorithm}
Założenie określające maksymalną liczbę reguł, niestety pozbawione jest możliwości kontroli zdolności generalizacji algorytmu, dlatego też w algorytmie OPTDL zastosowano wewnętrzną k-krotną walidację krzyżową, służącą ocenie zdolności uogólniania (podobnie jak w drzewie decyzji SSV \cite{R-Grabcz-SSV,R-Grabcz-HeteroDT}). Podczas realizacji walidacji, dla każdego jej kroku, tworzona jest nowa lista reguł, przy czym pożądane optymalizowane kryterium jest sprawdzane dla każdej nowo dodanej reguły. W ostatecznym kroku tworzenia listy, jej rozmiar jest dobierany jako średnia dokładność wyników uzyskanych kolejno dla każdego poziomu listy, pomniejszona o jej odchylenie standardowe (rozdział \ref{sec:MetaLearning}). Ostatecznie więc na całym zbiorze treningowym tworzona jest lista $Z$ reguł, (gdzie $Z$ to liczba reguł wynikająca z wewnętrznej walidacji), które zapewniają maksymalną dokładność przy minimalnej wariancji wyników.

\section{Poprawa kryterium podziału dla \\ algorytmów drzew decyzji oraz OPTDL} 
Zarówno systemy drzew decyzji, jak również drzew heterogenicznych czy też algorytm OPTDL używają kryteriów statystycznych (jak np. indeksy Gini, SSV). Wszystkie one bazują na analizie liczebności przypadków, oceniając w ten sposób jakość  podziałów dla tworzonej struktury wiedzy. Z uwagi na dyskretny charakter wartości liczebności wektorów dla poszczególnych podziałów możliwe jest występowanie impasów, objawiających się równością wartości funkcji kryterium statystycznego dla kilku podziałów. Typowe algorytmy drzew decyzji podejmują wówczas decyzję w sposób losowy, jednak przeprowadzona przez autora rozprawy analiza wskazuje, iż dla atrybutów ciągłych możliwe jest ominięcie problemu powstawania impasów. Jest to realizowane dla dowolnego indeksu statystycznego (${\rm In}(f,x_{if},x_{jf})$) poprzez uwzględnienie marginesu separowalności $\mu$ co można wyrazić jako \reff{eq:ext-separ}
\be
\begin{array}{c}
	\mu(x_{if},x_{jf})=\frac{\left|{x_{if}-x_{jf}}\right|}{\max(f)-\min(f)}\\
	{\rm In}'(f,x_{if},x_{jf})=2\cdot {\rm In}(f,x_{if},x_{jf})+\mu(x_{if},x_{jf})
\end{array}
\label{eq:ext-separ}
\ee
Wówczas w kryterium ${\rm In(\cdot)}$ uwzględnia się znormalizowaną odległość (do przedziału [0,1]) pomiędzy parą wektorów $x_{if}$,$x_{jf}$, która wyznacza miejsce podział danego atrybutu lub reguły $f$. 
%
%Zarówno drzewa decyzji jak i algorytm OPTDL używają identycznych funkcji wyznaczających punkt podziału w węźle lub wartość progu reguły prototypowej, które ze względu na skończoną liczebność zbioru treningowego przyjmują wartości dyskretne. W obydwu przypadkach najlepsza wartość wyznaczana jest jako jedna ze wszystkich możliwych podziałów par wektorów z przeciwnych klas, powoduje to częste występowanie impasów, występujących gdy więcej niż jeden podział posiada identyczną wartość funkcji kryterialnej.
%Najczęściej spotykanym rozwiązaniem takiej sytuacji jest losowy wybór progu, jednakże możliwy jest świadomy wybór optymalnej wartości progu poprzez uwzględnienie maksymalnego marginesu pomiędzy wektorami wyznaczającymi próg. Jeżeli wystąpi sytuacja identyczności wartości kryterium (Gini, SSV, itp) rozważa się wówczas odległość pomiędzy wektorami wyznaczającymi próg, za najlepszą wartość progu uważa się taką, która zapewnia maksymalne rozseparowanie sąsiednich wektorów. Procedura ta zmniejsza wariancję wyników, zapewniając jednocześnie najlepszą ich jakość.  

\section{Porównanie metod reguł prototypowych progowych}
Weryfikacji dokładności zaproponowanego w pracy algorytmu OPDL dokonano porównując wyniki klasyfikacji z wynikami uzyskanymi dla metod drzew heterogenicznych. Podczas realizacji testów porównawczych algorytm HDT był testowany w dwóch trybach - z pojedynczym kryterium (oznaczenie HDT), gdzie do budowy drzewa wykorzystano jedynie atrybuty wynikające z odległości, tym samym uzyskanym wynikiem była drzewiasta struktura reguł prototypowych progowych oraz w trybie drugim (HDT$^{mix}$), trybie heterogenicznym, gdzie zbiór atrybutów stanowił połączenie normalnego zbioru treningowego z atrybutami wynikającymi z wzajemnych odległości wektorów. Do realizacji algorytmu drzew heterogenicznych wykorzystano algorytm drzew decyzji bazujący na indeksie Gini. Procedura testowa obejmowała test dziesięciokrotnej walidacji krzyżowej algorytmów realizowany na zbiorach danych opisanych w rozdziale \reff{chap:Dodatek}. Uzyskane wyniki średniej dokładności oraz odchylenie standardowe wraz z liczbą wyznaczonych reguł przedstawia tabela \reff{tab:OPDLcomp}.
\begin{table}[htb]
%\scriptsize
\footnotesize
\begin{center}
	\begin{tabular}{|l|r@{ $\pm$ }l|c|r@{ $\pm$ }l|c|r@{ $\pm$ }l|c|r@{ $\pm$ }l|c|}
\hline
&\multicolumn{3}{c|}{HDT}&\multicolumn{3}{c|}{HDT$^{mix}$}&\multicolumn{3}{c|}{OPDL}\\ \hline
Zbiór danych&\multicolumn{2}{c|}{Dokładność}&l&\multicolumn{2}{c|}{Dokładność}&l&\multicolumn{2}{c|}{Dokładność}&l\\
\hline
Cukrzyca 				&71.76&5.10 &2 &74.87&5.52	&2 &72.14&5.36 &1\\
Choroby serca 			&81.75&6.83 &1 &81.75&6.83	&1 &81.45&6.66 &1\\
Jonosfera 				&91.60& 8.76&3 &90.09&6.41 &3 &91.79&6.23 &7\\
Rak piersi 				&97.23& 2.10&1 &97.23&2.10	&1 &97.38&2.14 &1\\
Wyrostek robaczkowy  &85.62&11.60&1 &83.80&10.47&1 &86.70&14.92&4\\
Sonar 					&59.17&14.53&4 &61.12&10.16&5 &64.60&11.71&5\\
Choroby wątroby 		&58.55&7.53 &2 &57.68&5.17 &2 &59.36&9.40 &5\\
Lancet 					&93.91&2.56 &6 &93.48&2.21	&1 &93.20&3.28 &5\\ 
%\hline
%Średnia dokładność   &\multicolumn{2}{c|}{78.86}&5.625&\multicolumn{2}{c|}{}&&\multicolumn{2}{c|}{79.54}&5.25&\\
\hline
\end{tabular}
\caption{Porównanie wyników dla systemów reguł prototypowych progowych (HDT,OPTDL) oraz systemu heterogenicznego HDT$^{mix}$. }
\end{center}
\label{tab:OPDLcomp}
\end{table}

\section{Podsumowanie wyników}
Analiza uzyskanych rezultatów wskazuje, iż nie można jednoznacznie wskazać algorytmu dominującego. Każda z metod dla różnych zbiorów danych uzyskiwała najlepsze rezultaty. Nawet w przypadku dwóch wersji algorytmu HDT istniały czasami istotne różnice w dokładności. Należy tutaj zwrócić uwagę, iż dla zbiorów {\it jonosfera}, {\it wyrostek robaczkowy} oraz {\it choroby wątroby} lepsze rezultaty uzyskano stosując jedynie reguły prototypowe progowe, nie zaś ich kombinację z regułami klasycznymi (HDT$^{mix}$). Chociaż często wzrost wartości średniej dokładności powodował też zwiększenie wartości odchylenia standardowego wyników.  Różnice w przypadku algorytmów HDT mogą też być spowodowane problemem realizacji przeszukiwania, gdyż algorytm drzewa decyzji stosował metodę przeszukiwania typu {\it najpierw najlepszy}. Jej zastąpienie metodą {\it przeszukiwania wiązką} powinno ustabilizować wyniki, i podnieść średnią dokładność algorytmu HDT$^{mix}$, gdyż ze względu na dużą liczbę atrybutów rośnie tutaj znacznie problem przeszukiwania.\\
Wyniki uzyskane algorytmem OPDL są nieznacznie gorsze w stosunku do wyników algorytmów HDT, jednak zaletą algorytmu OPDL jest płaska struktura uzyskanych reguł, co w niektórych przypadkach może znacznie ułatwić proces interpretacji uzyskanych reguł. Uzyskane wyniki wskazują również, na nieznaczny wzrost liczby uzyskanych reguł, jednak dla niektórych zbiorów, jak {\it jonosfera} czy też {\it cukrzyca} algorytm OPDL pozwolił na uzyskanie najlepszych wyników dokładności w porównaniu z algorytmem HDT tworzącym jedynie reguły prototypowe progowe.
