Apprentissage non supervisé

M.-J. Huguet

https://homepages.laas.fr/huguet

2017-2018

Plan

1. Contexte : l’Intelligence Artificielle

2. Contexte : l’apprentissage

3. Clustering

4. Méthodes hiérarchiques

5. Méthodes par partitionnement

2

Références (1) Intelligence Artificielle, S. Russel, P. Norvig, Pearson Education, 2010 Intelligence Artificielle, Livre Blanc INRIA, 2016

L’IA, mythes ou réalités, Intersectices 2015 o https://interstices.info/jcms/p_84122/l-intelligence-artificielle-mythes-et-realites

Apprentissage Artificiel, A. Cornuejols, L. Miclet, Eyrolles, 2003

Cours (accessibles sur le web): Histoire de l’IA, Frédéric Fürst, Univ Picardie, 2015 (?)

Apprentissage, Jean-Daniel Zucker, UPMC, 2010-2011

Clustering, Gilles Gasso et Ph. Leray, INSA Rouen

Data Mining, Jamal Atif, Paris Dauphine, 2015-2016

Apprentissage non supervisé, Nicolas Baskiotis, Paris6, 2016-2017

Apprentissage, Chloe-Agathe Azencott, Centrale SupElec, 2016-2017

3

Références (2) Cours du collège de France http://www.college-de-france.fr

Enseignement Mathématiques et Sciences Numériques Gérard Berry : Algorithmes, machines et langages

Enseignement Chaires annuelles Informatique et Sciences Numériques 2017-2018 : Claire Mathieu – Algorithmes

2015-2016 : Yann LeCun : L’apprentissage profond

2011-2012 : Serge Abiteboul : Sciences des données : de la logique du premier ordore à la toile

Enseignement Chaires annuelles Innovations Technologiques 2011-2012 : Jean-Paul Laumond : La Robotique

4

Références (3) Associations scientifiques : Association Française d’IA : http://afia.asso.fr/ Groupe de Recherche IA (CNRS) : http://www.gdria.fr/

Site (Informatique) : https://interstices.info/

5

Section 1. Contexte : l’Intelligence Artificielle

6

Le buzz (1) Apprentissage : Sujet en vogue dans les médias et la presse scientifique Nombreuses réalisations depuis 20 ans avec une forte accélération :

1997 : Deep Blue (IBM) : un système informatique bat le champion du monde d’échecs

2005 : Challenge DARPA : un robot se déplace de façon autonome en env. inconnu

2007 : Challenge DARPA : un robot se déplace de façon autonome en env. urbain

2011 : Watson (IM) : bat des champions du monde au Jeu Jeopardy!

2012 : Succès de l’apprentissage profond en reconnaissance d’images (Imagenet)

o Large ScaleVisualization Challenge

2014 : Google : description automatique d’images

2015 : Facebook : reconnaissance faciale

2015/2016 : AlphaGo (Google) : bat le champion du monde de Go

2016 : Daddy’s Car (composition style Beatles), Sony CSL

7

Le buzz (2) Mais aussi : Jeux vidéo : piloter des personnages (virtuels) dans des mondes virtuels

Compagnons (smartphones et tablettes) : reconnaissance de la parole

Traduction instantanée (Skype translator, assistants, …)

Véhicules sans chauffeur

Moteurs de recherche : Google Knowledge Graph / Graph Search

Développement d’outils en open source pour l’apprentissage Généraux : Scikitlearn, R, (Matlab, ….)

Deep Learning : TensorFlow, Theano, Caffe, …

8

Le buzz (3) Débats

Robots guerriers

Transhumanisme

Emploi

Trading haute fréquence

Fouille de données et respect de la vie privée

Crainte du pouvoir « donné » aux machines : Éthique des recherches et des algorithmes, explicabilité, autonomie partagée

Intelligence Artificielle ≠ Apprentissage automatique, c’est aussi : Vision, parole

Ingénierie des connaissances, web sémantique

Robotique, véhicules autonomes

Traitement du langage naturel

Raisonnement et aide à la décision

Logiques9

Bref aperçu de l’IA (1) 1956 : Naissance « officielle » de l’IA

Conférence de Dartmouth (initiateurs : )

Précurseurs (années 1950 …) :

o A. Turing : une machine peut-elle penser ? (Test de Turing)

o H. Simon & A. Newel : démonstration automatique de théorèmes (LogicTheorist)

