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
[bewerken | brontekst bewerken]Het begrip formeel concept heeft zijn oorsprong in de filosofische theorie over het begrip concept. Een concept is bepaald door haar 'extent', welke dingen onder het concept vallen, en haar 'intent', welke kenmerken of attributen deze dingen gemeen hebben.
Dit wordt vertaald naar een 'formele context', dit is een tripel bestaande uit een verzameling van objecten, een verzameling van eigenschappen of attributen, en een tweeplaatsige relatie van naar . betekent dat eigenschap heeft.
De namen voor objecten en gaan terug op de Duitse namen die Wille gebruikte: Gegenstände en Merkmale.
De relatie 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 en kolom 1 is als de eigenschap bezit, en 0 in andere geval.
In een formele context kan dan een formeel concept worden omschreven als een paar waarin een deelverzameling is van de objectenverzameling en een deelverzameling van de attributenverzameling , zodanig dat tegelijk geldt: is de grootste verzameling objecten die alle eigenschappen uit bezitten, en is de grootste verzameling eigenschappen, die door alle objecten uit worden gedeeld.
Formele definitie
[bewerken | brontekst bewerken]Een formeel concept wordt gedefinieerd in termen van de machtsverzamelingen van G en van M; dit zijn partieel geordende verzamelingen met ordeningsrelatie "is deelverzameling van".
Men definieert dan een afbeelding f van op met:
Dit is de verzameling van eigenschappen die door alle objecten uit gedeeld worden, en wordt aangeduid met . Als een enkel object bevat noemt men de object-intent van object .
Analoog wordt een afbeelding g gedefinieerd van op :
Dit is de verzameling van objecten die alle attributen uit bezitten. Deze verzameling wordt aangeduid met . Als een enkel attribuut bevat noemt men de attribuut-extent van attribuut .
Wanneer nu en spreekt men over een formeel concept . Birkhoff noemde dit een polariteit. is de extent van het concept en de intent.
Voor een formeel concept is en .
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
[bewerken | brontekst bewerken]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
[bewerken | brontekst bewerken]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 (A1, B1) wordt lager geordend dan (of: is een echt subconcept van) een tweede concept (A2, B2) wanneer A1 een deelverzameling is van A2 of B2 een deelverzameling van B1. 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
[bewerken | brontekst bewerken]Voorbeeld 1
[bewerken | brontekst bewerken]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 .
De verzameling eigenschappen die gemeenschappelijk zijn aan is .
en vormen geen formeel concept. Immers is niet de grootste verzameling eigenschappen die gemeenschappelijk zijn aan A,B en E. Maar de verzamelingen en 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 uit naar , dan wordt ; y is de enige eigenschap die deze vier objecten gemeen hebben. Omgekeerd is . en vormen dus ook een concept. Merk op dat en : 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 is een benedenbuur van als en er geen ander concept is met . 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:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d9/ExampleLattice.png/260px-ExampleLattice.png)
Voorbeeld 2
[bewerken | brontekst bewerken]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:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Concept_lattice.svg/400px-Concept_lattice.svg.png)
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
[bewerken | brontekst bewerken]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
[bewerken | brontekst bewerken]- Bernhard Ganter's Formal Concept Analysis Page
- Formal Concept Analysis Homepage (deze website bevat ook een collectie links naar FCA-software)
Bronnen
[bewerken | brontekst bewerken]- 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.
- ↑ 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)
- ↑ P.G. Elzinga. "Formalizing the concepts of crimes and criminals." Proefschrift Universiteit van Amsterdam, 2011. Gearchiveerd op 13 maart 2014.
- ↑ 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. Gearchiveerd op 2 december 2022.
- ↑ 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). Gearchiveerd op 6 februari 2023.