Cours

Notions de bases sur les treillis et les systèmes

de fermeture en data mining
K. BELATTAR,
Département Informatique - Université d’Alger 1
11/04/2021 1
Relation d’ordre
Soit 𝐸 un ensemble fini, une relation binaire 𝑅 sur un ensemble non vide 𝐸 et une partie de 𝐸* 𝐸, noté X R 𝑌;
𝑋, 𝑌 ∈ 𝑅.
On dit 𝑅 est une relation d’ordre (binaire) sur 𝐸 ssi:
∀ 𝑋, 𝑌, 𝑍 ∈ 𝐸:
1.𝑅 est reflexive : X 𝑅 𝑋
2.𝑅 est anti symétrique: X 𝑅 𝑌 et Y 𝑅 𝑋 → 𝑋 = 𝑌
3.𝑅 est transitive: X 𝑅 𝑌 et Y 𝑅 𝑍 → X 𝑅 𝑍
(𝐸, 𝑅) est un ensemble ordonné.
Exemple:
1) A={1,2,3}
R={(1,1), (2,2), (3,3)}
R est une relation d’ordre sur A.
2) (≤, R).
3) (⊆, P(E))
Relation d’ordre
11/04/2021 2
Relation de couverture
Soit ∝. est une relation de couverture associée à un ensemble ordonné
(𝐸, R). Elle est définie comme suit :
𝑋 ≤. 𝑌 ⇔ 𝑋 ≤ 𝑌 et ∄: 𝑋 < 𝑍 < 𝑌
𝑌 couvre 𝑋
Exemple:
E={A,B,C,D}
1) AB ⊆. ABC, ⊆. est une relation de couverture.
2) A ⊆. ABC, ⊆. n’est pas une relation de couverture.

11/04/2021 3
Opérateurs sur les ensembles ordonnés
Soit 𝑃 ⊆ 𝐸.
𝑃
A) 𝑴𝒂𝒙(𝑷)/𝑴𝒊𝒏(𝑷)
𝑀𝑎𝑥 𝑃 : Le plus grand élément (selon ≥) de P. X
M
𝑀𝑎𝑥 𝑃 ≥ ={∃ M ∈ 𝑃 / M ≥ X}
𝑚𝑖𝑛(𝑃): Le plus petit élément (selon ≤) de P. 𝑀𝑎𝑥 𝑃 ≤
𝑚𝑖𝑛 𝑃 ≤ ={m ∈ 𝑃 / m ≤ X}
𝑃
Exemples:
P = CD, CDE, ACD, BDE, ACDE X
m
𝑀𝑎𝑥 𝑃 ≥ ={BDE, ACDE}
𝑀𝑖𝑛 𝑃 ≤ ={CD,BDE} 𝑀𝑖𝑛 𝑃 ≤

11/04/2021 4
Opérateurs sur les ensembles ordonnés
B) 𝑈𝐵/L𝐵 (ensembles majorant/minorant)
𝑈𝐵 𝑃 = ∩𝑋∈𝐸 UB X
Avec UB X ={M ∈ 𝐸 / X ≤ M}
L𝐵 𝑃 =∩𝑋∈𝐸 LB X
Avec LB X ={m ∈ 𝐸 / m ≤ X}
Exemples:
UB({A, B})=UB({A}) ∩ UB({B)}={A,AB,AC,ABC} ∩{B,AB, BC,ABC}= {AB,ABC}
LB({AB,AC})=LB({AB}) ∩ LB({AC)}={∅, 𝐴, 𝐵} ∩ {∅, 𝐴, 𝐶}={∅, 𝐴}

11/04/2021 5
Opérateurs sur les ensembles ordonnés
C) Meet (borne Inf)/Join (borne Sup)
Meet: le(s) plus grand(s) minorant(s), noté 𝑋 𝑌,
Meet (P) =𝑀𝑎𝑥 𝑃 ≥ (𝐿𝐵 𝑃 )
Join: le(s) plus petit(s) majorant(s), ), noté 𝑋 𝑌,
Join (P) =𝑀𝑖𝑛 𝑃 ≤ (𝑈𝐵 𝑃 )

