détection de similitude rapide

Question

J'ai une grande collection d'objets et je dois comprendre les similitudes entre les deux.

Pour être exact: donné deux objets que je peux calculer leur dissemblance comme un nombre, un métriques - des valeurs plus élevées signifient moins de similarité et de 0 signifie que les objets ont des contenus identiques. Le coût du calcul de ce nombre est proportionnel à la taille du plus petit objet (chaque objet a une taille donnée).

J'ai besoin de la capacité de trouver rapidement, étant donné un objet, l'ensemble des objets similaire.

Pour être exact: je dois produire une structure de données qui mappe un objet o à l'ensemble des objets qui ne sont plus dissemblables à o que d, pour une valeur de dissimilarité d, de telle sorte que la liste des objets dans le jeu ne prend pas plus de temps que si elles étaient dans un tableau ou d'une liste liée (et peut-être qu'ils sont en réalité). En règle générale, l'ensemble sera très inférieur au nombre total d'objets, donc il vaut vraiment la peine d'effectuer ce calcul. Il est assez bon si la structure de données suppose un d fixe, mais si cela fonctionne pour un d arbitraire, encore mieux.

Avez-vous vu ce problème avant, ou quelque chose de semblable à elle? Qu'est-ce qu'une bonne solution?

Pour être précis, une solution simple consiste à calculer les différences entre toutes les paires d'objets, mais il est lent - O (n ² ) où n est le nombre d'objets. Y at-il une solution générale à la complexité inférieure?

Answer 1

Sans savoir plus de détails sur la métrique, il est difficile de dire. Je n'ai aucune idée pour l'élimination de l'O (n ^ 2) aspect, mais il peut y avoir un moyen de réduire certaines des constantes concernées. Par exemple, si vous aviez une métrique euclidienne d (p, q) = sqrt ((p_1-q_1) ^ 2 + .. + (p_n-q_n) ^ 2), vous pouvez carré votre distance d et le comparer à la partie sommes de (p_i-Q_i) ^ 2 et arrêter quand vous dépassez d ^ 2.

Que cela fait gagner du temps dépend de la façon coûteuse la comparer est juste le calcul des summands et combien de calculs de summand vous pourriez attendre d'éviter en faisant cela (évidemment, plus d est le mieux).

Answer 2

  

Je dois produire une structure de données   que les cartes tout objet o à l'ensemble des   des objets plus dissemblables à o que   d, pour une certaine valeur de dissimilarité d.

Il est peut-être le plus rapide d'abandonner tout le calcul de similarité lorsque le sous-total devient plus grand que d. Par exemple, si vos similitudes sont basées sur des distances cosinus ou Hausdorff cela peut se faire facilement.

PS: si cela ne peut se faire, votre problème pourrait être lié au problème de k-plus proches voisins (ou plus précisément un problème voisin le plus proche avec un quartier de seuil). Vous devez rechercher des algorithmes qui trouvent près par les membres sans calculer toutes les distances (peut-être quelque chose en utilisant l'inégalité du triangle). Wikipedia devrait vous aider à explorer des algorithmes appropriés.

Answer 3

Si votre mesure de similarité est transitive, vous n'avez pas de calculer la similitude pour toutes les paires d'objets depuis des objets a, b, c:

similarity(a,c) = similarity(a,b) op similarity(b,c)

où op est un opérateur binaire, par exemple la multiplication ou l'addition.

Answer 4

Je pense que la solution dépend beaucoup plus de détails sur la nature de votre problème.

1. Avez-vous besoin de trouver les objets similaires pour le même objet plusieurs fois, ou une seule fois? Si elle est à plusieurs reprises, créant alors une structure de données où vous calculer la différence une fois pour chaque paire, puis connectez des objets à des objets similaires afin que vous puissiez récupérer rapidement la liste sans recalcul pourrait être très utile amélioration de la performance.

2. Quelle est la nature du calcul? À un extrême, si la nature de la différence est qu'il est, par exemple, la différence de hauteur entre deux personnes, puis en maintenant la liste triée par la hauteur laisseriez-vous trouver les objets similaires très rapidement. Je présume que le vrai problème est plus compliqué que cela, mais après sur cette logique, si la différence est la somme de plusieurs quantités linéaires, vous pouvez créer un tableau multi-dimenstional, puis imaginer conceptuellement l'ensemble des objets similaires à ceux au sein d'une dimension n sphère (c.-à-cercle, sphère, hypersphère, etc.) centrée autour de l'objet de référence, et les retrouver directement. En fait, il me semble que si les calculs de rayon sont trop compliqués ou prennent trop d'exécution, une bonne approximation serait de créer un cube à n dimensions (ie carré, cube, Tesseract, etc.) autour de l'objet de référence, récupérer tous les objets qui se trouvent dans ce cube comme « candidats », puis faire exactement le calcul réel des candidats.

Par exemple, supposons que la « différence » est la somme des valeurs absolues des différences de trois attributs, par exemple a1, a2, et a3. On pourrait créer une matrice en 3 dimensions et régler la valeur de chaque noeud du réseau de l'objet avec ces valeurs, le cas échéant. Ensuite, si vous voulez trouver tous les objets avec une différence inférieure à d o à partir d'objets, vous pouvez écrire:

for (x1=o.a1-d;x1<o.a1+d;++x1)
{
  for (x2=o.a2-d;x1<o.a2+d;++x2)
  {
    for (x3=o.a3-d;x1<o.a3+d;++x3)
    {
      if (array[x1][x2][x3]!=null
        && (abs(x1-o.a1)+abs(x2-o.a2)+abs(x3-o.a3)<=d)
        {
          ... found a match ...
        }
    }
  }
}

Je soupçonne que les règles de différence sont plus compliquées que cela, mais bien, il suffit d'ajouter de sophistication à l'alrorithm pour répondre à la complexité des règles. Le point est d'utiliser le tableau pour limiter l'ensemble des objets que vous devez examiner.

3. Encore une fois la nature du calcul: Si l'un des éléments constituant la différence, ou un petit sous-ensemble, tend à être plus importants que d'autres, puis créer une structure de données qui vous permet de comparer rapidement cette portée. Si elle est à portée, faire pleinement comparer. Sinon, vous ne regardez même pas à elle.

Answer 5

est-il pas possible d'utiliser un k d-arbre?

Il peut être nécessaire (si possible) pour normaliser les dimensions. Par la suite, il vous suffit de remplir l'arbre, et utiliser une recherche « plus proches voisins N », et essayer de trouver un objet dans une certaine plage.

Answer 6

Exemple d'objets: Images, Documents. Bien sûr de travailler avec la représentation première de ces objets est la plupart du temps pas utile. habituellement on prétraiter la forme brute et la transformer en une forme normalisée (pour les documents, par exemple un vecteur pour lequel chaque entrée représente le nombre / pour cent de fois un certain mot est apparu, pour les images, il pourrait être une représentation de caractéristiques visuelles trouvé dans l'image).

si d est fixe et un n ^ 2 pré-calcul est possible, vous pouvez simplement utiliser une représentation graphique à l'aide d'une liste chaînée pour chaque objet par exemple. Vous pouvez avoir des solutions plus efficaces sur la charge de la précision en utilisant des algorithmes approximatifs les plus proches des voisins.

Answer 7

Peut-on supposer que la similitude est transitive, à savoir. diff(a,c) == diff(a,b) + diff(b,c)? Si oui, vous pouvez essayer ce qui suit:

1. Trier la collection d'objets. Si la mesure de similarité d'objet n'a pas de valeur absolue décente, vous pouvez sélectionner arbitrairement un objet comme « zéro » et de trier tous les autres objets par leur ressemblance avec cet objet.
2. Pour les objets avec s de ressemblance avec o, trouver o dans la liste triée et recherche à gauche et à droite jusqu'à ce que la diff pousse plus grand que s.

L'avantage de ceci est que le tri peut être fait une fois, et la construction de jeu suivant est proportionnel au nombre de membres qui seront dans le jeu.

Answer 8

On dirait BK-Tree. Voici un petit exemple . Vous créez fondamentalement arbre et vérifier quelle branche doit être utilisé pour la recherche d'un objet similaire et qui non, si vous empêchez O(n2)