問題タブ [locality-sensitive-hash]

ユークリッド距離を使用する Python 3 での LSH の効率的な実装を探しています。

「in-python」LSHForest実装がありますが、コサイン距離を使用します。

また、この実装を使用しても、各バスケットのコンテンツを表示する方法が見つかりませんでした。たとえば、クラスタリングに LSH を使用している場合、特定の半径内にある特定の数のおおよそのネイバーのみが返されます。しかし、すべての隣人を見たい場合、それがどのように行われるかわかりません（任意の検索半径を使用したくありません。これを使用して非常に大きなまたは無限の半径の意味が何であるかが本当にわかりません実装）。

どんな洞察にも感謝します。どうもありがとう。

私はすでにこの質問を読みましたが、残念ながら役に立ちませんでした。

私が理解していないのは、どのバケットが高次元空間クエリ ベクトルに割り当てられるかを理解した後で何をするかということですq。局所性に依存するファミリ関数のセットを使用して、低次元 (次元) ハッシュ コードh_1,h_2,...,h_nに変換したとします。qnc

次に、割り当てられcたバケットのインデックスでありq、(うまくいけば) 最も近い隣人にも割り当てられます。たとえば、100 個のベクトルがあるとします。

さて、 の NN を見つけるために行うことは、これら100個のベクトルqの間の距離を計算することですが、それは正しいですか? つまり、 の使用はインデックス作成のためだけです (どのバケットに割り当てるかを決定するためだけに使用されます) ですね。qcq

この調査 (セクション 2.2) で説明されているように、「ハッシュ テーブル ルックアップ」(前述のアプローチ) に代わる別の解決策は「高速距離近似」ですc。データセット内の各要素に関連するハッシュ コード。ハッシュコードが低次元空間にあり、距離の計算が高速であるため、これは高速であると想定されています（たとえば、ハッシュコード空間がバイナリの場合、XOR演算子を使用してハミングをすばやく計算できます2 つのハッシュ コード間の距離）。

さて、私が疑問に思っているのは、2つの方法の利点/欠点は何ですか? 他のアプローチではなく、あるアプローチを使用する必要があるのはなぜですか?

「エンティティ解決」タイプのユース ケースがあり、多くの (数百万の) デバイスで使用できるいくつかの (100 未満の) デバイス機能があります。私の目標は、これらのデバイスの ID を生成することです。課題は、同じデバイスが 2 つ以上のわずかに異なる表現を持つ可能性があることですが、それでもそれらすべてに同じデバイス ID を割り当てたいと考えています。

この点に関して、あなたの推薦が欲しいです：

1. どのような機能の前処理を適用する必要がありますか?
2. 私の目的に最適なアルゴリズムはどれですか?
3. そのようなアルゴリズムの標準的な実装があるかどうかについて言及してください。

よろしくお願いいたします。

パンダでファジーマッチングを使用して重複行を（効率的に）検出する方法

row_i を String() に変換し、それを他のすべてのものと比較する巨大な for ループなしで、1 つの列と他のすべての列の重複を見つける方法は?

Spark 1.4 ( https://github.com/soundcloud/cosine-lsh-join-spark/tree/master/src/main/scala/com/soundcloud/lsh ) で LSH アルゴリズムを適用し、テキスト ファイル (4GB ) LIBSVM 形式 ( https://www.csie.ntu.edu.tw/~cjlin/libsvm/ ) で重複を見つけます。まず、36 コアのエグゼキューターを 1 つだけ使用して、サーバーで scala スクリプトを実行しました。1.5時間で結果を取得しました。

結果をより速く取得するために、各ノードに 20 コアと 64 GB のメモリがある 3 つのノードを持つ hpc の糸を介して、hadoop クラスターでコードを実行しようとしました。私は hpc でコードを実行した経験があまりないので、ここにある提案に従いました: https://blog.cloudera.com/blog/2015/03/how-to-tune-your-apache-spark-jobs-part -2/

その結果、私は以下のように火花を提出しました：

私が理解しているように、ノードごとに 3 つのエグゼキューターを割り当て、各エグゼキューターに 19 GB を割り当てました。

しかし、2時間以上経過しても結果が得られませんでした。

私のスパーク構成は次のとおりです。

この問題をどのように掘り下げることができますか? 計算時間を改善するには、どこから始めればよいですか?

編集：

1)

私は合体が糸ではるかに遅いことに気づきました

2)

HPC のエグゼキューターとステージ:

サーバーからの実行者とステージ:

各ポイントの最近傍を見つけたいのですが、karlhigley ANN モデルを使用して試しました。これがコードの一部です

JavaRDD の neighbors2 は、すべてのネイバーとそのスコアを null として表示します。どこで間違って実装しているのか、正しい方法で実装する方法を理解するのを手伝ってくれる人はいますか?

これは私が出力を印刷する方法です