Zagadnienia

5.1 Wnioskowanie Boolowskie w obliczaniu reduktów i reguł decyzyjnych
- 5.1.1 Metody wnioskowań Boolowskich w szukaniu reduktów
- 5.1.2 Systemy decyzyjne oparte o zbiory przybliżone

5. Wnioskowanie Boolowskie w obliczaniu reduktów i reguł decyzyjnych

5.1. Wnioskowanie Boolowskie w obliczaniu reduktów i reguł decyzyjnych

5.1.1. Metody wnioskowań Boolowskich w szukaniu reduktów

5.1.1.1. Algebry Boola

\columns\column

9cm Algebra Boola Jest to struktura algebraiczna \definition

$\mathcal{B}=(B,+,\cdot,0,1)$

spełniająca następujące aksjomaty

- Przemienność:

$(a+b)=(b+a)\mbox{ oraz }$ $(a\cdot b)=(b\cdot a)$

- Rozdzielność:

$a\cdot(b+c)=(a\cdot b)+(a\cdot c),\mbox{ oraz}$ $a+(b\cdot c)=(a+b)\cdot(a+c)$

- Elementy neutralne:

$a+0=a\text{ oraz }a\cdot 1=a$

- Istnienie elementu komplementarnego:

$a+\overline{a}=1\mbox{ and }a\cdot\overline{a}=0$

*) Czasem negacja jest dodana do sygnatury algebry Boola.

<+-> Algebra zbiorów: $\mathbb{P}(X)=(2^{X},\cup,\cap,-,\emptyset,X)$ ;
<+-> Rachunek zdań

$(\{ zdania\ logiczne\},\vee,\wedge,\neg,\bot,\top)$
<+-> Binarna algebra Boola $\mathcal{B}_{2}=(\{ 0,1\},+,\cdot,0,1)$ to jest najmniejsza, ale najważniejsza algebra Boola w zastosowaniu.

$\begin{array}[]{c|c|c|c}x&y&x+y&x\cdot y\\ \hline 0&0&0&0\\ 0&1&1&0\\ 1&0&1&0\\ 1&1&1&1\\ \hline\end{array}\qquad\begin{array}[]{c|c}x&\neg x\\ \hline 0&1\\ 1&0\\ \end{array}$

Przykłady zastosowań:
- projektowanie układów scalonych;
- rachunek zdań.

Łączność (ang. Associative law):

$\qquad(x+y)+z=x+(y+z)\mbox{ oraz }(x\cdot y)\cdot z=x\cdot(y\cdot z)$

Idempotence:

$\qquad\qquad x+x=x\quad oraz\quad x\cdot x=x(dual)$

Działania z 0 i 1:

$\qquad x+1=1\quad oraz\quad x\cdot 0=0(dual)$

Pochłanienie (ang. Absorption laws):

$\qquad(y\cdot x)+x=x\quad oraz\quad(y+x)\cdot x=x(dual)$

Inwolocja (ang. Involution laws):

$\qquad\overline{(\overline{x})}=x$

