Sztuczna inteligencja/SI Moduł 10 - Zadanie i metody klasyfikacji

Zadanie klasyfikacji

Zadanie klasyfikacji jest szczególnym wariantem ogólnego zadania aproksymacji, w którym wartości aproksymowanego odwzorowania $\phi :O\rightarrow V\,$ należą do skończonego zbioru kategorii (klas) $V\,$. Odwzorowanie tego typu bywa w tradycyjnej terminologii maszynowego uczenia się nazywane pojęciem. Pojęcie reprezentuje wiedzę na temat podziału rozważanej dziedziny na pewne z góry określone klasy obiektów. Tak jak w ogólnym zadaniu aproksymacji, zakładamy, że wartości aproksymowanej funkcji (czyli kategorie pojęcia) znane są wyłącznie dla pewnego fragmentu dziedziny $T\in O\,$ i na podstawie znanych przykładów należy zbudować hipotezę (model klasyfikacji), która z możliwie niewielkim błędem będzie w stanie klasyfikować dowolne elementy dziedziny.

Możliwości stosowania zadania klasyfikacji są bardzo szerokie. Możemy mieć do czynienia np. z klasyfikacją klientów sieci handlowej na lojalnych i nielojalnych, klasyfikacją transakcji dokonywanych kartami płatniczymi na uczciwe i nieuczciwe, klasyfikacją pacjentów placówki medycznej do różnych jednostek chorobowych, klasyfikacją wyników obserwacji, pomiarów i odczytów czujników opisujących stan urządzenia technicznego do kategorii reprezentujących różne typy awarii, klasyfikacją dokumentów tekstowych (takich jak strony WWW) do różnych kategorii tematycznych itd. Uczenie się klasyfikacji i następnie automatyczne stosowanie zbudowanego na podstawie danych trenujących modelu jest szczególnie uzasadnione, jeśli:

• wyznaczenie właściwej kategorii może być dokonane przez człowieka, ale byłoby wówczas zbyt czasochłonne i kosztowne i dlatego ogranicza się je tylko do przypisania kategorii przykładom trenującym (np. klasyfikacja tekstu do kategorii tematycznych, klasyfikacja pacjentów do kategorii jednostek chorobowych - człowiek może korzystając ze swojej wiedzy wyznaczyć właściwą kategorię),
• właściwa kategoria będzie znana dopiero z pewnym opóźnieniem, a model jest potrzebny do jej wczesnej predykcji, w związku z czym jako przykładów trenujących można użyć danych historycznych o znanych już kategoriach (np. klasyfikacja transakcji kartami płatniczymi - po pewnym czasie wiadomo, które transakcje zostały zakwestionowane przez posiadacza karty i uznane za nieuczciwe).

Przedstawiając metody uczenia się klasyfikacji najwięcej uwagi poświęcimy szeroko znanej i bardzo często wykorzystywanej w praktycznych zastosowaniach indukcji drzew decyzyjnych. Ponadto zostaną zwięźle scharakteryzowane proste metody naiwnej klasyfikacji bayesowskiej i klasyfikacji pamięciowej.

Drzewo decyzyjne jako model klasyfikacji

Przez drzewo decyzyjne rozumiemy strukturę, która ma zwykłe właściwości drzewa w znaczeniu, jaki temu słowu nadaje się w informatyce, jest więc strukturą złożoną z węzłów, z których wychodzą gałęzie prowadzące do innych węzłów lub liści, oraz z liści, z których nie wychodzą żadne gałęzie. Węzły odpowiadają testom przeprowadzanym na wartościach atrybutów przykładów, gałęzie odpowiadają możliwym wynikom tych testów, liście zaś etykietom kategorii.

Testy

Test jest w ogólnym przypadku dowolną funkcją określoną na dziedzinie $t:O\mapsto R_{t}\,$, przy czym w praktyce rozważamy testy, które są funkcyjnie zależne od atrybutów. Najczęściej przyjmuje się ograniczenie, że wynik testu może zależeć od wartości dokładnie jednego atrybutu i tylko taki przypadek będzie tu rozważany. Test reprezentuje podział zbioru przykładów rozważanego w węźle drzewa decyzyjnego na podzbiory odpowiadające wynikom testu. Zależnie od typów atrybutów mogą być używane różne rodzaje testów, z których najważniejsze omówione są poniżej (podane nazewnictwo nie jest powszechnie przyjęte) dla atrybutu $a:O\mapsto A\,$.

Testy tożsamościowe: test utożsamiany jest z atrybutem, $t(o)\equiv a(o)\,$ (dla atrybutów nominalnych lub porządkowych).

Testy równościowe: test sprawdzający równość dla wartości atrybutu (dla atrybutów nominalnych lub porządkowych):

$t(o)={\begin{cases}1&{\textit {jesli\ }}a(o)=b\\0&{\textit {jesli\ }}a(o)\neq b\end{cases}}\,$

(1)

gdzie $b\in A\,$.

Testy przynależnościowe: test sprawdzający przynależność do zbioru dla wartości atrybutu (dla dowolnych typów atrybutów):

$t(o)={\begin{cases}1&{\textit {jesli\ }}a(o)\in B\\0&{\textit {jesli\ }}a(o)\not \in B\end{cases}}\,$

(2)

gdzie $B\subset A\,$.

Testy podziałowe: test sprawdzający przynależność do podzbiorów powstałych przez podział przeciwdziedziny atrybutu (dla dowolnych typów atrybutów):

$t(o)={\begin{cases}1&{\textit {jesli\ }}a(o)\in B_{0}\\2&{\textit {jesli\ }}a(o)\in B_{1}\\\dots \\m&{\textit {jesli\ }}a(o)\in B_{m}\\\end{cases}}\,$

(3)

gdzie parami rozłączne zbiory $B_{1},B_{2},\dots ,B_{m}\,$ stanowią wyczerpujący podział przeciwdziedziny atrybutu $A\,$.

