Fonctionnement de l’agrégation basée sur la densité

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. Le cas échéant, la période temporelle des points peut être utilisée pour rechercher des groupes de points s’agrégeant dans l’espace et le temps.

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.

Conseil :

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’outil 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

Le paramètre Méthodes d’agrégation de l’outil Agrégation basée sur la densité fournit trois options à 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. Cette méthode vous permet également d’utiliser les paramètres Champ temporel et Intervalle temporel de recherche pour rechercher des agrégats de points dans l’espace et le temps.
• 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-échelles (OPTICS) : 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. Cette méthode vous permet également d’utiliser les paramètres Champ temporel et Intervalle temporel de recherche pour rechercher des agrégats de points dans l’espace et le temps.

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

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 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 Nombre minimum d’entités par agrégat est petit, plus le nombre d’agrégats détectés est important. Plus le Nombre minimum d’entités par agrégat est grand, moins le nombre d’agrégats détectés est important.

Conseil :

Le Nombre minimum d’entités par agrégat 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 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. La distance principale est liée au paramètre Distance de recherche, lequel est utilisé à la fois par les méthodes Distance définie (DBSCAN) et Multi-échelles (OPTICS).

Illustration de la distance principale, mesurée en tant que distance depuis une entité spécifique devant être rejointe pour créer un agrégat comprenant un minimum de 4 entités (incluant l’entité spécifique).

Distance de recherche (DBSCAN et OPTICS)

Pour Distance définie (DBSCAN), si la valeur du paramètre Entités minimum par agrégat se trouve dans la Distance de recherche à partir d’un point spécifique, ce point est marqué comme point principal et inclus dans un cluster, ainsi que tous les points situés dans la distance principale. Un point de limite est un point situé dans la distance de recherche d’un point principal mais ne contenant pas lui-même le nombre minimal d’entités dans la distance de recherche. Chaque agrégat résultant est composé de points principaux et de points de limite, où les points principaux ont tendance à se retrouver au milieu du cluster et les points de limite à l’extérieur. Si un point ne possède pas le nombre minimum d’entités dans la distance de recherche et ne se situe pas dans la distance de recherche d’un autre point principal (en d’autres termes, si ce point n’est ni un point principal, ni un point de limite), il est marqué comme un point de bruit et n’est inclus dans aucun agrégat.

Agrégation de 4 entités minimum par agrégat. Le point principal possède 4 voisins situés dans la distance de recherche (y compris lui-même). Le point de limite ne possède que 3 entités dans la distance de recherche mais, étant voisin d’un point principal, il est inclus dans l’agrégat. Le point de bruit ne possède pas 4 entités dans la distance de recherche et, n’étant pas voisin d’un point principal, il n’est pas inclus dans l’agrégat.

Pour Multi-échelles (OPTICS), la valeur Distance de recherche est traitée comme étant la distance maximum qui sera comparée à la distance principale. La valeur Multi-échelles (OPTICS) utilise un concept de distance d’accès minimum, qui est la distance d’un point jusqu’à son voisin le plus proche n’ayant pas encore été visité par la recherche. (Remarque : OPTICS est un algorithme ordonné qui commence avec l’entité ayant l’ID le plus bas et s’exécute de ce point au point suivant pour créer un diagramme. L’ordre des points est fondamental pour les résultats.) La valeur Multi-échelles (OPTICS) recherche toutes les distances voisines dans les limites de la Distance de recherche spécifiée, en comparant chacune d’elle à la distance principale. 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. S’il n’y a pas d’autres points dans la distance de recherche, le processus redémarre à un nouveau point n’ayant pas été précédemment visité. À chaque itération, les distances d’accès sont recalculées et triées. La plus petite des distances est utilisée pour la distance d’accès finale de chaque point. Ces distances d’accès 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.

Lorsque toutes les entités se trouvant dans les limites de la distance principale ont été visitées, la distance d’accès assignée à une entité correspond à la plus petite distance entre l’entité sélectionnée et toutes les autres entités comprises dans la Distance de recherche.

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).

Agrégation dans l’espace et le temps (DBSCAN et OPTICS)

Dans deux des méthodes d’agrégation, la période temporelle de chaque point peut être spécifiée via le paramètre Champ temporel. Si ce paramètre est spécifié, l’outil recherche les agrégats de points proches les uns des autres dans l’espace et le temps. Le paramètre Intervalle temporel de recherche est analogue à la distance de recherche et est utilisé pour déterminer les points principaux, les points de limite et les points de bruit des agrégats spatio-temporels.

