2

x の金額を k の希望する金額に割り当てる必要があるとします。実際に割り当てられた k 個の値と k 個の必要な量の間の二乗距離を最小化するアルゴリズムはありますか?

たとえば、x=5 から k=3 までの 2、-3、4 の必要な量を割り当てる必要があるとします。

5 を 2,-3,6 に割り当てると、0^2 + 0^2 + 2^2 = 4 の二乗距離が生成されます。

負の金額または任意の金額を k の金額に割り当てることができます。唯一の制限は、割り当てられた金額の合計が元の x でなければならないことです。また、割り当て量は整数である必要はなく、実数のみです。

4

4 に答える 4

0

基本的に、データのベクトル v (長さ k) と総予算 b の場合、次の最適化問題があります。

min_{x1, x2, ..., xk} (x1-v1)^2 + (x2-v2)^2 + ... + (xk-vk)^2
s.t. x1 + x2 + ... + xk = b

これは、二次計画法ソフトウェア パッケージを使用して解くことができる線形制約付き二次計画です。たとえばquadprog、R 言語のパッケージを使用したソリューションは次のとおりです。

# Setup data
v <- c(2, -3, 4)
b <- 5

# Solve quadratic program
library(quadprog)
solve.QP(diag(length(v)), v, matrix(rep(1, length(v))), b, 1)$solution
# [1]  2.666667 -2.333333  4.666667

この例では、元の投稿で提供された割り当ての目標値 4 よりも小さい目標値 4/3 を取得します。

于 2015-08-03T00:45:48.030 に答える
0

これは特別なケースのLPです。delta-k 値がすべて同じになるように割り当てることで、常に最小値が達成されます。

目的関数は二乗和であり、すべてのデータ ポイントが均等に重み付けされるため、同じ値のデルタ ks 以外を割り当てると、二乗和が大きくなります。(josilber の quadprog ソリューションでは、delta-k 値はすべて 2/3 であることに注意してください。偏導関数の土地のどこかに、私が疲れすぎているか頭が悪くてうまくいかないという証拠が隠されています。)

于 2015-08-03T01:23:15.907 に答える