Zagadnienia

7. Problem dyskretyzacji

7.1. Problem dyskretyzacji

7.1.1. Przypomnienia podstawowych pojęć

Tablicą decyzyjną nazywamy strukturę \mathbb{S}=(U,A\cup\{ dec\}) gdzie

U nazywa się zbiorem obiektów

U=\{ u_{1},...,u_{n}\}

A jest zbiorem atrybutów postaci

a_{j}:U\longrightarrow V_{j}

dec jest specjalnym atrybutem zwanym decyzją

dec:U\longrightarrow\{ 1,...,d\}
A
\mathbb{S} a_{1} a_{2} dec
u_{1} 100 27 1
u_{2} 120 86 1
u_{3} 70 52 1
u_{4} 95 18 1
\ldots
u_{{1200}} 71 82 2
\ldots
  • Klasy decyzyjne:

    dec definiuje podział U=DEC_{1}\cup...\cup DEC_{d} gdzie

    DEC_{k}=\{ x\in U:dec(x)=k\}
  • Rozróżnialność: Dane są obiekty x,y\in U zbiór atrybutów B\subset A, mówimy, że x,yrozróżnialne przez B wtw, gdy istnieje a\in B taki, że a(x)\neq a(y)

Zbiór atrybutów B\subset A nazywamy reduktem tablicy \mathbb{S} wtw, gdy

  • dla dowolnych obiektów x,y\in U

    jeślidec(x)\ne dec(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,1\}^{n}\rightarrow\{ 0,1\} nazywamy Boolowskimi.

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

  • jednomian f^{{\prime}}=x_{{i_{1}}}x_{{i_{2}}}...x_{{i_{k}}} nazywamy implikantem pierwszym funkcji monotonicznej f jeśli

    • f^{{\prime}}({\bf x})\leqslant f({\bf x}) dla każdego wektora \bf x (jest implikantem)

    • każda funkcja większa od f^{{\prime}} nie jest implikantem

  • Np. funkcja

    f(x_{1},x_{2},x_{3})=(x_{1}+x_{2})(x_{2}+x3)

    posiada 2 implikanty pierwsze: f_{1}=x_{2} i f_{2}=x_{1}x_{3}

7.1.2. Problem dyskretyzacji

Dana jest niesprzeczna tablica decyzyjna \mathbb{S}=\left(U,A\cup\{ dec\}\right)

  • 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ęć {\bf P} nazywamy niesprzecznym z \mathbb{S} jeśli dla każdej pary obiektów x,y\in U takich, że d(x)\ne d(y) istnieje cięcie (a,c)\in{\bf P} rozróżniające x i y.

  • Zbiór cięć {\bf P}_{{opt}} nazywamy optymalnym dla \mathbb{S} jeśli {\bf P}_{{opt}} 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

    \chi^{2}=\sum _{{i=1}}^{2}\sum _{{j=1}}^{r}\frac{\left(n_{{ij}}-E_{{ij}}\right)^{2}}{E_{{ij}}}
  • <+-|alert@+> Z użyciem funkcji entropii;

    Gain\left(a;c;U\right)=Ent\left(U\right)-E\left(a;c;U\right)
  • <+-|alert@+> Gini's index

    G(a;c;U)=Gini(U)-\frac{|U_{L}|}{|U|}\cdot Gini(U_{L})-\frac{|U_{R}|}{|U|}\cdot Gini(U_{R})
  • 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 \mathbb{S}=\left(U,A\cup\{ dec\}\right)

  • Niech \bf C będzie zbiorem kandydujących cięć dla tablicy \mathbb{S};

  • Każde cięcie (a,c) jest skojarzone ze zmienną Boolowską p_{{(a,c)}};

  • Niech \psi _{{x,y}} będzie funkcją rozróżnialności dla x,y:

    \psi _{{x,y}}=\bigvee\{ p_{{(a,c)}}:(a,c)\text{ rozróżnia }x,y\}.
  • Funkcja boolowska

    \Psi _{\mathbb{S}}=\prod\{\psi _{{x,y}}:dec(x)\ne dec(y)\}

    koduje problem dyskretyzacji.

  • Minimalny implikant pierwszy \Psi _{\mathbb{S}} \Rightarrow optymalny zbiór cięć.

Ciecia kandydujące

(a,0.9);(a,1.15);(a,1.35);(a,1.5);\quad(b,0.75);(b,1.5);(b,2.5).

