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

debugcn 发表于 Dev

扬·斯普尔尼

首先，我想说的是我不是在寻找代码，而是在寻找一种算法。

动机：

我正在编写一个复杂的实时软件系统的顶级测试。它运行所有软件组件（约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_eventsset：

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％匹配

所以我我需要的是评估方法detected_events对expected_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）的乘积
- 计算时差
- 过滤器匹配的时间差大于给定的容差
- 创建给定匹配的所有可能排列
- 对于每个排列，从第一个匹配开始匹配，并丢弃“冲突”（即，后一个匹配使用相同的元素）
- 计算所有这些匹配的长度
- 只保留那些长度最大的
- 选择与min匹配（按所有时间差之和排序）
这行得通，但是正如您可能预期的那样，对于任何长度不超过几个元素的东西来说都太慢了。（我希望使用惰性评估使其有效，但无法使其正常工作）。

题：

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

这是一个解决问题-分配问题- https://en.wikipedia.org/wiki/Assignment_problem -感谢贝纳列维！

尤西·列维（Yossi Levi）

我将按照您的要求，提供一种非编程方法，但按照我的观点，它仅是逻辑（半数学）方法。

算法步骤：

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

澄清：S [i，j]是指列表A中第i个元素与列表B中第j个元素之间的差

创建二进制矩阵B，其中满足阈值critirea的每个元素均为1，否则为0（MATLAB-> B = S <L）

例如：

       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矩阵）
如果迹线或对角线对角线等于len（A），则完成（找到所有元素的匹配项）
选择具有最高TRACE（或相反对角线）排列的排列，最坏情况下排列的排列当然是N！（其中N是B的尺寸）

最佳方法：

在网上搜索如何在只有列交换允许的情况下如何查找矩阵的最大迹线时遇到了这个问题（请注意“示例”和“矩阵解释”部分）。此外，我在PyPI包中找到了它的实现。

如文档所述-算法正在尝试在矩阵的所有可能排列中找到最小的Trace-因此，请仅使用-Bas参数进行调用。

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

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

随时询问或提供您可能有的见解

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。

编辑于2021-04-5

我来说两句

0条评论

登录后参与评论

来自分类Dev

Related 相关文章

文章