代码之家 › 专栏 › 技术社区 › CookieOfFortune

快速/简单的阵列比较算法,无需共享数据

locality-sensitive-hash matlab algorithm python

CookieOfFortune · 技术社区 · 13 年前

我有两个由两个不同的系统生成的阵列,它们彼此独立。我想通过只比较从数组中生成的几个数字来比较它们的相似性。

现在,我只比较数组的最小值、最大值和和,但我想知道是否有更好的算法?任何类型的哈希算法都需要对数组之间的小浮点差不敏感。

编辑:我想做的是验证两种算法是否生成相同的数据,而不必直接比较数据。因此,该算法应该对数据的变化敏感,对每个元素之间的微小差异相对不敏感。

2 回复 | 直到 13 年前

abarnert 13 年前

我不会试图把它减少到一个数字;只要绕过一个 tuple 的值,并编写 close_enough 比较元组的函数。

例如,您可以使用 (mean, stdev) 作为您的价值,然后定义 关闭_关闭 因为“每个数组的平均值在另一个数组的平均数的0.25标准差以内”。

def mean_stdev(a):
    return mean(a), stdev(a)

def close_enough(mean_stdev_a, mean_stdev_b):
    mean_a, stdev_a = mean_stdev_a
    mean_b, stdev_b = mean_stdev_b
    diff = abs(mean_a - mean_b)
    return (diff < 0.25 * stdev_a and diff < 0.25 * stdev_b)

显然,正确的值是您想要根据您的用例进行调优的。也许你真的想把它建立在方差(stdev的平方)、方差和偏斜、stdev和sqrt(偏斜),或者除了算术平均值之外的一些完全不同的归一化的基础上。这完全取决于你的数字代表什么,以及“足够接近”的意思。

在不了解您的应用领域的情况下,很难给出更具体的内容。例如,如果你在比较音频指纹(或DNA指纹,或指纹指纹),你会想要与比较JPEG压缩的风景图像截然不同的东西。

在你的评论中,你说你想对价值观的顺序保持敏感。为了解决这个问题,您可以生成一些序列“无序”程度的度量。例如:

diffs = [elem[0] - elem[1] for elem in zip(seq, sorted(seq))]

这将为您提供每个元素和排序位置中的元素之间的差异。您可以在此基础上构建一个类似stdev的度量(每个值的平方、平均值、sqrt),或者取平均绝对差,等等。

或者,您可以比较实际索引与“右侧”索引的距离。或者,该值与基于平均值和stdev的索引处的预期值相距多远。或者有无数的可能性。同样,哪一个合适在很大程度上取决于您的应用领域。

Meirion Hughes 13 年前

这完全取决于你对“比较它们的相似性”的定义。

你想比较哪些功能? 你能识别哪些特征? 他们的模式可以识别吗?即,在这一组中,有6个临界点,有2个不连续点。。。等

您已经提到比较最小值/最大值/总和;在评论中也谈到了均值和标准偏差。这些都是该套装的所有功能。

最终,您应该能够获得所有这些特征,并创建一个n维描述符。例如[min,max,mean,std等]

然后,您可以比较这些n维描述符,以定义其中一个描述符是否比另一个“少”、“相等”或“多”。如果你想将其他集合分类为更像“集合A”还是更像“集B”,你可以研究分类器。

请参阅:

Classifying High-Dimensional Patterns Using a Fuzzy Logic

Support Vector Machines