Zagadnienia

4.1 Zbiory przybliżone
- 4.1.1 Wprowadzenie do teorii zbiorów przybliżonych
  - 4.1.1.1 Systemy informacyjne i tablice decyzyjne
  - 4.1.1.2 Redukty
- 4.1.2 Złożoność problemu szukania reduktów

4. Zbiory przybliżone

4.1. Zbiory przybliżone

4.1.1. Wprowadzenie do teorii zbiorów przybliżonych

4.1.1.1. Systemy informacyjne i tablice decyzyjne

Teoria zbiorów przybliżonych została wprowadzona w latach 80-tych przez prof. Zdzisława Pawlaka.
Głównym celem jest dostarczanie narzędzi dla problemu aproksymacji pojęć (zbiorów).
Zastosowania w systemach decyzyjnych:
- Redukcja danych, selekcja ważnych atrybutów;
- Generowanie reguł decyzyjnych;
- Odkrywanie wzorców z danych: szablony, reguły asocjacyjne;
- Odkrywanie zależności w danych.

\block

Definicja Jest to para $\mathbb{S}=(U,A)$ , gdzie

$U$ – skończony niepusty zbiór obiektów (ang. cases, states, patients, observations …);
$A$ – skończony, niepusty zbiór atrybutów. Każdy $a\in A$ odpowiada pewnej funkcji $a:U\rightarrow V_{a}$ zwanej wartościowaniem, gdzie $V_{a}$ jest nazwana dziedziną atrybutu $a$ .

Dla $B\subseteq A$ , definiujemy

$B$ -sygnatura obiektu $x\in U$ (ang. $B$ -information vector) jako

${inf}_{B}(x)=\{(a,a(x)):a\in B\}$
Zbiór sygnatur względem $B$ o obiektach z $U$ (ang. $B$ -information set):

$INF(\mathbb{S})=\{ inf_{B}(x):x\in U\}$

Tablica decyzyjna powstaje ze zwykłych tablic danych poprzez sprecyzowanie:

Atrybutów (nazwanych warunkowymi): cechy, których wartości na obiektach są dostępne, np. pomiary, parametry, dane osobowe, …
Decyzji (atrybut decyzyjny):, t.j. cecha “ukryta” związana z pewną znaną częściowo wiedzą o pewnym pojęciu:
- Decyzja jest znana tylko dla obiektów z (treningowej) tablicy decyzyjnej;
- Jest podana przez eksperta (np. lekarza) lub na podstawie późniejszych obserwacji (np. ocena giełdy);
- Chcemy podać metodę jej wyznaczania dla dowolnych obiektów na podstawie wartości atrybutów warunkowych na tych obiektach.

\columns\column

4.5cm Przedstawiona tablica decyzyjna zawiera:

8 obiektów będących opisami pacjentów
3 atrybuty: Headache Muscle pain, Temp.
Decyzję stwierdzącą czy pacjent jest przeziębiony czy też nie. lub nie

\column

8cm \example

$U$	Ból głowy	Ból mięśni	Temp.	Grypa
p1	Tak	Tak	N	Nie
p2	Tak	Tak	H	Tak
p3	Tak	Tak	VH	Tak
p4	Nie	Tak	N	Nie
p5	Nie	Nie	H	Nie
p6	Nie	Tak	VH	Tak
p7	Nie	Tak	H	Tak
p8	Nie	Nie	VH	Nie

Dane są obiekty $x,y\in U$ i 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)$ ;
$x,y$ są nierozróżnialne przez $B$ , jeśli one są identyczne na $B$ , tzn. $a(x)=a(y)$ dla każdego $a\in B$ ;
$[x]_{B}$ = zbiór obiektów nierozróżnialnych z $x$ przez $B$ .

Dla każdych obiektów $x,y$ :
- albo $[x]_{B}=[y]_{B}$ ;
- albo $[x]_{B}\cap[y]_{B}=\emptyset$ .
Relacja

$x\ IND_{B}\ y:=x,y\text{ są nierozróżnialne przez }B$

jest relacją równoważności.
Każdy zbiór atrybutów $B\subset A$ wyznacza podział zbioru obiektów na klasy nierozróżnialności.

Dla $B=\{ Bólgłowy,Bólmięśni\}$

\columns\column

4.5cm

obiekty $p1,p2,p3$ są nierozróżnialne;
są 3 klasy nierozróżnialności relacji $IND_{B}$ :
- $[p1]_{B}=\{ p1,p2,p3\}$
- $[p4]_{B}=\{ p4,p6,p7\}$
- $[p5]_{B}=\{ p5,p8\}$

\column

8cm \example

