Formeleconceptanalyse

Formeleconceptanalyse (formal concept analysis, FCA) is een kwalitatieve techniek uit de informatiekunde die werd ingevoerd door Rudolf Wille rond 1984. FCA bouwt een geordende hiërarchie van concepten of formele ontologie op voor een bepaald domein, waarbij formele concepten verbanden uitdrukken tussen bepaalde objecten en hun eigenschappen.

De techniek steunt op de ordetheorie en de theorie van tralies die door Garrett Birkhoff en anderen werd ontwikkeld in de jaren 1930.

FCA heeft zich ontwikkeld tot een uitgebreid onderzoeksgebied. Het is onder meer gebruikt in datamining^[1]^[2]^[3], information retrieval, tekstanalyse, kennisbeheer (knowledge management), machinaal leren en software engineering.

Achtergrond

Het begrip formeel concept heeft zijn oorsprong in de filosofische theorie over het begrip concept, die zegt dat een concept bepaald is door haar extent (welke dingen vallen onder het concept?) en haar intent (welke kenmerken of attributen hebben deze dingen gemeen?).

Dit wordt vertaald naar een formele context, dit is een tripel (G, M, R) bestaande uit een verzameling G van objecten, een verzameling M van eigenschappen of attributen, en een binaire relatie R van G naar M; xRy betekent: object x bezit eigenschap y.

De benamingen G voor objecten en M voor attributen gaan terug op de Duitse benamingen die Wille introduceerde: "Gegenstände" en "Merkmale".

De relatie R kan men voorstellen in een bipartiete graaf of de incidentiematrix daarvan; dit is een 0-1-matrix waarvan de rijen corresponderen met objecten en de kolommen met eigenschappen, en waarvan het element op rij i en kolom j 1 is als object i de eigenschap j bezit, en 0 in andere geval.

In een formele context kan dan een formeel concept omschreven worden als een paar (A, B) waarin A een deelverzameling is van de objectenverzameling G en B een deelverzameling van de attributenverzameling M, zodanig dat tegelijk geldt: A is de grootste verzameling objecten die alle attributen uit B bezitten, en: B is de grootste verzameling attributen die door alle objecten uit A gedeeld worden.

Formele definitie

Een formeel concept wordt gedefinieerd in termen van de machtsverzamelingen ${\mathcal {P}}(G)$ van G en ${\mathcal {P}}(M)$ van M; dit zijn partieel geordende verzamelingen met ordeningsrelatie "is deelverzameling van".

Men definieert dan een afbeelding f van ${\mathcal {P}}(G)$ op ${\mathcal {P}}(M)$ met:

f(A\in {\mathcal {P}}(G))=\{x\in M|sRx\ \forall s\in A\}

Dit is de verzameling van eigenschappen die door alle objecten uit $A$ gedeeld worden, en wordt aangeduid met $A'$ . Als $A=\{g\}$ een enkel object bevat noemt men $A'$ de object-intent van object $g$ .

Analoog wordt een afbeelding g gedefinieerd van ${\mathcal {P}}(M)$ op ${\mathcal {P}}(G)$ :

g(B\in {\mathcal {P}}(M))=\{y\in G|yRt\ \forall t\in B\}

Dit is de verzameling van objecten die alle attributen uit $B$ bezitten. Deze verzameling wordt aangeduid met $B'$ . Als $B=\{m\}$ een enkel attribuut bevat noemt men $B'$ de attribuut-extent van attribuut $m$ .

Wanneer nu $A'=B$ en $B'=A$ spreekt men over een formeel concept $(A,B)$ . Birkhoff noemde dit een polariteit. $A$ is de extent van het concept en $B$ de intent.

Voor een formeel concept $(A,B)$ is $g(f(A))=A''=A$ en $f(g(B))=B''=B$ .

De afbeeldingen f en g worden ook de afleidende operatoren genoemd. Ze definiëren een orde-omkerende Galoisverbinding (een term geïntroduceerd door Øystein Ore) tussen de machtsverzamelingen van de objectenverzameling en van de attributenverzameling. Omgekeerd kan elke dergelijke Galoisverbinding voorgesteld worden als een koppel van afbeeldingen van een formele context.

Ordening van concepten