o W. Mc Culloch & W. Pitts : réseaux de neurones artificiels

o W. Weaver : règles linguistiques, traduction automatique

Rêve de l’IA : Construire des machines pouvant égaler l’Homme10

Bref aperçu de l’IA (2) 1956 – 1974 : l'Age d’or

Deux approches : connexionnisme / cognitivisme

o Connexionnisme : Modélisation impossible du comportement du cerveau : reproduire le cerveau par une machine

o Cognitivisme : Modélisation de la pensée et du raisonnement (manipulation de symbôles)

1957 : Perceptron (F. Rosenblatt) : réseau de neurones artificiels à 1 seule couche

1957 : GPS General Problem Solver (H. Simon & A. Newel)

o Problème = Etat Courant, But, Opérateurs

o Systèmes de production = ensemble de règles d’inférence

o Résolution : appliquer ces règles (ch. arrière / induction)

1958 : LISP (J. Mc Carthy) : LISt Processing, langage de référence de l’IA

o Représentation du programme et des données par des listes

Année 60 : Grammaires de N. Chomsky, Réseaux Sémantiques (R. Quillian)11

Bref aperçu de l’IA (3) 1956 – 1974 : l'Age d’or Problèmes de jeux, Démonstration, Heuristiques, Logique, Planification

d’actions, Traitement du langage naturel, Vision, …

Deux familles : Logique : modèles mathématiques

Sciences cognitives et sciences humaines

Des prédictions (1958); dans 10 ans : o un ordinateur sera champion du monde d’échecs

• 1997 : Deep Blue

o un ordinateur écrira de la musique qui sera considérée comme esthétique

• 2016 : Daddy’s Car (style des Beatles), ….

o un ordinateur découvrira un théorème fondamental des mathématiques

o les théories psychologiques auront la forme de programmes12

Bref aperçu de l’IA (4) 1974 – 1980 : Premier hiver de l’IA Crise scientifique, morale et financière

Limite en puissance de calcul, Limite NP-Complétude

Besoin de grandes masses de données pour produire des connaissances

Paradoxe :

o certains problèmes difficiles pour l’Homme peuvent être résolus (ex : démonstration) mais des problèmes faciles pour l’Homme (reconnaître un visage), pas de résultats probant

Est-il pertinent de doter les machines d’intelligence ?

L’intelligence peut-elle se ramener à des modèles symboliques ?

Développement de nouveaux modèles et méthodes :

o Extension des logiques : Multi-valuées, Floues, Modales, Temporelles, …

o Langage Prolog (clauses de Horn),

13

Bref aperçu de l’IA (5) 1980-1987 : le retour des financements … Boom des systèmes experts et de l’ingénierie des connaissances (E. Feigenbaum)

Application à des domaines spécifiques (demande des entreprises) Pour limiter l’explosion combinatoire des systèmes de production :

Premiers systèmes experts : DENDRAL (Chimie), MYCIN (Médical)

Nouveaux modèles d’acquisition et de représentation des connaissanceso Frames, Graphes conceptuels, Logique de description

Raisonnement et Décision : Programmation par contraintes, Raisonnement à base de cas,

Apprentissage symbolique Permettre aux programmes de s’améliorer

Liens avec la biologique Algorithmes génétiques, Insectes sociaux, Systèmes Multi-Agents

Réseaux de neurones : rétro-propagation du gradient (J. Hopfield)

o Applications à la reconnaissance de caractères ou reconnaissance vocale14

Bref aperçu de l’IA (6) 1987 – 1993 (1995 ? 1997 ?) : Second hiver de l’IA

Recentrage vers la robotique (« les éléphants ne jouent pas aux échecs »)

o Le corps (capacités sensorielles, mouvement) est essentiel pour produire de la connaissance et du raisonnement

Spécialisation/Fragmentation de l’IA en nombreux sous-domaines

J. Pearl : liens entre des problèmes d’IA et des problèmes traités dans d’autres domaines (mathématique, économie, recherche opérationnelle) : probabilité, théorie de la décision, optimisation, modèles de Markov, réseaux bayésiens, …

Nombreuses réalisations dans des applications spécifiques :

o Robotique industrielle, reconnaissance vocale, diagnostic, reconnaissance des formes, recherche d’information, …

Quand un problème est résolu, ce n’est plus un problème d’IA …

Ne plus dire qu’on est spécialiste en IA … 15

Bref aperçu de l’IA (7) Fin années 1990 : Retour en force de l’IA Années 1990 :

