Fouille de Données

Processus ECD, fouille de motifs, clustering

Motivations

• Développement des TICs

• Gestion et collection de très grands volumes de données

Quelles sont Associations entre

les fraudes ? produits? Quel type
d’étoile?

Relations entre
gènes?
Motivations

• Développement des TICs

• Gestion et collection de très grands volumes de données

De telles
Quelles sont Associations entre analyses sont
les fraudes ? produits? impossibles Quel type
manuellementd’étoile?
!!!

Relations entre
gènes?
Motivations

• Développement des TICs

• Gestion et collection de très grands volumes de données

De telles
Quelles sont Associations entre analyses sont
les fraudes ? produits? impossibles Quel type
manuellementd’étoile?
!!!

Merci Fouille
de données !!!
Relations entre
gènes?
Evolution des sciences
• Avant 1600 : science empirique

• 1600-1950 : science théorique

• Années 50 - Années 90 : «Computational science»

• Depuis plus de 50 ans, beaucoup de disciplines se sont développées sur une 3ème branche - le calcul - comme
en physique, ....

• Simulation : trouver des modèles proches de la réalité

• 1990 - Aujourd’hui : «data science»

• Données omniprésentes (nouveaux instruments, simulations)

• capacité à gérer et stocker des volumes gigantesques.

• Internet

• La fouille de données est devenu un challenge majeur !!!

Knowlege Discovery from Database (KDD)
• KDD (Extraction de Connaissances à partir des Données) est un processus (semi)- automatique
d’extraction de connaissances à partir de bases de données où les connaissances sont :

• valides

• non connues a priori

• potentiellement utiles [Fayad et al., 96]

• Remarques :

• semi-automatique : différent d’une analyse manuelle mais souvent une interaction avec un
utilisateur est nécessaire

• non connues a priori : pas des tautologies.

• potentiellement utiles : pour une application donnée

Le processus KDD

Focus Pré- Transfor Data

sur l’appli. traitement Evaluation
mation Mining

Bases de Motifs/Modèle Connaissance

données

Processus itératif et interactif

«Focussing»
• Comprendre l’application

• Ex. : Etablir une nouvelle tarification.

• Définir l’objectif KDD

Exemple
• Ex. : Etablir des «profils de consommateurs»
d’application
• Acquisition des données

• Ex. : Bases de données des factures

• Gestion des données

• Système de fichiers ou SGBD ?

• Sélection des données pertinentes

• Ex. : considérer les 100 000 clients les plus importants et tous leurs appels sur l’année 2009
Pré-traitement
• Intégration des données à partir de différentes sources

• Conversion des noms d’attributs (CNo -> CustomerNumber)

• Utilisation de la connaissance du domaine pour détecter les doublons (e.g., utiliser les codes postaux)

• Vérifier la cohérence des données :

• des contraintes spécifiques à l’application

• Résolution des incohérences

• «Completion»

• Le cas des valeurs manquantes

• Le pré-traitement des données est souvent la tâche la plus coûteuse dans le processus KDD!
Pré-traitement

• Entrepôts de données

• persistant

• Intégration de données issues de plusieurs sources

• Dans un but d’analyse ou de prise de décision

Datawarehouse Report
operational DBs Generator
Integrate
Load serves OLAP
Update

Data Mining

figure provenant de M. Ester

Transformation
• Discrétisation des attributs numériques

• Indépendamment de la tâche de fouille de données

• Ex. : partitionner le domaine des attributs en des intervalles de même longueur.

• Spécifique de la tâche de fouille de données

• Partitionner en des intervalles qui maximisent le gain d’information par rapport à la classe

• Génération d’attributs dérivés :

• Agrégation d’un ensembles d’attributs

• Ex. : à partir d’appels

• nb minutes par jour, semaine, appels locaux ...

• Combinaison d’attributs :

• Ex. : variation de revenu (revenu 2009 - revenu 2008)

Transformation

• Sélection des attributs

• manuellement : Si les connaissances du domaine sont disponibles pour

les attributs.

• de façon automatique :

• Trop d’attributs -> des répercussions sur l’étape de fouille de données

• Choix des attributs primordial :

• Ex. : glace à la fraise

Data Mining

• Définition [Fayad et al. 96]

• La fouille de données est l’application d’algorithmes efficaces qui identifient les

motifs contenus dans une base de données

• Les différentes tâches de fouille :

b
• •• • • •• • aa b b ab
• • • a bb
• a a
•
clustering classification
A and B  C
association rules

• Autres tâches : regression, détection d’outlier, etc.

Data Mining

• Applications

• Clustering

• Segmentation, structuration d’un ensemble de documents «web», déterminer

des familles de protéines et des «super-familles», découvertes de communautés

• Classification :

• prédiction de la fonction d’une protéine, accorder un crédit, interpréter des

images en astronomie, etc.

• Règles d’association :

• mise en rayon, promotion, améliorer la structure d’un site web ...

Evaluation
• Présentation des motifs découverts avec une visualisation appropriée

• Evaluation des motifs par l’utilisateur

• Si l’évaluation n’est pas satisfaisante, alors relancer la fouille avec :

• des paramètres différents

• d’autres méthodes

• d’autres données

• Si l’évaluation est positive :

• Intégrer les connaissances découvertes dans une base de connaissance

• Utiliser ces connaissances dans les futures processus KDD

Evaluation

• Intérêt des motifs découverts :

• motifs déjà connus ?

• motifs surprenants ?

• motifs pertinents par rapport à l’application ?

• Pouvoir prédictif

• Quel est la précision du motif ?

• Dans combien de cas se produit il ?

• Peut-il se généraliser à d’autres cas non couverts ?

Données, information, connaissance
Data Mining ou non ?

• Recherche le salaire l’employé • Regrouper un ensemble de

Dupont documents retourner par un moteur
de recherche en fonction de leur
contenu

• Les personnes qui réalise l’action A

• Interroger un moteur de recherche
réalise dans le mois qui suit l’action
pour avoir des informations sur le
B
data mining
Applications KDD : Astronomie

• SKICAT System [Fayad et al 1996]

• Architecture

Removal of noise

Image segmentation

Manual analysis classification Feature extraction

• Méthode de classification : arbre de décision

• Evaluation :

• beaucoup plus rapide qu’une classification manuelle

• Classifie aussi des objets célestes très petits

Applications KDD : Marketing

• Customer segmentation [Piatetsky-Shapiro et al 2000]

• But : partitionner les consommateurs par rapport à leurs achats

• Motivation :

• product packages

• établir une nouvelle politique tarifaire

Applications KDD : Commerce électronique
Applications KDD : puces ADN
Le data mining au centre du processus KDD

Patte
Data Post- Inform rn
a
Know tion
Input Data Data Pre-
Processing Mining Processing
ledge

Data integration Pattern discovery Pattern evaluation

Normalization Association & correlation Pattern selection
Feature selection Classification Pattern interpretation
Dimension reduction Clustering Pattern visualization
Outlier analysis
…………
Data mining : à la confluence de nombreuses
disciplines

Machine Pattern Statistics

Learning Recognition

Applications Data Mining Visualization

Algorithm Database High-Performance

Technology Computing
Plan du cours

• Fouille de motifs (MP)

• Règle d’association, algorithme Apriori

• Fouille de séquences

• Fouille sous contraintes

• Autres types de motifs et données

• Clustering (MP)

• Apprentissage supervisé (AA)

Motifs ensemblistes et règles d’association
 Introduction
Motivations : chercher des régularités dans les données
Base de données de
transactions
beurre, lait, vin
oeufs, farine, coca
....
couches, bières, lait

• Analyse du «panier de la ménagère»

• Quels sont les produits qui sont fréquemment achetés ensembles ?

• Applications : rayonnage, mailing, cross marketing ...

Règles d’association

• Forme :

• Corps -> Tête [support, confiance]

• Exemples :

• couches -> bières [0.5, 0.7]

Achat
des 2.
• 98% des personnes qui achètent
des pneus, prennent l’option
montage.

Achat Achat
bières couches
Les règles d’association (plus formellement)

• Soit I = {i1,i2,..., in} un ensemble de littéraux appelés items.

• Un itemset X : un ensemble d’items X ⊆ I

• Une base de données D consiste en un ensemble de transactions Ti t.q. Ti ⊆ I

• On dit que T contient X si X ⊆ T

• Les items d’une transaction ou d’un itemset sont triés suivant un ordre
lexigographique

• Longueur d’un itemset = nombre d’items qu’il contient

• k-itemset : itemset de longueur k

Définitions

• Support absolu d’un itemset X dans D : nombre de transactions qui contiennent X

• Support relatif de X dans D : pourcentage de transactions de D qui contiennent X

• Itemset fréquent X dans D : itemset X avec un support ≥ minsup

• Règle d’association : règle de la forme X -> Y avec

• X ⊆ I,

• Y⊆I,

• X∩Y=∅
 Définitions
• Support d’une règle d’association X->Y dans D :

• support de X U Y dans D

• Confiance d’une règle d’association X->Y dans D :

• pourcentage de transactions contenant Y qui contiennent aussi X

• Objectif : Etant donné un seuil de support minsup et un seuil de confiance

mincong, découvrir toutes les règles d’association qui ont un support ≥ minsup
et une confiance ≥ minconf
Exemple

minsup = 50%,
minconf = 50%

Support
(A): 75%, (B), (C): 50%, (D), (E), (F): 25%,
(A, C): 50%, (A, B), (A, D), (B, C), (B, E), (B, F), (E, F): 25%
Règles d’association
A ⇒ C (support = 50%, confidence = 66.6%)
C ⇒ A (support = 50%, confidence = 100%)
Découverte des règles d’association

• Deux étapes :

• Découvrir tous les itemsets fréquents dans D

• Générer les règles d’association à partir des itemsets fréquents :

• Pour tous les itemsets fréquents X :

• Pour tous les A ⊂ X : (qui satisfait la contrainte de support)

• Générer la règle A ⇒ (X − A) (qui satisfait la contrainte de support)

• Verifier la confiance de la règle

Extraction des motifs fréquents (approche naïve)

• Générer tous les itemsets possibles, puis calculer leur support dans la base
de données

• Problèmes :

• Comment garder en mémoire un nombre important d’itemsets ?

• 100 items => 2100 -1 itemsets possibles !!!!

• Comment calculer le support d’un nombre important d’itemsets dans une

grande base de données (100 million de transactions) ?
Extraction des motifs fréquents (approche naïve)

• Générer tous les itemsets possibles, puis calculer leur support dans la base
de données

• Problèmes :

Approche
• Comment garder en mémoire un nombre important d’itemsets ? naïve
non viable !!!
• 100 items => 2100 -1 itemsets possibles !!!!

• Comment calculer le support d’un nombre important d’itemsets dans une

grande base de données (100 million de transactions) ?
Extraction des motifs fréquents

• Propriété d’ anti-monotonie du support :

• Tous les sous ensembles d’un itemset fréquent sont fréquents

• Si un itemset X n’est pas fréquent alors il n’existe pas d’itemset Y t.q X C

Y qui soit fréquent
Méthode

• Trouver les 1-itemsets fréquents, puis trouver les 2-itemsets fréquents ....

• Pour trouver les k+1-itemsets fréquents :

• Seulement considérer les k+1-itemsets t.q. :

• tous les k-sous-ensembles sont fréquents.

• Calcul du support :

• Une passe sur la base de données pour compter le support de tous les
itemsets pertinents.
Algorithme Apriori
Ck: set of candidate item sets of length k
Lk: set of all frequent item sets of length k

Apriori(D, minsup)
L1 := {frequent 1-item sets in D};
k := 2;
while Lk-1 ≠ ∅ do
Ck := AprioriCandidateGeneration(Lk − 1);
for each transaction T ∈ D do
CT := subset(Ck, T); // all candidates from Ck, that are
// contained in transaction T;
for each candidate c ∈ CT do c.count++;
Lk := {c ∈ Ck | (c.count / |D|) ≥ minsup};
k++;
return ∪k Lk;
Génération de candidats

• Propriétés de l’ensemble Ck des k-itemsets candidats

• Sur-ensemble de Lk

• Significativement plus petit que tous k-itemsets possibles de I

Génération de candidats : la jointure

• Etape 1:

• p et q : (k-1) itemsets fréquents

• p et q sont joints si ils ont leurs (k-2) premières valeurs identiques

• Ex. :

• p= (A B C)
(A B C D)
• q= (A B D)
C4
L3
Génération de candidats : élagage

• Etape 2 : l’élagage

• Supprimer tous les éléments de Ck qui ont un (k-1) sous-ensemble qui

n’appartient pas à Lk-1.

• Ex. : L3 = {(1 2 3), (1 2 4), (1 3 4), (1 3 5), (2 3 4)}

Jointure : C4 = {(1 2 3 4), (1 3 4 5)}

Elagage: suppression de (1 3 4 5) car (3 4 5) n’appartient pas à L3

Au final : C4 = {(1 2 3 4)}

Exemple d’une extraction complète
Au tableau avec un
treillis et tout l’espace
de recherche.
Exemple d’une extraction complète
Au tableau avec un
treillis et tout l’espace
de recherche.
minsup = 2
Exemple d’une extraction complète
Au tableau avec un
treillis et tout l’espace
de recherche.
minsup = 2
C1

Scan D
Exemple d’une extraction complète
Au tableau avec un
treillis et tout l’espace
de recherche.
minsup = 2
C1 L1

Scan D
Exemple d’une extraction complète
Au tableau avec un
treillis et tout l’espace
de recherche.
minsup = 2
C1 L1

Scan D

C2
Exemple d’une extraction complète
Au tableau avec un
treillis et tout l’espace
de recherche.
minsup = 2
C1 L1

Scan D

C2 C2

Scan D
Exemple d’une extraction complète
Au tableau avec un
treillis et tout l’espace
de recherche.
minsup = 2
C1 L1

Scan D

L2 C2 C2

Scan D
Exemple d’une extraction complète
Au tableau avec un
treillis et tout l’espace
de recherche.
minsup = 2
C1 L1

Scan D

L2 C2 C2

Scan D

C3
Exemple d’une extraction complète
Au tableau avec un
treillis et tout l’espace
de recherche.
minsup = 2
C1 L1

Scan D

L2 C2 C2

Scan D

C3 L3
Scan D
 Espace de recherche (suite au tableau)
12345

1234 1235 1245 2345

123 124 125 234 235 345

12 13 14 15 23 24 25 34 35 45

1 2 3 4 5

Ø
Calcul du support efficace

•Subset(Ck,T)
Tous les candidats de Ck qui sont contenus dans la transaction T
• Problèmes :
– Très grand nombres d’itemsets candidats
– Une transaction peut contenir un très grand nombre de candidats
• Structure de données Hash tree pour stocker Ck
Génération des règles à partir des itemsets

• Pseudo-code :

• Pour chaque itemset fréquent l :

• Générer tous les sous-ensembles non vides X de l

• Pour chaque X de l :

• Si support(l)/support(X) ≥ minconf alors

• produire la règle X => (l-X)

Exercice

• Voir feuille de «TD»

• Extraction de motifs fréquents

• Propriétés d’Apriori

• Bordures

• Règles d’association

• Propriétés

• ...
Visualisation des règles : dans un plan
Graphe de règles
Différentes mesures
Règles d’association multi-niveaux

• Dans de nombreuses applications, des hiérarchies sont associées aux items.

Clothes Shoes

Outerwear Underwear Walking-Shoes Hiking boots

Jackets Trousers

• Recherche des R.A sur les feuilles : support risque d’être trop bas.

• Recherche des R.A aux niveaux supérieurs : motifs risquent de représenter

des informations déjà connues.

• Il faut donc chercher des R.A sur tous les niveaux.

Exemple

Anorak Hiking boots

Support < minsup
Windcheater Hiking boots
Jacket Hiking boots Support > minsup

Propriétés :
• Support (Jacket Hiking boots) peut être différent de
support(Anorak Hiking boots) + support(Windcheater Hiking
boots)
• Si support(Jacket Hiking boots) > minsup, alors
support(Outerwear Hiking boots) > minsup
Règles d’association multi-niveaux [Agrawal et
Srikant, 1995]

• I = {i1, ..., im} un ensemble de littéraux (items)

• H un graphe orienté sans cycle (DAG) sur I

• Dans H, une arête de i vers j si :

• i est une généralisation de j,

• i est le père (prédécesseur direct) de j, j est un fils ou successeur direct

• Plus généralement, X prédécesseur de X s’il existe un chemin entre X et X dans H

• itemset Z est un prédécesseur d’un itemset Z : pour tout item de Z, on a au moins un pred
dans Z
• D est un ensemble de transactions T où T ⊆ I

• Généralement, une transaction de D contient uniquement des items qui sont

feuilles dans H

• Une transaction T supporte un item i si :

• i ∈ T ou i est un prédécesseur d’un item j de T

• T supporte un itemset X si tous les items de I sont supportés par T

• ex. : (coca, chips) supporte (soda, chips)

• Support(X,D) = % de transaction de D supportant X

• Règle d’association multi-niveaux :

• X Y où X ⊆ I, Y ⊆ I, X ∩ Y = ∅ et aucun item de Y n’est prédécesseur

d’un item de X dans H;

• Support(X Y,D) = support(X U Y, D)

• Confiance
Exemple

• Support(Jackets): 4/6 = 67%

• Support(Jackets, Hiking boots): 2/6 = 33%

• Hiking-boots Jackets : Support 33%, Confiance 100%

• Jackets Hiking-boots : Support 33%, Confiance 50%

Déterminer les itemsets fréquents

• Idée originale (algorithme basique) :

• Etendre la base de données avec tous les prédécesseurs des items

contenus dans chaque transaction;

• ex: T1: (coca,vin) =>T1’:(coca,soda,vin, alcool, boissons ...)

• Ne pas insérer de duplications !

• Ensuite, rechercher les itemsets fréquents (APriori);

• Optimisations : filtrage des prédécesseurs à ajouter, matérialisation des

prédécesseurs.
• Suppression des itemsets redondants

•Soit X un k-itemset, i un item et i’ un prédécesseur de i.

•X=(i,i’,...)
• Support de X − {i’} = support de X
• X ne doit pas être considérer pendant la génération de candidats
• On n’a pas besoin de compter le support d’un k-itemset qui contient l’item i
et son prédécesseur i’
•Algorithme Cumulate
Stratification

• Alternative à Apriori

• former des couches dans l’ensemble de candidats

• Propriété : si un itemset X n’est pas fréquent alors X non plus.

• Méthode :

• Ne pas compter le support tous les k-itemsets en même temps

• Compter en premier le support des itemsets les plus généraux et ensuite

considérer le calcul des plus spécifiques si nécéssaire.
Exemple

• Ck = {(Clothes Shoes), (Outerwear Shoes), (Jackets Shoes)}

• regarder d’abord (Clothes Shoes)

• compter ensuite le support de (Outerwear Shoes) uniquement si

nécessaire

Notations
• Depth d’un itemset

• (Ckn): Set of item sets from Ck with depth n, 0 ≤ n ≤ maximal depth t

Algorithme Stratify

• Au tableau à partir d’un exemple simple.

• Représentation de l’espace de recherche («treillis déformé»)

Intérêt des règles d’association multi-niveaux

• est un prédécesseur de

• Une règle d’association multi-niveaux est R-intéressante si :

• Elle n’a pas de prédécesseur direct ou

• Support (ou confiance) est R fois supérieur au support (confiance)

attendue et que le prédécesseur direct est aussi R-intéressant.
Exemple

R=2

• Rule-No Rule Support R-interesting ?

1 Clothes ⇒ Shoes 10 yes, no predecessor

2 Outerwear ⇒ Shoes 9 yes, support ≈ R * expected
support (w.r.t. rule 1)
3 Jackets ⇒ Shoes 4 no, support < R * expected
support (w.r.t. rule 2)
Choix du support

Outerwear
Fix support minsup = 5 %
Support = 10 %

Jackets Trousers
minsup = 5 %
Support = 6 % Support = 4 %

Variable support Outerwear

minsup = 5 %
Support = 10 %

Jackets Trousers minsup = 3 %

Support = 6 % Support = 4 %
Discussion

• Support fixe (même minsup pour tous les niveaux de H)