Exemples:
Meet({AB,AC})= {𝐴}
Join({A, B})={AB}

11/04/2021 6
Opérateurs sur les ensembles ordonnés
D) Treillis d’une relation (binaire)
On appelle un treillis, un ensemble ordonné (𝐸, ≤) dans lequel toute
paire d'éléments 𝑋, 𝑌 admet à la fois un meet (borne inférieure) et un
join (borne supérieure).

Exemple:
L’ensemble des parties d'un ensemble E
est un treillis T. 𝑇
𝐸

𝑎 ,..
Treillis des parties d'un ensemble de 3 éléments
11/04/2021 7
Opérateurs sur les ensembles ordonnés
D) Treillis complet d’une relation (binaire)
Soit (𝐸, ≤) 𝑢n ensemble ordonné.
𝑇 ⊆ 𝐸 est un treillis complet ssi:
∃ 𝑚𝑒𝑒𝑡 𝑇 𝑒𝑡 𝑢𝑛𝑖𝑞𝑢𝑒
∃ 𝑗𝑜𝑖𝑛 𝑇 𝑒𝑡 𝑢𝑛𝑖𝑞𝑢𝑒

Exemple:
𝑇 ⊆ 𝑃 𝐸 , est un treillis complet des parties d'un ensemble E.
∃ 𝑚𝑒𝑒𝑡 𝑇 =∩𝑋∈𝑇 𝑋
∃ 𝑗𝑜𝑖𝑛 𝑇 =∪𝑋∈𝑇 𝑋
11/04/2021 8
 Chaines et anti-chaines

Soit 𝑃 ⊆ 𝐸 et 𝑃 est une chaine si et seulement si tous les éléments de 𝑃

sont comparables.
𝑃 est une anti-chaine ssi il existe des éléments de 𝑃 sont
incomparables.
P(E)
P(E)
B
Exemples:
A A
B
(≤, R) est une chaine (∀ X, Y ∈ 𝑅, X ≤ Y ou Y ≤ 𝑋)
(⊆, P(E)) une anti-chaine.
A,B ⊆ P E , A ⊆ 𝐵 B⊆𝐴
11/04/2021 9
 Ensembles totalement/partiellement ordonnés

(E, ≤) est un ensemble totalement ordonné ssi E est une chaine.

(E, ≤) est un ensemble partiellement ordonnée ssi E est formé de chaines et anti-
chaines.

Exemples:

𝑅 est totalement ordonné par ≤.

𝑃 𝐸 est partiellement ordonné par ⊆;
(∀ A,B ⊆ P E , A ⊆ 𝐵 𝑜𝑢 B ⊆ 𝐴) et
(∀ A,B ⊆ P E , A ⊆ 𝐵 𝑒𝑡 B ⊆ 𝐴)

11/04/2021 10
Transversal
 Soit R est un ensemble, et une base de données structurée D ⊆
𝑃 𝑅 .
𝑇 ⊆ 𝑅 est un transversal de D ssi:
∀ 𝑙′ 𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡 𝑚𝑜𝑡𝑖𝑓 𝑌 ∈ 𝐷, 𝑌 ∩ 𝑇 ≠ ∅.
 Tous sur ensemble de 𝑇 est un transversal.
Exemple:
Soit la base de données structurées D suivante:
Id Motif
1 ACD
2 ABCE AB est un transversal de D
3 BE

