University of Tlemcen Knowledge Representation

Faculty of Sciences Artificial intelligence

Computer Science department Mohammed Ismail SMAHI

TP n°4 : Représentation de l’Incertitude avec Dempster-Shafer

Ce travail pratique a pour but d’appliquer la théorie de Dempster-Shafer (DS) à un problème de classification
supervisée multi-classes. Contrairement aux méthodes probabilistes classiques, la théorie DS est choisie car elle
permet de modéliser et de distinguer explicitement l’incertitude et l’ignorance dans le processus de prise de décision.
Nous utiliserons le célèbre dataset Iris, composé de 150 échantillons de fleurs répartis en trois espèces (Setosa,
Versicolor, Virginica), chacune décrite par quatre attributs morphologiques.

1. Préparation des données

Préparation de l’environnement

— Librairie DS : Installation de la bibliothèque Py- 1 import pandas as pd

thon dédiée qui fournit les structures de données 2 import numpy as np
(Fonctions de Masse, Cadre de Discernement) et 3 import [Link] as plt
les opérations clés (règle de combinaison de Demps- 4 import seaborn as sns
5 from [Link] import load_iris
ter). 6 from sklearn.model_selection import
,→ train_test_split
1 pip install py_dempster_shafer 7 from [Link] import
,→ confusion_matrix, accuracy_score,
,→ classification_report
— Imports et Rôles : Nous importons plusieurs mo- 8 from pyds import MassFunction, powerset
dules, chacun ayant un rôle précis (chargement, ex- 9 import functools
ploration et traitement des données, etc.).

Chargement du Dataset
Le dataset Iris (Fisher, 1936) est un jeu de données classique en classification. Il contient 150 échantillons répartis
en 3 classes équilibrées : setosa, versicolor et virginica. Chaque fleur est décrite par 4 attributs numériques :
longueur du sépale, largeur du sépale, longueur du pétale et largeur du pétale. Ce dataset est idéal pour introduire la
théorie de Dempster-Shafer, car certaines classes sont faciles à distinguer tandis que d’autres présentent un overlap
important, ce qui crée de l’incertitude naturelle.

1 iris = load_iris()
2 df = [Link]([Link],
,→ columns=iris.feature_names)
3 df["class"] =
,→ [Link].from_codes([Link],
,→ iris.target_names)
4 feature_cols = list(iris.feature_names)
5 varieties = list(df["class"].unique())
6 [Link]()

Visualisation exploratoire
La visualisation des données est une étape préliminaire essentielle. Elle permet de comprendre la structure glo-
bale des données et d’évaluer visuellement la séparabilité des classes et l’existence d’un éventuel chevauchement

1
 University of Tlemcen Knowledge Representation
Faculty of Sciences Artificial intelligence
Computer Science department Mohammed Ismail SMAHI

(ambiguïté) entre elles. Cette analyse est déterminante pour justifier l’approche et le modèle retenus.
— Distributions des Attributs (Boîtes à mous- — Relations entre attributs (Pairplot) : Le pair-
taches) : Des boîtes à moustaches sont utilisées plot offre une vue d’ensemble des projections du
pour visualiser la distribution (médiane, dispersion dataset par paire d’attributs. Les graphiques hors
interquartile) de chaque attribut parmi les trois diagonale illustrent la séparabilité visuelle des
classes. Ces figures sont essentielles pour évaluer classes dans l’espace 2D, tandis que la diagonale
le chevauchement et la séparabilité potentielle présente la distribution univariée de chaque at-
des classes. tribut par des courbes de densité.

1 fig, axes = [Link](2, 2, figsize=(14, 1 [Link](df, hue='class',

,→ 10)) ,→ palette=['#FF6B6B', '#4ECDC4',
2 axes = [Link]() ,→ '#FDC830'],
3 colors = ['#FF6B6B', '#4ECDC4', '#45B7D1'] 2 diag_kind='kde', markers=['o', 's', 'D'])
4 for idx, col in enumerate(feature_cols): 3 [Link]('Relations entre attributs (par
5 ax = axes[idx] ,→ classe)', y=1.01, fontsize=14,
6 # Création du boxplot ,→ fontweight='bold')
7 [Link](column=col, by='class', ax=ax, 4 plt.tight_layout()
,→ patch_artist=True) 5 [Link]()
8 # Personnalisation 6
9 ax.set_title(f'Distribution de { col} ',
,→ fontsize=12, fontweight='bold')
10 ax.set_xlabel('Classe', fontsize=10)
11 ax.set_ylabel('Valeur (cm)', fontsize=10) Tâche 1 : Interprétation des grpahes
12 ax.get_figure().suptitle('') # Retirer le
,→ titre automatique Analyser les différents graphiques exploratoire afin
13 [Link]('Distributions des attributs d’identifier les couples d’attributs discriminants, de
,→ par classe', fontsize=16, repérer les zones d’overlap (chevauchement) entre
,→ fontweight='bold', y=1.00)
classes, et d’expliquer en quoi ces différentes obser-
14 plt.tight_layout()
15 [Link]() vations justifient le recours à la théorie de Dempster-
Shafer (D-S) pour une tâche de classification.

