ゴール
私は取得しようとしています:
- おおよその最近傍ライブラリ FLANN、および
- Python バインディング pyflann
Ubuntu を実行している AWS ec2 インスタンスで正しく動作します。私の目的は、FLANN を他の ANN 実装 (ANNOY や scikit-learn ANN 実装など) と比較して、どちらが私が働いている会社に最適かを確認することです。次元が 500 までの数百万のベクトルを扱っています。
このため、代替の ANN 実装の提案を受け取るよりも、FLANN 自体を機能させることが重要です。Radim Rehurekの素敵なブログ投稿は知っていますが、さまざまな ANN アルゴリズムのパフォーマンスを確認したい具体的なデータ セットがあるため、彼のブログは私たちが独自にベンチマークする必要性を排除しません。データ。
問題
私は flann と pyflann の両方のバージョンをインストールすることに成功しましたが、「kmeans」パラメーターを使用して ANN インデックスを作成するように求められたときに、pyflann は意味のない結果を返します。たとえば、次の Python コードとその出力を考えてみましょう。
>>> from pyflann import *
>>> from numpy import *
>>> from numpy.random import *
>>> dataset = rand(1000, 100)
>>> testset = rand(10, 100)
>>> flann = FLANN()
>>> result,dists = flann.nn(dataset,testset, 5, algorithm="kmeans")
>>> print result
[[ -278697864 32687 -278697864 32687 1677721700]
[ 40632322 6 16778074 1677721700 9]
[ 285184 1509950821 12 25600 1811940196]
[ 15 426661632 140837888 18 16801138]
[ 16779610 21 23986182 107304960 24]
[-2080373660 190447616 27 1694501978 224002059]
[ 30 1694502490 257556491 33 -2080373404]
[ 207224832 36 1509949572 49 0]
[ 43668848 0 -278698024 32687 8650760]
[ 1006080 1392509796 1397948499 208 0]]
>>>
次の行から：
result,dists = flann.nn(dataset,testset, 5, algorithm="kmeans")
"testset" 内の 10 個の 100 次元ベクトルのそれぞれに対して 5 つの近傍を求めている場合、出力された配列は正しい次元を持ちます: 10 行は "testset" 内の 10 個のベクトルに対応し、各行の長さは 5 であり、事実を反映しています。私は5人の隣人を求めました。ただし、エントリの値は正しくありません。一部のエントリは負であり、多くのエントリは範囲 0 ～ 999 (考えられる最近傍のインデックスの範囲) の外にあるためです。比較のために、「kmeans」のみを「kdtree」に変更して、上記とほぼ同じコードを使用した私の端末の出力を次に示します。
>>> from pyflann import *
>>> from numpy import *
>>> from numpy.random import *
>>> dataset = rand(1000, 100)
>>> testset = rand(10, 100)
>>> flann = FLANN()
>>> result,dists = flann.nn(dataset,testset, 5, algorithm="kdtree")
>>> print result
[[189 363 397 723 685]
[400 952 892 332 477]
[560 959 295 591 394]
[596 652 250 43 448]
[498 706 543 761 323]
[334 974 591 620 766]
[435 386 58 962 421]
[234 301 189 355 191]
[857 133 420 544 612]
[978 995 439 648 627]]
>>>
今回は、期待どおり、すべてのエントリが 0 から 999 までの非負の整数です。もちろん、データはランダムに生成されるため、結果はさまざまですが、"kmeans" 引数を使用すると一貫してばかげた結果が生成されますが、"kdtree" は一貫して適切な結果が生成されます。
ソフトウェアとOSの詳細
(0) Ubuntu ディストリビューション:
Ubuntu 14.04 LTS
(1) libflann-dev:
タイピング：
sudo aptitude show libflann-dev
プロデュース:
Package: libflann-dev
State: installed
Automatically installed: no
Version: 1.8.4-3
Priority: optional
Section: universe/libdevel
Maintainer: Ubuntu Developers <ubuntu-devel-discuss@lists.ubuntu.com>
Architecture: amd64
Uncompressed Size: 11.2 M
Depends: libflann1.8 (= 1.8.4-3)
Description: Fast Library for Approximate Nearest Neighbors - development
FLANN is a library for performing fast approximate nearest neighbor searches in high dimensional spaces. It contains a collection of algorithms found to work best for
nearest neighbor search and a system for automatically choosing the best algorithm and optimum parameters depending on the dataset.
This package contains development files needed to build FLANN applications.
Homepage: http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN
(2)入力:
sudo aptitude show python
生成:
Package: python
State: installed
Automatically installed: no
Multi-Arch: allowed
Version: 2.7.5-5ubuntu3
Priority: optional
Section: python
Maintainer: Ubuntu Developers <ubuntu-devel-discuss@lists.ubuntu.com>
Architecture: amd64
Uncompressed Size: 687 k
Depends: python2.7 (>= 2.7.5-1~), python-minimal (= 2.7.5-5ubuntu3), libpython-stdlib (= 2.7.5-5ubuntu3)
Suggests: python-doc (= 2.7.5-5ubuntu3), python-tk (>= 2.7.5-1~)
Conflicts: python-central (< 0.5.5)
Breaks: python-bz2 (< 1.1-8), python-csv (< 1.0-4), python-email (< 2.5.5-3), update-manager-core (< 0.200.5-2)
Replaces: python-dev (< 2.6.5-2)
Provides: python-ctypes, python-email, python-importlib, python-profiler, python-wsgiref, python:any
Description: interactive high-level object-oriented language (default version)
Python, the high-level, interactive object oriented language, includes an extensive class library with lots of goodies for network programming, system administration,
sounds and graphics.
This package is a dependency package, which depends on Debian's default Python version (currently v2.7).
Homepage: http://www.python.org/
インストール方法
最初に、次のコマンドで FLANN をインストールしようとしました。
sudo apt-get install libflann1.8
pyflann をインストールした後:
sudo pip install -e git+git://github.com/Captricity/pyflann.git#egg=pyflann,
私が入力した：
python -c 'import pyflann'
エラーメッセージを受け取りました：
Traceback (most recent call last):
File "<string>", line 1, in <module>
File "/mnt/working/src/pyflann/pyflann/__init__.py", line 27, in <module>
from index import *
File "/mnt/working/src/pyflann/pyflann/index.py", line 27, in <module>
from bindings.flann_ctypes import *
File "/mnt/working/src/pyflann/pyflann/bindings/__init__.py", line 30, in <module>
from flann_ctypes import *
File "/mnt/working/src/pyflann/pyflann/bindings/flann_ctypes.py", line 169, in <module>
raise ImportError('Cannot load dynamic library. Did you compile FLANN?')
ImportError: Cannot load dynamic library. Did you compile FLANN?
次に、新しい ec2 インスタンスで、次のように入力しました。
sudo apt-get install libflann-dev
sudo pip install -e git+git://github.com/Captricity/pyflann.git#egg=pyflann
そして走った
python -c 'import pyflann'
文句なし。ただし、上記の「kmeans」の問題があります。
ノート
私は自分の MacBookPro に FLANN と pyflann をインストールすることに成功しました。すべて正常に動作します。最近傍クエリ引数として "kmeans" を使用しても、適切な結果が得られます。