%--------------------END P-rules----------------------------------
\chapter{Miary odległości} \label{chap:dist}%
Miary odległości, jak i miary podobieństwa stanowią bazę większości metod inteligencji
obliczeniowej. W literaturze opisywana jest duża liczba możliwych miar odległości,
jednakże praktyka metod sztucznej inteligencji pokazuje, że nie wszystkie z nich muszą
spełniać własności metryki opisywane warunkami \reff{eq:DistProp}. \\
W prezentowanej rozprawie terminy takie, jak podobieństwo lub odległość są używane w
szerszym znaczeniu niż matematycznym i muszą jedynie spełniać warunek {\it izolacji} dla
odległości. Założenie takie podyktowane jest zarówno analogią do procesów kognitywnych
zachodzących w naszych mózgach, gdzie przykładowo ,,niebo'' kojarzy się z kolorem
niebieskim, ale odwrotna relacja nie jest już tak silna $D\left( {niebo,niebieski} \right) \ne
D\left( {niebieski,niebo} \right)$ (gdzie $D(\cdot)$ oznacza funkcję odległości) nie jest więc spełniony warunek symetrii; podobnie mówiąc, że dziecko jest podobne do ojca oraz podobne do matki nie oznacza faktu, że matka i ojciec są do siebie podobni; oraz z praktyki metod inteligencji obliczeniowej, gdzie, jak pokazano w rozdziale \ref{chap:P2F-rules} transformacja iloczynu 
trójkątnej lub trapezoidalnej funkcja przynależności systemów rozmytych do postaci funkcji odległości nie spełniają warunku nierówności trójkąta.
%
\be
\begin{array}{l}
    D\left( {\Bx,\Bp} \right) \ge 0, \hbox{ równość, wtedy i tylko wtedy gdu }{\Bx} = {\Bp}\hbox{ (izolacja)} \\
    D\left( {\Bx,\Bp} \right) = D\left( {{\Bp},{\Bx}} \right)  \hbox{(symetria)} \\
    D\left( {\Bx,\Bp} \right) \le D\left( {{\Bx},{\By}} \right) + D\left( {{\By},{\Bp}} \right)  \hbox{(nierówność trójkąta)} \\
\end{array}
\label{eq:DistProp}
%
\ee
%
Ogólna taksonomia różnych neuronowych funkcji transferu zawierająca funkcje odległości i
podobieństwa może być znaleziona w \cite{Duch-TransFun,Norb-Book}. Jednakże nie
wyczerpuje ona wszystkich znanych miar, o pewnych zastosowaniach specyficznych miar
odległości, jak w problemach wizji komputerowej (ang. computer vision) donoszono również w pracach
\cite{Dubisson-HausdorffDist,Jacobs-NonMetricDist,D-Nowak-LearnDist}. W rozprawie przedstawiono
jedynie najpopularniejsze miary z ich własnościami, które jak dotąd zostały
zastosowane w systemach reguł progowych z bardzo dobrymi rezultatami.\\
W swojej pracy Duch i Jankowski \cite{Duch-TransFun} zaproponowali różne metody podziału miar odległości,
jednakże najbardziej istotną metodą z punktu widzenia rozprawy wydaje się być podział ze
względu na wpływ danych na wartość miary odległości.

\section{Deterministyczne miary odległości}
Deterministyczne funkcje odległości charakteryzują się brakiem wpływu rozkładu danych w
przestrzeni na wartość funkcji odległości. Innymi słowy rozkład danych treningowych nie
wpływa na wartość odległości mierzonej pomiędzy parą wektorów. Najpopularniejszym
przykładem takich funkcji jest metryka Euklidesa (norma $L_2$) \reff{eq:Euclid}
%
\be \label{eq:Euclid}
%
D\left({ {\Bx},{\Bp}} \right)= \sqrt {\sum\limits_{i = 1}^n {\left( {x_i  - p_i }
\right)^2 } }
%
\ee
%
gdzie $\Bx=\left[ {x_1 ,x_2 ,...,x_n } \right]^T $ i $\Bp=\left[ {p_1 ,p_2 ,...,p_n }
\right]^T $ są wektorami pomiędzy którymi odległość $D$ jest liczona. Metryka ta ma
istotną właściwość z punktu widzenia reguł prototypowych, a mianowicie stosując regułę
najbliższego sąsiada uzyskiwana granica decyzji pomiędzy dwoma prototypami jest zawsze
hiperpłaszczyzną. Dzięki temu znacznie upraszcza się proces wnioskowania i zrozumienia
rezultatów podjętych decyzji. \\
Innym przykładem metryki deterministycznej jest odległość Manhattan, znana również jako
norma $L_1$ gzie odległość jest obliczana jako suma różnic projekcji wektorów na osie
układu współrzędnych \reff{eq:Manh}.
%
\be \label{eq:Manh}
%
D\left({ {\Bx},{\Bp}} \right)= \sum\limits_{i = 1}^n {\left| {x_i  - p_i } \right| }
%
\ee
%
Ważną negatywną cechą normy $L_1$ w zastosowaniu do algorytmu \kNN jest możliwość wystąpienia impasów. Właściwość ta wynika z faktu, iż w odróżnieniu od innych
miar odległości obszar równej odległości pomiędzy dwoma prototypami nie jest jak w
przypadku normy $L_2$ hiperpłaszczyzną lub ogólnie figurą płaską, lecz granica ta w
pewnych obszarach przyjmuje postać podprzestrzeni o równej odległości od pary prototypów,
co uniemożliwia jednoznaczne podjęcie decyzji. Przedstawia to rys.\reff{fi:ManhDist}
%
\bfig
    \epsfig{figure=pic/ManhTie.eps,width=6.0cm}
%
  \caption{Przykład wykorzystania odległości Manhattan oraz impasu powstałego po jej wykorzystaniu (obszar nie zakreślony)}