• + : efficacité (suppression des successeurs non fréquents

• - : réduit l’intérêt des règles

• minsup trop haut : pas de règles de bas niveau

• minsup trop bas : trop de règles de haut niveau

• Support variable :

• + : Intérêt : on trouve des règles aux niveaux appropriés

• - : efficacité de l’extraction (pas de pruning des successeurs directs)

Règles multidimensionnelles

• Règle mono-dimensionnelle :
•buys(X, “milk”) buys(X, “bread”)
• Règle multidimensionnelle : ≥ 2 dimensions ou predicats
• RA Inter-dimension (pas de prédicats répétés)
•age(X,”19-25”) ∧ occupation(X,“student”) buys(X, “coke”)

• RA hybrides (prédicats répétés)

•age(X,”19-25”) ∧ buys(X, “popcorn”) buys(X, “coke”)

• Attributs catégoriels : Nombre finis de valeurs possibles, pas d’ordres parmi les
valeurs — approche cube de données
• Attributs quantitatifs : Numérique, ordre implicite parmi les valeurs— discrétisation,
clustering, ...
Autres applications de la recherche de motifs
ensemblistes : les icebergs
Amélioration de l’algorithme Apriori
Rappel
Les enjeux et les idées à développer

• Multiples passages sur la base de données

• Ensemble de candidats très importants

• Calcul du support d’un motif

• Réduire le nombre de passages sur la base de données

• Réduire le nombre de candidats

• Faciliter le calcul du support

 DIC : réduction du nombre de passage

• Dès que A et D sont déterminés comme

fréquents, on peut commencer à calculer
le support de (AD)

• Dès que les 2-sous-ensembles de (BCD)

sont trouvés fréquents alors on peut
commencer à chercher le support de
(BCD)

S. Brin R. Motwani, J. Ullman,

and S. Tsur, SIGMOD’97.
DIC: Dynamic Itemset Counting
DHP : Réduction du nombre de candidats

• A hashing bucket count < min_sup␣every candidate in the bucket is

infrequent

• Candidats: a, b, c, d, e

• Hash entrées: {ab, ad, ae} {bd, be, de}

• Large 1-itemset: a, b, d, e

• La somme des supports de {ab, ad, ae} < min_sup

• inutile de générer (ab)

• J. Park, M. Chen, and P. Yu, SIGMOD’95 – DHP: Direct Hashing and Pruning
Echantillonnage

• Choisir un échantillon et extraire des motifs fréquents à l’aide d’Apriori

• Un passage sur la BD pour vérifier les itemsets fréquents :

• Seulement la bordure des itemsets fréquents est vérifiée

• exemple : verif. abcd au lieu de abc, ab, bc, ....

• Un autre passage pour trouver les motifs qui manquent

Eclat/MaxEclat et VIPER

• Tid-list: la liste des transcations contenant un itemset

• représentation verticale

• Opération principale : intersection des tid-lists

• A : t1,t2,t3

• B ; t2,t3

• support de (AB) =2
FP-Growth

• Pas de génération de candidats

• Bases de données projetées

• Nous verrons ce concept de façon plus étendue avec

l’algorithme prefixSpan d’extraction de motifs séquentiels
Fouille de motifs fréquents sous contraintes
Motivations

• Trouver tous les motifs qui apparaissent dans une base de données

• Risque d’être trop nombreux et pas être intéressant

• La fouille de données doit être interactive

• l’utilisateur exprime ce qui doit être extrait

• Fouille de motifs sous contraintes

• Flexibilité pour l’utilisateur : modélise son intérêt

• Optimisation : pousser des contraintes pour une fouille plus efficace

Contraintes en fouille de motifs

• Contraintes sur les données - requêtes SQL

• trouver les produits vendus ensembles dans les magasins de N.Y.

• Contraintes sur les niveaux/dimensions

• région, prix, marque, catégories de consommateurs

• Contraintes sur les motifs ou règles

• les petits achats (<10$) qui provoquent de gros achats (>100$)

• Contraintes sur l’intérêt : (suppport, confiance, ...)

Extraction de motifs sous contraintes

• Solution naïve : post-traitement

• Approches plus efficaces :

• Analyser les propriétés des contraintes

• «pousser» des contraintes en même temps que la fouille des motifs

fréquents.
Anti-monotonie

• Si un motif X viole une contrainte, alors tous ses super-motifs aussi.

• sum(X.Price) ≤ v : antimonotone

• sum(X.Price) > v : non antimonotone

• Exemple :

• C: range(S.profit) ≤ 15

• itemset (ab) viole C

• comme tous les sur-ensemble de (ab)

Contraintes anti-monotone
Contraintes monotones

• X satisfait la contrainte C alors tous ses super motifs aussi.

• sum(X.Price)>v (monotone)
Contraintes monotones
Contraintes succinctes

• La vérification qu’itemset X satisfasse une contrainte C peut se faire sans

regarder les transactions.

• min(X.price) >v (succinct)

• sum(X.price) > v (non-succinct)

contraintes succinctes
Contraintes convertibles

• Convertir une contrainte en une contrainte monotone ou anti-monotone en

redéfinissant un ordre sur les items.

• ex : C:avg(S.profit)≥25

• Ordonné les items en par leur prix (décroissant)

• <a,f,g,d,b,h,c,e>

• si (afb) viole C

• (afb*) aussi
Introduction aux représentations condensées
Fouille de séquences (voir .pdf)
Fouille de motifs fréquents :
Clustering (regroupement, segmentation)
Différentes techniques de clustering
Problématique

• Soient N instances de données à K attributs

• Trouver un partitionnement en c clusters (groupes) ayant du

sens.

• Affectation automatique de «labels» aux clusters

• c peut être donné ou recherché

• Les classes ne sont pas connues à l’avance (non supervisé)

• Attributs de différents types

Qualité d’un clustering

• Une bonne méthode de regroupement permet de garantir

• Une grande similarité intra-groupe
• Une faible similarité inter-groupe
• La qualité d’un regroupement dépend donc de la mesure de similarité
utilisée par la méthode et de son implémentation
• La qualité d’une méthode de clustering est évaluée par son abilité à
découvrir certains ou tous les “patterns” cachés.
Objectif du clustering

• Minimiser les distances intra-clusters

• Maximiser les distances inter-clusters

Exemples d’applications

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 :
Mesure de la similarité

• Pas de définition unique de la similarité entre objets

• différentes mesures de distance d(x,y

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

• Le type de données considérées

• Le type de similarité recherchée

Choix de la distance

• Propriété d’une distance :

• d(x,y) ≥ 0

• d(x,y) = 0 ssi x=y

• d(x,y) = d(y,x)

• d(x,z) ≤ d(x,y) + d(y,z)

• Définir une distance sur chacun des champs

• ex (numérique, e.g., âge, poids, taille, etc.): d(x,y) =|x-y| ; d(x,y) = |x-y|/dmax
(dist. normalisée)
 Types des variables

• Intervalles:

• Binaires:

• catégories, ordinales, ratio:

• Différents types:

94
 Intervalle (discrètes)
•Standardiser les données
•Calculer l’écart absolu moyen:

•où

•Calculer la mesure standardisée (z-score)

95
Exemple

96
 Similarité entre objets

Les distances expriment une similarité

Ex: la distance de Minkowski :

où i = (xi1, xi2, …, xip) et j = (xj1, xj2, …, xjp) sont deux

objets p-dimensionnels et q un entier positif
Si q = 1, d est la distance de Manhattan

97
 Similarité entre objets(I)
Si q = 2, d est la distance Euclidienne :

Propriétés
d(i,j) ≥ 0
d(i,i) = 0
d(i,j) = d(j,i)
d(i,j) ≤ d(i,k) + d(k,j)

98
99
Exemple: distance de Manhattan

99
Exemple: distance de Manhattan

d(p1,p2)=120
d(p1,p3)=132

99
Exemple: distance de Manhattan

d(p1,p2)=120
d(p1,p3)=132

Conclusion: p1 ressemble plus à

p2 qu’à p3!!! :-(

99
Exemple: distance de Manhattan

d(p1,p2)=120
d(p1,p3)=132

Conclusion: p1 ressemble plus à

p2 qu’à p3!!! :-(

99
Exemple: distance de Manhattan

d(p1,p2)=120
d(p1,p3)=132

Conclusion: p1 ressemble plus à

p2 qu’à p3!!! :-(

d(p1,p2)=4,675
d(p1,p3)=2,324

99
Exemple: distance de Manhattan

d(p1,p2)=120
d(p1,p3)=132

Conclusion: p1 ressemble plus à

p2 qu’à p3!!! :-(

d(p1,p2)=4,675
d(p1,p3)=2,324

Conclusion: p1 ressemble
plus à p3 qu’à p2 !!! :-)

99
 Variables binaires

•Une table de contingence pour données binaires

Objet j
a= nombre de positions
où i a 1 et j a 1

Objet i

•Exemple oi=(1,1,0,1,0) et oj=(1,0,0,0,1)

•a=1, b=2, c=1, d=2

100
 Mesures de distances
•Coefficient d’appariement (matching) simple (invariant
pour variables symétriques):

•Exemple oi=(1,1,0,1,0) et oj=(1,0,0,0,1)

•d(oi, oj)=3/5
•Coefficient de Jaccard
•d(oi, oj)=3/4

101
 Variables binaires (I)
• Variable symétrique: Ex. le sexe d’une personne, i.e
coder masculin par 1 et féminin par 0 c’est pareil que le
codage inverse

• Variable asymétrique: Ex. Test HIV. Le test peut être

positif ou négatif (0 ou 1) mais il y a une valeur qui sera
plus présente que l’autre. Généralement, on code par 1
la modalité la moins fréquente
•2 personnes ayant la valeur 1 pour le test sont plus
similaires que 2 personnes ayant 0 pour le test

102
 Variables binaires(II)
• Exemple

• Sexe est un attribut symétrique

• Les autres attributs sont asymétriques
• Y et P ≡ 1, N ≡ 0, la distance n’est mesurée que sur les asymétriques

Les plus similaires sont Jack et Mary⇒atteints du même mal

103
 Variables Nominales

• Une généralisation des variables binaires, ex: rouge, vert et

bleu
• Méthode 1: Matching simple
• m: # d’appariements, p: # total de variables

• Méthode 2: utiliser un grand nombre de variables binaires

• Créer une variable binaire pour chaque modalité (ex:
variable rouge qui prend les valeurs vrai ou faux)

104
 Variables Ordinales

• Une variable ordinale peut être discrète ou continue

• L’ordre peut être important, ex: classement
• Peuvent être traitées comme les variables intervalles
• remplacer xif par son rang
• Remplacer le rang de chaque variable par une valeur
dans [0, 1] en remplaçant la variable f dans l’objet I par

• Utiliser une distance pour calculer la similarité

105
 En Présence de Variables de différents Types
• Pour chaque type de variables utiliser une mesure
adéquate. Problèmes: les clusters obtenus peuvent être
différents
• On utilise une formule pondérée pour faire la combinaison

• f est binaire ou nominale:

•d (f) = 0 si x = x , sinon d (f) = 1
ij if jf ij
• f est de type intervalle: utiliser une distance normalisée
• f est ordinale
• calculer les rangs r et
if
• Ensuite traiter z comme une variable de type
if
intervalle

106
 Approches de Clustering
• Algorithmes de Partitionnement: Construire plusieurs
partitions puis les évaluer selon certains critères

• Algorithmes hiérarchiques: Créer une décomposition

hiérarchique des objets selon certains critères

• Algorithmes basés sur la densité: basés sur des notions de

connectivité et de densité

107
Méthodes de clustering : caractéristiques

• Extensibilité

• Abilité à traiter différents types de données

• Découverte de clusters de différents formes

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

• Abilité à traiter les données bruitées et isolées.

 Algorithmes à partionnement
• Construire une partition à k clusters d’une base D de n
objets
• Les k clusters doivent optimiser le critère choisi
• Global optimal: Considérer toutes les k-partitions
• Heuristic methods: Algorithmes k-means et k-medoids
• k-means (MacQueen’67): Chaque cluster est représenté
par son centre
• k-medoids or PAM (Partition around medoids) (Kaufman
& Rousseeuw’87): Chaque cluster est représenté par un
de ses objets

109
La méthode des k-moyennes (K-Means)
• L’algorithme k-means est en 4 étapes :

1. Choisir k objets formant ainsi k clusters

2. (Ré)affecter chaque objet O au cluster Ci de

centre Mi tel que dist(O,Mi) est minimal

3. Recalculer Mi de chaque cluster (le barycentre)

4. Aller à l’étape 2 si on vient de faire une affectation

110
 K-Means :Exemple
• A={1,2,3,6,7,8,13,15,17}. Créer 3 clusters à partir de A

• On prend 3 objets au hasard. Supposons que c’est 1, 2 et

3. Ca donne C1={1}, M1=1, C2={2}, M2=2, C3={3} et M3=3

• Chaque objet O est affecté au cluster au milieu duquel, O

est le plus proche. 6 est affecté à C3 car dist(M3,6)<dist
(M2,6) et dist(M3,6)<dist(M1,6); On a
• C1={1}, M1=1,
• C2={2}, M2=2
• C3={3, 6,7,8,13,15,17}, M3=69/7=9.86

111
K-Means :Exemple (suite)

112
 K-Means :Exemple (suite)
• dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent
pas. C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

112
 K-Means :Exemple (suite)
• dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent
pas. C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

112
 K-Means :Exemple (suite)
• dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent
pas. C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

• dist(6,M2)<dist(6,M3)6 passe dans C2. Tous les autres objets ne bougent

pas. C1={1}, M1=1, C2={2,3,6}, M2=11/3=3.67, C3={7,8,13,15,17}, M3= 12

112
 K-Means :Exemple (suite)
• dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent
pas. C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

• dist(6,M2)<dist(6,M3)6 passe dans C2. Tous les autres objets ne bougent

pas. C1={1}, M1=1, C2={2,3,6}, M2=11/3=3.67, C3={7,8,13,15,17}, M3= 12

112
 K-Means :Exemple (suite)
• dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent
pas. C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

• dist(6,M2)<dist(6,M3)6 passe dans C2. Tous les autres objets ne bougent

pas. C1={1}, M1=1, C2={2,3,6}, M2=11/3=3.67, C3={7,8,13,15,17}, M3= 12

• dist(2,M1)<dist(2,M2)2 passe en C1. dist(7,M2)<dist(7,M3) 7 passe en

C2. Les autres ne bougent pas. C1={1,2}, M1=1.5, C2={3,6,7}, M2=5.34,
C3= {8,13,15,17}, M3=13.25

112
 K-Means :Exemple (suite)
• dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent
pas. C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

• dist(6,M2)<dist(6,M3)6 passe dans C2. Tous les autres objets ne bougent

pas. C1={1}, M1=1, C2={2,3,6}, M2=11/3=3.67, C3={7,8,13,15,17}, M3= 12

• dist(2,M1)<dist(2,M2)2 passe en C1. dist(7,M2)<dist(7,M3) 7 passe en

C2. Les autres ne bougent pas. C1={1,2}, M1=1.5, C2={3,6,7}, M2=5.34,
C3= {8,13,15,17}, M3=13.25

112
 K-Means :Exemple (suite)
• dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent
pas. C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

• dist(6,M2)<dist(6,M3)6 passe dans C2. Tous les autres objets ne bougent

pas. C1={1}, M1=1, C2={2,3,6}, M2=11/3=3.67, C3={7,8,13,15,17}, M3= 12

• dist(2,M1)<dist(2,M2)2 passe en C1. dist(7,M2)<dist(7,M3) 7 passe en

C2. Les autres ne bougent pas. C1={1,2}, M1=1.5, C2={3,6,7}, M2=5.34,
C3= {8,13,15,17}, M3=13.25

• dist(3,M1)<dist(3,M2)3 passe en 1. dist(8,M2)<dist(8,M3)8 passe en 2

112
 K-Means :Exemple (suite)
• dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent
pas. C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

• dist(6,M2)<dist(6,M3)6 passe dans C2. Tous les autres objets ne bougent

pas. C1={1}, M1=1, C2={2,3,6}, M2=11/3=3.67, C3={7,8,13,15,17}, M3= 12

• dist(2,M1)<dist(2,M2)2 passe en C1. dist(7,M2)<dist(7,M3) 7 passe en

C2. Les autres ne bougent pas. C1={1,2}, M1=1.5, C2={3,6,7}, M2=5.34,
C3= {8,13,15,17}, M3=13.25

• dist(3,M1)<dist(3,M2)3 passe en 1. dist(8,M2)<dist(8,M3)8 passe en 2

• C1={1,2,3}, M1=2, C2={6,7,8}, M2=7, C3={13,15,17}, M3=15

112
 K-Means :Exemple (suite)
• dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent
pas. C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

• dist(6,M2)<dist(6,M3)6 passe dans C2. Tous les autres objets ne bougent

pas. C1={1}, M1=1, C2={2,3,6}, M2=11/3=3.67, C3={7,8,13,15,17}, M3= 12

• dist(2,M1)<dist(2,M2)2 passe en C1. dist(7,M2)<dist(7,M3) 7 passe en

C2. Les autres ne bougent pas. C1={1,2}, M1=1.5, C2={3,6,7}, M2=5.34,
C3= {8,13,15,17}, M3=13.25

• dist(3,M1)<dist(3,M2)3 passe en 1. dist(8,M2)<dist(8,M3)8 passe en 2

• C1={1,2,3}, M1=2, C2={6,7,8}, M2=7, C3={13,15,17}, M3=15

112
 K-Means :Exemple (suite)
• dist(3,M2)<dist(3,M3)3 passe dans C2. Tous les autres objets ne bougent
pas. C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3= 66/6=11

• dist(6,M2)<dist(6,M3)6 passe dans C2. Tous les autres objets ne bougent

pas. C1={1}, M1=1, C2={2,3,6}, M2=11/3=3.67, C3={7,8,13,15,17}, M3= 12

• dist(2,M1)<dist(2,M2)2 passe en C1. dist(7,M2)<dist(7,M3) 7 passe en

C2. Les autres ne bougent pas. C1={1,2}, M1=1.5, C2={3,6,7}, M2=5.34,
C3= {8,13,15,17}, M3=13.25

• dist(3,M1)<dist(3,M2)3 passe en 1. dist(8,M2)<dist(8,M3)8 passe en 2

• C1={1,2,3}, M1=2, C2={6,7,8}, M2=7, C3={13,15,17}, M3=15

• Plus rien ne bouge

112
Illustration (1)
Illustration (2)
Illustration (3)
Exemple
 Commentaires sur la méthode des K-Means
• Force
• Relativement extensible dans le traitement d’ensembles

de taille importante
• Relativement efficace : O(t.k.n), où n représente # objets,

k # clusters, et t # iterations. Normalement, k, t << n.

• Faiblesses
• N’est pas applicable en présence d’attributs où la

moyenne n’est pas définie

• On doit spécifier k (nombre de clusters)

• Incapable de traiter des données bruitées

• Les clusters sont construits par rapports à des objets

inexistants (les milieux)

• Ne peut pas découvrir les groupes non-convexes

• Les outliers sont mal gérés. 117

Variantes des K-means

• Sélection des centres initiaux

• Calcul des similarités

• Calcul des centres (K-medoids : [Kaufman & Rousseeuw’87] )

• GMM : Variantes de K-moyennes basées sur les probabilités

• K-modes : données catégorielles [Huang’98]

• K-prototype : données mixtes (numériques et catégorielles)

Méthodes hiérarchiques

• Une méthode hiérarchique : construit une hiérarchie de

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

Entrée : un échantillon de m enregistrements x1, ..., xm

1. On commence avec m clusters (cluster = 1 enregistrement)

2. Grouper les deux clusters les plus « proches ».

3. S’arrêter lorsque tous les enregistrements sont membres d’un seul

groupe

4. Aller en 2.
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 noeuds intermédiaires de l’arbre représentent les clusters

Distances entre clusters

• Distance entre les centres des clusters (Centroid Method)

• Distance minimale entre toutes les paires de données des 2 clusters (Single
Link Method) d(i, j) = minx∈C ,y∈C {d(x, y) }
i j

• Distance maximale entre toutes les paires de données des 2 clusters

(Complete Link Method) d(i, j)=maxx∈C ,y∈C {d(x,y)}
i j

• Distance moyenne entre toutes la paires d’enregistrements (Average

Linkage) d(i, j) = avgx∈C ,y∈C {d(x, y) }
i j
+ et -

• Avantages :

• Conceptuellement simple

• Propriétés théoriques sont bien connues

• Quand les clusters sont groupés, la décision est définitive => le nombre
d’alternatives différentes à à examiner est réduit

• Inconvénients :

• Groupement de clusters est définitif => décisions erronnées sont impossibles à

modifier ultérieurement

• Méthodes non extensibles pour des ensembles de données de grandes tailles

Méthode basée sur la densité

• Pour ce types de problèmes, l’utilisation de mesures de similarité (distance) est

moins efficace que l’utilisation de densité de voisinage.
 Clustering basé sur la densité
• Voit les clusters comme des régions denses séparées par
des régions qui le sont moins (bruit)
• Deux paramètres:
•Eps: Rayon maximum du voisinage
•MinPts: Nombre minimum de points dans le voisinage-
Eps d’un point
• Voisinage : VEps(p): {q ∈ D | dist(p,q) <= Eps}
• Un point p est directement densité-accessible à partir de q
resp. à Eps, MinPts si
•1) p ∈VEps(q) p MinPts = 5
•2) |VEps (q)| >= MinPts q
Eps = 1 cm

126
 Clustering basé sur la densité

• Accessibilité:
p
• p est accessible à partir de q resp. à
Eps, MinPts si il existe p1, …, pn, p1 p1
q
= q, pn = p t.q pi+1 est directement
densité accessible à partir de
pi
• Connexité
p q
• p est connecté à q resp. à Eps,
MinPts si il existe un point o t.q p et
o
q accessibles à partir de o resp. à
Eps et MinPts.

127
 DBSCAN: Density Based Spatial
Clustering of Applications with Noise

• Un cluster est l’ensemble maximal de points connectés

• Découvre des clusters non nécessairement convexes

Bruit

Limite
Eps = 1cm
Centr MinPts = 5

128
 DBSCAN: l’algorithme

 Choisir p
 Récupérer tous les points accessibles à partir de p resp.
Eps et MinPts.
 Si p est un centre, un cluster est formé.
 si p est une limite, alors il n’y a pas de points accessibles
de p : passer à un autre point
 Répéter le processus jusqu’à épuiser tous les points.

129
Résumé

• Le clustering groupe des objets en se basant sur leurs similarités.

• Le clustering possède plusieurs applications.

• La mesure de similarité peut être calculée pour différents types de données.

• La sélection de la mesure de similarité dépend des données utilisées et le

type de similarité recherchée.
• Les méthodes de clustering peuvent être classées en :

• Méthodes de partitionnement,

• Méthodes hiérarchiques,

• Méthodes à densité de voisinage

• Plusieurs travaux de recherche sur le clustering en cours et en perspective.

• Plusieurs applications en perspective : Génomique, Environnement, ...