Séparation des données

Afin de pouvoir évaluer la performance du classifieur ratio de 80% pour l’apprentissage et 20% pour le test
de manière objective, le jeu de données initial est sé- (test_size=0.20).
paré en deux sous-ensembles : une base d’apprentissage
(train_df) et une base de test (test_df). Tâche 2 : Justification de la Séparation des
Données
1 train_df, test_df = train_test_split(df, Expliquez l’importance et le rôle des deux pa-
,→ test_size=0.20, random_state=42, ramètres de contrôle utilisés lors de la sé-
,→ stratify=df["class"])
paration du dataset Iris random_state=42 et
stratify=df["class"].
La fonction train_test_split est utilisée avec un

2
 University of Tlemcen Knowledge Representation
Faculty of Sciences Artificial intelligence
Computer Science department Mohammed Ismail SMAHI

2. Construction du modèle DS
La Fonction de Masse de Base (BMF) est construite de manière incrémentale selon les étapes suivantes : (1)
définition du cadre de discernement Ω comme l’ensemble des classes ; (2) extraction des intervalles [min, max]
pour chaque attribut et chaque classe ; (3) dérivation d’une hypothèse H ∈ Ω à partir de la valeur observée ; (4)
conversion de cette hypothèse en degrés de croyance sous forme de compteurs ; (5) normalisation de ces compteurs
et construction des fonctions de masse correspondantes.
Définition du cadre de discernement (Ω)
La partie du code, ci-dessous, établit le Cadre de Discer- une hypothèse de l’ensemble de puissances (2Ω ), essen-
nement avec l’ensemble des trois classes d’Iris : tielle pour attribuer des masses de croyance ultérieure-
ment.
1 omega = frozenset(varieties)
2 def empty_hypothesis(): Tâche 3 : Taille de l’Ensemble de Puissances
3 """Crée un dictionnaire"""
4 return [Link](powerset(omega),0.0) Afficher la taille du dictionnaire représentant la
BMF, qui correspond au nombre total d’hypothèses
La fonction empty_hypothesis() initialise ensuite une de l’ensemble de puissances (2Ω ).
BMF nulle. Elle crée un dictionnaire où chaque clé est
Extraction d’intervalles
Le but de cette partie est de déterminer la plage de va-
leurs (min,max) pour chaque attribut morphologique au
sein de chacune des trois classes du dataset Iris. Ces in- 1 def compute_class_ranges(df, feature_cols,
,→ class_col="class"):
tervalles statistiques sont cruciaux car ils définissent les 2 """Calcule les intervalles [min, max] pour
frontières utilisées pour attribuer les masses de croyance ,→ chaque classe et chaque attribut."""
dans la théorie de Dempster-Shafer (D-S). 3 class_ranges = {}
4 for c in varieties:
Tâche 4 : Détermination des intervalles 5 sub = df[df[class_col] == c]
6 ranges_c = {}
Appliquez cette fonction sur votre (train_df). Affi- 7 for f in feature_cols:
chez le dictionnaire obtenu et analysez visuellement, 8 ranges_c[f] = (sub[f].min(),
pour chaque attributs, les différents intervalles. Sur ,→ sub[f].max())
9 class_ranges[c] = ranges_c
la base de ces intervalles, quels sont les chevauche- 10 return class_ranges
ments les plus significatifs ?

Fonction de Dérivation d’Hypothèse 1 def hypothesis(varieties, class_ranges,

Ce bloc de code définit la fonction clé hypothesis, qui ,→ feature, value):
2 hset = []
associe une valeur observée aux classes compatibles se-
3 for c in varieties:
lon les intervalles appris. L’hypothèse retournée consti- 4 low, high = class_ranges[c][feature]
tue l’élément sur lequel la masse de croyance (BMF) est 5 if low < value < high:
attribuée pour l’attribut considéré. 6 [Link](c)
7 return frozenset(hset)

