\chapter{Metody reguł prototypowych} \label{chap:p-rules}

\section{Wstęp}\label{sec:PRules-Intro}
Bardzo interesującym narzędziem analizy danych są metody bazujące na podobieństwie (ang. similarity based methods, SBM) \cite{Duch-SBM,Duch-NSBM}. Ich głównym atutem, jak zostało to wspomniane w rozdziale \ref{sec:Intro}, jest możliwość integracji wielu różnych typów systemów analizy danych, jak bazujące na prawdopodobieństwie, sieci neuronowe czy metody zbiorów rozmytych. Z tej grupy metod wywodzą się również systemy reguł prototypowych jako narzędzie pozwalające na reprezentację wiedzy w postaci pewnego zbioru reguł  zrozumiałych dla człowieka.\\
Wszystkie metody wywodzące się z SBM reprezentują wiedzę w postaci zbioru prototypów (wektorów referencyjnych) oraz odpowiednich miar odległości wraz z modułem integrującym informację pochodzącą z poszczególnych wzorców. Systemy reguł prototypowych mają identyczną konstrukcję, jednakże nacisk położony jest w nich na możliwie najprostszą reprezentację wiedzy. Cel ten osiągany jest poprzez redukcję liczby wektorów referencyjnych (selekcję prototypów) oraz minimalizację liczby cech użytych do konstruowania modelu. Dzięki takiemu podejściu możliwa staje się reprezentacja wiedzy pochodzącej z dużych zbiorów danych w postaci zaledwie kilku prototypów.
W wielu dziedzinach życia taki sposób jest niezmiernie przydatny i stanowi alternatywę w stosunku do innych form zapisu wiedzy jak systemy klasycznych reguł lub też reguł rozmytych. Przykładem zastosowań systemów reguł-P są problemy medyczne gdzie znalezienie w zbiorze danych kilku przypadków pozwalających na dyskryminację z dużą dokładnością  może przynieść wiele korzyści. Dzięki temu możliwe staje się znalezienie charakterystycznych dla danych schorzeń symptomów wraz z ich odpowiednimi wartościami. \\ 
Cechą charakterystyczną reguł prototypowych jest ich uniwersalność. Pozwalają one na integrację różnych form wyrażenia reguł. Między innymi za ich pomocą możliwe jest zapisanie zarówno reguł klasycznych poprzez wykorzystanie odległości Czebyszewa, jak i reguł rozmytych - w postaci reguł prototypowych typu \kNN z separowalnymi funkcjami odległości oraz reguł typu M-z-N w postaci np. reguł progowych. \\
Reguły prototypowe charakteryzują się również bardzo dobrymi wynikami w realnych zastosowaniach. Przykładem tego mogą być wyniki uzyskane dla danych reprezentujących choroby raka piersi (zbiór Wisconsin Breast Cancer), gdzie zaledwie pojedyncza reguła pozwala na klasyfikację ze średnią dokładnością 97.3\%. \\
W systemach reguł-P można wyodrębnić dwa podstawowe typy reguł różniące się między sobą sposobem interpretacji. Wyróżnia się więc reguły najbliższego sąsiada lub k-najbliższych sąsiadów (ang. k-nearest neighbor rule, \kNN) oraz {\it reguły prototypowe progowe} (ang. prototype threshold rules, PTR) \cite{Duch-SBM}.  

\section{Reguły typu \kNN}
Reguły typu \kNN bazują na zasadzie analizy minimalnej odległości do poszczególnych prototypów, zgodnie z powszechnie znanym algorytmem klasyfikacji zwanym również \kNN \cite{Duda-Hart-kNN}. W notacji regułowej, przesłance reguły odpowiada tutaj pojedynczy prototyp, natomiast konkluzji odpowiada singleton określający etykietę klasy. Najczęściej spotykanym operatorem implikacji jest operator iloczynu, który pozwala na określenie wartości wagi $w$ określającej stopień aktywacji konkluzji. W takim przypadku uzyskiwany jest zbiór reguł postaci \reff{eq:kNN-Rule}
\beq \label{eq:kNN-Rule}
\hbox{ Jeżeli } \Bx \hbox{ {\it jest podobny do} } \Bp_1  \hbox{ To }C(\Bx) = C(\Bp_1)\\
\hbox{ Jeżeli } \Bx \hbox{ {\it jest podobny do} } \Bp_i  \hbox{ To }C(\Bx) = C(\Bp_i)\\
\hbox{ Jeżeli } \Bx \hbox{ {\it jest podobny do} } \Bp_{i+1}  \hbox{ To }C(\Bx) = C(\Bp_{i+1})
\eeq
gdzie ($\Bx$ {\it jest podobny do } $\Bp_i$) realizowane jest poprzez różne miary odległości ($D(\Bx,\Bp_i)$) lub podobieństwa ($S(\Bx,\Bp_i)$). Proces znajdowania ostatecznej odpowiedzi takiego systemu, gdy w algorytmie \kNN  $k=1$ można opisać zależnością \reff{eq:kNN-Rule-agreg}.
\be \label{eq:kNN-Rule-agreg}
%
\hbox{ Jeżeli } \Bp'=\arg \min_{i} D(\Bx,\Bp_i) \hbox{ To }C(\Bx) = C(\Bp')
%
\ee
%
Wartość parametru $k$ ma istotny wpływ na uzyskany wynik działania systemu. Odpowiada on za liczbę reguł (prototypów) branych pod uwagę podczas podejmowania decyzji, przy czym rozważanych jest $k$ najsilniej aktywowanych prototypów. W zależności od wybranej metody agregacji konkluzji odpowiedź systemu może wówczas przyjmować różne wartości. \\
W przypadku klasycznego algorytmu \kNN, gdy $k>1$ i agregacja poszczególnych konkluzji realizowana jest operatorem ($\max(\cdot)$) ostateczna odpowiedź podejmowana jest poprzez głosowanie wyznaczonych przez poszczególne najsilniej aktywowane prototypy etykiet klas. Takie rozwiązanie wymaga jednak dużej liczby prototypów co zmniejsza przejrzystość systemu, a tym samym jego przydatność jako reguł prototypowych. Dlatego też często stosowaną modyfikacją jest przekształcenie uzyskanej wartości odległości poprzez pewną funkcję $\mathcal{T}(\cdot)$ celem wyznaczenia wartości podobieństwa. Dzięki temu zwiększa się elastyczność systemu. Rozwiązanie to znane jest jako ważony lub rozmyty algorytm \kNN (ang. weighted/fuzzy/soft-\kNN) \cite{Kunch-Book,Duch-SBM}, a poprzez modyfikację operatora $\mathcal{T}(\cdot)$ wpływa się na różne sposoby ważenia. Najczęściej w przypadku algorytmu ważonego \kNN wartość aktywacji konkluzji - wartości wag $w_i$ przyjmuje się jako $w_i=1/D(\Bp_i,\Bx)$,  $w_i=1-D'(\Bp_i,\Bx)$ (gdzie $D'(\cdot)$ jest znormalizowaną wartością odległości). \\
Cechą charakterystyczną systemu \kNN jest jego równoważność z różnymi innymi systemami bazującymi na prototypach. Przykładem tego mogą być sieci RBF czy też klasyfikator Parzena, które są uzyskiwane dla $k=l$, gdzie $l$- to liczba wektorów zbioru treningowego oraz poprzez wykorzystanie ważonego algorytmu \kNN.\\
Znane są również rozwiązania klasyfikatora \kNN, w których każdemu prototypowi przypisanych jest $c$ etykiet odpowiednio dla każdej klasy z odpowiednimi wagami $\Bw$ (jak w algorytmie klasteryzacji z powtórnym etykietowaniem, opisanym w rozdziale \ref{sec:ProtoSel-clust}) \cite{Kunch-PrePost}. Odpowiada to złożonej konkluzji, gdzie poszczególne składowe wektora $\Bw$ określają stopień spełnienia danej składowej konkluzji. Jednym z alternatywnych rozwiązań jest również  przypisywanie wag prototypom uwzględniające zaufanie do każdego z nich. Przykładem tego jest praca Ducha o kompetentnych komitetach \cite{Duch-ProtoWeights}.\\
Kuncheva oraz Bezdek zebrali całą rodzinę różnych metod \kNN pod wspólnym systemem zwanym {\it Uogólniony Klasyfikator Najbliższego Prototypu} (ang. generalized nearest prototype classifier, GNPC).% przedstawionym na rys \reff{fi:GNPC} 
%\bfig
%
%\caption{Uogólniony klasyfikator najbliższego prototypu} \label{fi:GNPC}
%\efig 
GNPC składa się więc z pięciu elementów ($\BP$,$\BW$,$T(\cdot)$,$\mathcal{S}$,$\mathcal{A}$), które odpowiednio oznaczają:
\begin{itemize}
\item $\BP$ - zbiór prototypów
\item $\BW$ - macierz wag $[l \times c]$ dla poszczególnych etykiet 
\item $T(\cdot)$ - monotoniczna funkcja malejąca, transformująca odległość do postaci 
znormalizowana miara podobieństwa np. $S(\cdot)=exp\left({-D(\cdot)^2}\right)$ gdy $T(z)=exp(-z)$
\item $\mathcal{T}$ - operator implikacji, najczęściej operator T-normy w systemach rozmytych 
\item $\mathcal{A}$ - operator funkcji agregującej w systemach rozmytych
\end{itemize}
Tak zbudowany system prototypowy pozwala na realizację niemal wszystkich powszechnie znanych systemów bazujących na zasadzie najbliższego sąsiada, w tym sieci LVQ, klasyfikatora Parzena, sieci RBF czy też innych algorytmów bazujących na funkcjach jądrowych (np. SVM). Co więcej, do ich realizacji wystarczą jedynie operatory w postaci $\mathcal{T}=iloczyn(\cdot)$ odpowiadający operatorowi implikacji, oraz $\mathcal{A}=max(\cdot)$ lub $suma(\cdot)$.\\
W systemach reguł-P pożądana jest łatwość interpretacji wyników, która sprowadza się do optymalizacji takich parametrów systemu jak:
\begin{itemize}
\item redukcja liczby prototypów 
\item redukcja wymiarowości
\item selekcja odpowiedniej miary odległości lub podobieństwa
\item optymalizacja położenia prototypów
\item ważenie cech oraz prototypów
\item dobór odpowiedniej postaci operatorów $\mathcal{S}$ oraz $\mathcal{I}$
\end{itemize}
Należy zwrócić uwagę na pewne problemy, które mogą się pojawić podczas próby optymalizacji systemów reguł prototypowych. Często bowiem liczba prototypów oraz liczba cech jest odwrotnie proporcjonalna względem dokładności klasyfikacji. Pojawia się więc problem optymalizacji wielokryterialnej, gdzie pożądany jest kompromis pomiędzy przejrzystością modelu, czyli redukcją wymiarowości i liczby prototypów, a jego dokładnością.\\
Innym parametrem mającym istotny wpływ na możliwości interpretacji zbudowanego modelu jest dobór operatora  $\mathcal{A}()$ oraz $k$. Im większa jest wartość parametru $k$ tym więcej prototypów bierze udział w podejmowaniu decyzji, a tym samym zmniejsza się łatwość zrozumienia podjętej decyzji przez system. Podobna sytuacja występuje przy doborze funkcji $\mathcal{A}()$, gdzie ostateczna decyzja jest wynikiem ważenia różnych reguł składowych. Problem ten dotyczy w szczególności reguł prototypowych typu sieci RBF lub klasyfikatora Parzena, gdzie wszystkie prototypy jednocześnie biorą udział w podejmowaniu decyzji. Dlatego też najczęściej używanymi parametrami systemów reguł prototypowych jest $k=1$ oraz $\mathcal{A}(\cdot)=max(\cdot)$ co pozwala na najprostszą możliwą interpretację, gdzie odpowiedź systemu podejmowana jest przez jeden prototyp.\\
Ogólna postać procesu strojenia (uczenia) systemu reguł prototypowych typu najbliższego sąsiada stanowi szeregowy proces przetwarzania, który może przebiegać kolejno: w pierwszym kroku realizowane jest wstępne przetwarzanie danych (np. normalizacja lub standaryzacja), następnie dokonywana jest selekcja cech, w trzecim kroku następuje wybór odpowiedniej miary odległości $D(\cdot)$ zaś w kroku czwartym dokonywana jest selekcja i optymalizacja prototypów. % \reff{fi:SerialkNN}.
%\bfig
%
%\caption{Przetwarzanie danych w systemach reguł prototypowych} \label{fi:SerialkNN}
%\efig  

\section{Reguły prototypowe progowe}
W odróżnieniu od reguł prototypowych typu \kNN, gdzie pojedynczy prototyp można było interpretować jako przesłankę reguły spełnioną w stopniu równym odległości od prototypu, tak w przypadku reguł prototypowych progowych przesłanka zdefiniowana jest przez parametry ($\BP$,$\Theta$,$D(\cdot)$,$\bf{F}$) gdzie:
\begin{itemize}
\item $\BP$ - zbiór prototypów (pojedynczy prototyp odpowiada pojedynczej regule)
\item $\Theta$ - wartość progu
\item $D(\cdot)$ - miara odległości
\item $\bf{f}$ - zbiór cech (lokalny lub globalny)
\end{itemize} 
W związku z powyższym pojedynczą regułę można zdefiniować jako \reff{eq:rNN-Rule}
%
\be \label{eq:rNN-Rule}
%
\hbox{ Jeżeli } D(\Bx,\Bp_i)<\Theta_i \hbox{ To }C(\Bx) = C(\Bp_i)
%
\ee
%
Jej postać wskazuje na to, iż w odróżnieniu od reguł \kNN pojedynczy prototyp z progiem stanowi informatywną regułę wyznaczającą w hiperprzestrzeni wejściowej podprzestrzeń z przypisaną etykietą klasy. Pozwala to na uproszczenie interpretacji wyników oraz na zapis reguł w postaci listy typu {\it jeżeli~\ldots~to~\ldots ; jeżeli~\ldots~to~\ldots~jak~nie~to~\ldots} lub drzewa. \\
Taką konstrukcję zbioru reguł można zinterpretować w sposób, gdzie każda reguła jest niezależna od pozostałych reguł. Dzięki temu możliwa staje się lokalna transformacja danych w ramach podprzestrzeni wyznaczonej przez przesłankę reguły. Między innymi pozwala to np. na lokalną selekcję cech w celu maksymalizacji możliwości uogólniania. Tej właściwości niestety nie posiadają systemy typu \kNN, które wymagają wspólnego zbioru atrybutów w całej przestrzeni wejściowej. \\
Jednym z pierwszych i najprostszych systemów posiadających właściwość interpretacji jako zbioru reguł jest algorytm Ograniczonej Energii Kulomba (ang. restricted columb energy, RCE)  \cite{Duch-SBM,B-Duda-Hart}. Niestety jego wadą jest duży zbiór wektorów prototypowych, co znacznie utrudnia ich interpretację. Dlatego też w rozprawie omówiono oraz zaprezentowano dwa alternatywne algorytmy pozwalające na poszukiwanie odpowiedniego zbioru reguł. 

\section{Interpretacja reguł prototypowych}
Podstawą działania reguł prototypowych jest analiza podobieństwa badanego przypadku do wzorców (prototypów) opisujących dane zagadnienie. Pojedynczy prototyp opisuje więc w sposób ważony fragment przestrzeni skupionej wokół prototypu, gdzie waga jest proporcjonalna do odległości pomiędzy tym prototypem, a badanym obiektem. Można więc system prototypowy interpretować w sposób, w którym pojedynczy prototyp odpowiada przesłance reguły, zaś jej konkluzją jest wartość klasy do której ten prototyp jest przypisany. Wartość podobieństwa stanowi zaś współczynnik określający pewność podjętej decyzji. Ponieważ duża część funkcji odległości może zostać poddana dekompozycji na poszczególne składowe (np. funkcje addytywne) - separowalne funkcje odległości - interpretacja działania systemu prototypowego może więc zostać przedstawiona w postaci reguł rozmytych, co omówiono w rozdziale \reff{chap:P2F-rules}.\\
Interpretacja systemu jako wzorców w przestrzeni wejściowej ma wiele zalet. W szczególności analiza prototypów pozwala na wstępne skoncentrowanie uwagi badawczej na wybranych wzorcach i pominięcie analizy mniej informatywnych przypadków. Przykładem tego mogą być problemy diagnozowania medycznego, gdzie analiza prototypów pozwala na wskazanie konkretnych pacjentów, a tym samym najistotniejszych i najbardziej typowych objawów chorobowych pozwalających na odróżnienie ich od osób zdrowych.\\
 Kolejnym atutem prototypów jest ich uniwersalność w znaczeniu naturalnej interpretacji lingwistycznej. Przykładem tego może być porównanie z systemami reguł rozmytych. Lingwistyczne wnioskowanie w oparciu o systemy rozmyte zakłada przypisanie poszczególnym zmiennym lingwistycznym odpowiednich wartości lingwistycznych w postaci przymiotników przypisanych funkcją przynależności. Takie podejście czułe jest na kontekst sytuacyjny, przykładem tego może być przymiotnik {\it wysoki} opisujący {\it człowieka}, który w zależności od kontekstu - czy mamy na myśli: kobiety, mężczyzn, dzieci czy też koszykarzy przyjmuje różną reprezentację funkcyjną. Wady tej pozbawione są systemy prototypowe, w których prototyp odpowiada pewnej koncepcji, przy czym możliwa jest dekompozycja koncepcji na poszczególne składowe zmiennych lingwistycznych. Takie podejście wydaje się być dużo bardziej ogólne, co więcej - pozwala na integrację wiedzy z różnych źródeł, gdyż zawsze istnieje możliwość uszczegółowienia koncepcji poprzez dodanie jej nowych, opisujących ją atrybutów.\\