développement des ordinateurs personnels et du Web

o Rendre les moteurs de recherche plus intelligent

o Début du Web sémantique : des données aux connaissances

• Ontologies

Données massives, Apprentissage Automatique Apport intelligence computationnelle et puissance de calcul

On ne cherche plus une machine capable de tout résoudre : Focus sur des problèmes spécifiques

Pionniers en France : Jacques Pitrat (Doct. 1966) et Jean-Louis Laurière (1976 – ALICE) - Paris 6

Alain Colmerauer (Doct. 1967, - Prolog1 1974, Prolog4 1996) - Marseille16

Section 2. Contexte : l’apprentissage artificiel

17

Apprentissage Automatique/Artificiel (1) Qu’est-ce que l’apprentissage pour une « machine » ? Simon (1983) : changements dans un système lui permettant d’améliorer ses

performances sur une tâche déjà vue ou similaire.

Tâches ? Applications ? Classification, Organisation de connaissance

Résolution de problèmes, Planification et Actions

18Images JD. Zucker, UPMC - 2011

Apprentissage Automatique/Artificiel (2) Qu’est-ce que l’apprentissage pour une « machine » ? Simon (1983) : changements dans un système lui permettant d’améliorer ses

performances sur une tâche déjà vue ou similaire.

Changements ? Acquérir de nouvelles connaissances

o Acquérir de nouveaux faits / de nouvelles capacités

Réviser ses connaissances (son comportement)

o Résoudre mieux / plus efficacement les problèmes

Performances ? Taux de classification, cohérence, qualité des solutions, …

Optimiser une fonction objectif

19

Apprentissage Automatique/Artificiel (3) Différents types d’apprentissage

20 Images JD. Zucker, UPMC - 2011

Apprentissage Automatique/Artificiel (4) Raisonnement par induction Proposer des lois générales à partir de l’observation de cas particuliers

Exemple : déterminer le nombre a pour prolonger la séquence 1 2 3 5 a

Deux familles de modèles : Apprentissage Symbolique

Apprentissage Numérique

21

Apprentissage Automatique/Artificiel (5) Des observations / échantillons / exemples :

Des étiquettes / labels :

Apprendre une fonction / modèle : Pour prédire à partir de

Processus : Récupération d’échantillons bruts

Sélection de caractéristiques / features

Choix modèle / méthode d’apprentissage

Entrainement (déterminer les paramètres de ) Evaluation

22

Echantillon xFonction

fLabel y(décision)

Classification (y = classe)Régression (y = réel)

Concept (y = booléan)

Apprentissage Automatique/Artificiel (6) Échantillons et labels sont donnés Apprentissage supervisé Entrainement sur une base d’échantillons dite « de test » Evaluation sur une autre base d’échantillons

Obtention des étiquettes Couteux à obtenir sur des grands volumes de données Données sans étiquettes plus faciles à obtenir mais souvent plus compliqué à

exploiter

Échantillons sans étiquette Apprentissage non supervisé

23

Apprentissage non supervisé (1) Meilleure compréhension des données Rechercher une structure

En pré-traitement pour apprentissage non supervisé (ou pas)

Différentes problématiques Réduction de dimensions Clustering (classification, segmentation) Construire des classes à partir des exemples

Souvent Apprentissage non supervisé = Clustering

24

Apprentissage non supervisé (2) Objectif Partitionner les exemples/observations/données en clusters/classes Homogènes : les éléments d’un même cluster sont similaires

Séparés : les éléments de différents clusters sont différents

Le résultat dépend beaucoup de la modélisation du problème et de la distance …

25Images JD. Zucker, UPMC - 2011

Applications (1) Fouille de Données (Data Mining) De la donnée à l’information Collecter et Nettoyer les données

Stocker les données

Distribuer les données

Exploiter les données : extraire de l’information Prévisions / Prise de décision

Exemples : Analyse de profils de clients,

Analyse de documents, …

Voir conf en début de semestre

26

Mots clés : Informatique décisionnelle / Business Intelligence

Images JD. Zucker, UPMC - 2011

Section 3. Clustering

27

Position du problème Définition Un ensemble de exemples / observations Une observation : attributs

Déterminer clusters tel que Chaque cluster regroupe des observations similaires

Fort impact de la définition de similarité … Dépend du domaine d’application

28

Intérêts du clustering Comprendre les données (analyse exploratoire)

Identifier utilisateurs avec des profils similaires

