10

それぞれ平均 100 個の文字列を含む 250,000 個のリストがあり、10 個の辞書に保存されています。すべてのリストのペアごとの類似度を計算する必要があります (類似度メトリックはここでは関係ありませんが、簡単に言えば、2 つのリストの交差を取得し、結果を何らかの定数で正規化する必要があります)。

ペアごとの比較のために思いついたコードは非常に簡単です。itertools.product を使用して、すべてのリストを他のすべてのリストと比較しています。問題は、250,000 のリストに対してこれらの計算を時間効率の良い方法で実行することです。同様の問題に対処したことがある人へ：次の基準に関して、通常のオプション（scipy、PyTables）のどれがこれに最適ですか：

  • Python データ型をサポート
  • 非常にまばらな行列をスマートに格納します (値の約 80% は 0 になります)
  • 効率的 (10 時間以内に計算を実行できます)
4

2 に答える 2

10

データ内の任意の 2 点間の距離を決定する最も効率的な方法が必要ですか?

それとも、データ内のすべての行のすべてのペアワイズ類似度値を格納するこのmxm距離行列が実際に必要ですか?

通常、ペアごとの類似度の値を事前に計算して調べるよりも、迅速な検索用に最適化されたデータ構造を使用して、何らかのメトリック空間にデータを保持する方がはるかに効率的です。言うまでもなく、距離行列オプションは恐ろしくスケーリングします。n 個のデータ ポイントには、ペアごとの類似度スコアを格納するために nxn 距離行列が必要です。

kd ツリーは、小さい次元のデータに最適な手法です (ここでの「小さい」とは、特徴の数が約 20 未満であることを意味します)。 ボロノイ テッセレーションは、より高次元のデータに適していることがよくあります。

最近では、ボール ツリーが両方の優れた代替手段として使用されています。ボール ツリーは、kd ツリーのパフォーマンスを備えていますが、高次元での劣化はありません。

scikit-learn には、単体テストを含む優れた実装があります。それは十分に文書化されており、現在活発に開発されています。

scikit-learnはNumPyとSciPyで構築されているため、どちらも依存関係にあります。サイトには、scikit-learn のさまざまなインストール オプションが用意されています。

ボール ツリーの最も一般的な使用例はk-Nearest Neighborsです。ただし、OPで説明されているような場合など、それ自体で非常にうまく機能します。

次のようにscikit-learn ボール ツリーの実装を使用できます。

>>> # create some fake data--a 2D NumPy array having 10,000 rows and 10 columns
>>> D = NP.random.randn(10000 * 10).reshape(10000, 10)

>>> # import the BallTree class (here bound to a local variable of same name)
>>> from sklearn.neighbors import BallTree as BallTree

>>> # call the constructor, passing in the data array and a 'leaf size'
>>> # the ball tree is instantiated and populated in the single step below:

>>> BT = BallTree(D, leaf_size=5, p=2)

>>> # 'leaf size' specifies the data (number of points) at which 
>>> # point brute force search is triggered
>>> # 'p' specifies the distance metric, p=2 (the default) for Euclidean;
>>> # setting p equal to 1, sets Manhattan (aka 'taxi cab' or 'checkerboard' dist)

>>> type(BT)
    <type 'sklearn.neighbors.ball_tree.BallTree'>

ボール ツリーのインスタンス化と生成は非常に高速です (Corey Goldberg のタイマー クラスを使用してタイミングを計っています)。

>>> with Timer() as t:
        BT = BallTree(D, leaf_size=5)

>>> "ball tree instantiated & populated in {0:2f} milliseconds".format(t.elapsed)
        'ball tree instantiated & populated in 13.90 milliseconds'

ボール ツリーのクエリも高速です。

クエリの例:データ ポイント行インデックス 500 に最も近い 3 つのデータ ポイントを指定します。そして、それらのそれぞれについて、インデックスと、D[500,:] にあるこの参照点からの距離を返します。

>>> # ball tree has an instance method, 'query' which returns pair-wise distance
>>> # and an index; one distance and index is returned per 'pair' of data points

>>> dx, idx = BT.query(D[500,:], k=3)

>>> dx    # distance
    array([[ 0.   ,  1.206,  1.58 ]])

>>> idx    # index
    array([[500, 556, 373]], dtype=int32)

>>> with Timer() as t:
    dx, idx = BT.query(D[500,:], k=3)


>>> "query results returned in {0:2f} milliseconds".format(t.elapsed)
        'query results returned in 15.85 milliseconds'

scikit-learn ボール ツリー実装のデフォルトの距離メトリックはMinkowskiであり、これはユークリッドとマンハッタンの単なる一般化です (つまり、ミンコフスキー式には、パラメーター p があり、2 に設定するとユークリッドとマンハッタンに折りたたまれます) 、p = 1の場合。

于 2013-01-11T01:55:54.287 に答える
0

適切な距離 (類似度) 関数を定義すると、scipy.spatial.distanceのいくつかの関数が役立つ場合があります

于 2013-01-10T22:51:57.090 に答える