Pour l’option Distance définie (DBSCAN), lors de la recherche de membres d’agrégat, la valeur du paramètre Entités minimum par agrégat doit figurer dans les valeurs Distance de recherche et Intervalle temporel de recherche pour former un point principal d’un agrégat spatio-temporel.

Dans l’image suivante, la distance de recherche est de 1,6 kilomètre, l’intervalle temporel de recherche de 3 jours et le nombre minimum d’entités de 4. Le point P est un point principal car il existe 4 points dans la distance de recherche et l’intervalle temporel (y compris lui-même). Le point Q est un point de limite car il n’y a que 3 points dans la distance de recherche et l’intervalle temporel, mais il se trouve dans la distance de recherche et l’intervalle temporel d’un point principal d’un agrégat (le point ayant pour horodatage 05/01/2021) Les points C et D sont des points de bruit car ils ne sont ni des points principaux, ni des points de limite de l’agrégat, et tous les autres points (y compris P et Q) forment un seul agrégat.

Pour l’option Multi-échelles (OPTICS), tous les points figurant en dehors de la plage Intervalle temporel de recherche d’un point sont exclus lorsque le point calcule sa distance principale, recherche toutes les distances voisines dans la valeur Distance de recherche spécifiée et calcule la distance d’accès.

Dans l’image suivante, la distance de recherche est de 3,2 kilomètres, l’intervalle temporel de recherche de 3 jours et le nombre minimum d’entités de 4. La distance principale pour le point P est calculée en ignorant le point q3 car il se trouve en dehors de l’intervalle temporel de recherche. Dans ce cas, la distance principale du point P est égale à la distance d’accès du point P.

L’image suivante illustre le calcul de la distance d’accès lorsque des points voisins ont déjà été visités. Les points q1, q2 et q4 ont été ignorés car ils ont été précédemment visités, et les points q3 et q5 car ils se trouvent en dehors de la fenêtre horaire de recherche.

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.

Distances d’accès à partir des pics et des vallées dans le diagramme d’accès. Lorsque des distances plus importantes sont mesurées entre des points, un pic se forme sur le diagramme d’accès.

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 très faible (proche de 0) traite uniquement les pics les plus abrupts et élevés en tant que séparation entre les agrégats, ce qui a pour conséquence un nombre d’agrégats plus faible.

Sensibilité d’agrégat faible et Sensibilité d’agrégat élevée

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.

Diagramme d’accès conceptuel avec des agrégats de points de densités et de distances variables entre eux.

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 dessous de la Distance de recherche représentent les agrégats tandis que les pics situés au-dessus de la Distance de recherche représentent les points de bruit. La méthode Distance définie (DBSCAN) est la plus rapide des méthodes d’agrégation, mais n’est appropriée que s’il existe une Distance de recherche très claire à utiliser comme limite, et cette Distance de recherche s’applique bien à tous les agrégats. Ceci requiert que tous les agrégats significatifs aient des densités similaires.

Illustration de la Distance de recherche dans l’algorithme DBSCAN

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.

Illustration des niveaux hiérarchiques utilisés par l’algorithme HDBSCAN pour trouver les agrégats permettant d’optimiser la stabilité

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.

Illustration de l’intensité des pics dans le diagramme d’accès

Lorsque vous choisissez une 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).

Illustration de l’impact d’une Sensibilité d’agrégat élevée utilisée avec l’algorithme OPTICS et les agrégats correspondants

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.

Illustration de l’impact d’une Sensibilité d’agrégat modérée utilisée avec l’algorithme OPTICS et les agrégats correspondants

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.

Illustration de l’impact d’une Sensibilité d’agrégat faible utilisée avec l’algorithme OPTICS et les agrégats correspondants

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 sont attribuées et répétées de sorte que chaque agrégat se distingue visuellement des agrégats environnants.

Si la Méthode d’agrégation choisie est Ajustement automatique (HDBSCAN), 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 permettant de 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 dans la fenêtre 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 :

• Birant, D. & Kut, A. (janvier 2007). « ST-DBSCAN: An algorithm for clustering spatial–temporal data. » Dans Data & Knowledge Engineering (Vol 60, No. 1, pp. 208-221). https://doi.org/10.1016/j.datak.2006.01.013
• 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 :

• Agrawal, K. P., Garg, S., Sharma, S., & Patel, P. (novembre 2016). « Development and validation of OPTICS based spatio-temporal clustering technique. » Dans Information Sciences (Vol 369, pp. 388-401). https://doi.org/10.1016/j.ins.2016.06.048.
• 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.