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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \phi:O\rightarrow V \} , należą do skończonego zbioru kategorii (klas) Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle a:O\mapsto A \} ,.
- Testy tożsamościowe: test utożsamiany jest z atrybutem, Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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):
Parser nie mógł rozpoznać (błąd składni): {\displaystyle t(o) = \begin{cases} 1 & \textit{jesli\ } a(o)=b\\ 0 & \textit{jesli\ } a(o)\neq b \end{cases} \} , (1)
- gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle b\in A \} ,.
- Testy przynależnościowe: test sprawdzający przynależność do zbioru dla wartości atrybutu (dla dowolnych typów atrybutów):
Parser nie mógł rozpoznać (błąd składni): {\displaystyle t(o) = \begin{cases} 1 & \textit{jesli\ } a(o)\in B\\ 0 & \textit{jesli\ } a(o)\not\in B \end{cases} \} , (2)
- gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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):
Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle B_1,B_2,\dots,B_m \} , stanowią wyczerpujący podział przeciwdziedziny atrybutu Parser nie mógł rozpoznać (błąd składni): {\displaystyle A \} ,.
- Testy nierównościowe: test sprawdzający nierówność dla wartości atrybutu (dla atrybutów porządkowych i ciągłych):
Parser nie mógł rozpoznać (błąd składni): {\displaystyle t(o) = \begin{cases} 1 & \textit{jesli\ } a(o)\leq\theta\\ 0 & \textit{jesli\ } a(o)>\theta \end{cases} \} , (4)
- gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \theta\in A \} ,.
Dla testu Parser nie mógł rozpoznać (błąd składni): {\displaystyle t \} , i zbioru przykładów Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} , będziemy stosować oznaczenia:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_{tr} = \{o\in P \;|\; t(o)=r\}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle P^v_{tr} = \{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:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle o \} , aura temperatura wilgotność wiatr Parser nie mógł rozpoznać (błąd składni): {\displaystyle \phi(o) \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , słoneczna ciepła duża słaby Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 2 \} , słoneczna ciepła duża silny Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 3 \} , pochmurna ciepła duża słaby Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 4 \} , deszczowa umiarkowana duża słaby Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 5 \} , deszczowa zimna normalna słaby Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 6 \} , deszczowa zimna normalna silny Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 7 \} , pochmurna zimna normalna silny Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 8 \} , słoneczna umiarkowana duża słaby Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 9 \} , słoneczna zimna normalna słaby Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 10 \} , deszczowa umiarkowana normalna słaby Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 11 \} , słoneczna umiarkowana normalna silny Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 12 \} , pochmurna umiarkowana duża silny Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 13 \} , pochmurna ciepła normalna słaby Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 14 \} , deszczowa umiarkowana duża silny Parser nie mógł rozpoznać (błąd składni): {\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:
|
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:
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle v_l \} , - kategoria umieszczona w liściu Parser nie mógł rozpoznać (błąd składni): {\displaystyle l \} ,,
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle t_n \} , - test umieszczony w węźle Parser nie mógł rozpoznać (błąd składni): {\displaystyle n \} ,,
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle n[r] \} , - poddrzewo, do którego z węzła Parser nie mógł rozpoznać (błąd składni): {\displaystyle n \} , prowadzi krawędź odpowiadająca wynikowi Parser nie mógł rozpoznać (błąd składni): {\displaystyle r \} , umieszczonego w nim testu.
Przy pierwszym wywołaniu jako zbiór przykładów Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} , przekazywany jest cały zbiór trenujący Parser nie mógł rozpoznać (błąd składni): {\displaystyle T \} ,.
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{buduj-drzewo}(P,v,S) \} ,
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} , - zbiór przykładów etykietowanych pojęcia Parser nie mógł rozpoznać (błąd składni): {\displaystyle c \} ,,
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle v \} , - domyślna etykieta kategorii,
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle S \} , - zbiór możliwych testów;
zwraca drzewo decyzyjne reprezentujące hipotezę przybliżającą Parser nie mógł rozpoznać (błąd składni): {\displaystyle c \} , na zbiorze Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} ,;
- jeśli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{kryterium-stopu}(P,S) \}
,
- utwórz liść Parser nie mógł rozpoznać (błąd składni): {\displaystyle l \} ,;
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle v_l := \textit{kategoria}(P,v) \} ,;
- zwróć Parser nie mógł rozpoznać (błąd składni): {\displaystyle l \} ,;
- utwórz węzeł Parser nie mógł rozpoznać (błąd składni): {\displaystyle n \} ,;
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle t_n := \textit{wybierz-test}(P,S) \} ,;
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle v := \textit{kategoria}(P,v) \} ,;
- dla każdego Parser nie mógł rozpoznać (błąd składni): {\displaystyle r\in R_{t_n} \}
,
- Parser nie mógł rozpoznać (błąd składni): {\displaystyle n[r] := \textit{buduj-drzewo}(P_{t_nr},v, S-\{t_n\}) \} ,;
- zwróć Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} , jest pusty,
- wszystkie przykłady ze zbioru Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} , należą do tej samej kategorii pojęcia Parser nie mógł rozpoznać (błąd składni): {\displaystyle c \} ,,
- zbiór możliwych do użycia testów Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle g_t(P) = I(P) - E_t(P), \} , (5)
gdzie
Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(P) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{v\in V} -\frac{|P^v|}{|P|} \log\frac{|P^v|}{|P|}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle E_t(P) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{r\in R_t}\frac{|P_{tr}|}{|P|}E_{tr}(P), \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle E_{tr}(P) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sum_{v\in V}-\frac{|P^v_{tr}|}{|P_{tr}|} \log\frac{|P^v_{tr}|}{|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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{aura} \} , z podane w poprzednim przykładzie zbioru danych. Do jego obliczenia są potrzebne liczności następujących zbiorów:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T^1| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\{3,4,5,7,9,10,11,12,13\}|=9, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T^0| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\{1,2,6,8,14\}|=5, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T_{\textit{aura},\textit{sloneczna}}| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\{1,2,8,9,11\}|=5, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T^1_{\textit{aura},\textit{sloneczna}}| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\{9,11\}|=2, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T^0_{\textit{aura},\textit{sloneczna}}| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\{1,2,8\}|=3, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T_{\textit{aura},\textit{pochmurna}}| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\{3,7,12,13\}|=4, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T^1_{\textit{aura},\textit{pochmurna}}| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\{3,7,12,13\}|=4, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T^0_{\textit{aura},\textit{pochmurna}}| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\emptyset|=0, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T_{\textit{aura},\textit{deszczowa}}| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\{4,5,6,10,14\}|=5, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T^1_{\textit{aura},\textit{deszczowa}}| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\{4,5,10\}|=3, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T^0_{\textit{aura},\textit{deszczowa}}| = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle |\{6,14\}|=2. \} ,
Przyjmując logarytmy dwójkowe można obecnie obliczyć, z dokładnością do trzech miejsc po przecinku:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle E_{\textit{aura},\textit{sloneczna}}(P) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle -\frac{2}{5}\log_2\frac{2}{5}-\frac{3}{5}\log_2\frac{3}{5} = 0.971, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle E_{\textit{aura},\textit{pochmurna}}(P) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle -\frac{4}{4}\log_2\frac{4}{4}-\frac{0}{4}\log_2\frac{0}{4} = 0, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle E_{\textit{aura},\textit{deszczowa}}(P) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle -\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:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{aura} \} ,. Mamy:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle I(T) = -\frac{9}{14}\log_2\frac{9}{14}-\frac{5}{14}\log_2\frac{5}{14} = 0.940. \} ,
Wobec tego
Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle b_1 \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle b_2 \} , atrybutu ciągłego lub porządkowego Parser nie mógł rozpoznać (błąd składni): {\displaystyle a \} , wszystkie przykłady w zbiorze Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} , mają tę samą kategorię, to na pewno optymalna wartość progowa Parser nie mógł rozpoznać (błąd składni): {\displaystyle \theta \} , nie znajduje się między Parser nie mógł rozpoznać (błąd składni): {\displaystyle b_1 \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle b_2 \} , i w związku z tym obliczanie jakości testów dla takich wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle o\in P \} ,, dla którego Parser nie mógł rozpoznać (błąd składni): {\displaystyle b_1\leq a(o)\leq b_2 \} ,, mamy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \phi(o)=v \} ,, to w przypadku wyboru wartości progowej Parser nie mógł rozpoznać (błąd składni): {\displaystyle b_1\leq\theta<b_2 \} , uzyskamy podział zbioru Parser nie mógł rozpoznać (błąd składni): {\displaystyle P \} , na dwa podzbiory, w których te przykłady o kategorii Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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ę Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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ę Parser nie mógł rozpoznać (błąd składni): {\displaystyle v\in V \} ,. Załóżmy, że na tej ścieżce kolejno występują testy Parser nie mógł rozpoznać (błąd składni): {\displaystyle t_1,t_2,\dots,t_m \} ,, a odpowiednie gałęzie odpowiadają wynikom tych testów Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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łą:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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ł:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{aura}(o)=\textit{sloneczna} \land\textit{wilgotnosc}(o)=\textit{duza} \rightarrow \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{aura}(o)=\textit{sloneczna} \land\textit{wilgotnosc}(o)=\textit{normalna} \rightarrow \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{aura}(o)=\textit{pochmurna} \rightarrow \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{aura}(o)=\textit{deszczowa} \land\textit{wiatr}(o)=\textit{silny} \rightarrow \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{aura}(o)=\textit{deszczowa} \land\textit{wiatr}(o)=\textit{slaby} \rightarrow \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle T \} , są szacowane prawdopodobieństwa poszczególnych kategorii pojęcia docelowego Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}(\phi(o)=v) \} , dla wszystkich kategorii Parser nie mógł rozpoznać (błąd składni): {\displaystyle v\in V \} , pojęcia docelowego Parser nie mógł rozpoznać (błąd składni): {\displaystyle c \} , oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(a_i(o)=b\,|\,\phi(o)=v\big) \} , dla wszystkich kategorii Parser nie mógł rozpoznać (błąd składni): {\displaystyle v\in V \} , oraz wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle b\in A_i \} , dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle i=1,2,\dots,n \} ,, przy czym Parser nie mógł rozpoznać (błąd składni): {\displaystyle A_i \} , jest przeciwdziedziną atrybutu Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , w sytuacji, gdy w zbiorze Parser nie mógł rozpoznać (błąd składni): {\displaystyle T \} , nie ma żadnego przykładu spełniającego określone warunku. Najprostszą techniką jest zastępowanie ich pewną niewielką, lecz dodatnią wartością Parser nie mógł rozpoznać (błąd składni): {\displaystyle \epsilon \} , (mniejszą niż prawdopodobieństwo, jakie otrzymalibyśmy, gdyby znalazł się Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , taki przykład).
Klasyfikowanie przykładów
Załóżmy, że dany jest pewien przykład Parser nie mógł rozpoznać (błąd składni): {\displaystyle o_*\in O \} , i należy, przy dostępnych oszacowaniach prawdopodobieństw Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}(\phi(o)=v) \} , dla wszystkich Parser nie mógł rozpoznać (błąd składni): {\displaystyle v\in V \} , oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(a_i(o)=b\,|\,\phi(o)=v\big) \} , dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle i=1,2,\dots,n \} ,, wszystkich Parser nie mógł rozpoznać (błąd składni): {\displaystyle b\in A_i \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle g \} , możemy zapisać następująco:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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
Parser nie mógł rozpoznać (błąd składni): {\displaystyle g(o_*) = \mathrm{arg}\max_{v\in V} \mathrm{Pr}\Big(\phi(o)=v \,\big|\,\bigwedge_{i=1}^na_i(o)=a_i(o_*)\Big), \} , (9)
przy czym symbol Parser nie mógł rozpoznać (błąd składni): {\displaystyle \bigwedge \} , służy do zwartego zapisu koniunkcji Parser nie mógł rozpoznać (błąd składni): {\displaystyle n \} , równości. Oznacza to wybór dla przykładu Parser nie mógł rozpoznać (błąd składni): {\displaystyle o_* \} , kategorii najbardziej prawdopodobnej dla dowolnego przykładu wybranego z dziedziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle O \} ,, który jest opisany przez wektor wartości atrybutów Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{\mathrm{Pr}(\phi(o)=v)\cdot \mathrm{Pr}\Big(\bigwedge_{i=1}^na_i(o)=a_i(o_*) \,\big|\,\phi(o)=v\Big)} {\mathrm{Pr} \Big(\bigwedge_{i=1}^na_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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle v\in V \} ,.
Ponieważ wartości Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}(\phi(o)=v) \} , znamy, pozostaje określić sposób obliczania prawdopodobieństw postaci
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\Big(\bigwedge_{i=1}^na_i(o)=b_i\,\big|\,\phi(o)=v\Big) \} , (11)
dla dowolnych Parser nie mógł rozpoznać (błąd składni): {\displaystyle b_i\in A_i \} ,, Parser nie mógł rozpoznać (błąd składni): {\displaystyle i=1,2,\dots,n \} ,, i Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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ść:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}_{o\in\Omega} \Big(\bigwedge_{i=1}^na_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:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle o_*=1 \} , mamy:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{aura}(1) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{sloneczna}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{temperatura}(1) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{ciepla}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{wilgotnosc}(1) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{duza}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{wiatr}(1) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \textit{slaby}. \} ,
Niezbędne prawdopodobieństwa możemy oszacować w następujący sposób:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}(\phi(o)=1) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{9}{14}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}(\phi(o)=0) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{5}{14}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(\textit{aura}(o)=\textit{sloneczna}\,|\,\phi(o)=1\big) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{2}{9}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(\textit{aura}(o)=\textit{sloneczna}\,|\,\phi(o)=0\big) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{3}{5}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(\textit{temperatura}(o)=\textit{ciepla} \,|\,\phi(o)=1\big) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{2}{9}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(\textit{temperatura}(o)=\textit{ciepla} \,|\,\phi(o)=0\big) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{2}{5}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(\textit{wilgotnosc}(o)=\textit{duza} \,|\,\phi(o)=1\big) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{3}{9}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(\textit{wilgotnosc}(o)=\textit{duza} \,|\,\phi(o)=0\big) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{4}{5}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(\textit{wiatr}(o)=\textit{slaby}\,|\,\phi(o)=1\big) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{6}{9}, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}\big(\textit{wiatr}(o)=\textit{slaby}\,|\,\phi(o)=0\big) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{2}{5}. \} ,
Na tej podstawie obliczamy dla kategorii Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} , i Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 \} , iloczyny prawdopodobieństw, których porównanie zgodnie z będzie podstawą do klasyfikacji przykładu Parser nie mógł rozpoznać (błąd składni): {\displaystyle 1 \} ,:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}(\phi(o)=1) \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \cdot \mathrm{Pr}\big(\textit{aura}(o)=\textit{sloneczna} \,|\,\phi(o)=1\big)\cdot \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \cdot \mathrm{Pr}\big(\textit{temperatura}(o)=\textit{ciepla} \,|\,\phi(o)=1\big)\cdot \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \cdot \mathrm{Pr}\big(\textit{wilgotnosc}(o)=\textit{duza} \,|\,\phi(o)=1\big)\cdot \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \cdot \mathrm{Pr}\big(\textit{wiatr}(o)=\textit{slaby} \,|\,\phi(o)=1\big) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \frac{9}{14} \cdot\frac{2}{9} \cdot\frac{2}{9} \cdot\frac{3}{9} \cdot\frac{6}{9} = \frac{648}{91854} = 0.007, \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathrm{Pr}(\phi(o)=0) \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \cdot \mathrm{Pr}\big(\textit{aura}(o)=\textit{sloneczna} \,|\,\phi(o)=0\big)\cdot \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \cdot \mathrm{Pr}\big(\textit{temperatura}(o)=\textit{ciepla} \,|\,\phi(o)=0\big)\cdot \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \cdot \mathrm{Pr}\big(\textit{wilgotnosc}(o)=\textit{duza} \,|\,\phi(o)=0\big)\cdot \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \cdot \mathrm{Pr}\big(\textit{wiatr}(o)=\textit{slaby} \,|\,\phi(o)=0\big) = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle = \} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle T \} ,. Zawartością tak rozumianej pamięci są więc pary Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle o,\phi(o)\rangle \} , dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle o\in T \} ,.
Istotnym założeniem, na którym opierają się metody pamięciowe, jest dostępność metryki określonej na dziedzinie Parser nie mógł rozpoznać (błąd składni): {\displaystyle O \} ,, mierzącej odległość między dowolnymi dwoma przykładami. Jest to pewna funkcja Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle o_1,o_2\in O \} , jest obliczana następująco:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \alpha_i \} , dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle o_*\in O \} , wyznacza się wartość Parser nie mógł rozpoznać (błąd składni): {\displaystyle g(o_*) \} , biorąc pod uwagę zapamiętane przykłady trenujące Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle \phi(o)\rangle \} , dla Parser nie mógł rozpoznać (błąd składni): {\displaystyle o\in T \} , i uzależniając ich wpływ na obliczenie Parser nie mógł rozpoznać (błąd składni): {\displaystyle g(o_*) \} , od odległości Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle o_* \} , bierze się pod uwagę najbliższy mu, według przyjętej metryki, przykład trenujący. Jeśli przykładem tym jest Parser nie mógł rozpoznać (błąd składni): {\displaystyle \langle o,\phi(o)\rangle \} , dla pewnego Parser nie mógł rozpoznać (błąd składni): {\displaystyle o\in T \} ,, to przyjmuje się Parser nie mógł rozpoznać (błąd składni): {\displaystyle g(o_*)=\phi(o) \} ,. Formalnie można to zapisać następująco:
Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle g(o)=\phi(o) \} , dla pewnego przykładu Parser nie mógł rozpoznać (błąd składni): {\displaystyle o\in O \} , wystarczy jednokrotna prezentacja przykładu trenującego Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle k \} , najbliższych sąsiadów. Polega on na znalezieniu w zbiorze zapamiętanych przykładów Parser nie mógł rozpoznać (błąd składni): {\displaystyle T \} , ustalonej liczby Parser nie mógł rozpoznać (błąd składni): {\displaystyle k\geq 1 \} , przykładów najbliższych przykładowi Parser nie mógł rozpoznać (błąd składni): {\displaystyle o_* \} ,, którego dotyczy zapytanie, i wyznaczeniu Parser nie mógł rozpoznać (błąd składni): {\displaystyle g(o_*) \} , na podstawie kategorii tych Parser nie mógł rozpoznać (błąd składni): {\displaystyle k \} , przykładów. Wybór ten dokonywany jest przez zwykłe bądź ważone głosowanie.
