我不知道该算法是否有名称,但是基本上对于给定的名称y
,我想找到这样的最大值x
:
import numpy as np
np_array = np.random.rand(1000, 1)
np.sum(np_array[np_array > x] - x) >= y
当然,搜索算法将是找到最高值n_1
,然后将其减小为第二大值n_2
。如果停止n_1 - n-2 > y
; 其他同时减少n_1
和n_2
到n_3
,如果停(n_1 - n_3) + (n_2 - n_3) > y
...
但是我觉得必须有一种算法来生成x
收敛到其真实值的{ s}序列。
让我们使用来自注释的示例:
a = np.array([0.1, 0.3, 0.2, 0.6, 0.1, 0.4, 0.5, 0.2])
y = 0.5
首先,让我们按降序对数据进行排序:
s = np.sort(a)[::-1] # 0.6, 0.5, 0.4, 0.3, 0.2, 0.2, 0.1,
让我们看一下如何选择x
影响总和的可能值r = np.sum(np_array[np_array > x] - x)
:
x ≥ 0.6
,则r = 0.0 - x
⇒-∞ < r ≤ -0.6
0.6 > x ≥ 0.5
,则r = 0.6 - x
⇒ 0.0 < r ≤ 0.1
(其中0.1 = 0.6 - 0.5 × 1
)0.5 > x ≥ 0.4
,则r = 0.6 - x + 0.5 - x = 1.1 - 2 * x
⇒ 0.1 < r ≤ 0.3
(其中0.3 = 1.1 - 0.4 × 2
)0.4 > x ≥ 0.3
,则r = 0.6 - x + 0.5 - x + 0.4 - x = 1.5 - 3 * x
⇒ 0.3 < r ≤ 0.6
(其中0.6 = 1.5 - 0.3 × 3
)0.3 > x ≥ 0.2
,则r = 0.6 - x + 0.5 - x + 0.4 - x + 0.3 - x = 1.8 - 4 * x
⇒ 0.6 < r ≤ 1.0
(其中1.0 = 1.8 - 0.2 × 4
)0.2 > x ≥ 0.1
,则r = 0.6 - x + 0.5 - x + 0.4 - x + 0.3 - x + 0.2 - x + 0.2 - x = 2.2 - 6 * x
⇒ 1.0 < r ≤ 1.6
(其中1.6 = 2.2 - 0.1 × 6
)0.1 > x
,则r = 0.6 - x + 0.5 - x + 0.4 - x + 0.3 - x + 0.2 - x + 0.2 - x + 0.1 - x + 0.1 - x = 2.4 - 8 * x
⇒1.6 < r ≤ ∞
r
除部分外,的范围是连续的a[0] < r ≤ 0.0
。重复的元素会影响中的r
每个值的可用值范围a
,但除此之外没有什么特别的。我们可以删除,但也可以使用np.unique
代替np.sort
:
s, t = np.unique(a, return_counts=True)
s, t = s[::-1], t[::-1]
w = np.cumsum(t)
如果您的数据可以合理地预期不包含重复,然后使用排序s
在一开始显示,并集t = np.ones(s.size, dtype=int)
,因此w = np.arange(s.size) + 1
。
对于s[i] > x ≥ s[i + 1]
,的界限由r
给出c[i] - w[i] * s[i] < r ≤ c[i] - w[i] * s[i + 1]
,其中
c = np.cumsum(s * t) # You can use just `np.cumsum(s)` if no duplicates
因此,找到y
最终结果是将其放置在正确边界之间的问题。这可以通过二进制搜索来完成,例如np.searchsorted
:
# Left bound. Sum is strictly greater than this
bounds = c - w * s
i = np.searchsorted(bounds[1:], y, 'right')
的第一个元素bounds
始终是0.0
,结果索引i
将指向上限。通过截断第一个元素,我们将结果移至下限,而忽略零。
通过解决x
选定箱中的位置来找到解决方案:
y = c[i] - w[i] * x
所以你有了:
x = (c[i] - y) / w[i]
您可以编写一个函数:
def dm(a, y, duplicates=False):
if duplicates:
s, t = np.unique(a, return_counts=True)
s, t = s[::-1], t[::-1]
w = np.cumsum(t)
c = np.cumsum(s * t)
i = np.searchsorted((c - w * s)[1:], y, 'right')
x = (c[i] - y) / w[i]
else:
s = np.sort(a)[::-1]
c = np.cumsum(s)
i = np.searchsorted((c - s)[1:], y, 'right')
x = (c[i] - y) / (i + 1)
return x
这不能处理where的情况y < 0
,但是y
由于searchsorted
可以很好地向量化,因此它允许您同时输入许多值。
这是用法示例:
>>> dm(a, 0.5, True)
Out[247]: 0.3333333333333333
>>> dm(a, 0.6, True)
0.3
>>> dm(a, [0.1, 0.2, 0.3, 0.4, 0.5], True)
array([0.5 , 0.45 , 0.4 , 0.36666667, 0.33333333])
至于这个算法是否有名字:我什么都不知道。自从我写这篇文章以来,我觉得“离散的疯狂”是个恰当的名字。也很好地滑开了舌头:“哦,是的,我使用离散疯狂来计算阈值”。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句