11/04/2021 11
Transversal minimal
X ⊆ 𝑅 est un transversal minimal de D, noté Tr D ssi:
1) 𝑋 est un transversal.
2) ∀ 𝑥 ∈ 𝑋, 𝑋 − 𝑥 n’est pas un transversal.
Propriété:
Tr D = 𝑇𝑟 (𝑚𝑖𝑛 𝐷 )
Exemple:
AB est un transversal minimal de D , noté Tr D :
- AB est un transversal,
- A n’est pas un transversal (car 𝐴 ∩ 𝐵𝐸 = ∅), et
- B n’est pas un transversal (car 𝐵 ∩ 𝐴𝐶𝐷 = ∅).
11/04/2021 12
Algorithme de Berge
Soit D = {𝑋1 , 𝑋2 , … 𝑋𝑛 } ⊆ 𝑃(𝑅) est une base de données structurée:
L’algorithme de Berge se base sur le calcul récursive de tous les transverses
minimaux de la base de donnée D.
𝑆1 = {{𝑥} / 𝑥 ∈ 𝑋1 },
….,
𝑇𝑟 𝑆𝑛 = 𝑀𝑖𝑛≤ {𝑋 ∪ {𝑦} / 𝑋 ∈ 𝑇𝑟 𝑆𝑛−1 , 𝑦 ∈ 𝑋𝑛 }
Exemple:
𝐷1 = 𝐴𝐵, 𝐴𝐶
𝑇𝑟 𝐷1 = 𝑆2
𝑆1 = {𝐴, 𝐵}𝐴𝐶
𝑆2 = 𝑀𝑖𝑛≤ {𝐴, 𝐴𝐶, 𝐴𝐵, 𝐵𝐶}
𝑆2 = {𝐴, 𝐵𝐶}
11/04/2021 13
Opérateur de fermeture
Soit (E, ≤) un ensemble ordonné.
L’application h: (E, ≤)  (E, ≤) est un opérateur de fermeture selon un
contexte C ssi:
1. X ≤ ℎ𝑐 𝑋 (extensive)
2. X ≤ 𝑌 → ℎ𝑐 𝑋 ≤ ℎ𝑐 𝑌 (isotone)
3. ℎ𝑐 (ℎ𝑐 𝑋 )=ℎ𝑐 𝑋 (idempotence)
- Fermeture de Galoi ℎ𝐷
- Fermeture d’Armstrong ℎ𝐹

11/04/2021 14
Fermeture de Galoi
Fermeture de Galoi
Soit le contexte (C) 𝐷 ⊆ 𝑃(𝑅) avec 𝑅 ensemble d’éléments.
La fermeture de Galoi ℎ𝐷 de motif 𝑋 est définie comme suit:
ℎ𝐷 (𝑋) =∩ 𝑌∈𝐷 𝑒𝑡 𝑋⊆𝑌 Y

ℎ𝐷 𝑋 : intersection des lignes de la base de données D contenant X.

Exemple: Id Motif
X=BD 1 ACD
ℎ𝐷 𝐵𝐷 = ABCDE 2 ABCDE
11/04/2021 3 BE 15
Axiomes d’Armstrong
Règles permettant de dériver de nouvelles dépendances fonctionnelles à
partir d’un ensemble de dépendances fonctionnelles.
Soit 𝑟(𝑅) une relation d’attributs 𝑅.

𝐴1 : 𝑅𝑒𝑓𝑙é𝑥𝑖𝑣𝑖𝑡é
Si X ⊆ 𝑌 alors Y → 𝑋
𝐴2 : 𝐴𝑢𝑔𝑚𝑒𝑛𝑡𝑎𝑡𝑖𝑜𝑛
Si X → 𝑌 et Z ⊆ 𝑊 alors X W → 𝑌Z
𝐴3 : 𝑇𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑖𝑡é
Si X → 𝑌 et Y → 𝑍 alors X →Z

11/04/2021 16
Axiomes d’Armstrong

𝐴4 : 𝑃𝑠𝑒𝑢𝑑𝑜 𝑡𝑟𝑎𝑛𝑠𝑖𝑡𝑖𝑣𝑖𝑡é
Si X → 𝑌 et YZ → 𝑊 alors XZ → 𝑊

𝐴5 : 𝐷é𝑐𝑜𝑚𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛
Si X → YZ alors X → 𝑌 et X → 𝑍

