如何为巨大的输入集绘制算法运行时?

机器算法验证 数据可视化 标准差 标准错误 异常值 算法
2022-04-14 04:30:28

对于我的学士论文,我想比较两种算法的运行时间。运行时间是通过让这些算法针对庞大输入集中的每个值运行来衡量的。该输入集可以划分为三个子集X1,X2,X3. 每个子集包含 40,000 个值,算法对每个值执行一次。在我的情节中,我想在 x 轴上设置输入集,在 y 轴上设置每个集的运行时间。这种数据的良好表示是什么?

我首先尝试了一个散点图,但由于一些值真的很离群,所以该图的比例将最重要的值压缩到视觉上无法区分的区域。然后我叠加了平均值的线,标准偏差的误差线:

散点图

这清楚地表明了这些异常值有多远和少。在平均值线下甚至无法识别非离群值散点值,它们本身不是很容易区分。因为这些异常值对我的评估并不重要,所以我决定将图表更改为仅显示具有标准偏差的平均值:

具有标准偏差的平均值

这些部分改善了这种情况,但为了将标准偏差拟合到图上,平均值仍然有些接近。但我觉得删除误差线既不真实,也不科学准确。此外,像这样绘制数据会使误差线低于零,这表明数据的表示不好,因为时间值低于零显然是不可能的。

如何更好地表示这样的数据?在这种情况下,显示平均值实际上是一个好主意吗?或者像中位数这样的其他特征会更好吗?或者甚至从该数据中删除构成进一步异常值的 5%?

此外,我不知道误差线的良好格式是什么,可以避免它们低于零的情况。是否有高于平均值的标准偏差和低于平均值的标准偏差,然后我可以不对称地绘制?

我都在寻找对这个特殊案例的洞察力和关于如何展示数据的资源。如果有人想自己尝试一下,我将每个数据点的前 100 个值设为可用(上面的图表是用这些制作的): http: //pastebin.com/sjdPy8Np

4个回答

继续评论主题,您应该为异常值找到解释,以了解是包含它们还是隔离它们。我注意到异常值奇怪地聚集在一起。一个输入集行的异常值似乎经常与另一个输入集中同一行的异常值一起出现。

在此处输入图像描述

关于您的图表,一旦您解决了异常值问题,箱线图可能是一个可行的选择。这是一个带有异常值的版本,但使用了对数变换(如果算法有乘法方面,这可能是合适的)。

在此处输入图像描述

这失去了行内相关性。为了强调这些,您可以对同一行中的值使用相同的标记符号(直到您用完符号!)。另一种方法是平行坐标图,其中每一行都由一条连接线表示。

在此处输入图像描述

最后,不要觉得有义务在一个情节中总结您的所有发现。

顺便说一句,如果您发布更多数据,请使用计算机友好格式,例如 CSV 或 JSON。

每个输入集的最小值可能是最多信息的。许多令人讨厌的因素会降低您的基准测试速度,但很少有因素会导致代码运行得更快Python 基准测试模块timeit的文档说:

从结果向量计算平均值和标准偏差并报告这些是很诱人的。但是,这不是很有用。在典型情况下,最小值给出了机器运行给定代码片段的速度的下限;结果向量中的较高值通常不是由 Python 速度的可变性引起的,而是由其他进程干扰您的计时精度引起的。所以结果的 min() 可能是您应该感兴趣的唯一数字。之后,您应该查看整个向量并应用常识而不是统计数据。

然后,您可以求助于极值理论,以更严格地估计您的代码可能运行的最快速度。但是,这假设您的代码和数据是固定的。换句话说,你会重复这个过程X1,X2 and X3,然后尝试对结果进行一些推断(例如,比较可信区间或其他内容)。

作为替代方案,我喜欢@xan 建议在对数刻度上绘图。给定域,使用它可能更合适log2代替log10--每个增量然后对应于运行时间加倍,并且可能与您的算法的一些理论分析相匹配。

我强烈怀疑您的原始数据不是正态分布的,因为您的数据是右偏的并且它们不可能左偏(以零为界)。正如您所提到的,假设这里的正态性会导致误差估计延伸到零以下,我认为这是不合适的。您可能需要考虑原始数据的可能转换。这里有一个很好的简历帖子和一个 SixSigma 页面可以帮助您开始深思熟虑地考虑这些替代方法。

一旦您的数据符合您对例如正态性的假设,关于表示数据的问题可能会自行解决。

祝你好运!

就我而言,我会发现以下最直观和最具说明性的内容:三个图的堆栈,每个图对应一个子集,显示两种算法的估计密度曲线。(以下示例,但请注意,它们是简单的 pdf,而不是估计曲线。)

要添加更多细节,您可以包括划分您选择的分位数的垂直线。(中位数、十分位数等)

在此处输入图像描述