6

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

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

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

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

你以前见过这个问题，或者类似的东西吗？什么是好的解决方案？

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

4

8 回答 8

2

我需要生成一个数据结构，将任何对象 o 映射到与 o 不相似的对象集，而不是 d，对于某些相异值 d。

当小计大于 时，放弃相似度计算可能是最快的d。例如，如果您的相似性基于余弦或豪斯多夫距离，则可以轻松完成。

 

PS：如果无法做到这一点，您的问题可能与 k 最近邻问题（或更准确地说是具有阈值邻域的最近邻问题）有关。您应该寻找在不计算所有距离的情况下找到附近成员的算法（可能使用三角不等式）。维基百科应该帮助你探索合适的算法。

于 2009-12-11T16:45:31.483 回答
1

如果您的相似性度量是传递性的，则您不必计算所有对象对的相似性，因为对于对象 a、b、c：

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

其中op是二元运算符，例如乘法或加法。

于 2009-12-11T16:11:25.750 回答
1

在不了解指标的更多细节的情况下，很难说。我对消除 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 越小越好）。

于 2009-12-11T16:49:37.467 回答
1

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

  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. 再次谈谈计算的性质：如果构成差异的元素之一或某个小子集往往比其他元素更重要，则创建一个数据结构，使您可以在范围内快速进行比较。如果在范围内，请进行完整比较。如果没有，那么你甚至不看它。
于 2009-12-11T17:35:04.697 回答
1

不能使用k d-tree吗？

可能有必要（如果可能）对尺寸进行标准化。之后，您只需要填充树，并使用“最近 N 个邻居”搜索，并尝试找到某个范围内的任何对象。

于 2009-12-11T19:37:38.053 回答
1

对象示例：图像、文档。当然，使用这些对象的原始表示大多是没有用的。通常人们会预处理原始形式并将其转换为某种规范化形式（对于文档，例如一个向量，其中每个条目表示某个单词出现的次数/百分比，对于图像，它可能是发现的视觉特征的表示在图像中）。

如果 d 是固定的并且 ^2 预计算是可行的，例如，您可以只使用使用每个对象的链表的图形表示。您可以使用近似最近邻算法以牺牲准确性为代价获得更有效的解决方案。

于 2010-04-08T22:50:15.717 回答
0

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

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

这样做的好处是可以进行一次排序，随后的集合构建与集合中的成员数量成正比。

于 2009-12-11T16:14:35.060 回答
0

听起来像 BK 树。这是一个小例子。您基本上创建树并检查哪个分支应该用于类似的对象搜索，哪个不应该，所以你防止O(n2)

于 2016-05-30T13:03:25.137 回答