Formal concept analysis (FCA) is a principled way of deriving a concept hierarchy or formal ontology from a collection of objects and their properties. This means deriving implicit relationships between objects regarding their attributes.
Each concept in the hierarchy represents the set of objects sharing the same values for a certain set of properties; and each sub-concept in the hierarchy contains a subset of the objects in the concepts above it.
Formal concept analysis finds practical application in fields including data mining, text mining, machine learning or semantic web.
We use the example from https://en.wikipedia.org/wiki/Formal_concept_analysis:
var fc = new FormalContext[Int, String]
fc.set_object_attributes(1, ["odd", "square"])
fc.set_object_attributes(2, ["even", "prime"])
fc.set_object_attributes(3, ["odd", "prime"])
fc.set_object_attributes(4, ["even", "composite", "square"])
fc.set_object_attributes(5, ["odd", "prime"])
fc.set_object_attributes(6, ["even", "composite"])
fc.set_object_attributes(7, ["odd", "prime"])
fc.set_object_attributes(8, ["even", "composite"])
fc.set_object_attributes(9, ["odd", "square", "composite"])
fc.set_object_attributes(10, ["even", "composite"])
var concepts = fc.formal_concepts
for concept in concepts do
print concept
end
var cl = new ConceptLattice[Int, String].from_concepts(concepts)
cl.show_dot
serialization :: serialization_core
Abstract services to serialize Nit objects to different formatscore :: union_find
union–find algorithm using an efficient disjoint-set data structure
# Formal Concept Analysis
#
# Formal concept analysis (FCA) is a principled way of deriving a concept hierarchy
# or formal ontology from a collection of objects and their properties.
# This means deriving implicit relationships between objects regarding their
# attributes.
#
# Each concept in the hierarchy represents the set of objects sharing the same
# values for a certain set of properties; and each sub-concept in the hierarchy
# contains a subset of the objects in the concepts above it.
#
# Formal concept analysis finds practical application in fields including data
# mining, text mining, machine learning or semantic web.
#
# ## Building a FormalContext
#
# We use the example from https://en.wikipedia.org/wiki/Formal_concept_analysis:
#
# ~~~
# var fc = new FormalContext[Int, String]
# fc.set_object_attributes(1, ["odd", "square"])
# fc.set_object_attributes(2, ["even", "prime"])
# fc.set_object_attributes(3, ["odd", "prime"])
# fc.set_object_attributes(4, ["even", "composite", "square"])
# fc.set_object_attributes(5, ["odd", "prime"])
# fc.set_object_attributes(6, ["even", "composite"])
# fc.set_object_attributes(7, ["odd", "prime"])
# fc.set_object_attributes(8, ["even", "composite"])
# fc.set_object_attributes(9, ["odd", "square", "composite"])
# fc.set_object_attributes(10, ["even", "composite"])
# ~~~
#
# ## Computing the set of FormalConcept
#
# ~~~
# var concepts = fc.formal_concepts
# for concept in concepts do
# print concept
# end
# ~~~
#
# ## Visualizing formal concept with ConceptLattice
#
# ~~~nitish
# var cl = new ConceptLattice[Int, String].from_concepts(concepts)
# cl.show_dot
# ~~~
module fca
import poset
# Formal Context
#
# A formal context is a triple *K = (G, M, I)*, where *G* is a set of `objects`,
# *M* is a set of `attributes`, and *I ⊆ G × M* is a binary relation called incidence
# that expresses which objects have which attributes (`objects_attributes`).
#
# Predicate *gIm* designates object *g*'s having attribute *m*.
# For a subset *A ⊆ G* of objects and a subset *B ⊆ M* of attributes, one defines
# two derivation operators as follows:
#
# * *A' = {m ∈ M | ∀ g ∈ A, gIm}*, and dually
# * *B' = {g ∈ G | ∀ m ∈ B, gIm}*.
class FormalContext[O: Object, A: Object]
# Objects in the context
var objects = new HashSet[O]
# Attributes considered to build concepts
var attributes = new HashSet[A]
# Association between objects and attributes
var objects_attributes = new HashMap[O, Set[A]]
# Associate a set of `attributes` to `object`
fun set_object_attributes(object: O, attributes: Collection[A]) do
for attribute in attributes do
set_object_attribute(object, attribute)
end
end
# Associate an `attribute` to `object`
fun set_object_attribute(object: O, attribute: A) do
attributes.add attribute
objects.add object
if not objects_attributes.has_key(object) then
objects_attributes[object] = new HashSet[A]
end
objects_attributes[object].add attribute
end
# Derive the set of formal concepts from the objects and attributes
fun formal_concepts: Set[FormalConcept[O, A]] do
# black magic!
var concepts = new HashSet[FormalConcept[O, A]]
var extentsByAttr = new HashMap[Set[A], Set[O]]
for attribute in attributes do
var ka = new HashSet[A].from([attribute])
extentsByAttr[ka] = new HashSet[O]
for object in objects do
if not objects_attributes[object].has(attribute) then continue
extentsByAttr[ka].add(object)
end
end
var nextents = new HashMap[Set[A], Set[O]]
for k1, v1 in extentsByAttr do
for k2, v2 in extentsByAttr do
if k1 == k2 then continue
var n = v1.intersection(v2)
if extentsByAttr.values.has(n) then continue
var ka = k1.union(k2)
nextents[ka] = n
end
end
extentsByAttr.add_all nextents
var contained = true
for k1, v1 in extentsByAttr do
if not contained then break
for k2, v2 in extentsByAttr do
if k1 == k2 then continue
var n = v1.intersection(v2)
if extentsByAttr.values.has(n) then continue
contained = false
break
end
end
if contained then
extentsByAttr[new HashSet[A]] = new HashSet[O].from(objects)
end
var extents = new HashSet[Set[O]]
for objects in extentsByAttr.values do
extents.add objects
end
for extent in extents do
var intents: Set[A] = new HashSet[A]
var count = 0
var cl = new FormalConcept[O, A]
if extent.is_empty then
intents.add_all(attributes)
else
for object in objects do
if not extent.has(object) then continue
var prev = objects_attributes[object]
if count > 0 then
intents = prev.intersection(intents)
else
intents = prev
end
count += 1
cl.objects.add(object)
end
end
cl.attributes.add_all intents
concepts.add cl
end
return concepts
end
end
# Formal Concept
#
# A pair *(A,B)* is a formal concept of a FormalContext *(G, M, I)* provided that:
#
# * *A ⊆ G*,
# * *B ⊆ M*,
# * *A′ = B*, and
# * *B′ = A*.
#
# Equivalently and more intuitively, *(A,B)* is a formal concept precisely when:
#
# * every object in *A* has every attribute in *B*,
# * for every object in *G* that is not in *A*, there is some attribute in *B* that
# the object does not have,
# * for every attribute in *M* that is not in *B*, there is some object in *A*
# that does not have that attribute.
class FormalConcept[O: Object, A: Object]
# Concept attributes
var attributes = new HashSet[A]
# Concept objects
var objects = new HashSet[O]
# Is `self` a subconcept of `super_concept`?
#
# A concept C1 is a subconcept of C2 if C2 has all the objects of C1.
fun is_subconcept(super_concept: FormalConcept[O, A]): Bool do
if self == super_concept then return false
if objects.length > super_concept.objects.length then return false
return super_concept.objects.has_all(objects)
end
redef fun to_s do return "{attributes}\n{objects}"
end
# Concept Lattice
#
# Formal concepts are partially ordered with regard to inclusion of their extents
# or (which is equivalent) inverse inclusion of their intent.
class ConceptLattice[O: Object, A: Object]
super POSet[FormalConcept[O, A]]
# Build `self` from a set of formal `concepts`.
init from_concepts(concepts: Set[FormalConcept[O, A]]) do
for c in concepts do
add_node c
end
for c1 in concepts do
for c2 in concepts do
if c1 == c2 then continue
if not is_lower_neighbour(c1, c2, concepts) then continue
add_edge(c2, c1)
end
end
end
# Is `sub` the greatest lower bound of `sup` considering all `concepts`?
fun is_lower_neighbour(sub, sup: FormalConcept[O, A], concepts: Set[FormalConcept[O, A]]): Bool
do
if sub == sup then return false
if not sub.is_subconcept(sup) then return false
for concept in concepts do
if sub == concept then continue
if sup == concept then continue
if not sub.is_subconcept(concept) then continue
if not concept.is_subconcept(sup) then continue
return false
end
return true
end
end
lib/fca/fca.nit:15,1--253,3