0

メモリが限られているビッグ データに対して knn 検索を実行しようとしています。

私は HDF5 と python を使用しています。

ブルートフォース線形検索（pytablesを使用）とkd-tree検索（sklearnを使用）を試しました

驚くべきことですが、kd-tree メソッドにはより多くの時間がかかります (バッチ サイズを大きくすると、kd-tree がよりうまく機能するのではないでしょうか? しかし、メモリによって制限される最適なサイズもわかりません)。

今、私は計算を高速化する方法を探しています.HDF5ファイルは個々のPCに合わせて調整できると思います.また、おそらくnymexprまたはいくつかのpythonトリックを使用してノルム計算を高速化できます. 

import numpy as np
import time
import tables
import cProfile

from sklearn.neighbors import NearestNeighbors

rows = 10000
cols = 1000
batches = 100
k= 10

#USING HDF5
vec= np.random.rand(1,cols)
data = np.random.rand(rows,cols)
fileName = 'C:\carray1.h5'
shape = (rows*batches, cols)  # predefined size
atom = tables.UInt8Atom()  #?
filters = tables.Filters(complevel=5, complib='zlib') #?

#create
# h5f = tables.open_file(fileName, 'w')
# ca = h5f.create_carray(h5f.root, 'carray', atom, shape, filters=filters)

# for i in range(batches):
    # ca[i*rows:(i+1)*rows]= data[:]+i  # +i to modify data

# h5f.close()

#can be parallel?
def test_bruteforce_knn():
    h5f = tables.open_file(fileName)

    t0= time.time()
    d = np.empty((rows*batches,))
    for i in range(batches):
        d[i*rows:(i+1)*rows] = ((h5f.root.carray[i*rows:(i+1)*rows]-vec)**2).sum(axis=1)
    print (time.time()-t0)
    ndx = d.argsort()
    print ndx[:k]

    h5f.close()

def test_tree_knn():
    h5f = tables.open_file(fileName)

        # it will not work
    # t0= time.time()
    # nbrs = NearestNeighbors(n_neighbors=k, algorithm='ball_tree').fit(h5f.root.carray)
    # distances, indices = nbrs.kneighbors(vec)
    # print (time.time()-t0)

        #need to concatenate distances, indices somehow 
    t0= time.time()
    d = np.empty((rows*batches,))
    for i in range(batches):
        nbrs = NearestNeighbors(n_neighbors=k, algorithm='ball_tree').fit(h5f.root.carray[i*rows:(i+1)*rows])
        distances, indices = nbrs.kneighbors(vec)  # put in dict? 
        #d[i*rows:(i+1)*rows] = 
    print (time.time()-t0)
    #ndx = d.argsort()
    #print ndx[:k]

    h5f.close()

cProfile.run('test_bruteforce_knn()')
cProfile.run('test_tree_knn()')
4

1 に答える 1

1

私が正しく理解している場合、あなたのデータには 1000 次元がありますか? この場合、kd-tree は次元の呪いに苦しむため、うまく機能しないことが予想されます。

代わりに、近似最近傍検索方法を確認することをお勧めします。たとえば、flannを見てください。

于 2013-10-25T07:38:57.350 に答える