Introduction au Data Mining

(Fouille de Données)

Dr. A. SIDIBE
Le Data-Mining qu’est-ce que c’est ?
Traduction : Fouille de données.
 Terme récent (1995) représentant un mélange d’idées et d’outils provenant de la
Statistique, l’Intelligence Artificielle et l’Informatique.
 La définition exacte reste peu claire et les terminologies associées au Data-Mining
sont encore floues.
 Une définition suivant un critère égocentré :
Le data-mining est un processus de découverte de règle, relations, corrélations et/ou
dépendances à travers une grande quantité de données, grâce à des méthodes
statistiques, mathématiques et de
reconnaissances de formes.
Autres définitions :
Le data-mining est un processus d’extractions automatique d’informations
predictives à partir de grandes bases de données.
Qu’est-ce que le Data Mining( fouille de données)?

La Fouille de données (découverte de connaissance dans de grandes bases de données):

 Extraction d’information intéressante (non triviale, implicite, non connue
précédemment et potentiellement utile) ou de patterns
 Découverte de connaissance (mining) dans des BDs, extraction de connaissance, analyse
de données/pattern
 Propose des résumés d’information (rapports multidimensionnels, résumés statistiques)
Pourquoi la fouille de données?

 L’explosion des données

Les outils de collecte automatique des données et les bases de données conduisent
àd’énormes masses de données stockées dans des entrepôts
 Submergés par les données, manque de connaissance!
 Solution: Entrepôts de données et fouille de données
Entrepôts de données et analyse on-line
Extraction de la connaissance intéressante (règles, régularités, patterns, contraintes)
àpartir de grandes bases de données
Data-Mining : les raisons du développement

Pourquoi le data mining s’est développé ?

 Intérêt économique : du produit aux clients.
 Technologie de l’information : faible coût de stockage de données, saisie automatique
de transaction (code bar, click, données de localisation GPS, internet)
 Augmentation de la puissance de calculs des ordinateurs (loi de Moore)
⇒ Extraire de la connaissance à partir de grandes bases de données devient possible
 Exemples d’applications
 Entreprise et Relation Clients : système de création de profils clients, ciblage de
clients potentiels et nouveaux marchés
 Finances : minimisation de risque financiers
 Bio-informatique : Analyse du génome, mise au point de médicaments, ...
 Internet : spam, e-commerce, détection d’intrusion etc...
 Sécurité
Data Mining: Un processus de découverte de connaissance
Data Mining: Un processus de découverte de connaissance
De nombreuses personnes considèrent data mining comme un synonyme d'un autre terme couramment utilisé,
découverte de connaissances à partir de données, ou KDD, tandis que d'autres considèrent data mining comme une étape
essentielle du processus de découverte de connaissances. Le processus de découverte des connaissances est illustré à la
figure suivante sous la forme d'une séquence itérative des étapes suivantes :
Data Mining: Un processus de découverte de connaissance
 Les étapes du processus de découverte des connaissances
1. Nettoyage des données (pour éliminer le bruit et les données incohérentes)
2. Intégration des données (lorsque plusieurs sources de données peuvent être combinées) Une tendance
populaire dans le secteur de l’information consiste à effectuer le nettoyage et l’intégration des données
comme une étape de prétraitement, où les données résultantes sont stockées dans un entrepôt de données.
3. Sélection des données (où les données pertinentes pour la tâche d'analyse sont extraites de la base de
données)
4. Transformation de données (où les données sont transformées et consolidées sous des formes appropriées à
l'extraction en effectuant des opérations de synthèse ou d'agrégation). Parfois, la transformation et la
consolidation des données sont effectuées avant le processus de sélection des données, en particulier dans le
cas de l'entreposage de données. La réduction des données peut également être effectuée pour obtenir une
représentation plus petite des données d'origine sans sacrifier leur intégrité.
5. Data mining (un processus essentiel où des méthodes intelligentes sont appliquées pour extraire des modèles
de données)
6. Évaluation des modèles (pour identifier les modèles(patterns) vraiment intéressants représentant des
connaissances sur la base de mesures d'intéressement - voir la section 1.4.6)
7. Présentation des connaissances (où des techniques de visualisation et de représentation des connaissances
sont utilisées pour présenter les connaissances extraites aux utilisateurs)
 Les Etapes du Processus de Découverte des Connaissances
Les étapes 1 à 4 sont différentes formes de prétraitement des données, ou les données sont destinées à la
fouille. L'étape de la fouille donnée peut interagir avec l'utilisateur ou une base de connaissances. Les
modèles intéressants sont présentés à l'utilisateur et peuvent être stockés en tant que nouvelles
connaissances dans la base de connaissances.
La vue précédente présente la fouille de données comme une étape du processus de découverte des
connaissances, bien qu’elle est essentiel car elle révèle des modèles cachés d’évaluation. Cependant, dans
l'industrie, dans les médias et dans le milieu de la recherche, le terme fouille de données est souvent
utilisé pour désigner l'ensemble du processus de découverte des connaissances (peut-être parce que le
terme est plus court que la découverte des connaissances à partir de données).
Par conséquent, nous adoptons une vision large des fonctionnalités de fouille de données : La fouille de
données consiste à découvrir des modèles(patterns) et des connaissances intéressants à partir de
grandes quantités de données. Les sources de données peuvent inclure des bases de données, des
entrepôts de données, le Web, d'autres référentiels d'informations ou des données transmises en
continu dans le système.
Etapes d’un Processus de Découverte de Connaissance
1. Connaître le domaine d’application
Connaissance pertinente déjà établie et buts de l’application
2. Sélection des données cibles
3. Data cleaning, prétraitement
4. Réduction de données et transformation
5. Choix des fonctions du data mining
Synthèse, résumé, classification, régression, association, clustering.
6. Choix des algorithmes de fouille
7. Data mining
Recherche des modèles intéressants
8. Evaluation des pattern et présentation de la connaissance
Visualisation, transformation, etc.
9. Utilisation de la connaissance
Mise en œuvre d’un projet d’un projet de DM

