题

我有大量的对象，我需要找出它们之间的相似之处。

确切地说：给定两个对象，我可以将它们的差异计算为数字，a 公制 - 值越高意味着相似度越低，0 意味着对象具有相同的内容。计算该数字的成本与较小对象的大小成正比（每个对象都有给定的大小）。

我需要能够在给定一个对象的情况下快速找到与其相似的一组对象。

确切地说：我需要生成一个数据结构，对于某些相异值 d，将任何对象 o 映射到与 o 不相似的对象集，这样列出集合中的对象不会比它们在数组中花费更多的时间或链表（也许它们实际上是）。通常，该集合将比对象总数小得多，因此执行此计算确实值得。如果数据结构假设一个固定的 d 就足够了，但如果它适用于任意 d，那就更好了。

您以前见过这个问题或类似的问题吗？什么是好的解决方案？

确切地说：一个简单的解决方案涉及计算所有对象对之间的差异，但这很慢 - O(n2) 其中 n 是对象的数量。有没有复杂度较低的通用解决方案？

有帮助吗？

解决方案

不知道度量的更多的细节，这是很难说。我没有为消除为O（n ^ 2）方面的任何想法，但有可能会降低所涉及的一些常量的一种方式。例如，如果你有一个欧几里德度量d（P，Q）= SQRT（（P_1-Q_1）^ 2 + ... +（P_N-Q_N）^ 2），即可方的距离d，并比较它的部分（P_I-Q_I）^ 2，当你超过d ^ 2停止的总和。

这是否会真正节省您的时间取决于如何昂贵的比较是只计算被加数，以及如何你可以指望，以避免这样做，许多被加数计算（显然，小d是，越好）。

其他提示

  

我需要产生数据结构   任何对象映射O到组   对象没有更多不同的邻比   d，对于一些相异值d。

这可能是最快的，只是放弃相似度计算时的小计变得比d大。例如，如果你的相似之处是基于余弦或豪斯多夫距离这很容易做到。

PS：如果这不能这样做，你的问题可能与第k近邻问题（或者更精确的最近邻问题阈值附近）。你应该寻找发现近距离的成员，而不计算所有的距离（可能使用三角不等式的东西）算法。维基百科应该帮助你去探索合适的算法。的

如果您的相似度是传递的，你没有来计算的相似性将所有对对象的自为对象，B，C：

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

其中op是一个二进制运算符例如乘法或加法。

我认为解决方案取决于有关问题性质的更多细节。

  1. 您是否需要多次查找同一对象的相似对象，还是只查找一次？如果多次，那么创建一个数据结构，在其中为每对计算一次差异，然后将对象连接到相似的对象，以便您可以快速检索列表而无需重新计算，这可能是非常有用的性能增强。

  2. 计算的本质是什么？在一种极端情况下，如果差异的性质是，例如，两个人之间的身高差异，那么维护按身高排序的列表可以让您非常快速地找到相似的对象。我假设真正的问题比这更复杂，但是按照这个逻辑，如果差异是几个线性量的总和，您可以创建一个多维数组，然后从概念上想象一组类似的对象在 n 维球体内（即以参考对象为中心的圆、球体、超球体等），然后再次直接找到它们。实际上，我想到如果半径计算太复杂或花费太多运行时间，一个好的近似方法是创建一个 n 维立方体（即围绕参考对象的正方形、立方体、超正方体等），检索位于该立方体内的所有对象作为“候选者”，然后对候选者进行实际计算。

例如，假设“差异”是三个属性（例如 a1、a2 和 a3）的差异的绝对值之和。您可以创建一个 3 维数组，并将数组每个节点的值设置为具有这些值的对象（如果有）。那么如果你想找到与对象 o 差异小于 d 的所有对象，你可以这样写：

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 ...
        }
    }
  }
}

我怀疑差异规则比这更复杂，但是很好，只需增加算法的复杂性以匹配规则的复杂性即可。重点是使用数组来限制您必须检查的对象集。

  1. 再次讨论计算的性质：如果构成差异的一个元素或某个小子集往往比其他元素更重要，那么创建一个数据结构，允许您在范围内快速比较。如果在范围内，则进行全面比较。如果没有，那你连看都不看。

时它不可能使用一ķ d-树？

这可能是必要的（如果可能的话）来归一化的尺寸。之后，你只需要填充树，并使用“最近的N个邻居”进行搜索，并试图找到一些范围内的任何物体。

对象的实施例： 图像，文档。当然，与这些对象的原始表示工作大多是没有用的。通常一个将预先处理原始形式并把它变成一些归一化形式（文档，说一个向量，其中每个条目表示的次某个词出现的数目/百分比，对于图像可以发现的视觉特征的表示在图像）。

如果d是固定的，并且一个N ^ 2预先计算是可行的，可以只使用一个图表示使用链表的每个对象，例如。 您可以使用近似最近邻算法对精确度的代价更有效的解决方案。

我们可以假设相似性是传递的，即。 diff(a,c) == diff(a,b) + diff(b,c)？如果是这样，您可以尝试以下操作：

  1. 对对象集合进行排序。如果对象相似度度量没有合适的绝对值，您可以任意选择一个对象作为“零”，并根据与该对象的相似度对所有其他对象进行排序。
  2. 寻找相似的对象 s 到 o, ， 寻找 o 在排序列表中，向左和向右搜索，直到 diff 大于 s.

这样做的优点是排序可以完成一次，并且后续的集合构建与集合中的成员数量成正比。

听起来像BK-树。 这里是一个小例如的。基本上，你创建的树和检查应使用哪个分支类似对象的搜索和没有，所以你防止O(n2)

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top