4

N x M バイナリ マトリックスの束を並べ替えて、最も類似したものが二重リンク リストの隣人になるようにするにはどうすればよいですか?

私は一連の 2 次元バイナリ マトリックスを持っており、相互に最も類似したマトリックスがデータ構造内で互いに「隣接」するように、データ構造内の一連のマトリックスを効率的に並べ替える必要があります。効率的に検索する必要があるマトリックスが 40,000 近くあるため、マップ構造は効率的ではないと思います。

2 つの行列間の距離の公式は次のとおりです。

getSimilarity(matrix toCompare)
    //initialize variable "sum" to 0
    //for each rowT in this and each rowC in toCompare
      //sum += max(rowT,rowC) - bitwiseAnd(rowT,rowC)
    // return sum

データ構造を提供する必要さえありません。必要なのは、2 つの行列を比較する方法だけです。これにより、同様の行列が互いにできるだけ近くにクラスター化された結果が得られます。

編集: 12/19/12 1:52PM 私の行はユーザー属性を表し、私の列はページ属性を表します。各マトリックスは、特定のページ属性を持ちながらユーザーが持つ属性を表しています (たとえば、ユーザーの年齢が 42 歳未満で、ページ 4 にアクセスしたことがあるなど)。

4

3 に答える 3

4

マトリックスにある類似性演算子がメトリック空間を定義していることに気付きました。あれは：

  • M1 = M2 の場合に限り、D(M1, M2) = 0
  • 任意の M1、M2 について D(M1, M2) ≥ 0。
  • D(M1、M2) = D(M2、M1)、および
  • D(M1, M3) ≤ D(M1, M2) + D(M2, M3) (三角不等式)

その結果、考えられるすべてのデータを格納できる方法の 1 つは、メトリック空間ツリーにあると考えられます。これは、オブジェクトをメトリック空間に格納するためのデータ構造の一種であり、初期値に「近い」すべての要素を簡単に検索できます。エレメント。

データには、離散メトリック空間であるという利点があります。つまり、提供した距離関数は常に整数の答えを出力します。つまり、互いに距離が 1.5 の 2 つの行列は存在せず、距離 π にある 2 つの行列を取得することもできません。

したがって、マトリックスをBK-treeに格納することをお勧めします。BK ツリーは多くの場合、文字列を格納するために使用されますが、より一般的には、任意の個別のメトリック空間に要素を格納できます。これにより、個々の行列に対して合理的に効率的に最近傍検索を行うことができます (通常、コレクション内のすべての行列を調べる必要はありません)。

直観的に、BK ツリーは次のように構造化されます。選択したマトリックスを「ルート ノード」として選択します。次に、コレクション内のすべての行列をルート行列と比較し、ルート行列からの距離に基づいてサブツリーに分散します。次に、これらの各サブツリーを同じ方法で再帰的に再分割します。三角形の不等式により、単純な再帰アルゴリズムを使用して BK ツリーで近くの行列を検索できます。

お役に立てれば！

于 2012-12-18T01:16:07.433 に答える
1

あなたの相似関数がわかりません。行を行と比較するべきではありませんか？また、一般的に、bitwiseAndが高いほど類似性が高いことを意味しますが、あなたの場合はマイナス記号が付いています。

多くの場合、局所性鋭敏型ハッシュは、あなたのような問題を解決するために使用されます。たとえば、マトリックスが白黒の画像であると想像でき、類似した画像をすばやく見つけたいと考えています。ハッシュ関数は、類似した画像が類似したハッシュを持つように設計されています。したがって、アイテムのデータベースをハッシュし、ハッシュされたスペースで近くのアイテムを見つけて候補として使用し、候補に対してより高価な完全な類似性チェックを実行します。

複数の異なるLSHを使用し、完全な比較を保証するために、少なくとも2つのLSHでいくつかのアイテムが近接している必要がある、増幅と呼ばれるさらに高度な手法があります。大量のデータセットのマイニングの第3章では、問題について詳しく説明しています。

于 2012-12-18T05:27:30.800 に答える
0

2 次元以上の最近傍の状況を処理する手法として、「ボロノイ図」を参照することをお勧めします。

あなたの類似度は単なるスカラー (= 1 次元) 距離ですか? いつもポジティブ？それとも、2 次元以上のベクトル距離を使用する意味があるでしょうか?

ビットごとの AND は、違いを取得するのにはあまり役に立ちません。ビット単位の EXOR の方が理にかなっています。すべてのビットの重要度が同じ場合、2 つの符号なし整数間のハミング距離となる EXOR の 1 ビットをカウントすることができます。

ブール行列の差分カウント距離関数:

int getSimilarity(matrix other) {
  int sum = 0;

  for(int col = 1; col < M; col++) {
    for (int row = 1; row < N; row++) {
       sum += (this[row, col] != other[row, col]) ? +1 : 0;
    }
  }

  return sum;
}

この距離関数は、行/列の距離に重み係数を掛けることで調整できます。

于 2012-12-18T07:40:11.563 に答える