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 de Machine Learning non assistés qui détectent automatiquement les modèles basés uniquement 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 comptent parmi les méthodes les plus utilisées dans l’apprentissage automatique. Les outils Agrégation multivariée et Agrégation multivariée spatialement contrainte utilisent également des méthodes de Machine Learning non assistées pour déterminer les agrégats naturels dans les données. Ces méthodes de classification sont considérées comme non assistées, car elles n’exigent aucun jeu d’entités préclassées pour guider ou entraîner la méthode de recherche d’agrégats dans les 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 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 la localisation 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é propose trois options qui permettent de trouver des agrégats dans les 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 est la méthode d’agrégation la plus rapide, mais cette méthode n’est appropriée que s’il existe une 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 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 exige une valeur représentant le nombre minimum d’entités requises pour considérer qu’il s’agit d’un agrégat. En fonction de la méthode d’agrégation sélectionnée, il peut être nécessaire de spécifier des paramètres supplémentaires, comme indiqué ci-après.

Nombre minimal 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 entre 10 points et 100 points, et que vous définissez la valeur du paramètre Nombre minimal d’entités par agrégat sur 20, tous les agrégats comportant moins de 20 points sont soit considérés comme du bruit (puisqu’ils ne forment pas un regroupement suffisamment important pour être considéré comme un agrégat), soit fusionnés avec les agrégats à proximité afin de satisfaire l’exigence du nombre minimal d’entités requises. En revanche, en sélectionnant une valeur de paramètre Nombre minimal d’entités par agrégat inférieure à la valeur correspondant selon vous au plus petit agrégat représentatif peut entraîner une subdivision des agrégats. En d’autres termes, plus la valeur du paramètre Nombre minimal d’entités par agrégat est petite, plus le nombre d’agrégats détectés est important. Plus la valeur est élevée, plus le nombre d’agrégats détectés est faible.

Conseil :

La valeur idéale du paramètre Nombre minimal d’entités par agrégat dépend de ce que vous essayez de capturer et de la question de l’analyse. Elle devrait correspondre à la plus petite taille de regroupement que vous souhaitez considérer comme un agrégat représentatif. En augmentant cette valeur, vous risquez 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 nombre minimal d’entités par agrégat est élevé, la distance principale correspondante est plus importante. Si la valeur sélectionnée est faible, la distance principale correspondante est 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-échelle (OPTICS).

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

Distance de recherche (DBSCAN et OPTICS)

Pour Distance définie (DBSCAN), si la valeur du paramètre Entités minimales par agrégat se trouve dans le rayon de recherche à partir d’un point spécifique, ce point est marqué comme point principal et est inclus dans un agrégat, ainsi que tous les points situés dans le rayon principal. 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 minimal d’entités dans le rayon de recherche et ne se situe pas dans le rayon 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 la méthode d’agrégation Multi-échelle (OPTICS), la valeur de distance de recherche est traitée comme étant la distance maximale qui est 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 méthode Multi-échelle (OPTICS) recherche toutes les distances voisines dans les limites de la distance de recherche spécifiée, en comparant chacune d’elles à 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 attribuée à une entité correspond à la plus petite distance entre l’entité sélectionnée et toutes les autres entités comprises sous le seuil de la Distance de recherche.

Pour Distance définie (DBSCAN) et Multi-échelle (OPTICS), la distance de recherche par défaut est la distance principale la plus élevée du jeu de données en excluant les distances principales figurant dans le 1 % supérieur (c’est-à-dire en excluant les 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, le nombre minimal d’entités par agrégat doit figurer dans la distance de recherche et l’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-échelle (OPTICS), tous les points figurant en dehors de la plage d’intervalle temporel de recherche d’un point sont exclus lorsque le point calcule sa distance principale, recherche toutes les distances voisines dans la 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 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égation 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 génère un nombre d’agrégats plus faible.

Illustration d’une sensibilité d’agrégation faible et d’une sensibilité d’agrégation élevée.

La sensibilité d’agrégation 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 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 seule la méthode Multi-échelle (OPTICS) 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 explique 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 la méthode Distance définie (DBSCAN), vous pouvez imaginer que vous tracez une ligne à travers le diagramme d’accès à la 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 claire à utiliser comme limite et si cette distance de recherche s’applique bien à tous les agrégats. 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’informations sur l’algorithme, consultez la 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.

Lorsque vous choisissez une valeur très élevée pour Sensibilité d’agrégation, 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égation élevée utilisée avec l’algorithme OPTICS et des agrégats correspondants.

Si vous optez pour une sensibilité d’agrégation modérée, les pics moyens et grands sont utilisés, mais pas les petits pics.

Illustration de l’impact d’une sensibilité d’agrégation modérée utilisée avec l’algorithme OPTICS et des agrégats correspondants.

Lorsque vous choisissez une sensibilité d’agrégation très faible, aboutissant ainsi à la détection du plus petit nombre d’agrégats.

Illustration de l’impact d’une sensibilité d’agrégation faible utilisée avec l’algorithme OPTICS et des agrégats correspondants

La méthode Multi-échelle (OPTICS) est celle 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 de type 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 valeur Ajustement automatique (HDBSCAN) est sélectionnée pour le paramètre Méthode d’agrégation, la classe d’entités en sortie contient également les champs PROB, qui correspond à la probabilité d’appartenance de l’entité au groupe qui lui est attribué, OUTLIER, qui indique que l’entité peut être un point aberrant dans son propre agrégat (une valeur plus élevée signifie que l’entité a plus de chances d’être un point aberrant) et EXEMPLAR, qui désigne les entités les plus représentatives de chaque agrégat.

Remarque :

Tous les points identifiés comme étant du bruit sont considérés comme faisant partie du même agrégat ; des points aberrants, des probabilités et un point représentatif sont calculés pour l’agrégat de bruit. Ces valeurs risquent de ne pas être aussi significatives que celles qui sont calculées pour d’autres agrégats qui ne sont pas constitués de points.

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 survolant la barre de progression, en cliquant sur le bouton contextuel ou en développant la section des messages dans la fenêtre Géotraitement. Vous pouvez également consulter les messages d’une précédente exécution de l’outil Agrégation basée sur la densité dans l’historique de 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 permet de sélectionner toutes les entités contenues dans un agrégat spécifié et d’explorer la taille de chacun des agrégats.

Ressources supplémentaires

Pour plus d’informations sur DBSCAN, reportez-vous aux références suivantes :

• 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 HDBSCAN, reportez-vous aux références suivantes :

• 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 OPTICS, reportez-vous aux références suivantes :

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