python-3.x - 使用整数输入的曲线拟合 Python 3.3

Question

我正在使用 scipy 的 curvefit 模块来拟合一个函数，并想知道是否有办法告诉它唯一可能的条目是整数而不是实数？关于另一种方法的任何想法？

Answer 1

在其一般形式中，整数规划问题是 NP-hard(参见 here)。有一些有效的启发式或近似算法来解决这个问题，但没有一个能保证精确的最优解。

在 scipy 中，您可以对整数系数进行网格搜索并使用，例如 curve_fit在给定整数系数的实参数上。至于网格搜索。 scipy 有 brute 功能。

例如，如果 y = a * x + b * x^2 + some-noise在哪里 a必须是整数，这可能有效:

使用 a = 5 生成一些测试数据和 b = -1.5 :

coef, n = [5, - 1.5], 50
xs = np.linspace(0, 10, n)[:,np.newaxis]
xs = np.hstack([xs, xs**2])
noise = 2 * np.random.randn(n)
ys = np.dot(xs, coef) + noise

给定整数系数的函数使用 curve_fit 拟合实系数方法:

def optfloat(intcoef, xs, ys):
    from scipy.optimize import curve_fit
    def poly(xs, floatcoef):
        return np.dot(xs, [intcoef, floatcoef])
    popt, pcov = curve_fit(poly, xs, ys)
    errsqr = np.linalg.norm(poly(xs, popt) - ys)
    return dict(errsqr=errsqr, floatcoef=popt)

给定整数系数的函数，使用上述函数优化浮点系数并返回错误:

def errfun(intcoef, *args):
    xs, ys = args
    return optfloat(intcoef, xs, ys)['errsqr']

最小化 errfun使用 scipy.optimize.brute找到最佳整数系数并调用optfloat用优化的整数系数找到最优的实系数:

from scipy.optimize import brute
grid = [slice(1, 10, 1)]  # grid search over 1, 2, ..., 9
# it is important to specify finish=None in below
intcoef = brute(errfun, grid, args=(xs, ys,), finish=None)
floatcoef = optfloat(intcoef, xs, ys)['floatcoef'][0]

使用这种方法我得到[5.0, -1.50577]对于最优系数，这对于整数系数是精确的，并且对于实系数足够接近。