Les tâches en fouille de données

By 3 May 2013

1.2.2 Les tâches en fouille de données

La fouille de données est en fait un ensemble de techniques dédiées à différentes tâches groupées généralement en deux grandes catégories : des tâches descriptives et autres prédictives (Fayyad et al., 1996). Les tâches de la première catégorie ont pour objectifs de décrire des phénomènes ou des tendances gisant dans les données, alors que celles de la deuxième classe s’intéressent à l’estimation de valeurs futures de variables en prenant en considération d’autres valeurs historisées.

Présentons, dans les points suivants, les principales tâches que le DM est amené à accomplir, que nous avons résumé de (Fayyad et al., 1996), (Zaïane, 1999), (Gardarin, 1999), (Gilleron et al., 2000) et (Larose, 2005).

1.2.2.1 La description

Cette tâche permet de résumer les caractéristiques générales des objets d’un ensemble de données, dans le but de fournir des modèles sous forme de règles de caractérisation.

Les modèles doivent décrire des caractéristiques claires, qui puissent amener à une interprétation et une explication intuitive.

Plusieurs techniques, qui diffèrent par leur degré de simplicité et de compréhension, peuvent être utilisées dans cette tâche. Nous pouvons citer : l’analyse exploratoire, les arbres de décision, les méthodes de visualisation, les réseaux de neurones…etc.(cf. 1.4).

1.2.2.2 L’analyse d’association

L’objectif dans l’analyse d’association est la découverte des produits ou éléments (on dit aussi items) liés. L’application type de cette tâche est l’analyse du panier de la ménagère, bien connue dans le monde du marketing, où on tente de trouver les associations pouvant existées entre les produits commandés (produits souvent achetés ensemble), en explorant les transactions enregistrées dans les bases des supermarchés.

Les règles d’association générées dans cette tâche ont la forme suivante : si X alors Y, qu’on note X  Y, où X et Y sont des ensembles d’objets (généralement des produits). Les règles de cette forme traduisent le fait que si les objets de l’ensemble X sont présents dans une transaction, alors les objets de l’ensemble Y le sont aussi avec une certaine probabilité.

L’analyse d’association peut être utilisée également dans tout domaine où il s’avère intéressant de rechercher des associations d’objets ou des liaisons de faits. Ce genre d’analyse est très convoité dans une moult de métiers tels que dans les banques, les télécommunications, la médecine, le Web…etc.

Pour l’extraction des règles d’association, on utilise un algorithme célèbre appelé Apriori introduit par Agrawal en 1993 dans (Agrawal et al., 1993) ou un de ses dérivés. Cet algorithme (présenté dans 1.4.7) peut générer un nombre important de règles, qui peuvent comporter certaines règles inutiles. Afin de réduire le nombre de règles extraites et se limiter seulement à celles intéressantes, deux mesures appelées support et confiance ont été introduites.

Le support d’une règle est le pourcentage de transactions qui vérifient cette règle, quant à la confiance, elle indique le pourcentage de transactions qui vérifient la conclusion de la règle parmi celles qui vérifient ses prémisses.

Support(XY)=|XY|/|BD|
|X| : est le nombre de transaction contenant X.
|BD| : est le nombre total de transactions dans la base.
Confiance(XY)=|XY|/|X|=Support(XY)/Support(X).

1. Support et confiance d’une règle d’association.

Avec ces deux mesures, l’approche adoptée dans les algorithmes de fouille de données est de retenir les règles avec un support supérieur à un minimum (MinSup), et une confiance supérieure à un minimum (MinConf).

1.2.2.3 La classification

La classification a pour but d’identifier la classe, prise dans un ensemble prédéfini, i.e connu à l’avance, à la quelle appartiennent des objets en examinant certaines propriétés ou traits descriptifs. Des exemples courants de tâche de classification sont : attribuer ou non un crédit à un client sur la base de sa situation personnelle, établir un diagnostic médical à partir de la description clinique d’un patient, déclencher un processus d’alerte en fonction de signaux reçus par des capteurs…etc.

La classification est une tâche d’apprentissage supervisé1, le système apprend en généralisant une procédure de classification à partir d’exemples. Un exemple consiste en la description d’un cas avec la classification correspondante.

Une meilleure tâche de classification doit induire une procédure ayant un bon pouvoir prédictif, c’est-à-dire pouvant classer de nouveaux exemples n’ayant pas participés à son apprentissage. La qualité de la classification est donc fonction de cette capacité de généralisation.

1 L’apprentissage est couramment divisé en deux types supervisé et non supervisé : si nous disposons d’exemples d’apprentissage avec les réponses correctes ou désirées nous parlons d’apprentissage supervisé. Dans le cas contraire, i.e. si nous n’avons pas de sorties ou de réponses préétablies, le système apprend à catégoriser les entrées en détectant les régularités, nous parlons d’apprentissage non supervisé.

Cette tâche est souvent accomplie en un processus à deux étapes : une première d’apprentissage à partir d’exemples où un modèle est construit, et une deuxième de test ou d’utilisation de ce modèle. Elle a fait l’objet de multiples travaux proposant des techniques variées, avec pour chacune ses avantages et ses inconvénients. Parmi les plus utilisées, nous pouvons lister : les arbres de décision, les réseaux de neurones, les classificateurs naïfs de Bayes et les algorithmes génétiques (Cf. 1.4).

1.2.2.4 La segmentation

Similaire à la classification, la segmentation consiste à regrouper les objets donnés en entrée dans des ensembles homogènes appelés segments, groupes ou encore clusters. C’est une tâche d’apprentissage non supervisé, car nous ne disposons d’aucune information autre que la description des objets à segmenter. Les segments sont donc automatiquement inférés à partir des données. Elle diffère de la classification dans le sens où il n’existe pas de segments prédéfinis.

Le regroupement en clusters est basé sur des mesures de similitudes existantes entre les objets. L’idée consiste à maximiser ces mesures entre les objets du même groupe et de les minimiser entre ceux appartenant à des groupes différents. On parle de homogénéité interne et de séparation externe (Xu et al., 2005). Cette similarité entre les objets s’exprime en terme d’une fonction de distance, où les objets à segmenter sont assimilés à des points de l’espace. Le choix de cette fonction est fait parmi plusieurs mesures disponibles, selon le type de données considérées (discrètes, réelles,…etc.) et le type de similarité recherchée. Rappelons qu’une distance doit vérifier les propriétés suivantes : (d(x, y) dénote la distance entre les objets x et y)

1) d(x, y)>=0 ; 2) d(x, x)=0 ; 3) d(x, y)=d(y, x) ; 4) d(x, z) <=d(x, y) +d(y, z).

Voici des exemples de fonctions de distances :

La distance euclidienne : d(x,y)=√∑i(xi-yi)2
La distance de Manhattan : d(x,y)=∑i(|xi-yi|

2. Exemples de fonctions de distance

Selon (Berkhin, 2002) les techniques de segmentations sont divisées en trois classes. Nous donnons le principe de chacune d’elles dans ce qui suit.

La segmentation hiérarchique construit une hiérarchie ou un arbre de clusters appelés dendrogrammes, où chaque cluster contient des clusters fils. Elle procède soit de manière ascendante (agglomérative), par fusion des N clusters initiaux et en remontant (N étant le nombre d’objets ou de points), soit de façon descendante (divisive) par séparation du cluster initial contenant tous les points à segmenter. Le processus se termine généralement à la vérification d’une condition d’arrêt, souvent le nombre de clusters demandés.

Contrairement aux méthodes de segmentation hiérarchique, où les clusters ne sont pas révisés une fois construits, dans la segmentation par partitions, les points ou les objets sont déplacés et réaffectés entre les clusters, ce qui améliorera leur qualité. L’algorithme le plus connu de cette famille de méthodes est le K-moyenne (K-means) (Cf. 1.4), il permet de segmenter N objets en K groupes en les agrégeant autour de centres mobiles (Gardarin, 1999).

Dans certaines classes de problèmes, tels que la reconnaissance de formes ou la segmentation de figures irrégulières, la notion de distance entre objets n’est pas suffisante et l’application des techniques hiérarchiques ou partitionnistes ne donne pas des résultats satisfaisants. Pour résoudre ce type de problèmes, la notion de voisinage dense fut introduite. La segmentation par voisinage dense considère les clusters comme des régions homogènes de haute densité entourées par des régions de faible densité. La densité est définie par deux paramètres : r le radius du voisinage de l’objet et d le nombre minimum d’objets qui doivent être contenus dans le voisinage pour considérer la zone comme dense. C’est-à-dire que deux points sont dans un même voisinage s’ils sont à une distance inférieure au seuil r. un voisinage est dense s’il contient plus d’un nombre fixe d de points (Berkhin, 2002), (Candillier, 2006).

Notons que bien que cette approche a donné des résultats satisfaisants dans des problèmes réels, son adaptation à de grandes bases de données n’est pas évidente selon (Gardarin, 1999).

1.2.2.5 La prédiction

Dans cette tâche, le but est d’estimer par différents algorithmes des valeurs futures de variables, dites à prédire, en prenant en considération d’autres valeurs historisées de variables prédictives. Par exemple, on peut grâce à cette tâche prédire les valeurs futures d’actions ou prédire, au vu de leurs actions passées, les départs des clients…etc.

Une variété de méthodes est utilisée dans la prédiction. Nous citons les méthodes statistiques, telles que la régression (linéaire, multiple ou logistique), les réseaux de neurones…etc. (Cf. 1.4).

1.2.2.6 L’analyse d’exception et de déviation

Dans cette fonction, on tente de dégager et d’étudier des exceptions ou des surprises contenues dans les données, comme par exemple les objets ne pouvant être classés dans une classification (Fayyad et al., 1996). Ces cas peuvent révéler des explications utiles dans certains domaines, ou indiquer des données bruitées ou erronées. .

Lire le mémoire complet ==> (Prétraitement & Extraction de Connaissances en Web Usage Mining)
S2WC2 : un WUM Framework Centré Utilisateur
Mémoire En vue de l’obtention du diplôme de Magister – Option : Informatique et Communication Electronique
Département des Mathématiques et d’Informatique – Spécialité : Informatique
Université Kasdi Merbah de Ouargla – Faculté des Sciences et Sciences de l’Ingénieur