View
118
Download
1
Category
Preview:
Citation preview
FOUILLE DE DONNÉES
Bertrand JouveUniversité Lyon 2
FOUILLE DE GRAPHES
Eléments de cours - Master 2
2011-2012
Sources
Ce support de cours a été réalisé en partie à l’aide de plusieurs documents accessibles en libre accès sur le web ou de notes de cours de collègues : o Vipin Kumar : http://www-users.cs.umn.edu/~kumar/dmbook/index.php#item3
o Philippe Leray : http://asi.insa-rouen.fr/enseignement/siteUV/dm/Cours/clustering.pdf
o Taofiq Dkaki : communications personnelles
o Ricco Rakotomalala : http://eric.univ-lyon2.fr/~ricco/cours/supports_data_mining.html
o M. Cottrell et P. Letremy : http://samos.univ-paris1.fr/archives/ftp/preprints/samos173.pdf
o Machine Learning Group (Austin) : http://www.cs.utexas.edu/~mooney/cs391L/slides/svm.ppt
o Mingyue Tan : http://www.iro.umontreal.ca/~pift6080/H09/documents/papers/svm_tutorial.ppt
Plan
1) Organisation des séances
2) Eléments de bibliographie et logiciels
3) Qu’est ce que la fouille de données ?
data (cleaning, preprocessing), visualisation.
4) Méthodes de fouille de données
Prédictive/supervisée et descriptive/non-supervisée
5) Challenges
6) Fouille de graphes et système complexes
2 séances de cours (2*3H) : exposé général sur la fouille de données
2 séances de cours/TD (2*1H45) sur la fouille de graphes à partir d’exemples
5 séances de restitution d’articles 1 séance de 2H pour le contrôle des
connaissances.
1) Organisation des séances
De nombreuses ressources sur le web : Knowledge Discovery in Databases(KDD), Extraction de connaissances dans les bases de données (ECD), Datamining, fouille de données, …
2) Eléments de bibliographie et logiciels
http://www.kdnuggets.com/http://www.math.ccsu.edu/larose/DM%20resources.htm
http://www.web-datamining.net/
Des logiciels
http://www.rdatamining.com/
R SAS
J. Han, M. Kamber (2001)
Ludovic Lebart, Marie Piron, Alain Morineau (2006)
Stéphane Tufféry (2005)
Usama M. Fayyad, Gregory Piatetsky-Shapiro, Padhraic Smyth, Ramasamy Uthurusamy (1996)
Des livres
3) Qu’est ce que la fouille de données ?
EXEMPLES commerciaux Le panier de la ménagère :Déterminer les produits qui sont souvent associés dans un chariot de supermarché
• traitement des tickets d’achats
→ corrélation Bières / couches le samedi
→ réorganisation des rayonnages
http://www.amazon.fr :Quels sont les livres qui pourraient être achetés par le visiteur ?
EXEMPLES scientifiques Qualité de vie (réchauffement climatique)
• extraction d’information sur la pollution atmosphérique, sonore, … sur la gène ressentie, …
→ cartographie fine, modèles, prévision
→ décisions publiques, aménagements, Modèles sociétaux nouveaux
• webmining, analyse des réseaux sociaux (Facebook)
→ communautés dynamiques et multi-échelles
→ amélioration des modes de communication et d’organisation
Génome
•Les tumeurs du cerveau représentent la 1er cause de mortalité de cancer chez les enfants
→ Gene expression database
Encyclopædia Britannica
“data mining, also called knowledge discovery in databases, in
computer science, the process of discovering interesting and
useful patterns and relationships in large volumes of data. (…)
Data mining is widely used in business (insurance, banking, retail),
science research (astronomy, medicine), and government security
(detection of criminals and terrorists).”
Définition
Extraction automatique ou semi-automatique de connaissances cachées, potentiellement utiles, à partir de données stockées dans des grandes bases de données.
Fouille de données = extraction de connaissances à partir des données (ECD) = Data Mining = Knowledge Data Discovery (KDD)
« Comment trouver un diamant dans un tas de charbon sans se salir les mains »
1. Compréhension du domaine d’application
2. Création du sous-ensemble cible de données
3. Nettoyage des données (erreurs, données manquantes, valeurs atypiques)
4. Transformation des données (normalisation, linéarisation, découpage en classes, compression)
5. Explicitation de l’objectif et de la stratégie d’analyse
6. Choix des méthodes
7. Test, en précisant les critères
8. Exploitation
9. Diffusion
DATA MINING
expert
décideuranalyste(Fayyad, 1997)
CRISP-DM découpe le processus de data mining en six phases principales :• Connaissance du Métier• Connaissance des Données• Préparation des Données• Modélisation• Évaluation• Déploiement
Shearer C. The CRISP-DM model: the new blueprint for data mining [archive]. J Data Warehousing 2000;5:13—22.
Méthode standardisée CRISP-DM Cross-Industry Standard Process for Data Mining
Ce que la fouille de données n’est pas : Chercher un numéro de téléphone dans un annuaire
téléphoniqueEffectuer une recherche avec google
Ce que la fouille de données est : Analyser des résultats de requêtes effectuées avec
google.Analyser la structuration des pages d’un annuaire
téléphonique
Informatique : Evolution des Langages d’interrogation, Environnement hétérogène et sites distants, Fiabilité, sécurité, stockage distribué, temps réel
Fouille de données et statistique Historiquement la fouille de données est la rencontre de
l’intelligence artificielle et de la statistique : les entreprises veulent exploiter, valoriser, les masses de données qu’elles archivent (data warehouse = entrepôts de données) à des fin de marketing et de prise de décision.
StatistiqueClassification hiérarchiqueNuées dynamiques,Régression linéaire,…
IA Perceptron multicoucheReconnaissance de
formeRéseaux bayésiens,Règles d’induction,…
CROISER LES METHODES
Les différences à dépasser : Données a priori : dans la plupart des problèmes de data mining, les
données sont préalables à l’étude, recueillies parfois à d’autres fins. En statistique, la démarche de recueil des données (planification expérimentale, sondage) fait partie intégrante du processus.
Taille des données : de nombreuses méthodes statistiques classiques ne sont pas adaptées à des volumes de millions de données.
Automatisation : la statisticien reste au plus près des experts pour s’assurer une bonne compréhension, une cohérence , une intégrité des données. Les promoteurs de logiciels de FDD isolent les deux par des interfaces différentes.
Validation : l’évaluation de l’erreur est primordiale dans certains domaines (pharmacie, aéronautique), et la question de la représentativité des données devient centrale.
Objectifs disciplinaires : preuve d’un côté et efficacité opérationnelle de l’autre.
Fouille de données et statistique
Pourquoi la FDD maintenant ?
http://genomesonline.org
we see the doubling of the numbers of base pairs in GenBank every 18 months
Aug-0
1
Oct-0
2
Dec-0
3
Feb-0
5
Apr-0
6
Jun-
07
Aug-0
8
Oct-0
9
Dec-1
00
200
400
600
800
1000
1200
1400
edits (en milliers)
new "wikipedian" (>10)
Wikipedia – Google analytics (http://stats.wikimedia.org)
Pourquoi la FDD maintenant ?
http://www.allfacebook.com/google-vs-facebook-2010-09
Pourquoi la FDD maintenant ?
Google : Statistiques concernant l’exploitation du bois
Vitesse de transmission des réseaux (Zighed D.A., Rakotomalala R.,2003.)
R. Grossman, C. Kamath, V. Kumar (2001)
Les questions de fouille de données sont maintenant cruciales dans beaucoup de domaines.
Le problème aujourd’hui n’est pas un manque de données mais un manque d’analystes et de méthodes plus performantes.
Il ne faut pas croire que les logiciels sont « plug-and-play » et fournissent des « solutions » sans nécessité de l’être humain :• les logiciels donnent toujours des résultats• il est facile de faire de la « mauvaise fouille de
données » et cela peut « coûter » très cher.• La plupart des erreurs proviennent d’une mauvaise
utilisation des logiciels « boîte noire ».
Conclusions intermédiaires
a. Les données
Qu’est ce qu’une donnée ?
Une collection d’objets et leurs attributs ou caractéristiques
Type d’attribut : Qualitatif
○ Nominal○ Ordinal
Quantitatif○ Discret○ Continu
Tid Refund Marital Status
Taxable Income Cheat
1 Yes Single 125K No
2 No Married 100K No
3 No Single 70K No
4 Yes Married 120K No
5 No Divorced 95K Yes
6 No Married 60K No
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No
10 No Single 90K Yes 10
Attributes
Objects
Données spatiales : images satellitaires, données géo-référencées, …
Données textuelles : entretiens, blogs, courrier électronique, …
Des contraintes de spécification des données :
Données relationnelles : World Wide Web, Réseaux Sociaux, …
Données temporelles : flux de circulation, bourse, …
Données multimédia : photos, vidéo, …
Données séquentielles : génome, …
Qualité des données :
Les données peuvent ne pas être de bonne qualité
Bruitées ou comprenant des individus aberrants : enregistrement sonore par un mauvais enregistreur, photo mal sauvegardée, manuscrit peu lisible, renard dans un poulailler…
Avec des valeurs manquantes : information non non collectée (personne refusant de répondre à un questionnaire), protocole expérimental défaillant ou coûteux, …
Problème de Vrai/Fausse duplication : homonymies dans les réseaux sociaux, même personne avec différente adresses mail, …
Solutions : Pour les données manquantes, on peut
○ Éliminer les individus à problème○ Estimer les valeurs manquantes○ Ignorer les valeurs manquantes pour l’analyse○ Remplacer par toutes les valeurs possibles
Pour les données dupliquées, on peut mettre en œuvre un processus de détection des individus dupliquées
Ces questions sont souvent difficiles et ne sont pas à sous-estimer.
Attention : on peut être très intéressé par les individus « aberrants » s’ils sont interprétables Détection d’intrusion dans les
réseaux informatiquesDétection de fraude sur cartes de crédits
Prétraitements des données Agrégation d’attributs ou d’individus
Réduire le nombre d’attributs ou d’individus, Opérer un changement d’échelle pour diminuer la
variabilité ou augmenter le nombre d’individus par attributs○ Jours agrégées en semaines, mois, années.
Standard Deviation of Average Monthly Precipitation (Australie)
Standard Deviation of Average Yearly Precipitation
© T
an e
t al
. (2
004)
Prétraitements des données
Échantillonnage : L'objectif est de construire un échantillon tel que les observations pourront être généralisées à l'ensemble de la population.
Question type : est-ce qu’un échantillon de taille n suffit ?
Souvent nécessaire pour des questions de coût ou de temps calcul.○ Notion d’échantillon représentatif○ Théorie statistique de l’échantillonnage : tirage
aléatoire avec ou sans remise, tirage stratifié, …
Prétraitements des données
Réduction de dimension : Questions de coût ou de temps calcul.
Améliorer la visualisation des données
Éliminer le bruit
On utilise par exemple les techniques d’ACP, mais aussi
les techniques non linéaires.
Analyes multi-spectrale d’une section de grain d’orge (19 dimensions) Nu
zilla
rd e
t a
l. (2
00
3)
Prétraitements des données
Sélections d’un sous-ensemble d’attributsPermet aussi de réduire la dimensionLorsque l’information contenue dans un attribut est
déjà présente dans d’autres attributs et qu’il n’y a pas nécessité de l’isoler.○ Exemple : prix de vente d’un produit et TVA
Lorsque l’attribut n’est pas utile pour l’étude○ Exemple : Dans une étude de circulation des
usagers sur un campus universitaire, la couleur des yeux.
Pour des raisons de confidentialité○ Exemple : le nom des individus
Prétraitements des données
Création ou transformation d’attributsCombinaison d’attributsTransformation dans un nouvel espace
○ Exemple: transformée de Fourier
DiscrétisationCertaines méthodes ne conviennent que pour des
données à valeurs discrètes.○ Exemples : valeurs de températures et catégories
« froid/tiède/chaud »
b. Visualisation (non détaillée)
La visualisation revêt deux aspects : Pour présenter les résultats des calculs dans un
format plus facilement appréhendable par l’humain.Comme étape au cœur du data mining, permettant
une présentation des données qui permettent à l’humain une exploration visuelle.○ L’œil humain est extrêmement sensible à des
discontinuités de couleurs○ L’œil humain est capable de détecter des formes
inhabituelles, ○ …
Les outils classiques de statistique
Température à la surface de la terre en juillet 1982 (SST) for July 1982 (dizaines de milliers de points)
Evolution de 2 communautés de l’internet
Aynaud & Guillaume (2010)
L’œil humain est un « outil » très puissant mais attention :
The café wall
Triangle de Kanizsa
The café wall
Illusion d’Ehrenstein
4) Méthodes de fouille de données
2 types de méthodes
Méthodes descriptives (ou non supervisées) : objectif : trouver des « formes » interprétables qui permettent de décrire les données sans référence à une base d’exemples. C’est donc la construction d’un modèle et la découverte de relations dans les données.
clustering (K-means, CAH), règles d’associations, SOM, …
Méthodes prédictives (ou supervisées) : objectif : à partir d’exemples, inférer sur les données pour réaliser des prédictions. En ce basant sur un ensemble d’exemples, on infère par exemple les classes d’appartenance d’autres individus. Les classes sont donc ici connues. classification, régression, k-ppv …
Méthodes descriptives
Clustering
Règles d’association
Clustering
Définition : étant donné un ensemble d’individus chacun ayant un certain nombre d’attributs, et une mesure de similarité entre eux deux à deux, trouver des classes telles que : Les indices de similarités entre individus d’une même classe soient faibles
Les indices de similarités entre individus de classes différentes soient fortes.
Expression in Exp 1
Exp
ress
ion
in E
xp 2 Proteins
Notion de similarité Distance : on appelle distance sur un ensemble E, une
application telle que :
Séparation
Symétrie
Inégalité triangulaire
Une distance est dite ultra-métrique si de plus
Une distance est euclidienne si elle peut-être représentée dans l’espace euclidien Rn sans déformation.
A1 A2 A3 A4 A5 A6I1 1 1 1 1I2 1 1 1I3 1 1 1I4 1 1I5 1 1I6 1 1 1 1
Exemple
Notion de similarité
Similarité : une similarité est une application qui a les propriétés de la distance sauf éventuellement l’inégalité triangulaire.
Ecart : un écart est une application qui a les propriétés d’une similarité sauf éventuellement la symétrie.
La similarité peut-être une fonction des valeurs que peuvent prendre les objets sur un certain nombre d’attributs. Elle peut aussi résulter d’un simple test de catégorisation par exemple.
Exemple : Sur un ensemble de 10000 articles de journaux, la distance entre deux articles est égale au nombre de mots communs.
Exemples de (dis)similarités
Données quelconques:
Exemples de (dis)similarités
Données binaires :
A1 A2 A3 A4 A5 A6I1 1 1 1 1I2 1 1 1I3 1 1 1I4 1 1I5 1 1I6 1 1 1 1
Exemple
Certaines peuvent être étendues aux données discrètes non binaires
Dice
Exemples de (dis)similarités
Exemple de la distance de Dice
Notion de similaritéLa dissimilarité peut résulter simplement d’un test de catégorisation libre :D(i,j)=0 si i et j sont classés ensembleD(i,j)=1 sinonpuis moyenné sur l’ensemble des patients
Différents types de clustering Par partitionnement :
Les classes forment une partition de l’espace des individus (pas de recouvrement)
les classes peuvent être empiétantes
Par classification hiérarchique
Il est toujours très important de pouvoir évaluer la qualité d’une partition. Il n’y a pas de critère universel, mais il faut s’accorder sur un critère en début d’étude avec les experts du domaine.Les critères statistiques courants dépendent en général de l’inertie interclasses, de l’inertie totale, du diamètre des classes.Mais si un expert n’est pas capable d’expliquer la majorité des classes trouvées, il y a probablement un problème !! Il est souvent très utile de croiser les méthodes.
Méthode de partitionnement de type k-means
Algorithme :
Choisir k éléments initiaux, centres des classes
Assigner à chaque individu la classe dont le centre est le plus proche
Recalculer le centre de chaque classe
Itérer l’algorithme jusqu’à ce que les individus ne changent plus de classe.
Méthode de partitionnement de type k-means
Très simple à mettre en place mais
• la complexité est élevée : k * n * O(distance) * nombre(iter)
• les « outliers » faussent les moyennes et donc les centres (les supprimer en preprocessing)
• sensibilité à l’initialisation (essayer plusieurs initialisations et sortir les
formes fortes) : on peut tomber dans des minimum locaux.
Utiliser une CAH pour déterminer les centroïdes
Avantages et inconvénients
Optimisation de
Peu de chances de tirer un point initial dans chaque cluster. K=10 et P=0,00036
Méthode de partitionnement de type k-means
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
yIteration 1
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
yIteration 2
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
yIteration 3
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
yIteration 4
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
yIteration 5
-2 -1.5 -1 -0.5 0 0.5 1 1.5 2
0
0.5
1
1.5
2
2.5
3
x
yIteration 6
Tan
el a
l. (2
004)
Méthode de partitionnement de type k-means
Tan
el a
l. (2
004)
Original Points K-means (2 Clusters)
Méthode de classification hiérarchique
Principe : produire une série de groupes (« clusters ») emboîtés soit par agglomération des individus (Classification Ascendante Hiérarchique) soit par division du tout (Classification Descendante Hiérarchique).
Algorithme général de la CAH :Partir de la partition initiale où les classes sont les singletons
Construire une nouvelle partition en réunissant les classes les plus proches (au sens d’un critère à définir)
Itérer l’algorithme jusqu’à l’obtention d’une seule classe.
M2 NTIE 2009-2010
Budget loisirs Budget alimentation
Famille 1 (F1) 2 1
Famille 2 (F2) 1,5 1
Famille 3 (F3) 2 3
Famille 4 (F4) 3 4
Famille 5 (F5) 1 6
Famille 6 (F6) 2 6
Famille 7 (F7) 8 1
Famille 8 (F8) 8 3
Famille 9 (F9) 10 5
F1F2
F3
F4
F7
F8
F6F5
F9
F2F1 F5 F6F3 F4 F7 F8 F9
Ultramétrique du lien simple
Comment définir la similarité inter-clusters ? Lien simple
Lien complet
Lien moyen
Distance de Ward
Distance des centres de gravité
Partition à partir d’une CAH:
Où Couper le dendrogramme ?
→ détermination de k le nombre de classes
Augmentation minimum de l’inertie intra classe
Effet de chaîne
Casse les gros clusters denses
Peut être utilisé pour initialiser un k-means
Source : Economie et Statistique n°332-333, 2000, Insee
• Description des structures démographiques : âge, fécondité, solde migratoire, …• description des structures sociales : tx de nuptialité, tx de divortialité, …• description du marché du travail : tx d’activité, tx de salariat, …• niveau d’éducation : tx de titulaires d’un diplôme de 1er cycle d’études supérieures, …
Distance de l’ACP et Métrique de Ward
Exemple : Performances macro-économiques et structures sociales européennes http://www.insee.fr/fr/ffc/docs_ffc/es332-333c.pdf
Ward Lien simple Lien complet
Exemples :
Une méthode utilisant le concept de graphes : CHAMELEON Graphe des k plus proches voisins:
o On dispose d’une matrice de proximité (similarité ou non)
o Considérer chaque individu comme un nœud du graphe
o Chaque individu est relié par une arête à ses k plus proches voisins.
Techniques de clustering de graphe : coupe minimale, …
→ multitude de « petits » clusters très denses en connexions
Agglomération : o Utiliser des techniques d’agglomération hiérarchique (CAH) pour
fusionner les « petits » clusters.
Donne de bons résultats sur les données spatiales
CHAMELEON CURE
Règles d’associations Principe : Etant donné un ensemble de transactions, trouver des
règles qui permettront de prédire un item sur la base des occurrences des autres items dans la transaction : il s’agit de mettre en relation des données
Exemple :
• Supermarché
o Un grand nombre d’articles : pain, beurre, …
o Un grand nombre de paniers
Items Lait Beurre Thé Café Confiture
1 1 0 0 1 1
2 0 1 1 0 1
3 1 1 0 1 1
4 1 1 1 0 1
5 1 1 1 1 1
6 0 1 1 1 0
Transactions
Remarque :
• si « Thé » alors « Beurre »• si « Lait et Beurre » alors « confiture »• …
The → Beurre
{Lait, Beurre}→ Confiture
Règles d’associations Mesure :
Confiance :
Support :
Objectif : étant donné un ensemble de transactions, il s’agit de trouver des règles dont la confiance et le support sont supérieurs à des seuils donnés.
Algorithme naïf : lister toutes les règles, calculer les valeurs de support et de confiance et comparer aux seuils.
→ algorithme irréalisable.
Items Lait Beurre Thé Café Confiture
1 1 0 0 1 1
2 0 1 1 0 1
3 1 1 0 1 1
4 1 1 1 0 1
5 1 1 1 1 1
6 0 1 1 1 0
Transactions
c(Thé→ Beurre) =4/4=1 s(Thé→ Beurre)= 4/6=0,67c(Beurre→ Thé) =4/5=0,8 s(Beurre→ Thé)= 4/6=0,67
Règles d’associations Stratégie pour baisser la complexité :
Ne chercher les règles d’association que dans les ensembles fréquents, c’est-à-dire dont le support est supérieur au seuil fixé.
Propriétés : o Si un ensemble n’est pas fréquent alors
aucun de ses sur-ensemble ne peut être fréquent .
o Si un ensemble est fréquent alors tous ses sous-ensemble le sont.
Algorithme : Générer les singletons fréquents F1.
A chaque itération k, générer les Fk candidats à partir des Fk-1. Eliminer les Fk qui contiennent au moins un sous-ensemble non-fréquent.
Chercher les Fk qui ont un bon taux de confiance.
A=lait ; B = Beurre ; C=ThéD = Café ; E = Confiture
s(A→C)=1/3
Cartes de Kohonen (self organizing map)
Origine :o Organisation anatomo-fonctionnelle du cortex
o Tanzi (1893) « l’activation répétée d’un neurone conduit à des modifications métaboliques provoquant le mouvement des prolongements de ce neurone en direction d’autres neurones, de façon à former un lien ». Santiago Ramón y
Cajal (Nobel, 1906)
o Loi de « Hebb » (1949) : renforcement synaptique :Si 2 neurones sont activés simultanément alors leur connexion est renforcée
→ apprentissage
1012 neurones
Cartes de Kohonen
Principe :o Trouver une projection entre l’espace des données (grande
dimension) et l’espace des représentations (petite dimension) qui conserve la « topologie » des données d’entrée : des données proches vont donner des « sorties » proches.
321 321
Apprentissage compétitif
entrée
sortie
« winner-take-all »
données
sortie
Exemple : la réduction de couleurs
TL ouS
ensemble d’apprentissage
RVB
10045
201
indice de proximité
8078
130
Modification de la valeur du représentant et des valeurs des représentants des classes voisines : ils se rapprochent de la donnée présentée. Ainsi c’est toute la région de la carte autour du neurone gagnant qui se spécialise.
données
résultat
Neurone gagnant
Exemple : classification d’images
Cartes de Kohonen Avantages:
o Visualisation facile des cartes de sortie avec des entrées qui sont dans des espaces de grandes dimensions
Inconvénient :o Temps de convergence
o Pas ou peu de preuves mathématiques (convergence)
o Pas d’unicité de la représentation
o Perte de la distance entre les données, remplacée par le « simple » voisinage.
o Choix du voisinage
Choix du voisinage :
Cartes de Kohonen
Super-classes : on peut regrouper les classes d’une carte de Kohonen en super-classes à l’aide d’une classification hiérarchique sur les vecteurs des représentants de chaque classe par exemple.
Super-classes
Distance entre les classes
Recensement de 1783 communes pour 5 dates
Cottrel & Letremy http://samos.univ-paris1.fr/archives/ftp/preprints/samos173.pdf
Méthodes prédictives
Classification : arbres de décision, SVM, …
régression
k plus proches voisins
Classification Définition : étant donné un ensemble d’individus (appelé
ensemble d’apprentissage) répartis en k groupes (appelés classes), il s’agit de définir un modèle (fonction des valeurs d’attributs des individus de l’ensemble d’apprentissage) qui permet d’attribuer chaque nouvel individu à l’une des k classes.
Un ensemble d’individus dont la répartition dans les classes est connue sert à tester le modèle. Il est appelé ensemble test.
Exemples:• Iris de Fischer : 3 classes et 4 attributs
• Prédire si une tumeur est bénigne ou maligne.
• Reconnaissance des visages
setosa versicolor virginica
Nombre de classes connu !
L’œil et le cerveau humain
L’œil et le cerveau humain son extrêmement efficace dans les tache de classification.
Reconnaissance de visages
Reconnaissance en scènes naturelles
Reconnaissance en scènes naturelles
Classification par arbre de décision Principe : méthode basée sur un principe de « diviser pour
régner » pour créer des sous-groupes de plus en plus petits jusqu’à la classification nœud = test sur un attribut
Une branche
= une valeur d’un attribut
Les étiquettes des feuilles
= les étiquettes des classes
Taux d’erreur : proportion d’instances mal classées
Problèmes : choix de l’ordre des attributs, critère de terminaison, …
Exemple [Quinlan,86]
Attention au sur-apprentissage qui produit des modèles mauvais en prédiction (incapacité à généraliser)
Classification par arbre de décision
Souvent plusieurs arbres sont possibles, pour choisir on attribut une valeur à un arbre
→ plusieurs modèles de valeurs possibles
Il est nécessaire de trouver des critères de construction car on ne peut construire tous les arbres possibles (Iris = 55296 arbres possibles)
o On choisit l’attribut le plus informatif et on itère (récursif)
→ Notion d’information et de mesure de l’information
Critère de terminaison :
o Taille de l’arbre,o Nombre d’individus dans les feuilles,o …
Mesure d’entropie de Shannon
Exemple :
)( log)( )(1
2 i
C
ii cpcpSI
p(ci) : probabilité de la classe ci o Nulle quand il n’y a qu’une classeo D’autant plus grande que les classes sont équiprobables : maximal lorsque la distribution est uniforme
Gain d’entropie associé à un attribut A
Gain(S,A) I(S) SvSv valeurs( A)
I(Sv)
A chaque étape dans l’arbre, on choisit l’attribut qui donne le plus grand gain d’information.
Exemple de choix pour le 1er test : outlook
yesyesnonono
yesyesyesyes
yesyesyesnono
sunny overcast rainyGénérer les règles associées aux données Michell 97
I(S) = - 9/14 log2(9/14) - 5/14 log2(5/14) = 0,940
p2 = 2 n2 = 3 : I(p2,n2) = -2/5log2(2/5)-3/5log2(3/5)=0,971p1 = 4 n1 = 0 : I(p1,n1) = -4/4log2(4/4) = 0 (« nœud pur »)p3 = 3 n3 = 2 : I(p3,n3) = -3/5log2(3/5)-2/5log2(2/5)=0,971
Entropie des sous-arbres associés au test Ensoleillement :
2ème exemple avec les iris de Fischer :
Ensemble d’apprentissage : 100 individus pris au hasard dans le fichier Iris
Règles induites uniquement 2 variables utilisées sur 4
Ensemble test : 50 individus pris au hasard dans le fichier Iris privé de l’ensemble d’apprentissage
Taux d’erreur = 2/50 = 4%
Dans un arbre de décision, les frontières des classes sont parallèles aux axes→ difficulté à détecter des combinaisons de variables
Rakotomalala (2005)
Une méthode de l’IA : k-PPV
Principe : à partir d’un ensemble d’apprentissage S, le classifieur fait voter les k plus proches voisins de chaque nouvel individu pour savoir à quelle classe il appartient.
Deux choix cruciaux : o La mesure de similarité entre les individus
o L’algorithme de vote
k-PPV = k plus proches voisins
Avantages / Inconvénients:
o Très simple à mettre en œuvre
o A chaque nouvel individu à classer, il est nécessaire de parcourir tout l’ensemble d’apprentissage.
Diagramme de Voronoi
Cartes de Kohonen (self organizing map)
Origine :o Organisation anatomo-fonctionnelle du cortex
o Tanzi (1893) « l’activation répétée d’un neurone conduit à des modifications métaboliques provoquant le mouvement des prolongements de ce neurone en direction d’autres neurones, de façon à former un lien ». Santiago Ramón y
Cajal (Nobel, 1906)
o Loi de « Hebb » (1949) : renforcement synaptique :Si 2 neurones sont activés simultanément alors leur connexion est renforcée
→ apprentissage
1012 neurones
Cartes de Kohonen
Principe :o Trouver une projection entre l’espace des données (grande
dimension) et l’espace des représentations (petite dimension) qui conserve la « topologie » des données d’entrée : des données proches vont donner des « sorties » proches.
321 321
Apprentissage compétitif
entrée
sortie
« winner-take-all »
données
sortie
Exemple : la réduction de couleurs
TL ouS
ensemble d’apprentissage
RVB
10045
201
indice de proximité
8078
130
Modification de la valeur du représentant et des valeurs des représentants des classes voisines : ils se rapprochent de la donnée présentée. Ainsi c’est toute la région de la carte autour du neurone gagnant qui se spécialise.
données
résultat
Neurone gagnant
Exemple : classification d’images
Cartes de Kohonen Avantages:
o Visualisation facile des cartes de sortie avec des entrées qui sont dans des espaces de grandes dimensions
Inconvénient :o Temps de convergence
o Pas ou peu de preuves mathématiques (convergence)
o Pas d’unicité de la représentation
o Perte de la distance entre les données, remplacée par le « simple » voisinage.
o Choix du voisinage
Choix du voisinage :
Cartes de Kohonen
Super-classes : on peut regrouper les classes d’une carte de Kohonen en super-classes à l’aide d’une classification hiérarchique sur les vecteurs des représentants de chaque classe par exemple.
Super-classes
Distance entre les classes
Recensement de 1783 communes pour 5 dates
Cottrel & Letremy http://samos.univ-paris1.fr/archives/ftp/preprints/samos173.pdf
Support Vector Machine Classifieur linéaire
f x yest
+1
-1
f(x,w,b) = sign(w x + b)
Comment séparer ces données ?
w x +
b=0
w x + b<0
w x + b>0
Support Vector Machine Classifieur linéaire
f x yest
+1
-1
f(x,w,b) = sign(w x + b)
Comment séparer ces données ?
Support Vector Machine Classifieur linéaire
f x yest
+1
-1
f(x,w,b) = sign(w x + b)
Comment séparer ces données ?
Support Vector Machine Classifieur linéaire
f x yest
+1
-1
f(x,w,b) = sign(w x + b)
Comment choisir le bon séparateur ?
Support Vector Machine Classifieur linéaire
f x yest
+1
-1
f(x,w,b) = sign(w x + b)
Classé à tort avec la classe +1
Support Vector Machine Classifieur linéaire
+1
-1
Marge = épaisseur maximale de la frontière sans toucher de points
Support Vector Machine Classifieur linéaire
+1
-1
Vecteurs supports
Classifieur à marge maximale (LSVM)
Support Vector Machine Si les données ne sont pas linéairement séparables
o On peut plonger les données dans un espace de plus grande dimension dans lequel elle deviennent séparables.
0 xx2
Φ: x → φ(x)
Il est toujours possible de trouver un espace assez grand pour que les données deviennent linéairement séparables mais le temps calcul peut devenir trop important
K(xi,xj)= φ(xi) Tφ(xj) Produit scalaire, notion de Noyau
Web mining Définition : application des techniques de data mining au contenu, à
la structure, aux usages (ressources du web).
o Web content mining (sons, images, video, textes) : text mining, …
o Web structure mining
o Web usage mining (navigation, requêtes, créations, …) : fichiers de « log », cookies
Hyperlinks, Blog networks, Social network, …
content structure usages
Web mining Objectifs :
o Optimiser la navigation pour maximiser le confort des internautes, augmenter le nombre de pages consultées (bannières publicitaires), …
o Déceler les centres d’intérêt des internautes,
o …
Fichier de « log »: fichier texte enregistré sur le serveur du site web dans lequel une ligne est écrite à chaque intervention de l’internaute (changement de pages, requête, téléchargement d’une fichier, …)
Source: web-datamining.net
Web mining Deux propriétés communes aux réseaux réels :
o Loi de faible puissance : distribution des degrés, … [Kumar, Barabasi, …]
WWW, graphe des appels téléphoniques, relations proies/prédateurs, …
o Petits mondes [Watts and Strogatz] : la distance entre 2 nœuds reste faible et 2 nœuds qui ont beaucoup de voisins en communs ont une forte probabilité d’être connectés.
Broder el al. (2000)
Pk ~ k-β (β>1)
Newman & Girvan (2003)
Q = 0.65 ± 0.02
FIN
Recommended