我有一个数据集（> 5000）。每个单独的数据记录都构造为多级 n 叉树（>200 个节点）。树节点标识符在树中是唯一的。但是相同的标识符用于表示整个数据集的相同类型的节点。我想根据记录之间的相似性将数据集分组为多个集群。记录通常具有相似的结构，除了一些记录修剪了一些分支。
这里有一些过于简化的例子。
basic type:
A - B - C
\- D - E - F
\- G - H - I
\- J
sample 1:
A
\- D - E - F
\- G - H - I
\- J
sample 2:
A - B - C
\- G - H - I
\- J
sample 3:
A - B - C
\- D - E - F
\- G - H - I
我不知道数据集中有多少种不同类型的树结构。估计10-30左右吧。这就是为什么我想通过对数据集进行聚类来更好地理解数据集。我想要“集群”，因为我想允许集群中的小变化，以便我可以拥有可控数量的集群用于分析目的。
任何想法？谢谢
由于这些树都是某些通用树的子树（在有根的意义上），因此您可以像对称差异的大小一样简单。
如果你的树可以有非常不同的大小，那么与小树相比，在测量大树的相似性时更加宽松可能是有益的；在这种情况下，Jaccard 距离可能会很好地工作。
最后，您可能想要更多地关心实际的树结构。考虑：
basic type:
A - B - C
\- D - E - F
\- G - H - I
\- J
sample 2:
A - B - C
\- G - H - I
\- J
sample 4:
A - B
\- D - E
\- G - H
\- J
样本 2 和 4 都从基本类型中丢失了 3 个节点，因此根据我的前两个指标中的任何一个，与它的距离相同。但是对于您的用例，可能失去整个分支与失去三片叶子或多或少不同。您可以按与根的距离或任何其他事物的距离加权，以适应这些差异；如果您的聚类算法需要一个严格的度量，您的权重仍然满足公理，请小心。
您必须将数据转换为图表。有像Networkx这样的工具可以创建图形，您可以使用karateclub 库中的函数对其进行分类，例如graph2vec。
要将数据转换为图形，您需要解析数据结构以适应 networkx 之一。
import networkx as nx
G = nx.Graph()
然后进行一个循环，按照其层次结构添加节点或边来获取数据：
G.add_node(1)
G.add_edge(1, 2)
另一个想法是使用适合于Tucker_decomposition或PARAFAC Decomposition等三维数据的矩阵分解以及大量其他基于深度学习的架构。
基本上每个网络/树都可以看作是一个NxN二进制矩阵，其中 N 是节点的数量，而节点i连接到 nodej的位置x_ij将为 1。如果您的网络具有方向性，您也可以考虑 +1 与 -1。第三个维度是您的样本。假设你有M样本，你最终会得到一个 3d 张量NxNxM。
根据您的样本，可以决定哪种算法更合适。如果是时间（所以有跨 M 维的关系或其他一些结构差异）