2D Numpy配列で最初の要素が重複している行の平均 – 2Dなnumpy.ndarrayの最初の要素(1列目)で各行をグルーピングして集計(平均を算出)

2D Numpy配列で最初の要素が重複している行の平均 – 2Dなnumpy.ndarrayの最初の要素(1列目)で各行をグルーピングして集計(平均を算出)

Average rows with duplicate first element in 2D numpy array – StackOverflow

データの構造化なので,Pandasを用いれば簡単な話.
(実用上もPandasを用いるのがリーズナブル;後述)

import numpy as np
import pandas as pd


a = np.array(
    [
        [1, 2, 3, 4],
        [2, 2, 3, 4],
        [1, 4, 5, 6],
        [3, 2, 3, 4]
    ]
)
print(a)

df = pd.DataFrame(a)
res = df.groupby(0, as_index=False).mean().values
print(res)
%timeit df = pd.DataFrame(a);res = df.groupby(0, as_index=False).mean().values
[[1 2 3 4]
 [2 2 3 4]
 [1 4 5 6]
 [3 2 3 4]]
[[1 3 4 5]
 [2 2 3 4]
 [3 2 3 4]]
100 loops, best of 3: 2.11 ms per loop

これを,Numpyでどうやるか考える.
まあ,先に答え合わせをしておけば,回答がリーズナブルで,

def groupby_mean(a):
    # Sort array by groupby column
    b = a[a[:,0].argsort()]

    # Get interval indices for the sorted groupby col
    idx = np.flatnonzero(np.r_[True,b[:-1,0]!=b[1:,0],True])

    # Get counts of each group and sum rows based on the groupings & hence averages
    counts = np.diff(idx)
    avg = np.add.reduceat(b[:,1:],idx[:-1],axis=0)/counts.astype(float)[:,None]

    # Finally concatenate for the output in desired format
    return np.c_[b[idx[:-1],0],avg]


def groupby_mean_matmul(a):
    unq = np.unique(a[:,0])
    m = a[:,0,None] == unq
    return np.c_[unq, m.T.dot(a[:,1:])/m.sum(0)[:,None].astype(float)]


print(groupby_mean(a))
%timeit groupby_mean(a)

print(groupby_mean_matmul(a))
%timeit groupby_mean_matmul(a)

a = np.concatenate([a]*1000000)
%timeit df = pd.DataFrame(a);res = df.groupby(0, as_index=False).mean().values
%timeit groupby_mean_matmul(a)
%timeit groupby_mean(a)
[[1. 3. 4. 5.]
 [2. 2. 3. 4.]
 [3. 2. 3. 4.]]
10000 loops, best of 3: 68 µs per loop

[[1. 3. 4. 5.]
 [2. 2. 3. 4.]
 [3. 2. 3. 4.]]
10000 loops, best of 3: 49.5 µs per loop

10 loops, best of 3: 170 ms per loop
1 loop, best of 3: 413 ms per loop
1 loop, best of 3: 372 ms per loop

凄いの一言なんだけど,理解を深めるため,自分であれこれ考えてみる.

ちなみに,データサイズについて,小規模(-1万)だとNumpyの方が速いが,
中規模以上(10万-)ではPandasの方が速いので,
実用的にはPandasがリーズナブルチョイス.
Numpyソリューションはどちらもブロードキャストを用いているので,
小規模だと速いがデータサイズに対して時空間効率が指数的に悪化していくので,
中規模以上になるとあまり使い物にならないのは容易に想像できる.
(まあ,かと言って,だからこれよりも良い方法が思い付く訳ではない..残念)
ブロードキャストは便利なのでついつい使ってしまうが,
バイナリサーチに置き換えられる事も多いので,気を付けないといけない(自戒).

 

まあ,言っている先から,ブロードキャストしまくり.

 

def groupby_mean02(a):
    u = np.unique(a[:, 0])
    cond = np.searchsorted(u, a[:, 0])
    sidx = cond.argsort()
    _, idx, cnt = np.unique(cond[sidx], return_index=True, return_counts=True)
    return np.add.reduceat(a[sidx], idx) / cnt[:, None]


a = np.array(
    [
        [1, 2, 3, 4],
        [2, 2, 3, 4],
        [1, 4, 5, 6],
        [3, 2, 3, 4]
    ]
)
print(groupby_mean02(a))

