寻求一些建议。有没有人知道在n维空间中匹配算法的好地方开始查找？例如，任何约会网站都必须使用某种算法来匹配两个人。我所了解的是，我们可以将一个人的特征映射到n维数组中，并为每个特征分配一个点数。一旦我们拥有了所有（可用的）特征，我们就可以在n维数组中表示此人的点。然后，将2个人匹配起来就像在这个n维数组中找到2个点之间的最短距离一样简单。有没有人参考实现这种算法的资料？编写这种东西的最佳语言是什么？
5个回答
6
如果您想要找到一个人的最佳匹配，Bentley & Shamos 发布了一种多维分治方法：在 O(N log N) 的时间内进行分治：Divide-and-conquer in multidimensional space，发表于1976年第八届ACM理论计算机科学研讨会。如果找不到副本，这个也可能会有所帮助。
然而，在您的示例应用中，实际上找到最近邻并不是最大的问题 - 更棘手的是将输入映射到维度。例如，如果一个维度是“喜欢动物”，对于那些喜欢狗和猫但受不了马的人，应该给予什么价值？那么喜欢马，认为狗还行，讨厌猫，并且对金鱼漠不关心的人呢？
然而，在您的示例应用中，实际上找到最近邻并不是最大的问题 - 更棘手的是将输入映射到维度。例如，如果一个维度是“喜欢动物”，对于那些喜欢狗和猫但受不了马的人，应该给予什么价值？那么喜欢马，认为狗还行，讨厌猫，并且对金鱼漠不关心的人呢？
- danio
2
匹配人到维度上的建议很好。也许可以像每个维度上有一个刻度一样，比如：喜欢猫和狗但不喜欢马的人会得到+1/+1/-1的分数，在那个维度上得到+1的分数或类似的东西。 - Reed Copsey
@danio: 你可以将一个单一的“喜欢动物”维度分解为独立的“喜欢狗”，“喜欢猫”等维度。 - j_random_hacker
1
以下是一个解决方案。
假设用户为U1、U2、U3、U4、U5......Un。 属性为A1、A2、A3、A4、A5......Am。
将它们存储为：
A1 - U1、U2、U3... A2 - U4、U6、U7.... A3 -
配置文件属性是索引，存储所有用户。现在，如果有一个新用户加入，查看其属性，并找到这些属性的共同用户。出现在这些列表中的次数越多，排名越高。
- Thoughtful Monkey
1
首先，选择您最熟悉的语言。处理此类算法相当简单，并且应该适用于任何现代语言。（只要存在某种数组概念和可能的矩阵库，您就应该没问题。）我之前在C、C++和C#中实现了许多这样的算法，但也看到了Python、VB.NET等语言的实现。
根据您想要做什么，有几个选项。
话虽如此，您想要做什么取决于您的目标。如果您只想找到最佳匹配，可以使用简单的距离计算（即：n维数组中每个维度/属性的平方和的平方根），可选择加权每个属性的距离，然后使用最接近的点。
如果您想将人员分组在一起，则需要考虑聚类算法。对于此类数据，我认为K-Means聚类或模糊C均值聚类是最好的选择。
- Reed Copsey
0
你用例子描述的并不是n维匹配，而是具有多个特征节点的二分图匹配。（您需要提供一个函数，可以计算出两个人之间的距离）。对此应该有非常有效的算法。在n维匹配中，您将尝试从超过两个集合中匹配节点（在您的例子中，假设您可以将人划分为身体、灵魂和音乐偏好，则重新组合它们以制造出真正美好的情侣。）这里是三维匹配的维基百科文章，它是NP完全的。
另外，正如其他人所指出的那样，如果您的目标不是将人配对，而是找到兼容的群体，则应考虑将它们聚集到一起。可以使用无监督学习等方法来实现。
- ntg
0
你提到的过程被称为k最近邻，其中k=1。这是寻找相似向量最直观的方法。
- rjprins
1
k最近邻算法是一种分类算法，不是Herman正在寻找的内容。 - Fifi
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接