n维匹配算法

Question

在这里寻找一些建议.有没有人知道在n维空间中开始研究匹配算法的好地方.例如,任何约会网站必须使用某种算法来匹配2个人.我所读到的是,我们可以使用针对每个特征的点系统来映射n维阵列中的人的特征.一旦我们拥有了一个人的所有(可用)特征,我们就可以在n维数组中的某个点上表示这个人.然后,匹配2个人就像在这个n-dim阵列中找到2点之间的最短距离一样简单.有没有人对这类算法的实现有任何参考？写这些东西的最佳语言是什么？

Answer 1

如果你想找到一个人最接近的匹配,宾利和Shamos发表了多层面的分而治之的方法:为O分而治之(N日志N)时间:分而治之的多维空间中关于计算理论的第八届年度ACM研讨会的会议记录1976.如果你不能得到一份副本,这也可能有所帮助.

然而,对于您的示例应用程序,实际上找到最近邻居似乎并不是最大的问题 - 将输入映射到维度上要困难得多.例如,如果一个维度是"喜欢动物",那么您对喜欢狗和猫但不能忍受马的人有什么价值呢？那些爱马的人,认为狗是好的,对猫很生气,对金鱼有些矛盾吗？

Answer 2

首先，选择您最熟悉的语言。处理这个问题的算法相当简单，并且应该适用于任何现代语言。（只要有一些数组的概念，并且可能有一个矩阵库，你应该没问题。）我之前已经用 C、C++ 和 C# 实现了其中的许多概念，但也见过 python、vb.net 等中的实现。

根据您想要做什么，有几种选择。

话虽这么说，你想做什么取决于你的目标。如果您只想找到最佳匹配，可以使用简单的距离计算（即：n 维数组中每个维度/属性的平方和的 sqrt），可选择对每个属性距离进行加权，并使用最近的点。

如果您想将人们分组，您需要了解聚类算法。对于这样的数据，我怀疑某种形式的 K 均值聚类或模糊 c 均值聚类效果最好。