%
\label{fi:ManhDist}
\efig

Norma $L_\infty$ znana również jako odległość Czebyszewa opisywana jest równaniem
\reff{eq:Cheby}
%
\be \label{eq:Cheby}
%
D\left({\Bx,\Bp}\right)=\max\limits_{i=1..n} \left|{x_i-p_i}\right|
%
\ee
%
Funkcja ta, z punktu widzenia reguł prototypowych ma istotne znaczenie, pozwalając na
uzyskiwanie klasycznych reguł ostrych w zapisie prototypowym. \\
Przedstawione dotychczas miary odległości stanowią poszczególne przypadki ogólnej metryki
Minkowskiego opisanej równaniem \reff{eq:Mink}, gdzie zmiana parametru $\alpha$ wpływa na kształt konturu stałej odległości od prototypu.
\reff{fi:MinkConst}
%
\be \label{eq:Mink}
%
D\left({ {\Bx},{\Bp}} \right)= \left({\sum\limits_{i = 1}^n {\left| {x_i  - p_i }
\right|^\alpha } }\right)^{1/\alpha}
%
\ee
%
Przez odpowiednie określenie wartości parametru $\alpha$ możliwe jest uzyskanie odległości Manhatan dla $\alpha=1$, podobnie dla $\alpha=2$ otrzymuje się odległość Euklidesa, natomiast dalszy wzrost wartości w granicy gdy $\alpha\rightarrow \infty$ prowadzi do odległości Czebyszewa. \\
Interpretacja rys.\reff{fi:MinkConst} zmierza do wniosku, że wzrost wartości $\alpha$ odpowiada zwiększeniu wypukłości funkcji odległości, tym samym wzrostowi pola recepcyjnego pojedynczego prototypu. Powoduje to, że zmianie ulega kształt granicy decyzji klasyfikatora 1NN, co obrazuje rys.\reff{fi:MinkDecis}. W praktyce analizy danych bardzo często wartość $\alpha$ poddawana jest adaptacji w procesie uczenia jako jeden z parametrów modelu, tak by zmaksymalizować dokładność uzyskanych wyników.
\bfig
%
    \epsfig{figure=pic/Mink1_2_10.eps,width=8.0cm}
  \caption{Kształ odległości Minkowskiego dla trzech różnych wartości parametru $\alpha$: 1,2,10 }
%
\label{fi:MinkConst}
\efig
      
\bfig
%
    \epsfig{figure=pic/Mink1.eps,width=4.7cm}
    \epsfig{figure=pic/Mink2.eps,width=4.7cm}
    \epsfig{figure=pic/Mink10.eps,width=4.7cm}
  \caption{Kształt granicy decyzji dla klasyfikatora 1NN dla trzech różnych wartości $\alpha$ odległości Minkowskiego: 1,2,10}
%
\label{fi:MinkDecis}
\efig
%
Pewną popularną miarą odległości, dającą dla niektórych zbiorów danych bardzo dobre
wyniki, jest miara Canberra \reff{eq:Canberra} należąca do grupy miar korelacyjnych rys.\reff{fi:Canberra}.
\be \label{eq:Canberra}
	D(\Bx,\Bp)=\sum_{i=1}^n\frac{|x_i-p_i|}{|x_i|+|p_i|}
\ee
Miara ta ma pewne specyficzne cechy, jest niesymetryczna (nie jest więc miarą metryczną)
oraz dla wektora referencyjnego położonego w początku układu współrzędnych przyjmuje
stałą wartość równą 1. Inną cechą tej miary jest możliwość występowania symbolu
nieoznaczonego jako wartość odległości w przypadku wystąpienia dzielenia przez 0. Cechy
te powodują że praktyczne zastosowania w/w funkcji choć często dające dobre rezultaty
powinno być uważnie rozpatrzone.
 \bfig
%
    \epsfig{figure=pic/CamberraBorder.eps,width=6cm}
    \epsfig{figure=pic/CamberraSurf.eps,width=7cm}
    \caption{Kształt granicy decyzji oraz wykres powierzchni odległości Canbera}
%
\label{fi:Canberra}
\efig
 Inną, popularną miarą powszechnie stosowaną do analizy tekstów jest odległość
 cosinusowa, będąca w rzeczywistości miarą podobieństwa zdefiniowaną jako
\reff{eq:CosineDist1}. 
%
\be \label{eq:CosineDist1}
	D\left({ {\Bx},{\Bp}} \right)= \frac{\Bx^T\Bp}{\left| {\Bx} \right|\left| {\Bp} \right|}
\ee
Funkcja ta mierzy cosinus konta pomiędzy dwoma wektorami $\Bx$ oraz
$\Bp$ jako ich iloczyn skalarny znormalizowany przez iloczyn długości tych wektorów.
Własność ta jest używana do porównywania dokumentów, gdyż przedstawia ona odległość jako
relatywny rozkład jej elementów składowych, uniezależniając wartość od długości tekstów.
Kształt granic decyzji oraz kształt powierzchni odległości cosinusowej przedstawia rys.\reff{fig:Cosine}
\bfig 
%
    \epsfig{figure=pic/CosineBorder,width=6cm}
    \epsfig{figure=pic/CosineSurf,width=7cm}
    \caption{Granica decyzji oraz kształt cosinusowej funkcji odległości}
%
\label{fig:Cosine}
\efig
Podobnie do analizy tekstów używa się miar znormalizowanych, uniezależniając wartość odległości od długości wektorów, co zapisuje się jako \reff{eq:normDist}.
\be
	\overline{D}(\Bx,\Bp)=D\left({\fracS{\Bx}{\left|{\Bx}\right|},\fracS{\Bp}{\left|{\Bp}\right|}}\right) 
%\left|{\Bp}\right|}
	\label{eq:normDist}
\ee

