Approche pour la distribution de l’algorithme OPTICS

Approche pour la distribution de l’algorithme OPTICS

Les techniques de Data Mining distribuées

Les approches de Data Mining distribuées peuvent être divisées en deux catégories : les approches traditionnelles et les nouvelles approches. Les approches de distribution traditionnelles exigent qu’un grand nombre de données soit transféré à un site central ; ce qui engendre des coûts de communication très élevés. Les nouvelles approches sont basées sur l’agrégation des modèles locaux, elles évitent le transport de grandes quantités de données à un site central ; ce qui réduit les coûts de communications. Plusieurs algorithmes distribués de Data Mining on été développés. Parmi : une approche pour l’extraction de règles d’associations distribuée [12], l’approche FDM (A fast distributed algorithm for mining association rules) [6,7], L’approche GFM (Grid-based Frequent itemsets Mining) [8, 13] et l’approche parallèle de l’algorithme FP-Growth [14]. Ce domaine de recherche est très large, mais peu de travaux ont été consacrés au clustering distribué. Parmi les travaux existants, on trouve dans [15, 16, 17] La parallelisation de l’algorithme de clustering basé sur la densité DBSCAN. Dans [18] une version parallèle de BIRCH (balanced iterative reducing and clustering using hierarchies) et dans [4] l’approche de clustering distribuée multi-etage. Dans la suite de ce chapitre, nous présentons quelques algorithmes distribués traditionnels. Nous étudions ceux basés sur l’extraction d’itemsets fréquents (l’approche FDM et deux variantes de l’approche GFM). Nous présentons aussi quelques nouvelles approches basées sur le clustering tels que l’approche multi-etage [4] et une version distribuée de DBSCAN [5]. 1.3.1 Techniques de distribution traditionnelles 1.3.1.1 Étude de performances de l’algorithme Apriori distribué La découverte de motifs fréquents est l’un des domaines majeurs du DM. A l’origine de ce domaine se trouvent les travaux d’Agrawal et Srikant (1994) [19] sur la découverte d’itemsets (ensemble d’items) fréquents. Le problème de la découverte d’itemsets fréquents consiste à considérer les transactions dans une base de données comme des listes d’items, d’utiliser un seuil de support minimal, noté, minsup et de sélectionner tous les itemsets dont le nombre d’apparition dans la base de données est supérieur à minsup. Ce problème est le plus simple dans le domaine de la découverte de motifs fréquents, comparativement à la recherche de séquences, d’arbres ou de graphes fréquents. Toutefois, il se retrouve dans de nombreuses Chapitre 2 Techniques de Data Mining distribuées 8 applications, en particulier dans l’analyse de données de vente d’entreprise commerciales. De plus, de part sa simplicité, toutes les améliorations algorithmiques significatives en découverte de motifs fréquents ont d’abord été réalisées dans le cas des itemsets fréquents avant d’être adaptées à des motifs plus complexes, c’est en particulier le cas pour la fermeture [20] ou les méthodes sans génération de candidats [21]. Nous allons nous concentrer sur les travaux qui traitent l’extraction d’itemsets fréquents dans un environnement distribué. L’approche GFM (Grid-based Frequent itemsets Mining) [8] à été proposée pour distribuer l’algorithme Apriori. Nous comparons cette approche avec l’approche distribuée classique FDM (A fast distributed algorithm for mining association rules). L’approche FDM est basée sur une stratégie d’élagage globale, contrairement à l’approche GFM qui est une amélioration de l’approche FDM du fait qu’elle est basée sur une stratégie d’élagage locale. Nous présentons ensuite une approche distribuée de l’algorithme qui traite l’hétérogénéité des données [13]. Avant de commencer l’étude de ces approches distribuées, nous présentons d’abord l’extraction d’itemsets fréquents par l’algorithme Apriori.

L’approche GFM (Grid-based Frequent itemsets Mining)