Prawa DeMorgana (ang. DeMorgan's laws):

$\displaystyle\neg(x+y)$

$\displaystyle=\neg x\cdot\neg y\quad oraz\quad\neg(x\cdot y)=\neg x+\neg y(dual)$

Prawa konsensusu (ang. Consensus laws):

	$\displaystyle(x+y)\cdot(\overline{x}+z)\cdot(y+z)$	$\displaystyle=(x+y)\cdot(\overline{x}+z)\text{ oraz }$
	$\displaystyle(x\cdot y)+(\overline{x}\cdot z)+(y\cdot z)$	$\displaystyle=(x\cdot b)+(\overline{x}\cdot z)$

Zasada dualności:

Każda algebraiczna równość pozostaje prawdziwa jeśli zamieniamy operatory $+$ na $\cdot$ , $\cdot$ na $+$ , 0 na 1 oraz 1 na 0.

5.1.1.2. Funkcje Boolowskie i wnioskowanie Boolowskie

<+-> Każde odwzorowanie $f:\{ 0,1\}^{n}\rightarrow\{ 0,1\}$ nazywamy (zupełną) funkcją Boolowską.
<+-> Funkcje Boolowskie $\equiv$ formuły Boolowskie:
- Stałe, zmienne, operatory $\overline{\ }$ , $+$ oraz $.$
- Literały, mintermy (jednomiany), maxtermy, …
- Kanoniczna postać dyzjunkcyjna (DNF), np. $f=xy\overline{z}+x\overline{y}z+\overline{x}yz+xyz$ ;
- Kanoniczna postać koniunkcyjna (CNF), np. $f=(x+y+z)(\overline{x}+y)$
<+-> Term $t=x_{{i_{1}}}...x_{{i_{m}}}\overline{x_{{j_{1}}}}...\overline{x_{{j_{k}}}}$ nazywamy implikantem funkcji $f$ jeśli

$\forall _{{{\bf a}\in\{ 0,1\}^{n}}}\quad t({\bf a})=1\Rightarrow f({\bf a})=1$
<+-> Implikant pierwszy: jest to implikant, który przestaje nim być po usunięciu dowolnego literału.
<+-> Kanoniczna postać Blake'a: każdą funkcję Boolowską można przedstawić jako sumę wszystkich jej imlikantów pierwszych:

$f=t_{1}+t_{2}+...+t_{k}$

Wiele formuł reprezentuje tę samą funkcję;

$\phi _{1}=xy\overline{z}+x\overline{y}z+\overline{x}yz+xyz$

$\phi _{2}=(x+y+z)(\overline{x}+y+z)(x+\overline{y}+z)(x+y+\overline{z})$

$\phi _{3}=xy+xz+yz$

$xy\overline{z}$ jest implikantem

$xy$ jest implikantem pierwszym

$x$	$y$	$z$	$f$
0	0	0	0
1	0	0	0
0	1	0	0
1	1	0	1
0	0	1	0
1	0	1	1
0	1	1	1
1	1	1	1

<+-> Niech $\prec$ oznacza relację częściowego porządku w $\{ 0,1\}^{n}$
<+-> Funkcja $f$ jest monotoniczna (niemalejąca) wtw, gdy dla każdych ${\bf x,y}\in\{ 0,1\}^{n}$ jeśli $\bf x\prec y$ to $f({\bf x})\leq f({\bf y})$
<+-> monotoniczne funkcje Boolowskie można zapisać bez użycia negacji.
<+-> term $f^{{\prime}}=x_{{i_{1}}}\cdot x_{{i_{2}}}...\cdot 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}\wedge x_{3}$

Modelowanie: Kodowanie problemu za pomocą układu równań Boolowskich;
Redukcja: Sprowadzenie układu równań do pojedynczego równania postaci $f=0\quad\text{lub}\quad f=1$
Konstrukcja: Znalezienie wszystkich implikantów pierwszych funkcji $f$ (konstrukcja kanonicznej postaci Blake'a);
Dedukcja: Zastosowanie pewnej sekwencji wnioskowań transformujących implikanty pierwsze do rozwiązań problemu.

\columns\column

6cm <1-> \onslide

Problem:

$A,B,C,D$ are considering going to a party. Social constrains:

If A goes than B won't go and C will;
If B and D go, then either A or C (but not both) will go
If C goes and B does not, then D will go but A will not.

\onslide

<2-> Problem modeling:

$\displaystyle\scriptsize A\rightarrow\overline{B}\wedge C$	$\displaystyle\leftrightsquigarrow A(B+\overline{C})$	$\displaystyle=0$
$\displaystyle...$	$\displaystyle\leftrightsquigarrow BD(AC+\overline{AC})$	$\displaystyle=0$
$\displaystyle...$	$\displaystyle\leftrightsquigarrow\overline{B}C(A+\overline{D})$	$\displaystyle=0$

\column

6cm

<3-> After reduction:

$f=A(B+\overline{C})+BD(AC+\overline{AC})+\overline{B}C(A+\overline{D})=0$
<4-> Blake Canonical form: $f=B\overline{C}D+\overline{B}C\overline{D}+A=0$
<5-> Facts:

$\displaystyle BD$ $\displaystyle\longrightarrow C$

$\displaystyle C$ $\displaystyle\longrightarrow B\vee D$

$\displaystyle A$ $\displaystyle\longrightarrow 0$
<6-> Reasoning: (theorem proving)

e.g., show that

”nobody can go alone.”

\columns\column

7cm

<+-> Problem SAT: czy równanie

$f(x_{1},...,x_{n})=1$

posiada rozwiązanie?
<+-> SAT odgrywa ważną rolę w teorii złożoności (twierdzenie Cooka, dowodzenie NP-zupełności …)
<+-> Każdy SAT-solver może być używany do rozwiązywania problemu planowania.
<+-> Blocks world problem: Po redukcji formuła boolowska nadal zawiera $O(tk^{2})$ zmiennych i $O(tk^{3})$ klauzuli ( $k,t$ - liczby bloków i kroków).
<+-> Np. Dla $k=15$ , $t=14$ , mamy 3016 zmiennych i 50457 klausuli

\column

5cm<4->\only

\only

<3->

<+-> Konstrukcja funkcji odróżnialności:
- Zmienne boolowskie: atrybuty $a_{1},...,a_{k}$ ;
- Klauzula:
  
  $\phi _{{u,v}}=\bigvee\{ a\in A:a(u)\neq a(v)\}$
- Funkcja rozróżnialności:
  
  $\mathcal{F}_{{\mathbb{S}}}(a_{1},...,a_{k})=\bigwedge _{{x,y\in U:dec(x)\neq dec(y)}}\phi _{{x,y}}(a_{1},...,a_{k})$
<+-> przekształcenie funkcji rozróżnialności do postaci DNF
<+-> każdy implikant pierwszy odpowiada jednemu reduktowi;

Hurt.	Jakość obsługi	Jakość towaru	Obok autostrady?	Centrum?	decyzja
ID	$a_{1}$	$a_{2}$	$a_{3}$	$a_{4}$	$dec$
1	dobra	dobra	nie	nie	strata
2	dobra	dobra	nie	tak	strata
3	bdb	dobra	nie	nie	zysk
4	slaba	super	nie	nie	zysk
5	slaba	niska	tak	nie	zysk
6	slaba	niska	tak	tak	strata
7	bdb	niska	tak	tak	zysk
8	dobra	super	nie	nie	strata
9	dobra	niska	tak	nie	zysk
10	slaba	super	tak	nie	zysk
11	dobra	super	tak	tak	zysk
12	bdb	super	nie	tak	zysk
13	bdb	dobra	tak	nie	?
14	slaba	super	nie	tak	?

$\mathbb{M}$	1	2	6	8
3	$a_{1}$	$a_{1},a_{4}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{1},a_{2}$
4	$a_{1},a_{2}$	$a_{1},a_{2},a_{4}$	$a_{2},a_{3},a_{4}$	$a_{1}$
5	$a_{1},a_{2},a_{3}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{4}$	$a_{1},a_{2},a_{3}$
7	$a_{1},a_{2},a_{3},a_{4}$	$a_{1},a_{2},a_{3}$	$a_{1}$	$a_{1},a_{2},a_{3},a_{4}$
9	$a_{2},a_{3}$	$a_{2},a_{3},a_{4}$	$a_{1},a_{4}$	$a_{2},a_{3}$
10	$a_{1},a_{2},a_{3}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{2},a_{4}$	$a_{1},a_{3}$
11	$a_{2},a_{3},a_{4}$	$a_{2},a_{3}$	$a_{1},a_{2}$	$a_{3},a_{4}$
12	$a_{1},a_{2},a_{4}$	$a_{1},a_{2}$	$a_{1},a_{2},a_{3}$	$a_{1},a_{4}$

$\displaystyle f$	$\displaystyle=$	$\displaystyle(\alpha _{1})(\alpha _{1}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{4})$
		$\displaystyle(\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3})(\alpha _{4})(\alpha _{2}\vee\alpha _{3})(\alpha _{2}\vee\alpha _{4})$
		$\displaystyle(\alpha _{1}\vee\alpha _{3})(\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{4})$

$\displaystyle f$	$\displaystyle=$	$\displaystyle(\alpha _{1})(\alpha _{1}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{4})$
		$\displaystyle(\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3})(\alpha _{4})(\alpha _{2}\vee\alpha _{3})(\alpha _{2}\vee\alpha _{4})$
		$\displaystyle(\alpha _{1}\vee\alpha _{3})(\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{4})$

