L’outil Agrégation basée sur la densité détecte les zones où les points sont concentrés et celles où les points sont séparés par des zones vides ou clairsemées. Les points ne faisant pas partie d’un agrégat sont classés comme bruit.
Cet outil utilise les algorithmes d’agrégation d'entraînement machine non assistés qui détectent automatiquement les modèles basés purement sur la localisation géographique et la distance par rapport à un nombre de voisins spécifié. Ces algorithmes sont considérés non assistés puisqu'ils ne requièrent aucune formation sur ce que signifie la notion d’agrégat.
Astuce :
Les techniques d’agrégation, de regroupement et de classification font partie des méthodes les plus utilisées dans l’apprentissage automatique. Les outils d’agrégation multivariée et d’agrégation multivariée spatialement contrainte utilisent également des méthodes d’apprentissage automatique non assistées pour déterminer les agrégats naturels dans vos données. Ces méthodes de classification sont considérées non assistées car elles n'exigent aucun ensemble d’entités pré-classées pour guider ou entraîner la recherche d’agrégats dans vos données.
Applications possibles
Voici quelques exemples d’application de cet outil :
- Les réseaux urbains de distribution d’eau constituent des infrastructures importantes cachées sous terre. Un agrégat de ruptures et d’éclatements de canalisation peut indiquer l’imminence de problèmes plus importants. L’outil d’agrégation basée sur la densité peut permettre à un ingénieur d’identifier où se trouvent ces agrégats et de prendre des actions préventives adaptées dans les zones du réseau de distribution d’eau qui présentent un risque élevé.
- Supposons que vous disposiez des données de position pour tous les tirs réussis et ratés des joueurs de NBA. L’agrégation basée sur la densité peut vous permettre de voir les positions de tirs réussis et ratés pour chaque joueur. Cette information peut ensuite être utilisée afin de construire une stratégie de jeu.
- Imaginons que vous étudiez une maladie parasitaire et que vous disposez d’un jeu de données représentant les ménages dans votre zone d’étude, certains d’entre eux étant touchés, et d’autres non. L’outil d’agrégation basée sur la densité vous permet de déterminer quels sont les plus importants agrégats de ménages infestés pour vous aider à localiser une zone où commencer le traitement et exterminer les parasites.
- Les tweets de géolocalisation suite à une catastrophe naturelle ou à une attaque terroriste peuvent être agrégés ce qui permet d’organiser les opérations de secours et d’évacuation en fonction de la taille et de l’emplacement des agrégats identifiés.
Méthodes d’agrégation
L’outil agrégation basée sur la densité fournit trois Clustering Methods (Méthodes d’agrégation) différentes à l'aide desquelles trouver des agrégats dans vos données ponctuelles :
- Defined distance (DBSCAN) [Distance définie] — utilise une distance spécifiée pour séparer les agrégats denses du bruit plus clairsemé. L’algorithme DBSCAN représente la méthode d’agrégation la plus rapide, mais cette méthode n’est appropriée que s’il existe une Search Distance (Distance de recherche) très claire à utiliser, et qui s’applique bien à tous les agrégats potentiels. Ceci requiert que tous les agrégats significatifs aient des densités similaires.
- Self-adjusting (HDBSCAN) [Ajustement automatique] — utilise une plage de distances pour séparer les agrégats de diverses densités du bruit plus clairsemé. L’algorithme HDBSCAN est la méthode d’agrégation la plus axée sur les données, et de ce fait celle nécessitant le moins d’informations saisies par l’utilisateur.
- Multi-scale (OPTICS) [Echelles multiples] — utilise la distance entre des entités voisines pour créer un diagramme d’accès lequel est ensuite utilisé pour séparer les agrégats de densités diverses du bruit. L’algorithme OPTICS est celui qui offre le plus de flexibilité pour affiner les agrégats détectés, bien que cela sollicite d’importantes ressources de calcul, particulièrement lorsque la Search Distance (Distance de recherche) est importante.
Cet outil prend les Input Point Features (Entités points en entrée), un chemin d'accès aux Output Features (Entités en sortie) et une valeur représentant le nombre minimum d’entités requis pour considérer qu’il s'agit d’un agrégat. En fonction de la Clustering Method (Méthode d’agrégation) sélectionnée, il peut être nécessaire de spécifier des paramètres supplémentaires, comme cela est décrit ci-dessous.
Nombre minimum d’entités par agrégat (requis pour toutes les méthodes)
Ce paramètre détermine le nombre minimum d’entités requis pour considérer qu’un regroupement de points est un agrégat. Par exemple, si vous avez plusieurs agrégats différents, dont la taille varie de 10 points à 100 points, et que vous définissez le Minimum Features per Cluster (Nombre minimum d’entités par agrégat) à 20, tous les agrégats composés de moins de 20 points seront soit considérés comme du bruit (puisqu’ils ne forment pas un regroupement suffisamment important pour considérer qu’il s’agit d’un agrégat), soit fusionnés avec les agrégats à proximité afin de satisfaire l’exigence du nombre d’entités requis. En revanche, en choisissant un nombre minimum d’entités par agrégat (Minimum Features Per Cluster) plus petit que ce vous considérez être le plus petit agrégat représentatif peut conduire à diviser des agrégats significatifs en agrégats plus petits. En d’autres termes, plus le Minimum Features Per Cluster (Nombre minimum d’entités par agrégat) est petit, plus le nombre d'agrégats détectés sera important. Plus le Minimum Features Per Cluster (Nombre minimum d’entités par agrégat) sera grand, moins le nombre d’agrégats détectés sera important.
Astuce :
Le nombre minimum d’entités par agrégat (Minimum Features Per Cluster) idéal dépend de ce que vous essayez de capturer et de votre question d’analyse. Il devrait correspondre à la plus petite taille de regroupement que vous souhaitez considérer comme un agrégat représentatif. En augmentant le Minimum Features Per Cluster (Nombre minimum d’entités par agrégat) vous prenez le risque de faire fusionner certains des agrégats de plus petite taille.
Le paramètre Minimum Features Per Cluster (Nombre minimum d’entités par agrégat) est également important pour le calcul de la distance principale, laquelle est une mesure utilisée par les trois méthodes de recherche d’agrégats. D’un point de vue conceptuel, la distance principale de chaque point, est une mesure de la distance requise pour se rendre de chaque point jusqu’au nombre minimum d’entités défini. Ainsi, si le Minimum Features per Cluster (Nombre minimum d’entités par agrégat) est élevé, la distance principale correspondante sera plus grande. Si le Minimum Features per Cluster (Nombre minimum d’entités par agrégat) est faible, la distance principale correspondante sera plus petite. En bordure des agrégats, les points auront des distances principales importantes (et probablement n’entrant pas dans un agrégat). La distance principale, est liée au paramètre Search Distance (Distance de recherche), lequel est utilisé à la fois par les méthodes Defined distance (DBSCAN) [Distance définie] et Multi-scale (OPTICS) [Echelles multiples].
Distance de recherche (DBSCAN et OPTICS)
Dans le cas de la Defined distance (DBSCAN) [Distance définie], lorsque le Minimum Features per Cluster (Nombre minimum d’entités par agrégat) ne peut être trouvé dans la Search Distance (Distance de recherche) depuis un point donné, ce point est marqué comme bruit. En d’autres termes, si la distance principale (la distance requise pour atteindre le nombre minimum d’entités) pour une entité est supérieure à la Search Distance (Distance de recherche), le point est marqué comme bruit. La Search Distance (Distance de recherche), lors de l’utilisation de la Defined distance (DBSCAN) [Distance définie], est traitée comme une limite de recherche.
Pour Multi-scale (OPTICS) [Echelles multiples], la Search Distance (Distance de recherche) est traitée comme étant la distance maximum qui sera comparée à la distance principale. Multi-scale (OPTICS) [Échelles multiples] utilise un concept de distance d’accès maximum, laquelle correspond à la distance entre un point et son voisin le plus proche n’ayant pas encore été visité par la recherche (Remarque : OPTICS est un algorithme ordonné commençant par l’entité se trouvant à OID 0 et continuant depuis ce point jusqu’au suivant pour créer un diagramme. L’ordre des points est fondamental pour les résultats). Multi-scale (OPTICS) [Echelles multiples] recherche toutes les distances voisines dans les limites de la Search Distance (Distance de recherche) spécifiée, en comparant chacune d’elle à la distance de recherche. Lorsqu’une distance est inférieure à la distance principale, cette distance principale est assignée à l’entité comme distance d’accès. Lorsque toutes les distances sont supérieures à la distance principale, la plus petite de ces distances est assignée comme distance d’accès. Ces distances sont ensuite utilisées pour créer le diagramme d’accès, lequel est un diagramme ordonné des distances d’accès utilisées pour détecter les agrégats.
Pour les algorithmes Defined distance (DBSCAN) [Distance définie] et Multi-scale (OPTICS) [Echelles multiples], lorsque aucune distance n’est spécifiée, la Search Distance (Distance de recherche) par défaut équivaut à la distance principale la plus élevée trouvée dans le jeu de données, à l’exclusion des distances principales appartenant au 1 % supérieur (en d’autres termes à l’exclusion des distances principales les plus extrêmes).
Diagramme d’accès (OPTICS)
Lorsque toutes les distances d’accès ont été calculées pour la totalité du jeu de données, un diagramme d’accès est construit qui ordonne les distances et révèle la structure d’agrégation des points.
Les dépressions du diagramme d’accès signifient qu’une faible distance doit être parcourue d’un point à un autre. De ce fait, les dépressions représentent des agrégats distincts dans le modèle de points. Plus un agrégat est dense, plus les distances d'accès sont réduites, et plus la dépression est faible sur le diagramme (l’agrégat rose par exemple est le plus dense dans l’exemple ci-dessus). Les agrégats moins denses ont des distances d'accès plus élevées et des dépressions plus importantes sur le diagramme (l’agrégat vert foncé par exemple est le moins dense dans l’exemple ci-dessus). Les pics représentent les distances devant être parcourues d’un agrégat à un autre, ou d’un agrégat à un bruit et à nouveau vers un agrégat, selon la configuration de l’ensemble de points.
Les plateaux dans un diagramme d’accès se forment lorsque la distance de recherche (option Search Distance) est inférieure à la distance principale la plus élevée. Un aspect fondamental de l’utilisation d’une méthode d’agrégation OPTICS consiste à déterminer les agrégats depuis le diagramme d’accès, ce qui est obtenu en utilisant le paramètre de Cluster Sensitivity (Sensibilité d’agrégat).
Cluster Sensitivity (Sensibilité d’agrégat) (OPTICS)
Le paramètre Cluster Sensitivity (Sensibilité d’agrégat) détermine de quelle manière la forme (à la fois la pente et la hauteur) des pics dans le diagramme d’accès sera utilisée pour séparer les agrégats. Une Cluster Sensitivity (Sensibilité d’agrégat) très élevée (proche de 100) traitera même les plus petits pics en tant que séparation entre les agrégats, ce qui aura pour conséquence un nombre d’agrégats plus important. Une sensibilité d’agrégat (Cluster Sensitivity) très faible (proche de 0) traitera uniquement les pics les plus abrupts et élevés en tant que séparation entre les agrégats, ce qui aura pour conséquence un nombre d’agrégats plus faible.
La Cluster Sensitivity (Sensibilité d’agrégat) par défaut est calculée comme étant le seuil à partir duquel l’ajout d’agrégats supplémentaires n’apporte pas d’informations supplémentaires, ceci est effectué en utilisant la divergence de Kullback-Leibler entre le diagramme d’accès d’origine et le diagramme d’accès lissé obtenu après agrégation.
Comparaison des méthodes
Alors que seul l’algorithme Multi-scale (OPTICS) [Echelles multiples] utilise le diagramme d’accès pour détecter les agrégats, le diagramme peut être utilisé pour aider à expliquer, de manière conceptuelle la façon dont ces méthodes diffèrent les unes des autres. À titre d’exemple, le diagramme d’accès ci-dessous sera utilisé pour expliquer les différences entre ces 3 méthodes. Le diagramme révèle des agrégats de densité et distance de séparation variées. Nous explorerons les résultats de l’utilisation de chacune des méthodes d’agrégation dans cet exemple.
Pour l’algorithme Defined distance (DBSCAN) [Distance définie], vous pouvez considérer de tracer une ligne à travers le diagramme d’accès à la Search Distance (Distance de recherche) spécifiée. Les zones situées en deçà de la distance de recherche (option Search Distance) représentent des agrégats alors que les pics situés au-delà de la distance de recherche (option Search Distance) représentent des points de bruit. La Defined distance (DBSCAN) [Distance définie] représente la méthode d’agrégation la plus rapide, mais cette méthode n’est appropriée que s’il existe une Search Distance (Distance de recherche) très claire à utiliser comme limite, et cette Search Distance (Distance de recherche) s’applique bien à tous les agrégats potentiels. Ceci requiert que tous les agrégats significatifs aient des densités similaires.
Pour l’algorithme Self-adjusting (HDBSCAN) [Ajustement automatique], les distances d’accès peuvent être pensées comme des niveaux imbriqués d’agrégats. Chaque niveau d’agrégation aurait pour résultat la détection d’un ensemble d’agrégat différent. L’algorithme Self-adjusting (HDBSCAN) [Ajustement automatique] choisit quel niveau d’agrégat dans chaque série d’agrégats imbriqués créera de manière optimale les agrégats les plus stables intégrant le plus grand nombre possible de membres sans intégrer de bruit. Pour plus d'information sur l’algorithme, consultez l’excellente documentation des créateurs de HDBSCAN. L’algorithme Self-adjusting (HDBSCAN) [Ajustement automatique] est la méthode d’agrégation la plus axée sur les données, et de ce fait celle nécessitant le moins d’informations saisies par l’utilisateur.
Pour l’algorithme Multi-scale (OPTICS) [Echelles multiples], le travail consistant à détecter les agrégats ne repose pas sur une distance particulière, mais sur les pics et dépressions dans le diagramme. Imaginons que chaque pic puisse être classé selon son niveau Petit, Moyen, ou Grand.
Lorsque vous choisissez une Cluster Sensitivity (Sensibilité d’agrégat) très élevée, tous les pics, des petits aux grands, agissent comme des séparations entre les agrégats (augmentant ainsi le nombre d’agrégats).
Choisir une Cluster Sensitivity (Sensibilité d’agrégat) modérée entraînera l’utilisation des pics moyens et grands, mais pas des petits pics.
Lorsque vous choisissez une Cluster Sensitivity (Sensibilité d’agrégat) très faible, seuls les grands pics sont utilisés, ce qui a pour conséquence un très faible nombre d’agrégats détectés.
L'algorithme Multi-scale (OPTICS) [Echelles multiples] est celui qui offre le plus de flexibilité pour affiner les agrégats détectés. C’est aussi la plus lente des trois méthodes d’agrégation.
Résultats
Cet outil produit une classe d'entités en sortie avec un nouveau champ d’entier CLUSTER_ID vous indiquant à quel agrégat appartient chaque entité. Le rendu par défaut dépend du champ COLOR_ID. Une couleur différente sera assignée à chaque agrégat. Les couleurs seront assignées et répétées de sorte que chaque agrégat soit visuellement distinct des agrégats voisins.
Si la méthode d’agrégation (Clustering Method) choisie est Self-adjusting (HDBSCAN) [Ajustement automatique], la classe d’entités en sortie contient également les champs PROB, ce qui correspond à la probabilité que l’entité appartienne au groupe qui lui est assigné, OUTLIER, ce qui désigne le fait que l’entité est peut-être un point aberrant dans son propre agrégat (lorsque la valeur est élevée, l’entité a plus de chances d’être un point aberrant) et EXEMPLAR, ce qui désigne les entités les plus prototypiques ou les plus représentatives de chaque agrégat.
Cet outil crée également des messages et des diagrammes pour vous aider à comprendre les caractéristiques des agrégats identifiés. Vous pouvez accéder aux messages en pointant sur la barre de progression, en cliquant sur le bouton contextuel et en développant la section Messages (Messages) dans la fenêtre Geoprocessing (Géotraitement). Vous pouvez également accéder aux messages d'une précédente exécution de l'outil Agrégation basée sur la densité via l'historique du géotraitement. Les diagrammes créés sont accessibles dans depuis la fenêtre Contents (Contenu).
Outre le diagramme d’accès créé lorsque l’algorithme Multi-scale (OPTICS) [Échelles multiples] est choisi, toutes les méthodes d’agrégation créent également un diagramme à barres affichant tous les ID uniques d’agrégats. Ce diagramme peut être utilisé pour sélectionner facilement toutes les entités contenues dans un agrégat spécifié, et pour explorer la taille de chacun des agrégats.
Ressources supplémentaires
Pour plus d’informations sur l’algorithme DBSCAN :
- Ester, M., Kriegel, H. P., Sander, J., & Xu, X. (août 1996). A density-based algorithm for discovering clusters in large spatial databases with noise. Dans Kdd (Vol. 96, No. 34, pp. 226-231).
Pour plus d’informations sur l’algorithme HDBSCAN :
- Campello, R. J., Moulavi, D., & Sander, J. (avril 2013). Density-based clustering based on hierarchical density estimates. Dans Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 160-172). Springer, Berlin, Heidelberg.
Pour plus d’informations sur l’algorithme OPTICS :
- Ankerst, M., Breunig, M. M., Kriegel, H. P., & Sander, J. (juin 1999). OPTICS: ordering points to identify the clustering structure. Dans ACM Sigmod record (Vol. 28, No. 2, pp. 49-60). ACM.
Vous avez un commentaire à formuler concernant cette rubrique ?