Identifier des communautés dans des réseaux sociaux,

…

Visualiser les données Complémentaire avec la réduction de dimension (ACP)

Limiter la visualisation à un « représentant » du cluster

Inférer des connaissances Exemple : Annotation d’échantillons

Identifier des images représentant le même objet

Identifier les points appartenant au même élément d’une image

Identifier des textes traitant d’un même sujet

Label sur le représentant label sur tous les éléments du cluster

29

Exemples de clustering Quelques applications

30

Caractérisation du clustering (1) Cluster = un regroupement de données Regrouper des échantillons proches Eloigner des échantillons différents

Qu’est-ce qu’un bon clustering ? Problème mal posé …. L’objectif dépend du problème considéré

31Images N. Baskiotis, LIP6 - 2017

Caractérisation du clustering (2) Clustering

Définir une distance, une similarité

Distance intra-cluster/classe (minimiser)

Distance inter-cluster/classe (maximiser)

Distance entre deux points : ,

Plus la distance est élevée moins les points sont similaires

Similarité : ,,

32

Caractérisation du clustering (3) Clustering Déterminer une partition ∶ → ,… telle que

⋃ , et ⋂ ∅ pour chaque cluster/classe , ∀ , ∈ et ∉ : on veut vérifier

, , et , ,

Trouver la partition ∗: où dépend de la fonction de similarité utilisée

Combien de partitions possibles en fonction de la taille de et du nombre de classes ?

33

Nombre de partitions Nombre de Bell Nombre de partitions différentes d’un ensemble de éléments Equations de récurrences :

, 1, 1 1,

34

k1 2 3 4 5 6 6 8 9 10 Nb Bell

n

1 1 12 1 1 23 1 3 1 54 1 7 6 1 155 1 15 25 10 1 526 1 31 90 65 15 1 2037 1 63 301 350 140 21 1 8778 1 127 966 1701 1050 266 27 1 41399 1 255 3025 7770 6951 2646 428 35 1 2111210 1 511 9330 34105 42525 22827 5214 708 44 1 115266

Caractérisation du clustering (4) Trouver la partition ∗: où dépend de la fonction de

similarité utilisée

Deux difficultés : Mesure de similarité / distance

Valeur de Méthodes paramétriques : la valeur est fixée

Méthodes non paramétriques : la valeur n’est pas fixée

35

Nombre de cluster Nombre de clusters

36

Données

K=2 K=4

K=6

Distances (1) Distance : une fonction ∶ → vérifiant :

Symétrie : , ,

Séparation : , 0 ⟺

Inégalité triangulaire : , , , ,

Distance de Minkowski ou Norme

Si 2, distance euclidienne

Si 1, distance de Manhattan

37

Image: Wikipedia

Distances (2) Distance de Hamming Mesurer différence entre deux séquences de symboles Traitement du signal

Soit et deux observations de dimension

Hamming : , ∶

Exemple Entre 1011101 et 1001001 distance de Hamming = 2

Entre 2143896 et 2233796 distance de Hamming = 3

Entre ramer et cases distance de Hamming = 3

38

Distances (3) Distance de Levenshtein (distance d’édition)

Mesurer la différence entre deux chaines de caractères Nombre d’opérations élémentaires (insérer/supprimer/remplacer) pour passer d’une

chaine source à une chaine destination

o Passer de "a " vers "ab" : distance = 1 (insérer ‘b’)

Autres : compter des n-grammes Sous séquences de longueur présentes dans une séquence

Comparer des séquences à partir des n-grammes communs

39

Evaluation d’un clustering (1) Centroïde/Barycentre d’un cluster (avec | |):

∑ ∈

Homogénéité Qualité intra cluster pour un cluster : moyenne des distances entre chaque point et le centre :

Tightness : ∑ ,∈

Un cluster homogène a une valeur faible

sur l’ensemble des clusters : moyenne des : ∑

40

Evaluation d’un clustering (2) Séparation Qualité inter cluster : distance entre deux clusters Saut minimal (single linkage) : 2 clusters sont proches si 2 de leurs

points sont proches Distance minimale entre 2 points appartenant à des clusters différents

, ∈ , ∈ ,

Saut maximal (complete linkage) : 2 clusters sont proches si tous leurs points sont proches Distance maximale entre 2 points appartenant à des clusters différents

, ∈ , ∈ ,

41Images J. Atif, Paris Dauphine- 2016