<+-> usuwanie alternatyw regułą pochłaniania (t.j. $p\wedge(p\vee q)\equiv p$ ):

$\displaystyle f$ $\displaystyle=$ $\displaystyle(\alpha _{1})(\alpha _{4})(\alpha _{2}\vee\alpha _{3})$
<+-> sprowadzanie funkcji $f$ z postaci CNF (koniunkcja alternatyw) do postaci DNF (alternatywa koniunkcji)

$\displaystyle f$ $\displaystyle=$ $\displaystyle\alpha _{1}\alpha _{4}\alpha _{2}\vee\alpha _{1}\alpha _{4}\alpha _{3}$
<+-> Każdy składnik jest reduktem! Zatem mamy 2 redukty: $R_{1}=\{ A_{1},A_{2},A_{4}\}$ i $R_{2}=\{ A_{1},A_{3},A_{4}\}$

5.1.1.3. Heurystyka Johnsona

<+-> Atrybut jest ważniejszy jeśli częściej występuje w klauzulach;
<+-> Selekcja: W każdym kroku wybierzmy atrybut, który najczęściej występuje w funkcji rozróżnialności;
<+-> Usuwanie: Usuwamy z tej funkcji te klauzule, które zawierają wybrany atrybut;
<+-> Powtarzamy Selekcja i Usuwanie dopóty, póki funkcja rozróżnialności zawiera jeszcze jakąś klazulę.

Heurystyka Johnsona

Znaleźć atrybut, który występuje najczęściej w macierzy rozróżnialności;
Usuwnąć wszystkie pola zawierające wybrany atrybut;
Powtarzamy kroki 1 i 2 dopóki wszystkie pola macierzy są puste.

$\mathbb{M}$	1	2	6	8
3	$a_{1}$	$a_{1},a_{4}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{1},a_{2}$
4	$a_{1},a_{2}$	$a_{1},a_{2},a_{4}$	$a_{2},a_{3},a_{4}$	$a_{1}$
5	$a_{1},a_{2},a_{3}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{4}$	$a_{1},a_{2},a_{3}$
7	$a_{1},a_{2},a_{3},a_{4}$	$a_{1},a_{2},a_{3}$	$a_{1}$	$a_{1},a_{2},a_{3},a_{4}$
9	$a_{2},a_{3}$	$a_{2},a_{3},a_{4}$	$a_{1},a_{4}$	$a_{2},a_{3}$
10	$a_{1},a_{2},a_{3}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{2},a_{4}$	$a_{1},a_{3}$
11	$a_{2},a_{3},a_{4}$	$a_{2},a_{3}$	$a_{1},a_{2}$	$a_{3},a_{4}$
12	$a_{1},a_{2},a_{4}$	$a_{1},a_{2}$	$a_{1},a_{2},a_{3}$	$a_{1},a_{4}$

W macierzy nierozróznialności z poprzedniego przykładu

$\qquad$ $a_{1}$ - występuje 23 razy $\qquad$ $a_{2}$ - występuje 23 razy

$\qquad$ $a_{3}$ - występuje 18 razy $\qquad$ $a_{4}$ - występuje 16 razy
Jeśli wybieramy $a_{1}$ , to po usunięciu pól zawierających $a_{1}$ zostało 9 niepustych pól macierzy nierozróżnialności. Wśród nich:

$a_{2}$ - występuje 7 razy $\quad$ $a_{3}$ - występuje 7 razy $\quad$ $a_{4}$ - występuje 6 razy
Jeśli wybieramy tym razem $a_{2}$ to zostały 2 niepuste pola i wśród nich $a_{4}$ jest zdecydowanym faworytem.
Możemy dostać w ten sposób redukt: $R_{1}=\{ a_{1},a_{2},a_{4}\}$ .

Niech $X=\{(u,v)\in U^{2}:dec(u)\neq dec(v)\}$ ;
Niech $S_{{a_{i}}}=\{(u,v)\in X:a_{i}(u)\neq a_{i}(v)\}$ ;
Niech $C^{{*}}\subset A$ będzie minimalnym reduktem, lecz $C=\{ a_{1},...,a_{k}\}$ będzie reduktem znalezionym przez heurystykę Johnsona;
Załóżmy, że heurystyka Johnsona musi płacić 1zł za każdym razem, gdy dodała ${a_{i}}$ do $C$ .
Rozłóżmy ten koszt tym elementom, które zostały po raz pierwszy pokryte przez zbiór $S_{{a_{i}}}$
Niech $c_{x}$ = koszt ponoszony przez $x$ . Jeśli $x$ jest pokryty po raz pierwszy przez $a_{i}$ , to

