POSSIBILISTIC INFORMATION: Aı konceptu´ Tutorial Form´aln´ aln´ı anal´yza Metoda zpracov´an´ı dat s filozofick´ym pozad´ım
George J. Klir Michal Krupka State University of New York (SUNY) Binghamton, New York 13902, USA
[email protected] Palacky University, Olomouc, Czech Republic
!
prepared for International Centre for Information and Uncertainty, Palacky University, Olomouc
! ! M. Krupka (DAMOL)
!
Form´ aln´ı konceptu´ aln´ı anal´ yza
6. ˇr´ıjna 2011
1/1
Příklad: snídaně Ingredience Chléb Máslo Vejce Cibule Med Olej Sladký rohlík Sůl
Jídla Chléb s máslem Vejce na měkko Volská oka Míchaná vejce Míchaná vejce na cibulce Chléb s máslem a cibulí Chléb s máslem a medem Sladký rohlík Sladký rohlík s máslem
Příklad: snídaně ch
má
Chm
x
x
Vm
x
x
Vol
x
x
x
x
Mv
x
x
x
x
Mvc
x
x
x
x
Cmc
x
x
Cmm
x
x
Sr Srm
vej
cb
md
ol
sr
s x
x
x
x x
Otázky - Jak zjistit jídla, která obsahují dané ingredience? - Jak zjistit ingredience, které jsou v daných jídlech? - „Mám chuť na vajíčka“, „mám chuť na chléb s máslem“ - Nemám olej. Jaké jídlo si mohu připravit?
x x x
x
x
Jídla Chm: chléb s máslem, Vm: vejce na měkko, Vol: volská oka, Mv: míchaná vejce, Mvc: míchaná vejce na cibulce, Cmc: chléb s máslem a cibulí, Cmm: chléb s máslem a medem, Sr: sladký rohlík, Srm: sladký rohlík s máslem. Ingredience ch: chléb, má: máslo, vej: vejce, cb: cibule, md: med, ol: olej, sr: sladký rohlík, s: sůl
Příklad: snídaně ch
má
vej
cb
md
ol
sr
s
ch Chm
x
Vm
x
Vol
x
x x
x x
s
x
x
x
x
vaj Mv
x
má
x
x
Chm
x
Sr,sr Mvc
x
x
x
x
x
cb Cmc Cmm
x x
x x
Sr Srm
x
x
Vm
Vol,Mv,ol
x
Cmc x
x
Cmm,md
x
Jídla Chm: chléb s máslem, Vm: vejce na měkko, Vol: volská oka, Mv: míchaná vejce, Mvc: míchaná vejce na cibulce, Cmc: chléb s máslem a cibulí, Cmm: chléb s máslem a medem, Sr: sladký rohlík, Srm: sladký rohlík s máslem Ingredience ch: chléb, má: máslo, vej: vejce, cb: cibule, md: med, ol: olej, sr: sladký rohlík, s: sůl
Mvc
Srm
Příklad: snídaně ch
má
vej
cb
md
ol
sr
s
ch Chm
x
Vm
x
Vol
x
x x
x x
s
x
x
x
x
vaj Mv
x
má
x
x
x
Chm Sr,sr
Mvc
x
x
x
x
x
cb Cmc Cmm
x x
x
x
x
Sr Srm
x
Pozorování - Ne všechny uzly v obrázku jsou označeny. - Jak interpretovat uzly v obrázku? - Jak zkonstruovat obrázek z tabulky? - Lze zkonstruovat tabulku z obrázku?
Vol,Mv,ol
x
Cmm,md Cmc
x x
Vm
x
Mvc
Srm
Cíl p¯ednáπky Cíl p¯ednáπky
Uspořádané množiny
Uspo¯ádání Uspo¯ádání Binární relace relace na na mnoæinÏ mnoæinÏXXsesenaz˝vá naz˝váuspo¯ádání, uspo¯ádání,jestliæe jestliæeje je – reflexivní, reflexivní, tj. tj. pro pro kaædé kaædéxx22XXplatí platíxxx,x, – antisymetrická, antisymetrická, tj. tj. xxyyaayyxxjedinÏ jedinÏkdyæ kdyæx x==y,y, –– tranzitivní, tranzitivní, tj. tj. zz xxyy aayyzzplyne plynexxz.z. Mnoæina Mnoæina X X ss uspo¯ádáním uspo¯ádánímsesenaz˝vá naz˝váuspo¯ádaná uspo¯ádanámnoæina. mnoæina. Zobrazení uspo¯ádané mnoæiny Hasseov˝m diagramem ch s
vaj
má
Chm Sr,sr
Vm
M. Krupka (Reintegrace, Informatická propedeutika) M. Krupka (Reintegrace, Informatická propedeutika)
cb Vol,Mv,ol
Cmm,md
V˝zkumná Ëinnost student˘ Cmc V˝zkumná Ëinnost student˘ Mvc
Srm
22. zá¯í 2011 2/3 22. zá¯í 2011 2/3
Úplné svazy Horní a dolní závora Horní a dolní závora Nechª X je uspo¯ádaná mnoæina, Y ✓ X. Prvek x 2 X se naz˝vá horní závora Horní a dolní závora Nechª X je uspo¯ádaná mnoæina, Y ✓ X. Prvek x 2 X se naz˝vá horní závora mnoæiny Yje, jestliæe pro kaædé y 2 YYplatí y Prvek x. Prvek xX2se X naz˝vá se naz˝vá dolní Nechª X uspo¯ádaná mnoæina, ✓ X. x 2 horní závora mnoæiny Y , jestliæe pro kaædé y 2 Y platí y x. Prvek x 2 X se naz˝vá dolní závora mnoæiny Y , jestliæe pro kaædé y platí 2 Y platí x Prvek y. x 2 X se naz˝vá dolní mnoæiny Y , jestliæe pro kaædé y 2 Y y x. závora mnoæiny Y , jestliæe pro kaædé y 2 Y platí x y.
závora mnoæiny Y , jestliæe pro kaædé y 2 Y platí x y. Supremum a infimum Supremum a infimum Prvek x 2 X se naz˝vá supremum mnoæiny Y , jestliæe je její horní závorou a pro Supremum Prvek x 2 X aseinfimum naz˝vá supremum mnoæiny Y , jestliæe je její horní závorou a pro kaædou dalπí její horní závoru z platí x z (x je nejmenπí horní závora Y ). Píπeme W xdalπí Prvek 2 Xjejí se horní naz˝vá supremum mnoæiny Yje, nejmenπí jestliæe jehorní její horní závorou a pro kaædou závoru z platí x z (x závora Y ). Píπeme x = WY . kaædou dalπí její horní závoru z platí x z (x je nejmenπí horní závora Y ). Píπeme x = Y . PrvekWx 2 X se naz˝vá infimum mnoæiny Y , jestliæe je její dolní závorou a pro x = xY2. X se naz˝vá infimum mnoæiny Y , jestliæe je její dolní závorou a pro Prvek kaædou dalπí její dolní závoru z platí x z (x je nejvÏtπí dolní závora Y ). Píπeme V Prvek xdalπí 2 Xjejí se dolní naz˝vá infimum mnoæiny Y , jejestliæe je dolní její dolní závorou a pro kaædou závoru z platí x z (x nejvÏtπí závora Y ). Píπeme x = VY . kaædou její dolní závoru z platí x z (x je nejvÏtπí dolní závora Y ). Píπeme x = V Ydalπí . x = svaz Y. Úpln˝ Úpln˝ svaz Uspo¯ádaná mnoæina X se naz˝vá úpln˝ svaz, jestliæe kaædá její podmnoæina má Uspo¯ádaná mnoæina X se naz˝vá úpln˝ svaz, jestliæe kaædá její podmnoæina má Úpln˝ svaz supremum a infimum. supremum infimum. X se naz˝vá úpln˝ svaz, jestliæe kaædá její podmnoæina má Uspo¯ádanáa mnoæina
Konceptuální svazy Formální kontext Formálníkontext kontext Formální Formální kontext je trojice hX, Y, Ii, kde X je mnoæina objekt˘, Y mnoæina atribut˘ Formálníkontext kontextjejetrojice trojice hX, Y, Ii, je mnoæina objekt˘, Y mnoæina atribut˘ Formální hX, Y, Ii, kdekde X jeXmnoæina objekt˘, Y mnoæina atribut˘ a I binární relace mezi X a Y . a II binární binárnírelace relacemezi meziXXa Ya .Y . Formální koncept Pro mnoæiny A ✓ X a B ✓ Y klademe Formální A✓ Formálníkoncept konceptPro Promnoæiny mnoæiny AX ✓ aXBa✓BY✓klademe Y klademe " A " = {y 2 Y | pro kaædé x 2 A platí hx, yi 2 I} AA= " {y 2 Y | pro kaædé x 2 A platí hx, yi 2 I} # = {y 2 Y | pro kaædé x 2 A platí hx, yi 2 I}
B# = {x 2 X | pro kaædé y 2 B platí hx, yi 2 I} B = # {x 2 X | pro kaædé y 2 B platí hx, yi 2 I} B " # = {x 2 X | pro kaædé y 2 B platí hx, yi 2 I} Pokud A" = B a B# = A, naz˝váme dvojici hA, Bi formální koncept, mnoæina A Pokud A "= B a B = A, naz˝váme dvojici hA, Bi formální koncept. # se naz˝vá B intent tohoto konceptu. Pokud A extent = B aaBmnoæina = A, naz˝váme dvojici formálního hA, Bi formální koncept.
Pro dva formální koncepty hA1 , B1 i, hA2 , B2 i klademe hA1 , B1 i hA2 , B2 i právÏ Pro dva formální koncepty hA hA hA hA 1 ,,B 1 i, 2 ,,B 2 iiklademe 1 , ,B 1 i i 2, B 2 i iprávÏ Pro dva formální koncepty hA B i, hA B klademe hA B hA , B 1 1 2 2 1 1 2 2 právÏ kdyæ A1 ✓ A2 .
kdyæ A ✓ A . 1 2 kdyæ A1 ✓ A2 .
Základní v˝sledek Základní v˝sledek Mnoæina Y, I) vπech formálních koncept˘ formálního kontextu hX, Y, Ii spolu ZákladníB(X, v˝sledek Mnoæina B(X, Y, I) vπech formálních koncept˘ formálního kontextu hX, Y, Ii spolu sMnoæina uspo¯ádáním svaz. B(X,Y,jeI)úpln˝ vπech formálních koncept˘ formálního kontextu hX, Y, Ii spolu
s uspo¯ádáním je úpln˝ svaz. s uspo¯ádáním je úpln˝ svaz. Tento úpln˝ svaz se naz˝vá konceptuální svaz Tento úpln˝ svaz se naz˝vá konceptuální svaz
Zpět k příkladu ch
má
vej
cb
md
ol
sr
s
ch Chm
x
Vm
x
Vol
x
x x
x x
s
x
x
x
x
vaj Mv
x
má
x
x
Chm
x
Sr,sr Mvc
x
x
x
x
x
cb Cmc Cmm
x x
x x
Sr Srm
x
x
Vm
Vol,Mv,ol
x
Cmc x
x
Cmm,md
x
Jídla Chm: chléb s máslem, Vm: vejce na měkko, Vol: volská oka, Mv: míchaná vejce, Mvc: míchaná vejce na cibulce, Cmc: chléb s máslem a cibulí, Cmm: chléb s máslem a medem, Sr: sladký rohlík, Srm: sladký rohlík s máslem Ingredience ch: chléb, má: máslo, vej: vejce, cb: cibule, md: med, ol: olej, sr: sladký rohlík, s: sůl
Mvc
Srm
Příklady aplikací - obecně: jiný pohled na data - vyhledávání informací (information retrieval) - analýza zdrojového kódu programu - vyhodnocování dotazníků - taxonomie zkamenělin - další aplikace viz např. kniha [1]
Kde je to filozofické pozadí? • v širším slova smyslu: zpřístupnění abstraktní matematické teorie uživateli [3] • v užším slova smyslu: redukce konceptu na extent a intent [3, port-royalská logika]
Poznámky • toto je jen začátek: k řešení problému obvykle nestačí pouze zkonstruovat konceptuální svaz • hlavní potíž: velikost konceptuálního svazu
Úloha • napište co nejrychlejší program na vygenerování konceptuálního svazu (podrobnosti na webu)
Literatura [1] C. Carpineto and G. Romano. Concept Data Analysis: Theory and Applications. John Wiley & Sons, 2004. [2] B. Ganter and R. Wille. Formal Concept Analysis – Mathematical Foundations. Springer, 1999. [3] R. Wille. Restructuring lattice theory: an approach based on hierarchies of concepts. In I. Rival, editor, Ordered Sets, pages 445–470. Boston, 1982. seminal publication on Formal Concept Analysis.
