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 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∈A odpowiada pewnej funkcji a:U→Va zwanej wartościowaniem, gdzie Va jest nazwana dziedziną atrybutu a.

Dla B⊆A, definiujemy

B-sygnatura obiektu x∈U (ang. B-information vector) jako

i⁢n⁢fB⁢x=a,a⁢x:a∈B
Zbiór sygnatur względem B o obiektach z U (ang. B-information set):

I⁢N⁢F⁢S=i⁢n⁢fB⁢x:x∈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∈U i 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;
x,y są nierozróżnialne przez B, jeśli one są identyczne na B, tzn. a⁢x=a⁢y dla każdego a∈B;
xB = zbiór obiektów nierozróżnialnych z x przez B.

Dla każdych obiektów x,y:
- albo xB=yB;
- albo xB∩yB=∅.
Relacja

x⁢⁢I⁢N⁢DB⁢⁢y:=x,y⁢ są nierozróżnialne przez ⁢B

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

Dla B=B⁢ó⁢l⁢g⁢ł⁢o⁢w⁢y,B⁢ó⁢l⁢m⁢i⁢ę⁢ś⁢n⁢i

\columns\column

4.5cm

obiekty p⁢1,p⁢2,p⁢3 są nierozróżnialne;
są 3 klasy nierozróżnialności relacji I⁢N⁢DB:
- p⁢1B=p⁢1,p⁢2,p⁢3
- p⁢4B=p⁢4,p⁢6,p⁢7
- p⁢5B=p⁢5,p⁢8

\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

B¯⁢X=x:xB⊂X⁢⁢B¯⁢X=x:xB∩X≠∅

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=a1,a2 <2-> \onslide

IND(B)={	1,2,	s⁢u⁢n⁢n⁢y,h⁢o⁢t
	3,13,	o⁢v⁢e⁢r⁢c⁢a⁢s⁢t,h⁢o⁢t
	4,10,14,	r⁢a⁢i⁢n⁢y,m⁢i⁢l⁢d
	5,6,	r⁢a⁢i⁢n⁢y,c⁢o⁢o⁢l
	8,11,	s⁢u⁢n⁢n⁢y,m⁢i⁢l⁢d
	{7},{9},{12}}

\onslide

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

X=C⁢L⁢A⁢S⁢Sn⁢o=1,2,6,8,14

\onslide

<4-> Aproksymacje pojęcia X:

	LB⁢X	=1,2
	UB⁢X	=1,2,5,6,8,11,4,10,14

\onslide

<5-> Reguła pewna:

If ⁢B⁢x=s⁢u⁢n⁢n⁢y,h⁢o⁢t⁢then ⁢d⁢x=n⁢o

\column

5.4cm \onslide<1->

A∣	a1	a2	a3	a4∣	d
ID∣	outlook	temp.	hum.	windy∣	play
1∣	sunny	hot	high	FALSE∣	no
2∣	sunny	hot	high	TRUE∣	no
3∣	overcast	hot	high	FALSE∣	yes
4∣	rainy	mild	high	FALSE∣	yes
5∣	rainy	cool	normal	FALSE∣	yes
6∣	rainy	cool	normal	TRUE∣	no
7∣	overcast	cool	normal	TRUE∣	yes
8∣	sunny	mild	high	FALSE∣	no
9∣	sunny	cool	normal	FALSE∣	yes
10∣	rainy	mild	normal	FALSE∣	yes
11∣	sunny	mild	normal	TRUE∣	yes
12∣	overcast	mild	high	TRUE∣	yes
13∣	overcast	hot	normal	FALSE∣	yes
14∣	rainy	mild	high	TRUE∣	no

\onslide

<5-> Reguły przybliżone:

		If ⁢B⁢x=r⁢a⁢i⁢n⁢y,c⁢o⁢o⁢l⁢then ⁢d⁢x=n⁢o
		If ⁢B⁢x=r⁢a⁢i⁢n⁢y,m⁢i⁢l⁢d⁢then ⁢d⁢x=n⁢o
		If ⁢B⁢x=s⁢u⁢n⁢n⁢y,m⁢i⁢l⁢d⁢then ⁢d⁢x=n⁢o

\block

Jakość aproksymacji (ang. accuracy of approximation)

αB⁢X=B¯⁢XB¯⁢X

0≤αB⁢X≤1
Jeśli αB⁢X=1, to zbiór X jest dokładnie definiowany przez B;
Jeśli α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⊂A nazywamy reduktem tablicy decyzyjnej A wtw, gdy

B zachowuje rozróżnialność zbioru A:

t.j. dla dowolnych obiektów x,y∈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⊂A nazywamy reduktem tablicy A wtw, gdy

B zachowuje rozróżnialność zbioru A względem decyzji d⁢e⁢c:

t.j. dla dowolnych obiektów x,y∈U,

jeśli d⁢e⁢c⁢x≠d⁢e⁢c⁢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)

R⁢E⁢D⁢S= zbiór wszystkich reduktów tablicy decyzyjnej S;
Jeśli S=U,A∪d⁢e⁢c i A=n to

R⁢E⁢D⁢S≤nn/2
rdzeń: zbiór atrybutów będących we wszystkich reduktach

K=⋂B∈R⁢E⁢D⁢SB.

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 S=U,A∪d⁢e⁢c;

Szukane:

“najkrótszy redukt tablicy decyzyjnej S”, tzn. taki redukt decyzyjny B∈RED⁢S,d⁢e⁢c, że

∀X∈RED⁢S,d⁢e⁢cB≤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⊂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->

5-⟹\onslide

S⁢G av1 av2 av3 av4 av5 a*

x* 0 0 0 0 0 0

ue1 1 1 0 0 0 1

ue2 1 0 0 1 0 1

ue3 0 1 0 0 1 1

ue4 0 1 0 1 0 1

ue5 1 0 1 0 0 1

ue6 0 0 1 0 1 1

S⁢G	av1	av2	av3	av4	av5	a*
x*	0	0	0	0	0	0
ue1	1	1	0	0	0	1
ue2	1	0	0	1	0	1
ue3	0	1	0	0	1	1
ue4	0	1	0	1	0	1
ue5	1	0	1	0	0	1
ue6	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 S1,S2,…,Sn. Zbiór X⊂S nazywamy zbiórem przecinającym, jeśli X ma niepuste przecięcie z każdym ze zbiorów S1,S2,…,Sn.
- 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

S⁢G	av1	av2	av3	av4	av5	a*
x*	0	0	0	0	0	0
ue1	1	1	0	0	0	1
ue2	1	0	0	1	0	1
ue3	0	1	0	0	1	1
ue4	0	1	0	1	0	1
ue5	1	0	1	0	0	1
ue6	0	0	1	0	1	1

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

S⁢G	av1	av2	av3	av4	av5	a*
x*	0	0	0	0	0	0
ue1	1	1	0	0	0	1
ue2	1	0	0	1	0	1
ue3	0	1	0	0	1	1
ue4	0	1	0	1	0	1
ue5	1	0	1	0	0	1
ue6	0	0	1	0	1	1

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

S⁢G	av1	av2	av3	av4	av5	a*
x*	0	0	0	0	0	0
ue1	1	1	0	0	0	1
ue2	1	0	0	1	0	1
ue3	0	1	0	0	1	1
ue4	0	1	0	1	0	1
ue5	1	0	1	0	0	1
ue6	0	0	1	0	1	1