Oznaczmy przez p_{1}^{a},p_{2}^{a},p_{3}^{a},p_{4}^{a},\quad p_{1}^{b},p_{2}^{b},p_{3}^{b} zmienne Boolowskie odpowiadające cięciom. Wówczas

\begin{array}[]{ll}\psi\left(2,1\right)=p_{1}^{a}+p_{1}^{b}+p_{2}^{b};&\psi\left(2,4\right)=p_{2}^{a}+p_{3}^{a}+p_{1}^{b};\\
\psi\left(2,6\right)=p_{2}^{a}+p_{3}^{a}+p_{4}^{a}+p_{1}^{b}+p_{2}^{b}+p_{3}^{b};&\psi\left(2,7\right)=p_{2}^{a}+p_{1}^{b};\\
\psi\left(3,1\right)=p_{1}^{a}+p_{2}^{a}+p_{3}^{b};&\psi\left(3,4\right)=p_{2}^{a}+p_{2}^{b}+p_{3}^{b};\\
\psi\left(3,6\right)=p_{3}^{a}+p_{4}^{a};&\psi\left(3,7\right)=p_{2}^{b}+p_{3}^{b};\\
\psi\left(5,1\right)=p_{1}^{a}+p_{2}^{a}+p_{3}^{a};&\psi\left(5,4\right)=p_{2}^{b};\\
\psi\left(5,6\right)=p_{4}^{a}+p_{3}^{b};&\psi\left(5,7\right)=p_{3}^{a}+p_{2}^{b}.\end{array}

Funkcja kodująca problem dyskretyzacji

\small\begin{array}[]{cl}\Phi _{{\mathbb{S}}}=&\left(p_{1}^{a}+p_{1}^{b}+p_{2}^{b}\right)\left(p_{1}^{a}+p_{2}^{a}+p_{3}^{b}\right)\left(p_{1}^{a}+p_{2}^{a}+p_{3}^{a}\right)\left(p_{2}^{a}+p_{3}^{a}+p_{1}^{b}\right)\\
&p_{2}^{b}\left(p_{2}^{a}+p_{2}^{b}+p_{3}^{b}\right)\left(p_{2}^{a}+p_{3}^{a}+p_{4}^{a}+p_{1}^{b}+p_{2}^{b}+p_{3}^{b}\right)\left(p_{3}^{a}+p_{4}^{a}\right)\\
&\left(p_{4}^{a}+p_{3}^{b}\right)\left(p_{2}^{a}+p_{1}^{b}\right)\left(p_{2}^{b}+p_{3}^{b}\right)\left(p_{3}^{a}+p_{2}^{b}\right).\end{array}

Po sprowadzeniu do postaci DNF mamy:

\Phi _{{\mathbb{S}}}=p_{2}^{a}p_{4}^{a}p_{2}^{b}+p_{2}^{a}p_{3}^{a}p_{2}^{b}p_{3}^{b}+p_{3}^{a}p_{1}^{b}p_{2}^{b}p_{3}^{b}+p_{1}^{a}p_{4}^{a}p_{1}^{b}p_{2}^{b}.

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:

    disc(c,X)=conflict(X)-conflict(X_{L})-conflict(X_{R})

    gdzie conflict(X) = liczba par obiektów różnych decyzji w zbiorze X.

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

\mathbb{S}{}^{{*}} p_{1}^{a} p_{2}^{a} p_{3}^{a} p_{4}^{a} p_{1}^{b} p_{2}^{b} p_{3}^{b} d^{{*}}
(u_{1},u_{2}) 1 0 0 0 1 1 0 1
(u_{1},u_{3}) 1 1 0 0 0 0 1 1
(u_{1},u_{5}) 1 1 1 0 0 0 0 1
(u_{4},u_{2}) 0 1 1 0 1 0 0 1
(u_{4},u_{3}) 0 0 1 0 0 1 1 1
(u_{4},u_{5}) 0 0 0 0 0 1 0 1
(u_{6},u_{2}) 0 1 1 1 1 1 1 1
(u_{6},u_{3}) 0 0 1 1 0 0 0 1
(u_{6},u_{5}) 0 0 0 1 0 0 1 1
(u_{7},u_{2}) 0 1 0 0 1 0 0 1
(u_{7},u_{3}) 0 0 0 0 0 1 1 1
(u_{7},u_{5}) 0 0 1 0 0 1 0 1
new 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.