1. Comprendre et analyser les objectifs de l’application

2. Créer une base de données pour la mise au point de l’application.
3. Prétraitement et nettoyage des données
4. Analyse statistique des données (réduction de la dimension, projection, etc...)
5. Identifier le type de problèmes ( discrimination, clustering, etc...) et choisir un
algorithme.
6. Evaluer les performances de l’algorithme.
7. Réitérer les étapes précédentes si nécessaire.
8. Déployer l’application.
Fouille de données: Sur quel type de données?

 Bases de données relationnelles

 Data warehouses / entrepôts de données
 Réservoir de données
 Orientées Objet
 Bases de données spatiales
 Données chronologiques et données temporelles
 Bases textuelles et multimédia
 WWW
 Intérêt des modèles (patterns) découverts
Un système de data mining génère des milliers de patterns, tous ne sont pas
intéressants.
 Intérêt
Un pattern est intéressant si il est
facilement compris par les humains,
valide sur données nouvelles ou testées avec un certain degré de certitude,
potentiellement utile,
nouveau, ou validant certaines hypothèses que l’on cherche à confirmer
 Objectif vs. subjectif
 Objectif: basé sur des statistiques et des structures de patterns
 Subjectif: basé sur des croyances des utilisateurs
La Fouille de Données
La Fouille de Données

 Bases de données à fouiller

Relationnelles, transactionnelles, orientées objet, spatiales, séries chronologiques,
textuelles, multi-media, WWW, etc.
 Connaissance à fouiller
Caractérisation, discrimination, association, classification, déviation et analyse des outliers
 Techniques utilisées
Bases de données, data warehouse (OLAP), machine learning, statistiques, visualisation,
réseaux de neurones.
Exemples d’Applications : E-commerce
Dell
 Problème : 50% des clients de Dell achètent leurs machines à travers le site Web. Mais
seulement 0.5% des visiteurs du site deviennent clients.
 Solution : Stocker les séquences de clicks des visiteurs, analyser les caractéristiques des
acheteurs et lors de la visite d’un client potentiel, adapter le contenu du site pour maximiser
la probabilité d’un achat.
Amazon
 Opportunité : la liste des achats des clients est stockée en mémoire et par ailleurs, les
utilisateurs du site notent les produits ! Comment tirer profit des choix d’un utilisateur pour
proposer des produits à un autre client ?
 Solutions : technique dit de filtrage collaboratif permettant de regrouper des clients ayant les
mêmes “goûts”
 Exemples d’applications : Analyse des risques

Détection de fraudes pour les assurances

 Analyse des déclarations des assurés par un expert afin d’identifier les cas de fraudes.
 Extraction de caractéristiques à partir de ces déclarations (type d’accident, de blessures, etc...)
 Applications de méthodes statistiques pour identifier les caractéristiques des déclarations fortement corrélées à
la fraude.

Prêt Bancaire
 Objectif des banques : réduire le risque des prêts bancaires.
 Créer un modèle à partir de caractéristiques des clients pour discriminer les clients à risque
des autres.
Exemples d’applications : Commerce

Organisation de rayonnage
 Objectifs : Identifier les produits que les gens sont susceptibles d’acheter conjointement afin
