Hrubé množiny

(spodní a horní aproximace, pozitivní, negativní a hraniční oblast, možné využití pro dolování znalostí)

Prerekvizity: základní algebraické pojmy (relace ekvivalence, rozklad na množině)

Celá otázka je prakticky přímo přepsaná ze slajdů SFC.

Teorie hrubých množin pracuje s daty uloženými v dvojrozměrných tabulkách. Tyto tabulky určují dva typy atributů pro každý prvek univerza (např. seznam pacientů):

podmínkové atributy (např. symptomy pacientů)

rozhodovací atributy (např. diagnostikované nemoci, rozhoduje se na základě podmínkových)

Nad univerzem lze vytvořit relaci ekvivalence podle všech jednotlivých atributů. Dle těchto relací lze pak vytvořit rozklady univerza, čímž vznikají podmnožiny obsahující prvky univerza, které jsou podle jednoho z atributů (ať už podmínkových či rozhodovacích) ekvivalentní. Prvkům rozkladu rozhodovacích atributů se říká pojmy.

Uvažujme tabulku:

Universum	Podmínkové atributy	Rozhodovací atributy
A1	A2	A3
a	<html><span style=„color: blue; font-weight: bold;“>1</span></html>	<html><span style=„color: blue; font-weight: bold;“>1</span></html>	<html><span style=„color: blue; font-weight: bold;“>1</span></html>
b	<html><span style=„color: blue; font-weight: bold;“>1</span></html>	<html><span style=„color: blue; font-weight: bold;“>1</span></html>	<html><span style=„color: blue; font-weight: bold;“>1</span></html>
c	<html><span style=„color: blue; font-weight: bold;“>1</span></html>	<html><span style=„color: green; font-weight: bold;“>2</span></html>	<html><span style=„color: green; font-weight: bold;“>2</span></html>
d	<html><span style=„color: green; font-weight: bold;“>2</span></html>	<html><span style=„color: green; font-weight: bold;“>2</span></html>	<html><span style=„color: blue; font-weight: bold;“>1</span></html>
e	<html><span style=„color: green; font-weight: bold;“>2</span></html>	<html><span style=„color: red; font-weight: bold;“>3</span></html>	<html><span style=„color: green; font-weight: bold;“>2</span></html>
f	<html><span style=„color: green; font-weight: bold;“>2</span></html>	<html><span style=„color: red; font-weight: bold;“>3</span></html>	<html><span style=„color: green; font-weight: bold;“>2</span></html>
g	<html><span style=„color: green; font-weight: bold;“>2</span></html>	<html><span style=„color: red; font-weight: bold;“>3</span></html>	<html><span style=„color: blue; font-weight: bold;“>1</span></html>

Barvy v každém sloupci určují rozklad univerza podle daného atributu. Jednotlivé rozklady a jejich ekvivalenční třídy jsou:

R1* = {R11, R12} = a_b_c_d_e_f_g

R2* = {R21, R22, R23} = a_b_c_d_e_f_g

R3* = {R31, R32} = a_b_d_g_c_e_f

Lze definovat i rozklady na složených relacích (součin rozkladů jednotlivých relací):

R4* = (R1 <m>inter</m> R2)* = {R41, R42, R43, R44} = a_b_c_d_e_f_g

Indukce pravidel

Teorie hrubých množin slouží k mapování rozkladů podmínkových atributů na pojmy. Pro konzistentní záznamy z tabulky lze vytvořit (indukovat) pravidla jednoduše:

if R41 then R31

if R42 then R32

if R43 then R31

Pro R44 nelze indukovat jednoduché pravidlo, protože není podmnožinou žádné množiny z R3*.

Aproximační prostory

Aproximační prostor je dvojice S = (U, R), kde U je univerzum prvků a R je relace ekvivalence na <m>U*U</m>.

ekvivalenčním třídám se v terminologii Aproximačních prostorů říká elementární množiny v S

každé sjednocení libovolných elementárních množin: definovatelná množina v S (také rozlišitelná)

množina, která není definovatelnou množinou: hrubá množina

dolní aproximace libovolné množiny X v prostoru S: <m>underline{S}(X)</m> je sjednocení všech elementárních množin, které jsou podmnožinami X

horní aproximace libovolné množiny X v prostoru S: <m>overline{S}(X)</m> je sjednocení všech elementárních množin, jejichž průnik s X je neprázdný

pozitivní oblast = POSS(X) = dolní aprox.

hraniční oblast = BOUNDS(X) = horní aprox. - spodní aprox.

negativní oblast = NEGS(X) = U - horní aprox.

množina je rozlišitelná ⇔ množina není hrubá

množina je rozlišitelná ⇔ hraniční oblast je prázdná

Indukce pravidel na aproximačním prostoru

pravidla z dolní aproximace jsou pro jakýkoli pojem jistá

pravidla z horní aproximace jsou nejistá a zavádí se pro ně faktor důvěry

Faktor důvěry

Při indukci pravidel pro podmínkový parametr <m>X_i</m> a pojem <m>Y_j</m> se vytvořeno pravidlo <m>if X_i then Y_j</m> s faktorem důvěry <m>alpha = {|X_i inter Y_i|}/{|X_i|}</m>

Zbylá (nejistá) pravidla pro příklad z tabulky jsou tedy:

if R44 then R31 with <m>alpha = 0.33</m>

if R44 then R32 with <m>alpha = 0.67</m>

Použití hrubých množin při dolování z dat

Vstupem do dolování je datový sklad: opět tabulka obsahující podmínkové a rozhodovací atributy. Nad relacemi ekvivalence podle těchto atributů jsou utvořeny rozklady.

Postup pro indukci konzistentních pravidel:

hledání pozitivních oblastí na jednotlivých podmínkových atributech

pro každý prvek rozkladu se zjistí, zda není celý podmnožinou některého pojmu

poté následuje stejný proces pro dvojice, (trojice, …) podmínkových atributů

konec nastane při konzistentní tabulce v případě, že všechny řádky tabulky jsou zachyceny v indukovaných pravidlech

U nekonzistentní tabulky je postup stejný, ovšem rozklady, které „zbydou“ jsou hrubými množinami a pravidla z nich utvořená jsou uvedena pro všechny varianty pojmů a ohodnocená faktorem důvěry.