Choix d'un sous-ensemble de points les plus éloignés dans un ensemble de points donné

Question

Imaginez que l'on vous donne un ensemble S de n points en 3 dimensions. La distance entre deux points quelconques est une simple distance euclidienne. Vous voulez choisir un sous-ensemble Q de k points dans cet ensemble, de sorte qu'ils soient les plus éloignés les uns des autres. En d'autres termes, il n'existe aucun autre sous-ensemble Q' de k points tel que le minimum de toutes les distances par paires dans Q est inférieur à celui de Q'.

Si n est d'environ 16 millions et k d'environ 300, comment faire efficacement ?

Je pense que c'est NP-hard donc peut-être que nous voulons juste nous concentrer sur l'approximation. Une idée à laquelle je peux penser est d'utiliser l'échelle multidimensionnelle pour trier ces points sur une ligne, puis d'utiliser une version de la recherche binaire pour obtenir les points les plus éloignés sur cette ligne.

Answer 1

Je suis également presque sûr que le problème est NP-Hard, le problème le plus similaire que j'ai trouvé est celui de la Problème du k-centre . Si le temps d'exécution est plus important que l'exactitude, un algorithme gourmand est probablement votre meilleur choix :

Q ={}
while |Q| < k
    Q += p from S where mindist(p, Q) is maximal

Remarque : dans des problèmes similaires, par exemple le le problème de la couverture de l'ensemble il est possible de montrer que la solution de l'algorithme glouton est au moins 63% aussi bonne que la solution optimale.

Afin d'accélérer les choses, je vois 3 possibilités :

1. Indexez votre ensemble de données dans un R-Tree d'abord, puis effectuer une recherche gourmande. La construction du R-Tree est O(n log n), mais bien qu'il soit développé pour la recherche du plus proche voisin, il peut également vous aider à trouver le point le plus éloigné d'un ensemble de points en O(log n). Cela peut être plus rapide que l'algorithme naïf O(k*n).

2. Echantillonnez un sous-ensemble de vos 16 millions de points et exécutez l'algorithme glouton sur ce sous-ensemble. Comme il s'agit de toute façon d'une approximation, vous pourrez peut-être faire l'économie d'un peu plus de précision. Vous pouvez également combiner cette méthode avec l'algorithme 1.

3. Utilisez une approche itérative et arrêtez-vous lorsque vous manquez de temps. L'idée ici est de sélectionner aléatoirement k points dans S (appelons cet ensemble Q'). Ensuite, à chaque étape, vous échangez le point p_ de Q' qui a la distance minimale à un autre point de Q' avec un point aléatoire de S. Si l'ensemble résultant Q'' est meilleur, continuez avec Q'', sinon répétez avec Q'. Pour ne pas rester bloqué, vous pouvez choisir un autre point de Q' que p_ si vous n'avez pas trouvé de remplacement adéquat après quelques itérations.

Answer 2

Si vous pouvez vous permettre de faire ~ k*n calculs de distance alors vous pourriez

1. Trouvez le centre de la distribution des points.
2. Sélectionnez le point le plus éloigné du centre. (et le retirer de l'ensemble des points non sélectionnés).
3. Trouvez le point le plus éloigné de tous les points actuellement sélectionnés et sélectionnez-le.
4. Répétez 3. jusqu'à ce que vous finissiez avec k points.