Wadą systemów prototypowych jest jednak redundancja informacji, która może występować dla reguł typu \kNN gdy prototypy opisane w przestrzeni wejściowej przyjmują te same wartości dla danego atrybutu. Przykładem tego mogą być prototypy opisujące osobę zdrową, dla której normalna temperatura ciała wynosi $36,6^o C$. W przypadku reguł prototypowych niemożliwe jest jednak pozbycie się tej informacji gdyż jest ona składową opisu tych koncepcji. Rozwiązaniem problemu redundancji może być segmentacja problemu i podział na podprzestrzenie w których niezależnie dokonuje się adaptacji modelu - zagadnienie to jednak nie było rozważane w ramach rozprawy. Inną możliwością jest transformacja reguł prototypowych do reguł rozmytych, gdzie w opisie przesłanki reguły możliwe jest wyłączenie części wspólnej kilku przesłanek zdekomponowanych reguł prototypowych.   

\section{Reguły prototypowe a metody bazujące na przypadkach (ang. case based reasoning)}
%Problem uczenia przez analizę przypadków był analizowany przez wielu badaczy, w tym na szczególną uwagę zasługują metody typu: 
Do metod uczenia poprzez analizę przypadków można zaliczyć: wnioskowanie pamięciowe zaproponowane przez Stanfilla i Waltza (ang. memory based reasoning, MBR) \cite{MBR}, uczenie w oparciu o instancje autorstwa Aha i innych (ang. instance based learning, IBL) \cite{Aha-IBL} oraz wnioskowanie w oparciu o przypadki (ang. case based reasoning, CBR) \cite{CBR}. Wszystkie one bazują na algorytmie \kNN, jednakże żadna z wymienionych dotychczas metod nie miała na celu reprezentacji danych w sposób zrozumiały dla człowieka. \\
Głównym zadaniem metod IBL jest maksymalizacja zdolności generalizacji i minimalizacji złożoności obliczeniowej algorytmu \kNN. Powoduje to, że metody należące do grupy IBL stanowią istotną grupę algorytmów mogących służyć ekstrakcji reguł-P. Niestety przeprowadzone eksperymenty \cite{Norb-ProtoSel1} wskazują, iż część z metod IBL pozostawia dużo niepotrzebnych wektorów w procesie uczenia, koncentrując się nie na uzyskaniu przejrzystości modelu, lecz jedynie na maksymalizacji jego zdolności uogólniania.\\
CBR powszechnie stosowany jest do rozwiązywania różnych problemów analizy przypadków, gdzie pojedyncze sytuacje odpowiadają wystąpieniu określonych zjawisk. Innymi słowy CBR bazuje na rozwiązywaniu nowych problemów na podstawie podobieństwa do już rozwiązanych zagadnień zgromadzonych w bazie wiedzy. CBR między innymi używany jest w analizie przepisów prawa precedensowego, wiele wdrożeń można również zaobserwować w medycynie np. \cite{CBR-Schmidt-Medic}. W systemach CBR główny nacisk położony jest również na maksymalizację dokładności predykcji, jednakże poszczególne przypadki traktowane są jako pojedyncze reguły postępowania, a baza wiedzy jest często inkrementacyjnie rozbudowywana. Związane jest to z procesem eksploracji danych online, gdzie często każdorazowy sukces lub porażka predykcji zakończony jest umieszczeniem tego przypadku w bazie wiedzy z odpowiednio zmodyfikowaną etykietą. Wykorzystanie algorytmu \kNN w CBR związane jest z koniecznością analizy podjętej decyzji, a jak opisano w poprzednim podrozdziale metoda \kNN pozwala na jej łatwą interpretację. \\
Główną różnicą modeli CBR w stosunku do reguł-P jest brak przejrzystości systemów CBR, co związane jest z dużą liczbą przypadków zgromadzonych w bazie wiedzy. Problem ten powoduje również zmniejszenie szybkości działania oraz duże zapotrzebowanie na zasoby tego typu systemu. Dlatego powszechnie stosuje się różne metody mające na celu przyspieszenie procesu znajdywania najbliższych sąsiadów. Do typowych rozwiązań należą tutaj algorytm Kd-tree \cite{KDTree} lub inne metody drzew decyzji jak C4.5, które wykorzystywane są do wstępnej indeksacji i selekcji przypadków  \cite{Plaza-CBR}.\\
%Problem of system transparency usually is solved by logical rules, however if number of obtained
%rules increase then the simplicity of model decrease, in other words transparency is inverse
%proportion to the rules number. Before fuzzy logic and F-rules, rules extraction processes used to
%base on classical - crisp logical rules (C-rules), which in applications to real world problems may
%lead to huge set of useless rules with week generalization and small intelligible. The simplest
%example of this problem describes fig. \ref{fi:CrispRulesProb}.a%

%\section{Uniwersalność reguł prototypowych}
%ab