$U$	Ból głowy	Ból mięśni	Temp.	Grypa
p1	Tak	Tak	N	Nie
p2	Tak	Tak	H	Tak
p3	Tak	Tak	VH	Tak
p4	Nie	Tak	N	Nie
p5	Nie	Nie	H	Nie
p6	Nie	Tak	VH	Tak
p7	Nie	Tak	H	Tak
p8	Nie	Nie	VH	Nie

Każdy zbiór obiektów $X$ (np. klasa decyzyjna, pojęcie) może być opisany za pomocą atrybutów ze zbioru $B$ dokładnie lub w przybliżeniu
- dokładny opis: jeśli $X$ jest sumą pewnych klas nierozróznialności definiowanych przez $B$ (ZBIORY DOKŁADNE)
- przybliżony opis: w przeciwnym przypadku (ZBIORY PRZYBLIŻONE)
W obu przypadkach $X$ może być opisany przez 2 “dokładne zbiory” zwane dolną i górną aproksymacją zbioru $X$

$\underline{B}(X)=\{ x:[x]_{B}\subset X\}\quad\overline{B}(X)=\{ x:[x]_{B}\cap X\neq\emptyset\}$

Obszar brzegowy (ang. $B$ -boundary region) pojęcia $X$ zawiera obiekty, dla których nie możemy jednoznacznie zdecydować czy należą one do $X$ czy nie na podstawie atrybutów z $B$
Obszar wewnętrzny (ang. $B$ -inside region of X) zawiera obiekty, które możemy pewnie klasyfikować jako elementy pojęcia $X$ mając do dyspozycji atrybuty z $B$ .
Zbiór jest przybliżony (ang. rough set) jeśli obszar brzegowy jest niepusty, w przeciwnym przypadku zbiór jest nazwany dokładny (ang. crisp set).

\columns\column

6cmNiech $B=\{ a_{1},a_{2}\}$ <2-> \onslide

$\displaystyle IND(B)=\{$	$\displaystyle\{ 1,2\},$	$\displaystyle(sunny,hot)$
	$\displaystyle\{ 3,13\},$	$\displaystyle(overcast,hot)$
	$\displaystyle\{ 4,10,14\},$	$\displaystyle(rainy,mild)$
	$\displaystyle\{ 5,6\},$	$\displaystyle(rainy,cool)$
	$\displaystyle\{ 8,11\},$	$\displaystyle(sunny,mild)$
	$\displaystyle\{ 7\},\{ 9\},\{ 12\}\}$

\onslide

<3-> Chcemy aproksymować pojęcie definiowane przez klasę decyzyjną (play=no)

$X=CLASS_{{no}}=\{ 1,2,6,8,14\}$

\onslide

<4-> Aproksymacje pojęcia $X$ :

	$\displaystyle\mathbf{L}_{B}(X)$	$\displaystyle=\{ 1,2\}$
	$\displaystyle\mathbf{U}_{B}(X)$	$\displaystyle=\{ 1,2,{5},6,8,{11},{4},{10},14\}$

\onslide

<5-> Reguła pewna:

$\textbf{If }B(x)=(sunny,hot)\textbf{ then }d(x)={no}$

\column

5.4cm \onslide<1->

${\mathbb{A}}$ $\hfil\mid$	$a_{1}$	$a_{2}$	$a_{3}$	$a_{4}$ $\hfil\mid$	$d$
ID $\hfil\mid$	outlook	temp.	hum.	windy $\hfil\mid$	play
1 $\hfil\mid$	sunny	hot	high	FALSE $\hfil\mid$	no
2 $\hfil\mid$	sunny	hot	high	TRUE $\hfil\mid$	no
3 $\hfil\mid$	overcast	hot	high	FALSE $\hfil\mid$	yes
4 $\hfil\mid$	rainy	mild	high	FALSE $\hfil\mid$	yes
5 $\hfil\mid$	rainy	cool	normal	FALSE $\hfil\mid$	yes
6 $\hfil\mid$	rainy	cool	normal	TRUE $\hfil\mid$	no
7 $\hfil\mid$	overcast	cool	normal	TRUE $\hfil\mid$	yes
8 $\hfil\mid$	sunny	mild	high	FALSE $\hfil\mid$	no
9 $\hfil\mid$	sunny	cool	normal	FALSE $\hfil\mid$	yes
10 $\hfil\mid$	rainy	mild	normal	FALSE $\hfil\mid$	yes
11 $\hfil\mid$	sunny	mild	normal	TRUE $\hfil\mid$	yes
12 $\hfil\mid$	overcast	mild	high	TRUE $\hfil\mid$	yes
13 $\hfil\mid$	overcast	hot	normal	FALSE $\hfil\mid$	yes
14 $\hfil\mid$	rainy	mild	high	TRUE $\hfil\mid$	no

\onslide

