0
votes

Étant donné un ensemble de points ou de vecteurs, trouvez l'ensemble de N points les plus proches les uns des autres

J'ai par exemple 100 vecteurs ayant chacun une dimension de 12. Je voudrais trouver par exemple 8 vecteurs les plus proches les uns des autres. En d'autres termes, les 8 meilleurs vecteurs correspondants. Je peux utiliser la distance euclidienne ou de Manhattan comme mesure de mesure pour quantifier la similitude entre les vecteurs. Une première réflexion révèle que je pourrais formuler ce problème comme une programmation non linéaire 0-1 qui est NP difficile à résoudre lorsque le nombre de vecteurs augmente. Je suis également passé par l'algorithme de clustering k-means mais il n'utilise pas la distance euclidienne comme mesure. Toute idée de l'algorithme pouvant cibler ce problème. La raison pour laquelle je pose la question est que je suis sûr que ce problème a été abordé dans la littérature, mais je n'ai pas pu trouver un tel algorithme.

optimization vector cluster-analysis

2 commentaires

Je pense que vous devez définir la métrique de distance pour que le problème soit bien défini: comment un ensemble de N points est défini pour être plus proche qu'un autre ensemble? En ce qui concerne la métrique, le problème peut être plus ou moins difficile. Cette méthode peut vous intéresser.

Pour référence future, Mathematics Stack Exchange ou Operations Research Stack Exchange seraient de meilleurs endroits pour des questions comme celle-ci, à la fois en raison de leurs bases d'utilisateurs et de leur prise en charge de LaTeX (notation mathématique).

3 Réponses :

2
votes

Cela peut en fait être formulé comme un programme d'entiers quadratiques ou linéaires:

Le modèle quadratique peut ressembler à:

 min z
     z >= y(i,j)*dist(i,j)   for all i<j
     sum(i, x(i)) = 8
     y(i,j) >= x(i)+x(j)-1 
     x(i) âˆˆ {0,1} 
     y(i,j) âˆˆ [0,1]

Le modèle MIP linéaire est une variante du modèle quadratique:

  min sum((i,j), y(i,j)*dist(i,j))
      sum(i, x(i)) = 8
      y(i,j) >= x(i)+x(j)-1
      x(i) âˆˆ {0,1} 
      y(i,j) âˆˆ [0,1]

Nous pouvons affiner les choses en ne considérant que les distances avec i < j (essentiellement pas de double comptage).

Au lieu de faire la somme sur toutes les distances, nous pouvons également minimiser la distance maximale dans nos points sélectionnés:

  min sum((i,j), x(i)*x(j)*dist(i,j))
      sum(i, x(i)) = 8
      x(i) âˆˆ {0,1}

Ces modèles sont indépendants de la métrique ou de la dimensionnalité que vous utilisez. Que vous utilisiez des distances euclidiennes ou de Manhattan ou que vous normalisiez ou utilisiez des poids, les modèles restent les mêmes. La même chose pour que vous ayez des données de faible ou de haute dimension. Ces modèles ont juste besoin d'une matrice de distance.

Les modèles MIP résolvent assez rapidement avec Gurobi. Avec des données aléatoires utilisant vos tailles (sélectionnez 8 points parmi 100 en utilisant des coordonnées à 12 dimensions), ces modèles prennent 50 et 9 secondes pour que la somme linéaire et le modèle max trouvent des solutions optimales éprouvées. Quelques détails supplémentaires sont ici .

Pour un ensemble de données 2D, nous pouvons tracer les résultats:

0 commentaires

0
votes

Je suis d'accord avec Jérôme Richard que la mesure de la distance doit être clarifiée. Est-ce la somme des longueurs euclidiennes des 56 segments de ligne reliant les paires des huit points sélectionnés, ou la distance maximale entre une paire, ou quoi?

Cela dit, si la «similitude» est le but, on peut se demander quels huit points sont contenus dans la plus petite balle ou boîte possible. Trouver la plus petite boule est un problème quadratique convexe et trouver le plus petit hyperrectangle a un objectif non convexe (je pense), mais trouver les vecteurs qui correspondent au plus petit hypercube est facile à formuler sous la forme d'un programme linéaire mixte.

0 commentaires

0
votes

avec OPL CPLEX, vous pouvez résoudre ce problème à la fois avec la programmation mathématique et la programmation par contraintes .

Prog math:

using CP;

int scale=1000000;

int nbdim=2;
int m=8;
int n=50;

range dim=1..nbdim;
range points=1..n;

float x[p in points][d in dim]=rand(scale)/scale;

float distance[p1 in points][p2 in points]=sqrt(sum(d in dim)((x[p1][d]-x[p2][d])^2));

// which point for as the m th point ?
dvar int which[1..m] in points;

dexpr float maxDist=max(ordered i,j in 1..m) distance[which[i]][which[j]];

minimize maxDist;
subject to
{
  allDifferent(which);
}

{int} chosenPoints={which[k] | k in 1..m};

Programmation par contraintes:

int scale=1000000;

int nbdim=2;
int m=8;
int n=50;

range dim=1..nbdim;
range points=1..n;

float x[p in points][d in dim]=rand(scale)/scale;

float distance[p1 in points][p2 in points]=sqrt(sum(d in dim)((x[p1][d]-x[p2][d])^2));

// Should we keep that point ?
dvar  boolean which[points];

dexpr float maxDist=max(ordered i,j in points) distance[i][j]*((which[i]==1) && (which[j]==1));

minimize maxDist;
subject to
{
  sum (p in points) which[p]==m;
}

{int} chosenPoints={k | k in points:which[k]==1};

0 commentaires