Obsah

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:

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:

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

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:

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>.

Indukce pravidel na aproximačním prostoru

  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

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:

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:

  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.