Notes de Cours : Data Mining

y : un attribut nominal qu’on appelle la classe (ou étiquette) de l’exemplaire,

appartenant à un ensemble fini de classes qu’on dénote par Y.

-

Quand | |=2, on parle de classification binaire, sinon on parle de classification

multi-classes

On suppose que chaque exemplaire appartient à une et une seule classe, c’est-à-

dire la valeur vraie (mais inconnu) de y est unique pour chaque exemplaire.

Le but du PCS est : à partir de l’ensemble X, construire (ou induire, ou apprendre)

un classeur : une procédure (ou algorithme, ou programme) dont le input est le

p-tuple x d’un exemplaire quelconque, et le output est sa classe y.









On appelle X un échantillon d’apprentissage (training set).

Une fois un classeur est construit, il est nécessaire d’évaluer sa performance

(qualité), du moins pour le comparer avec d’autres classeurs, obtenus avec autres

méthodes d’apprentissage par exemple. La performance d’un classeur est le plus

souvent mesurée par son taux de classification correcte sur un autre échantillon,

appelé échantillon de test (testing set) ; c’est-à-dire la proportion d’exemplaires

dans l’échantillon de test pour lesquels le classeur donne la bonne réponse (selon

les données de l’échantillon bien sûr).

Une grave erreur que les data miners débutants souvent commettent consiste à

utiliser un échantillon de test qui n’est pas indépendant de l’échantillon

d’apprentissage. Or le taux de classification d’un classeur sur l’échantillon

d’apprentissage est presque toujours une estimation trop optimiste de la

performance vraisemblable du classeur.

A ce point, il est fondamental de distinguer deux processus différents et bien

séparés dans le lifecycle d’un classeur :

(1) l’induction (training) du classeur ; et

(2) l’utilisation du classeur comme un « Black Box ».

b) Approche très naïve : la méthode ZeroR

Ignore totalement les valeurs des attributs, d’où son nom ZeroR. Il existe en deux

versions principales :

o Version 1 : prédit y en prenant une valeur au hasard de l’ensemble Y.

o Version 2 : prédit y comme la classe la plus fréquente selon X .

Evidemment le processus de l’induction d’un classeur ZeroR est très simple : on a

qu’à stocker l’ensemble Y dans un tableau (version 1), ou calculer la classe la plus

fréquente (version 2).

Ce classeur a presque toujours un taux de classification très mediocre. Il est donc

inutile pour des applications réelles. On l’utilise seulement comme un baseline de

performance : la performance d’une méthode fiable doit être du moins

supérieure à celle du classeur ZeroR.

2) Approche Bayésienne et Méthodes Simples :

a) Introduction :

Cette approche se base sur une interprétation probabiliste des données x et y

d’un exemplaire quelconque comme étant des variables aléatoires X et Y.

Donc, le problème de prédire la classe y d’un exemplaire, basé sur ses attributs x

et l’ensemble X peut être résolu à partir des probabilités suivantes :



















Pr[y | x,X] ,  y Y

Ayant calculé toutes ces probabilités conditionnelles, on peut ensuite prédire la

classe y comme étant la classe la plus probable, c’est-à-dire :

y = argmaxy Y [ Pr[y | x,X] ]

Dans cette approche Bayésienne, l’induction (construction) du classeur consiste

"tout simplement" à estimer les valeurs de toutes les probabilités Pr[y|x,X] a

partir des exemplaires dans X, c’est-à-dire, on doit les estimer pour toutes les

différentes valeurs des attributs x et des classes y. Ces probabilités seront

stockées et prêtes à être utilisées pour prédire la classe de nouvelles données.

Cette approche est parfaitement fiable, sauf que, malheureusement, les

probabilités dont on parle au-dessus sont généralement trop difficiles à estimer

en pratique (du moins il nous faudrait un nombre colossal d’exemplaires…)

Cependant, cette approche est utile dans des cas spéciaux ou l’on peut faire des

simplifications, ce qui est le cas pour les méthodes de OneR et de Naïve Bayes.

b) Méthode OneR :

Il s’agit de simplifier l’approche Bayésienne (discutée au-dessus) en utilisant un

seul attribut (d’où son nom en Anglais "OneR"). Avec cette supposition, le calcul

des probabilités conditionnelles devient assez facile…

On suppose qu’on dispose de deux échantillons indépendants (non-joints) : de

training et de test.

La méthode d’induction d’un classeur OneR est comme suit :

o Tout d’abord on construit P classeurs, ou le ieme classeur utilise seulement

les valeurs du ieme attribut. Selon l’approche Bayésienne, pour induire le

ieme classeur on doit calculer la probabilité conditionnelle Pr[y|xi,X], pour

, et du ieme attribut, xi  Di

toutes les différentes valeurs de la classe, y

o Cette probabilité est estimée avec le rapport : Pr[y|xi,X]  n(xi,y)/n(xi), ou

n(xi,y) = nombre d’exemplaires dans X qui appartiennent à la classe y et pour

lesquels le ieme attribut a pour valeur xi

n(xi) = nombre d’exemplaires pour lesquels le ieme attribut a pour valeur xi

o Ensuite, on estime le taux de classification correcte de chacun de ces

classeurs.

o Finalement, on maintient le classeur le plus performant !

Exercice (TD) : base de données « jouer tennis »

c) Méthode de Naïve Bayes

















