分类数据

Question

让我们说我有一些大集合的数据，排在一行中的每个元素是一个（键，值）对：

1) [(bird, "eagle"), (fish, "cod"),  ... , (soda, "coke")] 
2) [(bird, "lark"), (fish, "bass"),  ..., (soda, "pepsi")] 
n) .... 
n+1) [(bird, "robin"), (fish, "flounder"), ..., (soda, "fanta")] 

我想的能力，运行一些可以让我确定新行的计算，那么与这一行“最相似”的行是什么？

我认为找到任何特定行的“最相似”行的最直接方式是直接将所述行与所有其他行进行比较。这显然在计算上非常昂贵。

我正在寻找以下形式的解决方案。

• ，可以采取一排，并且产生用于该行的一些衍生物的整数的函数。这个返回的整数将是该行的一种“签名”。这个签名的重要属性是，如果两行非常“相似”，它们将生成非常接近的整数，如果行非常“不同”，则它们会生成较远的整数。显然，如果它们是相同的行，它们会生成相同的签名。

• 然后，我可以将这些生成的签名与它们所指向的行的索引进行匹配，并通过它们的签名对它们进行排序。我将保留这种数据结构，以便我可以快速查找。说它数据库B.

• 当我有一个新的行，我想知道哪些存在的行中的数据库B是最相似的，我想：

  1. 生成一个签名为新行
  2. 通过在数据库B的衣柜比赛
  3. 返回最匹配的（签名指数）排序列表中的二进制搜索（可能是一个完美的匹配）在数据库B行

我知道他们在这个问题上挥舞着很多手。我的问题是，我实际上不知道该函数会产生这个签名。我看到Levenshtein距离，但这些代表了转换成本，而不是签名。我看到我可以尝试有损压缩，有两件事情可能是“可铲除的”，因为它们压缩到相同的东西。我正在寻找关于如何做到这一点的其他想法。

谢谢。

Answer 1

编辑：这是我原来的答复，我们称之为案例1，在没有优先的键

你不能做到这一点作为一个有序整数，因为这是一维的，你的数据是多维的。所以在这个意义上的“接近”不能成立。

你的例子显示了所有3条线的鸟，鱼和苏打水。钥匙是否固定并且已知？如果它们不是，那么你的第一步是散列一行的键来建立具有相同键的行。

对于这些值，可以认为这是一个穷人的周六晚上的相似把戏。对值进行哈希处理，在哈希上匹配的任何两行都是完全匹配的，并表示相同的“点”，零距离。

如果N是键/值对的数目：

最接近非精确“接近度”将意味着匹配N-1 N个值。因此，您生成N个以上的哈希值，每个哈希值都会删除一个值。在这些散列上匹配的任何两行在共同的N个值中都有N-1个。

下一个最接近的非精确“接近度”将意味着N个值中的N-2匹配。因此，你生成的N以上的散列（我无法确定这个迟到的二进制数），这次每个散列都留下了两个值的组合。在这些散列上匹配的任何两行都有N-N个共同的N-2个。

所以你可以看到这是怎么回事。在逻辑上，你最终会得到2^N哈希，但并不是非常可口，但我认为你不会走得太远，因为你达到了一个点，即匹配值太少会被认为是“值得考虑的”。

编辑：要看看我们如何逃避维度，只考虑两个键，值1-9。绘制图表上所有可能的值。我们看到{1,1}接近{2,2}，但{5,6}接近{6,7}。所以我们得到一个头脑风暴，我们说，啊哈！我会用毕达哥拉斯定理计算每个点与原点的距离！这将使{1,1}和{2,2}易于检测。但是，然后{1,10}和{10,1}两点将得到相同的数字，即使它们与图上的距离相差太远。所以我们说，好的，我需要为每个角度添加角度。相同距离处的两个点通过它们的角度来区分，两个相同角度的点通过它们的距离来区分。但是现在我们已经在两个维度上绘制了它们。

编辑：情况2。将当存在优先给键，当键1大于钥匙2更显著，这是比键3，等。在这种情况下更显著，如果所允许的值分别AZ，您可以将这些值串在一起，就好像它们是数字一样以获得可排序的值。 ABC离ABD非常近，但离BBD很远。

Answer 2

如果你有很多数据，并想要做这个核心，我会建议一个统计方法，如PLSA或PSVM，它可以从文本中提取标识主题并识别具有相似主题概率的文档。

一个简单但不太准确的方法是使用Soundex，它可用于多种语言。你可以存储soundex（这将是一个简短的字符串，不是一个整数，我怕），并寻找与soundex完全匹配，它应该指向类似的行。

我认为期望函数将一系列字符串转换为一个整数，使得彼此相邻的整数映射到相似的字符串是不现实的。最接近的可能是对每个单独的元组进行校验和，并将新行的校验和与现有行的校验和进行比较，但是我猜你正试图想出一个可以编入索引的单个数字。