Data Mining resume de cours

La technique dite des règles d’associations est une technique d’apprentissage non supervisé. Son but est de transcrire la connaissance sous la forme d’une règle d’association,

Antécédent et conséquent d’une règle : Une règle d’association s’écrira toujours sous la forme suivante:  A => B (si A alors B)

L’antécédent (condition) est ce qui est à gauche de la règle. ex: pain et fromage/Le conséquent (résultat) est ce qui vient à la droite de la règle. ex: lait

La règle d’association sera donc: si antécédent(s) alors (=>) conséquent(s).

En général, les règles d’association peuvent être : utiles, trivial ou déjà identifier ,inexplicable , temporelles .

Il existe plusieurs types de règles d’associations: Intratransactionnelles: achats effectués lors d’une même transaction.2 Intertransactionnelles: achats effectués sur plusieurs transactions généralement dans le temps.3 Unidimensionnelles: formées d’items de même nature 4  ex: produits dans un super marché.  5-Multidimensionnelles: formées d’items de différentes dimensions  ex: produits achetés et caractéristiques des clients:

Chevrolet cavalier => revenu < 25000$.

T: une transaction////D: la base de données transactionnelles, contenant n transactions///I = {i1, i2, …, im} l’ensemble des m items pouvant faire partie d’une base de données transactionnelles D.//Soit T  une transaction; T est donc un sous-ensemble de I : T ⊆ I./////Une règle d’association est de la forme   X => Y    où : X ⊂ I, Y ⊂ I et  X ∩ Y = ∅/////Soit n le nombre de transactions dans la base de données D.

Fréquence de la règle (X => Y) (est compris entre [0; n]) :;; Fréq(X=>Y) = nombre de transactions dans D qui contiennent X ∩Y  (X et Y).

Dans ma bas de données , j’observe freq transactions qui contiennent simultanément les éléments qui constitue ma base de donnes.

Support de la règle (X => Y) (est compris entre [0; 1])  Supp(X => Y) = Fréq (X => Y) / n/// c’est-à-dire P(X et Y arrivent)////Le support est utilisé pour identifier les règles qui sont fréquentes.///dans la base de données , la probabilités d’observer simultanément (tous les éléments qui constitue ma règle d’association)

Confiance de la règle (X => Y)  (est compris entre [0;1])///Conf(X=>Y) = Fréq (X =>Y) / Fréq (X)       =P(Y | X)

La probabilité d’observer dans un panier d’achat mon conséquent étant donne que j’observe mon antécédent// la probabilités que le client choisisse mon conséquent étant donne qu’il a acheté mon antécédent .

Effet de levier (lift) de le règle (X => Y ) (est compris entre [0; +inf[)   //Lift(X=>Y) = Conf (X =>Y ) / Supp (Y )///  = P(X et Y arrivent) /  P (X)P(Y)

Mieux comprendre le levier (ou lift) : Si on considère le règle : X => Y//Lorsque l’on calcule le lift(X=>Y), on cherche à comprendre quel est l’effet d’observer l’antécédent X dans « un panier, une transaction » sur la probabilité d’observer le conséquent Y.///Pour mesurer cet effet, je vais en fait calculer le ratio de probabilités suivant :Lift(X=>Y) =Lift>1 il existe une relation positive entre l’antécédent et le conséquent. Les chances que le client achète le conséquent sont multipliées par le lift des lors que le client achète l’antécédent. ///lift =<1 il existe une relation négative entre l’antécédent et le conséquent. Les chances que le client achète le conséquent sont réduite de 1-lift % des lors que le client achète l’antécédent.////Le support est une mesure symétrique:////support (X => Y) = support (Y => X ) La confiance n’est pas une mesure symétrique:////conf (X => Y) ≠ conf (Y => X ) ///Le lift:        Indique le gain de la règle versus le tirage aléatoire. //Est une mesure symétrique: lift (X => Y ) = lift(Y => X )// Si X et Y sont indépendants le lift sera égal à 1.Une valeur plus grande que 1 indique une association positive et une valeur inférieure à 1 indique une association négative et donc pas utile.////En fait un lift égal à 2 signifie que le consommateur qui achète le produit X a deux fois plus de chances d’acheter Y que le consommateur en général///[pic 1]

.Avantages et incovénients des règles : Les avantages des règles d’associations:///Règles simples à comprendre///Résultats explicites facilement applicables.///Adaptée à l’exploitation non dirigée des données.///Les inconvénients à utiliser les règles d’association:  Volume est exponentiel.///Difficulté à déterminer le nombre d’articles dans une règle.

Ignore les articles rares.////Ne tient pas compte de la quantité acheté d’un item ni de la valeur ou du profit généré par l’item.

1-Algorithme Apriori (par Agrawal et Srikant, 1994 : Au point de départ de l’algorithme, il faut fixer un seuil de support minimal (minsup) pour que seules les règles d’associations avec un support plus grand ou égal à ce seuil soient générées.

2-À l’itération k  (1 ≤ k ≤ m), l’algorithme procède en deux étapes: a)il génère tous les sous-ensembles de k items potentiellement fréquents à partir des sous- ensembles des (k-1) items fréquents. (note: un itemset fréquent => support(itemset) >= minsup)

B)il élague tous les sous-ensembles de k items qui ne peuvent être fréquents.C)L’algorithme fait un k-ième passage dans la base de données pour calculer le support des sous-ensembles de k items générés et retenus.3-L’algorithme retourne l’union de tous les itemsets fréquents

