Formální koncepční analýza - Formal concept analysis

Formální koncepční analýza ( FCA ) je principiální způsob odvození hierarchie konceptů nebo formální ontologie ze sbírky objektů a jejich vlastností . Každý koncept v hierarchii představuje objekty sdílející nějakou sadu vlastností; a každý dílčí koncept v hierarchii představuje podmnožinu objektů (stejně jako nadmnožinu vlastností) v pojmech nad ním. Termín zavedl Rudolf Wille v roce 1981 a staví na matematické teorii mřížek a uspořádaných sad , kterou vytvořil Garrett Birkhoff a další ve třicátých letech minulého století.

Formální konceptuální analýza najde praktické uplatnění v oblastech, včetně dolování dat , textů , strojového učení , řízení znalostí , sémantický web , vývoj software , chemii a biologii .

Přehled a historie

Původní motivací formální koncepční analýzy bylo hledání skutečného významu teorie matematické objednávky . Jedna taková možnost velmi obecné povahy je, že datové tabulky mohou být transformovány do algebraických struktur nazývaných kompletní mříže a že tyto mohou být použity pro vizualizaci a interpretaci dat. Za základní datový typ je považována datová tabulka, která představuje heterogenní vztah mezi objekty a atributy, tabelující dvojice ve tvaru „objekt g má atribut m “. Je označován jako formální kontext . V této teorii je formální koncept definován jako pár ( A , B ), kde A je sada objektů (nazývaná rozsah ) a B je sada atributů ( záměr ) tak, že

rozsah A se skládá ze všech objektů, které sdílejí atributy v B , a duálně
Smyslem B se skládá ze všech atributů sdílených objektů A .

Tímto způsobem formální koncepční analýza formalizuje sémantické představy o rozšíření a intenzitě .

Formální pojmy jakéhokoli formálního kontextu lze - jak je vysvětleno níže - uspořádat v hierarchii, která se formálněji nazývá „pojmová mřížka“ kontextu. Pojmovou mřížku lze graficky zobrazit jako „čárový diagram“, který pak může být užitečný pro pochopení dat. Často jsou však tyto mříže příliš velké pro vizualizaci. Potom může být nápomocná matematická teorie formální koncepční analýzy, např. Pro rozložení mřížky na menší části bez ztráty informací nebo pro vložení do jiné struktury, která je snáze interpretovatelná.

Teorie ve své současné podobě sahá do počátku 80. let minulého století a výzkumná skupina vedená Rudolfem Wille , Bernhardem Ganterem a Peterem Burmeisterem na Technische Universität Darmstadt . Jeho základní matematické definice však byly zavedeny již ve 30. letech 20. století Garrettem Birkhoffem jako součást obecné mřížkové teorie. Další předchozí přístupy ke stejné myšlence vycházely z různých francouzských výzkumných skupin, ale skupina Darmstadt pole normalizovala a systematicky zpracovávala jak svou matematickou teorii, tak její filozofické základy. Ty se týkají zejména Charlese S.Peirce , ale také Port-Royal Logic .

Motivace a filozofické pozadí

Ve svém článku „Restructuring Lattice Theory“ (1982), zahajujícím formální koncepční analýzu jako matematickou disciplínu, Wille vychází z nespokojenosti se současnou mřížkovou teorií a čistou matematikou obecně: Produkce teoretických výsledků - často dosažená „propracovanou mentální gymnastikou " - bylo působivé, ale spojení mezi sousedními oblastmi, dokonce i části teorie, byla stále slabší."

Restrukturalizace mřížkové teorie je pokusem oživit spojení s naší obecnou kulturou tak, aby byla tato teorie interpretována co nejkonkrétněji, a tímto způsobem podporovat lepší komunikaci mezi teoretiky mřížky a potenciálními uživateli mřížkové teorie.

- Rudolf Wille,

