8

各サンプルがこれに似た構造を持つデータセットがあります

X=[ [[],[],[],[]], [[],[]] , [[],[],[]] ,[[][]]]

例えば:

X=np.array([ [ [1,2,3], [2,4,5] ,[2,3,4] ] , [ [5,6], [6,6] ] , [[2,3,1],[2,3,10],[23,1,2],[1,4,5]]  ] ,"object")

Y=np.array([ [ [12,14,15] ,[12,13,14] ] , [ [15,16], [16,16] ] , [[22,23,21],[32,33,11],[12,44,55]]  ] ,"object")

したがって、すべてのサンプルについて、x のすべての要素と同じインデックスの y の対応する要素との間の内積を計算し、結果を合計する必要があります。すなわち:

result=0

for i in range(3):
    for n,m in itertools.product(X[i],Y[i]):
        print "%s, %s" % (n,m)
        result+=np.dot(n,m)

   .....:         
[1, 2, 3], [12, 14, 15]
[1, 2, 3], [12, 13, 14]
[2, 4, 5], [12, 14, 15]
[2, 4, 5], [12, 13, 14]
[2, 3, 4], [12, 14, 15]
[2, 3, 4], [12, 13, 14]
[5, 6], [15, 16]
[5, 6], [16, 16]
[6, 6], [15, 16]
[6, 6], [16, 16]
[2, 3, 1], [22, 23, 21]
[2, 3, 1], [32, 33, 11]
[2, 3, 1], [12, 44, 55]
[2, 3, 10], [22, 23, 21]
[2, 3, 10], [32, 33, 11]
[2, 3, 10], [12, 44, 55]
[23, 1, 2], [22, 23, 21]
[23, 1, 2], [32, 33, 11]
[23, 1, 2], [12, 44, 55]
[1, 4, 5], [22, 23, 21]
[1, 4, 5], [32, 33, 11]
[1, 4, 5], [12, 44, 55] 

これは私のコード全体です:

 print "***build kernel***"
        K = np.zeros((n_samples, n_samples))
        for i in range(n_samples):
            for j in range(n_samples):

                K[i,j] = self.kernel(X[i], X[j])

def kernel(x1,x2):
    N=8 #number of objects
    result=0 
    for i in xrange(N):
        for n,m in itertools.product(x1[i],x2[i]):
            result+=np.dot(n,m)
    return result    

ご覧のとおり、このアルゴリズムの複雑さは高すぎます。また、私のサンプルはこれよりもはるかに大きくなっています。そのため、400 個のサンプルを含む小さなデータ セットであっても、結果が得られるまで 4 時間待たなければなりません。このアルゴリズムを実装するより良い方法を探しています。PS: マルチスレッドまたはマルチプロセッシングについて考えていましたが、それが役立つかどうかわかりません?!

提案をいただければ幸いです。

4

3 に答える 3

14

操作が必要な各ペアの内積を合計する代わりにn * m、各リスト内のすべてのベクトルを合計して、操作のみを行う最終的な内積を実行できn + mます。

前:

def calc_slow(L1, L2):
    result = 0
    for n, m in itertools.product(L1, L2):
        result += np.dot(n, m)
    return result

後:

def calc_fast(L1, L2):
    L1_sums = np.zeros(len(L1[0]))
    L2_sums = np.zeros(len(L2[0]))
    for vec in L1:
        L1_sums += vec
    for vec in L2:
        L2_sums += vec
    return np.dot(L1_sums, L2_sums)

編集:numpyを利用したさらに高速なバージョン:

def calc_superfast(L1, L2):
    return np.dot(np.array(L1).sum(0),
                  np.array(L2).sum(0))

出力は同じです。

print X[0], Y[0], calc_slow(X[0], Y[0])
print X[0], Y[0], calc_fast(X[0], Y[0])

プリント:

