python - 找到最能解释数据的树状层次结构

Question

考虑以下数据框:

      A  B  C
1    A1 B1 C1
2    A2 B2 C2
3    A3 B1 C1
4    A1 B1 C2
5    A2 B1 C1
6    A1 B4 C2

其中 A、B 和 C 表示属性。我希望推断出 A、B 和 C 之间的最有可能 层次结构。通过这个，我的意思是找到 {A,B,C} 的顺序，该顺序产生一个层次结构，该层次结构具有最少数量的节点且具有多个父节点。

例如，让我们考虑一种分层可能性:

A->B->C

我们注意到它有多个父节点。为了看到这一点，我们观察到 A1 与 B1 和 B4 在 A1 组合中同时出现B1 C1 和 A1 B4 C1。但是，A3也与 B1 在 3 行中同时出现，与 A3 B1 C1.

换句话说，只关注图的这一部分，如果我们假设层次结构A->B->C，我们将有一个节点B1两位家长:

因此，问题是，给定一个像上面那样的任意数据框，我如何才能找到产生最少数量且具有多个父节点的列的层次结构排序？

注意事项:

这个问题有更多变体，例如

1. 找到具有最少(额外)多父边的层次结构
2. 找到边总数最少的层级

解决这些变体中的任何一个都会很棒。

Answer 1

这是带有数据框的无向图。 Edge (x,y) 表示有一些数据行使得 x,y 都被提及。

例如 - 最后一行 "A1,B4,C2"添加边 (A1,B4), (B4,C2), (A1,C2)

现在可以根据您的意愿对 A、B、C 进行排序。

Finding the hierarchy with the least number of (extra) multi-parent edges

我们可以暴力破解所有排列(对于 N = 8..10 来说相当快)并找到最便宜(最小、最短)的排列。这种树(下图)中的边成本可以通过上图计算。

Mb 可能有一些贪婪的方法，比如“在当前步骤中选择最便宜的”，我现在不确定，但我很确定这种问题表示是有前瞻性的。