2017-10-19 24 views
0

Existe-t-il un moyen de diviser un ensemble de données constitué de paires de points 3D (ou simplement leurs numéros d'index) en groupes connectés? Autrement dit, deux paires (a, b) et (c, d) devraient être dans le même groupe si elles partagent un point commun (c.-à-d. A = c, b = c, a = d ou b = d) ou s'il y a une chaîne d'une ou plusieurs autres paires, partageant chacune un point commun avec le précédent, d'une paire à l'autre.Clustering par données répétées

Par exemple, la liste des paires:

[[1,2],[2,3],[4,5],[6,7],[7,8],[9,4],[8,5]] 

seraient regroupés comme suit:

[[1,2],[2,3]] 

[[4,5],[6,7],[7,8],[9,4],[8,5]] 

Dans le premier groupe, les paires (1,2) et (2,3) avoir le point 2 en commun et ne partager aucun point avec des paires en dehors du cluster. Dans la deuxième grappe, la paire (4,5) partage des points communs avec (9,4) et (8,5), alors que (8,5) a un point commun avec (7,8), qui a un point commun avec (6,7).

Les données sont à l'origine stockées dans un tableau numpy, mais le format de sortie n'est pas trop important.

Je dois pouvoir accéder par la suite aux données qui composent chaque groupe.

+2

Je ne comprends pas la logique du groupement. Si '[1,2], [2,3]' est dans une grappe, pourquoi n'est-ce pas [6,7], [7,8] 'également dans cette grappe? Qu'entendez-vous par "points répétés"? – roganjosh

+1

@roganjosh Je pense que le problème peut être exprimé en trouvant les composantes connexes d'un graphique, où les paires données sont des arêtes et les nombres sont des nœuds. OP, consultez networkx. –

+0

@AlexHall cette explication n'est malheureusement pas aidé par l'édition aléatoire pour ajouter des commentaires (pas par le PO ou vous) à la question. Mais même ainsi, dois-je interpréter la sortie requise comme identifiant une rupture dans un graphe de connexion, et vider le reste à une autre liste? '[6,7], [7,8]' est toujours connecté, mais il apparaît avec le reste. – roganjosh

Répondre

2

En utilisant networkx:

import networkx 

edges = [[1, 2], [2, 3], [4, 5], [6, 7], [7, 8], [9, 4], [8, 5]] 

graph = networkx.Graph(edges) 
print(list(networkx.connected_components(graph))) 

Sortie:

[set([1, 2, 3]), set([4, 5, 6, 7, 8, 9])] 
+0

Je suis tombé sur networkx moi-même. Merci beaucoup pour votre exemple travaillé. –