d’organiser les rayonnages
 Données : Code-Barre des produits.
 Méthodes : Extractions de règles d’association
 Exemples :
 résultats logiques : les boissons alcoolisées et les biscuits apéritifs sont souvent proches.
 résultats étranges : dans une étude américaine, la vente de bière est plus importante si le rayon des
couches n’est pas trop loin, et si sur le chemin il y a des chips, cela permet d’augmenter la vente des 3
produits.
 Les Mesures de Distance
Définition d'une mesure de distance
Supposons que nous ayons un ensemble de points, appelé espace. Une mesure de distance sur cet espace est une
fonction d(x, y) qui prend deux points dans l'espace comme arguments et produit un nombre réel, et satisfait les
axiomes suivants :

1. d(x, y) ≥ 0 (pas de distances négatives).

2. d(x, y) = 0 si et seulement si x = y (les distances sont positives, sauf pour la distance d'un point à lui-même).

3. d(x, y) = d(y, x) (la distance est symétrique).

4. d(x, y) ≤ d(x, z) + d(z, y) (l'inégalité triangulaire).

L'inégalité triangulaire est la condition la plus complexe. Il dit, intuitivement, que pour voyager de x à y, nous
ne pouvons obtenir aucun avantage si nous sommes obligés de passer par un troisième point particulier z.
L'axiome d'inégalité triangulaire est ce qui fait que toutes les mesures de distance se comportent comme si la
distance décrivait la longueur d'un chemin le plus court d'un point à un autre.
Distances Euclidiennes
La mesure de distance la plus familière est celle que nous appelons normalement « distance ». Un espace
euclidien à n dimensions est un espace où les points sont des vecteurs de n nombres réels. La mesure de
distance conventionnelle dans cet espace, que nous appellerons la norme L2, est définie :

Similarité des ensembles Jaccard

La similarité de Jaccard des ensembles S et T est |S∩T|/|S∪T|, c'est-à-dire le rapport de la taille de
l'intersection de S et T à la taille de leur union. On notera la similitude Jaccard de S et T par SIM(S, T).
|𝑺 ∩𝑻 |
𝑺𝑰𝑴 ( 𝑺 ,𝑻 ) =
|𝑺 ∪𝑻 |
Distance Jaccard
La distance Jaccard des ensembles est d(x, y) = 1 − SIM(x, y). C'est-à-dire que la distance Jaccard est de 1 moins le rapport
des tailles de l'intersection et de l'union des ensembles x et y. Il faut vérifier que cette fonction est une mesure de distance.
Distance en cosinus
La distance en cosinus entre deux points est l'angle que font les vecteurs de ces points. Cet angle sera compris
entre 0 et 180 degrés, quel que soit le nombre de dimensions de l'espace. On peut calculer la distance du cosinus
en calculant d'abord le cosinus de l'angle, puis en appliquant la fonction arc-cosinus pour traduire en un angle
compris entre 0 et 180 degrés. Étant donné deux vecteurs x et y, le cosinus de l'angle entre eux est le produit
scalaire x. y divisé par les normes L2 de x et y (c'est-à-dire leurs distances euclidiennes à partir de l'origine).

La Distance Edit
Cette distance a un sens lorsque les points sont des chaînes. La distance entre deux chaînes et est le plus petit
nombre d'insertions et de suppressions de caractères uniques qui convertiront x en y.
Example : The edit distance between the strings x = abcde and y = acfdeg is 3. To convert x to y:
1. Delete b.
2. Insert f after c.
3. Insert g after e.
No sequence of fewer than three insertions and/or deletions will convert x to y.
Thus, d(x, y) = 3.
Distance de Hamming

Étant donné un espace de vecteurs, nous définissons la distance de Hamming entre deux vecteurs comme le nombre de
composants dans lesquels ils diffèrent. Le plus souvent, la distance de Hamming est utilisée lorsque les vecteurs sont
booléens ; ils se composent uniquement de 0 et de 1. Cependant, en principe, les vecteurs peuvent avoir des composantes de
n'importe quel ensemble.
Clustering (Segmentation)
La Problématique du Clustering
 Soient N instances de données à k attributs,
 Trouver un partitionnement en c clusters (groupes) ayant un sens
(Similitude)
 Affectation automatique de “labels” aux clusters
 c peut être donné, ou “découvert”
 Plus difficile que la classification car les classes ne sont pas connues
à l’avance (non supervisé)
 Attributs
 Numériques (distance bien définie)
 Enumératifs ou mixtes (distance difficile à définir)
Qualité d’un Clustering

 Une bonne méthode de clustering produira des clusters d’excellente qualité avec :
 Similarité intra classe importante
 Similarité inter classe faible
 La qualité d’un clustering dépend de :
 La mesure de similarité utilisée
 L’implémentation de la mesure de similarité
 La qualité d’une méthode de clustering est évaluée par son abilité à découvrir certains
ou tous les “patterns” cachés.
Les Objectifs du Clustering
Exemples d’Applications du Clustering
 Marketing: segmentation du marché en découvrant des groupes de clients distincts à
partir de bases de données d’achats.
 Environnement: identification des zones terrestres similaires(en termes d’utilisation)
dans une base de données d’observation de la terre.
 Assurance: identification de groupes d’assurés distincts associés à un nombre important
de déclarations.
 Planification de villes: identification de groupes d’habitations suivant le type
d’habitation, valeur, localisation géographique, …
 Médecine: Localisation de tumeurs dans le cerveau
 Nuage de points du cerveau fournis par le neurologue
 Identification des points définissant une tumeur
Exemple: Segmentation de Marchés
Mesure de la similarité

 Il n’y a pas de définition unique de la similarité entre objets

 Différentes mesures de distances d(x,y)

 La définition de la similarité entre objets dépend de :

1) Le type des données considérées
2) Le type de similarité recherchée
Choix de la distance
 Propriétés d’une distance:

 Définir une distance sur chacun des champs

