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