algorithm - 在图中查找最接近匹配的高效算法

Question

编辑:包括对我的问题的具体解释(由 Billiska 正确推断):"集合A是用户的集合。集合B是产品的集合。每个用户对一个或多个产品进行评分。评分是1到10。你想为每个用户推断，谁是另一个用户最相似的他的味道。”

“另一半是选择你想要如何对 A 元素的相似性进行排名。” - 这也是我问题的一部分。我觉得在大多数产品中评分相似的用户具有封闭的亲和性，但同时我想避免 user1 和 user2 在只有少数非常好的匹配(也许我需要一个非线性分数)。

免责声明:我从未使用过图形数据库。

我有两组数据A和B，A与零到多个B有关系。每个关系都有一个固定值。

例如

A1--5-->B10

A1--1-->B1000

所以我最初的想法是“耶，那是一个图，是时候学习图数据库了!”但在我太得意忘形之前......这样做的唯一原因是我可以回答问题......

对于每个 A，根据它们的权重找到最相似的 A 的集合，我要考虑的地方

• 权重差异(假设为 1 到 10)，因此 10 和 10 的得分高于 10 和 1；但是后来我遇到了如何处理没有配对的问题(或者我 - 我只是不确定)
• 两个集合共有的顶点数(忽略权重)。目的是将具有很多顶点的两个 A 排序为比只有一个匹配顶点的两个 A 更高的相同 B。

执行此操作的最佳方法是什么？

(补充 - 据我所知，这可能算作第二个问题):如果 A 的集合为数百万，B 为 10 万，并且我需要实时答案，那么该方法将如何改变？

Answer 1

不是一个完整的答案。我也不完全了解这项技术。但我知道这很重要。

如果将数据视为矩阵。例如让行对应于集合 A，让列对应于集合 B，条目是权重。然后它是一个带有一些缺失值的矩阵。

recommender system 中使用的一项技术(在协同过滤的范畴下)是低秩近似。

它基于这样的假设，即所述用户-产品评分矩阵通常具有低秩。粗略地说，如果多个用户的行可以表示为其他用户行的线性组合，则该矩阵具有低秩。

我希望这会成为进一步阅读的开始。

是的，您可以在 low-rank approximation wiki page 中看到该技术可用于猜测缺失的条目(缺失评分)。我知道这是一个不同但相关的问题。