Upload
others
View
3
Download
1
Embed Size (px)
Citation preview
Apprentissage non supervisé
M.-J. Huguet
https://homepages.laas.fr/huguet
2017-2018
Plan1. Contexte : l’Intelligence Artificielle
2. Contexte : l’apprentissage
3. Clustering : définitions générales4. Méthodes hiérarchiques ascendantes / agglomératives
5. Méthodes par partitionnement
6. Méthodes hiérarchiques descendantes / divisives
7. Méthodes basées voisinage (densité)
8. Comparaison des méthodes (scikitlearn)
9. Fouille de données1. Graphes2. KDD - Knowledge Discovery Databases
10. Réduction de dimensions (Analyse en Composantes principales)2
Autres références Cours / Sites Introduction to Data Mining : https://www-users.cs.umn.edu/~kumar001/dmbook/index.php
Carlos Castillo : http://chato.cl/
Jeux de tests : http://archive.ics.uci.edu/ml/index.php
Site Kagle
MeetupToulouse Data Science https://www.meetup.com/fr-FR/Tlse-Data-Science/
3
Section 5. Méthodes par partitionnement
4
Principe Ne pas explorer toutes les valeurs possibles pour le nombre de clusters
Considérer que le nombre de clusters est fixé
Exploration d’un intervalle possible sur les clusters
Approches :
Méthodes exactes par évaluation des partitions possibles
Méthodes approchées
Méthode des k-means ou méthodes des centres mobiles :
o à chaque cluster : son centre de gravité (le point associé à la valeur moyenne)
Variante : k-medoïds
o À chaque cluster : son représentant le plus représentatif (le point ayant la distance moyenne minimale / autres points)
5
Nombre de partitions (suite) Nombre de partitions d’un ensemble en : Nombre de Stirling (de deuxième espèce) : , Equations de récurrence :
, 1, 1 1, 0,0 1 et ∀ 0, , 0 0, 0
Formulation explicite : ,!∑ 1
Où est le nombre de combinaisons de parmi
Nombre de Bell : ∑ ,
6
Nombre de partitions (suite) Nombre de Stirling , et nombre de Bell ∑ ,
7
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
Méthode k-means (1) Objectif :
minimiser ∑ ∑ || ||∈ (min Squared Error)
Algorithme : Initialisation
Choisir k éléments (centres) : , … , Les placer dans un cluster : ←
Répéter Affecter chaque élément au centre le plus proche
o ∪ tel que || || Re-évaluer le centre de gravité de chaque cluster
o ∑ ∈
Jusqu’à : // Conditions d’arrêt //
8
Méthode k-means (2) Conditions d’arrêt :
Nombre d’itérations
Plus de changement sur les centres de gravité (ou changements limités)
Pas de changements dans la composition des clusters
Complexité : où
le nombre d’itérations
9
Exemple d’implémentation
Exemple (1) – Données initiales Données initiales Déterminer 3
clusters
10
Exemple (2) – Choix des centres et Allocation Choisir 3 centres Allocation des
points au centre le plus proche
11
Exemple (3) – Re-calcul des centres Calcul des
nouveaux centres pour les 3 clusters
Nouvelle allocation des points aux centres
12
Exemple (4) – Dernière itération Solution
obtenue après 10 itérations
13
Caractéristiques Stratégie gloutonne : Obtention d’un minimum local Faible complexité
Choix des points initiaux Fort impact sur le résultat
Forme des clusters Formes convexes Chaque point d’un cluster est plus proche de
son centre de gravité que des autres centres
14
Initialisation (1) Aléatoire Faire plusieurs exécutions avec différentes initialisation et conserver la meilleure
solution
Echantillonner et utiliser approche hiérarchique pour déterminer des centres
Exemple d’initialisation :
15
Initialisation (2) Points les plus distants
Sensibilité aux anomalies
16
Initialisation (3) K-means++ Choix des centres avec une probabilité liée à la distance au carré aux autres
centres
Garanties / qualité du résultat (2007)
17
Limitations k-means (1) Sensibilité à la
taille des clusters
Sensibilité aux densités différentes
18
Limitations k-means (2) Forme non
convexe
Anomalies
19
Variantes (1) Augmenter le
nombre de clusters
Taille
Densité
20
Variantes (2) Augmenter le
nombre de clusters
Forme
21
Variantes (3) Split & Merge (post-processing)
Découper un cluster quand sa variance est supérieure à un seuil
Regrouper deux clusters quand la distance entre leurs centres est inférieure à un seuil
K-means - - (SIAM International Conference on Data Mining 2013)
Calcul de clusters et détection de anomalies
22
Section 6. Méthodes hiérarchiques descendantes
23
Clustering hiérarchique descendant Principe Clustering descendant (divisif) Initialement toutes les observations sont dans le même cluster
Le diviser jusqu’à séparer toutes les observations
Assez peu de méthodes ? Nombre de possibilités pour diviser en 2 : 2 1
Approche ascendante : nombre de possibilités pour regrouper :
Approches heuristiques Ascendante : regrouper les observations les plus proches
Descendante : séparer les observations les plus éloignées
basées sur calculs de distance
24
Mesure basée sur un calcul d’arbre couvrant Calcul de l’arbre couvrant minimal Minimal SpanningTree (MST) Distance « saut minimal » (single link)
25
Approches hiérarchiques Ascendante
Descendante
26
Clustering hiérarchique descendant Approche descendante Paradigme « divide & conquer »
Diviser les observations initiales en un grand nombre de clusters Déterminer un représentant de chaque cluster
Appliquer une méthode « classique » sur le nouveau problème
Diviser les observations initiales en clusters (méthodes k-means par ex.) Appel récursifs sur les clusters obtenus
27
Section 7. Méthodes basées voisinage / densité
28
Problématique Formes non convexes
29
Approche hiérarchique
K-means
Méthode DBSCAN (1) Objectif Obtenir des formes non convexes
Principe Pour associer les 2 points A et B
créer un chemin pour passer de l'un à l'autre en restant à l'intérieur du même cluster
Notion de voisinage
o Cercle
DBSCAN : Density-Based Spatial Clustering of Applications with Noise30
Méthode DBSCAN (2) Voisinage Pour une observation , et une valeur
Epsilon voisinage : ∈ ,
Point intérieur (core point) : si | |
Points connectés par densité : et sont connectés si Il existe une suite de points intérieurs , , … , tels que
∈ , ∈ , …., ∈
31
Méthode DBSCAN (3) Principe Maintenir une liste de points visités
Répéter Sélectionner un point non visité
Construire le voisinage de
Si alors marquer bruit
Sinon // est un point intérieur
o Initialiser un cluster ← o Agrandir le cluster par voisinage
o Ajouter à la liste des clusters
o Marquer les points de comme visités
Arrêt : tous les points sont visités
32
Le point orange = bruit
Le point orange = cluster violet
Taille voisinage =4
Méthode DBSCAN (4) Exemple
33
Méthode DBSCAN (5) Différents types de points : Points intérieurs (core points)
Points frontières : taille du voisinage inférieure à la limite mais appartenant au voisinage d’un point intérieur
Bruit (noise point) : ni point intérieur ni point frontière
34
Caractéristiques Peu sensible à la forme et à la taille des clusters Peu sensible aux anomalies
Paramètres : Fixer la taille du voisinage et le nombre de points à considérer
Très utilisé En particulier en segmentation d’images
35
Limitation Sensible à la densité
36
Taille voisinage =4
Epsilon=9.92
Epsilon=9.75
Méthodes basées graphe (1) A partir des données Déterminer la matrice de proximité 2 à 2 Single link, complete link, etc,
Construire un graphe : un sommet du graphe : une donnée
Arête : valuée par la proximité
Clusters : composantes connexes du graphe
Mais graphe complet
« Sparsification » du graphe
37
Méthode basées graphe (2) « Sparsification » du graphe Réduire la quantité d’information à manipuler Réduire le temps de calcul pour le clustering et
Augmenter la taille des problèmes pouvant être considérés
Conserver uniquement les voisins les plus similaires devraient être dans le même cluster
réduire les effets du bruit et des anomalies
Exemple : Méthode Chameleon Hiérarchique
38
Méthode Chameleon Pré-processing : Calculer le graphe des plus proches voisins
Deux phases Déterminer des sous clusters initiaux (partition du graphe des k-ppv) Approche hiérarchique ascendante : Mesures spécifiques pour regrouper des clusters (inter-connectivité et proximité)
39
Quelques résultats
40
Méthode SNN (Shared Near Neighbor) Graphe Sommets : les observation Arêtes : pondérées par le nombre de voisins en commun
41
Méthode SNN Principe Calculer matrice de similarité Sparsification : conserver uniquement les k voisins les plus similaires Construire le graphe SNN Seuil de similarité
Composantes connexes
Appliquer méthode DBSCAN
Remarque : tous les points ne sont pas alloués à un cluster
Complexité :
42
Quelques résultats
43
Section8. Comparaison (scikitlearn)
44
Scikitlearn (1) Scikitlearn Librairie d’algorithmes d’apprentissage surpervisé et non suppervisé Interface en Python Basé sur (NumPy, SciPy, Matplotlib, Ipython, Sympy, Pandas) Pour le chargement, la manipulation et le résumé de données : NumPy,
Pandas
Scikit-learn homepage http://scikit-learn.org
Presentations et Tutorials http://scikit-learn.org/stable/presentations.html
45
Scikitlearn (2)
46
Scikitlearn (3) Clustering 9 méthodes proposées et comparées http://scikit-learn.org/stable/modules/clustering.html
47
Section 9.1. Fouille de Données et Graphes
48
Partitionnement de Graphes (1) Fouille de données dans des graphes Différentes problématiques Mesures et Propriétés de graphes réels (densité,
diamètres, connexité, ….)
Algorithmique : calculer sur des grands graphes
Détection de communautés (clustering)
Applications Réseaux sociaux, de communication,
Systèmes de recommandation,
Cartographie,
Epidémiologie,
Sociologie, …
49
Partitionnement de Graphes (2) Détection de communautés dans des graphes/réseaux
Quelques propriétés dans des graphes : Composantes connexes / k-connexes
Cliques, …..
50
Partitionnement de Graphes (3) Méthode hiérarchique ascendante
1. Associer une communauté (un cluster) à chaque sommet
2. Calculer une distance entre chaque paire de communautés
3. Fusionner les deux communautés les plus proches
Retour étape 2
Distance entre communautés : min, max, moyenne entre paires de sommets
51
Partitionnement de Graphes (4) Méthode hiérarchique descendante
1. Calculer la centralité (poids) de chaque lien
o nb de plus courts chemins utilisant le lien
2. Enlever le lien de plus forte centralité
Retour en 1 jusqu’à ce que tous les liens soient supprimés
Résultats : différentes composantes connexes à chaque étape Calcul centralité à chaque étape
52
Partitionnement de Graphes (5) Méthodes basées voisinage/densité
Maximiser le nombre de connexions intra-communautés
Minimiser le nombre de connexions inter-communautés
Si seulement minimiser le nombre de connexions inter-communautés
53
Cut(A,B)=2
Connexions(A)=3
Connexions(B)=3
Min Cut=1
Ce n’est pas une bonne solution
Partitionnement de Graphes (6) Méthodes basées voisinage/densité
Différentes variantes pour déterminer un « bon » partitionnement
Normalized-Cut : ,,
_
,
_
o Avec _ le nombre de liens ayant une extrémités dans
Variantes avec des arêtes pondérés
o Exemple : partitionnement espace aérien (th. Bichot 2012)
54
Partitionnement de Graphes (7) Méthode par propagation de labels
Initialisation Affection d’un label différent à chaque sommet (un label différent par sommet)
Itérations Trier les sommets dans un ordre aléatoire
Pour chaque sommet $x$ :
o déterminer le label $l$ maximal pris par ses voisins (random si égalité)
Arrêt : stabilité sur les labels ou nombre maximal d’itérations
Intérêt : méthode rapide
Limite : résultats non stables (sensibilité liées aux étapes avec de l’aléatoire)
55
Partitionnement de Graphes (8) Méthode par propagation de labels
Résultats différents …
56
Section 9.2. Fouille de Données - KDD
57
Généralités (1) Fouille de données (Data Mining)
Processus de découverte automatique de connaissances dans des grandes collections de données
KDD : Knowledge Discovery Databases
Différentes étapes en KDD Pre-processing des données
o Préparation des données (nettoyage, normalisation, ….)
Fouille de données
Post-processing des résultats :
o Validité et pertinence des connaissances obtenues / besoins initiaux
o Visualisation
58
Généralités (2) Techniques de fouille de données
Analyse prédictive Déterminer un modèle de classification des données à partir d’exemples
Exploitation de ce modèle pour prédire la classification de nouvelles données
Clustering Partitionner des données pour regrouper des observations similaires et séparer des
observations différentes
Découverte de patterns Découvrir des « patterns » corrélés ou des associations des patterns corrélés
Différents problèmes
o Frequent Item Sets
o Association Rules
59
Découverte de patterns (1) Ensemble d’items : , … , d’une base de données
ItemSet : ⊆ Frequence de X : : nombre de transactions de contenant X
Support de : : fraction des transactions de contenant
| |
FrequentItemSet Pour une base de transaction et un seuil ̅, déterminer l’ensemble de tous les
ItemSet tel que ̅
60
ID Items
1 A B
2 A C D E
3 B C D F
4 A B C D
5 A B C F
freq({A,B,C})=2supp({A,B,C})=2/5
Découverte de patterns (2) Association Rule
Exprimer une relation entre deux itemsets : → avec et deux itemsets tels que ∩ ∅
Support : → ∪
Confiance : →∪ ∪
61
Exemple : {A,B} {E,F}{A,D} {B} : co-occurence
ID Items
1 A B
2 A C D E
3 B C D F
4 A B C D
5 A B C F
supp({B,C} {D}) = supp({B,C,D})=2/5conf ({B,C} {D}) = freq({B,C,D})/freq({B,C}) = 2/3
Découverte de patterns (3) But Obtenir toutes les règles d’association → telles que ∪ ̅ → ̅
Méthode Brute-Force Énumérer toutes les règles d’association
Calculer les valeurs de support et de confiance
Sélectionner celles respectant les seuils
Impossible de passer à l’échelle
62
Découverte de patterns (4) Retour sur l’exemple
Mêmes valeurs de support
Valeurs de confiance différentes
Déterminer les règles d’association1. Générer les itemsets fréquents (ayant un support supérieur à un seuil)
2. Générer les règles d’association à partir de chaque itemset fréquent
o Enumérer les associations possibles pour les itemsets fréquents
Mais problème de passage à l’échelle pour générer les itemsets fréquents …63
ID Items
1 A B
2 A C D E
3 B C D F
4 A B C D
5 A B C F
Supportfreq(BCD)/5
Confiance freq(BCD)/freq(ant)
{B,C}{D} 0,4 (2/5) 0,67 (2/3)
{B,D}{C} 0,4 1,00 (2/2)
{C,D }{B} 0,4 0,67
{D}{B,C} 0,4 0,67
{C}{B,D} 0,4 0,50
{B}{C,D} 0,4 0,50
Règles d’association avec les 3 items B, C et D
Découverte de patterns (5)
64
Pour items : 2 1 itemsets possiblesnull
AB AC AD AE BC BD BE CD CE DE
A B C D E
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
ABCD ABCE ABDE ACDE BCDE
ABCDE
Méthode « Apriori » (1) But : réduire le nombre de sommets candidats à explorer
Principe : Si un itemset X est fréquent alors tous ses sous-ensembles sont également
fréquents ∀ , ∶ ⊆ ⇒
Le support d’un itemset ne peut pas dépasser celui de ses sous-ensembles
Propriété d’anti-monotonie
65
Méthode « Apriori » (2) Elagage de l’arbre
66
Méthode « Apriori » (3) Application
67
ID Items
1 A B
2 A C D E
3 B C D F
4 A B C D
5 A B C F
1-Item Freq SuppA 4 0,8B 4 0,8C 4 0,8D 3 0,6E 1 0,2F 2 0,4
2-Items Freq Supp{A,B} 3 0,6{A,C} 3 0,6{A,D} 2 0,4{B,C} 3 0,6{B,D} 2 0,4{C,D} 3 0,6
Seuil Fréquence = 3 Seuil Support = 3/5=0,6
3-Items Freq Supp{A,B,C} 2 0,4
Méthode « Apriori » (4) Déterminer les règles d’association Partir d’un itemset fréquent et déterminer tous les sous-ensembles tels
que → respectant le seuil de confiance Ex : , , , , l’ensemble des règles d’association est :
Nombre de règles d’association : 2| | 2 on ne considère pas ∅ → et → ∅
Propriétés : soit , , , , , → , → , → , ,
68
{A}{BCD} {B}{ACD} {C}{ABD} {D}{ABC}{AB}{CD} {AC}{BD} {AD}{BC} {BC}{AD} {BD}{AC} {CD}{AB}{ABC}{D} {ABD}{C} {ACD}{B} {BCD}{A}
Méthode « Apriori » (5) Elagage de l’arbre
69
Pruned Rules
Méthode « Apriori » (6) Application
70
ID Items
1 A B
2 A C D E
3 B C D F
4 A B C D
5 A B C F
1-Item Freq SuppA 4 0,8B 4 0,8C 4 0,8D 3 0,6E 1 0,2F 2 0,4
2-Items Freq Supp{A,B} 3 0,6{A,C} 3 0,6{A,D} 2 0,4{B,C} 3 0,6{B,D} 2 0,4{C,D} 3 0,6
Seuil Fréquence = 3 Seuil Support = 3/5=0,6
3-Items Freq Supp{A,B,C} 2 0,4
Supp Conf{A}{B} 0,6 0,75{B}{A} 0,6 0,75{A}{C} 0,6 0,75{C}{A} 0,6 0,75{B}{C} 0,6 0,75{C}{B} 0,6 0,75{C}{D} 0,6 0,75{D}{C} 0,6 1
Seuil Confiance=0,8
Méthode « Apriori » (7) Nombreuses optimisations de la méthodes
Structures de données,
Génération de règles redondantes : élagage
Mesures complémentaires : intérêt des connaissances produites
Extensions à la recherche de séquences de patterns Transactions successives sur un horizon temporel
71
Section 11. Réduction de dimensions
72
Réduction de dimensions (1) Le problème : Un ensemble de exemples / observations Une observation : attributs / features Exemple : une image avec pixels
Réduire la dimensions des observations
Extraire des caractéristiques pertinentes / données Feature extraction (méthode non supervisée)
Analyse en composantes principales (ACP) / PCA
73
Réduction de dimensions (2) Intérêts : Visualisation des données Plus facile en dimension 2 ou 3 ….
Cout algorithmique des traitements Mémoire, calculs, acquisition
Apprentissage Modèle de taille réduite
Moins d’erreurs d’apprentissage ex : distance entre deux attributs ne dépend pas de l’attribut (tous ont le même poids)
74
3PPV- bleu 3PPV- orange
Réduction de dimensions (3) Objectifs Réduire le nombre de dimensions pour représenter les données tout en
minimisant l’information perdue
Analyse en Composantes Principales Maximiser la variance lors de la projection dans le nouvel espace de
représentation Standardisation des données
75
Standardisation des données (1) Variance Soit une variable statistique :
Taille population (Somme des , avec : nb d’occurrences de )
Variance (où moyenne de ) = carré de l’écart type
…
Mesure de dispersion autour de la moyenne Ex : [10; 20; 30; 40; 50] (effectif = 1 pour chaque valeur)
o Variance = 200 (Ecart type = 14,14)
Ex : [0,1; 0,2; 0,3; 0,4; 0,5] (effectif = 1 pour chaque valeur)
o Variance = 0,02 (Ecart type = 0,1414)
76
Valeur de x v1 v2 … vpEffectif n1 n2 np
Standardisation des données (2) Centrer et normer chaque valeur :
←
Ex [10; 20; 30; 40; 50] [-1,41; -0,70; 0; 0,70; 1,41] Moyenne = 0, Variance = 1
Ex : [0,1; 0,2; 0,3; 0,4; 0,5] [-1,41; -0,70; 0; 0,70; 1,41] Moyenne = 0, Variance = 1
77
Analyse en Composantes Principales (1) Données initiales :
But ACP : Déterminer nouvelles colonnes combinaison linéaire des colonnes
initiales de telle sorte que la perte d’information soit minimale Nouvelles colonnes composantes principales
Nouveaux axes axes principaux
Combinaisons linaires facteurs principaux
78
attributs1 2 j d
échantillons
1 x_1,1 x_1,2 x_1,j x_1,d2 x_2,1 x_2,2 x_2,j x_2,d
i x_i,1 x_i,2 x_i,j x_i,d
n x_n,1 x_n,2 x_n,j x_n,d
Analyse en Composantes Principales (2) Projection des points dans un sous espace
79
Analyse en Composantes Principales (3) Chercher le nouvel espace $F$ tel que
Ce qui revient à maximiser
C’est à dire la variance
80
Analyse en Composantes Principales (4) Projection : La composante $j$ fournit les coordonnées des observations dans le nouveau
repère sur le $j$ème axe
Chaque composante fournit une valeur de la variance
Les axes sont orthogonaux : Les composantes principales ne sont pas deux à deux corrélées
81
Analyse en Composantes Principales (5) Choix du nombre de composantes Variance totale expliquée
…
Ratio obtenu pour chaque composante :
∑
Ratio cumulé sur 2 composante :
∑
82
Exemple UCI Data set (Optdigits)
83
Conclusion (1) Un aperçu de quelques méthodes d’apprentissage artificiel
non supervisé pour : Le clustering
La fouille de données (KDD)
La fouille de graphes
Domaine très vaste : beaucoup de méthodes spécifiques
Présence de contraintes additionnelles Éléments devant être (ou pas) dans un même cluster, appartenance possible à
plusieurs clusters, ….
Sélection d’items respectant une contrainte Transaction ayant un prix supérieur à un seuil
Visite de certains types de pages web, ou d’une certaine séquence, …
Volume de données : scala / Spark, …
84
Conclusion (2) Combinatoire des problèmes Problèmes d’optimisation/décision mal définis Méthodes approchées spécifiques
Mineure Analyse Prescriptive : Méthodes d’optimisation combinatoire
Méthodes exactes/approchées
Programmation Mathématique, Programmation par Contraintes
Recherche locale, Métaheuristiques (Recuit, Tabou, Génétique, Colonies de Fourmis, …)
Quelques liens : Tias Guns : http://homepages.vub.ac.be/~tiasguns/
Andrea Lodi : http://www.cerc.gc.ca/chairholders-titulaires/lodi-fra.aspx
Data Mining & Constraint Programming : https://link.springer.com/book/10.1007%2F978-3-319-50137-6
85
86