首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >基于列的数组返回多数加权表决

问基于列的数组返回多数加权表决
EN

Stack Overflow用户
提问于 2020-09-11 23:23:04
回答 2查看 551关注 0票数 5

我有一个具有3 x 3维数的矩阵w和一个向量w,即3,。

代码语言:javascript
复制
x = np.array([[1, 2, 1],
              [3, 2 ,1],
              [1, 2, 2]])

w = np.array([0.3, 0.4, 0.3])

我需要生成另一个向量y,即对每一行x的多数票。x的每一列按w中相应的值加权。就像这样:

对于y[0],它应该查找X[0] => [1, 2, 1]

  • 值1=第一和第三0,2的列
  • 值2=第二个1的列
  • 值3= none的列

按X值分组的列的权重之和(以w表示):

  • 值为1:0.3 + 0.3 = 0.6的列的权重之和
  • 值为2:0.4的列的权重之和
  • 值为3:0的列的权重之和

由于值为1的列的权重之和最高,y[0] = 1。诸若此类。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2020-09-12 03:04:34

如果您了解广播业,就可以用numpy来完成它。缺点是,由于代码是向量化的,所以计算量比需要的要多。如果w向量的大小非常大,这将很重要。

也许有人想出了一个更简单的方法来写它,但这就是我如何做到这一点,而不考虑太多。

的答案首先:

代码语言:javascript
复制
i = np.arange(3) + 1
m = (x.reshape((1,4,3)) == i.reshape((3,1,1)))
np.argmax(np.sum(m, axis=2).T*w, axis=1) + 1

