Formální konceptuální analýza

Informatika Formální konceptuální analýza Matematické pozadí FKA Využití FKA Literatura

Formální konceptuální analýza moderní metoda analýzy dat

Tomáš Kühr

14. ˇríjna 2011

Tomáš Kühr

Formální konceptuální analýza


Osnova

1

Informatika

2


3

Matematické pozadí FKA

4

Využití FKA

Tomáš Kühr



Co je to informatika?

Tomáš Kühr



Co je to informatika?

“Computer science is no more about computers than astronomy is about telescopes. ” “Informatika se nezabývá poˇcítaˇci o nic více než astronomie dalekohledy. ” Edsger Dijkstra

Tomáš Kühr



Informatika ˇ Informatika je veda, která se zabývá informacemi (daty) a jejich zpracováním. ˇ eji ˇ zaznamenáváme ve formeˇ vzájemneˇ Data nejbežn propojených tabulek (databází).

Rodn´ eˇ c´ıslo 751224/1234 825513/9876 830524/4433 ...

Pˇ r´ıjmen´ı Nov´ ak Nˇemeˇckov´ a Oulehla ...

Jm´ eno Josef Dana Vladim´ır ...

Rodn´ eˇ c´ıslo 830524/4433 751224/1234 825513/9876 ...

Tomáš Kühr

ID 20134 1264 1264 ...

ID 20134 1264 13469 ...

Ulice 17. listopadu Pod Palmami Koˇ nsk´a


ˇ ıslo C´ 123 5 28 ...

Mˇ esto Olomouc Praha Lhota ...


Informatika ˇ Informatika je veda, která se zabývá informacemi (daty) a jejich zpracováním. ˇ eji ˇ zaznamenáváme ve formeˇ vzájemneˇ Data nejbežn propojených tabulek (databází).

Rodn´ eˇ c´ıslo 751224/1234 825513/9876 830524/4433 ...

Pˇ r´ıjmen´ı Nov´ ak Nˇemeˇckov´ a Oulehla ...

Jm´ eno Josef Dana Vladim´ır ...

Rodn´ eˇ c´ıslo 830524/4433 751224/1234 825513/9876 ...

Tomáš Kühr

ID 20134 1264 1264 ...

ID 20134 1264 13469 ...

Ulice 17. listopadu Pod Palmami Koˇ nsk´a


ˇ ıslo C´ 123 5 28 ...

Mˇ esto Olomouc Praha Lhota ...


Binární data Jsou nejjednodušším typem informace. Vyjadˇrují, zda zkoumaný objekt má cˇ i nemá danou vlastnost. Jiné typy dat lze relativneˇ snadno pˇrevést na binární data. 2 nohy pes ˇ kocka ovce koza slepice krocan

4 nohy × × × ×

× ×

vejce

× Tomáš Kühr

mléko

maso

vlna

× ×

× × × ×

×



Binární data Jsou nejjednodušším typem informace. Vyjadˇrují, zda zkoumaný objekt má cˇ i nemá danou vlastnost. Jiné typy dat lze relativneˇ snadno pˇrevést na binární data. 2 nohy pes ˇ kocka ovce koza slepice krocan

4 nohy × × × ×

× ×

vejce

× Tomáš Kühr

mléko

maso

vlna

× ×

× × × ×

×



Formální konceptuální analýza (FKA)

metoda analýzy dat,

K0

jejíž základy položil Rudolf Wille v roce 1982. K2

ˇ Umožnuje jiný pohled na data.

K3

K4

Z tabulky s binárními daty je vytvoˇrena množina K5 tzv. konceptu˚ (maximální shluky = obdélníky kˇrížku˚ v tabulce).

K6 K7

Koncepty lze pˇrirozeneˇ uspoˇrádat.

Tomáš Kühr


K1


Hledání konceptu˚ Nalezené:

2 nohy pes ˇ kocka ovce koza slepice krocan

4 nohy × × × ×

vejce

× ×

× Tomáš Kühr

mléko

maso

vlna

× ×

× × × ×

×



Hledání konceptu˚ Nalezené: h{pes, koˇcka, ovce, koza} , {4 nohy}i,


4 nohy × × × ×

vejce

× ×

× Tomáš Kühr

mléko

maso

vlna

× ×

× × × ×

×



Hledání konceptu˚ Nalezené: h{pes, koˇcka, ovce, koza} , {4 nohy}i, h{ovce, koza, slepice, krocan} , {maso}i,


4 nohy × × × ×

vejce

× ×

× Tomáš Kühr

mléko

maso

vlna

× ×

× × × ×

×



Hledání konceptu˚ Nalezené: h{pes, koˇcka, ovce, koza} , {4 nohy}i, h{ovce, koza, slepice, krocan} , {maso}i, h{slepice, krocan} , {2 nohy, maso}i,


4 nohy × × × ×

vejce

× ×

× Tomáš Kühr

mléko

maso

vlna

× ×

× × × ×

×