\section{Miary zależne od rozkładu danych}
Miary zależne od rozkładu danych mają tą właściwość, że na wartości odległości przez nie
przyjmowane ma wpływ wzajemne położenie innych wektorów, stanowiących zbiór przypadków do
których należą wektory pomiędzy którymi liczona jest ta odległość. W grupie tej można
wyznaczyć trzy podgrupy: ważone funkcje odległości, probabilistyczne miary odległości 
oraz odległości heterogeniczne.\\
Problematyka adaptacji miar odległości do badanego zagadnienia jest coraz szerzej dostrzegana przez różne środowiska naukowe. W szczególności dotyczy to problemów analizy tekstów \cite{D-Lebanon-TextDist}, obróbki obrazu \cite{D-Chopra-DistFaceVerifi,D-Nowak-LearnDist} czy też zastosowań biomedycznych \cite{D-Scholkopf-ProteinKernel}. Wynikiem tego są różnego rodzaju warsztaty dotyczące problematyki optymalizacji miar odległości odbywające się podczas konferencji jak np. ,,Learning to Compare Examples'' odbywająca się w ramach konferencji NIPS'06. 

\subsection{Ważone miary odległości}
Do tej rodziny miar należą odległości przedstawione w poprzednim rozdziale, z tą jednak
różnicą, że wpływ poszczególnych atrybutów jest ważony poprzez czynnik $w_i$.
\be
%
D\left({ {\Bx},{\Bp};{\Bw}} \right)= \left({\sum\limits_{i = 1}^n {w_i\left| {x_i  - p_i
} \right|^\alpha } }\right)^{1/\alpha}
%
\ee
Wektor $\Bw$ jest uzyskiwany z rozkładu danych i ma wartości niezależne dla każdej z
cech. Problem wyznaczania wektora $\Bw$ poruszali w swoich pracach m.in. Jankowski,
Martinez oraz Dudani \cite{Norb-Book,Martinez-IBL,Dudani-WDist}, natomiast ogólne
porównanie różnych metod ważenia cech dla klasyfikatora \kNN przedstawił Wettschereck i inni w \cite{Aha-WDist}.\\
W literaturze spotkać można dwa podejścia związane z ważeniem cech - globalne oraz
lokalne. W pierwszym podejściu wyznaczane są wspólne wagi dla wszystkich prototypów,
osobno dla każdej z cech. Podejście to ma tą cechę, iż podaje ogólny poziom istotności
cechy w procesie dyskryminacji dla analizowanego zbioru. Jest to więc w pewnych
problemach bardzo pożądana wiedza. Możliwa jest też selekcja lub ranking cech w oparciu o tak
wyznaczone współczynniki. Druga możliwość - ważenie lokalne wyznacza odpowiednie wagi dla
każdej z cech i dla każdego z prototypów osobno, dzięki czemu możliwe jest uzyskanie
większej elastyczności modelu, a uzyskane prototypy lepiej oddają lokalne rozkłady
danych. Wadą podejścia lokalnego jest wzrost liczby stopni swobody
budowanego modelu ($l\cdot n$) w stosunku do ($ l + n$) dla modelu z globalnym ważeniem
cech. Ma to szczególnie istotne znaczenie przy analizie pewnej klasy problemów
zawierających małą liczbę wektorów treningowych ($m$).\\
Przedstawione funkcje odległości mają jedną istotną wadę - używając ich zakłada się bowiem
niezależność cech. Założenie to jest uzasadnione, jeżeli dążymy do uzyskania dużej
łatwości w interpretacji modelu, podobnie jak w rozmytych lub neuronowo-rozmytych
systemach regułowych, gdzie niezależność poszczególnych składowych pozwala na
wykorzystanie wnioskowania opartego o prawa logiki rozmytej. Wadą takiego podejścia jest
 niedokładne odwzorowanie rozkładu danych w przestrzeni, w szczególności jeżeli
