DBSCAN | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

DBSCAN (density-based spatial clustering of applications with noise) est un algorithme de partitionnement de données proposé en 1996 par Martin Ester, Hans-Peter Kriegel, Jörg Sander et Xiaowei Xu. Il s'agit d'un algorithme fondé sur la densité dans la mesure qui s’appuie sur la densité estimée des clusters pour effectuer le partitionnement. thumb|400px|Les points A sont les points déjà dans le cluster. Les points B et C sont atteignables depuis A et appartiennent donc au même cluster. Le point N est une donnée aberrante puisque son epsilon voisinage ne contient pas de points dont l'epsilon voisinage contient MinPts points ou plus. L'algorithme DBSCAN utilise 2 paramètres : la distance et le nombre minimum de points devant se trouver dans un rayon pour que ces points soient considérés comme un cluster. Les paramètres d'entrées sont donc une estimation de la densité de points des clusters. L'idée de base de l'algorithme est ensuite, pour un point donné, de récupérer son -voisinage et de vérifier qu'il contient bien points ou plus. Ce point est alors considéré comme faisant partie d'un cluster. On parcourt ensuite l'-voisinage de proche en proche afin de trouver l'ensemble des points du cluster. DBSCAN(D, ε, MinPts) C = 0 pour chaque point P non visité des données D marquer P comme visité PtsVoisins = epsilonVoisinage(D, P, ε) si tailleDe(PtsVoisins) < MinPts marquer P comme BRUIT sinon C++ étendreCluster(D, P, PtsVoisins, C, ε, MinPts) étendreCluster(D, P, PtsVoisins, C, ε, MinPts) ajouter P au cluster C pour chaque point P' de PtsVoisins si P' n'a pas été visité marquer P' comme visité PtsVoisins' = epsilonVoisinage(D, P', ε) si tailleDe(PtsVoisins') >= MinPts PtsVoisins = PtsVoisins U PtsVoisins' si P' n'est membre d'aucun cluster ajouter P' au cluster C epsilonVoisinage(D, P, ε) retourner tous les points de D qui sont à une distance inférieure à ε de P Les points du jeu de données sont séparés en 3 types : Les points centraux (core points) Les points frontières (border points) Les points aberrants (noise points) Un point du jeu de données est dit central si : Son voisinage est dense Ces points forment des composantes connexes indépendantes de l'ordre d'exploration du jeu de données.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (44)

Personnes associées (4)

Unités associées (11)

Concepts associés (3)

Cours associés (13)

Séances de cours associées (42)

K-moyennes

Le partitionnement en k-moyennes (ou k-means en anglais) est une méthode de partitionnement de données et un problème d'optimisation combinatoire. Étant donnés des points et un entier k, le problème est de diviser les points en k groupes, souvent appelés clusters, de façon à minimiser une certaine fonction. On considère la distance d'un point à la moyenne des points de son cluster ; la fonction à minimiser est la somme des carrés de ces distances.

Partitionnement de données

vignette|upright=1.2|Exemple de clustering hiérarchique. Le partitionnement de données (ou data clustering en anglais) est une méthode en analyse des données. Elle vise à diviser un ensemble de données en différents « paquets » homogènes, en ce sens que les données de chaque sous-ensemble partagent des caractéristiques communes, qui correspondent le plus souvent à des critères de proximité (similarité informatique) que l'on définit en introduisant des mesures et classes de distance entre objets.

Regroupement hiérarchique

Dans le domaine de l'analyse et de la classification automatique de données, le regroupement hiérarchique est un partitionnement de données ou clustering, au moyen de diverses méthodes, dites « ascendantes » et « descendantes ». Les méthodes dites « descendantes » partent d’une solution générale vers une autre plus spécifique. Les méthodes de cette catégorie démarrent avec une seule classe contenant la totalité puis se divisent à chaque étape selon un critère jusqu’à l’obtention d’un ensemble de classes différentes.

CIVIL-226: Introduction to machine learning for engineers

Machine learning is a sub-field of Artificial Intelligence that allows computers to learn from data, identify patterns and make predictions. As a fundamental building block of the Computational Thinki

CS-401: Applied data analysis

This course teaches the basic techniques, methodologies, and practical skills required to draw meaningful insights from a variety of data, with the help of the most acclaimed software tools in the dat

MICRO-455: Applied machine learning

Real-world engineering applications must cope with a large dataset of dynamic variables, which cannot be well approximated by classical or deterministic models. This course gives an overview of method

Recovering Static and Time-Varying Communities Using Persistent Edges

Maximilien Claude Robert Dreveton

This article focuses on spectral methods for recovering communities in temporal networks. In the case of fixed communities, spectral clustering on the simple time-aggregated graph (i.e., the weighted graph formed by the sum of the interactions over all tem ...

Ieee Computer Soc2024

Characterizing the genetic structure of large cohorts has become increasingly important as genetic studies extend to massive, increasingly diverse biobanks. Popular methods decompose individual genomes into fractional cluster assignments with each cluster ...

SPRINGERNATURE2023

Single-Trace Clustering Power Analysis of the Point-Swapping Procedure in the Three Point Ladder of Cortex-M4 SIKE

Aymeric Genet, Novak Kaluderovic

In this paper, the recommended implementation of the post-quantum key exchange SIKE for Cortex-M4 is attacked through power analysis with a single trace by clustering with the k-means algorithm the power samples of all the invocations of the elliptic curve ...

Springer, Cham2022

Prédire les précipitations: Miniprojet BIO-322

Introduit un mini-projet où les étudiants prédisent les précipitations à Pully en utilisant l'apprentissage automatique, en mettant l'accent sur la reproductibilité et la qualité du code.

Scène sémantique ouverte : SCIM

Présente le SCIM pour la compréhension de la scène sémantique du monde ouvert par regroupement, inférence et cartographie.

Méthodes de regroupement

Couvre les méthodes de regroupement des moyennes K, hiérarchiques et DBSCAN avec des exemples pratiques.