algorithm - 如何表示隐式关系？

Question

我正在开发一个应用程序，我必须在其中处理名为“技能”的实体。现在的问题是“技能 A”可以与“技能 B”具有一定的相关性(相关性用于搜索目的)。同样，“技能 B”也可以与“技能 C”相关。我们目前有以下数据模型来表示这种情况

技能 {SkillId, SkillName}

RelevantSkill {SkillId, RelevantSkillId, RelevanceLevel}

现在，在上述情况下，我们在“技能 A”和“技能 C”之间建立了隐式关系。这种情况下的最佳数据模型是什么？我们还必须在执行搜索时遍历此层次结构。

Answer 1

您所要求的似乎基本上是根据一组成对距离计算的图形距离算法(斜线数据结构)。一个合理的(并且很好计算的)指标是 commute time .

可以这样想:构建一个图，其中每个节点都是一个Skill，每条边代表它所连接的节点之间的相关性。现在假设您从图中的某个节点(某些技能)开始，然后沿着定义的边随机跳到其他节点。假设从技能 A 跳到技能 B 的概率与这些技能彼此之间的相关性成正比(通过这些技能与其他技能的相关性标准化......)。现在，通勤时间表示从技能 A 到技能 C 所需的平均步数。

这有一个很好的特性，即在两个节点之间添加更多路径可以缩短通勤时间:如果技能 A 和 B、B 和 C、C 和 D、D 和 A 相关，则 A 和 B 之间的通勤时间C 会变得更短。此外，使用稀疏连接的技能图的特征值分解可以很容易地计算出通勤时间(我认为我给你的引用资料显示了这一点，但如果没有，也有很多可用的)。

如果您想实际存储任何一对 Skill 之间的通勤时间，您需要一个完全连接的图或 NxN 矩阵(N 是 Skill 的数量)。然而，一个更好的变体是，如上所述，丢弃所有弱于某个阈值的连接，然后将稀疏连接的图作为行存储在数据库中。

祝你好运，我希望这对你有所帮助!