3
 University of Tlemcen Knowledge Representation
Faculty of Sciences Artificial intelligence
Computer Science department Mohammed Ismail SMAHI

Tâche 5 : Application de la Fonction d’Hypothèse

Pour valider la logique de la fonction hypothesis, exécutez-la sur les échantillons suivant : test_indices =
[0, 50, 100]. Démontrez que la fonction hypothesis génère des hypothèses singulières pour les échantillons
non ambigus (indices 0 et 50) et potentiellement ambigus (indice 100), et expliquez pourquoi.

Conversion Hypothèse → Degré de Croyance (compteurs)

Lorsqu’un attribut génère une hypothèse H à partir d’une L’idée est simple : plus une hypothèse est précise, plus le
valeur observée (exp. la longueur du pétale), il faut conver- compteur correspondant est renforcé. Ainsi, chaque type
tir cette hypothèse en un degré de croyance. Pour cela, d’hypothèse (∅, singleton, ensemble ambigu, ensemble to-
nous utilisons un ensemble de compteurs associés à tous tal) déclenche une action spécifique sur les compteurs,
les sous-ensembles de Ω. selon cette algorithme 1.

Algorithme 1 : Compt. de croyance (m.à.j) 1 def update_hypothesis(count_dict, h, omega):

Input : Dictionnaire des compteurs C, 2 """
3 Met à jour les compteurs selon le type
hypothèse h, cadre de discernement Ω ,→ d'hypothèse h.
Output : Compteurs mis à jour 4 """
if h = ∅ then 5 if len(h) == 0:
C[Ω] ← C[Ω] + 1.0 // Pure ignorance 6 count_dict[omega] += 1.0
7 ...
else
if |h| = 1 then
C[h] ← C[h] + 0.9 Tâche 6 : M-à-j des compteurs d’hypothèses
C[Ω] ← C[Ω] + 0.1 // Inf. précise À partir de l’algorithme de mise à jour des comp-
else teurs présenté ci-dessus : (1) Implémentez en Python
C[h] ← C[h] + 0.9 la fonction correspondante à l’algorithme. (2) Véri-
C[Ω] ← C[Ω] + 0.1 // Inf. ambiguë fiez le résultat de la fonction, en l’appliquant sur des
end exemples aléatoires.
end

Normalisation et construction des Mass Functions

L’Algorithme 2 met en œuvre la combinaison des fonctions de masse dans le cadre de la théorie de Dempster-
Shafer selon les étapes suivantes :

1. Construction des fonctions de masse élé- tenir une fonction de masse mf valide, qui est ajou-
mentaires : Chaque attribut f ∈ feature_cols tée àPl’ensemble M. Cette normalisation garantit
est traité comme une source d’évidence indépen- que A∈Ω mf (A) = 1.
dante. La valeur observée est traduite en une hy-
pothèse hf ⊆ Ω (via la fonction hypothesis()).
Les compteurs associés sont mis à jour, via 1 def normalize(dic):
update_hypothesis(), puis normalisés afin d’ob- 2 return MassFunction(dic).normalize()

4
 University of Tlemcen Knowledge Representation
Faculty of Sciences Artificial intelligence
Computer Science department Mohammed Ismail SMAHI

2. Fusion des sources d’évidence représente le degré de conflit entre les sources.
Les fonctions de masse élémentaires sont combi- En pratique, cette combinaison est réalisée de ma-
nées à l’aide de la règle conjonctive de Dempster. nière récursive par application successive de l’opé-
La fonction de masse résultante m est définie par : rateur conjonctif, ce qui correspond directement à
4 l’instruction suivante :
1 X Y
m(A) = mi (Bi ), ∀A ⊆ Ω,
1−K 1 [Link](lambda a, b: a & b,
B1 ∩···∩Bn =A i=1
,→ mass_list)
où
X 4
Y
K= mi (Bi )
B1 ∩···∩Bn =∅ i=1

Tâche 7 : Génération des Masses Globales

Implémentez en Python l’algorithme de combinaison des fonctions de masse fondé sur la théorie de Dempster-
Shafer, tel que décrit dans l’Algorithme 2.

Algorithme 2 : Combinaison des fonctions de

