2

我正在尝试一个想法，我有以下子问题：

我有一个m包含固定长度元组的大小列表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

一种选择是使用穷举搜索，但这对于我的问题是不够的，因为列表非常大。我想出的另一个想法是首先使用kmedoids对列表进行聚类并检索Kmedoids（聚类中心）。对于查询，我可以通过K调用距离函数来确定最近的集群。然后，我可以从该特定集群中搜索最近的元组。我认为它应该可以工作，但我不完全确定，如果查询元组位于集群的边缘是否可以。

但是，我想知道，如果你有更好的想法来解决这个问题，因为我的大脑现在完全是空白的。但是，我有一种强烈的感觉，可能有一种聪明的方法可以做到这一点。

只要能够降低查询的复杂性，需要预先计算的解决方案就可以了。

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 回答