[[1, 2, 3], [2, 4, 5], [2, 3, 4]] [[12, 14, 15], [12, 13, 14]] 711
[[1, 2, 3], [2, 4, 5], [2, 3, 4]] [[12, 14, 15], [12, 13, 14]] 711.0

タイミングは、大幅な改善があることを示しています。タイミングコード:

import random
import time
def rand_vector(size=3):
    return [random.randint(1, 100) for _ in xrange(3)]
def rand_list(length=200):
    return [rand_vector() for _ in xrange(length)]

print "Generating lists..."
L1 = rand_list(200)
L2 = rand_list(200)

print "Running slow..."
s = time.time()
print calc_slow(L1, L2)
print "Slow for (%d, %d) took %.2fs" % (len(L1), len(L2), time.time() - s)

print "Running fast..."
s = time.time()
print calc_fast(L1, L2)
print "Fast for (%d, %d) took %.2fs" % (len(L1), len(L2), time.time() - s)

サンプル出力:

Generating lists...
Running slow...
75715569
Slow for (100, 100) took 1.48s
Running fast...
75715569.0
Fast for (100, 100) took 0.03s

Generating lists...
Running slow...
309169971
Slow for (200, 200) took 5.29s
Running fast...
309169971.0
Fast for (200, 200) took 0.04s

Running fast...
3.05185703539e+12
Fast for (20000, 20000) took 1.94s

20000 要素の 2 つのリストの操作は、それぞれわずか 2 秒しかかかりませんでしたが、古い方法では数時間かかると予想されます。


これが機能する理由は、操作をグループ化できるからです。次のリストがあると仮定します。

L1 = [a, b, c], [d, e, f], [g, h, i] 
L2 = [u, v, w], [x, y, z]

次に、各ペアの内積を合計すると、次のようになります。

a*u + b*v + c*w + a*x + b*y + c*z +
d*u + e*v + f*w + d*x + e*y + f*z +
g*u + h*v + i*w + g*x + h*y + i*z

uvwxy、およびz要素を除外できます。

u*(a + d + g) + v*(b + e + h) + w*(c + f + i) +
x*(a + d + g) + y*(b + e + h) + z*(c + f + i)

次に、これらの合計をさらに因数分解できます。

(u + x)*(a + d + g) + (v + y)*(b + e + h) + (w + z)*(c + f + i)

これは、各初期リストから合計されたベクトルの内積です。

于 2013-03-18T15:07:45.517 に答える
3

itertools.product内部行列で内積を直接実行することで、 の必要性を回避することもできます。

def calc_matrix(l1, l2):
    return np.array(l1).dot(np.array(l2).T).sum()

def kernel(x1, x2):
    return sum(
       calc_matrix(l1, l2)
       for l1, l2 in zip(x1, x2)
    )

編集:

短いリスト (要素数が数千未満) では、これは Claudiu の (素晴らしい) 回答よりも高速になります。彼は、これらの数値を超えるとより適切にスケーリングします。

Claudiu のベンチマークの使用:

# len(l1) == 500

In [9]: %timeit calc_matrix(l1, l2)
10 loops, best of 3: 8.11 ms per loop

In [10]: %timeit calc_fast(l1, l2)
10 loops, best of 3: 14.2 ms per loop

# len(l2) == 5000

In [19]: %timeit calc_matrix(l1, l2)
10 loops, best of 3: 61.2 ms per loop

In [20]: %timeit calc_fast(l1, l2)
10 loops, best of 3: 56.7 ms per loop
于 2013-03-18T15:09:27.927 に答える
-1

ここでできることは何もありません。すべての乗算の結果を取得したい場合は、それらを実行する必要があります。それがアルゴリズムの動作です。できる唯一のことの 1 つは、結果をハッシュテーブルに保存することです。これは、重複した結果が多数あることがわかっている場合に備えて、そうしないと大量のメモリを消費することになります。ところで、マルチスレッド化によってプログラムの実行速度が向上する可能性がありますが、必要な操作の数である複雑さは決して改善されません。

于 2013-03-18T15:00:03.417 に答える