ILOG 3 Traitement Informatique des Universit Paris 13/Youn s …bennani/tmpc/TID/tid2.pdf · 2005-10-01 · Universit Paris 13/Youn s Bennani Traitement Informatique des Donn es 3

Université Paris 13/Younès Bennani Traitement Informatique des Données 1

2 Younès BENNANI

ILOG 3

TraitementInformatique desDonnées



Bayes ClassifierHypothèse de Multi-normalité

xx

x

x

x

x

x

x

x

x

oo

o

oo

oo

o

o

oo

ll

l

l

l

ll

l

ll

l

l

l

l

!1

"1

!2

"2

!3

"3

La fonction de décision est :

gi(X ) = !1

2(X ! µi )

t" i

!1(X ! µi) !

n

2ln 2#[ ] !

1

2ln " i[ ] + ln P(Ci )[ ]

La frontière entre les classes :gij(X ) = gi(X) ! gj(X)


Bayes ClassifierHypothèse de Multi-normalité


Notions de distances

Définir une distance entre un objet et une classe à partir de la distance entre objets

(formes) :

Approche la plus simple et la plus intuitive en RdF.

Un élément appartient à une classe s'il est plus proche de cette classe que

toutes les autres.

La distance dépend de la forme à traiter et des paramètres extraits.

xx

x

x

x

x

x

x

x

x

oo

o

oo

oo

o

o

oo

X+


Définition d’une distance

E : ensemble de points,

Espace métrique réel s'il existe une fonction :

d : ExE ! !

vérifiant :

1. " (x,y) # E2, x#y $ d(x,y) > 0, (séparabilité)

2. " x # E, d(x,x) = 0, (réflexivité)

3. " (x,y) # E2, d(x,y)=d(y,x), (symétrie)

4. " (x,y,z) # E3, d(x,z) $ d(x,y) + d(y,z). (inégalité triangulaire)


Exemples de distances

Distance de Hamming

X = xi{ }i=1Kn

=

x1

x2

M

xn

!

"

#

# #

$

%

&

& &

Y = yi{ }i=1Kn

d1(X,Y) = xi ! yi

i=1

n

"

d2(X,Y ) = xi ! yi( )

2

i=1

n

"

dk (X,Y ) = xi ! yii=1

n

"k#

$ % &

' (

1

k

d! (X,Y ) = max i=1Kn xi " yi

Distance Euclidienne

Distance dk

Distance du maximum

E : ensemble de points, (X,Y) # E2


Distances entre formes etclasses

Plus la distance est petite, plus on admet que la ressemblance est

grande.

xx

x

x

x

x

x

x

x

x

oo

o

oo

oo

o

o

oo

X

+

Ci

Cj

d (Ci, Cj)

d2(X,Y ) = xi ! yi( )

2

i=1

n

"

• La distance d entre deux classes Ci et Cj est définie par :

d (Ci ,Cj) = inƒ d X,Y( ) ; X !Ci et Y !Cj{ }

d (X, Cj)

d (X, Ci)


Distances binaires

• caractéristiques des formes ne sont pas mesurables.

• codage binaire : 1 % présence de l’attribut (caractère)

0 % absence de l’attribut

• Le nombre de fois où X et Y possèdent le même caractère (couples de 11)

• Le nombre de fois où X et Y ne possèdent aucun caractère commun (couples de 00)

• Le nombre de fois où X ne possède pas le caractère possédé par Y (couples de 01)

• Le nombre de fois où X possède un caractère non possédé par Y (couples de 10)

a = xi .yii=1

n

!

b = 1 ! xi( )i=1

n

" 1 ! yi( )

h = 1 ! xi( )i=1

n

" .yi

g = xi . 1 ! yi( )i=1

n

"


Quelques distances binaires

• Russel et Rao

• Joccard et Needham

• Dice

• Sokal et Sneath

S1(X,Y ) =

a

a + b + g + h

S2(X,Y ) =

a

n ! b

S3(X,Y ) =

a

2a + g + h

S4(X,Y) =

a

a + 2(g + h)

S5(X,Y ) =a + b

n

S6 (X,Y ) =a

g + h

• Sokal et Michenon

• Kulzinsky


Exemple

Caractéristiques

Rond Allongé Rouge Vert

1 0 1 0

0 1 0 1

1 0 0 1

S2( , )=0 et S2( , )=0.33

et se ressemblent plus que et


MDC: Minimum-Distance Classifier

M classes { C1,C2,..., CM }, M prototypes Y = { Y1,Y2,..., YM } dans !n

on cherche à identifier la forme X.

• Attribuer un élément X à une classe Ck :

X !Ck " Ck = ArgminCi

d X,Ci( )

!

Di= d X,C

i( ) = d(X,Yi ) = X "Yi( )t

X "Yi( )[ ]1

2,1# i # M

