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ů):

1. podmínkové atributy (např. symptomy pacientů)
2. 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:

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

• R₁* = {R₁₁, R₁₂} = a_b_c_d_e_f_g
• R₂* = {R₂₁, R₂₂, R₂₃} = a_b_c_d_e_f_g
• R₃* = {R₃₁, R₃₂} = a_b_d_g_c_e_f

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

• R₄* = (R₁ <m>inter</m> R₂)* = {R₄₁, R₄₂, R₄₃, R₄₄} = a_b_c_d_e_f_g

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 R₄₁ then R₃₁
• if R₄₂ then R₃₂
• if R₄₃ then R₃₁

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

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 = POS_S(X) = dolní aprox.
• hraniční oblast = BOUND_S(X) = horní aprox. - spodní aprox.
• negativní oblast = NEG_S(X) = U - horní aprox.
• množina je rozlišitelná ⇔ množina není hrubá
• množina je rozlišitelná ⇔ hraniční oblast je prázdná

1. pravidla z dolní aproximace jsou pro jakýkoli pojem jistá
2. pravidla z horní aproximace jsou nejistá a zavádí se pro ně 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 R₄₄ then R₃₁ with <m>alpha = 0.33</m>
• if R₄₄ then R₃₂ with <m>alpha = 0.67</m>

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:

1. hledání pozitivních oblastí na jednotlivých podmínkových atributech
2. pro každý prvek rozkladu se zjistí, zda není celý podmnožinou některého pojmu
3. poté následuje stejný proces pro dvojice, (trojice, …) podmínkových atributů
4. 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.