J'ai les points suivants dans l'espace 3D:

enter image description here

Je dois grouper les points, selon D_max et d_max:

D_max = max dimension of each group
d_max = max distance of points inside each group

Comme ça:

enter image description here

La forme du groupe dans l'image ci-dessus ressemble à une boîte, mais la forme peut être tout ce qui serait la sortie de l'algorithme de groupement .


J'utilise Python et visualise les résultats avec Blender. J'envisage d'utiliser le scipy.spatial.KDTree et en appelant son requête, cependant, je ne suis pas sûr que ce soit le bon outil pour le travail à accomplir. Je crains qu'il n'y ait un meilleur outil que je ne connaisse pas. Je suis curieux de savoir s'il existe un autre outil / bibliothèque / algorithme qui peut m'aider.


Comme l'a souligné @CoMartel, il existe DBSCAN et également des modules Clusters HDBSCAN qui semblent convenir à ce type de problèmes. Cependant, comme l'a souligné @Paul, il leur manque l'option de taille maximale du cluster qui correspond à mon paramètre D_max. Je ne sais pas comment ajouter une fonction de taille de cluster maximale aux clusters DBSCAN et HDBSCAN.


Grâce à @ Anony-Mousse, j'ai regardé Agglomérative Clustering: comment ça marche et Hierarchical Clustering 3: single-link vs complete- lien et j'étudie En comparant les algorithmes de clustering Python, j'ai l'impression que le fonctionnement de ces algorithmes devient plus clair.

3
user3405291 23 mai 2018 à 11:36

3 réponses

Meilleure réponse

Comme demandé, mon commentaire comme réponse:

Vous pouvez utiliser DBSCAN (http://scikit-learn.org /stable/modules/generated/sklearn.cluster.DBSCAN.html) ou HDBSCAN.

Ces deux algorithmes permettent de regrouper chaque point en fonction de d_max (distance maximale entre 2 points du même ensemble de données), mais ils ne prennent pas la taille maximale du cluster. La seule façon de limiter la taille maximale d'un cluster est de réduire le paramètre eps, qui contrôle la distance maximale entre 2 points du même cluster.

2
Has QUIT--Anony-Mousse 25 mai 2018 à 20:11

Algorithme de clustering DBSCAN avec la distance maximale de points à l'intérieur de chaque extension de groupe

Vous pouvez utiliser l'algorithme DBSCAN de manière récursive.

def DBSCAN_with_max_size(myData, eps = E, max_size = S):
     clusters = DBSCAN(myData, eps = E)
     Big_Clusters = find_big_clusters(clusters)
     for big_cluster in Big_Clusters:
         DBSCAN_with_max_size(big_cluster ,eps = E/2 ,max_size = S) //eps is something lower than E (e.g. E/2)
0
Pouria golshanrad 7 sept. 2018 à 16:29

Utilisez le clustering aggloméré hiérarchique .

Si vous utilisez liaison complète , vous pouvez contrôler le diamètre maximal des clusters. Le lien complet est la distance maximale.

Le paramètre epsilon de DBSCAN n'est pas une distance maximale car plusieurs étapes sont jointes de manière transitoire. Les clusters peuvent devenir beaucoup plus gros que epsilon!

2
Has QUIT--Anony-Mousse 25 mai 2018 à 20:14