%timeit groupby_mean_matmul(a)
%timeit groupby_mean(a)
%timeit groupby_mean02(a)

a = np.concatenate([a]*1000000)
%timeit groupby_mean_matmul(a)
%timeit groupby_mean(a)
%timeit groupby_mean02(a)
[[1. 3. 4. 5.]
 [2. 2. 3. 4.]
 [3. 2. 3. 4.]]

10000 loops, best of 3: 49.5 µs per loop
10000 loops, best of 3: 68.2 µs per loop
10000 loops, best of 3: 36.8 µs per loop

1 loop, best of 3: 439 ms per loop
1 loop, best of 3: 369 ms per loop
1 loop, best of 3: 744 ms per loop

numpy.uniqueは高機能過ぎて遅い.
データサイズが大きくなると,それが顕著.

def groupby_mean03(a):
    sidx = a[:, 0].argsort()
    b = a[sidx]
    c = b[:, 0]
    cond = np.searchsorted(np.arange(c.min(), c.max()), c)
    cnt = np.bincount(cond)
    idx = np.concatenate(([0], cnt.cumsum()[:-1]))
    return np.add.reduceat(b, idx) / cnt[:, None]


a = np.array(
    [
        [1, 2, 3, 4],
        [2, 2, 3, 4],
        [1, 4, 5, 6],
        [3, 2, 3, 4]
    ]
)
print(groupby_mean03(a))
%timeit groupby_mean(a)
%timeit groupby_mean_matmul(a)
%timeit groupby_mean03(a)

a = np.concatenate([a]*1000000)
%timeit groupby_mean(a)
%timeit groupby_mean_matmul(a)
%timeit groupby_mean03(a)
[[1. 3. 4. 5.]
 [2. 2. 3. 4.]
 [3. 2. 3. 4.]]
10000 loops, best of 3: 70.8 µs per loop
10000 loops, best of 3: 49 µs per loop
10000 loops, best of 3: 20.4 µs per loop
1 loop, best of 3: 370 ms per loop
1 loop, best of 3: 412 ms per loop
1 loop, best of 3: 436 ms per loop
!pip install -q line_profiler
%load_ext line_profiler
%lprun -f groupby_mean03 groupby_mean03(a)
Timer unit: 1e-06 s

Total time: 0.450397 s
File: 
Function: groupby_mean03 at line 1

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     1                                           def groupby_mean03(a):
     2         1     140880.0 140880.0     31.3      sidx = a[:, 0].argsort()
     3         1     182710.0 182710.0     40.6      b = a[sidx]
     4         1          8.0      8.0      0.0      c = b[:, 0]
     5         1      57306.0  57306.0     12.7      cond = np.searchsorted(np.arange(c.min(), c.max()), c)
     6         1      16703.0  16703.0      3.7      cnt = np.bincount(cond)
     7         1         58.0     58.0      0.0      idx = np.concatenate(([0], cnt.cumsum()[:-1]))
     8         1      52732.0  52732.0     11.7      return np.add.reduceat(b, idx) / cnt[:, None]

ソートがボトルネックになっている(多分,PandasとNumpyの差はそこ).
合理的には,forループに置き換えて,JITコンパイルするのが良いんだろうけど,
もうちょっとテクニカルに考える(遊ぶ)事はできないか.

とりあえず,ソートを無くしてみる.

def groupby_mean04(a):
    c = a[:, 0]
    b = int(10**np.ceil(np.log10(a.shape[1])))
    wmat = c[:, None] * b + np.arange(a.shape[1])
    val = np.bincount(wmat.ravel(), a.ravel())
    cnt = np.bincount(c)
    return val[val!=0].reshape(-1, 4) / cnt[1:, None]


a = np.array(
    [
        [1, 2, 3, 4],
        [2, 2, 3, 4],
        [1, 4, 5, 6],
        [3, 2, 3, 4]
    ]
)
print(groupby_mean04(a))
%timeit groupby_mean(a)
%timeit groupby_mean_matmul(a)
%timeit groupby_mean03(a)
%timeit groupby_mean04(a)

a = np.concatenate([a]*1000000)
%timeit groupby_mean(a)
%timeit groupby_mean_matmul(a)
%timeit groupby_mean03(a)
%timeit groupby_mean04(a)
[[1. 3. 4. 5.]
 [2. 2. 3. 4.]
 [3. 2. 3. 4.]]