Tento cíl sahá zpět k pedagogovi Hartmutovi von Hentigovi, který v roce 1972 prosazoval restrukturalizaci věd s cílem zlepšit výuku a učinit vědy vzájemně dostupné a obecněji (tj. Také bez specializovaných znalostí) kritizovatelné. Formální analýza pojmů se tedy od svého vzniku zaměřuje na interdisciplinaritu a demokratickou kontrolu výzkumu.

Opravuje výchozí bod mřížkové teorie během vývoje formální logiky v 19. století. Tehdy - a později v modelové teorii - byl koncept jako unární predikát do té míry redukován. Filozofie konceptů by se nyní měla stát méně abstraktní vzhledem k záměru. Z tohoto důvodu, formální koncept analýza je orientována směrem k kategorie rozšíření a intension z lingvistiky a klasické koncepční logiky.

Formální koncepční analýza si klade za cíl jasnost pojmů podle pragmatické zásady Charlese S. Peirce rozvinutím pozorovatelných elementárních vlastností subsumovaných objektů. Ve své pozdní filozofii Peirce předpokládal, že logické myšlení má za cíl vnímat realitu triadovým konceptem, úsudkem a závěrem . Matematika je abstrakcí logiky, rozvíjí vzorce možných realit, a proto může podporovat racionální komunikaci . Na tomto pozadí Wille definuje:

Cílem a významem formální koncepční analýzy jako matematické teorie konceptů a hierarchií konceptů je podpora racionální komunikace lidí matematickým rozvojem vhodných koncepčních struktur, které lze logicky aktivovat.

- Rudolf Wille,

Příklad

Data v tomto příkladu jsou převzata ze sémantické terénní studie, kde byly různé druhy vodních ploch systematicky kategorizovány podle jejich atributů. Za tímto účelem to bylo zjednodušeno.

Datová tabulka představuje formální kontext , čárový diagram vedle ní ukazuje její koncepční mřížku . Formální definice následují níže.

Příklad pro formální kontext: „vodní plochy“
těla z vody		atributy
těla z vody		dočasný	běh	přírodní	stagnující	konstantní	námořní
předměty	kanál
	kanál
	laguna
	jezero
	maar
	louže
	rybník
	bazén
	nádrž
	řeka
	potůček
	runnel
	moře
	proud
	tarn
	torrent
	pramínek

Liniový diagram odpovídající formálním kontextovým vodním útvarům vlevo

Výše uvedený čárový diagram se skládá z kruhů, spojovacích segmentů čar a popisků. Kruhy představují formální pojmy . Řádky umožňují odečíst hierarchii subkoncept-superkoncept. Každý objekt a název atributu se v diagramu použije jako popisek přesně jednou, přičemž objekty pod ním a atributy nad kruhy konceptů. To se provádí tak, že k atributu lze dosáhnout z objektu prostřednictvím vzestupné cesty právě tehdy, pokud objekt atribut má.

V zobrazeném diagramu má např. Objektový zásobník atributy stagnující a konstantní , ale nikoli atributy dočasné, běžící, přirozené, námořní . V souladu s tím má louže přesně vlastnosti dočasné, stagnující a přirozené .

Původní formální kontext lze rekonstruovat z označeného diagramu i formálních konceptů. Rozsah konceptu se skládá z těch objektů, ze kterých stoupající cesta vede do kruhu představujícího koncept. Záměr se skládá z těch atributů, ke kterým z tohoto pojmového kruhu (v diagramu) existuje vzestupná cesta. V tomto diagramu koncept bezprostředně nalevo od štítkové nádrže má záměr stagnující a přirozený a rozsah louže, Maaru, jezera, rybníka, plesa, bazénu, laguny a moře .

Formální souvislosti a koncepty

Formální kontext je trojitý $K = (G, M, I)$ , kde G je sada objektů , M je sada atributů a $I \subseteq G \times M$ je binární relace nazývaná incidence, která vyjadřuje, které objekty mají které atributy . Pro podmnožiny $A \subseteq G$ objektů a podmnožiny $B \subseteq M$ atributů definujeme dva derivační operátory následovně:

A ' = {m \in M | (g, m) \in I pro všechny g \in A}

, tj. sada všech atributů sdílených všemi objekty z A a duálně

