使用给定的度量将一组元素匹配到另一组
首先，我想说我不是在寻找代码，我是在寻找算法。
动机：
我正在编写复杂实时软件系统的顶级测试。它运行所有软件组件（约 20 个进程，约 100 个线程），设置假数据源（rtsp 视频源）并将准备好的数据（视频文件）提供给系统，记录系统响应（事件），然后停止系统准备好的测试数据已发送。
由于测试数据始终相同，我希望测试的系统能够在正确的时间（从测试开始）提供正确的响应（事件）。
然后，我将生成的响应（事件）与预期事件（手动准备）进行比较，我希望这些事件都在那里，可能会有一些小的时间差异，我会限制一些给定的时间差异，比如说 5 秒time-tolerance。
假设测试的系统应该在 1500 秒长的视频中检测动物，我观看了它并记下了 5 种动物以及它们出现在视频中的时间：
at 10s - a sparrow
at 20s - a cat
at 50s - a rabbit
at 100s - an owl
at 1000s - a bear
基于此，我会编写expected_events集合：
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')
]
我认为这是失败的，因为：
它没有检测到猫
熊被发现晚了 10.5 秒
因此，只有 5 个中的 3 个真正匹配，结果应该是 60% 匹配
因此，我需要一种评估方法，detected_events以便expected_events能够评估被测试系统的工作效果。
简单化
由于匹配事件类型对于解决问题至关重要，并且可以单独匹配每个事件类型，因此我将进行以下简单说明：
所有事件都是相同的 - 即只有事件的时间很重要，因此事件将仅由时间戳表示
时间戳将使其
int更易于阅读
我认为什么是“好的”匹配：
正如你们许多人在评论中指出的那样，除了忽略具有时间差 > 的匹配之外，实际上我没有评估最终匹配的指标time-tolerance。这使得它变得有点困难，但我认为它很直观 - 我知道什么时候应该发生什么，我将其与实际事件进行比较，我会尝试尽可能地匹配它们以确保：
匹配尽可能多的预期事件
每个
detected_event匹配expected_event必须在给定的时间容限内同时发生。
所以我会考虑“正确”匹配（有 5 秒的时间容差）：
Qyouu2回答
-
慕斯王
我将遵循您的要求，并提供一种非编程方法，但仅是我认为的逻辑（半数学）方法。算法步骤：让我们将阈值定义为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 矩阵）如果 Trace 或对角线等于 len(A) 则完成（找到所有元素的匹配）选择具有最高 TRACE（或相反对角线）的排列 最坏情况下的排列数量当然是 N！（其中N是B的维度）正如文档所述 - 该算法试图找到所有可能的矩阵排列的最小跟踪 - 因此只需将其-B作为参数即可。总体示例（最后一步采用更优雅的方法）：A = [1,5,7]B = [6,6,2]T = 2S = 5 5 1 1 1 31 1 5B = 0 0 11 1 01 1 0permutations of columns:1- 0 0 11 1 01 1 0Trace = 1other-diagonal = 3Done -- > no need for more permutations because len(other-diagonal) == 3A[1] =1 === B[3] =2A[2] =5 === B[2] =6A[3] =7 === B[1] =6请随意询问，或提供您可能有的任何见解 -
慕仙森
我刚刚发现 scipy python 包中“匈牙利算法”（赋值问题）有很好的实现：https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html示例（对于expected, detected，metric请参阅问题的示例代码）：from scipy.optimize import linear_sum_assignment...def match_events(expected, detected, metric, tolerance=5): # some arbitrary large value used to prevent impossible matches dont_match = 1000 * tolerance def modified_metric(e, d): dt = metric(e, d) return dt if dt <= tolerance else dont_match cost_matrix = [ [ modified_metric(exp, det) for det in detected ] for exp in expected ] row_idx, col_idx = linear_sum_assignment(cost_matrix) for e_idx, d_idx in zip(row_idx, col_idx): dt = cost_matrix[e_idx][d_idx] if dt <= time_tolerance: yield (expected[e_idx], detected[d_idx], dt)它不是很优雅，因为我必须以某种方式将匹配限制为tolerance，但匈牙利算法仅适用于所有可能组合的矩阵，因此我使用dont_matchvalue 来标记这些情况。
随时随地看视频慕课网APP
相关分类
Python