$c_{x}=\frac{1}{|S_{{a_{i}}}-(S_{{a_{1}}}\cup...\cup S_{{a_{{i-1}}}})|}$

Heurystyka Johnsona ponosi łączny koszt $=|C|$ . Mamy

$|C|=\sum _{{x\in X}}c_{x}\leq\sum _{{a\in C^{*}}}\sum _{{x\in S_{{a}}}}c_{x}$
Gdybyśmy pokazali, że dla dowolnego altrybutu $a\in A$

$\sum _{{x\in S_{{a}}}}c_{x}\leq H(|S_{{a}}|)$

gdzie $H(n)=\sum _{{i=1}}^{n}\frac{1}{i}$ , wówczas możemy oszacować dalej:

$\displaystyle|C|$ $\displaystyle\leq\sum _{{a\in C*}}\sum _{{x\in S_{{a}}}}c_{x}\leq|C^{*}|\cdot H(\max\{|S_{{a}}:a\in A|\})$

$\displaystyle\leq|C^{*}|\cdot H(|X|)\leq|C^{*}|\cdot\ln(|X|+1)$

Lemat:

Dla dowolnego altrybutu $a\in A$

$\sum _{{x\in S_{{a}}}}c_{x}\leq H(|S_{{a}}|)$

Dowód:

Niech $u_{i}=|S_{a}-(S_{{a_{1}}}\cup...\cup S_{{a_{{i-1}}}})|$ , mamy:

$u_{0}=|S_{a}|\geq...\geq u_{{i-1}}\geq u_{i}\geq...\geq u_{k}=0;$

gdzie $k$ jest najmniejszym indeksem t., że $S_{a}=S_{{a_{1}}}\cup...\cup S_{{a_{k}}}$
Zatem

$\displaystyle\sum _{{x\in S_{a}}}{c_{x}}$ $\displaystyle=\sum _{{i=0}}^{k}(u_{{i-1}}-u_{i})\cdot\frac{1}{|S_{{a_{i}}}-(S_{{a_{1}}}\cup...\cup S_{{a_{{i-1}}}})|}$

$\displaystyle\leq\sum _{{i=0}}^{k}(u_{{i-1}}-u_{i})\cdot\frac{1}{u_{{i-1}}}\leq\sum _{{i=0}}^{k}(H(u_{{i-1}})-H(u_{i}))=H(|S_{a}|)$

5.1.1.4. Inne heurystyki

ILP (Integer Linear Program)
Symulowane wyżarzanie (simulated annealing)
Algorytmy genetyczne
SAT solver
???

Dana jest funkcja $f:\{ 0,1\}^{n}\rightarrow\{ 0,1\}$ zapisana w postaci CNF za pomocą zmiennych $x_{1},...,x_{n}$

Utwórz nowe zmienne $\{ y_{1},...,y_{{2n}}\}$ odpowiadające literałom $x_{1},\overline{x_{1}},...,x_{n},\overline{x_{n}}$ ;
Dla każdej zmiennej $x_{i}$ , utwórzmy nierówność $y_{{2i-1}}+y_{{2i}}\leq 1$
Zamień każdą klausulę $\omega _{i}=(l_{{i_{1}}}\vee...\vee l_{{i_{{n_{i}}}}})$ na nierówność $y_{{i_{1}}}+...+y_{{i_{{n_{i}}}}}\geq 1$ ;
Utwórzmy układ nierówności z poprzednich punktów:

$\mathbf{A}\mathbf{y}\geq\mathbf{b}$
Zagadnienie programowania liniowego liczb całkowitych (ILP) jest definiowane jako problem szukania

$\min\sum _{{i=1}}^{{n}}y_{i}\quad\text{ przy ograniczeniu: }\mathbf{A}\mathbf{y}\geq\mathbf{b}.$

