算法帮助需要

Question

我有一组序列（例如10000个序列），并生成一个矩阵（10000×10000），表示每两个序列之间的成对相似性。

现在的目标是从大集合中检索一个子集（例如1000个序列），并确保该子集中每两个序列之间的成对相似性在一个范围内（例如50％〜85％）。

有没有什么快速的算法来做到这一点？

Answer 1

可以改造这个到图论问题：

1. 每个序列是一个节点
2. 如果两个节点的相似性是在给定的范围相比，还有他们之间的边缘
3. 你的目标是找到大号connected component（如果您的相似关系是过渡性的......）或大号clique（...如果不是）。

Answer 2

您可以生成两两相似的排序列表（回头指向您的矩阵），获取该排序列表的子集，然后确保该子列表与您的子集之间的交集与您的子集大小相同，从而验证子集中的所有元素都在指定范围内。

虽然需要大量的设置来生成矩阵和大量的空间来创建有序列表。至少，你的矩阵设置是O（n^2）。

Answer 3

这听起来像是“集团发现”给我;集团决策问题是NP完全的。

根据序列相似性背后的统计数据，您可能会满意最大团问题的近似算法。一个随机算法对你来说甚至可能足够好。但总的来说，这是一个非常棘手的问题，即使N = 100，也不太可能做到这一点。

Answer 4

许多相似之处与n维中的点积相当或相关空间，即使当相似性没有被明确计算时。在这些情况下，可能还有其他情况，a.b和b.c的高值可能意味着a.c的高值，但这种情况的好处并不是很好 - 不如我想象的那么好。

仅涉及三个向量 - a，b和c我认为，无论底层空间的维度如何，您都可以绘制三维图表，并且我认为最糟糕的情况是所有三个向量都处于飞机上面b和c下面b。在那种情况下，例如所有单位矢量都是单位矢量，a.b = b.c = 0.9，a比b大约25度，c比它低大约25度，a.c = 0.62。事实上，在这种情况下，对于ac = bc = x，ac = 2x^2 - 1.

在这些情况下，如果我绝对需要解决这个问题，我会尝试回溯搜索来枚举几组非常接近到特定节点。例如，您可以从两个最相似的节点开始，然后运行一个搜索，在每个级别上添加尚未尝试过的最接近原始种子节点的节点。或者你可以建立一个单一的链接聚类，并检查出所需大小的所有子树。