masse pour un échantillon
1 def combine_masses_for_sample(sample,
Input : Échantillon x, ensemble des attributs ,→ feature_cols, varieties, class_ranges,
F , variétés V , intervalles de classes R, ,→ omega):
cadre de discernement Ω 2 """ Combine les fonctions de masse de tous
,→ les attributs pour un échantillon
Output : Fonction de masse combinée m 3 donné et retourne la valeur combinée. """
M←∅ 4
for chaque attribut f ∈ F do 5 mass_list = []
mf ← empty_hypothesis() 6 # TODO 1
7 for f in ... :
hf ← hypothesis(V, R, f, x[f ])
8 ...
update_hypothesis(mf , hf , Ω) 9 ...
mf ← normalize(mf ) 10
M ← M ∪ {mf } 11 # TODO 2
12 combined = ...
end 13
M
m← mi 14 return combined
mi ∈M
return m

Prise de décision
Une fois les fonctions de masse combinées, le résultat exprime une incertitude globale qui ne permet pas de décider
immédiatement. L’Algorithme 3 transforme cette information en une décision concrète. Selon l’attitude adoptée
face à l’incertitude, on choisit une stratégie de décision spécifique. Les stratégies de décision considérées (pour ce
TP) sont les suivantes :

5
 University of Tlemcen Knowledge Representation
Faculty of Sciences Artificial intelligence
Computer Science department Mohammed Ismail SMAHI

Algorithme 3 : Prise de décision à partir d’une — Maximisation de la masse, qui retient l’hypo-
fonction de masse m thèse recevant le soutien direct le plus élevé :
Input : Fonction de masse m, mode
mode ∈ {mass, bel, pl, betp} 1 best_h = None
best_m = -1
Output : Classe sélectionnée ω ∗ ∈ Ω 2
3 for A in [Link]():
if mode = mass then 4 if combined[A] > best_m:
A∗ ← arg maxA⊆Ω, m(A)>0 m(A) 5 best_h = A
else 6 best_m = combined[A]
7 result = best_h
if mode = bel then
calculer Bel(A) pour tout A ⊆ Ω
— Maximisation de la crédibilité (belief ), cor-
A∗ ← arg maxA⊆Ω, m(A)>0 Bel(A)
respondant à une décision prudente fondée sur les
else
évidences certaines :
if mode = pl then
calculer P l(A) pour tout A ⊆ Ω 1 bel = [Link]()
A∗ ← arg maxA⊆Ω, m(A)>0 P l(A) 2 result = max(bel, key=[Link])
else
// Mode pignistique direct — Maximisation de la plausibilité (plausibility ),
calculer BetP (ω) pour tout ω ∈ Ω adoptant une posture plus optimiste en privilégiant
ω ∗ ← arg maxω∈Ω BetP (ω) l’hypothèse la moins contredite :
return ω ∗
end 1 pl = [Link]()
end 2 result = max(pl, key=[Link])

end
— Transformation pignistique, qui convertit la fonc-
return A∗
tion de masse en une distribution de probabilité
afin d’obtenir directement une décision singleton :

1 betp = [Link]()
2 result = max(betp, key=[Link])

Tâche 7 : Prise de décision

— Implémentez l’algorithme de prise de décision décrit dans l’Algorithme 3. Votre implémentation devra
permettre de sélectionner une seule stratégie de décision (maximisation de la masse, de la crédibilité, de
la plausibilité ou transformation pignistique) et garantir une sortie mono-classe.
— Étendez l’algorithme de décision en ajoutant une stratégie de vote, la classe finale est issue du vote
majoritaire entre les 04 modes.

6
 University of Tlemcen Knowledge Representation
Faculty of Sciences Artificial intelligence
Computer Science department Mohammed Ismail SMAHI

3. Prédiction et évaluation
1. Analyse du code. Commentez la partie Prédiction et évaluation du code fourni en expliquant l’intérêt de
l’ajout de la fonction min_dist_attr à l’intérieur de la fonction ds_predict.
2. Autres stratégies de conversion d’hypothèses. Proposez d’autres fonctions permettant de convertir les
hypothèses en un degré de croyance, puis comparez les résultats obtenus avec ceux de la stratégie initiale déjà
implémentée par l’algorithme 1).
3. Changement du protocole d’exécution. Modifiez la configuration d’exécution afin d’utiliser un découpage
50% / 50% (apprentissage / test). Exécutez ensuite le code et commentez les résultats obtenus en les
comparant à la version initiale.