Evaluation d’un clustering (3) Séparation Saut moyen (average linkage) Distance moyenne entre toutes les paires de points

, ∑ ∑ ,∈∈

Distance entre les barycentres

, , ∑ ∈ , ∑ ∈ )

Sur les clusters : moyenne distance deux à deux

∑ ∑ ,

Avoir une valeur élevée42Images J. Atif, Paris Dauphine- 2016

Evaluation d’un clustering (4) Combinaison des deux critères (homogénéité et séparation) Indice de Davies Bouldin pour un cluster :

Combiner les valeurs des tightness (intra) et distances entre les barycentres (inter):

,

Valeur faible si les clusters sont homogènes (numérateur petit) et s’ils sont bien séparés (dénominateur grand)

pour tous les clusters : ∑

Aide pour déterminer le nombre de clusters (minimiser )

43

Evaluation d’un clustering (5) Silhouette : autre évaluation pour homogénéité et séparation

Pour chaque point : est-ce qu’il appartient au « bon » cluster : Est-il proche des points du cluster auquel il appartient ?

o distance moyenne aux autres points du même cluster

o ∑ ,∈ ,

Est-il loin des points des autres clusters ?

o Distance moyenne minimale si affecté dans un autre cluster?

o ∑ ,∈

Si le point est dans le bon cluster :

Silhouette : combinaison des deux scores : ,

o compris dans [-1, 1])

Pour tous les points : ∑

Aide pour déterminer le nombre de clusters (minimiser )44

Au moins 2 points et 2 clusters …

Exemple (scikitlearn) 2 clusters, silhouette (moyenne) = 0,705

3 clusters, silhouette (moyenne) = 0,588

45

Exemple (scikitlearn) 4 clusters, silhouette (moyenne) = 0,650

5 clusters, silhouette (moyenne) = 0,563

46

Stabilité d’un clustering Stabilité Nombreux algorithmes non déterministes : résultats différents lors

d’exécutions différentes de l’algorithme lancer l'algorithme plusieurs fois sur les mêmes données (éventuellement bruitées),

avec initialisation différente, avec des sous-ensembles différents,

Est-ce que les points sont regroupés de manière similaire ?

Mesure pour évaluer cette similarité …. (sans dépendre de la numérotation des clusters) … Voir Indice de Rand

47

K=2 K=4 K=5

Clustering pertinent … Cohérence des résultats Besoin d’un expert du domaine Évaluation « manuelle »

Vérification sur un sous-ensemble de données

48

Section 4. Méthodes Hiérarchiques

49

Principe général Deux types de méthodes hiérarchiques Clustering ascendant (agglomératif) Initialement chaque observation est un cluster

Agglomérer les observations proches

Itérer jusqu’à 1 seul cluster

Clustering descendant (divisif) Initialement toutes les observations sont dans le même cluster

Le diviser jusqu’à séparer toutes les observations

50

Dendrogramme (1) Représentation du résultat Dendrogramme = arbre Feuilles = échantillons

Nœuds = cluster

Hauteur des branches

Proportionnelle distance entre clusters

Représentation partielle Le « haut » de l’arbre

51

Dendrogramme (2) Représentation du résultat Couper un dendrogramme Un ensemble de clusters

52

Exemple

Propriété : monotonie Les fusions se font dans l’ordre croissant de distance

Les barres horizontales (fusion/cluster) ne croisent pas les verticales

53

Méthode ascendante Clustering Hiérarchique Ascendant (CHA)

Initialisation Chaque observation est placé dans un cluster

Calcul d’une matrice de similarité entre clusters (observations)

Répéter

Sélectionner dans les deux clusters les plus semblables et

Fusionner pour former un cluster

Mise à jour de pour calculer similarité entre et les autres clusters

Arrêt : 1 seul cluster

54

Application (1) Données

Distance Euclidienne

55

p1 p2 p3 p4 p5 p6p1 0p2 0,23 0p3 0,22 0,14 0p4 0,37 0,19 0,16 0p5 0,34 0,14 0,28 0,28 0p6 0,24 0,24 0,10 0,22 0,39 0

Application (2) Saut minimal (single linkage)

56

p1 p2 p3 p4 p5 p6p1 0p2 0,23 0p3 0,22 0,14 0p4 0,37 0,19 0,16 0p5 0,34 0,14 0,28 0,28 0p6 0,24 0,24 0,10 0,22 0,39 0

Sélection Min 0,10

Cluster (p3, p6)