现在一步一步的解释.注意到通常从零开始计数更好,但是我遵循了你们的惯例。

  1. 我添加了一行,因此数组不对称(更容易检查形状) In 1: X= np.array([1,2,1,.:3,2,1,.:1,2,2,…:3,1,3]) .:W= np.array(0.3,0.4,0.3)
  2. 第一步是拥有索引数组i。你的会议一开始就开始。 In 2: i= np.arange(3) +1
  3. 技巧步骤:创建一个形状为(3,4,3)的数组,其中数组的第一个条目是(4,3)数组,包含所有条目0或1。它是1当且仅当x == i。这是通过向x和i添加维度来实现的,这样就可以广播它们。该操作基本上比较x和i的所有组合,因为x的所有维度都匹配i的size=1维度,反之亦然: In 3: M=(x.reshape( 1,4,3) == i.reshape((3,1,1))*1 In 4: M Out4: array([[1,0,1,0,0,0,1,1,0,0,0,0,1,0],[0,1,0,0,1,0,0,0],[0,0,0,1,0,0,0,0,0,1,0,1])
  4. 现在,您沿着行(即axis=2)求和,以获得每个选择在x的每一行中出现的次数(请注意,当您将其与x进行比较时,结果是转置的): In 5: np.sum(m,axis=2) Out5: Out5([ 2,1,1,1,1,1,2,0,0,0,2])
  5. 我希望你已经知道这是怎么回事了。您可以直接阅读:在x的第一行中,1出现两次,2出现一次。在x的第二行中,全部出现一次,在第三行x中,1出现一次,2出现两次,等等。
  6. 乘以权重: 在7: np.sum(m,axis=2).T*w Out7: array([0.6,0.4,0.、0.3、0.4、0.3、0.3、0.8、0。,0.3,0。,0.6])
  7. 获取行的最大值(添加一个以符合您的约定): In 8: np.argmax(np.sum(m,axis=2).T*w,axis=1) +1 Out8:数组(1,2,2,3)

特例: Tie

评论中提出了以下情况:

代码语言:javascript
复制
x = np.array([[2, 2, 4, 1]])
w = np.array([0.1, 0.2, 0.3, 0.4])

权重之和为:

代码语言:javascript
复制
[0.1, 0.4, 0., 0.4]

所以在这种情况下没有胜利者。从这个问题上还不清楚在这种情况下人们会做些什么。一个人可以拿走所有,一个也不带走..。我们可以在最后找出这些案件:

代码语言:javascript
复制
final_w = np.sum(m, axis=2).T*w
result = np.argmax(np.sum(m*w, axis=2), axis=0) + 1
special_cases = np.argwhere(np.sum(final_w == np.max(final_w), axis=1) > 1)

注意:--为了提高可读性,我使用了改型方法,但我经常使用迪姆斯或np.newaxis。就像这样:

代码语言:javascript
复制
i = np.arange(3) + 1
m = (x[np.newaxis] == i[:, np.newaxis, np.newaxis])
np.argmax(np.sum(m, axis=2).T*w, axis=1) + 1

--另一种选择:--您也可以使用某种编译代码。例如,在这种情况下,numba非常容易使用。

票数 4
EN

Stack Overflow用户

发布于 2020-09-12 05:34:48

这是一种非常疯狂的方法,它涉及排序和索引,而不是添加一个新的维度。这有点像np.unique使用的基于排序的方法。

首先,在每一行中找到排序的索引:

代码语言:javascript
复制
rows = np.repeat(np.arange(x.shape[0]), x.shape[1])  # [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3]
cols = np.argsort(x, axis=1).ravel()                 # [0, 2, 1, 2, 1, 0, 0, 1, 2, 1, 0, 2]

现在,您可以创建一个按列排序的元素数组,包括未加权元素和加权元素.前者将被用来得到求和的指数,后者实际上将被求和。

代码语言:javascript
复制
u = x[rows, cols]                            # [1, 1, 2, 1, 2, 3, 1, 2, 2, 1, 3, 3]
v = np.broadcast_to(w, x.shape)[rows, cols]  # [0.3, 0.3, 0.4, 0.3, 0.4, 0.3, 0.3, 0.4, 0.3, 0.4, 0.3, 0.3]

您可以在以下位置找到要应用np.add.reduce的断点:

代码语言:javascript
复制
row_breaks = np.diff(rows).astype(bool)            # [0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0]
col_breaks = np.diff(u).astype(bool)               # [0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0]
break_mask = row_breaks | col_breaks               # [0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0]
breaks = np.r_[0, np.flatnonzero(break_mask) + 1]  # [ 0,  2,  3,  4,  5,  6,  7,  9, 10]

现在,您可以得到每一行相同数字的权重之和:

代码语言:javascript
复制
sums = np.add.reduceat(v, breaks)  # [0.6, 0.4, 0.3, 0.4, 0.3, 0.3, 0.7, 0.4, 0.6]

但是,您需要将它们拆分为与每行唯一元素的数量相对应的段:

代码语言:javascript
复制
unique_counts = np.add.reduceat(break_mask, np.arange(0, x.size, x.shape[1]))
unique_counts[-1] += 1  # The last segment will be missing from the mask: # [2, 3, 2, 2]

unique_rows = np.repeat(np.arange(x.shape[0]), unique_counts)  # [0, 0, 1, 1, 1, 2, 2, 3, 3]

现在可以对每个段进行排序以找到最大值:

代码语言:javascript
复制
indices = np.lexsort(np.stack((sums, unique_rows), axis=0))  # [1, 0, 2, 4, 3, 5, 6, 7, 8]

每次运行结束时的索引如下:

代码语言:javascript
复制
max_inds = np.cumsum(unique_counts) - 1  # [1, 4, 6, 8]

因此,最高金额是:

代码语言:javascript
复制
sums[indices[max_inds]]  # [0.6, 0.4, 0.7, 0.6]

您可以在索引中分解索引,以便从每一行中获得正确的元素。请注意,max_inds及其所依赖的所有内容都与x.shape[1]大小相同,如预期的那样:

代码语言:javascript
复制
result = u[breaks[indices[max_ind]]]

这个方法看起来不太漂亮,但是它可能比在数组上使用额外的维度更节省空间。此外,它的工作方式与x中的数字无关。请注意,我从未以任何方式减去任何或调整的x。实际上,所有行都是独立处理的,row_breaks在构造breaks时破坏了最大元素与下一个元素的最小值的重合。

TL;博士

享受:

代码语言:javascript
复制
def weighted_vote(x, w):
    rows = np.repeat(np.arange(x.shape[0]), x.shape[1])
    cols = np.argsort(x, axis=1).ravel()
    u = x[rows, cols]
    v = np.broadcast_to(w, x.shape)[rows, cols]
    row_breaks = np.diff(rows).astype(bool)
    col_breaks = np.diff(u).astype(bool)
    break_mask = row_breaks | col_breaks
    breaks = np.r_[0, np.flatnonzero(break_mask) + 1]
    sums = np.add.reduceat(v, breaks)
    unique_counts = np.add.reduceat(break_mask, np.arange(0, x.size, x.shape[1]))
    unique_counts[-1] += 1
    unique_rows = np.repeat(np.arange(x.shape[0]), unique_counts)
    indices = np.lexsort(np.stack((sums, unique_rows), axis=0))
    max_inds = np.cumsum(unique_counts) - 1
    return u[breaks[indices[max_inds]]]

基准测试

基准以下列格式运行:

代码语言:javascript
复制
rows = ...
cols = ...
x = np.random.randint(cols, size=(rows, cols)) + 1
w = np.random.rand(cols)
%timeit weighted_vote_MP(x, w)
%timeit weighted_vote_JG(x, w)
assert (weighted_vote_MP(x, w) == weighted_vote_JG(x, w)).all()

我对weighted_vote_JG使用了以下泛化,并作了适当的更正:

代码语言:javascript
复制
def weighted_vote_JG(x, w):
    i = np.arange(w.size) + 1
    m = (x[None, ...] == i.reshape(-1, 1, 1))
    return np.argmax(np.sum(m * w, axis=2), axis=0) + 1

行: 100行,科尔斯: 10行

代码语言:javascript
复制
  MP: 440 µs ± 5.12 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
* JG: 153 µs ± 796 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

行: 1000行,科尔斯: 10行

代码语言:javascript
复制
  MP: 2.53 ms ± 43.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
* JG: 1.03 ms ± 12 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

行: 10000,科尔斯: 10

代码语言:javascript
复制
  MP: 23.5 ms ± 200 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
* JG: 16.6 ms ± 67.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

行: 100000,科尔斯: 10

代码语言:javascript
复制
  MP: 322 ms ± 3.11 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
* JG: 188 ms ± 858 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

行: 100,科尔斯: 100

代码语言:javascript
复制
* MP: 3.31 ms ± 257 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
  JG: 12.6 ms ± 244 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

行: 1000,科尔斯: 100

代码语言:javascript
复制
* MP: 31 ms ± 159 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
  JG: 134 ms ± 581 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

行: 10000,科尔斯: 100

代码语言:javascript
复制
* MP: 417 ms ± 7.06 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  JG: 1.42 s ± 126 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

行: 100000,科尔斯: 100

代码语言:javascript
复制
* MP: 4.94 s ± 25.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
  JG: MemoryError: Unable to allocate 7.45 GiB for an array with shape (100, 100000, 100) and data type float64

故事的寓意:对于少量的列和权重,扩展的解决方案更快。对于更多的列,请使用“我的版本”。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/63855417

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档