使用给定的度量将一组元素匹配到另一组

Question

首先，我想说我不是在找代码，我是在找算法。

动机：

我正在编写复杂实时软件系统的顶级测试。它运行所有软件组件（~20 个进程，~100 个线程），设置假数据源（rtsp 视频源）并将准备好的数据（视频文件）提供给系统，记录系统响应（事件），然后发送所有准备好的测试数据后停止系统。

由于测试数据始终相同，我希望被测系统在正确的时间（从测试开始）提供正确的响应（事件）。

然后我将生成的响应（事件）与预期事件（手动准备）进行比较，我希望它们都在那里，可能会有一些小的时间差异，我会用一些给定的 time-tolerance 来限制，让我们说5 秒。

假设测试系统应该在 1500 秒长的视频中检测动物，我看了它并记下了 5 只动物和它们出现在视频中的时间：

at   10s - a sparrow
at   20s - a cat
at   50s - a rabbit
at  100s - an owl
at 1000s - a bear

基于此，我会写 expected_events set:

expected_events = [
    Event(10, 'sparrow'),
    Event(20, 'cat'),
    Event(50, 'rabbit'),
    Event(100, 'owl')
    Event(1000, 'bear')
]

并且我希望能够判断实际检测到的事件（这将受到处理器负载、磁盘使用、网络使用 atd 的影响，因为这是真实计算机上的多进程系统）匹配这些expected_eevents.

假设测试系统返回：

detected_events = [
    Event(10.1, 'sparrow'),
    Event(19.5, 'cat'),
    Event(50.2, 'rabbit'),
    Event(99.3, 'owl')
    Event(1000.2, 'bear')
]

我认为这是正确的，与预期事件 100% 匹配，所有事件都存在且时差低于 time-tolerance:

matches = [
    {'name': 'sparrow', 'detected': 10.1,   'expected': 10,   'time-diff': 0.1},
    {'name': 'cat',     'detected': 19.5,   'expected': 20,   'time-diff': 0.5},
    {'name': 'rabbit',  'detected': 50.2,   'expected': 50,   'time-diff': 0.2},
    {'name': 'owl',     'detected': 99.3,   'expected': 100,  'time-diff': 0.7},
    {'name': 'bear',    'detected': 1000.2, 'expected': 1000, 'time-diff': 0.2},
]

如果被测系统返回：

detected_events = [
    Event(10.1, 'sparrow'),
    Event(50.2, 'rabbit'),
    Event(99.3, 'owl')
    Event(1010.5, 'bear')
]

我希望这会导致这样的匹配：

raw_matches = [
    {'name': 'sparrow', 'detected': 10.1,   'expected': 10,   'time-diff': 0.1},
    {'name': 'cat',     'detected': None,   'expected': 20,   'time-diff': None},
    {'name': 'rabbit',  'detected': 50.2,   'expected': 50,   'time-diff': 0.2},
    {'name': 'owl',     'detected': 99.3,   'expected': 100,  'time-diff': 0.7},
    {'name': 'bear',    'detected': 1010.5, 'expected': 1000, 'time-diff': 10.52},
]

pruned_matches = [
    {'name': 'sparrow', 'detected': 10.1,   'expected': 10,   'time-diff': 0.1},
    {'name': 'rabbit',  'detected': 50.2,   'expected': 50,   'time-diff': 0.2},
    {'name': 'owl',     'detected': 99.3,   'expected': 100,  'time-diff': 0.7},
]

我认为这是失败的，因为：

没有检测到猫
熊被发现晚了 10.5 秒
因此 5 个中只有 3 个真正匹配，结果应该是 60% 匹配

所以我需要的是一种针对 expected_events 评估 detected_events 的方法，以便能够评估测试系统的工作情况。

简化

因为匹配事件类型对这个问题来说是必不可少的，可以分别匹配每个事件类型来完成，我将做以下简单化：

所有事件都是相同的 - 即只有事件的时间很重要，因此事件将仅由时间戳表示
时间戳将是 int 以便于阅读

我认为什么是“好”匹配：

正如你们中的许多人在评论中指出的那样，除了排除时差 > time-tolerance 的匹配之外，我实际上没有评估最终匹配的指标。这让事情变得有点困难，但我认为这是直观的——我知道什么时候应该发生什么，我将其与实际事件进行比较，我会尽可能地匹配它们以确保：

尽可能多的预期事件被匹配
每个 detected_event 匹配 expected_event 必须在给定的时间容限内同时发生。

所以我会考虑“正确”匹配（时间容差为 5 秒）：

                                  matches = [
expected_events = [10, 20]  =>        {'expected': 10,    'detected': 10},
detected_events = [10, 20]            {'expected': 20,    'detected': 20},
                                  ]

                                  matches = [
expected_events = [10, 20]  =>        {'expected': 10,    'detected': 15},
detected_events = [15, 25]            {'expected': 20,    'detected': 25},
                                  ]

                                  matches = [
expected_events = [10, 20]  =>        {'expected': 10,    'detected':  5},
detected_events = [ 5, 15]            {'expected': 20,    'detected': 15},
                                  ]

                                  matches = [
expected_events = [10, 11]  =>        {'expected': 10,    'detected': 11},
detected_events = [11, 12]            {'expected': 11,    'detected': 12},
                                  ]


                                  matches = [
expected_events = [10, 20]  =>        {'expected': 10,    'detected': 10},
detected_events = [10, 26]        ]

