2

私は次のサブ問題があるアイデアを試しています:

m固定長のタプルを含むsize のリストがありますn。

[(e11, e12, .., e1n), (e21, e22, .., e2n), ..., (em1, em2, .., emn)]

(t1, t2, .., tn)ここで、リストに属さないランダムなタプルが与えられた場合、リストに属する最も近いタプルを見つけたいと思います。

次の距離関数 (ハミング距離) を使用します。

def distance(A, B):
    total = 0
    for e1, e2 in zip(A, B):
        total += e1 == e2
    return total

1 つのオプションは、徹底的な検索を使用することですが、リストが非常に大きいため、これは私の問題には十分ではありません。私が思いついた他のアイデアは、最初kmedoidsにリストをクラスター化してKmedoid（クラスターセンター）を取得するために使用することです。クエリでKは、distance 関数を呼び出して最も近いクラスターを特定できます。次に、その特定のクラスターから最も近いタプルを検索できます。うまくいくはずだと思いますが、クエリタプルがクラスターの端にある場合に問題がないかどうかは完全にはわかりません。

しかし、私の心は今完全に空白なので、問題を解決するためのより良いアイデアがあるかどうか疑問に思っていました. しかし、何か巧妙な方法があるのではないかと強く感じています。

何かを事前に計算する必要があるソリューションは、クエリの複雑さを軽減する限り問題ありません。

4

2 に答える 2

3

要素 (タプル内) からそれが表示されるタプルにマップするハッシュ テーブル (辞書/マップ) を格納できますhash:element->list<tupple>。

ここで、新しい「クエリ」がある場合、新しい「クエリ」の各要素に対してそれぞれを繰り返しhash(element)、ヒットの最大数を見つける必要があります。

擬似コード:

findMax(tuple):
  histogram <- empty map  
  for each element in tuple:
     #assuming hash_table is the described DS from above
     for each x in hash_table[element]: 
         histogram[x]++ #assuming lazy initialization to 0
  return key with highest value in histogram

希望するメトリックに正確に従わない代替手段は、kd treeです。違いは、要素間の「距離」も考慮に入れるkdツリーです（平等/不平等だけではありません）。
kd ツリーでは、要素が比較可能である必要もあります。

于 2012-11-15T15:18:28.883 に答える
1

データが十分に大きい場合は、その上にいくつかの逆インデックスを作成することをお勧めします。

n要素のmベクトルのデータを使用します。

データ：

0: 1, 2, 3, 4, 5, ...
1: 2, 3, 1, 5, 3, ...
2: 5, 3, 2, 1, 3, ...
3: 1, 2, 1, 5, 3, ...
...
m: m0, ... mn

次に、次のようにn 個のインデックスを取得します。

インデックス0

1: 0, 3
2: 1
5: 2

インデックス1

2: 0, 3
3: 3, 3

インデックス2

3: 0
1: 1, 3
2: 2

...

次に、インデックスのみを検索して、クエリのタプル値のいずれかを含むタプルを取得し、それらの中で最も近いタプルを見つけます。

def search(query)
  candidates = []
  for i in range(len(query))
    value = query[i]
    candidates.append(indexes[i][value])

  # find candidates with min distance
  for candidate in candidates
    distance = distance(candidate, query)
    ...

重いプロセスはインデックスを作成することです.インデックスを作成すると、検索は非常に高速になります.

于 2012-11-15T23:05:53.367 に答える