Testy nierównościowe: test sprawdzający nierówność dla wartości atrybutu (dla atrybutów porządkowych i ciągłych):

$t(o)={\begin{cases}1&{\textit {jesli\ }}a(o)\leq \theta \\0&{\textit {jesli\ }}a(o)>\theta \end{cases}}\,$

(4)

gdzie $\theta \in A\,$.

Dla testu $t\,$ i zbioru przykładów $P\,$ będziemy stosować oznaczenia:

$P_{tr}=\{o\in P\;|\;t(o)=r\},\,$
$P_{tr}^{v}=\{o\in P\;|\;\phi (o)=v\land t(o)=r\}.\,$

Klasyfikacja za pomocą drzewa

Klasyfikacja przykładu za pomocą drzewa decyzyjnego polega na przejściu ścieżki od korzenia do liścia drzewa wzdłuż gałęzi wyznaczanych przez wyniki stosowania do tego przykładu testów związanych z odwiedzanymi kolejno węzłami. Osiągnięcie liścia wyznacza kategorię. W ten sposób drzewo decyzyjne umożliwia zaklasyfikowanie dowolnego przykładu, a więc reprezentuje hipotezę.

Przykład drzewa decyzyjnego. Rozważmy następujący zbiór danych:

$o\,$	aura	temperatura	wilgotność	wiatr	$\phi (o)\,$
$1\,$	słoneczna	ciepła	duża	słaby	$0\,$
$2\,$	słoneczna	ciepła	duża	silny	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 0 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 3 \,}	pochmurna	ciepła	duża	słaby	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 4 \,}	deszczowa	umiarkowana	duża	słaby	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 5 \,}	deszczowa	zimna	normalna	słaby	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 6 \,}	deszczowa	zimna	normalna	silny	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 0 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 7 \,}	pochmurna	zimna	normalna	silny	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 8 \,}	słoneczna	umiarkowana	duża	słaby	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 0 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 9 \,}	słoneczna	zimna	normalna	słaby	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 10 \,}	deszczowa	umiarkowana	normalna	słaby	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 11 \,}	słoneczna	umiarkowana	normalna	silny	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 12 \,}	pochmurna	umiarkowana	duża	silny	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 13 \,}	pochmurna	ciepła	normalna	słaby	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1 \,}
Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 14 \,}	deszczowa	umiarkowana	duża	silny	Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 0 \,}

Łatwo sprawdzić, że poniżej przedstawione drzewo decyzyjne klasyfikuje poprawnie wszystkie przykłady z tego zbioru. Przy poszczególnych węzłach i liściach podano odpowiadające im podzbiory przykładów.

Drzewo to możemy również zapisać w następującej postaci tekstowej:

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \textit{aura}=\textit{sloneczna}: \,} ${\textit {wilgotnosc}}={\textit {normalna}}:\,$ $1\,$ ${\textit {wilgotnosc}}={\textit {duza}}:\,$ $0\,$ ${\textit {aura}}={\textit {pochmurna}}:\,$ $1\,$ ${\textit {aura}}={\textit {deszczowa}}:\,$ ${\textit {wiatr}}={\textit {slaby}}:\,$ $1\,$ ${\textit {wiatr}}={\textit {silny}}:\,$ $0\,$

W takim zapisie struktura drzewa jest uwidoczniona za pomocą wcięć poszczególnych wierszy.

Zstępująca budowa drzewa

Popularne algorytmy indukcji drzew decyzyjnych wykorzystują schemat zstępującej budowy drzewa. Zgodnie z nim tworzenie drzewa rozpoczyna się od umieszczenia pierwszego węzła (jeśli podział zbioru przykładów będzie uznany za potrzebny) bądź liścia (jeśli podział zbioru przykładów będzie uznany za zbędny) w korzeniu. W przypadku umieszczenia w korzeniu węzła na podstawie przykładów trenujących należy wybrać test dla tego węzła i odpowiednio podzielić zbiór przykładów na podzbiory zgodnie z wynikami tego testu. Każdemu wynikowi odpowiada gałąź prowadząca do poddrzewa, które należy obecnie utworzyć na podstawie odpowiadającego mu podzbioru przykładów. Ten zstępujący proces zatrzymuje się, gdy której z tworzonych poddrzew stanie się liściem.

Ze względu na rekurencyjny charakter struktury drzewiastej (każde poddrzewo jest drzewem) szczególnie wygodnie jest taki schemat formułować rekurencyjnie, np. tak w postaci przedstawionej poniżej. W zapisanej procedurze rekurencyjnej dla wygody używane są następujące notacyjne skróty:

• $v_{l}\,$ - kategoria umieszczona w liściu $l\,$,
• $t_{n}\,$ - test umieszczony w węźle $n\,$,
• $n[r]\,$ - poddrzewo, do którego z węzła $n\,$ prowadzi krawędź odpowiadająca wynikowi $r\,$ umieszczonego w nim testu.

Przy pierwszym wywołaniu jako zbiór przykładów $P\,$ przekazywany jest cały zbiór trenujący $T\,$.

${\textit {buduj-drzewo}}(P,v,S)\,$

• $P\,$ - zbiór przykładów etykietowanych pojęcia $c\,$,
• $v\,$ - domyślna etykieta kategorii,
• $S\,$ - zbiór możliwych testów;

zwraca drzewo decyzyjne reprezentujące hipotezę przybliżającą $c\,$ na zbiorze $P\,$;

1. jeśli ${\textit {kryterium-stopu}}(P,S)\,$
   1. utwórz liść $l\,$;
   2. $v_{l}:={\textit {kategoria}}(P,v)\,$;
   3. zwróć $l\,$;
2. utwórz węzeł $n\,$;
3. $t_{n}:={\textit {wybierz-test}}(P,S)\,$;
4. $v:={\textit {kategoria}}(P,v)\,$;
5. dla każdego $r\in R_{t_{n}}\,$
   • $n[r]:={\textit {buduj-drzewo}}(P_{t_{n}r},v,S-\{t_{n}\})\,$;