występuje korelacja pomiędzy poszczególnymi cechami. Dlatego też często stosowanym
rozwiązaniem są macierze wag $\BW$, których elementy $\Bw_{ij}$ definiują relacje
pomiędzy cechami $i$-tą i $j$-tą. Jeżeli macierz $\BW$ określona jest jako macierz kowariancji
$\BW=\bf{A}$, wówczas odległość \reff{eq:Mahalanob} nazywana jest odległością Mahalanobisa. Przy czym  $\bf{A}$ jest macierzą symetryczną względem diagonalnej oraz dodatnio określoną.
\be \label{eq:Mahalanob}
%
D\left({ {\Bx},{\Bp};{\BW}} \right)= \left(\Bx-\Bp \right)^{T} {\mathbf W} \left(\Bx-\Bp \right)
%
\ee
Jak już wspomniano wartości macierzy ${\bf A}$ uzyskiwane są poprzez analizę korelacji
danych, zarówno globalną jak i lokalną. Powszechne są również podejścia wykorzystujące
różne metody optymalizacji jak gradientową, stosowaną powszechnie w sieciach RBF
\cite{Schwenker-3RBF} lub bazująca na algorytmie EM (ang. expectation maximization).
Przykładem zastosowania macierzy $\BW$ w algorytmie \kNN jest metoda {\it Large Margin \kNN}
zaproponowana przez Weinberger, Blitzer i Saulin w \cite{Weinberger-LMNN}.\\
Przedstawione dotychczas funkcje odległości przeznaczone są dla atrybutów
ciągłych, jednakże analiza realnych zbiorów danych często sprowadza się do problemu cech
dyskretnych, symbolicznych lub binarnych. W takich przypadkach powszechnie stosowanym
rozwiązaniem jest odległość Hamminga opisana równaniem \reff{eq:HammingDist}
\be \label{eq:HammingDist}
%
%D\left({\Bx,\Bp}\right)=\sum\limits_{i = 1}^n {\left\{ {\begin{array}{*{20}c}
%   {1{\hbox{ if }}x_i  = p_i }  \\
%   {0{\hbox{ if }}x_i  \ne p_i }  \\
%\end{array}} \right.}
%
D\left({\Bx,\Bp}\right)=\sum\limits_{i = 1}^n \delta(x_i,p_i)
\ee
gdzie $\delta(\cdot)$ jest deltą Kroneckera

\subsection{Probabilistyczne miary odległości}
Szczególny problem dla wszystkich metod bazujących na algorytmie \kNN stanowiły cechy o
nieciągłej dziedzinie, w szczególności cechy symboliczne, w których typowe funkcje
odległości nie zdają egzaminu. Pewnym rozwiązaniem tego problemu były funkcje odległości
z rodziny funkcji Hamminga, jednakże uzyskiwane rezultaty często odbiegały od oczekiwań.
Ich alternatywą stały się probabilistyczne miary odległości, wywodzące się z analizy
możliwości generalizacji algorytmu \kNN. Jedną z pierwszych probabilistycznych funkcji odległości
była miara, którą zaproponował Short i Fukunaga (miara SFN)
\cite{Fukunaga_SFM} opisana równaniem \reff{eq:SFMdist}
\be \label{eq:SFMdist}
%
D\left({\Bx,\Bp}\right) = \sum\limits_{k = 1}^c {p\left({C_k |\Bp}\right)\left|
{p\left({C_k |\Bp}\right) - p\left({C_k |\Bx}\right)} \right|}
%
\ee
SFM została wyznaczona jako miara lokalna, która bazowała na minimalizacji wartości
oczekiwanej różnicy pomiędzy błędem klasyfikacji algorytmu \kNN ze skończoną i
nieskończoną liczbą próbek (wartość teoretyczna) - innymi słowy bazowała na minimalizacji
asymptotycznego i skończonego ryzyka.\\
Inną probabilistyczną miarą odległości wyprowadzoną przy założeniu bezpośredniej
minimalizacji błędu klasyfikacji była miara Minimum Risk Metric (MRM) \reff{eq:MRMdist}
zaproponowana przez Blanzieri i Ricci w \cite{Ricci-MRM,Ricci-MRM2}.
\be \label{eq:MRMdist}
%
D\left({\Bx,\Bp}\right) = \sum\limits_{k = 1}^c {p\left({C_k |\Bp}\right)\left| {1 -
p\left({C_k |\Bx}\right)} \right|}
%
\ee
Stanfill i Waltz w \cite{Stanfill-VDM} zaproponowali odległość Value Difference Metric
(VDM). Ich propozycja nie wywodziła się z analizy teoretycznej, jednakże przeprowadzone
eksperymenty wykazały jej bardzo dużą skuteczność. Oryginalna miara VDM była
zaproponowana bezpośrednio dla danych symbolicznych jako \reff{eq:VDMdist}.
\be \label{eq:VDMdist}
%
D\left({X,P}\right)= \sum\limits_{i = 1}^n {\sqrt {\sum\limits_{j = 1}^c {\left(
{\frac{{N\left( {x_i ,c_j } \right)}}{{N\left( {x_i } \right)}}} \right)^2 } }
\sum\limits_{j = 1}^c {\left( {\frac{{N\left( {x_i ,c_j } \right)}}{{N\left( {x_i }
\right)}} - \frac{{N\left( {p_i ,c_j } \right)}}{{N\left( {p_i } \right)}}} \right)^2 } }
%
\ee
gdzie $N\left( {x_i}\right)$ oznacza liczbę wystąpień wartości $x$ dla cechy $i$ ($x_i$)
w zbiorze treningowym oraz $N\left( {x_i,c_j}\right)$ oznacza liczbę wystąpień wartości
$x_i$ dla $i$-tej cechy $j$-tej klasy $c_j$, a ostatecznie $N(x_i ,c_j)/N(x_i)$
%${\frac{{N\left( {x_i ,c_j }
%\right)}}{{N\left( {x_i } \right)}}}$ 
stanowi ocenę prawdopodobieństwa aposteriori $p(c|x)$. Wówczas
odległość VDM może zostać również zapisana jako \reff{eq:VDMPdist}
\be \label{eq:VDMPdist}
%
D\left({\Bx,\Bp}\right) = \sum\limits_{i = 1}^n {\sqrt {\sum\limits_{j = 1}^c {p\left(
{c_j \left| {x_i } \right.} \right)^2 } } \sum\limits_{j = 1}^c {\left( {p\left( {c_j
\left| {x_i } \right.} \right) - p\left( {c_j \left| {p_i } \right.} \right)} \right)^2 }
}
%
\ee
Oryginalna postać odległości VDM została następnie zmodyfikowana przez Cost i Salzberga
w \cite{Salsberg-MVDM} do postaci metryki MVDM (ang. modified value difference metric) \reff{eq:MVDMdist},
gdzie pominięto pierwszy czynnik równania odległości.
\be \label{eq:MVDMdist}
%
D\left({\Bx,\Bp}\right) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^c {\left( {p\left(
{c_j \left| {x_i } \right.} \right) - p \left( {c_j \left| {p_i } \right.} \right)}
\right)^\alpha } }
%
\ee
gdzie $\alpha$ oznacza wartość dobieraną empirycznie dla konkretnego problemu.\\

