在这里寻找一些建议。有谁知道在 n 维空间中开始研究匹配算法的好地方。例如，任何约会网站都必须使用某种算法来匹配 2 个人。我读到的是，我们可以将一个人的特征映射到一个 n 维数组中，每个特征都有一个点系统。一旦我们拥有了一个人的所有（可用）特征，我们就可以在一个 n 维数组中的一个点中表示这个人。然后，匹配 2 个人就像在这个 n-dim 数组中找到 2 点之间的最短距离一样简单。有没有人在实现这类算法时有任何参考？写这些东西的最佳语言是什么？
问问题
4481 次
5 回答
6
如果你想为一个人找到最接近的匹配，Bentley & Shamos 发表了一种多维分治法：O(N log N) time 分治法：Divide-and-conquer in multidimensional space in 1976 年第八届 ACM 计算理论年度研讨会论文集。如果您无法获得副本，这也可能会有所帮助。
但是，对于您的示例应用程序，实际上找到最近的邻居似乎并不是最大的问题——将输入映射到维度要棘手得多。例如，如果一个维度是“喜欢动物”，那么对于喜欢狗和猫但不能忍受马的人，你赋予什么价值？喜欢马、认为狗还可以、被猫惹恼、对金鱼矛盾的人呢？
于 2009-03-24T15:59:09.950 回答
1
首先，选择您最熟悉的语言。处理这个问题的算法相当简单，并且应该适用于任何现代语言。（只要有一些数组的概念，可能还有矩阵库，你应该没问题。）我以前在 C、C++ 和 C# 中实现了许多这些，但在 python、vb.net 等中看到了实现.
根据您要执行的操作，有几种选择。
话虽如此，你想做什么取决于你的目标。如果您只想找到最佳匹配，您可以使用简单的距离计算（即：n 维数组中每个维度/属性的平方和的 sqrt），可选地加权每个属性距离，并使用最近点。
如果您想将人们分组在一起，您需要查看聚类算法。对于这样的数据，我怀疑某种形式的 K-Means 聚类或模糊 c-means 聚类效果最好。
于 2009-03-24T15:50:02.813 回答
1
下面的解决方案怎么样。
假设用户是 U1, U2, U3, U4, U5.... Un。属性是A1，A2，A3，A4，A5..... Am
将这些存储为
A1 - U1、U2、U3... A2 - U4、U6、U7.... A3 -
Profile属性是索引并存储所有用户。现在，如果有新用户出现，请查看其属性，对于这些属性，请查找普通人。一个人出现在这些列表中的次数 - 更高的排名。
于 2012-05-07T05:46:36.623 回答
0
您在示例中描述的不是 n 维匹配，而是具有多个特征的节点的二分匹配。（你需要提供一个函数，假设两个人计算这个距离）。应该有非常有效的算法。在 n 维匹配中，您将尝试匹配来自两个以上集合的节点（在您的示例中，假设您可以将人们切割成身体、灵魂和音乐偏好，然后将它们重新组合成新的人。那么 n 维匹配将把人们分开，然后重新组合，这样新设计的人就会成为非常好的夫妻：D）这是维基百科文章中的 3 维匹配，它是 np 完整的。
此外，正如另一个人所指出的，如果您的目标不是成对匹配人，而是找到兼容的组，您应该考虑将他们聚集到组中。这可以通过例如无监督学习来完成
于 2014-04-02T13:45:55.077 回答
0
您提到的过程称为k最近邻居，k = 1。这是寻找相似向量的最直观的方法。
于 2009-04-01T11:48:28.010 回答