5.1.2. Systemy decyzyjne oparte o zbiory przybliżone

5.1.2.1. Reguły decyzyjne

Dla danego zbioru atrybutów $A$ definiujemy język deskryptorów jako trójkę

$\mathcal{L}(A)=(\mathbf{D},\{\vee,\wedge,\neg\},\mathbf{F})$

gdzie

$\mathbf{D}$ jest zbiorem deskryptorów

$\mathbf{D}=\{(a=v):a\in A\text{ and }v\in Val_{a}\};$
$\{\vee,\wedge,\neg\}$ jest zbiorem standardowych operatorów logicznych;
$\mathbf{F}$ jest zbiorem formuł logicznych zbudowanych na deskryptorach z $\mathbf{D}$ .
Dla każdego zbioru atrybutów $B\subseteq A$ oznaczamy:

$\mathbf{D}|_{B}=\{(a=v):a\in B\text{ and }v\in Val_{a}\}$ , czyli zbiór deskryptorów obciętych do $B$ .

$\mathbf{F}|_{B}$ zbiór formuł zbudowanych na $\mathbf{D}|_{B}$ .

Semantyka:

Niech $\mathbb{S}=(U,A)$ będzie tablicą informacyjną. Każda formuła $\phi\in\mathbf{F}$ , jest (semantycznie) skojarzona ze zbiorem $[[\phi]]_{{\mathbb{S}}}$ zawierającym obiekty spełniające $\phi$ .

Formalnie możemy indukcyjnie definiować semantykę jak następująco:

$\displaystyle[[(a=v)]]_{{\mathbb{S}}}$	$\displaystyle=\{ x\in U:a(x)=v\}$	(5.1)
$\displaystyle[[\phi _{1}\vee\phi _{2}]]_{{\mathbb{S}}}$	$\displaystyle=[[\phi _{1}]]_{{\mathbb{S}}}\cup[[\phi _{2}]]_{{\mathbb{S}}}$	(5.2)
$\displaystyle[[\phi _{1}\wedge\phi _{2}]]_{{\mathbb{S}}}$	$\displaystyle=[[\phi _{1}]]_{{\mathbb{S}}}\cap[[\phi _{2}]]_{{\mathbb{S}}}$	(5.3)
$\displaystyle[[\neg\phi]]_{{\mathbb{S}}}$	$\displaystyle=U\setminus[[\phi]]_{{\mathbb{S}}}$	(5.4)

Każda formuła $\phi$ może być charakteryzowana przez:

$length(\phi)=$ liczba deskryptorów w $\phi$ ;
$support(\phi)=|[[\phi]]_{{\mathbb{S}}}|=$ liczba obiektów spełniających formułę

\definition

Definicja reguł decyzyjnych Niech $\mathbb{S}=\{ U,A\cup\{ dec\}\}$ będzie tablicą decyzyjną. Regułą decyzyjną dla $\mathbb{S}$ nazywamy formuły postaci:

$\phi\Rightarrow\delta$

gdzie $\phi\in\mathbf{F}_{A}$ i $\delta\in\mathbf{F}_{{dec}}$ .

Formułę $\phi$ nazywamy poprzednikiem (lub założeniem) reguły $\mathbf{r}$ , a $\delta$ nazywamy następnikiem (lub tezą) reguły $\mathbf{r}$ .

Oznaczamy poprzednik i następnik reguły $\mathbf{r}$ przez $prev(\mathbf{r})$ oraz $cons(\mathbf{r})$ .

\definition

Reguły atomowa: Są to reguły postaci:

$\mathbf{r}\equiv(a_{{i_{1}}}=v_{1})\wedge...\wedge(a_{{i_{m}}}=v_{m})\Rightarrow(dec=k)$

(5.5)

Każda reguła decyzyjna ${\bf r}$ postaci (5.5) może być charakteryzowana następującymi cechami:

$length({\bf r})$ =	liczba deskryptorów występujących w założeniu reguły ${\bf r}$
$[{\bf r}]$ =	nośnik reguły ${\bf r}$ , czyli zbiór obiektów z $U$ spełniających założenie reguły ${\bf r}$
$support({\bf r})$ =	liczba obiektów z $U$ spełniających założenie reguły ${\bf r}$ : $support({\bf r})=card([{\bf r}])$
$confidence({\bf r})$ =	wiarygodność reguły ${\bf r}$ : $confidence({\bf r})=\frac{\|[{\bf r}]\cap DEC_{k}\|}{\|[{\bf r}]\|}$