<5-> Reguły przybliżone:

		$\displaystyle\textbf{If }B(x)=(rainy,cool)\textbf{ then }d(x)={no}$
		$\displaystyle\textbf{If }B(x)=(rainy,mild)\textbf{ then }d(x)={no}$
		$\displaystyle\textbf{If }B(x)=(sunny,mild)\textbf{ then }d(x)={no}$

\block

Jakość aproksymacji (ang. accuracy of approximation)

$\alpha _{B}(X)=\frac{|\underline{B}(X)|}{|\overline{B}(X)|}$

$0\leq\alpha _{B}(X)\leq 1$
Jeśli $\alpha _{B}(X)=1$ , to zbiór $X$ jest dokładnie definiowany przez $B$ ;
Jeśli $\alpha _{B}(X)<1$ , to zbiór $X$ jest aproksymacyjnie definiowany przez $B$ ;

4.1.1.2. Redukty

W systemach decyzyjnych, nie wszystkie atrybuty są potrzebne do procesie podejmowania decyzji;
Chcemy wybrać pewne podzbiory atrybutów niezbędnych do tego celu;
Redukty to minimalne podzbiory atrybutów zachowujących charakterystykę całego zbioru atrybutów.
W teorii zbiorów przybliżonych, istnieją co najmniej 2 pojęcia reduktów: informacyjne i decyzyjne.

\block

Definicja reduktu informacyjnego Zbiór atrybutów $B\subset A$ nazywamy reduktem tablicy decyzyjnej $A$ wtw, gdy

$B$ zachowuje rozróżnialność zbioru A:

t.j. dla dowolnych obiektów $x,y\in U$ ,

jeśli $x,y$ są rozróżnialne przez $A$ , to są również rozróżnialne przez $B$
$B$ jest niezredukowalny:

tzn. żaden właściwy podzbiór $B$ nie zachowuje rozróżnialności zbioru $A$ (t.j., $B$ jest minimalny pod względem rozróżnialności)

\block

Definicja reduktu decyzyjnego Zbiór atrybutów $B\subset A$ nazywamy reduktem tablicy $A$ wtw, gdy

$B$ zachowuje rozróżnialność zbioru $A$ względem decyzji $dec$ :

t.j. dla dowolnych obiektów $x,y\in U$ ,

jeśli $dec(x)\neq dec(y)$ i $x,y$ są rozróżnialne przez $A$ , to są również rozróżnialne przez $B$
$B$ jest niezredukowalny:

tzn. żaden właściwy podzbiór $B$ nie zachowuje rozróżnialności zbioru $A$ ( $B$ jest minimalny pod względem rozróżnialności)

$RED(\mathbb{S})=$ zbiór wszystkich reduktów tablicy decyzyjnej $\mathbb{S}$ ;
Jeśli $\mathbb{S}=(U,A\cup\{ dec\})$ i $|A|=n$ to

$|RED(\mathbb{S})|\leq\binom{n}{n/2}$
rdzeń: zbiór atrybutów będących we wszystkich reduktach

$K=\bigcap _{{B\in RED(\mathbb{S})}}B.$

Znaleźć rdzeń danej tablicy decyzyjnej;
Znaleźć jakiś redukt;
Znaleźć krótkie redukty;
Znaleźć długie redukty.

4.1.2. Złożoność problemu szukania reduktów

\onslide

<1-2> Problem najkrótszego reduktu \block

Dane:

Tablica decyzyjna $\mathbb{S}=(U,A\cup\{ dec\})$ ;

Szukane:

“najkrótszy redukt tablicy decyzyjnej $\mathbb{S}$ ”, tzn. taki redukt decyzyjny $B\in{\bf RED}(\mathbb{S},dec)$ , że

$\forall _{{X\in{\bf RED}(\mathbb{S},dec)}}|B|\leq|X|$

\onslide

<2> Twierdzenie Problem szukania najkrótszego reduktu jest NP-zupełny. \block

<+-| alert@+> Ogólnie musimy pokazać, że jakiś znany NP-zupełny problem jest “łatwiejszy” od problemu najkrótszego reduktu;
<+-| alert@+> Wybierzmy problem minimalnego pokrycia wierzchołkami:

“Dany jest graf $G=(V,E)$ . Znaleźć minimalny zbiór wierzchołków $X\subset V$ o takiej własności, że każda krawędź z $E$ posiada co najmniej jeden z końców w $X$ .”
<+-| alert@+> Wielomianowa transformacja:

\onslide
<4->

$\onslide<5->\implies$ \onslide

$\mathbb{S}({\bf G})$ $a_{{v_{1}}}$ $a_{{v_{2}}}$ $a_{{v_{3}}}$ $a_{{v_{4}}}$ $a_{{v_{5}}}$ $a^{*}$

$x^{*}$ 0 0 0 0 0 0

