将浮点数列表匹配到最接近的整数而不重复

Question

我有一个我正在尝试实现的算法，但我正在努力寻找一种好的方法来实现它。目标是获取浮点数列表，并与整数列表进行一对一映射，这样就没有两个浮点数被映射到同一个整数，并且映射具有最小的可能误差（无论是在总误差或均方误差）。

所以，例如，假设我有数字 [2.1, 2.3, 2.4, 7, 7.5, 8.9, 9.3]。我希望它 return 类似于：

{
    2.1: 1,
    2.3: 2, 
    2.4: 3,
    7: 7,
    7.5: 8,
    8.9: 9,
    9.3: 10
}

请注意，聚集在 2 周围的数字必须分散到 1、2 和 3。

提一下我的动机是一个实用的音乐动机可能会有所帮助：将一系列微调音高（音符 "in between the cracks"）映射到钢琴的琴键。所以 "good enough" 问题的解决方案真的是我所需要的，尽管真正最优的解决方案会更令人兴奋！

此外，我在 Python 工作，但当然这里真正的问题不是特定于语言的。

Answer 1

也许不是最优雅和最高效的代码，但是：

它是多项式复杂度
它提供了全局最优

基本思路：

计算一些最坏情况的候选范围（我们不能忘记任何可能改进的候选）
- 虽然我没有投入太多 -> "hack"
计算距离矩阵
求解矩形linear-assignment problem

代码：

import math
import numpy as np
from scipy.optimize import linear_sum_assignment
from scipy.spatial.distance import cdist

SQUARED_PENALTY = True

data = np.array([2.1, 2.3, 2.4, 7, 7.5, 8.9, 9.3])

# hacky safety-net -> which candidates to look at
min_ = math.floor(data.min())
max_ = math.ceil(data.max())
gap = max_ - min_

cands = np.arange(min_ - gap, max_ + gap)

cost_matrix = cdist(data[:, np.newaxis], cands[:, np.newaxis])

if SQUARED_PENALTY:
  cost_matrix = np.square(cost_matrix)

row_ind, col_ind = linear_sum_assignment(cost_matrix)

solution = cands[col_ind]

print(solution)
print('cost: ', np.round(cost_matrix[row_ind, col_ind].sum(), 3))

输出：l1-costs

[ 2  1  3  7  8  9 10]
cost:  3.3

输出：平方成本

[ 1  2  3  7  8  9 10]
cost:  2.41

Answer 2

你可以尝试这样的事情。这个想法是执行整数列表的所有排列，并通过蛮力计算针对您的实值向量的距离度量。

在您的示例中，我们只对每个排列的前 7 个值感兴趣，因为您的浮点数列表有 7 个值。我选择的整数列表有 10 个值，因此在这种情况下，您会意识到前 7 个值将重复 6 个连续样本，因此您可以通过每 6 个样本采样来减少迭代次数。对于这种强力解决方案，重要的是通过消除冗余信息、最小化计算（快速度量）、使用巧妙的测试方法等来减少迭代次数。为了在此处显示，我只是为指标添加了一个阈值，因此我得到了一个结果。但这可以在很大程度上得到改善。

如果您有更大的列表，并且如果您允许 "semi integers" 像 1.5 2.5，问题将变得更具挑战性。我这样说是因为下面代码的最佳结果是您选择的开始:) 对于任何两个列表和指标也很重要，如果你得到不止一个同样最优的解决方案也就不足为奇了。例如，[1,2,3,7,8,9,10] 的 L1 范数与 [2,1,3,7,8,9,10] 相同。这意味着什么取决于您的问题。

import itertools
import numpy as np

y=[2.1,2.3,2.4,7,7.5,8.9,9.3]
y_hat=[1,2,3,4,5,6,7,8,9,10]

py_hat=itertools.permutations(y_hat)
py_hat=list(py_hat)

list_p=[]
for p in py_hat[::6]:
    p=p[0:7]
    f= np.sum((np.array(y)-np.array(p))**2)
    if f < 2.5:
        list_p.append([p,f])

print(list_p)

[[(1, 2, 3, 7, 8, 9, 10), 2.41]]

将浮点数列表匹配到最接近的整数而不重复

Match list of floats to nearest integers without repeating

python

mapping

algorithm

rounding

mathematical-optimization