• Są to metody leniwej klasyfikacji, które opóźniają proces przetwarzania danych aż do momentu kiedy pojawi się nowy obiekt do klasyfikowania

• Typowe metody:

  • ⋄ k-nearest neighbor approach

    • * Przykłady treningowe są przedstawione jako punkty w metrycznej przestrzeni.

  • ⋄ Locally weighted regression

    • * Konstruuje lokalne aproksymacje pojęć

  • ⋄ Case-based reasoning

    • * Korzysta z symbolicznych reprezentacji i metod wnioskowania w oparciu o bazę wiedzy

algorytm najbliższych sąsiadów

Input:

Tablica decyzyjna D, nowy obiekt xq

Output:

Klasa decyzyjna, do której należy xq (czyli D⁢e⁢c⁢xq)

Krok 1:

Szukaj w zbiorze D, k najbliżej położonych obiektów R⁢xq=x1,x2,…,xk

Krok 2:

Wyznacz klasę dla xq na podstawie D⁢e⁢c⁢x1,D⁢e⁢c⁢x2,…,D⁢e⁢c⁢xk

0.4 0.59 \column

• Najczęściej wykorzystany dla danych z atrybutami numerycznymi

• Wymagania:

  • Zbiór treningowy

  • Funkcja odległości między obiektami

  • Wartość parametru k, liczba rozpatrywanych sąsiadów

• Podczas klasyfikacji:

  • Wyznaczanie k najbliższych sąsiadów

  • Wyznaczenie klasy decyzyjnej nowego obiektu na podstawie klas decyzyjnych najbliższych sąsiadów (np. przez głosowanie).

• Jest to przykład metody leniwej, gdyż

  • Nie buduje jawnego modelu wiedzy

  • Proces klasyfikacji może być czasochłonny

• Jeśli k jest za mała, klasyfikator będzie wrażliwa na drobne szumy w danych

• Jeśli k jest zbyt duża:

  • Wysoka złożoność obliczeniowa

  • Otoczenia mogą zawierać obiekty z innych klas

• Algorytm k-NN dla ciągłej decyzji

  • Wystarczy obliczyć średnią z decyzji najbliższych sąsiadów

• Problem skalowania atrybutów

  • Np. opis człowieka:

    • (Wzrost [m], Waga [kg], Klasa)

    • Wzrost odchyla się od 1.5 m do 1.85 m

    • Waga może mieć wartość od 45 kg do 120 kg

    Odległość euklidesowa jest bardziej wrażliwa na różnicę wag niż różnicę wzrostu.

• Przekleństwo wymiarów

• Może produkować wyniki niezgodne z intuicją (np. klasyfikacji dokumentów)

  • Rozwiązanie: Normalizacja

• Sąsiedzi ważeni względem odległośc

  • Wpływ sąsiada xi na obiekt testowy xq jest ważony przez wi=1d2⁢xq,xi

  • Bliżsi sąsiedzi mają większy wpływ

0.6

• Dany jest zbiór treningowy D, prawdopodobieństwo posteriori hipotezy h – P(h|D) – można liczyć wzorem Bayesa.

  P(h|D)=P(D|h)P(h)P⁢D

• MAP (maximum posteriori) hypothesis

  hM⁢A⁢P=argmaxh∈HP(h|D)=argmaxh∈HP(D|h)P(h)

• Trudności: ta metoda wymaga znajomości wielu rozkładów prawdopodobieństw ⟹ wysoki koszt obliczeniowy

0.39

• Klasyfikacja obiektu opisanego przez x

  P(dec=c|x)=P(x|dec=c)⋅P(dec=c)P⁢x

• P⁢x jest wspólna dla wszystkich hipotez;

• Pd⁢e⁢c=c – częstość występowania klasy c;

• Znaleźć c tak, że P(dec=c|x) było maksymalne, czyli, aby P(x|dec=c)⋅P(dec=c) było maksymalne;

• Problem: obliczenie P(x|dec=c) jest czasochłonne!

• Naiwne założenie: atrybuty są warunkowo niezależne!

  Wówczas

  P(x1,…,xk|C)=P(x1|C)⋅…⋅P(xk|C)

• Czyli

  P(dec=c|x)≈P(dec=c)∏i=1kP(xi|dec=c)⋅

  To założenie znacznie obniża złożoność obliczeniowy.

• Nowy obiekt x=r⁢a⁢i⁢n,h⁢o⁢t,h⁢i⁢g⁢h,f⁢a⁢l⁢s⁢e

  	P(X|p)·P(p)	=P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=0.010582
  	P(X|n)·P(n)	=P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=0.018286

• X jest klasyfikowany do klasy n (don’t play)

• Założenie o niezależności:

  • … powoduje, że obliczenia staje się możliwe

  • … optymalny klasyfikator o ile ono jest prawdziwe

  • … ale warunek bardzo rzadko spełniony w praktyce (atrybuty są często korelowane).

• Próby pokonania te ograniczenia:

  • Sieci Bayesowskie, które łączą metody wnioskowania Bayesowskiego z zależnościami między atrybutami

  • Drzewa decyzyjne, które przeprowadzają dedukcyjne kroki na pojedyńczych atrybutach, począwszy od najważniejszego

• Sieci Bayesowskie dopuszczają “warunkową niezależność” podzbiorów zmiennych.

• Jest to graficzny model zależności przyczynowo-skutkowych

• Naive Bayes jest szczególnym przypadkiem sieci Bayesowskiej (jakim?)

• Problemy związane uczeniem sieci Bayesowskich:

  • Prypadek najłatwiejszy: zarówno struktura sieci, jak i wszystkie zmienne są znane.

  • Znana jest struktura, ale brakuje rozkładów zmiennych.

  • Nawet struktura sieci nie jest z góry zadana.

Ogólna formuła

P(x1,…,xk|C)=∏i=1kP(xi|parent(xi),C)