快速相似性检测

如果不知道更多关于度量的细节,就很难说了。我对消除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映射到 对象与O不比 d,对于某些不同的值d。

当小计大于 d . 例如,如果你的相似性是基于余弦或豪斯多夫距离的,这很容易做到。

PS: 如果不能做到这一点,您的问题可能与k-最近邻问题有关(或者更精确地说,与阈值邻域有关的最近邻问题)。你应该寻找一种算法,可以在不计算所有距离的情况下靠近成员(可能是使用三角形不等式)。维基百科应该帮助你探索合适的算法。

如果相似性度量是可传递的,则不必计算所有对象对的相似性,因为对于对象A、B、C:

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

在哪里? op 是一个二进制运算符,例如乘法或加法。

我认为解决办法取决于更多关于你问题本质的细节。

1. 您需要为同一个对象多次或只查找一次类似的对象吗?如果有很多次,那么创建一个数据结构,在其中为每对计算一次差异,然后将对象连接到类似的对象,以便在不重新计算的情况下快速检索列表,这可能是一个非常有用的性能增强。

2. 计算的性质是什么?在一个极端,如果差异的本质是,例如,两个人之间的高度差异,那么保持按高度排序的列表可以让您很快找到相似的对象。我假设真正的问题比这个复杂,但是根据这个逻辑,如果差是几个线性量的和,你可以创建一个多维的数组,然后概念上想象一组类似的物体,就像在一个以空间为中心的多维球体(即圆、球体、超球体等)中的那些物体一样。e引用对象,然后再次直接找到它们。实际上,我突然想到,如果半径计算太复杂或运行时间太长,一个好的近似方法是在参考对象周围创建一个n维立方体(即正方形、立方体、苔丝ract等),检索该立方体内的所有对象作为“候选者”,然后对候选对象进行实际计算。阿特斯。

例如,假设“差异”是三个属性(如a1、a2和a3)差异的绝对值之和。您可以创建一个三维数组,并使用这些值(如果有的话)将数组的每个节点的值设置为对象。然后,如果要查找与对象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 ...
        }
    }
  }
}

我怀疑不同的规则比这更复杂,但是很好,只是在Alrorithm中添加复杂性以匹配规则的复杂性。重点是使用数组限制必须检查的对象集。

3. 再次说明计算的性质:如果组成差异的元素之一,或一些小的子集,往往比其他元素更重要,那么创建一个数据结构,允许您在范围内对此进行快速比较。如果在范围内,则进行完全比较。如果不是,那你甚至都不看它。

不能使用 K D-树?

可能需要(如果可能)规范化尺寸。然后,您只需要填充树,并使用“最近的n个邻居”搜索,并尝试在某个范围内找到任何对象。

对象示例: 图像,文件。当然,使用这些对象的原始表示法通常是没有用的。通常,人们会预先处理原始表单,并将其转换为某种规范化表单(对于文档,例如每个条目表示某个词出现的次数/百分比的向量,对于图像,它可以表示图像中的视觉特征)。

如果d是固定的,并且n^2预计算是可行的,那么您可以使用一个图表表示法,例如为每个对象使用一个链接列表。 您可以使用近似最近邻算法来获得更有效的解决方案,从而降低精度。

我们能假定相似性是可传递的吗? diff(a,c) == diff(a,b) + diff(b,c) 是吗?如果是,可以尝试以下操作:

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

这样做的好处是,排序可以完成一次,随后的集合构建与集合中的成员数成比例。

听起来像bk树。 Here is a small example . 基本上,您创建树并检查应该将哪个分支用于类似的对象搜索,而哪些分支不应用于类似的对象搜索,因此,您可以防止 O(n2)