6. zwróć $n\,$.

Kryterium stopu

Kryterium stopu określa, kiedy ma być zatrzymany proces rozrostu drzewa, czyli kiedy dla pewnego zbioru przykładów nie powstanie kolejny węzeł wewnętrzny, lecz liść. Oczywiste sytuacje, kiedy powinno się tak stać, są następujące:

• aktualny zbiór przykładów $P\,$ jest pusty,
• wszystkie przykłady ze zbioru $P\,$ należą do tej samej kategorii pojęcia $c\,$,
• zbiór możliwych do użycia testów $S\,$ jest pusty.

Najpóźniej po spełnieniu któregoś z tych warunków dalszy rozrost drzewa musi zostać zatrzymany. Powstałe wówczas drzewo będzie spójne z danymi trenującymi, o ile nie są one sprzeczne i zbiór testów jest wystarczający. W praktyce rozrost drzewa może być zatrzymywany wcześniej i będą wówczas otrzymane drzewa niespójne z danymi trenującymi, które jednak mogą być preferowane ze względu na większą prostotę i możliwość uniknięcia nadmiernego dopasowania.

Wybór testu

Przy wyborze testu należy się kierować rozsądnym postulatem, aby zbudować możliwie jak najprostsze drzewo. Zwiększa to jego czytelność dla człowieka i zmniejsza ryzyko nadmiernego dopasowania. Dążenie do prostoty sprowadza się do dążenia do tego, aby kolejno wybierane testy jak najbardziej przybliżały moment, kiedy będzie można utworzyć liść, czyli aby w węzłach potomnych coraz dokładniej można było określić kategorię. Jedną z przesłanek do stwierdzenia szybkiej możliwości utworzenia liścia jest wykrycie znaczniej nierównomierności rozkładu kategorii.

Najbardziej popularne jest wykorzystanie entropii do pomiaru nierównomierności rozkładu kategorii. Oparta na niej funkcja oceny testu, nazywana przyrostem informacji, jest obliczana następująco:

$g_{t}(P)=I(P)-E_{t}(P),\,$

(5)

gdzie

$I(P)=\,$	$\sum _{v\in V}-{\frac {|P^{v}|}{|P|}}\log {\frac {|P^{v}|}{|P|}},\,$
$E_{t}(P)=\,$	$\sum _{r\in R_{t}}{\frac {|P_{tr}|}{|P|}}E_{tr}(P),\,$
$E_{tr}(P)=\,$	$\sum _{v\in V}-{\frac {|P_{tr}^{v}|}{|P_{tr}|}}\log {\frac {|P_{tr}^{v}|}{|P_{tr}|}}.\,$

Preferowane są testy maksymalizujące przyrost informacji, co jest równoznaczne z minimalizacją entropii.

Zbiór kandydujących do wyboru testów zazwyczaj zawiera wszystkie możliwe do określenia testy dla wykorzystywanych do opisu przykładów atrybutów pewnych z góry przyjętych rodzajów. Często są to np. testy tożsamościowe dla atrybutów nominalnych i nierównościowe dla porządkowych i ciągłych, albo testy przynależnościowe lub podziałowe dla wszystkich typów atrybutów. W przypadku atrybutów ciągłych liczba testów, jakie należy rozważyć, jest duża i może decydować o koszcie obliczeniowym algorytmu. Konieczne są wówczas pewne heurystyki eliminujące najmniej obiecujące testy oraz odpowiednio staranna implementacja.

Przykład wyboru testu. Wyznaczymy wartość przyrostu informacji dla testu tożsamościowego na wartościach atrybutu ${\textit {aura}}\,$ z podane w poprzednim przykładzie zbioru danych. Do jego obliczenia są potrzebne liczności następujących zbiorów:

$|T^{1}|=\,$	$|\{3,4,5,7,9,10,11,12,13\}|=9,\,$
$|T^{0}|=\,$	$|\{1,2,6,8,14\}|=5,\,$
$|T_{{\textit {aura}},{\textit {sloneczna}}}|=\,$	$|\{1,2,8,9,11\}|=5,\,$
$|T_{{\textit {aura}},{\textit {sloneczna}}}^{1}|=\,$	$|\{9,11\}|=2,\,$
$|T_{{\textit {aura}},{\textit {sloneczna}}}^{0}|=\,$	$|\{1,2,8\}|=3,\,$
$|T_{{\textit {aura}},{\textit {pochmurna}}}|=\,$	$|\{3,7,12,13\}|=4,\,$
$|T_{{\textit {aura}},{\textit {pochmurna}}}^{1}|=\,$	$|\{3,7,12,13\}|=4,\,$
$|T_{{\textit {aura}},{\textit {pochmurna}}}^{0}|=\,$	$|\emptyset |=0,\,$
$|T_{{\textit {aura}},{\textit {deszczowa}}}|=\,$	$|\{4,5,6,10,14\}|=5,\,$
$|T_{{\textit {aura}},{\textit {deszczowa}}}^{1}|=\,$	$|\{4,5,10\}|=3,\,$
$|T_{{\textit {aura}},{\textit {deszczowa}}}^{0}|=\,$	$|\{6,14\}|=2.\,$

Przyjmując logarytmy dwójkowe można obecnie obliczyć, z dokładnością do trzech miejsc po przecinku:

$E_{{\textit {aura}},{\textit {sloneczna}}}(P)=\,$	$-{\frac {2}{5}}\log _{2}{\frac {2}{5}}-{\frac {3}{5}}\log _{2}{\frac {3}{5}}=0.971,\,$
$E_{{\textit {aura}},{\textit {pochmurna}}}(P)=\,$	$-{\frac {4}{4}}\log _{2}{\frac {4}{4}}-{\frac {0}{4}}\log _{2}{\frac {0}{4}}=0,\,$
$E_{{\textit {aura}},{\textit {deszczowa}}}(P)=\,$	$-{\frac {3}{5}}\log _{2}{\frac {3}{5}}-{\frac {2}{5}}\log _{2}{\frac {2}{5}}=0.971.\,$

