Zagadnienia

7. Problem dyskretyzacji

7.1. Problem dyskretyzacji

7.1.1. Przypomnienia podstawowych pojęć

Tablicą decyzyjną nazywamy strukturę S=U,A∪d⁢e⁢c gdzie

U nazywa się zbiorem obiektów

U=u1,…,un

A jest zbiorem atrybutów postaci

aj:U⟶Vj

d⁢e⁢c jest specjalnym atrybutem zwanym decyzją

d⁢e⁢c:U⟶1,…,d
A
S a1 a2 … d⁢e⁢c
u1 100 27 … 1
u2 120 86 … 1
u3 70 52 … 1
u4 95 18 … 1
… … … … …
u1200 71 82 … 2
… … … … …
  • Klasy decyzyjne:

    d⁢e⁢c definiuje podział U=D⁢E⁢C1∪…∪D⁢E⁢Cd gdzie

    D⁢E⁢Ck=x∈U:d⁢e⁢c⁢x=k
  • Rozróżnialność: Dane są obiekty x,y∈U zbiór atrybutów B⊂A, mówimy, że x,y są rozróżnialne przez B wtw, gdy istnieje a∈B taki, że a⁢x≠a⁢y

Zbiór atrybutów B⊂A nazywamy reduktem tablicy S wtw, gdy

  • dla dowolnych obiektów x,y∈U

    jeślid⁢e⁢c⁢x≠d⁢e⁢c⁢y i x,y są rozróżnialne przez A,

    to są również rozróżnialne przez B

    (B zachowuje rozróżnialność zbioru A)

  • B jest niezredukowalny (tzn. żaden właściwy podzbiór B nie zachowuje rozróżnialności zbioru A)

Problemy:

  • Czy istnieje redukt zawierający k atrybutów?

  • Znaleźć redukt o najmniejszej liczbie atrybutów.

  • funkcje f:0,1n→0,1 nazywamy Boolowskimi.

  • monotoniczne funkcje Boolowskie można zapisać bez użycia negacji.

  • jednomian f′=xi1⁢xi2⁢…⁢xik nazywamy implikantem pierwszym funkcji monotonicznej f jeśli

    • f′⁢x⩽f⁢x dla każdego wektora x (jest implikantem)

    • każda funkcja większa od f′ nie jest implikantem

  • Np. funkcja

    f⁢x1,x2,x3=x1+x2⁢x2+x⁢3

    posiada 2 implikanty pierwsze: f1=x2 i f2=x1⁢x3

7.1.2. Problem dyskretyzacji

Dana jest niesprzeczna tablica decyzyjna S=U,A∪d⁢e⁢c

  • Mówimy, że cięcie a,c rozróżnia obiekty x,y jeśli albo a⁢x<c<a⁢y lub a⁢y<c<a⁢x.

  • Zbiór cięć P nazywamy niesprzecznym z S jeśli dla każdej pary obiektów x,y∈U takich, że d⁢x≠d⁢y istnieje cięcie a,c∈P rozróżniające x i y.

  • Zbiór cięć Po⁢p⁢t nazywamy optymalnym dla S jeśli Po⁢p⁢t posiada najmniejszą liczbę cięć wśród niesprzecznych zbiorów cięć.

7.1.2.1. Istniejące metody dyskretyzacji

  1. Lokalne a globalne metody:

  2. Statyczne a dynamiczne metody: Metody statyczne poszukują zbioru cięć dla każdego atrybutu w sposób niezależny od innych atrybutów. Metody dynamiczne szukają cięć na wszystkich atrybutach jednocześnie

  3. Z nadzorem lub bez:

  • <+-|alert@+> Podział na przedziały o równych długościach lub równych częstotliwościach;

  • <+-|alert@+> Metoda OneR

  • <+-|alert@+> Testy statystyczne

    χ2=∑i=12∑j=1rni⁢j-Ei⁢j2Ei⁢j
  • <+-|alert@+> Z użyciem funkcji entropii;

    G⁢a⁢i⁢n⁢a;c;U=E⁢n⁢t⁢U-E⁢a;c;U
  • <+-|alert@+> Gini's index

    G⁢a;c;U=G⁢i⁢n⁢i⁢U-ULU⋅G⁢i⁢n⁢i⁢UL-URU⋅G⁢i⁢n⁢i⁢UR
  • Metoda statyczna bez nadzoru: podział danych numerycznych na równomierne przedziały;

  • Rozpatrujemy liczbę różnych najbardziej znaczących cyfr w danym przedziale:

    • jeśli ta liczba wynosi 3,6,7 lub 9 to podziel dany przedział na 3 równe przedziały.

    • jeśli ta liczba wynosi 2,4 lub 8 to podziel dany przedział na 4 równe przedziały.

    • jeśli ta liczba wynosi 1,5 lub 10 to podziel dany przedział na 5 równych przedziałów.

7.1.3. Dyskretyzacja metodą wnioskowania Boolowskiego