𝐴6 : 𝑈𝑛𝑖𝑜𝑛
Si X → 𝑌 et X → 𝑍 alors X → 𝑌𝑍
11/04/2021 17
Fermeture d’Armstrong

Soit 𝑟 relation d’attributs 𝑅 et 𝐹 un ensemble de dépendances

fonctionnelles valides sur 𝑟 R .
La fermeture d’Armtrong ℎ𝑓 est définie comme suit:
ℎ𝐹 𝑋 =∪𝑛𝑖=0 𝑍𝑖 𝑎𝑣𝑒𝑐 𝑍𝑛−1 = 𝑍𝑛
𝑒𝑡 𝑍0 = 𝑋
𝑍𝑛 =𝑍0 ∪{𝐴 ∈ R / XA et X ⊆ 𝑍𝑛−1 }

11/04/2021 18
Fermeture d’Armstrong
Exemple:
Soit 𝐹 ={AC, B E, E B, DA, DC}
Calculer la fermeture d’Armtrong de BD; ℎ𝐹 (𝐵𝐷).
𝑍0 = 𝐵𝐷,
𝑍1 = 𝐵𝐷𝐸 ( 𝑐𝑎𝑟 B E et B ⊆ 𝑍0 )
𝑍2 = 𝐴𝐵𝐷𝐸 (𝑐𝑎𝑟 D A et 𝐷 ⊆ 𝑍1 )
𝑍3 = ABCDE (𝑐𝑎𝑟 D C et 𝐷 ⊆ 𝑍2 )
𝑍4 = 𝐴𝐵𝐶𝐷𝐸 (car A C et 𝐴 ⊆ 𝑍3 )
𝑍5 = 𝐴𝐵𝐶𝐷𝐸 (car E B et 𝐸 ⊆ 𝑍4 )

11/04/2021 19
Algorithme de calcul de fermeture d’Armstrong
Entrées: 𝐹 ensemble de DF, X ⊆ 𝑅
Sortie: 𝐹𝑒𝑟𝑚 = ℎ𝐹 (𝑋).
𝐹𝑒𝑟𝑚 ← 𝑋
Répéter
Ancien ← 𝐹𝑒𝑟𝑚
Pour chaque DF ; 𝑋 → 𝐴 ∈ 𝐹 𝑓𝑎𝑖𝑟𝑒
si 𝑋 ⊆ 𝐹𝑒𝑟𝑚 𝑎𝑙𝑜𝑟𝑠
𝐹𝑒𝑟𝑚 ← 𝐹𝑒𝑟𝑚 ∪{A}
Jusqu’à Ancien= Ferm

11/04/2021 20
Système de fermeture
Dérivabilité des dépendances fonctionnelles
Soit un ensemble de dépendances fonctionnelles (𝐹) sur relation 𝑟
d’attributs 𝑅 et 𝑥, 𝑦 ⊆ 𝑅.
𝑥 → 𝑦 est dérivable à partir de 𝐹 (𝐹 ⊨ 𝑥 → 𝑦) ssi 𝑥 → 𝑦 peut etre
obtenu à partir de 𝐹 en appliquant les axiomes d’Armtrong.

Fermeture vs dérivabilité
𝐹 ⊨ 𝑥 → 𝑦  𝑦 ⊆ ℎ𝐹 (𝑥).

11/04/2021 21
Système de fermeture
Fermés
𝑋 est un fermé selon le contexte 𝐶 ssi:
ℎ𝐶 𝑋 = 𝑋
ℎ𝐹 𝑋 = 𝑋
ℎ𝐷 𝑋 = 𝑋
Clef
Soit 𝑋 un fermé, 𝑌 est un clef de 𝑋 ssi:

𝑌⊆𝑋
∀ 𝑦 ∈ 𝑌, 𝑦 ∉ ℎ𝐶 𝑥 − 𝑦

