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

考虑以下数据框:

      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 有两个父节点:

因此，问题是，给定一个像上面那样的任意数据框，我怎样才能找到产生最少节点数的列的层次顺序？
笔记:
这个问题有更多的变体，例如

找到具有最少(额外)多父边数的层次结构

找到总边数最少的层次

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

最佳答案

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

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

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



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

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

关于python - 找到解释数据的最树状层次结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26999331/