expected_events = [10, 20]  =>    matches = []
detected_events = [ 4, 26]

                                  matches = [
expected_events = [10, 20, 30] =>     {'expected': 20,    'detected': 17},
detected_events = [17, 24]        ]

我会认为这是“糟糕”的匹配（即这不是我想要的）：

                                  matches = [
expected_events = [10, 20]  =>        {'expected': 20,    'detected': 15},
detected_events = [15, 25]        ]
# matched only 1 events even though it's possible to match 2

                                  matches = [
expected_events = [10, 11]  =>        {'expected': 11,    'detected': 11},
detected_events = [11, 12]        ]
# matched only 1 events even though it's possible to match 2


                                  matches = [
expected_events = [10, 20]  =>        {'expected': 10,    'detected': 4},
detected_events = [ 4, 26]            {'expected': 20,    'detected': 26},
                                  ]
# should not match anything, time differences > 5sec

伪代码/我试过的：

代码应如下所示：

expected_events = [10, 20, 50, 100, 1000] # times in second
detected_events = [11, 18, 51,      1001]

def metric(ev1, ev2):
    return abs(ev1 - ev2)

matches = match_events(expected_events, detected_events, metric, tolerance=5)

简单、幼稚的方法 - 从最佳匹配开始

我尝试了非常简单的方法：
- （expected_events、detected_events）的产品
- 计算时差
- 过滤器匹配时差大于给定容差
- 按时差排序比赛
- 从第一个匹配开始匹配并丢弃“冲突”（即后面的匹配使用相同的元素）
这适用于简单的情况，但我运行在事件“转移”时遇到问题：
```
 expected_events = [10, 11]
 detected_events = [11, 12] 
```
现在我得到：
```
 [
     {'expected': 11,    'detected': 11},
 ]
```
虽然我想要：
```
 [
     {'expected': 10,    'detected': 11},
     {'expected': 11,    'detected': 12},
 ]
```
蛮力-排列

然后我尝试了暴力破解：
- （expected_events、detected_events）的产品
- 计算时差
- 过滤器匹配时差大于给定容差
- 创建给定匹配的所有可能排列
- 对于每个排列，从第一个匹配开始匹配并丢弃“冲突”（即后面的匹配使用相同的元素）
- 计算所有这些匹配的长度
- 只保留最大长度的那些
- select匹配最小值（按所有时间差之和排序）
这可行，但如您所料，它对于长度超过几个元素的任何内容来说都太慢了。（我希望使用惰性求值让它工作，但没能成功）。

问题：

这种匹配的正确算法是什么？在我看来，这可能已经 解决了问题 - 但我不知道要搜索什么。

它是一个已解决的问题 - 分配问题 - https://en.wikipedia.org/wiki/Assignment_problem -感谢 Yossi Levi！

Answer 1

我会按照您的要求提供一个 non-programming 方法，但在我看来只是合乎逻辑的 (semi-mathematical) 方法。

算法步骤：

让我们将阈值定义为 T
用无关值填充较小的列表（例如None）——只是为了确保尺寸一致
通过将一个列表中的每个元素与另一个列表中的元素相减的绝对值来创建相似度矩阵，让我们将矩阵定义为S。

说明：S[i,j]指列表A中的第i个元素与列表B中的第j个元素之间的差异

创建二进制矩阵B，其中满足阈值条件的每个元素为1，否则为0 (MATLAB-> B=S

例如：

       0 0 0
    
B =    0 1 1
    
       1 0 0

说 X 维度代表列表 A，Y 代表列表 B 那么：

B[2] === A[2]
B[2] === A[3]
B[3] === A[1] (=== means that two elements satisfy the criteria of similarity)

现在 - 问题变得更加数学化，为了找到最佳匹配，您可以使用以下建议之一：

蛮力（我认为不太优雅的方法）：

选择为 1 的元素（在未标记的行和列中）
将他的整个列和行标记为已标记
继续选择另外1个，直到没有合法的地方，总和为score
对所有选项迭代执行并选择最高的选项score

更优雅的做法：

迭代列的所有排列（对于 B 矩阵）
if Trace or opposite-diagonal equals to len(A) then finish (found matching for all elements)
选择具有最高 TRACE（或相反对角线）的排列最坏情况下的排列数是 of-course N！（其中N是B的维度）

最佳方法：

在网上搜索如何在只允许列交换的情况下找到矩阵的最大轨迹时，我将运行转换为 this（请注意 Example 和 矩阵解释 部分）。此外，我在 PyPI package.

中找到了它的实现

正如文档所说 - 该算法试图找到 最小值 跟踪所有可能的矩阵排列 - 所以只需使用 -B 作为参数即可。

总体示例（最后一步采用更优雅的方法）：

A = [1,5,7]
B = [6,6,2]

T = 2

S = 
5 5 1 
1 1 3
1 1 5

B = 
0 0 1
1 1 0
1 1 0

permutations of columns:

1- 
0 0 1
1 1 0
1 1 0

Trace = 1
other-diagonal = 3

Done -- > no need for more permutations because len(other-diagonal) == 3
A[1] =1 === B[3] =2
A[2] =5 === B[2] =6
A[3] =7 === B[1] =6

随时提问，或提供您可能有的任何见解

使用给定的度量将一组元素匹配到另一组

matching elements from one set to another using given metric

python

algorithm

matching

动机：

简化

我认为什么是“好”匹配：

伪代码/我试过的：

问题：