Umożliwia to wyznaczenie ważonej entropii:

$E_{\textit {aura}}(T)={\frac {5}{14}}\cdot 0.971+{\frac {4}{14}}\cdot 0+{\frac {5}{14}}\cdot 0.971=0.694.\,$

Do porównywania testów ze względu na kryterium przyrostu informacji wystarcza wyznaczenie dla nich entropii. Dla kompletności przykładu obliczymy jednak przyrost informacji dla atrybutu ${\textit {aura}}\,$. Mamy:

$I(T)=-{\frac {9}{14}}\log _{2}{\frac {9}{14}}-{\frac {5}{14}}\log _{2}{\frac {5}{14}}=0.940.\,$

Wobec tego

$g_{\textit {aura}}(T)=0.940-0.694=0.246.\,$

Testy nierównościowe

Zauważmy, że dla testów nierównościowych jako progi nierówności wystarczy brać pod uwagę tylko po jednej wartości (np. środkowej) pomiędzy każdymi dwoma sąsiednimi wartościami atrybutu występującymi w aktualnym zbiorze przykładów. W związku z tym dla wygody dokonuje się sortowania wartości atrybutu. Możliwość dalszego usprawnienia oceny testów nierównościowych kryje się w następującej właściwości. Można wykazać, że jeśli dla dwóch kolejnych (po posortowaniu) wartości $b_{1}\,$ i $b_{2}\,$ atrybutu ciągłego lub porządkowego $a\,$ wszystkie przykłady w zbiorze $P\,$ mają tę samą kategorię, to na pewno optymalna wartość progowa $\theta \,$ nie znajduje się między $b_{1}\,$ i $b_{2}\,$ i w związku z tym obliczanie jakości testów dla takich wartości $\theta \,$ można bezpiecznie pominąć. Intuicyjne uzasadnienie tego faktu jest prostsze od ścisłego dowodu i zadowolimy się nim. Otóż jeśli dla każdego przykładu $o\in P\,$, dla którego $b_{1}\leq a(o)\leq b_{2}\,$, mamy $\phi (o)=v\,$, to w przypadku wyboru wartości progowej $b_{1}\leq \theta <b_{2}\,$ uzyskamy podział zbioru $P\,$ na dwa podzbiory, w których te przykłady o kategorii $v\,$ będą rozdzielone (część z nich znajdzie się w jednym, a część w drugim podzbiorze). Oznacza to, że w podzbiorach tych będzie bardziej równomierny rozkład kategorii, niż gdyby wszystkie przykłady, o których mowa, znalazły się w tym samym podzbiorze, a tym samym nasz wybór wartości progowej $\theta \,$ nie jest najlepszy z możliwych.

Testy przynależnościowe

Ze względu na wykładniczo rosnącą liczbę możliwych podzbiorów przeciwdziedziny atrybutu również najlepszego testu przynależnościowego jest złożony obliczeniowo. Prosta heurystyka może polegać na tym, aby na początek rozważać wyłącznie podzbiory jednoelementowe i poddać ocenie oparte na nich testy przynależnościowe, następnie do najlepszego (lub kilku najlepszych) podzbioru dodać każdy możliwy drugi element i znów wybrać najlepszy podzbiór dwuelementowy, itd., tak długo jak długo ocena najlepszego uzyskanego dotąd testu będzie się poprawiać.

Testy podziałowe

Problem wyboru najlepszego testu podziałowego dla atrybutów o skończonej liczbie wartości jest problemem optymalnego podziału zbioru na podzbiory. Prosta heurystyka może polegać na rozpoczęciu od podzbiorów jednoelementowych i następnie w każdym kroku wyborze do połączenia dwóch takich podzbiorów, w których rozkład kategorii jest najbardziej zbliżony. Do mierzenia różnicy między rozkładami można np. wykorzystać statystykę $\chi ^{2}\,$. W tym celu rozważamy faktyczny rozkład kategorii w obu podzbiorach oraz rozkład oczekiwany określony na podstawie podzbioru będącego ich połączeniem.

Wybór kategorii

Wybór kategorii dla tworzonego liścia jest oczywisty: powinna to być kategoria większości przykładów w aktualnym zbiorze $P\,$, a gdyby ten zbiór był pusty, kategoria domyślna. Na pierwszym poziomie drzewa jest ona określana przez argument procedury budującej drzewo, a na niższych poziomach - jako większościowa kategoria w zbiorze przykładów związanym z węzłem macierzystym.

Przycinanie drzewa

Ze względu na dążenie do prostoty i uniknięcia nadmiernego dopasowania w praktyce najczęściej konieczne jest przycinanie drzew. Polega ono w podstawowej wersji na zastępowaniu wybranych węzłów (a tym samym całych poddrzew) liśćmi, którym przypisuje się kategorię większości przykładów trenujących, które w trakcie budowy drzewa były związane z eliminowanym węzłem. Zazwyczaj przycinanie realizowane jest w sposób wstępujący, tzn. w pierwszej kolejności rozważa się przycięcie węzłów położonych najniżej w drzewie. Podstawowe znaczenie ma kryterium przycinania, które decyduje, czy węzeł będzie zastąpiony liściem.

Prostym i pod wieloma względami najbardziej godnym polecenia kryterium przycinania jest błąd na oddzielnym zbiorze przykładów (niezależnym od zbioru trenującego). Przycięcie następuje, jeśli na tym oddzielnym zbiorze liść uzyskuje błąd nie większy, niż błąd poddrzewa. Jeśli ze względu na deficyt przykładów nie można pozostawić części z nich na potrzeby przycinania, powstaje konieczność formułowania kryteriów przycinania opartych wyłącznie na danych trenujących. Stosowane są wówczas m.in. różne techniki pesymistycznego szacowania błędu poddrzewa na zbiorze trenującym.