10000 loops, best of 3: 70.1 µs per loop
10000 loops, best of 3: 49.8 µs per loop
10000 loops, best of 3: 20.7 µs per loop
100000 loops, best of 3: 15.4 µs per loop
1 loop, best of 3: 374 ms per loop
1 loop, best of 3: 421 ms per loop
1 loop, best of 3: 451 ms per loop
1 loop, best of 3: 230 ms per loop
%lprun -f groupby_mean04 groupby_mean04(a)
Timer unit: 1e-06 s

Total time: 0.232817 s
File: 
Function: groupby_mean04 at line 4

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
     4                                           def groupby_mean04(a):
     5         1          9.0      9.0      0.0      c = a[:, 0]
     6         1         42.0     42.0      0.0      b = int(10**np.ceil(np.log10(a.shape[1])))
     7         1      89585.0  89585.0     38.5      wmat = c[:, None] * b + np.arange(a.shape[1])
     8         1     109026.0 109026.0     46.8      val = np.bincount(wmat.ravel(), a.ravel())
     9         1      34097.0  34097.0     14.6      cnt = np.bincount(c)
    10         1         58.0     58.0      0.0      return val[val!=0].reshape(-1, 4) / cnt[1:, None]

重み付けがいい加減なので,そのへんをうまいことしたい.
bincountを2回呼び出している辺りは無駄感あるけど,多分これが最善じゃないかなと.
もう少し最適化できそうだけど,小一時間考えて飽きてきたのでこの辺にしておく.

 
 

ブログ内検索用キーワード:
ちょっと後で自分が調べるとき用に冗長な文章.
任意の列要素に基づいてグルーピングして合計したい場合,
ビニングしてそれに基づいて合計したい場合,
numpy.bincountがリーズナブルチョイス.
平均を求める場合は,それを更にnumpy.bincountで求めた数で割れば良い.
numpy.bincountは1Dアレイしか処理できないので,
2D以上を処理する場合は,ウェイト行列を作ってnumpy.ndarray.ravelして
1Dで処理した後,reshapeして元の2Dの形に戻す.
本エントリの様に,ソートをすれば処理が楽だけど,
ソートはするというのはやっぱりn数が多くなると遅さが目立つので,
numpy.bincountをうまく活用してやれば2倍近い効率で処理が可能になる.
まあ,pandasを使えばもっと簡単にかつ効率的に処理ができる訳だけど.

関連:
別の配列に基づいて配列値をグルーピングして合計

一貫性のある最大領域(最大ブロブ)を取得

アレイの任意の列を減算

Counting Sort(Python/Numpy)

広告
カテゴリー: 未分類 パーマリンク

2D Numpy配列で最初の要素が重複している行の平均 – 2Dなnumpy.ndarrayの最初の要素(1列目)で各行をグルーピングして集計(平均を算出) への7件のフィードバック

  1. ピンバック: 1-dimのビット配列から、特定の2-dimの1のシーケンスの配列を取得する[Python] – 0/1の1次元配列から1をグルーピングして各グループごとに行方向へ展開し2次元配列を作成 | 粉末@それは風

  2. ピンバック: 1-dimのビット配列から、特定の2-dimの1のシーケンスの配列を取得する[Python] – 0/1の1次元配列から1をグルーピングして各グループごとに行方向へ展開し2次元配列を作成 | 粉末@それは風

  3. ピンバック: pandas.DataFrame.applyは(時空間効率の観点からは)使用するべきではない – 使用すべき明確な理由がない限りpandas.DataFrame.applyはリーズナブルチョイスになり得ない | 粉末@それは風のように

  4. ピンバック: pandas.DataFrame.applyは(時空間効率の観点からは)使用するべきではない – 使用すべき明確な理由がない限りpandas.DataFrame.applyはリーズナブルチョイスになり得ない | 粉末@それは風のように

  5. ピンバック: データフレーム各行の連続したゼロをカウント | 粉末@それは風のように (日記)

  6. ピンバック: pandasデータフレーム列内のNaNに基づいて累積和をリセット – 任意の条件に基づいた範囲で累積和を求める | 粉末@それは風のように (日記)

  7. ピンバック: データフレーム列内の連続した値の和(任意長の範囲で合計) | 粉末@それは風のように (日記)

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください