SAAFA-76-MRRRCH
Langages requête data mining
Extraction de connaissances à partir des données
L’extraction de connaissances à partir des données ECD (KDD – Knowledge Discovery in Databases -) a été déni comme étant un processus non trivial pour l’identication de motifs valides, nouveaux, utiles et compréhensibles à partir de données [3][4]. La qualication non triviale signie qu’une phase de recherche est eectuée et il ne s’agit pas d’un simple calcul. Les motifs découverts doivent être valides sur les nouvelles données avec un certain degré de certitude. Il est aussi intéressant que les motifs découverts soient nouveaux et utiles an que l’utilisateur puisse en bénécier. Enn, les motifs doivent être compréhensibles si nécessaire après un post-traitement. Le processus d’extraction de connaissances à partir des données (ECD) est itératif et interactif, il est possible de revenir à une étape antérieure comme l’utilisateur peut aussi intervenir et interagir avec le système. Le terme processus implique que KDD comprend plusieurs étapes [3][4] : 1. La première étape est la compréhension du domaine d’application et l’identication des objectifs des utilisateurs. 2. Sélection des données : cette étape consiste à sélectionner, parmi toutes les données, celles sur lesquelles l’extraction de connaissances sera eectuée. 3. Nettoyage de données et prétraitement : une fois l’ensemble de données est sélectionné, il peut être nécessaire d’appliquer un prétraitement. Les données peuvent ne pas être décrites complètement et qu’il y ait des valeurs manquantes à certains attributs. Des défauts de mesures peuvent provoquer des erreurs qu’on qualie de bruits. Cette étape consiste alors 5 Chapitre 1 Introduction au data mining à éliminer le bruit (nettoyage de données) présent dans les données et à la gestion des données manquantes. 4. Projection et réduction de données : Cette étape consiste à déterminer les caractéristiques utiles pour représenter les données et cela en fonction des objectifs dénis dans l’étape précédente. Les données à ce niveau peuvent être transformées par des méthodes de réduction et de projection pour réduire le nombre de variables, discrétiser les valeurs d’un certain attribut continu. 5. Déterminer une correspondance entre les objectifs dénis dans la première étape et une méthode data mining particulière : classication, segmentation…etc. 6. Fouille de données ou data mining : cette étape constitue le c÷ur du processus d’extraction de connaissances à partir des données. C’est l’étape où s’eectue l’extraction automatique des motifs à partir des données. 7. Interprétation des modèles extraits : il s’agit de voir si la connaissance extraite est nouvelle et pertinente pour le domaine considéré ; les modèles extraits sont représentés sous forme de graphes, de relations avec un degré de certitude. 8. Intégration de la connaissance : intégrer et exploiter la nouvelle connaissance dans un autre système pour un usage particulier. Le processus KDD est itératif, nous constatons qu’au niveau de l’étape d’interprétation des résultats, il est possible de retourner à n’importe quelle étape de 1 – 6 pour d’autres itérations, tel qu’il est illustré sur la gure Data mining Data mining ou fouille de données est une étape du processus KDD, elle consiste à appliquer des algorithmes d’analyse et de découverte pour l’énumération des motifs à partir des données [3][4]. Les principales tâches que le data mining est amené à accomplir sont [19][11] : Classication-Prédiction La classication et la prédiction (régression) sont deux opérations qui visent à estimer la valeur d’une variable (dite cible ou à expliquer) d’un individu en fonction de la valeur d’un certain nombre d’autres variables du même individu (indiquées comme variables explicatives). La valeur à expliquer est qualitative dans le cas de la classication et continue dans le cas de la prédiction. La classication permet de placer chaque individu de la population étudiée dans une classe, parmi plusieurs classes prédénies, en fonction des caractéristiques de l’individu indiquées comme variables explicatives. L’aectation à une classe à partir des caractéristiques explicatives se fait par une formule, un algorithme ou un ensemble de règles qui constitue un modèle et qu’il faut découvrir. Segmentation La segmentation ou le clustering est utilisée quand nous disposons d’un grand volume de données au sein duquel nous cherchons à distinguer des sous ensembles homogènes susceptibles de traitements et d’analyses diérenciés. Cette opération consiste à regrouper des objets en un nombre limité de groupes (segments ou clusters) ayant deux propriétés. D’une part, ils ne sont pas prédénis mais découverts au cours de l’opération et d’une autre part, les groupes de la segmentation regroupent les objets ayant des caractéristiques similaires et séparent les objets ayant des caractéristiques diérentes. La segmentation est beaucoup utilisée en marketing, médecine, sciences humaines… En marketing, elle vise à la recherche des diérents prols de clients constituant une clientèle. Après avoir détecté les classes résumant sa clientèle, l’entreprise peut par exemple élaborer pour chacune d’elles une ore. Elle peut aussi suivre l’évolution de sa clientèle au l des mois.
Contraintes succinctes
Han et al. ont étudié l’optimisation des requêtes d’extraction des règles d’association avec contraintes [16]. L’utilisateur avant d’émettre sa requête concernant l’extraction des règles d’association, peut spécier des contraintes que les règles doivent satisfaire. Leur challenge est de garantir un niveau de performance en étudiant les caractéristiques des contraintes imposées. Pour cela, ils ont introduit deux propriétés, caractérisant les contraintes, ayant un pouvoir d’élagage important : les contraintes anti-monotones et/ou succinctes. En se basant sur ces deux propriétés, ils ont classé les contraintes en quatre catégories puis proposé un algorithme d’extraction qui réalise un maximum d’élagage pour chaque catégorie de contraintes. Requêtes d’extraction des règles d’associations avec contraintes Han et al. ont introduit la notion CAQ – Constrained Association Query – ou bien requête d’extraction de règles d’association avec contraintes pour spécier les contraintes que doit véri- er la partie antécédente S1 et la partie conséquence S2 d’une règle d’association extraite. Une requête CAQ est dénie de la manière suivante : {S1, S2 | C} tel que C est l’ensemble de contraintes que doivent vérier S1 et S2 y compris la fréquence. Ces contraintes peuvent être dé- nies sur une seule variable comme la partie antécédente et/ou conséquence séparément comme elles peuvent lier les deux variables S1, S2 conjointement. Contraintes à une variable Une contrainte à une variable peut avoir l’une des formes suivantes [16] : 1. Contraintes classe : elle est sous la forme S ⊂ A, avec S est une variable ensemble et A est un attribut. Cette contrainte signie que S est un ensemble de valeurs du domaine de l’attribut A. 2. Contrainte domaine : ce type de contraintes peut avoir l’une des formes suivantes. Sθv, S est une variable ensemble, v est une constante du domaine de S et θ est l’un des opérateurs booléens suivants : =, 6=, , ≥. Cela signie que chaque élément de S est en relation θ avec la constante v. vθS, S et v sont dénis comme précédemment et θ est l’un des opérateurs ∈, 6∈. Cela signie que l’élément v appartient ou non à l’ensemble S. SθV ou V θS, S est une variable ensemble, V est un ensemble de constantes du domaine de S et θ est l’un des opérateurs ⊆, 6⊆, ⊂, 6⊂, =, 6=. 3. Contrainte aggrégat : elle est de la forme agg(S)θv, avec agg est l’une des fonctions d’aggrégat min, max, sum, count, avg et θ est l’un des opérateurs booléens =, 6=, , ≥. Cela signie que l’aggrégat de l’ensemble des valeurs numériques dans S sont en relation θ avec v. Contraintes à deux variables Une contrainte à deux variables peut avoir l’une des formes suivantes [16] : 1. S1θS2, Si est une variable ensemble et θ est l’un de ⊆, 6⊆, ⊂, 6⊂ 2. (S1 ◦ S2)θV , S1 et S2 des variables ensemble, V est un ensemble de constantes ou ∅, ◦ est l’un de ∩,∪ et θ est l’un des =, 6=, ⊆, 6⊆, ⊂, 6⊂. 3. agg1(S1)θagg2(S2), agg1 et agg2 sont deux fonctions d’aggrégat et θ est l’un des opérateurs booléens =, 6=, , ≥. L’optimisation et les contraintes anti-monotones L’anti-monotonie est l’une des deux propriétés qu’ont utilisé Han et al. pour l’optimisation des requêtes CAQ. Une fois les contraintes anti-monotones sont identiées, comment exploiter cette propriété ? L’idée est que l’optimisation avec élagage appliquée à la fréquence est aussi
|
Table des matières
Table des matières
Liste des _gures
Liste des tableaux
Liste des algorithmes
Introduction
1 Introduction au data mining
1.1 Introduction
1.2 Domaines d’application
1.3 Extraction de connaissances à partir des données
1.4 Data mining
1.5 Conclusion
2 Cadre théorique d’extraction de connaissances
2.1 Introduction
2.2 Dé_nitions
2.3 Bordures d’une théorie
2.4 Représentation ensembliste
2.5 Exemples de problèmes
2.5.1 Problèmes liés aux motifs fréquents
2.5.2 Découverte des clés dans une base de données
2.5.3 Découverte des dépendances fonctionnelles (DF) de la couverture canonique
2.5.4 Découverte des dépendances d’inclusion
2.6 Le projet iZi
2.6.1 Aspects méthodologiques
2.6.2 La librairie iZi
2.7 Problème de découverte de la couverture canonique des dépendances fonctionnelles
2.8 Conclusion
3 Langages requête data mining
3.1 Introduction
3.2 Exemples de langages de requête data mining
3.2.1 DMQL -Data Mining Query Language for relational databases-
3.2.2 MINE RULE
3.2.3 OLE DB for DM
3.2.4 DML -Data Mining Logic-
3.2.5 Comparaison
3.3 Conclusion
4 Techniques et algorithmes d’optimisation data mining
4.1 Introduction
4.2 Techniques d’optimisation
4.2.1 Monotonie / Anti-monotonie
4.2.2 Contraintes succinctes
4.3 Algorithmes d’optimisation
4.3.1 Apriori
4.3.2 Apriori+
4.3.3 ABS
4.3.4 CAP
4.4 Tableau récapitulatif
4.5 Conclusion
5 Optimisation des requêtes data mining pour IZI
5.1 Introduction
5.2 Approche d’optimisation pour IZI
5.2.1 Logique DML
5.2.2 Langage utilisateur
5.2.3 Détermination de la forme logique d’une requête
5.2.4 Génération d’un plan physique
5.3 Conclusion
Conclusion et perspectives
Bibliographie
A Inférence des dépendances fonctionnelles
Télécharger le rapport complet