11/04/2021 22
Système de fermeture
Soient 𝑃 𝑅 , ⊆ , un contexte 𝐶 ∈ 𝐷, 𝐹 et ℎ un opérateur de
fermeture.
Un système de fermeture est défini comme suit:
𝑆𝐹 𝐶 = {𝑋 ⊆ 𝑅 / ℎ𝐶 𝑋 = X}
𝑆𝐹 𝐹 = {𝑋 ⊆ 𝑅 / ℎ𝐹 𝑋 = X}
𝑆𝐹 𝐷 = {𝑋 ⊆ 𝑅 / ℎ𝐷 𝑋 = X}

11/04/2021 23
Système de fermeture
Treillis de Galoi

𝑆𝐹 𝐶 , ⊆ est un treillis complet appelé Treillis de Galoi avec ∀ 𝜋 ⊆

SF C .

𝑀𝑒𝑒𝑡 𝜋 =∩𝑋∈𝜋 𝑋
𝐽𝑜𝑖𝑛 𝜋 = ℎ𝑐 (∪ 𝑋)

11/04/2021 24
Algorithmes de calcul de système de fermeture
Algorithme de Norris
Soit 𝐷 = 𝑋1 , 𝑋2 , … 𝑋𝑛 une base de données sur R 𝐷 ⊆ 𝑃 𝑅 .
On définit un système de fermeture de la base 𝐷; 𝑆𝐹 𝐷 comme suit:
𝑆𝐹0 = 𝑅
𝑆𝐹1 = 𝑅 ∪ 𝑋1 ∩ 𝑅
…
𝑆𝐹𝑛 = 𝑆𝐹𝑛−1 ∪ {𝑋𝑛 ∩ y / y ∈ 𝑆𝐹𝑛−1 }
Propriété
Si 𝑥, 𝑦 ∈ 𝑆𝐹 𝐷 alors 𝑥 𝑦 ∈ 𝑆𝐹 𝐷

11/04/2021 25
Algorithmes de calcul de système de fermeture
Exemple:

𝐷 = 𝐴𝐵𝐶𝐸, 𝐴𝐶𝐷, 𝐵𝐶𝐸, 𝐵𝐸

Calculer le système de fermeture de la base de donnée D.
𝑆𝐹0 = 𝐴𝐵𝐶𝐷𝐸
𝑆𝐹1 = 𝐴𝐵𝐶𝐷𝐸, 𝐴𝐵𝐶𝐸
𝑆𝐹2 = ABCDE, ABCE, ACD, AC
𝑆𝐹3 = ABCDE, ABCE, ACD, AC, BCE, C
𝑆𝐹4 = ABCDE, ABCE, ACD, AC, BCE, C, BE, ∅
𝑆𝐹 𝐷 = {ABCDE, ABCE, ACD, AC, BCE, C, BE, ∅}
11/04/2021 26
Algorithmes de calcul de système de fermeture
Ordre lexographique (dictionnaire)
Soit R, ≤𝑑 un ensemble totalement ordonné par l’ordre lexographique
(ordre dictionnaire).
R = {𝐴0 , 𝐴1 , … 𝐴𝑛 } 𝐴0 ≤𝑑 𝐴1 ≤𝑑 … ≤𝑑 𝐴𝑛

Exemple:
Si R = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸}
∅ ≤𝑑 𝐴 ≤𝑑 𝐵 ≤𝑑 𝐶 ≤𝑑 𝐷 ≤𝑑 𝐸

11/04/2021 27
Algorithmes de calcul de système de fermeture
Ordre lectique (dictionnaire inversé)
∀ x, y ⊆ 𝑅, 𝑥 ≤𝑙 𝑦 ⇔ 𝑀𝑎𝑥( 𝑥 − 𝑦) ≤𝑑 (𝑦 − 𝑥)

Exemples:
1) 𝐴𝐶𝐷 ≤𝑙 𝐴𝐵𝐶 ?
𝐷 ≤𝑑 𝐶
Les deux chaines ACD et ABC ne sont pas ordonnées selon l’ordre lectique.