Mówimy, że reguła ${\bf r}$ jest niesprzeczna z $\mathbb{A}$ jeśli

$confidence({\bf r})=1$

\definition

Minimalne niesprzeczne reguły: Niech $\mathbb{S}=(U,A\cup\{ dec\})$ będzie daną tablicą decyzyjną. Niesprzeczną regułę

$(a_{{i_{1}}}=v_{1})\wedge...\wedge(a_{{i_{m}}}=v_{m})\Rightarrow(dec=k)$

nazywamy minimalną niesprzeczną regułą decyzyjną jeśli usunięcie któregokolwiek z deskryptorów spowoduje, że reguła przestaje być niesprzezcna z $\mathbb{S}$ .

5.1.2.2. Regułowe systemy decyzyjne

Klasyfikatory regułowe dzialają w trzech fazach:

Faza treningu: Generuje pewien zbiór reguł $RULES({\mathbb{A}})$ z danej tablicy decyzyjnej $\mathbb{A}$ .
Faza selekcji reguł: Szuka w $RULES({\mathbb{A}})$ tych reguł, które są wspierane przez obiekt $x$ . Oznaczamy zbiór tych reguł przez $MatchRules({\mathbb{A}},x)$ .
Faza klasyfikacji: wyznacza klasędecyzyjną dla $x$ za pomocą reguł z $MatchRules({\mathbb{A}},x)$ według następującego schematu:
1. Jeśli $MatchRules({\mathbb{A}},x)$ jest pusty: odpowiedź dla $x$ jest $``NIEWIEM^{{\prime\prime}}$ , tzn. nie mamy podstaw, aby klasyfikować obiekt $x$ do którejkolwiek z klas;
2. Jeśli $MatchRules({\mathbb{A}},x)$ zawiera tylko obiekty z $k$ -tej klasy: wówczas $dec(x)=k$ ;
3. Jeśli $MatchRules({\mathbb{A}},x)$ zawiera reguły dla różnych klas decyzyjnych: wówczas decyzja dla $x$ określimy za pomocą pewnego, ustalonego schematu głosowania między regułami z $MatchRules({\mathbb{A}},x)$ .

5.1.2.3. Szukanie minimalnych reguł decyzyjnych

Każda reguła powstaje poprzez skracanie opisu jakiegoś obiektu.
Redukty lokalne
Te same heurystyki dla reduktów decyzyjnych.

Hurt.	Jakość obsługi	Jakość towaru	Obok autostrady?	Centrum?	decyzja
ID	$a_{1}$	$a_{2}$	$a_{3}$	$a_{4}$	$dec$
1	dobra	dobra	nie	nie	strata
2	dobra	dobra	nie	tak	strata
3	bdb	dobra	nie	nie	zysk
4	slaba	super	nie	nie	zysk
5	slaba	niska	tak	nie	zysk
6	slaba	niska	tak	tak	strata
7	bdb	niska	tak	tak	zysk
8	dobra	super	nie	nie	strata
9	dobra	niska	tak	nie	zysk
10	slaba	super	tak	nie	zysk
11	dobra	super	tak	tak	zysk
12	bdb	super	nie	tak	zysk
13	bdb	dobra	tak	nie	?
14	slaba	super	nie	tak	?

$\mathbb{M}$	1	2	6	8
3	$a_{1}$	$a_{1},a_{4}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{1},a_{2}$
4	$a_{1},a_{2}$	$a_{1},a_{2},a_{4}$	$a_{2},a_{3},a_{4}$	$a_{1}$
5	$a_{1},a_{2},a_{3}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{4}$	$a_{1},a_{2},a_{3}$
7	$a_{1},a_{2},a_{3},a_{4}$	$a_{1},a_{2},a_{3}$	$a_{1}$	$a_{1},a_{2},a_{3},a_{4}$
9	$a_{2},a_{3}$	$a_{2},a_{3},a_{4}$	$a_{1},a_{4}$	$a_{2},a_{3}$
10	$a_{1},a_{2},a_{3}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{2},a_{4}$	$a_{1},a_{3}$
11	$a_{2},a_{3},a_{4}$	$a_{2},a_{3}$	$a_{1},a_{2}$	$a_{3},a_{4}$
12	$a_{1},a_{2},a_{4}$	$a_{1},a_{2}$	$a_{1},a_{2},a_{3}$	$a_{1},a_{4}$