Indukcja drzew decyzyjnych jako przeszukiwanie

Indukcję drzew decyzyjnych można traktować jako proces przeszukiwania w przestrzeni wszystkich drzew decyzyjnych dla danej dziedziny, spełniających pewne ograniczenia (takie jak zestaw dostępnych do użycia testów). Przemieszczanie się po przestrzeni drzew decyzyjnych może następować za pomocą różnego rodzaju operatorów, lecz wystarczy rozważyć dwa podstawowe ich rodzaje: zastąpienie liścia węzłem i zastąpienie węzła liściem. Proces zstępującej budowy drzewa opisany wyżej można sformułować jako sekwencyjne stosowanie pierwszego operatora (przy założeniu, że początkowe drzewo składa się z jednego liścia, a po utworzeniu każdego nowego węzła jego „potomkowie” są początkowo liścmi), zaś proces przycinania - jako sekwencyjne stosowanie drugiego operatora. Za wybór węzłów lub liści, do których w kolejnych krokach stosowane są operatory, odpowiedzialna jest strategia przeszukiwania. W ten sposób na algorytmy budowy i przycinania drzew decyzyjnych można patrzeć jak na pewne strategie przeszukiwania przestrzeni drzew decyzyjnych.

Reguły klasyfikacji

Poza drzewami decyzyjnymi popularną i czytelną dla człowieka reprezentację modeli klasyfikacji stanowią zbiory reguł. Do ich indukcji na podstawie przykładów trenujących opracowano szereg specjalizowanych algorytmów, chociaż nie są one tak szeroko stosowane, jak algorytmy indukcji drzew decyzyjnych. Niezależnie od tego warto zauważyć, że drzewo decyzyjne może być łatwo przekształcone do reprezentacji regułowej.

Nieformalnie możemy określić regułę klasyfikacji jako wyrażenie postaci:

JEŚLI warunki TO kategoria,

krócej zapisywanego jako

${\textit {warunki}}\rightarrow {\textit {kategoria}}.\,$

(6)

Reguła wyznacza kategorię przykładów, których wartości atrybutów spełniają podane warunki, na ogół stanowiące koniunkcję pewnych warunków elementarnych.

Rozważmy dowolne drzewo decyzyjne i pewną ścieżkę w tym drzewie, łączącą korzeń z liściem zawierającym etykietę $v\in V\,$. Załóżmy, że na tej ścieżce kolejno występują testy $t_{1},t_{2},\dots ,t_{m}\,$, a odpowiednie gałęzie odpowiadają wynikom tych testów $r_{1}\in R_{t_{1}},r_{2}\in R_{t_{2}},\dots ,r_{m}\in R_{t_{m}}\,$. Wówczas taka ścieżka jest równoważna z następującą regułą:

$t_{1}(o)=r_{1}\land t_{2}(o)=r_{2}\land \dots \land t_{m}(o)=r_{m}\rightarrow d.\,$

(7)

Ponieważ dla każdego liścia drzewa decyzyjnego można wskazać ścieżkę łączącą ten liść z korzeniem, więc określony w ten sposób zbiór ścieżek drzewa może być przekształcony w odpowiedni zbiór reguł, klasyfikujących wszystkie przykłady dziedziny w identyczny sposób jak to drzewo. To pozwala stwierdzić, że konwersja drzewa decyzyjnego do zbioru reguł jest zawsze możliwa, chociaż niekoniecznie celowa ze względu na pamięciową oszczędność reprezentacji lub jej czytelność. Najczęściej konwersję taką wykorzystuje się do przycinania, czyli zapobiegania nadmiernemu dopasowaniu. O ile bezpośrednie przycinanie drzewa umożliwia wyłącznie eliminację poddrzew, które okazują się „nieopłacalne”, przycinanie reguł pozwala na eliminację dowolnego warunku z koniunkcji stanowiącej lewą stronę każdej reguły. Daje to większą elastyczność w poszukiwaniu ostatecznej postaci modelu, a tym samym może sprzyjać poprawie jego jakości.

Przykład konwersji drzewa do zbioru reguł. Dla przedstawionego wcześniej drzewa decyzyjnego klasyfikującego stany pogody można podać następujący równoważny zbiór reguł:

${\textit {aura}}(o)={\textit {sloneczna}}\land {\textit {wilgotnosc}}(o)={\textit {duza}}\rightarrow \,$	$0,\,$
${\textit {aura}}(o)={\textit {sloneczna}}\land {\textit {wilgotnosc}}(o)={\textit {normalna}}\rightarrow \,$	$1,\,$
${\textit {aura}}(o)={\textit {pochmurna}}\rightarrow \,$	$1,\,$
${\textit {aura}}(o)={\textit {deszczowa}}\land {\textit {wiatr}}(o)={\textit {silny}}\rightarrow \,$	$0,\,$
${\textit {aura}}(o)={\textit {deszczowa}}\land {\textit {wiatr}}(o)={\textit {slaby}}\rightarrow \,$	$1.\,$

Naiwny klasyfikator bayesowski

Prostym, lecz w niektórych zastosowaniach bardzo użytecznym algorytmem uczenia się klasyfikacji, jest naiwny klasyfikator bayesowski. W tym przypadku zamiast symbolicznej reprezentacji wiedzy o zależnościach między kategoriami a wartościami atrybutów wykorzystywane są prawdopodobieństwa warunkowe.

Szacowanie prawdopodobieństw

