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 的相应元素之间的点积，并将结果求和。IE：

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 秒，而我预测使用旧方法需要几个小时。

这样做的原因是您可以将操作分组在一起。假设您有以下列表：

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

您可以分解出u, v, w, x, y, 和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 的基准测试：

# 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

你在这里无能为力。你想得到所有乘法的结果，你只需要做它们，这就是你的算法所做的。您可以做的唯一一件事就是将结果存储在哈希表中，以防您知道有很多重复的结果，但如果不这样做会消耗大量内存。顺便说一句，多线程可能会使您的程序运行得更快，但它永远不会提高它的复杂性，即所需的操作数量。

于 2013-03-18T15:00:03.417 回答