View
1
Download
0
Category
Preview:
Citation preview
Université Paris 13/Younès Bennani Traitement Informatique des Données 1
2 Younès BENNANI
ILOG 3
TraitementInformatique desDonnées
Université Paris 13/Younès Bennani Traitement Informatique des Données 2
Université Paris 13/Younès Bennani Traitement Informatique des Données 3
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)
Université Paris 13/Younès Bennani Traitement Informatique des Données 4
Bayes ClassifierHypothèse de Multi-normalité
Université Paris 13/Younès Bennani Traitement Informatique des Données 5
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+
Université Paris 13/Younès Bennani Traitement Informatique des Données 6
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)
Université Paris 13/Younès Bennani Traitement Informatique des Données 7
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 8
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)
Université Paris 13/Younès Bennani Traitement Informatique des Données 9
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
"
Université Paris 13/Younès Bennani Traitement Informatique des Données 10
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 11
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 12
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
!
!
Université Paris 13/Younès Bennani Traitement Informatique des Données 13
MDC: Minimum-Distance Classifier
• 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
Université Paris 13/Younès Bennani Traitement Informatique des Données 14
MDC: Minimum-Distance Classifier
• 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
!
"
#
#
# #
$
%
&
&
& &
Université Paris 13/Younès Bennani Traitement Informatique des Données 15
MDC: Minimum-Distance Classifier
• 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)
Université Paris 13/Younès Bennani Traitement Informatique des Données 16
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 :
Université Paris 13/Younès Bennani Traitement Informatique des Données 17
MDC: Minimum-Distance ClassifierExemple
!
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)#?
Université Paris 13/Younès Bennani Traitement Informatique des Données 18
La frontière entre les classes :
gij(X ) = gi(X) ! gj(X) = 0
!
X = (1,"1)
x1=1
2
x1
x2
MDC: Minimum-Distance ClassifierExemple
!
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 19
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 20
Méthodes non paramétriquesk-Nearest Neighbour : KNNk-plus proches voisins : KPPV
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 21
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.
Université Paris 13/Younès Bennani Traitement Informatique des Données 22
Méthodes non paramétriquesk-Nearest Neighbour : KNNk-plus proches voisins : KPPV
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 23
Méthodes non paramétriquesk-Nearest Neighbour : KNNk-plus proches voisins : KPPV
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 24
Méthodes non paramétriquesk-Nearest Neighbour : KNNk-plus proches voisins : KPPV
Université Paris 13/Younès Bennani Traitement Informatique des Données 25
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 26
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]
Université Paris 13/Younès Bennani Traitement Informatique des Données 27
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)
Université Paris 13/Younès Bennani Traitement Informatique des Données 28
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 29
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.
Université Paris 13/Younès Bennani Traitement Informatique des Données 30
Recherche des KNNMéthode de projection : d-dimension
Comment trouver le meilleur axe de projection ?
Université Paris 13/Younès Bennani Traitement Informatique des Données 31
!Maximum coordinate
distance
2Euclidian
1Manhattan
npMetric
Recherche des KNNMéthode de projection : d-dimension
É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
Université Paris 13/Younès Bennani Traitement Informatique des Données 32
Recherche des KNNMéthode de projection : d-dimension
É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
Université Paris 13/Younès Bennani Traitement Informatique des Données 33
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.
Université Paris 13/Younès Bennani Traitement Informatique des Données 34
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.
Université Paris 13/Younès Bennani Traitement Informatique des Données 35
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 36
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
La fonction de décision est :
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
Université Paris 13/Younès Bennani Traitement Informatique des Données 37
Exercice (Corrigé)
gi(X ) = XtYi !
1
2YitYi , 1 " i " M
La frontière entre les classes :
gij(X ) = gi(X) ! gj(X) = 0
La fonction de décision est :
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
Recommended