$\displaystyle f_{{u_{3}}}$

$\displaystyle=$

$\displaystyle(\alpha _{1})(\alpha _{1}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{2})=\alpha _{1}$

Reguły:

$(a_{1}=\text{bdb})\implies dec=\text{zysk}$

$\mathbb{M}$	1	2	6	8
3	$a_{1}$	$a_{1},a_{4}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{1},a_{2}$
4	$a_{1},a_{2}$	$a_{1},a_{2},a_{4}$	$a_{2},a_{3},a_{4}$	$a_{1}$
5	$a_{1},a_{2},a_{3}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{4}$	$a_{1},a_{2},a_{3}$
7	$a_{1},a_{2},a_{3},a_{4}$	$a_{1},a_{2},a_{3}$	$a_{1}$	$a_{1},a_{2},a_{3},a_{4}$
9	$a_{2},a_{3}$	$a_{2},a_{3},a_{4}$	$a_{1},a_{4}$	$a_{2},a_{3}$
10	$a_{1},a_{2},a_{3}$	$a_{1},a_{2},a_{3},a_{4}$	$a_{2},a_{4}$	$a_{1},a_{3}$
11	$a_{2},a_{3},a_{4}$	$a_{2},a_{3}$	$a_{1},a_{2}$	$a_{3},a_{4}$
12	$a_{1},a_{2},a_{4}$	$a_{1},a_{2}$	$a_{1},a_{2},a_{3}$	$a_{1},a_{4}$

$\displaystyle f_{{u_{8}}}$	$\displaystyle=$	$\displaystyle(\alpha _{1}\vee\alpha _{2})(\alpha _{1})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3})(\alpha _{1}\vee\alpha _{2}\vee\alpha _{3}\vee\alpha _{4})(\alpha _{2}\vee\alpha _{3})$
		$\displaystyle(\alpha _{1}\vee\alpha _{3})(\alpha _{3}\vee\alpha _{4})(\alpha _{1}\vee\alpha _{4})$
	$\displaystyle=$	$\displaystyle\alpha _{1}(\alpha _{2}\vee\alpha _{3})(\alpha _{3}\vee\alpha _{4})=\alpha _{1}\alpha _{3}\vee\alpha _{1}\alpha _{2}\alpha _{4}$

Reguły:

$(a_{1}=\text{dobra})\wedge(a_{3}=\text{nie})\implies dec=\text{strata}$
$(a_{1}=\text{dobra})\wedge(a_{2}=\text{super})\wedge(a_{4}=nie)\implies dec=\text{strata}$

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

	$\displaystyle BD$	$\displaystyle\longrightarrow C$
	$\displaystyle C$	$\displaystyle\longrightarrow B\vee D$
	$\displaystyle A$	$\displaystyle\longrightarrow 0$

	$\displaystyle\|C\|$	$\displaystyle\leq\sum _{{a\in C}}\sum _{{x\in S_{{a}}}}c_{x}\leq\|C^{}\|\cdot H(\max\{\|S_{{a}}:a\in A\|\})$
		$\displaystyle\leq\|C^{}\|\cdot H(\|X\|)\leq\|C^{}\|\cdot\ln(\|X\|+1)$

	$\displaystyle\sum _{{x\in S_{a}}}{c_{x}}$	$\displaystyle=\sum _{{i=0}}^{k}(u_{{i-1}}-u_{i})\cdot\frac{1}{\|S_{{a_{i}}}-(S_{{a_{1}}}\cup...\cup S_{{a_{{i-1}}}})\|}$
		$\displaystyle\leq\sum _{{i=0}}^{k}(u_{{i-1}}-u_{i})\cdot\frac{1}{u_{{i-1}}}\leq\sum _{{i=0}}^{k}(H(u_{{i-1}})-H(u_{i}))=H(\|S_{a}\|)$