Notes:  Les résultats varieront en fonction des seuils retenus à l’étape 1;///Il est possible de spécifier une confiance > 0 afin de ne retourner que les « associations fortes »./////---ex exercice ::cette règle d’association ne peut être estime car elle n respecte pas l’une des propriétés des règles d’association : items ne peut pas apparaitre dans l’antécédent et dans le conséquente // l’élément n’est pas un élément de l’itemset I , L’antécédent n’est pas inclus dans l’itemset initial .

I : pizza, lait , sucre , pomme , café ///// m= 5 (nombre de produits)//n=5( nombre de transaction).

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------Segmentation : Définition: C’est l’opération statistique qui consiste à regrouper des objets, qui se ressemblent, en un nombre limité de groupes nommés segments (ou clusters en anglais)./Non supervise/méthodes descriptive la plus utilise /utilisée lorsque le but est de rechercher des sous-ensembles homogènes issus d’un ensemble de grande taille et de caractériser ces sous-ensembles./ L’algorithme en question va tout faire pour:Rassembler les individus aux caractéristiques homogènes dans un cluster et Créer des clusters ayant des caractéristiques hétérogènes.

Mesure de la qualité de la segmentation : Mesure de Dissemblance/Ressemblance: la ressemblance est exprimée par une fonction de distance  d (i, j). Plus les individus se ressemblent, plus ils sont proches dans l’espace et plus  la distance sera faible.// Il est difficile de définir “assez ressemblant” ou “bonne ressemblance” pour inclure deux individus dans le même groupe, C’est pour cela qu’une fonction de distance est normalement utilisée, pour mesurer la resemblance (proximité) ou dissemblance (éloignement) entre deux individus.

Quelques propriété sur les distances : La fonction de distance utilisée doit respecter les propriétés suivantes: Séparation: la distance d’un individu à lui-même doit être nulle (sur la diagonale): d(i,i) = 0//Positive: la distance entre les individus est toujours positives ou mulle: //Symétrie: la distance entre l’individu i et j est la même que la distance entre j et i: d(i,j) = d(j,i)////Inégalité triangulaire: la relation suivante doit être respectée:  d(i,j) ≤ d(i,k) + d(k,j)[pic 2]

Notion de distance variable continue : Une fonction de distance, parmi les plus populaires pour des variables continues, est la distance euclidienne./où i et j font référence aux individus auxquels on s’intéresse et  1, 2, … p font référence aux variables///la distance de Manhattan.=====Avec L1: La standardisation de donnes : lorsque les variables continue ne sont pas mesurée dans la même unité ou si ils n’ont pas la même moyenne ou médiane :effet d’échelle[pic 3][pic 4][pic 5]

 / si=ecart type / x1 chapeau / moyenne.//// Manhatan =[pic 6][pic 7]

Notion de distance variable binaire : matrice de contingence :la distance du simple Matching :[pic 8]

La segmentation: 2 méthodes distinctes : La méthode Hiérarchique: Cette méthode est principalement utilisée lorsque l’on ne sait pas le nombre de groupes que l’on aimerait avoir. On va donc effectuer un grand nombre de regroupements successifs afin de choisir le nombre optimal de groupes à conserver.La méthode non-Hiérarchique: Avec cette méthode, on va fixer le nombre de groupes dès le départ (a priori). L’approche hiérarchique est moins exploratoire que la méthode non-hiérarchique car une fois un regroupement fait, il n’est plus possible de le défaire.

Methode Hiererachique : Forme général de l’algorithme de segmentation hiérarchique:1--Les segments initiaux sont formés par les observations (autant de groupes que d’observations)2-Les distances entre les segments sont calculés3-Les 2 segments les plus proches sont regroupés pour former un nouveau segment. Recalculer son centre.4-Recommencer à l’étape 2 jusqu’au moment ou il n’y a plus qu’un seul segment contenant toutes les observations

Note: avec la méthode hiérarchique, une fois que deux individus sont regroupés, ils le restent jusqu’à la fin. Ce n’est pas le cas avec les méthodes non hiérarchiques ou les individus peuvent changer de groupe n’importe quand///Mécaniques pour rassembler des segments ensembles : Méthode du plus proche voisin (très utilisée) (single linkage method): La distance entre deux groupes est définie comme étant distance minimale entre 2 individus issus de 2 groupes distincts. (Sensible à l’effet de chaîne, utile lorsque les clusters sont étirés, irréguliers ou tordus.)

Méthode du voisin le plus éloigné (maximum distance, farthest neighboor, diameter criterion or complet linkage): La distance entre deux groupes est définie comme étant la distance maximale entre 2 individus issus de 2 groupes distincts. (Très sensible aux valeurs aberrantes, produit des clusters de diamètre similaire, peu utilisée.)

Méthode de liaison moyenne (mean distance, average linkage): La distance entre deux groupes est définie comme la moyenne des distances entre toutes les paires de sujets(un pour chaque groupe) provenant des 2 groupes. (Moins sensible aux bruits et facile à calculer.)

Méthode centroïde: La distance entre deux groupe est définie comme étant la distance entre les représentants moyens de chaque groupe où le représentant moyen d’un groupe est la moyenne, variable par variable, des sujets formant le groupe. (La plus adapté lorsqu’il y a des valeurs aberrantes mais la moins précise.)

Méthode de Ward (la plus utilisée en pratique): Cette méthode est basée sur un critère d’homogénéité global des groupes. Pour un groupe donné,).

Les avantages des méthodes hiérarchiques:///Il n’est pas nécessaire de fixer un nombre de groupe a priori;///Fournissent l’information sur l’augmentation de la dispersion dans un groupe produit par l’agrégation;//Donnent une idée sur le nombre adéquat de classes en choisissant la partition correspondant au saut le plus élevé dans l’augmentation de la dispersion au sein des classes.///Les inconvénients: 1-Suivant la mesure, elles nécessitent le calcul des distances, entre individus deux à deux;2-Prohibitives dès que la taille du fichier devient grande (excède le millier d’individus).

methode non hierrarchique : l’algorithme K means : Après avoir fixé le nombre de groupes K que l’on souhaite avoir à la fin des itérations, l’algorithme procède comme suit:1--K points sont choisis pour être les points de départ de l’algorithme, les centres de k segments (choix aléatoire ou pseudo aléatoire)2La distance euclidienne entre les individus et les centres sont calculées et les individus sont associées aux segments les plus proches, c’est-à-dire au segment dont le centroïde est la plus proche.3-Les K centres sont remplacés par des nouveaux centres de gravité issus de l’étape 2. Les centres ne sont plus donnés par des individus.4-Vérifier si la valeur des centres est stable avec les nouvelles assignations, si non, retourner à l’étape 2////////Les avantages de l’algorithme de K-means: 1-Rapidité d’estimation (complexité linéaire): le temps d’estimation est proportionnel aux nombres d’individus; 2-Permet de détecter les valeurs extrêmes et de les isoler dans des clusters;3-Pratique quand il y a un très grand nombre d’observations (des milliers);4-Au cour de l’algorithme, la composition des clusters est dynamique et non statique comme c’est la cas avec les méthodes hiérarchiques. La qualité de la segmentation est améliorée à chaque itération.////// Les inconvénients de l’algorithme du K-means : 1-Obligation de fixer a priori le nombre de segments ou clusters. Ce problème peut être atténué en estimant la segmentation avec plusieurs valeurs de k différente-2-Dépendance au choix des centres initiaux (seeds). Mais ce problème peut être atténué en :-comparant les résultats avec des centres initiaux différents;-Estimant des segmentations sur des sous-échantillons de la population globale, et en choisissant le meilleur centre, obtenu sur la précédente segmentation, comme point de départ de la segmentation sur la population globale.//// CCC signifie Cubic Clustering Criterion. Il nous renseigne sur la qualité de la segmentation retenue. Suivant la valeur que le critère CCC prend, cela indique: la segmentation est bonne  la segmentation demande à être analysée la segmentation est possiblement affectée par la présence de segments ne contenant que très peu d’individus[pic 9][pic 10][pic 11]