numpy排序并删除最高值

ian_chan

我不知道该算法是否有名称,但是基本上对于给定的名称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_1n_2n_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 - x0.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 * x0.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 * x0.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 * x0.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 * x1.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 * x1.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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章