2) E ≤𝑙 𝐴𝐵𝐸 ?
∅ ≤𝑑 𝐵
Les deux chaines E et ABE sont ordonnées selon l’ordre lectique.

11/04/2021 28
Algorithmes de calcul de système de fermeture
Opérateur « Next »
∀𝑥 ⊆ 𝑅, ∀𝐴𝑖 ∈ 𝑅
𝑁𝑒𝑥𝑡 𝑥, 𝐴𝑖 = 𝑥 ∪ 𝐴𝑖 -𝐴1 𝐴2 … 𝐴𝑛−1
Exemple:
𝑥 𝐴𝑖 𝑁𝑒𝑥𝑡 𝑥, 𝐴𝑖
AB C ABC – AB = C
AE D AED – ABC = DE
ABE C ABCE – AB= CE
D E DE-ABCD= E
AD B ABD-A=BD
11/04/2021 29
Algorithmes de calcul de système de fermeture
Opérateur « Next »

∀𝑥 ⊆ 𝑅, 𝐴𝑖 = 𝑀𝑖𝑛𝑑 (𝑅 − 𝑥)
Exemple:
𝑥 𝐴𝑖 𝑁𝑒𝑥𝑡 𝑥, 𝐴𝑖
AB C C
AD B BD
ABE C CE

11/04/2021 30
Algorithmes de calcul de système de fermeture
Algorithme « Next closure »

Soient 𝑓𝑒𝑟𝑚 ⊆ 𝑅, 𝑢𝑛 𝑓𝑒𝑟𝑚é ℎ 𝑓𝑒𝑟𝑚é = 𝑓𝑒𝑟𝑚 , 𝑒𝑡 𝐴𝑖 = 𝑀𝑖𝑛≤𝑑 (𝑅 −

𝑓𝑒𝑟𝑚).
Si 𝑚𝑎𝑥 ≤𝑑 ℎ(𝑛𝑒𝑥𝑡(𝑓𝑒𝑟𝑚, 𝐴𝑖 ) − 𝑓𝑒𝑟𝑚) = 𝐴𝑖
Alors ℎ 𝑛𝑒𝑥𝑡(𝑓𝑒𝑟𝑚, 𝐴𝑖 ) est un fermé selon l′ ordre lectique .

11/04/2021 31
 Algorithmes de calcul de système de fermeture
Exemple:
Soient 𝑅 = A, B, C , et la base de données 𝐷. D Motif
Calculer le système de fermeture de la base D.
1 AB
∅ ≤𝑙 𝐴 ≤𝑙 𝐵 ≤𝑙 𝐴𝐵 ≤𝑙 𝐶 ≤𝑙 𝐴𝐶 ≤𝑙 𝐵𝐶 ≤𝑙 𝐴𝐵𝐶 2 AC
ℎ𝐷 𝑋 = Fermés ∅ 𝐴 𝐴𝐵 𝐴𝐵 𝐴𝐶 𝐴𝐶 𝐴𝐵𝐶 𝐴𝐵𝐶 3 ABC

Ferm 𝑨𝒊 =𝑴𝒊𝒏≤𝒅 (𝑹 − 𝒇𝒆𝒓𝒎) 𝐱 = 𝒏𝒆𝒙𝒕(𝒇𝒆𝒓𝒎, 𝑨𝒊 ) 𝒉 𝒙 𝒎𝒂𝒙 ≤𝒅 (𝒉 (𝒏𝒆𝒙𝒕(𝒇𝒆𝒓𝒎, 𝑨𝒊 )) − 𝒇𝒆𝒓𝒎 ) = 𝑨𝒊 ?

∅ A A A A=A OUI
A B B AB B=B OUI
AB C C AC C=C OUI
AC B BC ABC B=B OUI
ABC Stop

𝑆𝐹 = {∅,A,AB,AC,ABC}
11/04/2021 32