B ' = {g \in G | (g, m) \in I pro všechna m \in B}

, tj. množina všech objektů sdílejících všechny atributy z B.

Použití jednoho operátoru derivace a poté druhého představuje dva operátory uzavření :

A ↦ A ′ ′ = ( A ′ ) ′ pro A ⊆ G (uzavření rozsahu), a

B ↦ B ′ ′ = ( B ′ ) ′ pro B ⊆ M (záměrné uzavření).

Operátory derivace definují Galoisovo spojení mezi sadami objektů a atributů. Proto je ve francouzštině pojmová mříž někdy nazývána treillis de Galois (Galoisova mříž).

S těmito derivačními operátory dal Wille elegantní definici formálního pojmu: pár ( A , B ) je formální koncept kontextu $(G, M, I)$ za předpokladu, že:

⊆ G , B ⊆ M , '= B a B ' = .

Ekvivalentně a intuitivněji je ( A , B ) formální koncept právě tehdy, když:

každý objekt v A má každý atribut v B ,
pro každý objekt v G, který není v A , existuje nějaký atribut v B, který objekt nemá,
pro každý atribut v M, který není v B , existuje nějaký objekt v A , který tento atribut nemá.

Pro výpočetní účely může být formální kontext přirozeně reprezentován jako (0,1) matice K, ve které řádky odpovídají objektům, sloupce odpovídají atributům a každá položka k _{i , j se} rovná 1, pokud „objekt“ mám atribut j . " V tomto znázornění matrice, každý formální koncepce odpovídá maximální submatice (ne nutně souvislé) všech prvků, jejichž rovná 1. Je však zavádějící zvážit formální kontext jako logickou hodnotu , protože negovaný výskyt ( "objekt g se nebude mít atribut m ") není koncepční tvorba stejným způsobem, jak je definován výše. Z tohoto důvodu se při reprezentaci formálních kontextů obvykle vyhýbají hodnotám 1 a 0 nebo PRAVDA a NEPRAVDA a k vyjádření incidence se používá symbol jako ×.

Pojmová mříž formálního kontextu

Pojmy ( A _i , B _i ) kontextu K lze (částečně) uspořádat zahrnutím rozsahů, nebo ekvivalentně dvojitým zahrnutím záměrů. Pořadí ≤ na pojmech je definováno následovně: pro jakékoli dva pojmy ( A ₁ , B ₁ ) a ( A ₂ , B ₂ ) z K říkáme, že ( A ₁ , B ₁ ) ≤ ( A ₂ , B ₂ ) právě když A ₁ ⊆ A ₂ . Ekvivalentně ( A ₁ , B ₁ ) ≤ ( A ₂ , B ₂ ) kdykoli B ₁ ⊇ B ₂ .

V tomto pořadí má každý soubor formálních konceptů největší společný podkoncept , neboli setkání. Jeho rozsah se skládá z těch objektů, které jsou společné pro všechny rozsahy sady. Duálně , každá sada formálních konceptů má nejmenší společný superconcept , jehož záměrem obsahuje všechny atributy, které všechny objekty této sady konceptů.

Tyto operace setkávání a spojování splňují axiomy definující mřížku , ve skutečnosti úplnou mřížku . A naopak, lze ukázat, že každá úplná mřížka je koncepční mřížkou nějakého formálního kontextu (až do izomorfismu).

Přiřaďte hodnoty a negaci

Data v reálném světě jsou často uváděna ve formě tabulky atributů objektu, kde atributy mají „hodnoty“. Formální koncepční analýza s takovými daty zachází tak, že je transformuje do základního typu formálního kontextu („jedné hodnoty“). Metoda se nazývá koncepční škálování .

Negace atributu m je atribut ¬ m , jehož rozsah je jen doplňkem rozsahu m , tj. S (¬ m ) ′ = G \ m ′. Obecně se nepředpokládá, že by pro tvorbu konceptu byly k dispozici negované atributy. Ale páry atributů, které jsou navzájem negacemi, se často přirozeně vyskytují, například v kontextech odvozených od konceptuálního škálování.

