有效的算法来比较数字集之间的相似性？

我有很多套数字。 每组包含10个数字，我需要删除与任何其他集合具有5个或更多数字（无序）匹配的所有集合。

例如：

set 1: {12,14,222,998,1,89,43,22,7654,23} set 2: {44,23,64,76,987,3,2345,443,431,88} set 3: {998,22,7654,345,112,32,89,9842,31,23} 

鉴于集合1以上的3组10个数字和集合3将被认为是重复的，因为它们具有5个匹配的数字。 所以，在这种情况下，我会删除第3组（因为它被认为类似于第1组）。

我有超过10000套比较，我想非常有效地做到这一点。 我一直在讨论这个问题，我只是想不出一种有效的方法来进行这种比较（在一次通过中这样做会很棒）。

有任何想法吗？ 谢谢！

麦克风

Answer 1

您应该重新考虑您的要求，因为实际上，操作甚至没有明确定义的结果。 例如，采取这些集：

 set 1: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} set 2: {6, 7, 8, 9, 10, 11, 12, 13, 14, 15} set 3: {11, 12, 13, 14, 15, 16, 17, 18, 19, 20} 

如果你首先认为1和2是“重复”并消除集1，那么2和3也是“重复”，你只剩下一个剩余集。 但是如果你先取消第2组，那么1和3没有匹配，你剩下两组。

您可以轻松地将其扩展到完整的10,000套，以便根据您比较和消除的集合，您可能只剩下一套，或者只有5,000套。 我不认为这就是你想要的。

从数学上讲，你的问题是你试图找到等价类 ，但你用来定义它们的“相似性” 关系不是等价关系 。 具体来说，它不具有传递性。 通俗地说，如果集合A与集合B“相似”并且集合B与集合C“相似”，则您的定义不能确保A也与C“相似”，因此您无法有意义地消除类似集合。

在担心有效实施之前，您需要先澄清处理此问题的要求。 要么找到定义传递相似性的方法，要么保留所有集合并仅使用比较（或者使用每个单集的类似集合列表）。

Answer 2

签名树的另一个完美工作。 我再次感到震惊的是，那里没有一个实现它们的库。 如果你写一个，请告诉我。

从上面搜索结果中第一篇论文的摘要：

我们提出了一种方法，将设置数据表示为位图（签名），并将它们组织成分层索引，适用于相似性搜索和其他相关查询类型。 与先前技术相比，签名树是动态的并且不依赖于硬连线常数。 使用合成和真实数据集的实验表明，它对不同的数据特​​征具有鲁棒性，可扩展到数据库大小并且对各种查询有效。

Answer 3

你没有多说可能出现的数字范围，但我有两个想法：

• 一个倒置列表，将列表中显示的数字映射到包含它的列表，然后与这些列表相交以查找具有多个共同数字的列表。

• 将数字除以或将它们分组为“接近”数字的范围，然后细化（缩小）具有数字的列表。 您可以减少匹配列表的范围，这些列表具有可管理的列表数量，您可以精确地比较列表。 我认为这将是一种“接近”的方法。

Answer 4

我认为没有一种漂亮而美丽的方式来做到这一点。 大多数其他答案将让你在大多数对x,y之间进行比较x,y这将是O(N^2) 。 你可以更快地完成它。

算法：保留所有5元组的数组。 对于每个新的拆分它到所有可能的5元组，添加到该数组。 最后，排序并检查重复项。

有C(10, 5) = 10*9*8*7*6/120 = 9*4*7 ，长度为10的长度为5的大约250个子集。所以你保持一个10^3的表比您的数据大10^3倍，但只执行O(250*N)操作。 这应该是切实可行的，我怀疑它在理论上也是最好的。

Answer 5

有一种方法可以实现这一目标，具有高效率但极低的空间效率。

如果我的数学是正确的，那么10个数字中的5个数字的每个组合都会产生10个！（10-5）！5！ = 252组合乘以10000组= 252万组合。 一组5个整数将消耗20个字节，因此您可以将每个组合的每个组合放入HashSet 。 并且仅使用5兆字节（加上开销，至少将其吹出2-3次）。

现在这可能看起来很昂贵，但是如果替代方案，当你在现有的10000个单独检查一组新的10时，就是你计算了252套5并且看看它们中是否有任何一套，那么它必须更好。

