Zagadnienia

2. Problem klasyfikacji i klasyfikatory

2.1. Problem klasyfikacji i klasyfikatory

2.1.1. Wprowadzenie

  • Założenie: Dany jest skończony zbiór obiektów T=x1,,xn. Ten zbiór nazywamy zbiorem treningowym

    • Każdy obiekt (rekord) jest opisany wektorem informacyjnym, składającym się z wartości pochodzących z dziedziny pewnych atrybutów warunkowych.

    • Wyróżniony jest jeden atrybut, zwany też atrybutem decyzyjnym

      xixi1,,xik,di
  • Cel: wyznaczyć klasę decyzyjną, do której należy nowy nieznany dotąd obiekt.

  • Jak? Znaleźć zależność (najlepiej funkcyjną) między atrybutem decyzyjnym a atrybutami warunkowymi.

  1. Tworzenie modelu: opisywanie klas decyzyjnych

    • Klasa decyzyjna = zbiór obiektów mających taką samą wartość na atrybucie decyzyjnym

    • Klasyfikator: algorytm określenia klasy decyzyjnej obiektów za pomocą ich wartości na atrybutach warunkowych.

    • Klasyfikatory mogą być opisane za pomocą formuł logicznych, drzew decyzyjnych lub formuł matematycznych.

  2. Korzystanie z modelu do przypisanie nowym nieznanym obiektom ich klasy decyzyjne.

Problem: Jak oceniać model?

  • Wiele problemów decyzyjnych można opisać jako problem klasyfikacji

  • DSS (Decision Support System) jest systemem komputerowym dostarczającym narzędzia do rozwiązywania problemów klasyfikacji.

    Wejście:

    Zbiór treningowy

    Wyjście:

    Klasyfikator(y)

  • Wymagania:

    • Szybkość podejmowania decyzji, skalowalność

    • Skuteczność

    • Racjonalność

    • Możliwość współpracy z ekspertem: doradztwo, adaptacja, negocjacja, adopcja wiedzy eksperskiej, …

2.1.2. Przegląd metod klasyfikacji

2.1.2.1. Metody oparte o przykłady

  • 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

\block

algorytm najbliższych sąsiadów

Input:

Tablica decyzyjna D, nowy obiekt xq

Output:

Klasa decyzyjna, do której należy xq (czyli Decxq)

Krok 1:

Szukaj w zbiorze D, k najbliżej położonych obiektów Rxq=x1,x2,,xk

Krok 2:

Wyznacz klasę dla xq na podstawie Decx1,Decx2,,Decxk

\columns\column

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=1d2xq,xi

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

2.1.2.2. Wnioskowanie Bayesowskie

\columns\column

0.6

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

    P(h|D)=P(D|h)P(h)PD
  • MAP (maximum posteriori) hypothesis

    hMAP=argmaxhHP(h|D)=argmaxhHP(D|h)P(h)
  • Trudności: ta metoda wymaga znajomości wielu rozkładów prawdopodobieństw wysoki koszt obliczeniowy

\column

0.39

  • Klasyfikacja obiektu opisanego przez x

    P(dec=c|x)=P(x|dec=c)P(dec=c)Px
  • Px jest wspólna dla wszystkich hipotez;

  • Pdec=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=rain,hot,high,false

    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.

\block

Ogólna formuła

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

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.