Naiwny klasyfikator bayesowski zakłada, tak jak wcześniej poznane przez nas algorytmy indukcji, że przykłady są opisane za pomocą pewnego zestawu atrybutów $a_{1},a_{2},\dots ,a_{n}\,$, przy czym ograniczamy się do atrybutów o wartościach dyskretnych (nominalnych lub porządkowych). Na podstawie zbioru trenującego $T\,$ są szacowane prawdopodobieństwa poszczególnych kategorii pojęcia docelowego $c\,$ oraz prawdopodobieństwa poszczególnych wartości wszystkich atrybutów dla przykładów różnych kategorii. Interesujące nas oszacowania dotyczą prawdopodobieństw $\mathrm {Pr} (\phi (o)=v)\,$ dla wszystkich kategorii $v\in V\,$ pojęcia docelowego $c\,$ oraz $\mathrm {Pr} {\big (}a_{i}(o)=b\,|\,\phi (o)=v{\big )}\,$ dla wszystkich kategorii $v\in V\,$ oraz wartości $b\in A_{i}\,$ dla $i=1,2,\dots ,n\,$, przy czym $A_{i}\,$ jest przeciwdziedziną atrybutu $a_{i}\,$. Prawdopodobieństwa te szacuje się na podstawie częstości występowania w zbiorze trenującym przykładów o odpowiednich kategoriach i wartościach atrybutów. Należy przy tym zapobiec występowaniu prawdopodobieństw równych $0\,$ w sytuacji, gdy w zbiorze $T\,$ nie ma żadnego przykładu spełniającego określone warunku. Najprostszą techniką jest zastępowanie ich pewną niewielką, lecz dodatnią wartością $\epsilon \,$ (mniejszą niż prawdopodobieństwo, jakie otrzymalibyśmy, gdyby znalazł się $1\,$ taki przykład).

Klasyfikowanie przykładów

Załóżmy, że dany jest pewien przykład $o_{*}\in O\,$ i należy, przy dostępnych oszacowaniach prawdopodobieństw $\mathrm {Pr} (\phi (o)=v)\,$ dla wszystkich $v\in V\,$ oraz $\mathrm {Pr} {\big (}a_{i}(o)=b\,|\,\phi (o)=v{\big )}\,$ dla $i=1,2,\dots ,n\,$, wszystkich $b\in A_{i}\,$ i $v\in V\,$, wyznaczyć kategorię tego przykładu. Naiwny klasyfikator bayesowski wybiera wówczas kategorię najbardziej prawdopodobną, przy czym chodzi o wybór kategorii najbardziej prawdopodobnej dla przykładu o znanych wartościach atrybutów. Definicję modelu $g\,$ możemy zapisać następująco:

$g(o_{*})=\mathrm {arg} \max _{v\in V}\mathrm {Pr} {\big (}\phi (o)=v\,|\,a_{1}(o)=a_{1}(o_{*})\land a_{2}(o)=a_{2}(o_{*})\land \dots \land a_{n}(o)=a_{n}(o_{*}){\big )},\,$

(8)

lub krócej

$g(o_{*})=\mathrm {arg} \max _{v\in V}\mathrm {Pr} {\Big (}\phi (o)=v\,{\big |}\,\bigwedge _{i=1}^{n}a_{i}(o)=a_{i}(o_{*}){\Big )},\,$

(9)

przy czym symbol $\bigwedge \,$ służy do zwartego zapisu koniunkcji $n\,$ równości. Oznacza to wybór dla przykładu $o_{*}\,$ kategorii najbardziej prawdopodobnej dla dowolnego przykładu wybranego z dziedziny $O\,$, który jest opisany przez wektor wartości atrybutów $\langle a_{1}(o_{*}),a_{2}(o_{*}),\dots ,a_{n}(o_{*})\rangle \,$. Występujące w powyższym równaniu prawdopodobieństwo można z kolei korzystając ze wzoru Bayesa przekształcić do postaci:

${\frac {\mathrm {Pr} (\phi (o)=v)\cdot \mathrm {Pr} {\Big (}\bigwedge _{i=1}^{n}a_{i}(o)=a_{i}(o_{*})\,{\big |}\,\phi (o)=v{\Big )}}{\mathrm {Pr} {\Big (}\bigwedge _{i=1}^{n}a_{i}(o)=a_{i}(o_{*}){\Big )}}},\,$

(10)

przy czym w dalszym ciągu możemy się zajmować wyłącznie licznikiem tego ułamka, gdyż mianownik, który nie zależy od kategorii, nie wpływa na maksymalizację prawdopodobieństwa dla $v\in V\,$.

Ponieważ wartości $\mathrm {Pr} (\phi (o)=v)\,$ znamy, pozostaje określić sposób obliczania prawdopodobieństw postaci

$\mathrm {Pr} {\Big (}\bigwedge _{i=1}^{n}a_{i}(o)=b_{i}\,{\big |}\,\phi (o)=v{\Big )}\,$

(11)

dla dowolnych $b_{i}\in A_{i}\,$, $i=1,2,\dots ,n\,$, i $v\in V\,$. Naiwny klasyfikator bayesowski zakłada, że wartości poszczególnych atrybutów są od siebie warunkowo (względem kategorii) niezależne, czyli że zachodzi następująca równość:

$\mathrm {Pr} _{o\in \Omega }{\Big (}\bigwedge _{i=1}^{n}a_{i}(o)=b_{i}\,{\big |}\,\phi (o)=v{\Big )}=\prod _{i=1}^{n}\mathrm {Pr} _{o\in \Omega }{\big (}a_{i}(o)=b_{i}\,|\,\phi (o)=v{\big )}.\,$

(12)

Na ogół trudno określić, czy założenie to jest spełnione i można przypuszczać, że dla wielu dziedzin spełnione nie jest. Na przyjęciu mimo to takiego założenia polega właśnie „naiwność”, która znalazła odzwierciedlenie w zwyczajowej nazwie algorytmu. Nawet jednak jeśli założenie to jest samo w sobie istotnie naiwne, oparty na nim algorytm okazał się na tyle skuteczny, aby był stosowany mimo zniechęcającej nazwy. Ostateczną postać hipotezy reprezentowanej przez rozkłady prawdopodobieństw szacowane przez naiwny klasyfikator bayesowski można zapisać następująco:

