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

Question

我有很多套数字.每个集合包含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

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

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

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