36
14/06/22 14/06/22 BELKHIR ABDELKADER BELKHIR ABDELKADER Similarité Similarité Belkhir Abdelkader Laboratoire LSI USTHB [email protected]

02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB [email protected]

Embed Size (px)

Citation preview

Page 1: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23 BELKHIR ABDELKADERBELKHIR ABDELKADER

SimilaritéSimilarité

Belkhir AbdelkaderLaboratoire LSI [email protected]

Page 2: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23 BELKHIR ABDELKADERBELKHIR ABDELKADER

ProblématiqueProblématique• Input: Ensemble d’objets

• Tâche: traitement

Requête: Nouveau objetTâche: trouver l’objet (le plus) similaire parmi l’ensemble des objets

Le plus similaire

Page 3: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23 BELKHIR ABDELKADERBELKHIR ABDELKADER

1 SimilaritySearch in Web

2 SimilaritySearch in Theory

3 Revisingthe Problem

4 NewAlgorithms

Page 4: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23 BELKHIR ABDELKADERBELKHIR ABDELKADER

Une mesure de similarité, notée s, s: NxN R • x, y N : s(x,y) ≥ 0• x, y N : s(x,x) = s(y,y) ≥ s(x,y)• x, y N : s(x,y) = s(y,x)

Mesure de similarité

Soit N un ensemble d’objets (individus, documents, sites web, …)

Page 5: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23 BELKHIR ABDELKADERBELKHIR ABDELKADER

• Une mesure de dissimilarité, notée d, d: NxN R. • x, y N : d(x,y) ≥ 0• x, y N : d(x,x) = 0• x, y N : d(x,y) = d(y,x)

Mesure de dissimilarité

Page 6: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23 BELKHIR ABDELKADERBELKHIR ABDELKADER

similarité s dissimilarité d similarité s dissimilarité d

x, y N : d(x,y) = smax - s(y,x)

smax est la valeur de similarité maximale atteinte par les éléments de NxN.

Page 7: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Profil?Profil?

Profil = {X1, X2, …, Xn} Xi: variable (characteristique)

Page 8: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Profil : valeur binaireProfil : valeur binaire

système binaire:

1: characteristique est présente

0: sinon

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

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

Page 9: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Profil : valeur binaireProfil : valeur binaire

(X1 , X2 , … , Xm) : X

(Y1 , Y2 , … , Ym) : Y

X est-il similaire à Y?

Page 10: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Profile : similaritéProfile : similarité

profil {caracteristiques}

Graphe bi-parti

Page 11: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Graphe bi-parti Graphe bi-parti G(N G(N M, E) M, E)

Page 12: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Graphe bi-partiGraphe bi-parti

Page 13: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Graphe bi-parti Graphe bi-parti

Page 14: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Measure de SimilaritéMeasure de Similarité

s: NxN → R.

x, y N : s(x,y) ≥ 0 x, y N : s(x,x) = s(y,y) ≥ s(x,y)

x, y N : s(x,y) = s(y,x)

(X1 , X2 , … , Xm) : X

(Y1 , Y2 , … , Ym) : Y

X est-il similaire à Y? proportionelle aux arcs communs

Page 15: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

measure dissimilaritémeasure dissimilarité

d: NxN → R.

x, y N : d(x,y) ≥ 0 x, y N : d(x,x) = 0

x, y N : d(x,y) = d(y,x)

Page 16: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Similarité vers DissimilaritéSimilarité vers Dissimilarité

x, y N : d(x,y) = smax - s(y,x)

Page 17: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

measure similaritémeasure similarité

Page 18: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

measure similarité/dissimilaritémeasure similarité/dissimilarité

x, y N : s(x,y) = (1) x, y N : d( x, y) = smax - s( y, x) smax is equal to 1. d is equal to :

x, y N : d( x, y) = 1 -(2*a + b + c)/2*(a + b + c)

= (2)

Il est facile de vérifier que d( x, y) = 0 x = y

Page 19: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

la mesure de Jaccard

as’ = (a + b + c)

mesure la métaphore. aucune caractéristique commune d’où a = 0.