Dk= min1!i!M

d(X,Yi)( )

xx

x

x

x

x

x

x

x

!

oo

o

oo

oo

o

o

oo

ll

l

l

l

ll

l

ll

l

l

l

l

Y1

Y3

Y2

!

!



• Fonction de décision pour Ci :

Di

2 = X ! Yi( )t

X ! Yi( )[ ]

= X tX ! 2Xt

Yi+ Y

i

tYi

Constante

minimiser Di

2

!2Xt

Yi+ Y

i

t

Yi, 1 " i " M! minimiser

maximiser c2X

t

Yi! Y

i

t

Yi, 1 " i " M

gi(X ) = XtYi !

1

2YitYi , 1 " i " M

X #Ci ssi gi(X) > gj (X), j $ i



• Fonction de décision linéaire :

gi(X ) = XtYi !

1

2YitYi , 1 " i " M

gi(X ) = Wi

tX, 1! i ! M

X =

x1

x2

M

xn

1

!

"

#

#

# #

$

%

&

&

& &

Wi =

wi,1

wi, 2

M

wi, n

wi ,n+1

!

"

#

#

# #

$

%

&

&

& &

=

yi,1

yi, 2M

yi, n

'1

2YitYi

!

"

#

#

# #

$

%

&

&

& &



• Cas Multi-prototypes :

Ci! Y

i

(1),Y

i

(2),K, Y

i

(ni)

Di = min1! j! ni

d(X,Yi

( j ))( )

gi(X ) = XtYi

( j )!1

2Yi( j )( )

t

Yi

( j ), 1 " j " ni

X #Ci ssi gi(X) > gj (X), j $ i

• Fonction de décision pour Ci :

xx

x

x

x

x

x

x

x

!

oo

o

oo

oo

o

o

oo

ll

l

l

l

ll

l

ll

l

l

l

l

!

!

!

!

!

! !

!

!

Y1

(1),Y1

(2),Y1

(3),Y1

(4 )

!

Y2

(1),Y

2

(2),Y

2

(3)

!

Y3

(1),Y

3

(2)


MDC: Minimum-Distance ClassifierExemple

C1

! (1, 0), (1,1)

C2

! (0,1), (3,1)

C3