Hledání konceptu˚ Nalezené: h{pes, koˇcka, ovce, koza} , {4 nohy}i, h{ovce, koza, slepice, krocan} , {maso}i, h{slepice, krocan} , {2 nohy, maso}i, h{ovce, koza} , {4 nohy, mléko, maso}i,


4 nohy × × × ×

vejce

× ×

× Tomáš Kühr

mléko

maso

vlna

× ×

× × × ×

×



Hledání konceptu˚ Nalezené: h{pes, koˇcka, ovce, koza} , {4 nohy}i, h{ovce, koza, slepice, krocan} , {maso}i, h{slepice, krocan} , {2 nohy, maso}i, h{ovce, koza} , {4 nohy, mléko, maso}i, h{slepice} , {2 nohy, vejce, maso}i, 2 nohy pes ˇ kocka ovce koza slepice krocan

4 nohy × × × ×

vejce

× ×

× Tomáš Kühr

mléko

maso

vlna

× ×

× × × ×

×



Hledání konceptu˚ Nalezené: h{pes, koˇcka, ovce, koza} , {4 nohy}i, h{ovce, koza, slepice, krocan} , {maso}i, h{slepice, krocan} , {2 nohy, maso}i, h{ovce, koza} , {4 nohy, mléko, maso}i, h{slepice} , {2 nohy, vejce, maso}i, h{ovce} , {4 nohy, mléko, maso, vlna}i, 2 nohy pes ˇ kocka ovce koza slepice krocan

4 nohy × × × ×

vejce

× ×

× Tomáš Kühr

mléko

maso

vlna

× ×

× × × ×

×



Uspoˇrádání konceptu˚ Koncepty: K1 K2 K3 K4 K5 K6 K0 K7

= h{pes, koˇcka, ovce, koza} , {4 nohy}i, = h{ovce, koza, slepice, krocan} , {maso}i, = h{slepice, krocan} , {2 nohy, maso}i, = h{ovce, koza} , {4 nohy, mléko, maso}i, = h{slepice} , {2 nohy, vejce, maso}i, = h{ovce} , {4 nohy, mléko, maso, vlna}i, = h{pes, koˇcka, ovce, koza, slepice, krocan} , ∅i, = h∅, {2 nohy, 4 nohy, vejce, mléko, maso, vlna}i.

Koncepty uspoˇrádáme podle odpovídajících množin objektu: ˚ napˇr. {ovce, koza} ⊆ {pes, koˇcka, ovce, koza} ⇒ K4 ≤ K1 K7 ≤ K5 ≤ K3 ≤ K2 ≤ K0 , K7 ≤ K6 ≤ K4 ≤ K1 ≤ K0 , K4 ≤ K2 . Tomáš Kühr



Konceptuální svaz Uspoˇrádaná množina konceptu˚ tvoˇrí tzv. konceptuální svaz,

K0

ˇ Hasseovým který muže ˚ být graficky znázornen diagramem. Jednotlivé koncepty jsou v tomto diagramu ˇ uzly. znázorneny

K2 K3

K4

K5

K6

Koncepty Ki a Kj jsou v diagramu spojeny, ˇ výše pokud Ki ≤ Kj , pˇri cˇ emž Kj je umísten než Ki .

Tomáš Kühr

K1


K7


Formální kontext

Definice Formální kontext je trojice hX , Y , Ii, kde X je množina objektu, ˚ Y je množina atributu˚ a I je binární relace incidence mezi množinami X a Y .

Tomáš Kühr



Formální koncept Definice Pro dané množiny A ⊆ X a B ⊆ Y definujeme A↑ = {y ∈ Y | ∀x ∈ A platí hx, y i ∈ I} , B ↓ = {x ∈ X | ∀y ∈ B platí hx, y i ∈ I} . Pokud A↑ = B a B ↓ = A, pak dvojici hA, Bi nazýváme formální koncept. Množinu A nazýváme extent a množinu B intent tohoto konceptu. Pro dva formální koncepty hA1 , B1 i a hA2 , B2 i klademe hA1 , B1 i ≤ hA2 , B2 i, práveˇ když A1 ⊆ A2 .

Tomáš Kühr



Využití FKA

obecneˇ – jiný pohled na data, vyhledávání informací, na katedˇre informatiky UP: vyhodnocování dotazníku, ˚ ˇ taxonomie zkamenelin.

Tomáš Kühr



Literatura C. Carpineto, G. Romano: Concept Data Analysis: Theory and Applications. John Wiley & Sons, 2004. B. Ganter, R. Wille: Formal Concept Analysis – Mathematical Foundations. Springer, 1999. R. Wille: Restructuring lattice theory: an approach based on hierarchies of concepts. Ordered Sets, strany 445–470. Boston, 1982. Tuto prezentaci je možné stáhnout na adrese http://www.inf.upol.cz/prednasky-pro-stredni-skoly/.

Tomáš Kühr


Formální konceptuální analýza

Recommend Documents