\subsection{Heterogeniczne miary odległości}
Poważnym zagadnieniem problemów klasyfikacyjnych są zbiory o niejednorodnych typach
atrybutów, w których część cech jest ciągła, a część symboliczna lub
dyskretna. Wówczas żadna z dotychczas prezentowanych funkcji odległości nie pozwala na
uzyskiwanie pożądanych wyników. Problem ten studiowali Wilson i Martinez w
\cite{Martinez-HetDist} i zaproponowali szereg miar heterogenicznych, które
stosują różne typy odległości dla różnych typów cech. Ogólna idea zaproponowana przez
autorów wykorzystuje cechę addytywności funkcji odległości, gdyż większość spośród
przedstawionych funkcji uwzględniając miary VDM, Hamminaga czy Minkowskiego składają
poszczególne komponenty cech poprzez ich sumowanie.
\be \label{eq:HetDist}
%
\begin{array}{c}
D^2\left({\Bx,\Bp}\right) = D_{Mink}^2 \left( {\Bx_{\bf{a}} ,\Bp_{\bf{a}} ;\Bw_{\bf{a}}}
\right)  + D_{VDM}^2 (\Bx_{\bf{b}} ,\Bp_{\bf{b}} ;\Bw_{\bf{b}})\\
\\
 + D_{Hamm}^2 \left({\Bx_{\bf{c}} ,\Bp_{\bf{c}} ;\Bw_{\bf{c}}} \right)
\end{array}
%
\ee
gdzie $\bf{a},\bf{b},\bf{c}$ są wektorami
o indeksach cech odpowiednio ciągłych, symbolicznych i nominalnych, a $\Bw$ jest wektorem
normalizującym (wektorem wag) dla poszczególnych cech. Przykładem takich odległości
heterogenicznych są {\it Heterogeneous Euclidean-Overlap Metric} (HEOM), gdzie połączono
odległość Euklidesa z odległością Hamminga oraz {\it Heterogeneous Value Difference Metric}
(HVDM) \cite{Martinez-HetDist}, w której sumowane są odległości Euklidesa z odległością
VDM.
W obydwu tych przypadkach uwzględniono również problem brakujących wartości poprzez dodanie 1 dla
atrybutów z brakującymi wartościami.\\
Innym rozwiązaniem zaproponowanym przez Wilsona i Martineza była adaptacja odległości
probabilistycznej do analizy atrybutów ciągłych, bazując na wyrażeniu \reff{eq:MVDMdist}.
Zasugerowali oni trzy metody nieparametrycznej estymacji prawdopodobieństwa
wykorzystującej: dyskretyzację (naiwna dyskretyzacja stałej szerokości) - odległość DVDM,
interpolację wartości uzyskanych z miary DVDM - odległość IVDM oraz estymację bazującą
na okienkowaniu - zwaną odległością WVDM. Dzięki takiemu rozwiązaniu zniknął problem
normalizacji cech występujący w przypadku wykorzystania cechy addytywności odległości jak
w \reff{eq:HetDist}, gdyż wszystkie analizowane atrybuty transformowane są wstępnie do wspólnej
przestrzeni prawdopodobieństwa.\\

\section{Nowe probabilistyczne miary odległości}
Wykorzystania odległości probabilistycznych w zastosowaniu do metod reguł prototypowych
 analizowane były również podczas realizowanej rozprawy. Autor w pracach
\cite{Blachnik-ProbEstPol1,Blachnik-ProbEstTai,Blachnik-ProbEstPol2} zaproponował rozszerzenie istniejących miar heterogenicznych o dodatkową grupę bazującą na nieparametrycznych metodach estymacji prawdopodobieństwa. Grupa zaproponowanych miar dotyczyła wykorzystania odległości prawdopodobieństwa dla atrybutów ciągłych.
W rezultacie badań zaproponowano trzy miary (GVDM, LVDM oraz PVDM) wykorzystujące do estymacji różne metody wywodzące się z metody okien Parzena \cite{B-Webb-Book} i przeprowadzono analizę przydatności zaproponowanych metryk.

\subsection{Nieparametryczne metody estymacji\\ prawdopodobieństwa}
%W celu estymacji wartości rozkładu prawdopodobieństwa cechy $f$ dla wektora $x$ posłużono się następującymi miarami 
Do realizacji probabilistycznych funkcji odległości niezbędna jest estymacja prawdopodobieństwa dla każdego z atrybutów. W tym celu zweryfikowano trzy różne metody: wygładzania Gausowskiego, prostokątnych okien Parzena oraz okien przesuwnych, w wyniku czego uzyskano trzy nowe miary odpowiednio GVDM, LVDM oraz PVDM.
\paragraph{Wygładzanie Gaussowskie.} Miara GVDM, gdzie dla każdego z atrybutów $f$, wartość prawdopodobieństwa $p( c_j | x_{kf} )$ dla wektora $x_k$ wyznaczana jest wg. zależności \reff{eq:GVDM}
\beq
	p( c_j | x_{kf} )= \beta \cdot \sum\limits_{i=1}^{m_j} \exp\left({-\gamma (x_{if}-x_{kf})^2}\right) \\
	\beta=1/\sum\limits_{a=1}^C\left({\sum\limits_{i=1}^{m_j} \exp\left({-\gamma x_{if}^2}\right)}\right)
	\label{eq:GVDM}
\eeq
gdzie $\beta$ jest parametrem normalizującym zapewniającym by $\sum_j p( c_j | x_f ) = 1$, $x_{kf}$ to cecha $f$ $k$-tego wektora, $m_j$ to zbiór wektorów zbioru treningowego należących do klasy $j$-tej, natomiast  $\gamma$ jest parametrem definiowanym przez użytkownika określającym szerokość funkcji Gaussa.

\paragraph{Prostokątne okna Parzena.} Miara LVDM w której $p( c_j | x_kf )$ wyznacza się stosując lokalną estymację na zasadzie częstości według zależności \reff{eq:LVDM}
\be
	 p( c_j | x_{kf} )=\frac{N(w^{x_{kf}} ,c_j)}{N(w^{x_{kf}})}
	\label{eq:LVDM}
\ee
gdzie $N(w^{x_{kf}} ,c_j)$ jest liczebnością wektorów z klasy $c_j$ znajdujących się w obszarze określonym parametrami $w^{x_{kf}} =[a-\sigma/2$, $a+\sigma/2]$ i $N(w^{x_{kf}})$ jest odpowiednio całkowitą liczbą wektorów w tym obszarze, a $\sigma$ to parametr określający szerokość okna.

