Embed Size (px)
DESCRIPTION
Une architecture de systèmes de recommandation de combinaison d’items. Application au tourisme. Le 7 Décembre 2011. Romain Picot-Clémente. Laboratoire LE2I – UMR CNRS 5158 – Université de Bourgogne. INTRO DUCTION 1.0. Association loi 1901 Subventionnée par le Conseil Général - PowerPoint PPT Presentation
Citation preview
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
1
Laboratoire LE2I – UMR CNRS 5158 – Université de Bourgogne
Une architecture de systèmes de recommandation de combinaison d’items.
Application au tourisme.
Romain Picot-Clémente
Le 7 Décembre 2011
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
2INTRODUCTION 1.0
Côte-d’Or Tourisme
Missions
• Association loi 1901• Subventionnée par le Conseil Général• Président : Jean-Pierre REBOURGEON
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
3INTRODUCTION 1.0
Côte-d’Or Tourisme
Missions • Promouvoir le tourisme en Côte-d’Or• Conseiller, développer
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
4INTRODUCTION 2.0
Contexte Touristique
Problèmes
Objectifs industriels
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
5INTRODUCTION 2.0
Contexte Touristique
Problèmes
Objectifs industriels
• Pas de relation de conseil• Pertinence• Surcharge cognitive
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
6INTRODUCTION 2.0
Contexte Touristique
Problèmes
Objectifs industriels • Ensemble d’offres personnalisées• Savoir-faire --> conseil
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
7INTRODUCTION 3.0
Domaine de Recherche
Application Industrielle
• Résolution du problème de surcharge cognitive• Proposition de recommandations d’items
Systèmes de recommandation
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
8INTRODUCTION 3.0
Domaine de Recherche
Application Industrielle
Système de recommandation touristique
• Combinaison pertinente d’offres (items)• Prise en compte du savoir-faire de Côte d’Or Tourisme• Gestion de la mobilité
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
9PLAN
Etat de l’Art
Systèmes de recommandation
Couche SémantiqueCouche UtilisateurCouche Intelligence
Architecture
Définition du ProblèmeMétaheuristiques
Optimisation Combinatoire
OntologieRèglesMétaheuristique
Implémentation
Interfaces
Application Mobile
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
10ETAT DE L’ART 1.0
Basés sur le contenu
Basés sur le filtrage collaboratif
Systèmes de recommandation
• Modélisation des items / utilisateur• Comparaison
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
11ETAT DE L’ART 1.0
Basés sur le contenu
Basés sur le filtrage collaboratif
Systèmes de recommandation
• Choix des autres utilisateurs• Pas de modélisation items
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
12ETAT DE L’ART 2.0
Vecteurs de mots-clefs
Ontologie
Réseaux sémantiques
Méthodes basées sur le contenu
Utilisateur Document/item
comparaison
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
13ETAT DE L’ART 2.0
Vecteurs de mots-clefs
Ontologie
Réseaux sémantiques
Méthodes basées sur le contenu
• Mots-clefs + relations de cooccurrence• Comparaison utilisateur/items
Document textuel(Item)
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
ETAT DE L’ART 2.0
Vecteurs de mots-clefs
Ontologie
Réseaux sémantiques
Méthodes basées sur le contenu
• Pondérée --> comparaisons• Modélise utilisateur + Indexe items --> correspondances
14
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
ETAT DE L’ART 2.0
Vecteurs de mots-clefs
Ontologie
Réseaux sémantiques
Méthodes basées sur le contenu
• Pondérée --> comparaisons• Modélise utilisateur + Indexe items --> correspondances
4
23
1
2
5
4
2
1
6
74
114
21 4
14
23
1
2
5
4
2
1
6
74
114
21 4
1
Utilisateur Item
comparaison
15
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
ETAT DE L’ART 2.0
Vecteurs de mots-clefs
Ontologie
Réseaux sémantiques
Méthodes basées sur le contenu
• Pondérée --> comparaisons• Modélise utilisateur + Indexe items --> correspondances
Utilisateur
16
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
17ETAT DE L’ART 3.0
Intérêt ontologie
Savoir-faire
Type de recommandations
• Formelle, Rigoureuse• Expressivité• Moteur d’inférences• Standardisée (owl)• Outils nombreux
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
18ETAT DE L’ART 3.0
Intérêt ontologie
Savoir-faire
Type de recommandations
Liste d’items
VS
Combinaison
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
19ETAT DE L’ART 3.0
Intérêt ontologie
Savoir-faire
Type de recommandations
• Non considéré dans les SR actuels• Ontologie support
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
20
Trois couches
Couche intelligence
Couche sémantique
• Couche sémantique• Couche utilisateur• Couche intelligence
ARCHITECTURE 1.0
Couche utilisateur
Architecture générique
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
21
Trois couches
Couche intelligence
Couche sémantique• Domaine / items• Savoir-faire• Ontologie
ARCHITECTURE 1.0
Couche utilisateur
Architecture générique
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
22
Trois couches
Couche intelligence
Couche sémantique
• Liées au domaine• Propres à l’utilisateur
ARCHITECTURE 1.0
Couche utilisateur
Architecture générique
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
23
Trois couches
Couche intelligence
Couche sémantique
• Déduire intérêts utilisateur sur items• Rechercher combinaison
ARCHITECTURE 1.0
Couche utilisateur
Architecture générique
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
24ARCHITECTURE 2.0
Modèle de domaine
Modèle de buts
• Ontologie de domaine• Items indexés
Exemple
Couche sémantique
Exemple
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
25ARCHITECTURE 2.0
Modèle de domaine
Modèle de buts
Exemple
Couche sémantique
Exemple
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
26ARCHITECTURE 2.0
Modèle de domaine
Modèle de buts
Exemple
Couche sémantique
Exemple
• Savoir-faire• Ontologie de buts• Règles métiers
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
27ARCHITECTURE 2.0
Modèle de domaine
Modèle de buts
Exemple
Couche sémantique
Exemple
Règle métier
Pertinence des items dans ce but
)10,()(_),(_)( _ xpoidsxamisentretruextsparticipanplusieursxactivite amisentre
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
28ARCHITECTURE 3.0
Partie statique
Partie dynamique
Couche utilisateur
Nom
Age
Position géographique
Genre
…
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
29ARCHITECTURE 3.0
Partie statique
Partie dynamique
Couche utilisateur
Buts utilisateur
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
30ARCHITECTURE 4.0
Couche intelligence
Phase 1 : Projection/pondération • Intérêt utilisateur sur items• Partie dynamique --> poids
Intérêts utilisateurs
Matrice Buts-Items
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
31ARCHITECTURE 4.0
Couche intelligence
Phase 1 : Projection/pondération
Intérêts utilisateurs
5 items : {item1, item2, item3, item4, item5} 3 buts : {Sportif, Entre_amis, Nature}Règles métiers
Matrice Buts-Items
1061114
13814107
1525
BI
item1
item2
item3
item4
item5
Sportif Entre_amis Nature
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
32ARCHITECTURE 4.0
Couche intelligence
Phase 1 : Projection/pondération5 items : {item1, item2, item3, item4, item5} 3 buts : {Sportif, Entre_amis, Nature}Règles métiers
Poids d’intérêts utilisateur :
162211417
110
1061114
13814107
1525 item1
item2
item3
item4
item5
Partie dynamique (utilisateur) :
110
,_ NatureamisEntreSportifEntre_amisNature
1061114
13814107
1525
BI
item1
item2
item3
item4
item5
Sportif Entre_amis Nature
Intérêts utilisateurs
Matrice Buts-Items
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
33ARCHITECTURE 5.0
Couche intelligence
Phase 2 : Recherche combinatoire
Algorithme
• Pattern de combinaison• Fonction de comparaison• Algorithme de recherche
Pattern de combinaison
Fonction de pertinence
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
34ARCHITECTURE 5.0
Couche intelligence
Phase 2 : Recherche combinatoire
Algorithme
Pattern de combinaison
Fonction de pertinence
CampingMuseeActivite ,,
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
35ARCHITECTURE 5.0
Couche intelligence
Phase 2 : Recherche combinatoire
Algorithme
Pattern de combinaison
Fonction de pertinence• Comparer combinaisons• Corrélation entre items• Dépend application
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
36ARCHITECTURE 5.0
Couche intelligence
Phase 2 : Recherche combinatoire
Algorithme
Pattern de combinaison
Fonction de pertinence
• Explosion combinatoire• Méthode exacte trop lente• Métaheuristiques• Dépend application (temps, qualité, nbre résultats, …)
tHébergemen,RestaurantActivite,
2000 activités, 1000 restaurants, 1000 hôtels 2 milliards de combinaisons
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
37OPTIMISATION COMBINATOIRE 1.0
Problème touristique
Définitions
• Meilleurs items• Pattern touristique• Proximité
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
38OPTIMISATION COMBINATOIRE 1.0
Problème touristique
Définitions
• Items
• Pattern
• Combinaison
Définitions
avec un poids yixitypeinomii .,.,.,. iw
ntypetypetypepat ,...,, 21
niiincombinaiso ,...,, 21
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
39OPTIMISATION COMBINATOIRE 2.0
Dispersion combinaison
Dispersion modérée
• Quantifie éloignement• Ecart-type coordonnées
N
n
N
jjn
N
jjnk yi
Nyixi
Nxi
NC
1
2
1
2
1
.1..1.1)(
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
40OPTIMISATION COMBINATOIRE 2.0
Dispersion combinaison
Dispersion modérée• Eloignement subjectif• Tolérance de dispersion• Minimiser
Tolerance
CC kk
)()(mod
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
41OPTIMISATION COMBINATOIRE 3.0
Sous-combinaison
Exemple
• Pattern• Dispersion modérée
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
42OPTIMISATION COMBINATOIRE 3.0
Sous-combinaison
Exemple
Hôtel,Restaurant Parc,Cpat
Hôtel ,RestaurantCsubpat
5.0Ctolerance
1.0Csubtolerance
C
Csub
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
43OPTIMISATION COMBINATOIRE 4.0
Poids de combinaison
Pertinence de combinaison
N
wW
N
j iC
j
k
0
• Moyenne poids items• Maximiser
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
44OPTIMISATION COMBINATOIRE 4.0
Poids de combinaison
Pertinence de combinaison • Agrégation poids, dispersions modérées• Maximiser
1
0 ,modmod )()()( S
l lCk
Ck
k
k subCemPoidsMaxItWC
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
45OPTIMISATION COMBINATOIRE 5.0
Problème de sac à dos
Différences
Positionnement
Problème de sac à dos multidimensionnel à choix multiple
• Capacité max• Maximiser valeur totale
Items
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
46OPTIMISATION COMBINATOIRE 5.0
Problème de sac à dos
Différences
Positionnement
Problème de sac à dos multidimensionnel à choix multiple
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
47OPTIMISATION COMBINATOIRE 5.0
Problème de sac à dos
Différences
Positionnement
Problème de sac à dos multidimensionnel à choix multiple
• Plusieurs items d’un même type• Ordonnancement important
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
48OPTIMISATION COMBINATOIRE 6.0
Principe
Inconvénient
Métaheuristique
Avantage
• Parcours non linéaire espace• Caractère semi-aléatoire
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
49OPTIMISATION COMBINATOIRE 6.0
Principe
Inconvénient
Métaheuristique
Avantage• Flexibilité• Rapidité• Accessibilité
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
50OPTIMISATION COMBINATOIRE 6.0
Principe
Inconvénient
Métaheuristique
Avantage
• Optimum pas assuré
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
51OPTIMISATION COMBINATOIRE 7.0
Méthodes basées sur une population
Méthodes à état simple
Classes de métaheuristique
• Algo génétique, Colonie de fourmis, …• Echantillon de solutions• Couteux en temps
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
52OPTIMISATION COMBINATOIRE 7.0
Méthodes basées sur une population
Méthodes à état simple • Passage d’une solution à une autre itérativement• Plus rapide
Classes de métaheuristique
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
53OPTIMISATION COMBINATOIRE 8.0
Méthodes gloutonnes
Méthodes à état simple
Hill-Climbing
Recherche locale itérée
Méthode Tabou
Recuit simulé
• Méthode aveugle• Très rapide
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
54OPTIMISATION COMBINATOIRE 8.0
Méthodes gloutonnes
Méthodes à état simple
Hill-Climbing
Recherche locale itérée
Méthode Tabou
Recuit simulé
• Rapide• Minima locaux
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
55OPTIMISATION COMBINATOIRE 8.0
Méthodes gloutonnes
Méthodes à état simple
Hill-Climbing
Recherche locale itérée
Méthode Tabou
Recuit simulé
• Hill-Climbing itéré• Meilleure solution que Hill-Climbing• Possiblement long
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
56OPTIMISATION COMBINATOIRE 8.0
Méthodes gloutonnes
Méthodes à état simple
Hill-Climbing
Recherche locale itérée
Méthode Tabou
Recuit simulé
• Itère : recherche optimum dans le voisinage d’une solution• Liste Tabou des optima• Enfermement dans un même voisinage
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
57OPTIMISATION COMBINATOIRE 8.0
Méthodes gloutonnes
Méthodes à état simple
Hill-Climbing
Recherche locale itérée
Méthode Tabou
Recuit simulé• Sort des optima locaux• Rapide• Paramètres nombreux
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
58IMPLEMENTATION 1.0
Avant
Après
Intégration système
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
59IMPLEMENTATION 1.0
Avant
Après
Intégration système
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
60IMPLEMENTATION 2.0
Ontologie de domaine
Modèle de buts
Couche sémantique• Vues sur BDD• Table descriptive• Traduction --> Ontologie• Peuplement• Enrichissement
BDD
Tables
Vues + table descriptive
Programme de traduction
Ontologie
Expert du tourisme
Aperçu
Aperçu
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
61IMPLEMENTATION 2.0
Ontologie de domaine
Modèle de buts
Couche sémantique
Aperçu
Hôtel_possède_restaurant
Aperçu
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
62IMPLEMENTATION 2.0
Ontologie de domaine
Modèle de buts
Couche sémantique
Aperçu
• Identifier buts pour séjour• Ajouter dans ontologie de buts• Définir règlesAperçu
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
63IMPLEMENTATION 2.0
Ontologie de domaine
Modèle de buts
Couche sémantique
Aperçu
Aperçu
Entre amis En amoureux Nature Sportif FamilleVignoble Culturel Bien être
But
Root
)2,()(),()(Restaurant xpoidsxNatureTerrassexpossedex Nature
)20,()()( xpoidsxNaturex_piedRandonne_a Nature
)10,()(_),()( _ xpoidsxetreBienSpaxpossedexHôtel etreBien
)20,()(_)(__ _ xpoidsxamoureuxEnxjardinetParc amoureuxEn
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
64IMPLEMENTATION 3.0
Partie dynamique
Couche utilisateur
Partie statique
Entre amis
En amoureux Nature Sportif FamilleVignoble Culturel Bien être
But
Root
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
65IMPLEMENTATION 3.0
Partie dynamique
Couche utilisateur
Partie statique
• Position géographique • Tolérance de dispersion• Nombre de jours• Type d’hébergement• Date
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
66IMPLEMENTATION 4.0
Pattern
Couche intelligence
Tolérance
Type hébergement
54321 Restaurant ,Activite ,Activite ,Restaurant ,ActiviteCpattern
Nombre de jours
Geolocalisation
• Construction dynamique• De base :
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
67IMPLEMENTATION 4.0
Couche intelligence
• Aucun
• Général
• Spécifique
• Plusieurs types
Pattern
Tolérance
Type hébergement
Nombre de jours
Geolocalisation
54321 Restaurant ,Activite ,Activite ,Restaurant ,ActiviteCpattern
654321 tHébergemen,Restaurant ,Activite ,Activite ,Restaurant ,ActiviteCpattern
654321 Hôtel,Restaurant ,Activite ,Activite ,Restaurant ,ActiviteCpattern
654321 CampingHôtel,Restaurant ,Activite ,Activite ,Restaurant ,Activite Cpattern
65 tHebergemen,RestaurantCsubpattern
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
68IMPLEMENTATION 4.0
Couche intelligence
Pattern
Tolérance
Type hébergement
Nombre de jours
Geolocalisation
,Restaurant ,Activite ,Activite ,Restaurant ,Activite 54321Cpattern
1151, tHebergemen,RestaurantCsubpattern
11109876 tHebergemen,Restaurant ,Activite ,Activite ,Restaurant ,Activite
2 jours :
11102, tHebergemen,RestaurantCsubpattern
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
69IMPLEMENTATION 4.0
Couche intelligence
Pattern
Tolérance
Type hébergement
Nombre de jours
Géolocalisation
geoloc,Restaurant ,Activite ,Activite ,Restaurant ,Activite 54321Cpattern
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
70IMPLEMENTATION 4.0
Couche intelligence
Pattern
Tolérance
Type hébergement
Nombre de jours
Geolocalisation
654321 tHébergemen,Restaurant ,Activite ,Activite ,Restaurant ,ActiviteCpattern
65 tHebergemen,RestaurantCsubpattern
)( Cpatterntolerance
10010)(
Csubpatterntolerance
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
71IMPLEMENTATION 5.0
Initialisation
Couche intelligence: Recuit simulé
Benchmarks
)(1
0Cpertinenceenergie
• Température élevée • Combinaison aléatoire
• Energie :
0T
0C
Algorithme
Variation d’énergie
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
72IMPLEMENTATION 5.0
Initialisation
Couche intelligence: Recuit simulé
Algorithme• Décroissance par palier de température• 2000 modifications élémentaires à chaque palier• Taux d’acceptation mauvaise solution selon température
Benchmarks
Variation d’énergie
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
73IMPLEMENTATION 5.0
Initialisation
Couche intelligence: Recuit simulé
Algorithme
Benchmarks
Variation d’énergie
T0 T1 T2 T3 …
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
74IMPLEMENTATION 5.0
Initialisation
Couche intelligence: Recuit simulé
Algorithme
Variation d’énergie
Benchmarks
Jeux de données aléatoires Jeux de données réellesEnergie moyenne Temps moyen (ms) Energie moyenne Temps moyen (ms)
Recuit simulé 64.13 404 65.29 211Hill-Climbing 106.16 7 93.24 6
Meilleure énergie trouvée
62.70 65.25
• Jeu de données aléatoires : 30000 items• Jeu de données réelles : 4096 items• Energie : Recuit simulé >> Hill-Climbing• Temps : Hill-Climbing > Recuit simulé• Temps < 500 ms (quasi-temps réel)
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
75INTERFACE 1.0
Buts utilisateur
Proposition
Données statiques
Application mobile
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
76
Buts utilisateur
Proposition
Données statiques
Application mobile
INTERFACE 1.0
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
77
Buts utilisateur
Proposition
Données statiques
Application mobile
INTERFACE 1.0
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
78CONCLUSION 1.0
Apports
Perspectives
• Architecture de SR de combinaisons d’items + savoir-faire
• Problème d’optimisation combinatoire touristique
• Implémentation architecture dans le tourisme
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
79
Apports
Perspectives
• Evolution vers un système hybride• Propagation poids dans ontologie• Ontologie support d’inférence• Implémentation dans différents domaines
CONCLUSION 1.0
Rom
ain
Pico
t-Clé
men
te –
rom
ain.
pico
t-cle
men
te@
chec
ksem
.fr -
Equ
ipe
de p
roje
t Che
ckse
m –
Labo
rato
ire E
lect
roni
que
Info
rmati
que
et Im
age
(LE2
I – U
MR
CNRS
515
8) I
UT D
ijon-
Auxe
rre
– Un
iver
sité
de B
ourg
ogne
, BP
4787
0, 2
1078
Dijo
n Ce
dex,
Fra
nce
80
Romain [email protected]
