アルゴリズムの助けが必要です

Question

私は一連のシーケンス（例えば10000シーケンス）を持っており、2つのシーケンス間のペアワイズ類似性を表す行列（10000x10000）を生成します。

ここでは、大きなセットからサブセット（たとえば1000個のシーケンス）を取り出し、このサブセット内の2つのシーケンスのペアごとの類似性が範囲（たとえば50％〜85％）にあることを確認します。

これを行うための高速アルゴリズムはありますか？

Answer 1

あなたは、グラフ理論の問題にこれを変換することができます。

1. あなたの目標がある
、それらの間のエッジがあるよりも、二つのノードの類似性が与えられた範囲内にある場合は各シーケンスは、ノード
3. です（あなたの類似性の関係が推移的な場合は）connected component、または大きい場合はclique（そうでない場合）。

Answer 2

ペアワイズ類似性のリストを生成して（マトリックスに戻って参照する）、そのソートされたリストのサブセットを取得し、そのサブリストとサブセットの交差がサブセットと同じであることを保証することができますサブセット内のすべての要素が指定された範囲内にあることを確認します。

マトリックスを生成するには多くの設定が必要ですが、順序付きリストを作成するには多くの領域が必要です。少なくとも、マトリックスの設定はO（n^2）です。

Answer 3

これは私にとって「クリークの発見」のように聞こえます。クリークの決定問題はNP完全である。

シーケンスの類似性の背景に応じて、最大クリーク問題の近似アルゴリズムに満足できます。ランダム化されたアルゴリズムは、あなたにとって十分であるかもしれません。しかし、一般的にこれは非常に困難な問題であり、N = 100の場合でも多くを処理することはできそうもありません。

Answer 4

多くの類似点は、n次元のドットプロダクトと同等または関連していますたとえ類似性が明示的に計算されていなくても。このような場合や場合によっては、a.bとb.cの値が高いとa.cの値が高いことを意味する可能性がありますが、これの境界はあまり良くありません。最初はそれほど良いとは言えません。

a、b、cの3つのベクトルだけでは、基礎となる空間の次元に関係なく3次元の図を描くことができると思います。最悪の場合は3つのベクトルがすべて上のbとcはbとなる。その場合、例えば、 a.b = b.c = 0.9の場合、aはbの約25度上であり、cはその下の約25度であり、a.c = 0.62である。この場合、ac = bc = xの場合、ac = 2x^2 - 1となります。

このような状況では、この特定の問題を絶対に解決しなければならない場合は、ノードのセットを非常に近い特定のノードに送信する。たとえば、2つの最も類似したノードから始めて、各レベルで、元のシードノードの1つに最も近い試行されていないノードを追加した検索を実行できます。または、単一のリンククラスタリングを構築し、必要なサイズのすべてのサブツリーをチェックアウトすることもできます。