\paragraph{Okna przesuwne.} Miara PVDM - gdzie do estymacji wartości prawdopodobieństwa $p( c_j | x_{kf} )$ budowany jest histogram o nakładających się przedziałach, a wartość prawdopodobieństwa wyznaczana jest jako średnia wszystkich przedziałów, które obejmują badany wektor \reff{eq:PVDM}. 
\be
	p( c_j | x_{kf} )=\frac{1}{z}\sum\limits_{i=1}^z \frac{N^i(x_{fk} ,c_j)}{N^i(x_{fk})}
	\label{eq:PVDM}
\ee 
gdzie $z$ jest liczbą wszystkich przedziałów zawierających badany wektor $x_{kf}$, natomiast $N^i(x_{fk} ,c_j)$ oraz $N^i(x_{fk})$ to odpowiednio wartości prawdopodobieństwa znajdujące się w $i$ tym przedziale. \\

\subsection{Wykorzystanie probabilistycznych miar odległości\\ do systemów reguł prototypowych} \label{sec:DistTransform}
Odległość heterogeniczne z rodziny VDM mają pewną istotną cechę - możliwe jest bowiem pokazanie, iż w rzeczywistości miary te polegają na mapowaniu wektorów danych dla każdej z cech niezależnie na $c-1$ wymiarową przestrzeń prawdopodobieństwa, gdzie następnie stosowana jest metryka Minkowskiego \reff{eq:TransfVDM2Lin}

