寻找估算方法(数据分析)

Question

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

我现在面临的问题是要拿出一个方法(模型)估算的软件程序是如何工作的:即运行时间和最大内存使用情况.我已经拥有的是大量数据.该数据集概述了程序在不同条件下的工作方式,例如

<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>

我有数千行这样的数据.现在我需要知道如果我事先知道所有标准,我如何估计(预测)运行时间和最大内存使用量.我需要的是一个给出提示(上限或范围)的近似值.

我觉得这是一个典型的??? 我不知道的问题.你们能给我一些提示或给我一些想法(理论,解释,网页)或任何可能有用的东西.谢谢!

Answer 1

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

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

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,标准C的3557和3556之间的1个单位的差异可能不等于标准A的11到12之间的差异.如果您的数据是正态分布的,您可以将它们全部转换为标准使用此公式得分(或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. 您的计划的运行时间和记忆是否取决于您未在估算策略中输入的标准？例如,如果您依赖外部资源(如网络蜘蛛),则网络问题可能会以难以预测的方式影响运行时间和内存使用.如果是这种情况,您的估算会有很多变化.