Эффективная гистограмма различий для разреженных данных - PullRequest
Новая
       18

Эффективная гистограмма различий для разреженных данных

0 голосов
/ 29 октября 2018

Я хочу вычислить гистограмму различий между всеми элементами в одном массиве A со всеми элементами в другом массиве B.

Итак, я хочу получить гистограмму следующих данных: 

Delta1 = A1-B1
Delta2 = A1-B2
Delta3 = A1-B3
...
DeltaN = A2-B1
DeltaN+1 = A2-B2
DeltaN+2 = A2-B3 
...

Цель этого расчета - показать, что эти данные имеют корреляцию, хотя не у каждой точки данных есть «партнер» в другом массиве, и на практике корреляция довольно шумная.

Проблема в том, что на практике эти файлы очень большие, несколько ГБ, и все записи векторов представляют собой 64-битные целые числа с очень большими различиями. Мне кажется невозможным преобразовать эти данные в двоичные массивы, чтобы иметь возможность использовать корреляционные функции и преобразования Фурье для вычисления этого.

Вот небольшой пример, чтобы лучше понять, на что я смотрю. Эта реализация с поиском Numpy в цикле for довольно медленная. 

import numpy as np
import matplotlib.pyplot as plt

timetagsA = [668656283,974986989,1294941174,1364697327,\
1478796061,1525549542,1715828978,2080480431,2175456303,2921498771,3671218524,\
4186901001,4444689281,5087334517,5467644990,5836391057,6249837363,6368090967,8344821453,\
8933832044,9731229532]


timetagsB = [13455,1294941188,1715828990,2921498781,5087334530,5087334733,6368090978,9731229545,9731229800,9731249954]

max_delta_t = 500
nbins = 10000 
histo=np.zeros((nbins,2), dtype = float) 
histo[:,0]=np.arange(0,nbins)   

for i in range(0,int(len(timetagsA))):
    delta_t = 0
    j = np.searchsorted(timetagsB,timetagsA[i]) 
    while (np.round(delta_t) < max_delta_t and j<len(timetagsB)):
        delta_t = timetagsB[j] - timetagsA[i] 

        if(delta_t<max_delta_t):
            histo[int(delta_t),1]+=1 

        j = j+1

plt.plot(histo[0:50,1])
plt.show()

Было бы здорово, если бы кто-нибудь мог помочь мне найти более быстрый способ вычисления этого. Заранее спасибо!

1 Ответ

0 голосов
/ 29 октября 2018

EDIT

Приведенное ниже решение предполагает, что ваши данные настолько велики, что вы не можете использовать np.substract с np.outer, а затем нарезаете значение, которое хотите сохранить: 

arr_diff = np.subtract.outer(arrB, arrA)
print (arr_diff[(0<arr_diff ) &(arr_diff <max_delta_t)])
# array([ 14,  12,  10,  13, 216,  11,  13, 268], dtype=int64)

с данными вашего примера это работает, но не с слишком большим набором данных

ОРИГИНАЛЬНОЕ РЕШЕНИЕ

Давайте сначала предположим, что ваш max_delta_t меньше разницы между двумя последовательными значениями в timetagsB для простого способа сделать это (тогда мы можем попытаться обобщить его). 

#create the array instead of list
arrA = np.array(timetagsA)
arrB = np.array(timetagsB)
max_delta_t = np.diff(arrB).min() - 1 #here it's 202 just for the explanation

Вы можете использовать np.searchsorted векторизованным способом: 

# create the array of search 
arr_search = np.searchsorted(arrB, arrA) # the position of each element of arrA in arrB
print (arr_search)
# array([1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 6, 6, 6, 6, 7, 7, 7],dtype=int64)

Вы можете вычислить разницу между элементом arrB, соответствующим каждому элементу arrA, нарезав arrB с помощью arr_search

# calculate the difference
arr_diff = arrB[arr_search] - arrA
print (arr_diff[arr_diff<max_delta_t]) # finc the one smaller than max_delta_t
# array([14, 12, 10, 13, 11, 13], dtype=int64)

Итак, то, что вы ищете, рассчитывается как np.bincount

arr_bins = np.bincount(arr_diff[arr_diff<max_delta_t])
#to make it look like histo but not especially necessary
histo = np.array([range(len(arr_bins)),arr_bins]).T

Теперь проблема в том, что есть некоторые значения разности между arrA и arrB, которые не могут быть получены с помощью этого метода, когда max_delta_t больше, чем два последовательных значения в arrB. Вот один из способов, возможно, не самый эффективный в зависимости от значений ваших данных. Для любого значения max_delta_t 

#need an array with the number of elements in arrB for each element of arrA 
# within a max_delta_t range
arr_diff_search = np.searchsorted(arrB, arrA + max_delta_t)- np.searchsorted(arrB, arrA)
#do a loop to calculate all the values you are interested in
list_arr = []
for i in range(arr_diff_search.max()+1):
    arr_diff = arrB[(arr_search+i)%len(arrB)][(arr_diff_search>=i)] - arrA[(arr_diff_search>=i)]
    list_arr.append(arr_diff[(0<arr_diff)&(arr_diff<max_delta_t)])

Теперь вы можете np.concatenate list_arr и использовать np.bincount, например: 

arr_bins = np.bincount(np.concatenate(list_arr))
histo = np.array([range(len(arr_bins)),arr_bins]).T
...