====== 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 | 1 | 1 | 1 | | b | 1 | 1 | 1 | | c | 1 | 2 | 2 | | d | 2 | 2 | 1 | | e | 2 | 3 | 2 | | f | 2 | 3 | 2 | | g | 2 | 3 | 1 | 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₁ inter R₂)* = {R₄₁, R₄₂, R₄₃, R₄₄} = {{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 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í prostory ==== Aproximační prostor je dvojice S = (U, R), kde U je univerzum prvků a R je relace ekvivalence na U*U. * 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: underline{S}(X) je sjednocení všech elementárních množin, které jsou podmnožinami X * **horní aproximace** libovolné množiny X v prostoru S: overline{S}(X) 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á ==== 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 X_i a pojem Y_j se vytvořeno pravidlo if X_i then Y_j s faktorem důvěry alpha = {|X_i inter Y_i|}/{|X_i|} Zbylá (nejistá) pravidla pro příklad z tabulky jsou tedy: * if R₄₄ then R₃₁ with alpha = 0.33 * if R₄₄ then R₃₂ with alpha = 0.67 ===== 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.