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

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

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

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 AA* (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 AA* en als attributenverzameling de vereniging BB*. 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 BB*.

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

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

Voorbeeld 1

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:

 
tralie voor voorbeeld 1

Voorbeeld 2

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:

 

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

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.

bewerken

Bronnen

bewerken