基本上：

 public class SetOf5 { private final static HashSet numbers; private final int hashCode; public SetOf5(int... numbers) { if (numbers.length != 5) { throw new IllegalArgumentException(); } Set set = new HashSet(); hashCode = 19; for (int i : numbers) { set.add(i); hashCode = 31 * i + hashCode; } this.numbers = Collections.unmodifiableSet(set); } // other constructors for passing in, say, an array of 5 or a Collectio of 5 // this is precalculated because it will be called a lot public int hashCode() { return numbers.hashCode(); } public boolean equals(Object ob) { if (!(ob instanceof SetOf5)) return false; SetOf5 setOf5 = (SetOf5)ob; return numbers.containsAll(setOf5.numbers); } } 

然后你只需做两件事：

1. 为所有现有的5个元组创建一个HashSet ; 和
2. 创建一个算法来创建所有可能的5个集合。

然后，您的算法变为：对于每组10个数字，创建所有可能的5个集合，检查每个集合以查看它是否在集合中。 如果是，则拒绝10的集合。如果不是，则将5的集合添加到“集合集”中。 否则继续。

我想你会发现，相比10000套的蛮力比较，至少在10个数字的情况下，你的价格便宜得多。

Answer 6

由于您需要比较所有对集合，因此算法约为O（N ^ 2），其中N是集合的大小。

对于每次比较，你可以做O（X + Y），其中X和Y是两组的大小，在你的情况下每个10，所以它是常量。 但这需要您事先对所有集合进行排序，以便添加到O（N * xlgx），再次xlgx在您的情况下是常量。

两组的线性比较算法相当简单，因为现在对集合进行排序，您可以同时迭代这两个集合。 有关详细信息，请参阅c ++ std :: set_intersection。

然后整个算法是O（N ^ 2），对于10000集来说这将是相当慢的。

Answer 7

您应该在两组数据之间找到Pearson系数。 此方法将使您的程序可以轻松扩展到庞大的数据集。

Answer 8

也许你需要一个像这样的算法（因为我理解你的问题）？

 import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Set; /** * @author karnokd, 2009.06.28. * @version $Revision 1.0$ */ public class NoOverlappingSets { // because of the shortcomings of java type inference, O(N) public static Set setOf(Integer... values) { return new HashSet(Arrays.asList(values)); } // the test function, O(N) public static boolean isNumberOfDuplicatesAboveLimit( Set first, Set second, int limit) { int result = 0; for (Integer i : first) { if (second.contains(i)) { result++; if (result >= limit) { return true; } } } return false; } /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub List> sets = new LinkedList>() {{ add(setOf(12,14,222,998,1,89,43,22,7654,23)); add(setOf(44,23,64,76,987,3,2345,443,431,88)); add(setOf(998,22,7654,345,112,32,89,9842,31,23)); }}; List> resultset = new LinkedList>(); loop: for (Set curr : sets) { for (Set existing : resultset) { if (isNumberOfDuplicatesAboveLimit(curr, existing, 5)) { continue loop; } } // no overlapping with the previous instances resultset.add(curr); } System.out.println(resultset); } } 

我不是Big O表示法的专家，但我认为这个算法是O（N * M ^ 2），其中N是集合中元素的数量，M是集合的总数（基于循环数量I）在算法中使用）。 我冒昧地定义了我认为重叠的东西。

我认为你的问题是Polinomial。 当我记得我的讲座时，基于决策的版本将是NP难的 – 但如果我错了，请纠正我。

Answer 9

这是一个简单的问题，因为你的套装限制为十个。 对于每组十个数字，您有少于1,000个集合的子集，其中包含至少五个数字。 选择将整数序列散列为32位数字的散列函数。 对于每组十个整数，为具有五个或更多元素的每个整数子集计算此散列函数的值。 这为每组十个数字提供少于1,000个哈希值。 在所有这1,000个键下的哈希表中添加一个指向十个整数集的指针。 完成此操作后，您的哈希表有1,000 * 10,000 = 1000万个条目，这是完全可行的; 并且这第一遍是线性的（O（n））因为单个集合大小以10为界。

在下一个传递中，以任何顺序迭代所有哈希值。 每当有多个集合与相同的散列值相关联时，这意味着它们很可能包含至少五个整数的公共子集。 validation这一点，然后擦除其中一个集和相应的哈希表条目。 继续浏览哈希表。 这也是O（n）步骤。

最后，假设您在C中执行此操作。这是一个例程，用于计算单个十个整数集的哈希值。 假设整数按升序排列：

 static int hash_index; void calculate_hash(int *myset, unsigned int *hash_values) { hash_index = 0; hrec(myset, hash_values, 0, 0, 0); } void hrec(int *myset, unsigned int *hash_values, unsigned int h, int idx, int card) { if (idx == 10) { if (card >= 5) { hash_values[hash_index++] = h; } return; } unsigned int hp = h; hp += (myset[idx]) + 0xf0f0f0f0; hp += (hp << 13) | (hp >> 19); hp *= 0x7777; hp += (hp << 13) | (hp >> 19); hrec(myset, hash_values, hp, idx + 1, card + 1); hrec(myset, hash_values, h, idx + 1, card); } 

这将递归所有1024个子集，并在hash_values数组中存储基数为5或更多的子集的哈希值。 最后，hash_index计算有效条目的数量。 它当然是不变的，但我没有在这里用数字计算它。

Answer 10

让我们假设您有一个NumberSet类来实现您的无序集（并且可以枚举int以获取数字）。 然后，您需要以下数据结构和算法：

• Map> numberSets
• Map, int> matchCount
• Pair是一个关键对象，它为每个具有相同X和Y的实例返回相同的哈希码和相等（无论它们是否被交换）

现在为每个要添加/比较的集合执行以下操作（伪代码!!!）：

 for (int number: setToAdd) { Set numbers = numberSets.get(number); if (numbers == null) { numbers = new HashSet(); numberSets.put(number, numbers); } else { for (NumberSet numberSet: numbers) { Pair pairKey = new Pair(numberSet, setToAdd); matchCount.put(pairKey, matchCount.get(pairKey)+1); // make sure to handle null as 0 here in real code ;) } } numbers.add(number); } 

在任何时候你都可以通过这些配对，每个数量为5或更大的配对显示重复。

注意：删除集合可能是一个坏主意，因为如果A被认为是B的副本，而B是C的副本，那么C不必是A的副本。所以如果你删除B，你会不要删除C，并且添加集合的顺序将变得很重要。

Answer 11

我们将采用数据集，用签名装饰每个元素，然后对其进行排序。 签名具有以下属性：排序将这些元素组合在一起，这些元素可能具有重复。 当将data_set [j]与data_set [j + 1 …]中的项进行比较时，当[j + 1 …]中的第一个签名重复检查失败时，我们推进i。 这种“邻接标准”确保我们不必进一步观察; 除此之外的任何元素都不能重复。

这大大减少了O（N ^ 2）的比较。 我将让算法分析师决定多少，但下面的代码进行~400k比较，而不是100m的天真O（N ^ 2）。

签名从分支元素开始。 我们将数字的范围划分为N个相等大小的桶：1..k，k + 1..2k，2k + 1..3k，…当迭代元素时，如果数字落入则我们递增计数一个特殊的桶。 这产生了forms的初始签名（0,0,0,1,3,0,0，… 4,2）。

签名具有if的属性

 sum(min(sig_a[i], sig_b[i]) for i in range(10)) >= 5 

然后，与签名相关联的元素可能具有至少5个重复。 但更重要的是，如果上述情况不成立，则元素不能有5个重复。 让我们称之为“签名匹配标准”。

但是，按上述签名排序不具有上述的邻接属性。 但是，如果我们将签名修改为两个元素forms：

 (sum(sig[:-1]), sig[-1]) 

然后“签名匹配标准”成立。 但邻接标准是否成立？ 是。 该签名的总和为10.如果我们枚举，我们有以下可能的签名：

 (0,10) (1, 9) (2, 8) (3, 7) (4, 6) (5, 5) (6, 4) (7, 3) (8, 2) (9, 1) (10,0) 

如果我们将（0,10）与（1,9）…（10,0）进行比较，我们注意到一旦签名测试失败，它再也不会成为现实。 邻接标准成立。 此外，该邻接标准适用于所有正值，而不仅仅是“5”。

好的，这很好，但将签名分成两个大桶不一定会减少O（N ^ 2）搜索; 签名过于笼统。 我们通过为sig [： – 1]创建签名来解决这个问题

 (sum(sig[:-1]), sig[-1]), (sum(sig[:-2]), sig[-2]), ... 

等等。 我相信这个签名仍然满足邻接，但我可能是错的。

我没有做一些优化：签名只需要每个元组的最后一个值，而不是第一个，但是必须修改排序步骤。 此外，当很明显进一步扫描不能成功时，可以通过早期失败来优化签名比较。

 # python 3.0 import random # M number of elements, N size of each element M = 10000 N = 10 # Bounds on the size of an element of each set Vmin,Vmax = 0, (1 << 12) # DupCount is number of identical numbers required for a duplicate DupCount = 5 # R random number generator, same sequence each time through R = random.Random() R.seed(42) # Create a data set of roughly the correct size data_set = [list(s) for s in (set(R.randint(Vmin, Vmax) for n in range(N)) for m in range(M)) if len(s) == N] # Adorn the data_set signatures and sort def signature(element, width, n): "Return a signature for the element" def pearl(l, s): def accrete(l, s, last, out): if last == 0: return out r = l[last] return accrete(l, sr, last-1, out+[(sr,r)]) return accrete(l, s, len(l)-1, []) l = (n+1) * [0] for i in element: l[i // width] += 1 return pearl(l, len(element)) # O(n lg(n)) - with only 10k elements, lg(n) is a little over 13 adorned_data_set = sorted([signature(element, (Vmax-Vmin+1)//12, 12), element] for element in data_set) # Count the number of possible intersections def compare_signatures(sig_a, sig_b, n=DupCount): "Return true if the signatures are compatible" for ((head_a, tail_a), (head_b, tail_b)) in zip(sig_a, sig_b): n -= min(tail_a, tail_b) if n <= 0: return True return False k = n = 0 for i, (sig_a, element_a) in enumerate(adorned_data_set): if not element_a: continue for j in range(i+1, len(adorned_data_set)): sig_b, element_b = adorned_data_set[j] if not element_b: continue k += 1 if compare_signatures(sig_a, sig_b): # here element_a and element_b would be compared for equality # and the duplicate removed by adorned_data_set[j][1] = [] n += 1 else: break print("maximum of %d out of %d comparisons required" % (n,k)) 

Answer 12

看起来你想使用HashSet类。 这应该给你O(1)查询时间，如果你的循环正确，这应该给出非常有效的比较。 （我不是在这里讨论算法，而是简单地建议一个数据结构，以防它有用。）