Možné negace formálních konceptů naleznete v níže uvedené části pojmu algebry .

Dopady

Implikace → B se týká dvě sady A a B atributů a vyjadřuje, že každý objekt mající každý atribut z A má také každý atribut z B . Když $($ $G$ $,$ $M$ $,$ $I$ $)$ je formální kontext a A , B jsou podmnožinami množiny M atributů (tj. A, B ⊆ M ), pak implikace A → B platí, pokud A ′ ⊆ B ′ . Pro každý konečný formální kontext má množina všech platných implikací kanonický základ , irundundantní soubor implikací, ze kterých lze všechny platné implikace odvodit přirozenou inferencí ( Armstrongova pravidla ). To se používá při zkoumání atributů , což je metoda získávání znalostí založená na implikacích.

Šipkové vztahy

Formální koncepční analýza má propracované matematické základy, díky čemuž je pole všestranné. Jako základní příklad uvádíme relace šipek , které jsou jednoduché a snadno vypočítatelné, ale velmi užitečné. Jsou definovány následovně: Pro $g \in G$ a $m \in M$ let

g ↗ m \Leftrightarrow (g, m) \notin I a pokud m \subseteq n ' a m ' \neq n ', pak (g, n) \in I,

a duálně

g ↙ m \Leftrightarrow (g, m) \notin I a v případě, g ' \subseteq h' a g '\neq h ", pak (H, m) \in I .

Vzhledem k tomu, že lze spojovat pouze neincidentní páry objekt-atribut, lze tyto vztahy pohodlně zaznamenat do tabulky představující formální kontext. Mnoho vlastností mřížky lze vyčíst ze vztahů se šipkami, včetně distribučnosti a několika jejích zobecnění. Odhalují také strukturální informace a mohou být použity pro stanovení např. Kongruenčních vztahů mřížky.

Rozšíření teorie

Triadická koncepční analýza nahrazuje binární vztah dopadu mezi objekty a atributy ternárním vztahem mezi objekty, atributy a podmínkami. Incidence pak vyjadřuje, že objekt $g$ má za podmínky $c$ atribut $m$ . Ačkoli lze triádické pojmy definovat analogicky k výše uvedeným formálním pojmům, teorie jimi vytvořených trilatik je mnohem méně rozvinutá než teorie pojmových mřížek a zdá se být obtížná. Voutsadakis studoval n -ary případ. ${\ Displaystyle (g, m, c)}$
Fuzzy koncepční analýza : Na fuzzy verzi formální koncepční analýzy byla provedena rozsáhlá práce.
Algebry konceptu : Modelování negace formálních konceptů je poněkud problematické, protože doplněk $( G \ A , M \ B )$ formálního konceptu ( A , B ) obecně není konceptem. Protože je však koncepční mřížka kompletní, lze uvažovat o spojení ( A , B )^Δ všech konceptů ( C , D ), které splňují $C ⊆ G \ A$ ; nebo duálně Meet (, B )^𝛁 všech pojmů, které splňují $D$ $\subseteq$ $M$ $\$ $B$ . Tyto dvě operace jsou známé jako slabá negace a slabá opozice . To lze vyjádřit pomocí derivačních operátorů . Slabou negaci lze zapsat jako $($ $A$ $,$ $B$ $)$ $Δ$ $= (($ $G$ $\$ $A$ $) ' ', ($ $G$ $\$ $A$ $) ')$ , a slabou opozici lze zapsat jako $($ $A$ $,$ $B$ $)$ $𝛁$ $= (($ $M$ $\$ $B$ $) ', ($ $M$ $\$ $B$ $) ' ')$ . Pojmová mřížka vybavená dvěma dalšími operacemi Δ a 𝛁 je známá jako pojmová algebra kontextu. Koncepční algebry generalizují energetické sady . Slabá negace na koncepční mřížce L je slabá komplementace , tj.Mapa obrácení řádu $Δ:$ $L$ $\to$ $L,$ která splňuje axiomy $x$ $ΔΔ$ $\leq$ $x$ $a ($ $x$ $⋀$ $y$ $) ⋁ ($ $x$ $⋀$ $y$ $Δ$ $) =$ $x$ . Slabá kompozice je dvojí slabá komplementace. A (ohraničená) mřížka, jako je koncepční algebra, která je vybavena slabou komplementací a duální slabou komplementací, se nazývá slabě dikomplementovaná mřížka . Slabě dikomplementované mříže generalizují distribuční ortocomplementované mříže , tj. Booleovské algebry .