Op de verzameling van alle formele concepten kan men een partiële orde ≤ ("subconcept") definiëren. Als (A, B) en (A*, B*) twee concepten zijn, dan bepaalt men dat (A, B) ≤ (A*, B*) wanneer A ⊆ A* (of, wat op hetzelfde neerkomt: (A, B) ≤ (A*, B*) wanneer B* ⊆ B). Een concept wordt dus hoger gerangschikt dan een ander wanneer het meer objecten beschrijft of minder attributen heeft; het is een algemener concept.

Twee verschillende concepten hebben in deze ordening steeds een unieke grootste ondergrens of infimum. Voor concepten (A, B) en (A*, B*) is dit het concept met objectenverzameling de doorsnede A ∩ A* en als attributenverzameling de vereniging B ∪ B*. Evenzo hebben twee concepten een unieke kleinste bovengrens of supremum; die heeft als attributenverzameling de doorsnede van B en B* en als objectenverzameling de vereniging van A en A* en van eventuele andere objecten die alle attributen bezitten uit B ∩ B*.

Dit betekent dat de formele concepten een volledige tralie vormen, de concepttralie of Galoistralie. Dit is een concepthiërarchie voor de objecten en hun eigenschappen; een subconcept bevat een deelverzameling van de objecten in de concepten die hoger staan in de tralie. De tralie-ordening laat toe om implicatie-regels van eigenschappen en verbanden tussen objecten en eigenschappen op te sporen. De tralie kan met algebraïsche technieken geanalyseerd worden, maar ook visueel voorgesteld in een Hasse-diagram. Dit is een van de meest aantrekkelijke aspecten van FCA.

Men gebruikt ook de termen join voor het infimum van twee concepten, en meet voor het supremum. Deze kunnen uit de grafische voorstelling van de tralie afgelezen worden. Kies twee concepten in het tralie en volg de dalende paden vanuit deze concepten. Er is altijd een hoogste punt waar de paden samenkomen ("join"), dit is het infimum. Er is ook altijd een laagste punt in het tralie waar stijgende paden uit beide concepten samenkomen ("meet"); dit is het supremum. Als de twee concepten verbonden zijn door een lijn is het bovenste concept het supremum en het onderste het infimum.

Algoritmen

Een eenvoudig algoritme om alle concepten van een formele context te bepalen is gebaseerd op de volgende beschouwingen:

men hoeft enkel de concept-extents te bepalen (of de intents), de rest van een concept kan men bekomen door toepassing van de afleidende operatoren;
elke extent is de doorsnede van een aantal attribuut-extents;
de doorsnede van willekeurig veel extents is altijd een extent (met als speciaal geval de doorsnede van nul extents, die gelijk is aan G);
men kan alle extents van concepten bepalen uit de kennis van alle attribuut-extents (en vice versa).

Men kan dan een lijst van concept-extents opstellen als volgt:

Plaats op de lijst voor elk attribuut de attribuut-extent ervan.
Bereken voor elke twee verzamelingen in de lijst de doorsnede. Voeg die toe aan de lijst als ze er nog niet in staat. Ga met de uitgebreide lijst verder om alle paarsgewijze doorsneden te onderzoeken.
Als voor elke twee verzamelingen in de lijst hun doorsnede ook in de lijst staat, breid de lijst dan uit met G, de verzameling van alle objecten.

Hierbij moet men uiteraard geen verzamelingen aan de lijst toevoegen die er reeds in staan. Na afloop bevat de lijst alle concept-extents. Dan kan men voor elk ervan de corresponderende intent bepalen.

De ordening van de concepten gebeurt op basis van hun extent; een concept (A₁, B₁) wordt lager geordend dan (of: is een echt subconcept van) een tweede concept (A₂, B₂) wanneer A₁ een deelverzameling is van A₂ of B₂ een deelverzameling van B₁. De concepttralie kan men nu tekenen door de regels voor het opstellen van een Hasse-diagram te volgen.

Dit algoritme kan men handmatig uitvoeren voor (zeer) kleine contexten, maar het is niet efficiënt voor grote contexten. Er zijn verschillende efficiëntere algoritmen ontwikkeld om de concepttralie te bepalen en te updaten wanneer een nieuw object of een nieuw attribuut wordt toegevoegd aan de context. Sommige genereren een nieuw concept uit een bestaande door de extent te vergroten en/of de intent te verkleinen (of vice versa) volgens een strategie die garandeert dat alle concepten zullen gevonden worden, en liefst zo weinig mogelijk concepten meerdere malen gegenereerd worden. Andere genereren een nieuw concept uit de doorsnede van de extents van twee bestaande concepten. Er bestaan ook algoritmen die op een parallelle computer met meerdere processoren kunnen uitgevoerd worden.^[4]