Mise à jour de la matrice

o Distance minimale

p1 p2 (p3,p6) p4 p5

p1 0

p2 0,23 0

(p3,p6) 0,22 0,14 0

p4 0,37 0,19 0,16 0

p5 0,34 0,14 0,28 0,28 0

Application (3)

57

Saut minimal (single linkage)

Sélection Min 0,14

Cluster (p2, p5)

Mise à jour de la matrice

o Distance minimale

p1 p2 (p3,p6) p4 p5

p1 0

p2 0,23 0

(p3,p6) 0,22 0,14 0

p4 0,37 0,19 0,16 0

p5 0,34 0,14 0,28 0,28 0

p1 (p2,p5) (p3,p6) p4

p1 0

(p2,p5) 0,23 0

(p3,p6) 0,22 0,14 0

p4 0,37 0,19 0,16 0

Application (4)

58

Saut minimal (single linkage)

Sélection Min 0,14

Cluster (p2, p5, p3, p6)

Mise à jour de la matrice

o Distance minimale

p1 (p2,p5) (p3,p6) p4

p1 0

(p2,p5) 0,23 0

(p3,p6) 0,22 0,14 0

p4 0,37 0,19 0,16 0

p1 (p2,p5,p3,p6) p4p1 0(p2,p5,p3,p6) 0,22 0p4 0,37 0,16 0

Application (4)

59

Saut minimal (single linkage)

Sélection Min 0,16

Cluster (p2, p5, p3, p6, p4)

Mise à jour de la matrice

o Distance minimale

p1 (p2,p5,p3,p6) p4p1 0(p2,p5,p3,p6) 0,22 0p4 0,37 0,16 0

p1 (p2,p5,p3,p6,p4)

p1 0

(p2,p5,p3,p6,p4) 0,22 0

Sélection Min 0,22

Cluster (p2, p5, p3, p6, p4,p1)

Arrêt

Avec différentes mesures (1) Saut minimal (single linkage)

60

p1 p2 p3 p4 p5 p6p1 0p2 0,23 0p3 0,22 0,14 0p4 0,37 0,19 0,16 0p5 0,34 0,14 0,28 0,28 0p6 0,24 0,24 0,10 0,22 0,39 0

Avec différentes mesures (1) Saut maximal (complete linkage)

Saut moyen (average linkage)

61

Sélection Min

Mise à jour de la matrice

o Distance maximale

Sélection Min

Mise à jour de la matrice

o Distance moyenne

Synthèse clustering hiérarchique (1) Méthode flexible Nombre de clusters non fixé A établir en fonction du dendrogramme

Evaluer les différentes possibilités en utilisant les mesures d’homogénéité et de séparation (voir combinaison des scores)

Caractéristiques : Complexité : au moins (calcul de distance) Passage à l’échelle difficile Pas de remise en cause des classes fusionnées Sensible aux anomalies (outliers)

62

Synthèse méthode ascendante (2) Impact des mesures Saut minimal cluster de type chaine Saut maximal cluster de type sphérique

Saut moyen et barycentre uniquement avec données numériques Autres : tout type de données

Variantes Méthode de Ward (distance euclidienne) Méthode basée graphe de voisinage Méthode basée densité plutôt que distance

63

Clustering de Ward Méthodes CHA Regroupement basé sur mesure inter-cluster Ajouter une mesure intra-cluster

Clustering hiérarchique de Ward

Utiliser la mesure ∑ ,∈

Distance euclidienne mesure de l’écart type

Passage à la variance (dispersion)

Mesurer l’inertie d’un cluster : ∑ || ||∈

Faible si points resserrés dans un cluster

Ward : Regrouper deux clusters tels que l’augmentation de la variance intra-cluster soit minimale

64

Exemple Issu de travaux de recherche Obtention de trajets alternatifs en transport en commun Thèse G. Scano, 2016 (LAAS), A. Iglesias 2017 (EMSE)

Hypothèse : pas de préférence a priori sur les alternatives

Principe Générer un ensemble de trajets (base : K-Shortest Path)

Comparer des trajets : définition d’une distance : o Mode de transport; Ligne; Itinéraire (succession d’arrêts); Course (itinéraires avec

horaire), …

Clustering Regrouper les ensemble de solution similaires : CHA et saut minimal

Choisir le meilleur représentant de chaque cluster (temps de trajet)

65

Exemple (2)

66

Section 5. Méthodes par partitionnement

67