Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Travail de session : Mémoire Le clustering de données Par Nicolas Sola & Mathie

Travail de session : Mémoire Le clustering de données Par Nicolas Sola & Mathieu Schmitt Résumé Le travail du clustering consiste à regrouper les données en classe ; nous obtenons par ce biais une forte similarité intra-classe et une faible similarité inter-classe. Un nombre conséquent d’algorithmes nous sont présentés avec leurs avantages mais aussi leurs inconvénients. De ce fait, la présence d’un utilisateur expert capable de jugement objectif est fortement recommandée pour le choix des dimensions signiﬁcatives et l’analyse des résultats. D’une manière schématique, nous catégorisons les algorithmes de clustering autour de plusieurs méthodes : hiérarchique, par partition, basée sur la densité et sur les grilles. Les algorithmes sont entre autres usités pour pallier à des problématiques récurrentes telles que le traitement des données bruitées ou la gestion des objets à haute dimension. Nous ne méprenons pas sur l’importance de ces données bruitées qui peuvent en eﬀet compromettre signiﬁcativement la qualité des clusters. Elles inﬂuent directement sur les performances et le fonctionnement des algorithmes, qui plus est, sur la précision des clusters créés. La haute dimensionnalité des données (> 10 dimensions) enlève toute utilité aux mesures de distance et apportent aux objets une relative équidistance les uns par rapport aux autres. Nous adoptons la méthode du clustering par sous-espace comme solution à la problématique rencontrée. Ce genre de clustering se divise autour : – De méthodes de recherche ascendante qui utilisent celles basées sur la densité, les grilles statiques ou adaptatives, – De méthodes itératives de recherche descendante qui aﬀectent des coeﬃcients de pon- dération aux dimensions. Mots-clés : Clustering de données, réduction du bruit, haute-dimensionnalité des données, clustering hiérarchique, clustering par partition, clustering basé sur la den- sité, clustering basé sur les grilles Introduction Mise en contexte Clustering, apprentissage non supervisé ou regroupement automatique sont des expressions similaires auxquelles nous devons nous familiariser ; elles convergent toutes dans la même di- rection et font référence à des méthodes qui se singularisent par : un regroupement de données issues elles-mêmes d’un ensemble de données, en groupes homogènes inconnus initialement, en fonction de leur similarité. Les techniques de clustering voient leur intérêt se décupler très rapidement. Leurs appli- cations progressives sont très porteuses et se retrouvent aujourd’hui en nombre incalculable dans maints domaines. Nous pouvons citer par exemple l’analyse de données économiques qui permet de segmenter un marché ou proﬁler des clients, la classiﬁcation et catégorisation de documents sur le Web, la reconnaissance de formes et le traitement d’images,...// Posons-nous à présent la question pertinente suivante et tentons d’y répondre : quelles sont les raisons pour lesquelles ces techniques novatrices ont fait leur apparition ? La réponse que nous apportons fait preuve de bon sens. Depuis l’apparition de l’informa- tique, nous sommes confrontés à une croissance eﬀrénée de la quantité de données stockées dans le monde entier. Ces données se retrouvent sous formes diverses et variées et constituent un gigantesque vivier où l’Homme vient puiser des informations et des connaissances pour en ti- rer le meilleur proﬁt. Une analyse manuelle relève dès lors de l’impossible et au vu de ce constat, l’Homme crée des techniques de recherche, d’analyses de données de plus en plus performantes. Une idée prédomine désormais : regrouper des données et en soustraire des connaissances . Tout pense à croire que cette idée est en relation avec l’instinct primaire de l’Homme qui par son comportement obéit à la logique aristotélicienne, celle qui "aime" tout catégoriser. Et pour cause, "Aristote n’a pas vécu sous l’ère informatique certes, cependant nous lui de- vons les premières classiﬁcations hiérarchiques systématiques des connaissances et des concepts. S’inspirait-il des divisions utilisées pour l’organisation des armées ? Cette hypothèse nous semble plus que probable."[17]. Déﬁnition Nous utilisons de nos jours les techniques de clustering pour la découverte de groupes incon- nus parmi certains ensembles de données. La classiﬁcation peut être considérée comme une ﬁn en soi, néanmoins elle est très eﬃcace comme outil de pré-traitement et accepter par d’autres i méthodes de fouille de données. Figure 1: Étapes du datamining Dans le cadre d’une analyse complète de datamining, l’utilisation du clustering durant la phase de fouille de données s’avère bien judicieuse. Argumentons : le seul fait de pratiquer à un regroupement des données en fonction de leur similarité peut faire apparaître des "motifs" utiles qui viennent alimenter nos connaissances. Cette alternative sied parfaitement à des méthodes telles que : l’association, la récapitulation, la régression dans les cas d’absence de classement des données avec cependant possibilité de détecter des similarités entre ces données. ii Problématiques Nous utilisons dans notre vie quotidienne diﬀérentes méthodes de classement pour nos ob- jets ; il en va de même pour les algorithmes de clustering. L’article "Data Clustering : A review [8]" révèle qu’il "n’existe pas de techniques de clustering de données universellement applicables puisque nous sommes en présence d’une grande variété de structures multidimensionnelles de données.". Cette aﬃrmation nous conduit à ces deux questions : Quelles méthodes sont actuellement proposées ? Quelles sont leur spéciﬁcité respective ? Nous sommes amenés par ailleurs à œuvrer sur des ensembles de données potentiellement complexes avec plusieurs dimensions ou des ensembles contenants des données bruitées (des données parasites). Dès lors, des interrogations apparaissent : – Que signiﬁe la haute dimensionnalité des données ? – Quelles sont les techniques appropriées dans la gestion de ce problème ? – Quels sont les impacts occasionnés par les données bruitées sur une analyse de données ? – De quelle manière les algorithmes de clustering réagissent-ils face au bruit ? – A quelles méthodes faisons-nous appel pour l’élimination de ce "bruit" dans un ensemble de données ? Nous développerons principalement les réponses apportées à ces deux dernières questions et cernerons les problématiques qui en découlent. Nous souhaitons à toutes et à tous une bonne lecture, et de ne pas être : "Celui qui se perd dans ce qu’il lit, mais celui qui s’y trouve" Paul Valéry. iii Table des matières Introduction iii Mise en contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Déﬁnition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Problématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Table des matières iv 1 Méthodes de clustering 1 1.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Hiérarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Méthodes agglomératives et divisives . . . . . . . . . . . . . . . . . . 5 1.2.3 Méthodes de mesure entre deux clusters . . . . . . . . . . . . . . . . 6 1.2.4 Algorithme BIRCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.2 Fonctionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.3 Les méthodes heuristiques . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Autres méthodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4.1 Méthode s’appuyant sur la densité . . . . . . . . . . . . . . . . . . uploads/Management/clustering.pdf