Voor de voorstelling van de tralie zijn ook speciale programma's ontwikkeld. In reële toepassingen met duizenden objecten en tientallen attributen kan een concepttralie tienduizenden concepten bevatten; het is onmogelijk deze volledig af te beelden. Een "ijsberg"-diagram toont enkel het bovenste deel van de tralie, met concepten die meer dan een bepaald percentage van alle objecten dekken.

Voorbeelden

Voorbeeld 1

Stel we hebben 5 objecten: A,B,C,D,E en 4 eigenschappen: x,y,z,t. De relatie R wordt voorgesteld in deze tabel, die correspondeert met de incidentiematrix van R:

	x	y	z	t
A	√	√		√
B	√	√		√
C			√
D		√	√
E	√	√		√

De verzameling objecten met eigenschappen x en y is $g(\{x,y\})=\{A,B,E\}$ .

De verzameling eigenschappen die gemeenschappelijk zijn aan $\{A,B,E\}$ is $f(\{A,B,E\})=\{x,y,t\}$ .

$\{A,B,E\}$ en $\{x,y\}$ vormen geen formeel concept. Immers $\{x,y\}$ is niet de grootste verzameling eigenschappen die gemeenschappelijk zijn aan A,B en E. Maar de verzamelingen $\{A,B,E\}$ en $\{x,y,t\}$ vormen wel een formeel concept: A, B en E hebben alle drie de eigenschappen x, y en t; en de eigenschappen x, y, t worden enkel gedeeld door de objecten A, B en E. De rijen van A, B en E en de kolommen van x, y, en t vormen een maximaal gevulde rechthoek in de incidentiematrix.

Breidt men nu de verzameling $\{A,B,E\}$ uit naar $\{A,B,D,E\}$ , dan wordt $f(\{A,B,D,E\})=\{y\}$ ; y is de enige eigenschap die deze vier objecten gemeen hebben. Omgekeerd is $g(\{y\})=\{A,B,D,E\}$ . $\{A,B,D,E\}$ en $\{y\}$ vormen dus ook een concept. Merk op dat $\{A,B,E\}\subset \{A,B,D,E\}$ en $\{x,y,t\}\supset \{y\}$ : wanneer de extent vergroot, verkleint de intent en vice versa. Dit illustreert het orde-omkerend karakter van het formeel concept.

Door het bovenstaande algoritme toe te passen kunnen we alle concepten van deze context bepalen. De lijst van concept-extents begint met

{x}' = {A,B,E}

{y}' = {A,B,D,E}

{z}' = {C,D}

({t}' is gelijk aan {x}' en staat al in de lijst)

Deze wordt uitgebreid met:

{D} (doorsnede van 2e en 3e verzameling)

Ø (doorsnede van 1e en 3e verzameling)

{A,B,C,D,E} (omdat alle doorsneden van de 5 verzamelingen in de lijst staan)

Na bepaling van de intents geeft dit deze lijst van zes concepten, in willekeurige volgorde:

1: ({A,B,C,D,E), Ø)

2: ({A,B,D,E}, {y})

3: ({C,D}, {z})

4: ({D}, {y,z})

5: ({A,B,E}, {x,y,t})

6: (Ø, {x,y,z,t})

We bepalen nu de ordening van deze concepten op basis van hun extents:

1 > 2, 3, 4, 5, 6

2 > 4, 5, 6

3 > 4, 6

4 > 6

5 > 6

Om het tralie te tekenen maken we gebruik van het begrip benedenbuur. Concept $(A_{1},B_{1})$ is een benedenbuur van $(A_{2},B_{2})$ als $(A_{1},B_{1})<(A_{2},B_{2})$ en er geen ander concept is met $(A_{1},B_{1})<(A,B)<(A_{2},B_{2})$ . De benedenburen staan in het vet in bovenstaand lijstje. De regels zijn:

teken een cirkel per concept. Een conceptcirkel wordt altijd hoger getekend dan alle cirkels van zijn subconcepts.
verbind elke cirkel met zijn benedenburen.

Deze regels laten nog veel ruimte voor het opstellen van het diagram; een mogelijk traliediagram, waarin de concepten gelabeld zijn met hun extent, is:

Voorbeeld 2

We hebben als objecten de verzameling getallen E = {1,2,3,4,5,6,7,8,9,10} met als eigenschappen F = {samengesteld, even, oneven, priem, kwadraat}. Dit geeft de hierbijgevoegde incidentiematrix:

	samengesteld	even	oneven	priem	kwadraat
1			√		√
2		√		√
3			√	√
4	√	√			√
5			√	√
6	√	√
7			√	√
8	√	√
9	√		√		√
10	√	√

Het kleinste concept dat het getal 3 bevat heeft als objectverzameling {3,5,7} en als attributenverzameling {oneven, priem}.

De concepttralie van deze context kan voorgesteld worden als:

Hierin worden de attributen afgekort aangeduid met c voor samengesteld (composite), s voor kwadraat (square), e voor even, o voor oneven en p voor priem. Deze tralie vat de informatie uit de incidentiematrix samen in een compacte vorm. Men ziet bijvoorbeeld dat het concept "even priemgetal" een subconcept is van de concepten "even getal" en "priemgetal", of dat 9 het enige oneven samengestelde kwadraat is uit de gegeven getallenverzameling.

Men kan door de tralie bewegen in twee richtingen. Naar boven gaan komt overeen met veralgemenen en naar beneden gaan met specialiseren.

Opmerkingen

Voor FCA is een goede keuze van relevante attributen van groot belang. Numerieke grootheden (bijvoorbeeld leeftijd, vermogen, gewicht... van mensen) kan men niet als een attribuut gebruiken. Die moet men indelen in klassen (discretisatie), bijvoorbeeld klein, middelgroot en groot. Elke klasse is dan een attribuut. Hoeveel klassen men gebruikt voor een grootheid is een keuze die men moet maken. Een te groot aantal attributen zal de interpretatie van de analyseresultaten bemoeilijken. Het zou ook kunnen dat er semantische verbanden zijn tussen bepaalde eigenschappen; dat wil zeggen dat de eigenschappen niet onderling onafhankelijk zijn. Daardoor kan de bekomen ontologie overbodige of redundante informatie bevatten. De methode houdt daar geen rekening mee. Een voorbeeld zou kunnen zijn een formele context met zowel de eigenschappen "zoogdier" als "walvis".

Voor het opstellen van een goede attributenverzameling en het toekennen van attributen aan objecten kan men technieken zoals neurale netwerken, support vector machines of naïeve Bayes-classificeerders gebruiken.

Externe links

Bernhard Ganter's Formal Concept Analysis Page
Formal Concept Analysis Homepage (deze website bevat ook een collectie links naar FCA-software)

Bronnen

Bernhard Ganter, Gerd Stumme, Rudolf Wille (red.) Formal Concept Analysis: Foundations and Applications. Springer-Verlag, 2005. ISBN 3540278915
Garrett Birkhoff, Lattice Theory. American Mathematical Society Colloquium Publications, 1940 (repr. 2011). ISBN 0821810251
Abderrahim El Qadi, Driss Aboutajdine, Yassine Ennouary. "Formal Concept Analysis for Information Retrieval." International Journal of Computer Science and Information Security (2010), vol. 7 nr. 2, blz. 119-125.

Bronnen, noten en/of referenties

[1] Jonas Poelmans. "Essays on using Formal Concept Analysis in Information Engineering." Doctoraatsthesis K.U.Leuven, 2010. (hierin wordt FCA toegepast op de analyse van politieverslagen op het vlak van huiselijk geweld)

[2] P.G. Elzinga. "Formalizing the concepts of crimes and criminals." Proefschrift Universiteit van Amsterdam, 2011

[3] Aurélie Bertaux, Agnès Braud, Florence Le Ber. "Mining Complex Hydrobiological Data with Galois Lattices." gepubliceerd in International Workshop on Advances in Conceptual Knowledge Engineering ACKE'07), 2007.

[4] Petr Krajca, Jan Outrata, Vilem Vychodil. "Parallel Recursive Algorithm for FCA". Proceedings of the Sixth International Conference on Concept Lattices and Their Applications (CLA2008), blz. 71-82 (2008)

[1]

[2]

[3]

[4]