• Champs numériques:
d(x,y) = |x-y|,
d(x,y)= |x-y|/dmax (distance normalisée)
• Exemple: Age, taille, poids, …
Distance – Données numériques

 Combiner les distances : Soient x = (x1,…,xn) et y = (y1, …,yn)

 Exemples numériques :

• Si q =1 : La Distance de Minkowski est égale à la distance de Manhattan.

• Si q =2 : La Distance de Minkowski est égale à la distance euclidienne
Choix de la distance

 Champs discrets:

o Données binaires: d(0,0) = d(1,1) = 0, d(0,1) = d(1,0)=1

o Donnée énumératives: distance nulle si les valeurs sont égales et 1 sinon.

o Donnée énumératives ordonnées: idem. On peut définir une distance

utilisant la relation d’ordre.

o Données de types complexes: textes, images, données génétiques, ...

Méthodes de Clustering

 Méthodes hiérarchiques(par agglomération)

 Méthode de partitionnement(K-moyennes)

 Méthode par voisinage dense

 Caractéristiques
 Apprentissage non supervisé (classes inconnues)
 Pb: interprétation des clusters identifiés
Méthodes de Clustering-Caractéristiques

 Extensibilité

 Habilité à traiter différents types de données

 Découverte de clusters de différents formes

 Connaissances requises (paramètres de l’algorithme)

 Habilité à traiter les données bruitées et isolées l’algorithme)

isolées.
Algorithme des k-moyennes (K-means)
Algorithme des k-moyennes (K-means)
Illustration de Algorithme des k-moyennes (K-means)
 Les Avantages de K-moyennes

 Relativement extensible dans le traitement d’ensembles de taille

importante.
 Relativement efficace : O(t*k*n), où n représente le nombre d’ objets, k - le
nombre de clusters, et t - le nombre d’itérations. Normalement, k, t<< n.
 Produit généralement un optimum local; un optimum global peut être
obtenu en utilisant d’autres techniques telles que: algorithmes génétiques, …
 Les Inconvénients de K-means

 Applicable seulement dans le cas où la moyenne des objets est définie

 Besoin de de spécifier k, le nombre de clusters, a priori
 Incapable de traiter les données bruitées (noisy).
 Non adapté pour découvrir des clusters avec structures non-convexes, et
des clusters de tailles différentes
 Les points isolés sont mal gérés (doivent-ils appartenir obligatoirement à
un cluster ?) -probabiliste
Méthodes Hiérarchiques

 Une méthode hiérarchique construit une hiérarchie clusters, non

seulement une partition unique des objets.
 Le nombre de clusters k n’est pas exigé comme donnée
 Utilise une matrice de distances comme critère de clustering
 Une condition de terminaison peut être utilisée (ex. Nombre de clusters)
Méthodes Hiérarchiques
Méthodes Hiérarchiques
Arbre de clusters : Exemple
Arbre de clusters
 Résultat: Graphe hiérarchique qui peut être coupé à un niveau de
dissimilarité pour former une partition.

 La hiérarchie de clusters est représentée comme un arbre de

clusters, appelé dendrogramme
 Les feuilles de l’arbre représentent les objets
 Les nœuds intermédiaires de l’arbre représentent les clusters
dendrogramme
Distance entre clusters
Les Avantages Des Méthodes hiérarchiques
Inconvénients Des Méthodes hiérarchiques