Dans ce cas, s’=0 ; rejet.

s’il y a concordance totale (a ≠ 0 et b=c=0).

Dans ce cas, s’= a/a = 1 ; acceptation absolue.

Page 20: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

métaphoremétaphorecolor = RGB(r,g,b) ;

Dans notre cas, le troisième paramètre est ignoré.

Le rejet de la négociation rouge ; la mesure s’ = 0. La couleur est obtenue par RGB(255,0,0).

L’acceptation absolue vert ; la mesure s’ = 1. La couleur est obtenue par RGB(0,255,0).

Page 21: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

métaphoremétaphore

Le cas intermédiaire correspond à la valeur k de s’  (0≤k≤1) 

la couleur la formule suivante : RGB((1-k)*255, k*255, 0).

Page 22: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Mesure de similaritéMesure de similarité

valeur binaire : abstraction de haut niveau

Perte d’information!

cpu use : 10u ≠ 55u

Page 23: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

Graphe bi-parti valué

nouvelle mesure de similarité!

Page 24: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

Mesure de similarité valuéeMesure de similarité valuée

11/04/2311/04/23

Page 25: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Page 26: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

Page 27: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

Critiques:

• Représentation du profil par une structure plate (vecteur)

• Profil totalement défini

Vers une nouvelle mesure…..

11/04/2311/04/23

Page 28: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

1,0: RRsima

elseyx

yx

yxif

yxif

yxsima

ii

ii

ii

ii

ii

,max

,min

000

1

,

Page 29: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

cba

yxsimayxS

ni

iii

b

1

,,

Page 30: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

Quantitative similarityQuantitative similarity

11/04/2311/04/23

ai

i

bi

i

ci

iibaiai

ni

iiii

bw

wcwbwa

yxsimawayxS

1 1 1

1

,,

Page 31: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

Distance= 1-SimDistance= 1-Simmaxmax

11/04/2311/04/23

1,0: PPwdistb

yxdistbw ,

bi

i

ci

ibaiai

ai

ii

ni

iiii

wcwbwa

yxsimaw

1 11

1

),(*1

-

Page 32: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

11/04/2311/04/23

ci

ibai

bi

iai

ai

ii

ni

iiii

ci

ibai

bi

iai

ai

ii

bw

wcwbwa

yxsimawwcwbwayxdist

111

1111

,,

Page 33: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

PropertiesProperties

11/04/2311/04/23

neighborhood of the profile

nxxxx ,...,, 21

nn xxxxxxy ,...,, 2211

nn xxxxxxz ,...,, 2211

ci

ibai

bi

iai

ai

ii

ni

i ii

ii

ci

ibai

bi

iai

ai

ii

bw

wcwbwa

xx

xwwcwbwa

yxdist

111

1111,

ci

ibai

bi

iai

ai

ii

ni

i i

iii

ci

ibai

bi

iai

ai

ii

bw

wcwbwa

x

xxwwcwbwa

zxdist

111

1111,

Page 34: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

PropertiesProperties

11/04/2311/04/23

pK

i

p

iiip yxWyxd

1

1

,

zxdyxd pp ,,

Page 35: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

PropertiesProperties

11/04/2311/04/23

Partially defined profile

elseyx

yx

yxyxsi

yxif

yxsima

ii

ii

iiii

ii

ii

,max

,min

000

1

,

Page 36: 02/04/2015BELKHIR ABDELKADER Similarité Belkhir Abdelkader Laboratoire LSI USTHB belkhir@lsi-usthb.dz

Conclusion

Applications multiples pour la gestion des profils…..

Ahmed Belkhirat, Abdelkader Belkhir, A New Similarity Measure for the Profiles Management, UKSIM '11: Proceedings of the Tenth International Conference on Computer Modeling and Simulation, Cambridge England, 2011.

Belkhirat Ahmed, Bouras Abdelghani, Belkhir Abdelkader , A new similarity measure for the anomaly intrusion detection , NSS '09: Proceedings of the 2009 Third International Conference on Network and System Security, October, 2009 , Gold Coast, Australia

11/04/2311/04/23