4

由于我不知道我现在在做什么，我的措辞可能听起来很有趣。但说真的，我需要学习。

我面临的问题是提出一种方法（模型）来估计软件程序的工作方式：即运行时间和最大内存使用量。我已经拥有的是大量数据。该数据集概述了程序在不同条件下的工作方式，例如

<code>
RUN     Criterion_A  Criterion_B  Criterion_C  Criterion_D  Criterion_E <br>
------------------------------------------------------------------------
R0001           12         2           3556            27           9 <br>      
R0002            2         5           2154            22           8 <br>
R0003           19        12           5556            37           9 <br>
R0004           10         3           1556             7           9 <br>
R0005           5          1            556            17           8 <br>
</code>

我有成千上万行这样的数据。现在，如果我提前知道所有标准，我需要知道如何估计（预测）运行时间和最大内存使用量。我需要的是一个给出提示（上限或范围）的近似值。

我感觉这是典型的？？？我不知道的问题。你们能给我一些提示或给我一些想法（理论、解释、网页）或任何可能有帮助的东西。谢谢！

4

2 回答 2

5

您需要一个将一个或多个条件作为输入的新程序，然后输出对运行时间或内存使用情况的估计。这是一个机器学习问题。

您的输入可以列为数字向量，如下所示：

input = [ A, B, C, D, E ]

最简单的算法之一是K-最近邻算法。这背后的想法是，您将获取输入的数字向量，并在数据库中找到与输入向量最相似的数字向量。例如，给定这个输入向量：

input = [ 11, 1.8, 3557, 29, 10 ]

您可以假设运行时间和内存应该与这次运行的值非常相似（最初在上面列出的表格中）：

R0001           12         2           3556            27           9

有几种算法可以计算这两个向量之间的相似度，其中一种简单直观的算法是欧几里得距离。例如，输入向量和表格中的向量之间的欧几里得距离是这样的：

dist = sqrt( (11-12)^2 + (1.8-2)^2 + (3557-3556)^2 + (27-29)^2 + (9-10)^2 )
dist = 2.6533

应该直观地清楚，距离较小的点应该更好地估计运行时间和内存使用情况，因为距离应该描述两组标准之间的相似性。假设您的标准信息丰富且经过精心挑选，具有相似标准的点应该具有相似的运行时间和内存使用情况。

以下是如何在 R 中执行此操作的一些示例代码：

r1 = c(11,1.8,3557,29,10)
r2 = c(12,2.0,3556,27, 9)

print(r1)
print(r2)

dist_r1_r2 = sqrt( (11-12)^2 + (1.8-2)^2 + (3557-3556)^2 + (27-29)^2 + (9-10)^2 ) 
print(dist_r1_r2)
smarter_dist_r1_r2 = sqrt( sum( (r1 - r2)^2 ) ) 
print(smarter_dist_r1_r2)

取最近行的运行时间和内存使用情况是 K=1 的 KNN 算法。通过从数据库中获取多行的加权组合，可以将此方法扩展为包括来自多行的数据，其中与输入向量距离较小的行对估计的贡献更大。阅读 KNN 上的 Wikipedia 页面以获取更多信息，尤其是关于数据规范化的信息，包括来自多个点的贡献和计算距离。

在计算这些输入向量列表之间的差异时，您应该考虑对数据进行归一化。这样做的理由是，标准 C 的 3557 和 3556 之间相差 1 个单位可能不等于标准 A 的 11 和 12 之间的差 1。如果您的数据是正态分布的，您可以将它们全部转换为标准使用此公式的分数（或 Z 分数） ：

N_trans = (N - mean(N)) / sdev(N)

归一化数据的“正确”方法没有通用解决方案，因为它取决于您拥有的数据的类型和范围，但 Z 分数很容易计算，是一种首先尝试的好方法。

有许多更复杂的技术可用于构建诸如此类的估计，包括线性回归、支持向量回归和非线性建模。一些更复杂的方法背后的想法是，您尝试开发一个方程来描述变量与运行时间或内存之间的关系。例如，一个简单的应用程序可能只有一个标准，您可以尝试区分以下模型：

running_time = s1 * A + s0
running_time = s2 * A^2 + s1 * A + s0
running_time = s3 * log(A) + s2 * A^2 + s1 * A + s0

这个想法是 A 是您的固定标准，而 sN 是您可以调整的自由参数列表，直到您获得一个运行良好的模型。

这种方法的一个问题是有许多不同的可能模型具有不同数量的参数。区分具有不同数量参数的模型是统计学中的一个难题，我不建议您在第一次涉足机器学习时解决它。

您应该问自己的一些问题是：

  1. 我的所有标准都会影响运行时间和内存使用吗？有些是否只影响其中一个，而从预测的角度来看，有些是无用的？回答这个问题称为特征选择，是机器学习中的一个突出问题。
  2. 您对变量应如何影响运行时间或内存使用有任何先验估计吗？例如，您可能知道您的应用程序使用时间为 N * log(N) 的排序算法，这意味着您明确知道一个标准与运行时间之间的关系。
  3. 您的测量输入标准行与运行时间和内存使用情况配对是否涵盖了您的应用程序的所有可能用例？如果是这样，那么您的估计会好得多，因为机器学习可能很难处理它不熟悉的数据。
  4. 您的程序的运行时间和内存是否取决于您未输入到估算策略中的标准？例如，如果您依赖外部资源（例如网络蜘蛛），则网络问题可能会以难以预测的方式影响运行时间和内存使用。如果是这种情况，您的估计会有更多的差异。
于 2010-07-05T00:59:37.470 回答
2

如果您要预测的标准在当前已知标准的范围内，那么您应该对插值过程进行更多研究：

在数值分析的数学子领域中，插值是一种在一组离散的已知数据点范围内构造新数据点的方法

如果它超出您当前已知的数据范围研究外推不太准确：

在数学中，外推是在一组离散的已知数据点之外构建新数据点的过程。

方法

于 2010-07-05T00:13:43.393 回答