View
9
Download
0
Category
Preview:
Citation preview
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
Recommended