$g(o_{*})=\mathrm {arg} \max _{v\in V}\mathrm {Pr} (\phi (o)=v)\cdot \prod _{i=1}^{n}\mathrm {Pr} {\big (}a_{i}(o)=a_{i}(o_{*})\,|\,\phi (o)=v{\big )}.\,$

(13)

Dokonanie klasyfikacji przykładu wymaga więc wymnożenia dla każdej kategorii pewnej liczby oszacowanych na podstawie zbioru trenującego prawdopodobieństw, wybieranych w zależności od wartości atrybutów klasyfikowanego przykładu.

W wielu zastosowaniach, nawet kiedy założenie o niezależności jest w oczywisty sposób nie spełnione, naiwny klasyfikator bayesowski okazuje się bardzo skutecznym algorytmem, czasem nawet porównywalnym z omawianymi przez nas wcześniej zaawansowanymi algorytmami indukcji drzew decyzyjnych lub reguł. Przy tym wymagany nakład obliczeń jest znacznie mniejszy. Szczególnie dobre efekty osiągano stosując naiwny klasyfikator bayesowski do klasyfikacji tekstów.

Przykład klasyfikacji bayesowskiej. Zastosujemy naiwny klasyfikator bayesowski wyznaczony na podstawie zbioru trenującego z poprzednich przykładów do klasyfikacji pierwszego elementu z tego zbioru. Dla przykładu $o_{*}=1\,$ mamy:

${\textit {aura}}(1)=\,$	${\textit {sloneczna}},\,$
${\textit {temperatura}}(1)=\,$	${\textit {ciepla}},\,$
${\textit {wilgotnosc}}(1)=\,$	${\textit {duza}},\,$
${\textit {wiatr}}(1)=\,$	${\textit {slaby}}.\,$

Niezbędne prawdopodobieństwa możemy oszacować w następujący sposób:

$\mathrm {Pr} (\phi (o)=1)=\,$	${\frac {9}{14}},\,$
$\mathrm {Pr} (\phi (o)=0)=\,$	${\frac {5}{14}},\,$
$\mathrm {Pr} {\big (}{\textit {aura}}(o)={\textit {sloneczna}}\,|\,\phi (o)=1{\big )}=\,$	${\frac {2}{9}},\,$
$\mathrm {Pr} {\big (}{\textit {aura}}(o)={\textit {sloneczna}}\,|\,\phi (o)=0{\big )}=\,$	${\frac {3}{5}},\,$
$\mathrm {Pr} {\big (}{\textit {temperatura}}(o)={\textit {ciepla}}\,|\,\phi (o)=1{\big )}=\,$	${\frac {2}{9}},\,$
$\mathrm {Pr} {\big (}{\textit {temperatura}}(o)={\textit {ciepla}}\,|\,\phi (o)=0{\big )}=\,$	${\frac {2}{5}},\,$
$\mathrm {Pr} {\big (}{\textit {wilgotnosc}}(o)={\textit {duza}}\,|\,\phi (o)=1{\big )}=\,$	${\frac {3}{9}},\,$
$\mathrm {Pr} {\big (}{\textit {wilgotnosc}}(o)={\textit {duza}}\,|\,\phi (o)=0{\big )}=\,$	${\frac {4}{5}},\,$
$\mathrm {Pr} {\big (}{\textit {wiatr}}(o)={\textit {slaby}}\,|\,\phi (o)=1{\big )}=\,$	${\frac {6}{9}},\,$
$\mathrm {Pr} {\big (}{\textit {wiatr}}(o)={\textit {slaby}}\,|\,\phi (o)=0{\big )}=\,$	${\frac {2}{5}}.\,$

Na tej podstawie obliczamy dla kategorii $1\,$ i $0\,$ iloczyny prawdopodobieństw, których porównanie zgodnie z będzie podstawą do klasyfikacji przykładu $1\,$:

$\mathrm {Pr} (\phi (o)=1)\,$	$\cdot \mathrm {Pr} {\big (}{\textit {aura}}(o)={\textit {sloneczna}}\,|\,\phi (o)=1{\big )}\cdot \,$
	$\cdot \mathrm {Pr} {\big (}{\textit {temperatura}}(o)={\textit {ciepla}}\,|\,\phi (o)=1{\big )}\cdot \,$
	$\cdot \mathrm {Pr} {\big (}{\textit {wilgotnosc}}(o)={\textit {duza}}\,|\,\phi (o)=1{\big )}\cdot \,$
	$\cdot \mathrm {Pr} {\big (}{\textit {wiatr}}(o)={\textit {slaby}}\,|\,\phi (o)=1{\big )}=\,$
$=\,$	${\frac {9}{14}}\cdot {\frac {2}{9}}\cdot {\frac {2}{9}}\cdot {\frac {3}{9}}\cdot {\frac {6}{9}}={\frac {648}{91854}}=0.007,\,$
$\mathrm {Pr} (\phi (o)=0)\,$	$\cdot \mathrm {Pr} {\big (}{\textit {aura}}(o)={\textit {sloneczna}}\,|\,\phi (o)=0{\big )}\cdot \,$
	$\cdot \mathrm {Pr} {\big (}{\textit {temperatura}}(o)={\textit {ciepla}}\,|\,\phi (o)=0{\big )}\cdot \,$
	$\cdot \mathrm {Pr} {\big (}{\textit {wilgotnosc}}(o)={\textit {duza}}\,|\,\phi (o)=0{\big )}\cdot \,$
	$\cdot \mathrm {Pr} {\big (}{\textit {wiatr}}(o)={\textit {slaby}}\,|\,\phi (o)=0{\big )}=\,$
$=\,$	${\frac {5}{14}}\cdot {\frac {3}{5}}\cdot {\frac {2}{5}}\cdot {\frac {4}{5}}\cdot {\frac {2}{5}}={\frac {240}{8750}}=0.027.\,$