L’approche GFM est une amélioration de l’approche FDM du fait qu’elle est basée sur une stratégie d’élagage locale. Elle calcule la taille nécessaire k pour les itemsets fréquents localement dans chaque site sans l’échange des comptes support intermédiaire [8]. Tous les itemsets fréquents au niveau global sont déduits à la fin de la phase de calcul en tenant compte des : • Comptes support global collectés à partir des itemsets fréquents de taille k et tous les itemsets fréquents maximaux dans chaque nœud qui ne sont pas des sous ensembles d’autres itemsets fréquents de taille plus grande. • Sous ensembles d’itemsets fréquents localement qui échouent le test de fréquence global dans les étapes suivantes. Chapitre 2 Techniques de Data Mining distribuées 12 Les entrées de l’algorithme GFM sont le nombre de nœuds m, le seuil support global sw utilisé pour extraire les itemsets fréquents et l’ordre des itemsets k qu’on souhaite générer. Après avoir effectué le partitionnement horizontal de l’ensemble des transactions et l’affectation de chaque partition de données à un nœud local Ni {i=1,.., m}, chaque site local calcule les itemsets fréquents de taille k et envoie l’ensemble LLi aux autres sites. LLi représente les itemsets fréquents calculés localement dans le nœud Ni . L’ensemble LLi sera remplacé par l’ensemble des itemsets fréquents qui échouent le test global. Chaque site calcule les comptes support localement et les diffuse aux autres sites. Par la suite, chaque site va calculer l’ensemble Li qui représente l’ensemble des itemsets qui vérifient le test de fréquence global et aussi l’ensemble LLi. La sortie de l’algorithme est l’union des sous ensembles Li qui représente tous les itemsets fréquents d’ordre k désiré. L

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Liste des Acronymes
Table des matières
Table des figures
Liste des tableaux
INTRODUCTION GENERALE
Chapitre 1 : Techniques de Data Mining distribuées
1.1 Introduction
1.2 Motivations et domaines d’application du DDM
1.3 Les techniques de Data Mining distribuées
1.3.1 Techniques de distribution traditionnelles
1.3.1.1 Étude des performances de l’algorithme Apriori distribué
1.3.1.1.1 L’algorithme Apriori
1.3.1.1.2 L’extraction d’itemsets fréquents distribués
1.3.1.1.3 L’approche FDM
1.3.1.1.4 L’approche GFM
1.3.1.1.5 Evaluation et comparaison de FDM et GFM
1.3.1.1.6 L’extraction d’itemsets fréquents distribuée dans les
plateformes hétérogènes
1.3.2 Les nouvelles méthodes distribuées
1.3.2.1 Le clustering
1.3.2.2 L’approche Multi Etage
1.3.2.3 Distribution de l’algorithme DBSCAN
1.4 Conclusion
Chapitre 2 : Etude de l’algorithme de clustering OPTICS
2.1 Introduction
2.2 Motivation
2.3 L’ordre des clusters à base de densité
2.4 Identification de la structure de clustering
2.5 Définition formelle d’un cluster
2.6 Algorithme pour la détermination des clusters
2.6.1 L’algorithme naïf
2.6.2 Amélioration de l’algorithme naif
2.7 Conclusion
Table des matières
Chapitre 3 : Approche pour la distribution de l’algorithme OPTICS
3.1 Introduction
3.2 Le clustering local
3.3 Définition des modèles locaux
3.4 Détermination des bordures
3.5 Régénération des Clusters
3.6 Modèle de distribution
3.7 Modèles globaux3.8 Complexité de l’approche
3.9 Conclusion
Chapitre 4 : Evaluation et Expérimentation
4.1 Introduction
4.2 L’environnement de programmation
4.3 Implémentation
4.3.1 Implémentation de l’approche séquentiel
4.3.2 Détermination des clusters
4.3.3. Détermination des bordures
4.3.4. La régénération des bordures
4.3.5. La régénération des clusters
4.3.6. Résultats de l’exécution de l’algorithme OPTICS distribué
4.4 Evaluation des résultats
4.5 Conclusion
CONCLUSION GENERALE
REFERENCES BIBLIOGRAPHIQUES .

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *