寻找最小平方差之和的算法

Question

基本上，我正在编写的算法将列表 L 作为输入，并希望找到一个数字 x，使得 L 中的所有项 i 减去 x 的平方之和最小。寻找使 abs(L[i]-x)**2 的和最小的 x。到目前为止，我的算法正在按照预期工作，只是在浮点数的情况下不适用。我不确定如何实现浮点数。例如，[2, 2, 3, 4] 理想情况下应该产生结果 2.75，但是我的算法目前无法产生浮点整数。

 def minimize_square(L):
     sumsqdiff = 0
     sumsqdiffs = {}
     for j in range(min(L), max(L)):
             for i in range(len(L)-1):
                     sumsqdiff += abs(L[i]-j)**2
             sumsqdiffs[j]=sumsqdiff
             sumsqdiff = 0
     return min(sumsqdiffs, key=sumsqdiffs.get)

- madman2890

---

你可以使用 float(number) 将一个数字转换为浮点数。之后，任何涉及到 number 的操作都将得到浮点数结果。 - heltonbiker

你更感兴趣的是找到价值，还是将其作为编程练习来理解和改进算法？ - heltonbiker

Answer 1

很容易证明[*]，使平方差之和最小的数字是L的算术平均值。这给出了以下简单的解决方案：

In [26]: L = [2, 2, 3, 4]

In [27]: sum(L) / float(len(L))
Out[27]: 2.75

或者，使用NumPy：

In [28]: numpy.mean(L)
Out[28]: 2.75

[*] 这是证明的大纲：

我们需要找到最小化 f(x) = sum((x - L[i])**2) 的 x，其中求和是在 i=0..n-1 范围内进行的。

对 f(x) 求导并将其设为零：（参见链接）。

2*sum(x - L[i]) = 0

通过简单的代数运算，上述内容可以转化为

x = sum(L[i]) / n

这其实就是 L 的算术平均值。证毕。

- NPE

---

+1。你能添加一个简短的证明或链接吗？我非常感兴趣。谢谢！ - rubik

我不确定这是否一定正确。以下是一些随机数测试以展示：

L = [random.randrange(100) for i in range(20)] avgL = sum(L)/len(L) avgL 58 minimize_square(L) 59 L = [random.randrange(100) for i in range(20)] avgL = sum(L)/len(L) avgL 51 minimize_square(L) 49 L = [random.randrange(100) for i in range(20)] avgL = sum(L)/len(L) avgL 53 minimize_square(L) 55

- madman2890

@rubik：我已经添加了证明的大纲。 - NPE

@madman2890，你的 >>> L = [random.randrange(100) for i in range(20)] >>> avgL = sum(L)/len(L) >>> avgL 51 >>> minimize_square(L) 49 计算有缺陷，因为你没有将 len(L) 转换为浮点数。也就是说，你计算时使用了 avgL 作为平均值的整数截断，但它并不等于平均值。 - James Waldby - jwpat7

有趣的是，正是因为OLS，当我读到这个问题时，我立刻想到了平均值。 :) - NPE

Answer 2

我不确定这是最有效的方法，但你可以保持相同的算法并修改返回语句。

min_int = min(sumsqdiffs, key=sumsqdiffs.get)
return bisection(L,min_int-1,min_int+1)

其中bisection实现了以下方法：二分法

当且仅当在分析区间内存在单个函数最小值时，此方法才有效。

- igon

---

没有想到它是平方差的总和 -> 参考@NPE的答案。 - igon