Zagadnienia

7.1 Problem dyskretyzacji

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,y$ są rozróż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śli $dec(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

Lokalne a globalne metody:
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
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.

Systemy decyzyjne