如何計算數值數組的誤差最小化近似值

給定一組數值（整數或浮點數，或者很好）和一個正整數N，我想返回一個N值的數組，如果每個原始數組中的值被返回數組中最接近的匹配所取代，平方誤差（即（original_value - approximation）^ 2）被最小化。基本上，要找到最接近輸入數組的最小陣列。如何計算數值數組的誤差最小化近似值

對於N = 1的情況是微不足道的，用一些基本的代數可以很容易地顯示答案是值的均值。

也可以顯示，在對輸入數組進行排序後，每個「返回」值必須對應於來自輸入數組的一系列順序值，其值是其均值。因此，對於N = 2，最壞的情況下，我們可以從一個集合中以sorted_input [0]開始，另一個集合與其他所有值一起開始，然後依次將項目移動到第一個集合，返回任意組合使O（n）（忽略分揀成本）

但是，在N = 3及以上時，不清楚如何繼續。天真地嘗試所有的組合變成了O（n ^（N-1）），儘管它感覺它們應該存在，但我不能證明任何優化是「安全的」（即不會卡住某些局部最小值，非最優結果）

這很可能是問題實際上是NP-hard（我什至不知道如何驗證多項式時間的解決方案！），但感覺就像是那種問題一些數學詭計可能導致巨大的加速，所以我想我會問任何想法。請注意，我正在尋找最佳解決方案，而不僅僅是一個像樣的近似值。

來源

2016-09-20 tohoho

你看過「來回誤差補償和修正」嗎？ –

我對這個概念並不熟悉，所以我搜索了一下，我想我已經掌握了它的要點......但是，我沒有看到如何將它應用到手頭的問題上。你在想什麼樣的方法？ – tohoho

如果該操作是可逆或可實現的相反方向，則可以執行1個前向1個反向函數並取出錯誤，然後從原點前進1個步驟並減去1f1r版本的一半錯誤。 –

Cluster analysis是您的問題的一個很好的起點。短有很多算法，但他們大多是問題特定的。

來源

2016-09-20 08:43:54 Trifon

感謝您的鏈接，似乎我試圖做的實質上[k-means clustering]（https://en.wikipedia.org/wiki/K-means_clustering），正如我擔心的那樣，似乎是NP-hard在一般情況下。然而，在一維情況下，我發現[一篇聲稱能找到最佳解決方案的論文]（https://ideas.repec.org/c/boc/bocode/s456844.html）。雖然我無法訪問完整的文章，但看看源代碼表明它可能是時間和空間上的多項式。問題解決了？ – tohoho

Kyme被廣泛使用，它在許多語言中有許多實現，並且它是一個合理的解決方案。它不承諾找到最佳解決方案，它可能會收斂到當地的最低標準。我會看看你建議的文件，謝謝。 – Trifon

如何計算數值數組的誤差最小化近似值

回答

相關問題