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

• 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

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ęć.

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

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

Funkcja kodująca problem dyskretyzacji

Po sprowadzeniu do postaci DNF mamy:

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