\be \label{eq:TransfVDM2Lin}
%
\begin{array}{c}
D(\Bx,\Bp) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^c {\left( {p(c_j|x_i) - p(c_j|p_i)}\right)^q } } \\
\Downarrow \\
D(\Bx,\Bp) =\sum\limits_{k = 1}^{c\cdot n} {\left( {g(x_k) - g(p_k)}\right)^q } 
\end{array}
%
\ee
gdzie $g(\cdot)$ jest funkcją realizującą odwzorowanie zapisane zależnością
\be
 g(x_k)=\left\{{
\begin{array}{l}
p(c_{1\ldots c}|x_1)\\
p(c_{1\ldots c}|x_2)\\
p(c_{1\ldots c}|x_n)\\
\end{array}
}\right.
\ee
Jednak ze względu na liniową zależność atrybutów pochodzących z odwzorowania $p(c_{1\ldots c}|x_1)$ gdyż $\sum\limits_{j=1}^c p(c_j|x_1)=1$ wystarczające jest odwzorowanie pojedynczego atrybutu w postaci $c-1$ nowych atrybutów \cite{D-Duch-VDMinNN}. 


\subsection{Porównanie heterogenicznych miar odległości w zastosowaniu do reguł prototypowych} \label{sec:DistComp}
W celu sprawdzenia i porównania różnych miar odległości heterogenicznych dokonano weryfikacji opisanych miar  na realnych zbiorach danych. Testów porównawczych dokonano stosując 10-cio krotną walidację krzyżową, dla różnych zestawów parametrów metod estymacji i algorytmu klasyfikacji CFCM+LVQ opisanego w rozdziale \reff{sec:CFCM}. Wyniki porównania przedstawione w tabeli \reff{tab:DistComp}, zawierają najlepsze rezultaty uzyskane przez każdą z miar odległości oraz liczbę wybranych prototypów ($l$). Zbiory wykorzystane do testowania opisano w rozdziale \reff{chap:Dodatek}. 

%\begin{table}[htb]
%\scriptsize
%	\begin{tabular}{|l|c@{\hspace{5pt} }c|r@{ $\pm$ }l|c||r@{ $\pm$ }l|c||r@{ $\pm$ }l|c||r@{ $\pm$ }l|c|}
%\hline
%&&&\multicolumn{3}{c|}{Cleveland}&\multicolumn{3}{c|}{Ionosphere}&\multicolumn{3}{c|}{\begin{tabular}{c} Pima Indian\\ Diabetes\\ \end{tabular}}&\multicolumn{3}{c|}{WBC} \\ \hline
%&\multicolumn{2}{|c|}{Param.}&\multicolumn{2}{c|}{Dokładność}&l&\multicolumn{2}{c|}{Dokładność}&l&\multicolumn{2}{c|}{Dokładność}&l&\multicolumn{2}{c|}{Dokładność}&l\\ \hline
%HEOM&&&83.12&5.85&2&86.37&6.62&7&74.74&5.23&2&97.66&1.83&3 \\ 
%\hline	
%&\multicolumn{2}{|c|}{5}&82.80&6.50&7&90.38&6.05&5&75.78&4.56&2&97.81&1.83&3 \\ 
%DVDM&\multicolumn{2}{|c|}{7}&84.16&5.55&2&90.39&5.80&2&76.30&4.76&2&97.66&1.83&3 \\
%&\multicolumn{2}{|c|}{10}&84.50&5.78&2&90.70&7.38&5&75.39&4.77&2&97.51&1.67&3 \\ 
%\hline
%&\multicolumn{2}{|c|}{5}&83.14&6.20&2&91.25&7.13&5&75.78&6.16&2&97.66&1.69&3 \\
%IVDM&\multicolumn{2}{|c|}{7}&83.14&5.52&2&91.25&6.99&6&75.12&6.04&2&97.66&1.83&3 \\
%&\multicolumn{2}{|c|}{10}&83.14&6.60&3&90.42&7.51&4&74.73&5.58&2&97.81&1.83&4 \\
%\hline
%&\multicolumn{2}{|c|}{1}&\bf{84.81}&\bf{5.42}&6&88.41&6.81&6&73.84&4.88&6&97.66&1.69&6\\
%&\multicolumn{2}{|c|}{3}&\bf{84.81}&\bf{5.42}&6&89.82&5.49&6&74.88&6.69&6&97.66&1.69&6\\
%GVDM&\multicolumn{2}{|c|}{5}&84.48&5.39&6&90.93&5.31&6&74.10&5.99&6&97.66&1.69&6\\
%&\multicolumn{2}{|c|}{7}&84.48&5.62&6&90.40&5.09&6&75.01&5.85&6&97.37&1.48&6\\
%&\multicolumn{2}{|c|}{9}&83.80&6.21&6&91.21&5.03&6&74.35&5.11&6&97.66&1.69&6\\
%\hline
%&\multicolumn{2}{|c|}{0.2}&82.81&4.91&2&89.56&8.68&2&74.23&4.98&2&97.81&1.83&3 \\
%&\multicolumn{2}{|c|}{0.3}&84.49&5.86&2&90.40&7.87&3&74.23&4.38&2&97.81&1.83&3 \\
%LVDM&\multicolumn{2}{|c|}{0.4}&83.49&5.60&7&91.24&4.99&3&74.87&4.89&4&97.81&1.83&3 \\
%&\multicolumn{2}{|c|}{0.5}&82.82&6.01&6&91.51&4.32&2&73.96&4.03&2&97.81&1.83&3 \\
%&\multicolumn{2}{|c|}{0.6}&83.48&5.85&5&\bf{93.21}&\bf{4.62}&2&\bf{75.52}&\bf{3.97}&2&97.81&1.83&3\\
%\hline
%&0.2&0.01&83.48&6.10&3&90.15&8.18&3&74.87&5.48&3&97.81&1.83&3\\
%&0.2&0.05&83.49&6.48&3&89.85&6.41&3&74.48&5.79&3&97.81&1.83&3\\
%&0.2&0.09&83.14&6.20&3&89.01&6.43&3&75.14&6.42&3&97.81&1.83&3\\
%&0.3&0.01&83.82&6.36&3&90.96&6.70&3&75.13&5.32&3&97.66&1.83&3\\
%&0.3&0.05&83.14&6.20&3&90.14&6.30&3&75.66&4.65&3&97.81&1.83&3\\
%&0.3&0.09&83.12&6.07&3&88.38&5.34&3&75.79&4.24&3&97.81&1.83&3\\
%&0.4&0.01&83.48&5.41&3&91.50&5.91&3&74.87&4.73&3&97.81&1.83&3\\
%PVDM&0.4&0.05&82.47&6.74&3&91.53&5.09&3&75.01&4.76&3&97.81&1.83&3\\
%&0.4&0.09&83.83&6.29&3&87.84&5.33&3&75.92&5.12&3&97.81&1.83&3\\
%&0.5&0.01&84.85&5.99&3&91.50&4.60&3&75.66&4.99&3&97.81&1.83&3\\
%&0.5&0.05&83.83&6.29&3&91.82&5.32&3&74.88&4.52&3&97.81&1.83&3\\
%&0.5&0.09&83.83&6.29&3&89.00&7.10&3&74.75&5.95&3&97.81&1.83&3\\
%&0.6&0.01&83.81&5.94&3&90.93&5.24&3&75.27&5.19&3&97.81&1.83&3\\
%&0.6&0.05&84.14&4.60&3&91.25&6.80&3&75.27&4.91&3&97.81&1.83&3\\
%&0.6&0.09&83.48&6.26&3&90.96&5.88&3&73.44&5.24&3&97.81&1.83&3\\
%\hline
%	\end{tabular}
%	\label{tab:DistComp}
%\end{table}

\begin{table}[htb]
\begin{center}
\scriptsize
	\begin{tabular}{|l|r@{ $\pm$ }l|@{\hspace{2pt}}c@{\hspace{2pt}}|r@{ $\pm$ }l|@{\hspace{2pt}}c@{\hspace{2pt}}|r@{ $\pm$ }l|@{\hspace{2pt}}c@{\hspace{2pt}}|r@{ $\pm$ }l|@{\hspace{2pt}}c@{\hspace{2pt}}|}
\hline
&\multicolumn{3}{c|}{HVDM}&\multicolumn{3}{c|}{GVDM}&\multicolumn{3}{c|}{LVDM}&\multicolumn{3}{c|}{PVDM} \\ \hline
&\multicolumn{2}{c|@{\hspace{2pt}}}{Dokładność}&l&\multicolumn{2}{c|@{\hspace{2pt}}}{Dokładność}&l&\multicolumn{2}{c|@{\hspace{2pt}}}{Dokładność}&l&\multicolumn{2}{c|@{\hspace{2pt}}}{Dokładność}&l\\ \hline
Choroby serca&83.12&5.85&2&83.83&5.91&2&84.49&5.86&2&84.85&5.99&3\\
Jonosfera	 &86.37&6.62&7&91.21&5.03&2&93.21&4.62&2&91.82&5.32&3\\
Cukrzyca		 &74.74&5.23&2&74.88&5.62&2&75.52&3.97&2&75.79&4.24&3\\
Rak piersi	 &97.66&1.83&3&97.81&1.84&3&97.81&1.83&3&97.81&1.83&3\\
Wyrostek robaczkowy&86.61&13.32&2&85.79&11.39&2&86.79&10.23&2&86.79&10.23&2\\
Sonar			 &60.02&21.87&2&64.79&19.61&2&70.40&15.24&5&68.26&18.44&2\\
Choroby wątroby&59.42&6.49&6&59.98&5.40&2&59.93&7.71&2&65.52&8.33&2\\
Irysy			 &96.00&6.44&6&95.33&5.49&3&96.67&4.71&3&96.00&4.66&3\\
Winorośl		 &96.08&3.77&5&98.33&2.68&5&96.73&4.58&4&98.89&2.34&7\\
%Lancet		 &     &    & &92.19&4.30&4&92.19&4.30&4&92.19&4.30&4\\
%\hline
%Wartość średnia&\multicolumn{2}{c|@{\hspace{2pt}}}{82.44}&3.89&\multicolumn{2}{c|@{\hspace{2pt}}}{83.55}&2.56&\multicolumn{2}{c|@{\hspace{2pt}}}{84.61}&2.78&\multicolumn{2}{c|@{\hspace{2pt}}}{85.08}&3.11\\ 
\hline
	\end{tabular}
	\caption{Porównanie jakości klasyfikacji systemów reguł prototypowych typu \kNN z wykorzystaniem różnych probabilistycznych miar odległości.}
	\label{tab:DistComp}
\end{center}
\end{table}

Uzyskane rezultaty wskazują, iż zaproponowane miary heterogeniczne zwiększają dokładność klasyfikacji, co w znacznym stopniu uwydatnia się dla zbioru {\it jonosfera} oraz {\it sonar}. Ponadto dobór odpowiedniej metryki pozwala na redukcję liczby prototypów przy jednoczesnym wzroście dokładności klasyfikacji. Godnym zwrócenia uwagi jest fakt, iż miara PVDM wymagała doboru dwóch parametrów jednocześnie co znacznie zwiększyło złożoność obliczeniową tej metody, przy porównywalnych wynikach uzyskanych miarami GVDM oraz LVDM.\\
Przeprowadzona analiza wskazuje na dużą skuteczność zaproponowanych metryk. Ich wykorzystanie nie ogranicza się jedynie dla grupy metod reguł prototypowych, pozwalając na  jej użycie również wśród innych metod inteligencji obliczeniowej, w szczególności gdy nadrzędnym celem jest maksymalizacja dokładności klasyfikacji.

\section{Wnioski}
Analiza literaturowa wskazuje, iż dobór odpowiedniej metryki pozwala w znacznym stopniu na maksymalizację dokładności klasyfikacji oraz generalizacji budowanego modelu. Proces ten może być realizowany na podstawie wiedzy a'priori bądź też poprzez metody metauczenia, które pozwalają na jego automatyzację.\\
W praktyce stosowania miar heterogenicznych najczęściej spotykanym rozwiązaniem jest wykorzystanie metody omówionej w podrozdziale \ref{sec:DistTransform}, gdzie następuje odwzorowanie pojedynczego atrybutu w postaci $c-1$ cech. Należy tutaj zwrócić uwagę na pewne teoretyczne własności dwóch występujących tutaj podejść:
\begin{enumerate}
\item mapowanie do postaci prawdopodobieństwa jedynie cech symbolicznych i nominalnych (HEOM, HVDM)
\item mapowanie wszystkich cech do przestrzeni prawdopodobieństwa (miary DVDM, IVDM, GVDM, PVDM, LVDM)
\end{enumerate}
Pierwsze podejście najczęściej wykorzystuje metrykę Minkowskiego w nowej
rozszerzonej przestrzeni. Pojawia się jednak problem normalizacji lub ważenia atrybutów ciągłych nie poddanych transformacji, co powoduje niejednorodność różnych cech. W podejściu drugim omówiony problem nie występuje, gdyż wszystkie cechy znajdują się we wspólnej przestrzeni prawdopodobieństwa, co pozwala na
pominięcie problemu normalizacji. Jednakże wadą podejścia nr 2 jest konieczność
wyznaczenia optymalnych parametrów estymacji, co jest równie istotnym problemem jak
wyznaczanie wag. Obydwie te metody wydają się być więc równoważne.\\
Pewną korzyścią wynikającą z transformacji wartości atrybutów ciągłych do postaci prawdopodobieństwa w przypadku systemów reguł prototypowych jest możliwość redukcji liczby prototypów. Przykładowo, sytuacja taka może zajść, jeżeli rozkład wartości atrybutu $f$ przyjmuje postać jak na rys.\reff{fi:ProbDistTransf1}  
\bfig
	\epsfig{figure=pic/HDcomp1,width=9cm,height=6cm}
	\caption{Rozkład prawdopodobieństwa oraz wykres wartości atrybutu $f$ dla problemu klasyfikacji dwóch klas}
	\label{fi:ProbDistTransf1}
\efig
wówczas do poprawnej klasyfikacji takiego zagadnienia niezbędne są trzy prototypy. Po transformacji do postaci prawdopodobieństwa nowa cecha przyjmuje postać jak na rys.\reff{fi:ProbDistTransf2}. Dzięki temu możliwa jest redukcja złożoności modelu z trzech do dwóch prototypów przy zachowaniu podobnej dokładności klasyfikacji.
\bfig
	\epsfig{figure=pic/HDcomp2,width=9cm,height=6cm}
	\caption{Rozkład prawdopodobieństwa atrybutu $f$ po transformacji z wykorzystaniem odległości probabilistycznych}
	\label{fi:ProbDistTransf2}
\efig
Transformacja do wspólnej przestrzeni prawdopodobieństwa ma jednak pewne wady. Mianowicie odwzorowanie odwrotne - położenia prototypów z wartości prawdopodobieństwa do wartości wejściowej jest niejednoznaczne, gdyż możliwe jest znalezienie wiele różnych wektorów o równej wartości funkcji prawdopodobieństwa. Problem ten szczegónie dotyczy atrybutów ciągłych. 
Dlatego też spojrzenie na omówiony problem z perspektywy łatwości interpretacji uzyskanych wyników prowadzi do wniosku, iż w praktyce wykorzystanie odległości heterogenicznych typu HEOM lub HVDM ułatwia analizę uzyskanych wyników. Natomiast zaproponowane miary realizujące mapowanie atrybutów ciągłych (IVDM,DVDM,GVDM,LVDM,PVDM) powinny być używane bądź ze względu na dokładność wyników (możliwa poprawa dokładności klasyfikacji), bądź też gdy informacje o rozkładzie prawdopodobieństwa atrybutów są wystarczającym źródłem informacji, pozwalającym na interpretację wyników. 
%--------------------END Similarity and dissimilarity metrics----------------------------------