Oznacza to, że $g(1)=0\,$.

Klasyfikatory pamięciowe

Klasyfikatory pamięciowe reprezentują paradygmat „leniwego uczenia się”: uczenie się polega zasadniczo tylko na zapamiętaniu danych trenujących. Ich przetwarzanie odkładane jest do czasu, gdy zachodzi potrzeba odpowiedzi na zapytanie - zastosowania modelu do nowego przykładu, i koncentruje się na przykładach trenujących podobnych do niego. W ten sposób można się uczyć zarówno klasyfikacji, jak i regresji.

Pamięć i jej stosowanie

Przyjmiemy, że wszystkie przykłady, jakie otrzymał klasyfikator, składają się na zapamiętany przez niego zbiór trenujący $T\,$. Zawartością tak rozumianej pamięci są więc pary $\langle o,\phi (o)\rangle \,$ dla $o\in T\,$.

Istotnym założeniem, na którym opierają się metody pamięciowe, jest dostępność metryki określonej na dziedzinie $O\,$, mierzącej odległość między dowolnymi dwoma przykładami. Jest to pewna funkcja $\delta :O\times O\mapsto \Re ^{+}\cup \{0\}\,$, która nie musi w zasadzie spełniać żadnych szczególnych warunków, a jedynie dobrze odzwierciedlać nasze rozumienie podobieństwa przykładów z dziedziny, w której jest przeprowadzana aproksymacja funkcji. W przypadku, gdy wszystkie określone na dziedzinie atrybuty są ciągłe, najczęściej jest stosowana standardowa metryka euklidesowa z opcjonalnym skalowaniem, zgodnie z którą odległość między przykładami $o_{1},o_{2}\in O\,$ jest obliczana następująco:

$\delta (o_{1},o_{2})={\sqrt {\sum _{i=0}^{n-1}\alpha _{i}^{2}{\big (}a_{i}(o_{1})-a_{i}(o_{2}){\big )}^{2}}},\,$

(14)

przy czym $\alpha _{i}\,$ dla $i=0,1,\dots ,n-1\,$ są współczynnikami skalującymi, dzięki którym można regulować wpływ poszczególnych cech na odległość. Przy omawianiu grupowania były dyskutowane możliwości uogólnienia takiej odległości na atrybuty porządkowe i ciągłe, umożliwiłoby stosowanie aproksymatorów pamięciowych również dla dziedzin z takimi atrybutami.

Potrafiąc mierzyć stopień podobieństwa przykładów, mamy możliwość odpowiadania na zapytania na podstawie zawartości pamięci klasyfikatora. Najczęściej bowiem dla zadanego w zapytaniu przykładu $o_{*}\in O\,$ wyznacza się wartość $g(o_{*})\,$ biorąc pod uwagę zapamiętane przykłady trenujące $\langle \phi (o)\rangle \,$ dla $o\in T\,$ i uzależniając ich wpływ na obliczenie $g(o_{*})\,$ od odległości $\delta (o,o_{*})\,$, zdefiniowanej w odpowiedni dla dziedziny sposób.

Najbliższy sąsiad

Najprostszym i najbardziej znanym podejściem do klasyfikacji na podstawie zapamiętywania jest metoda najbliższego sąsiada, często nazywana krótko NN (nearest neighbor). Jak nazwa sugeruje, w celu wyznaczenia odpowiedzi na zapytanie dotyczące przykładu $o_{*}\,$ bierze się pod uwagę najbliższy mu, według przyjętej metryki, przykład trenujący. Jeśli przykładem tym jest $\langle o,\phi (o)\rangle \,$ dla pewnego $o\in T\,$, to przyjmuje się $g(o_{*})=\phi (o)\,$. Formalnie można to zapisać następująco:

$g(o_{*})=f{\big (}\mathrm {arg} \min _{o\in T}\delta (o,o_{*}){\big )}.\,$

(15)

Zauważmy, że tak sformułowany algorytm klasyfikacji nie wymaga przyjęcia żadnych założeń dotyczących dziedziny i reprezentacji przykładów poza tym, że jest dla nich określona pewna miara odległości.

Zaletą algorytmu NN jest jego prostota i uniwersalność. Uniwersalność umożliwia stosowanie go do zupełnie dowolnych dziedzin i określonych na nich odwzorowań. Można również powiedzieć, że charakteryzuje się on bardzo dużą (w istocie maksymalną) szybkością uczenia się, jeśli zgodzimy się rozumieć przez to, że do uzyskania $g(o)=\phi (o)\,$ dla pewnego przykładu $o\in O\,$ wystarczy jednokrotna prezentacja przykładu trenującego $\langle o,\phi (o)\rangle \,$. Dokładność uzyskiwanej aproksymacji zależy oczywiście od ilości dostępnych danych trenujących i jakości metryki, jaka jest wykorzystywana do znajdowania najbliższych sąsiadów.

Oczywistym mankamentem najprostszej wersji algorytmu NN jest łatwo zrozumiała tendencja do nadmiernego dopasowywania się do zaszumionych danych trenujących. Jeśli dla przykładu, którego dotyczy zapytanie, najbliższym sąsiadem będzie przykład o niepoprawnej wartości funkcji docelowej, to błąd odpowiedzi na to zapytanie może być arbitralnie duży. Często stosowanym uogólnieniem algorytmu NN, który w pewnym stopniu neutralizuje ten problem, jest algorytm kNN, używający $k\,$ najbliższych sąsiadów. Polega on na znalezieniu w zbiorze zapamiętanych przykładów $T\,$ ustalonej liczby $k\geq 1\,$ przykładów najbliższych przykładowi $o_{*}\,$, którego dotyczy zapytanie, i wyznaczeniu $g(o_{*})\,$ na podstawie kategorii tych $k\,$ przykładów. Wybór ten dokonywany jest przez zwykłe bądź ważone głosowanie.