$u_{{e_{1}}}$ 1 1 0 0 0 1

$u_{{e_{2}}}$ 1 0 0 1 0 1

$u_{{e_{3}}}$ 0 1 0 0 1 1

$u_{{e_{4}}}$ 0 1 0 1 0 1

$u_{{e_{5}}}$ 1 0 1 0 0 1

$u_{{e_{6}}}$ 0 0 1 0 1 1

$\mathbb{S}({\bf G})$	$a_{{v_{1}}}$	$a_{{v_{2}}}$	$a_{{v_{3}}}$	$a_{{v_{4}}}$	$a_{{v_{5}}}$	$a^{*}$
$x^{*}$	0	0	0	0	0	0
$u_{{e_{1}}}$	1	1	0	0	0	1
$u_{{e_{2}}}$	1	0	0	1	0	1
$u_{{e_{3}}}$	0	1	0	0	1	1
$u_{{e_{4}}}$	0	1	0	1	0	1
$u_{{e_{5}}}$	1	0	1	0	0	1
$u_{{e_{6}}}$	0	0	1	0	1	1

<+-> Można też pokazać, że problem najkrótszego reduktu jest “łatwiejszy” niż znany problem “Minimal Hitting Set” (minimalny zbiór przecinający?)
- Dane: Zbiór $S$ i rodzina jego podzbiorów $\{ S_{1},S_{2},...,S_{n}\}$ . Zbiór $X\subset S$ nazywamy zbiórem przecinającym, jeśli $X$ ma niepuste przecięcie z każdym ze zbiorów $S_{1},S_{2},...,S_{n}$ .
- Szukane: minimalny zbiór przecinający.
<+-> Te problemy są obliczeniowo równoważne!

Czyli każdy algorytm dla jednego problemu można przeksztalcić w czasie wielomianowym na odpowiedni algorytmu dla drugiego problemu, który posiada te same cechy zlożonościowe.

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

$U$	Ból głowy	Ból mięśni	Temp.	Grypa
p1	Tak	Tak	N	Nie
p2	Tak	Tak	H	Tak
p3	Tak	Tak	VH	Tak
p4	Nie	Tak	N	Nie
p5	Nie	Nie	H	Nie
p6	Nie	Tak	VH	Tak
p7	Nie	Tak	H	Tak
p8	Nie	Nie	VH	Nie

$U$	Ból głowy	Ból mięśni	Temp.	Grypa
p1	Tak	Tak	N	Nie
p2	Tak	Tak	H	Tak
p3	Tak	Tak	VH	Tak
p4	Nie	Tak	N	Nie
p5	Nie	Nie	H	Nie
p6	Nie	Tak	VH	Tak
p7	Nie	Tak	H	Tak
p8	Nie	Nie	VH	Nie

$U$	Ból głowy	Ból mięśni	Temp.	Grypa
p1	Tak	Tak	N	Nie
p2	Tak	Tak	H	Tak
p3	Tak	Tak	VH	Tak
p4	Nie	Tak	N	Nie
p5	Nie	Nie	H	Nie
p6	Nie	Tak	VH	Tak
p7	Nie	Tak	H	Tak
p8	Nie	Nie	VH	Nie

$U$	Ból głowy	Ból mięśni	Temp.	Grypa
p1	Tak	Tak	N	Nie
p2	Tak	Tak	H	Tak
p3	Tak	Tak	VH	Tak
p4	Nie	Tak	N	Nie
p5	Nie	Nie	H	Nie
p6	Nie	Tak	VH	Tak
p7	Nie	Tak	H	Tak
p8	Nie	Nie	VH	Nie

Systemy decyzyjne

Zagadnienia

4. Zbiory przybliżone

4.1. Zbiory przybliżone

4.1.1. Wprowadzenie do teorii zbiorów przybliżonych

4.1.1.1. Systemy informacyjne i tablice decyzyjne

4.1.1.2. Redukty

4.1.2. Złożoność problemu szukania reduktów

$U$	Ból głowy	Ból mięśni	Temp.	Grypa
p1	Tak	Tak	N	Nie
p2	Tak	Tak	H	Tak
p3	Tak	Tak	VH	Tak
p4	Nie	Tak	N	Nie
p5	Nie	Nie	H	Nie
p6	Nie	Tak	VH	Tak
p7	Nie	Tak	H	Tak
p8	Nie	Nie	VH	Nie

$U$	Ból głowy	Ból mięśni	Temp.	Grypa
p1	Tak	Tak	N	Nie
p2	Tak	Tak	H	Tak
p3	Tak	Tak	VH	Tak
p4	Nie	Tak	N	Nie
p5	Nie	Nie	H	Nie
p6	Nie	Tak	VH	Tak
p7	Nie	Tak	H	Tak
p8	Nie	Nie	VH	Nie