algorithm - 如何计算数值数组的误差最小化近似值

Question

给定一个数值数组(整数或 float ，两者都可以)和一个正整数 N，我想返回一个包含 N 个值的数组，这样，如果原始数组中的每个值都被其最接近的匹配替换为返回的数组，平方误差(即(原始值 - 近似值)^ 2)被最小化。基本上，找到最接近输入数组的较小数组。

N = 1 的情况很简单，用一些基本的代数可以很容易地证明答案是这些值的平均值。

还可以表明，在对输入数组进行排序后，每个“返回”值必须对应于输入数组中的一组顺序值，其值是它们的平均值。所以对于 N = 2，在最坏的情况下，我们可以只从一个带有 sorted_input[0] 的集合开始，另一个带有所有其他值的集合，然后一个接一个地依次将项目移动到第一组，返回任何组合以最小化 O(n) 中的错误(忽略排序成本)

但是，在 N = 3 及以上时，尚不清楚如何进行。天真地尝试所有组合变成了 O(n^(N-1))，虽然感觉它们应该存在，但我无法证明任何优化都是“安全的”(即不会陷入某个局部最小值非最佳结果)

很可能这个问题实际上是 NP 难的(我什至不知道如何在多项式时间内验证一个解决方案!)，但它感觉像是那种需要一些数学技巧的问题可以导致巨大的加速，所以我想我会询问任何想法。请注意，我正在寻找最佳解决方案，而不仅仅是一个合适的近似值。

Answer 1

Cluster analysis是你的问题的一个很好的起点。简而言之，有很多算法，但它们大多是针对特定问题的。