Dana jest niesprzeczna tablica decyzyjna S=U,A∪d⁢e⁢c

  • Niech C będzie zbiorem kandydujących cięć dla tablicy S;

  • Każde cięcie a,c jest skojarzone ze zmienną Boolowską pa,c;

  • Niech ψx,y będzie funkcją rozróżnialności dla x,y:

    ψx,y=⋁pa,c:a,c⁢ rozróżnia ⁢x,y.
  • Funkcja boolowska

    ΨS=∏ψx,y:d⁢e⁢c⁢x≠d⁢e⁢c⁢y

    koduje problem dyskretyzacji.

  • Minimalny implikant pierwszy ΨS ⇒ optymalny zbiór cięć.

Ciecia kandydujące

a,0.9;a,1.15;a,1.35;a,1.5;⁢b,0.75;b,1.5;b,2.5.

Oznaczmy przez p1a,p2a,p3a,p4a,⁢p1b,p2b,p3b zmienne Boolowskie odpowiadające cięciom. Wówczas

ψ⁢2,1=p1a+p1b+p2b;ψ⁢2,4=p2a+p3a+p1b;ψ⁢2,6=p2a+p3a+p4a+p1b+p2b+p3b;ψ⁢2,7=p2a+p1b;ψ⁢3,1=p1a+p2a+p3b;ψ⁢3,4=p2a+p2b+p3b;ψ⁢3,6=p3a+p4a;ψ⁢3,7=p2b+p3b;ψ⁢5,1=p1a+p2a+p3a;ψ⁢5,4=p2b;ψ⁢5,6=p4a+p3b;ψ⁢5,7=p3a+p2b.

Funkcja kodująca problem dyskretyzacji

ΦS=p1a+p1b+p2b⁢p1a+p2a+p3b⁢p1a+p2a+p3a⁢p2a+p3a+p1bp2b⁢p2a+p2b+p3b⁢p2a+p3a+p4a+p1b+p2b+p3b⁢p3a+p4ap4a+p3b⁢p2a+p1b⁢p2b+p3b⁢p3a+p2b.

Po sprowadzeniu do postaci DNF mamy:

ΦS=p2a⁢p4a⁢p2b+p2a⁢p3a⁢p2b⁢p3b+p3a⁢p1b⁢p2b⁢p3b+p1a⁢p4a⁢p1b⁢p2b.

Czyli optymalnym zbiorem cięć jest a,1.15,a,1.5,b,1.5

  • <+-|alert@+> W algorytmie zachłannym, preferujemy cięcia rozróżniające największą liczbę par obiektów.

  • <+-|alert@+> Miara rozróżnialności dla danego cięcia względem zbioru obiektów X:

    d⁢i⁢s⁢c⁢c,X=c⁢o⁢n⁢f⁢l⁢i⁢c⁢t⁢X-c⁢o⁢n⁢f⁢l⁢i⁢c⁢t⁢XL-c⁢o⁢n⁢f⁢l⁢i⁢c⁢t⁢XR

    gdzie c⁢o⁢n⁢f⁢l⁢i⁢c⁢t⁢X = liczba par obiektów różnych decyzji w zbiorze X.

  • <+-|alert@+> Można realizować zachłanną heurystykę w czasie O⁢n⁢k⁢log⁡n⁢P, gdzie n jest liczbą obiektów, k jest liczbą atrybutów, P jest zbiorem cięć znalezionych przez algorytm

S* p1a p2a p3a p4a p1b p2b p3b d*
u1,u2 1 0 0 0 1 1 0 1
u1,u3 1 1 0 0 0 0 1 1
u1,u5 1 1 1 0 0 0 0 1
u4,u2 0 1 1 0 1 0 0 1
u4,u3 0 0 1 0 0 1 1 1
u4,u5 0 0 0 0 0 1 0 1
u6,u2 0 1 1 1 1 1 1 1
u6,u3 0 0 1 1 0 0 0 1
u6,u5 0 0 0 1 0 0 1 1
u7,u2 0 1 0 0 1 0 0 1
u7,u3 0 0 0 0 0 1 1 1
u7,u5 0 0 1 0 0 1 0 1
n⁢e⁢w 0 0 0 0 0 0 0 0

7.1.3.1. Uogólnienia problemu dyskretyzacji

  • Hiperpłaszczyzny jako cięcia;

  • Krzywe wyższego rzędu;

  • Grupowanie wartości nominalnych;

  • Inne kryteria optymalizacji.

  • Dyskretyzacja jako proces wstępnego przetwarzania

  • Miarę rozróżnialności można stosować do konstrukcji drzew decyzyjnych.

  • Drzewa generowane tą miarą mają dużo ciekawych własności i dużą skuteczność w procesie klasyfikacji.

  • Rozumowanie Boolowskie jest prostym, ale mocnym narzędziem w dziedzinie rozpoznawania wzorców, eksploracji danych (ang. Data Mining), sztucznej inteligencji …

  • Złożoność funkcji Boolowskiej kodującej dany problem może być miarą trudności tego problemu.

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.