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
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
Osnova
1
Informatika
2
Formální konceptuální analýza
3
Matematické pozadí FKA
4
Využití FKA
Tomáš Kühr
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
Co je to informatika?
Tomáš Kühr
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Formální konceptuální analýza
ˇ ıslo
C´
123
5
28
...
Mˇ
esto
Olomouc
Praha
Lhota
...
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Formální konceptuální analýza
ˇ ıslo
C´
123
5
28
...
Mˇ
esto
Olomouc
Praha
Lhota
...
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Formální konceptuální analýza
K1
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
Hledání konceptu˚
Nalezené:
2 nohy
pes
ˇ
kocka
ovce
koza
slepice
krocan
4 nohy
×
×
×
×
vejce
×
×
×
Tomáš Kühr
mléko
maso
vlna
×
×
×
×
×
×
×
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
Hledání konceptu˚
Nalezené: h{pes, koˇcka, ovce, koza} , {4 nohy}i,
2 nohy
pes
ˇ
kocka
ovce
koza
slepice
krocan
4 nohy
×
×
×
×
vejce
×
×
×
Tomáš Kühr
mléko
maso
vlna
×
×
×
×
×
×
×
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
Hledání konceptu˚
Nalezené: h{pes, koˇcka, ovce, koza} , {4 nohy}i,
h{ovce, koza, slepice, krocan} , {maso}i,
2 nohy
pes
ˇ
kocka
ovce
koza
slepice
krocan
4 nohy
×
×
×
×
vejce
×
×
×
Tomáš Kühr
mléko
maso
vlna
×
×
×
×
×
×
×
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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,
2 nohy
pes
ˇ
kocka
ovce
koza
slepice
krocan
4 nohy
×
×
×
×
vejce
×
×
×
Tomáš Kühr
mléko
maso
vlna
×
×
×
×
×
×
×
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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,
2 nohy
pes
ˇ
kocka
ovce
koza
slepice
krocan
4 nohy
×
×
×
×
vejce
×
×
×
Tomáš Kühr
mléko
maso
vlna
×
×
×
×
×
×
×
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
×
×
×
×
×
×
×
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
×
×
×
×
×
×
×
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Formální konceptuální analýza
K7
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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í konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Formální konceptuální analýza
Informatika
Formální konceptuální analýza
Matematické pozadí FKA
Využití FKA
Literatura
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
Download

Formální konceptuální analýza