我正在尝试计算两个集合之间的一种模糊Jaccard指数，其基本原理如下:作为Jaccard指数，我想计算两个集合中共同的项目数量与两个集合中不同项目总数之间的比率。问题是，我想使用一个带有阈值的相似性函数来确定在两个集合中什么算作"相同"的项目，以便相似的项目:
- 在union中不会被计算两次
- 被计算在交叉路口
我有一个工作的实现在这里(在python中):
def fuzzy_jaccard(set1, set2, similarity, threshold):
intersection_size = union_size = len(set1 & set2)
shorter_difference, longer_difference = sorted([set2 - set1, set1 - set2], key=len)
while len(shorter_difference) > 0:
item1, item2 = max(
itertools.product(longer_difference, shorter_difference),
key=lambda (a, b): similarity(a, b)
)
longer_difference.remove(item1)
shorter_difference.remove(item2)
if similarity(item1, item2) > threshold:
union_size += 1
intersection_size += 1
else:
union_size += 2
union_size = union_size + len(longer_difference)
return intersection_size / union_size
这里的问题是集合的大小是二次的，因为在itertools.product中，我迭代所有可能的元素对，从每个集合(*)中取一个。现在，我认为我必须这样做，因为我想将set1中的每个项目a与set2中的最佳候选b相匹配，并且set1中的另一个项目a'不太相似。
我有一种感觉，应该有一个O(n)的方式，我没有抓住。你有什么建议吗?
还有其他两个问题，比如一旦我得到最佳匹配，就重新计算每对的相似性，但我不太关心它们。
我怀疑在一般情况下是否有可能是O(n)，但至少在大多数情况下，你可能会做得比O(n^2)好得多。
相似性是可传递的吗?我的意思是:你能不能假设距离(a, c) <=距离(a, b) +距离(b, c)?如果不是，这个答案可能不会有帮助。我把相似性当作距离来对待。
尝试聚集数据:
选择半径r。基于直觉，我建议将r设置为您计算的前5个相似度平均值的三分之一，或者其他。
在set1中选取的第一个点成为第一个簇的中心。将set2中的点分类为在簇内(与中心点相似<= r)或在簇外。还要跟踪距离团块中心2r以内的点。
可以要求团簇中心点之间的距离至少为2r;在这种情况下，有些点可能不在任何团块中。我建议至少让他们从彼此。(如果您处理的是大量维度，则可能更少。)你可以把每个点都当作团块的中心，但这样就不会节省任何处理时间。
当你选择一个新的点时，首先将它与集群中心点进行比较(即使它们在同一个集合中)。它要么在一个已经存在的团块中，要么成为一个新的团块中心，(或者如果它在团块中心的r和2r之间，也可能两者都不是)。如果它在一个簇中心的r范围内，然后将它与另一个集合中距离该簇中心2r范围内的所有点进行比较。您可以忽略距离团块中心2r以上的点。如果你在集群中找不到一个相似的点(可能是因为集群没有点了)，那么你可能需要扫描所有剩下的点来寻找这种情况。希望这种情况只会发生在集合中剩下的点不多的时候。如果这很有效，那么在大多数情况下，你会找到簇中最相似的点，并知道它是最相似的点。
这个想法可能需要一些调整。
如果涉及到大量的维度，那么你可能会发现，对于给定的半径r，令人沮丧的是，许多点在2r以内，而很少点在r以内。
这是另一个算法。计算相似度函数越耗时(与维护排序的点列表所花费的时间相比)，您可能希望拥有的索引点就越多。如果您知道维数，那么使用索引点的数量可能是有意义的。如果一个点与另一个索引点太相似，可以拒绝作为候选索引点。
对于您使用的第一个点和您决定用作索引点的任何其他点，生成另一个集合中所有剩余点的列表，按照与索引点的距离排序，
当你比较点P1和另一个集合中的点时，我认为你可以跳过集合，可能有两个原因。考虑你找到的和p最相似的点。如果P2与索引点相似，则可以跳过与该索引点完全不同的所有点。如果P2与索引点不同，则可以跳过与该索引点足够相似的所有点。我认为在某些情况下，对于同一个索引点，你可以跳过这两种类型的点