! (1,2), (0, 0), ("1,1)

X = (1,"1)#?

Consider a three-class problem in R2 where each class is represented

by its prototypes as follows:

Given the incoming pattern :



!

g1(X) = x

1,x

2( ) 1,0( )t"1

21,0( ) 1,0( )

t= x

1"1

2

g2(X) = x

1,x

2( ) 0,1( )t"1

20,1( ) 0,1( )

t= x

2"1

2

g3(X) = x

1,x

2( ) 0,0( )t"1

20,0( ) 0,0( )

t= 0

!

D1

=min d X, 1,0( )( ),d X, 1,1( )( )[ ]" 1,0( )

D2

=min d X, 0,1( )( ),d X, 3,1( )( )[ ]" 0,1( )

D3

=min d X, 1,2( )( ),d X, #1,1( )( ),d X, #1,1( )( )[ ]" 0,0( )

!

g12(X) = g

1(X) " g

2(X)= x

1" x

2= 0

g23(X) = g

2(X) " g

3(X)= x

2"1

2= 0

g31(X) = g

3(X) " g

1(X)=

1

2" x

1= 0

Les fonctions de décision :

Les frontières entre les 3 classes :

entre C1 et C2

entre C2 et C3

entre C3 et C1

! X "C1

g1(X) =

1

2, g

2(X) = !

3

2, g

3(X ) = 0

C1

! (1, 0), (1,1)

C2

! (0,1), (3,1)

C3

! (1,2), (0, 0), ("1,1)

X = (1,"1)#?


La frontière entre les classes :

gij(X ) = gi(X) ! gj(X) = 0

!

X = (1,"1)

x1=1

2

x1

x2


!

g12(X) = g

1(X) " g

2(X)= x

1" x

2= 0

g23(X) = g

2(X) " g

3(X)= x

2"1

2= 0

g31(X) = g

3(X) " g

1(X)=

1

2" x

1= 0

entre C1 et C2

entre C2 et C3

entre C3 et C1

!

(1,0)

!

(1,1)!

(1,2)

!

(0,0)!

("1,1)

!

(3,1)

!

(0,1)

!

x2

=1

2

!

x1

= x2

entre C1 et C2

entre C2 et C3

entre C3 et C1


Méthodes non paramétriquesk-Nearest Neighbour : KNNk-plus proches voisins : KPPV

N observations D = { X1

, X2

,...,XN

} dans !n

réparties en M classes {C1,C2,..., CM},

d(Xi

, Xj

) est une distance entre les observations Xi

et Xj

.

Règle du plus proche voisin (k=1) :

Xi

est affecté à la classe Cj si Cj est la classe de l'objet Xj

, tel que :

d(Xi

, Xj

) = min k#i, K=1…N

d(Xi

, Xk

), pour Xk

appartenant à D.

xx

x

x

x

x

x

x

x

x

oo

o

o

o oo

o

o

oo

Xi

Ci

x

x

x +o

oo

oo

oo

o

x

xx

x

x

x

Cj

Xj



Règle des k plus proches voisins :

Xi

est affecté à la classe Ci si Ci est la classe la mieux représentée parmi

les k voisins les plus proches de Xi

, tel que :

ki = max { k1, k2, …, kM } $ Xi

# Ci.

Avec ki = le nombre d’éléments de la classe Ci parmi les k voisins les plus proches de Xi

.

et k1+k2+ …+ kM = k

xx

x

x

x

x

x

x

x

x

oo

o

o

o oo

o

o

oo

Xi

Ci

x

x

x +o

oo

oo

oo

o

x

xx

x

x

x

Cj kj =3ki =5

k = 8


Algorithme des KNN

ErrBayes ! lim n"# ErrPPV ! 2ErrBayes

Début

on cherche à classer le point y

Pour chaque exemple (x,C(x)) de l’ensemble d’apprentissage

faire

Calculer la distance d(x,y) entre x et y

Fin pour

Dans les k points proches de y

compter le nombre d’occurrences de chaque classe

Attribuer à y la classe qui apparaît le plus souvent

Fin.



Propriétés de convergence en probabilité :

la probabilité d’erreur avec la règle du plus proche voisin (PPV)

converge en probabilité vers une quantité inférieure à deux

fois l’erreur minimum de la décision bayésienne, mais reste

supérieure ou égale à une fois cette erreur.

ErrBayes ! lim n"# ErrPPV ! 2ErrBayes

Considérations pratiques (heuristique) :

choisir k autour de où est le nombre

moyen de points d’apprentissage par classe.

!

mC

!

mC



Surface de séparation générée par KNN

Voronoi Net

Delaunay Net

Frontière entre

les 2 classes

Prototypes

de la classe 1

Prototypes

de la classe 2




Décision et Rejetvariante (k,l)-Nearest Neighbour(k,l)-NN

Décisions avec rejet :

consiste à fixer un seuil l de décision :

k/2 < l < k

et à décider que Xi

est affecté à la classe Ci si au moins l parmi

les k voisins les plus proches de Xi

appartiennent à Ci.

xx

x

x

x

x

x

x

x

x

oo

o

o

o oo

o

o

oo

Xi

Ci

x

x

x +o

oo

oo

oo

o

x

xx

x

x

x

Cj kj =3ki =5

(k,l) = (8,5) $ Xi

# Ci

(k,l) = (8,6) $ Rejet


Variantes accéléréesk-Nearest Neighbour : KNNk-plus proches voisins : KPPV

KNN = méthode lente en phase de décision

nécessite le calcul de N distances dans un espace

à n dimensions.

Variantes sub-optimales nécessitent moins de calcul :

• La condensation

[P.E. Hart, « The condensed Nearest Neighbor Rule » IEEE Transactions Information Theory, 14, May, 1968.]

• Le pavage

[C. Delannoy, « Un algorithme rapide de recherche de plus proches voisins » RAIRO Informatique,

14(3):275-286, 1980.]

• La hiérarchie

[J. H. Friedman, J. L. Bentley, R. A. Finkel, « An algorithm for finding best matches in logarithmic

expected time », ACM Transactions on Software, 3(3), 1977]

• Le tri

[T. P. Yunk, « A technique to identify Nearest Neighbors », IEEE Transactions on Systems, Man and

Cybernetics, 6:678-683, 1976]


Recherche des KNNMéthode de projection

J.H. Friedman, F. Baskett, L.J. Shustek

« An algorithm for finding nearest neighbors »IEE trans. Comput?, Vol. C-24, pp. 1000-1006, Oct. 1975

Méthode non-paramétrique KNN

Avantages :

- pas d’hypothèse sur les distributions

- simple à mettre en œuvre

- donne une probabilité d’erreur faible

Inconvénients :

- temps de calcul important

(recherche des knn)

- place mémoire

(stockage de l’ensemble des prototypes)


Recherche des KNNMéthode de projection : 2-dimension

Pré-traitement

Étape 0 :projeter l’ensemble des points sur un axe et trierles projections(projection+trie une seule fois pour l’ensemble des données)O(NlogN)

Recherche des knn

Étape 1 :localiser la projection du point test sur l’axe deprojection(recherche dichotomique O(logN))

Étape 2 :trouver les 2 plus proches projections(une de chaque coté)de la projection du point test

Étape 3 :calculer la distance (en dimension complète)entre les 2 prototypes et le point testchoisir le prototype minimisant cette distance : rd


Recherche des KNNMéthode de projection : 2-dimension

Étape 4 :déterminer les limites de la recherche

- borne #1=projection du test+rd- borne #2=projection du test -rd

Étape 5 :calculer et sauvegarder en mémoire les distances entre le test et les prototypes à l’intérieur desdeux bornes

Étape 6 :trouver le prototype minimisant la distance par rapport au test = le plus proche voisin

Pour la recherche des knn (k>1)

Étape 7 :supprimer le ppv (trouvé à l’étape 6) de la listedes prototypes à l’intérieur des bornesrépeter k fois de l’étape 1 à l’étape 7

Si k>1, les bornes sont recalculées à chaque itération.


Recherche des KNNMéthode de projection : d-dimension

Comment trouver le meilleur axe de projection ?


!Maximum coordinate

distance

2Euclidian

1Manhattan

npMetric


Étape 0.1 :projeter l’ensemble des points sur les d axes et trier les projections

Étape 0.2 :estimer le nombre n de distances à calculer dans lecas d’une distribution uniforme (worst case)

!

kd!( )1/ dN1"(1/ d )

!

" kdd

2#1

$

% &

'

( ) !

$

% &

'

( )

1/ d

2N( )1#(1/ d )

!

k1/ dN1"(1/ d )

K: le nombre des ppv, d: la dimension, N: le nombre de prototypes



Étape 1 :localiser la projection du test sur chaque axe

Étape 2 :trouver la position du (n/2)ème prototype de chaquecoté du test

Étape 3 :calculer la distance S entre ces 2 prototypes

Étape 4 :calculer la projection de la densité locale D au voisinage du point test (local projected density) :

Étape 5 :sélectionner l’axe minimisant D et l’utiliser pourla recherche des knn (méthode 2-dimension)!

D = n /S


Nettoyage (editing) de l’ensembled’apprentissage

Début

diviser aléatoirement l’ensemble d’apprentissage en deux

sous-ensembles S1 et S2

tant que la stabilisation de S1 et S2 n’est pas réalisée

faire

1-classer tous les points de S1 sur S2 par la règle du 1-ppv

2-éliminer de S1 tous les points dont la classe n’est pas la même

que celle de leur plus proche voisin dans S23-classer tous les points de S2 sur le nouveau S1 par la règle du 1-ppv

4-éliminer de S2 tous les points dont la classe n’est pas la même

que celle de leur plus proche voisin dans S1

fin tant que

L’ensemble d’apprentissage nettoyé est composé de S1& S2

fin.


Condensation (condensing) de l’ensembled’apprentissage

Début

ordonner les m exemples d’apprentissage de x1 à xminitialiser S par x1 et G par x2 à xm

tant que S et G ne sont pas stabilisés faire

pour

chaque point gi de G faire

si le 1-ppv de gi dans S n’a pas la même classe que gi alors

enlever gi de G et le mettre dans S

fin si

fin pour

fin tant que

L’ensemble d’apprentissage condensé est S

fin.


Exercice : K-NN

C1 ! (0,3), (0, 2), (0,1), (0, 0), ("1,0), ("2, 0)

C2 ! (1,3), (1,1),(1,0), (0, "1)

X = (1,4)#? avec 1 " NN, 3 " NN et 5 " NN


Exercice (Corrigé)

C1 g1(X) C2 g2 (X)

(0, 3) 7.5 (1,3) 8

(0, 2) 6 (1,1) 4

(0,1) 3.5 (1,0) 0.5

(0, 0) 0 (0, !1) ! 4.5

(!1,0) !1.5

(!2, 0) ! 4

X = (1,4)

gi(X ) = XtYi !

1

2YitYi , 1 " i " M


1-NN

3-NN3-NN

3-NN 5-NN

5-NN

5-NN

5-NN

5-NN

5-NN => C1

3-NN => C1

1-NN => C2

x1

x2


Exercice (Corrigé)

gi(X ) = XtYi !

1

2YitYi , 1 " i " M

La frontière entre les classes :

gij(X ) = gi(X) ! gj(X) = 0


g1(X) = x1 x2( )0

3

!

" # $ % &1

20 3( )

0

3

!

" # $ %

= 3x2 &9

2

g2 (X) = x1 x2( )1

3

!

" # $ % &1

21 3( )

1

3

!

" # $ %

= x1 +3x2 & 5

g12(X) = g1(X) ! g2(X ) = 3x2 !9

2! x1 ! 3x2 + 5

= !x1 +1

2= 0

x1 =1

2

X = (1,4)

x1=1

2

x1

x2

Documents

ILOG 3 Traitement Informatique des Universit Paris 13/Youn s …bennani/tmpc/TID/tid2.pdf · 2005-10-01 · Universit Paris 13/Youn s Bennani Traitement Informatique des Donn es 3