Časová koncepční analýza

Temporal concept analysis (TCA) je rozšířením formální koncepční analýzy (FCA) s cílem koncepčního popisu časových jevů. Poskytuje animace v koncepčních mřížích získaných z dat o měnících se objektech. Nabízí obecný způsob chápání změny konkrétních nebo abstraktních objektů v souvislém, diskrétním nebo hybridním prostoru a čase. TCA aplikuje koncepční škálování na dočasné databáze.

V nejjednodušším případě TCA uvažuje o předmětech, které se mění v čase, jako o částici ve fyzice, která je pokaždé přesně na jednom místě. K tomu dochází v těch dočasných datech, kde atributy 'dočasný objekt' a 'čas' dohromady tvoří klíč databáze. Poté je stav (dočasného objektu v čase v pohledu) formalizován jako určitý objektový koncept formálního kontextu popisující zvolený pohled. V tomto jednoduchém případě je typickou vizualizací časového systému liniový diagram koncepční mřížky pohledu, do kterého jsou vloženy trajektorie dočasných objektů.

TCA generalizuje výše uvedený případ zvážením dočasných databází s libovolným klíčem. To vede k představě rozmístěných objektů, které jsou v daném okamžiku na mnoha místech, například v pásmu vysokého tlaku na mapě počasí. Pojmy „dočasných objektů“, „času“ a „místa“ jsou v měřítcích reprezentovány jako formální pojmy. Stav je formalizován jako sada objektových konceptů. To vede k pojmové interpretaci představ o částicích a vlnách ve fyzice.

Algoritmy a nástroje

Existuje řada jednoduchých a rychlých algoritmů pro generování formálních konceptů a pro konstrukci a navigaci mřížek konceptů. Průzkum najdete v Kuzněcovově a Obiedkově nebo v knize Gantera a Obiedkova, kde lze nalézt i nějaký pseudokód. Protože počet formálních konceptů může být ve velikosti formálního kontextu exponenciální, je složitost algoritmů obvykle dána s ohledem na velikost výstupu. Koncepční mříže s několika miliony prvků lze zvládnout bez problémů.

Dnes je k dispozici mnoho softwarových aplikací FCA. Hlavní účel těchto nástrojů se pohybuje od formálního vytváření kontextu po formální dolování konceptů a generování mřížky konceptů daného formálního kontextu a odpovídajících implikací a asociačních pravidel . Většina těchto nástrojů jsou akademické open-source aplikace, jako například:

ConExp
ToscanaJ
Mřížový těžař
Coron
FcaBedrock
GALAKTICKÉ

Související analytické techniky

Bicliques

Formální kontext lze přirozeně interpretovat jako bipartitní graf . Formální pojmy pak odpovídají maximálním biclikům v tomto grafu. Matematické a algoritmické výsledky formální koncepční analýzy tak mohou být použity pro teorii maximálních bicliků. Pojem bipartitní dimenze (komplementárního bipartitního grafu) se promítá do Ferrersovy dimenze (formálního kontextu) a řádové dimenze (koncepční mřížky) a má aplikace např. Pro Booleovskou maticovou faktorizaci.

Biclustering a multidimenzionální shlukování

Vzhledem k tabulce číselných údajů o atributu objektu je cílem biclustering seskupit některé objekty s podobnými hodnotami některých atributů. Například v datech genové exprese je známo, že geny (objekty) mohou sdílet společné chování pouze pro podmnožinu biologických situací (atributů): člověk by měl podle toho vytvářet lokální vzorce pro charakterizaci biologických procesů, ty druhé by se měly případně překrývat, protože gen může být zapojen do několika procesů. Stejná poznámka platí pro systémy doporučujících, kde se zajímáme o místní vzorce charakterizující skupiny uživatelů, kteří silně sdílejí téměř stejný vkus pro podmnožinu položek.

Bicluster v datové tabulce binárních atributů objektů je pár (A, B) skládající se z inkluzní maximální sady objektů A a inkluzní maximální sady atributů B tak, že téměř všechny objekty z A mají téměř všechny atributy z B a naopak.

Formální pojmy lze samozřejmě považovat za „rigidní“ bluslustery, kde všechny objekty mají všechny atributy a naopak. Proto není divu, že některé definice biclusterů pocházející z praxe jsou pouze definicemi formálního konceptu.

Bicluster s podobnými hodnotami v datové tabulce číselných atributů objektů je obvykle definován jako pár skládající se ze sady objektů s maximální inkluzí a z maximální sady atributů s podobnými hodnotami pro objekty. Takový pár může být reprezentován jako obdélník maximálního zahrnutí v numerické tabulce, modulových řadách a permutacích sloupců. Ukázalo se, že dvojklastry podobných hodnot odpovídají trikonceptům triádického kontextu, kde je třetí dimenze dána stupnicí, která reprezentuje hodnoty číselných atributů binárními atributy.

Tuto skutečnost lze zobecnit na n -dimenzionální případ, kde n -dimenzionální shluky podobných hodnot v n -dimenzionálních datech jsou reprezentovány n+1 -dimenzionálními koncepty. Tato redukce umožňuje používat standardní definice a algoritmy z vícerozměrné koncepční analýzy pro výpočet vícerozměrných klastrů.

Prostory znalostí

V teorii znalostních prostorů se předpokládá, že v jakémkoli znalostním prostoru je rodina stavů znalostí uzavřena unií. Doplňky stavů znalostí tedy tvoří uzavírací systém a mohou být reprezentovány jako rozsahy nějakého formálního kontextu.

Praktické zkušenosti s formální analýzou konceptu

Formální analýzu konceptu lze použít jako kvalitativní metodu pro analýzu dat. Od raných počátků FBA na začátku 80. let 20. století získala výzkumná skupina FBA na TU Darmstadt zkušenosti z více než 200 projektů využívajících FBA (od roku 2005). Včetně oborů: lékařství a buněčná biologie , genetika , ekologie , softwarové inženýrství , ontologie , informační a knihovnické vědy , administrativní správa , právo , lingvistika , politologie .

Mnoho dalších příkladů je například popsáno v: Formální koncepční analýza. Nadace a aplikace , konferenční příspěvky na pravidelných konferencích, jako jsou: Mezinárodní konference o formální koncepční analýze (ICFCA), Concept Lattices and their Applications (CLA) nebo Mezinárodní konference o koncepčních strukturách (ICCS).

Viz také

Poznámky

Reference

Ganter, Bernhard; Stumme, Gerd; Wille, Rudolf, eds. (2005), Formal Concept Analysis: Foundations and Applications , Lecture Notes in Artificial Intelligence, no. 3626, Springer-Verlag, ISBN 3-540-27891-5
Ganter, Bernhard; Wille, Rudolf (1998), Formal Concept Analysis: Mathematical Foundations , přeložil C. Franzke, Springer-Verlag, Berlin, ISBN 3-540-62771-5
Carpineto, Claudio; Romano, Giovanni (2004), Concept Data Analysis: Theory and Applications , Wiley, ISBN 978-0-470-85055-8
Wolff, Karl Erich (1994), F. Faulbaum v StatSoft 1993 (ed.), První kurz formální koncepční analýzy (PDF) , Gustav Fischer Verlag, s. 429–438, archivováno z originálu (PDF) v letech 2006- 03-23
Davey, BA; Priestley, HA (2002), „Kapitola 3. Formální koncepční analýza“, Úvod do mříží a pořádku , Cambridge University Press , ISBN 978-0-521-78451-1

Languages

In other projects