假设我们拥有以半结构化格式呈现的树状数据。 例如，这棵树可以是一个有效的 XML 文档或一个有效的 JSON 文档。 你可以想象它是一个类似于 Lisp 的 S 表达式，或者 Haskell 或 Ocaml 中的（G）代数数据类型。
我们有大量的树状结构的“文档”。 我们的目标是对相似的文档进行聚类。 聚类是指将文档分成 j 组，使得每组中的元素看起来彼此相似。
我相信一定有一些论文描述了相关方法，但由于我对 AI/聚类/机器学习领域不是很了解，我想向了解这些领域的人请教，应该查找什么，在哪里挖掘。
我目前的方法如下：
- 我想将每个文档转换为 N 维向量，以便进行 K-means 聚类。
- 为此，我递归地遍历文档树，并在每个级别计算一个向量。 如果我位于树的顶点，则我对所有子顶点进行递归，然后将它们的向量相加。 此外，每次递归时，都会应用一个功率因子，因此树越往下，影响就越小。 文档的最终向量是树的根。
- 根据树叶上的数据，我应用一个函数将数据转换为向量。
但肯定有更好的方法。 我的方法的一个弱点是它只能对具有非常相似的顶部结构的树进行相似性聚类。 如果相似性存在，但出现在树的更深处，那么我的方法可能效果不佳。
我想象在全文搜索中也有解决方案，但我确实想利用数据中存在的半结构化特性。
距离函数
正如建议的那样，需要定义文档之间的距离函数。 没有这个函数，我们就无法应用聚类算法。
事实上，问题可能就在于这个距离函数及其示例。 我希望根附近元素相同的文档能聚类得更近。 树越往下，影响就越小。
后退一步的视角：
我想对程序的堆栈跟踪进行聚类。 这些是结构良好的树结构，其中接近根的函数是失败的内部函数。 我需要一个合理的堆栈跟踪之间的距离函数，这些堆栈跟踪可能是因为代码中发生了相同的事件而产生的。
回答：
鉴于您的问题的性质（堆栈跟踪），我会将其简化为字符串匹配问题。 将堆栈跟踪表示为树有点多余：对于堆栈跟踪中的每个元素，您都只有一个父级。
如果字符串匹配确实更适合您的问题，您可以运行数据，将每个节点映射到哈希，并为每个“文档”创建其 n-gram。
例子：
映射：
- 异常 A -> 0
- 异常 B -> 1
- 异常 C -> 2
- 异常 D -> 3
文档 A：0-1-2 文档 B：1-2-3
文档 A 的 2-gram：X0, 01, 12, 2X
文档 B 的 2-gram：X1, 12, 23, 3X
使用 n-gram，您将能够对类似的事件序列进行聚类，而与根节点无关（在本例中为事件 12）
但是，如果您仍然确信您需要树而不是字符串，则必须考虑以下几点：查找树的相似性要复杂得多。 您将要查找相似的子树，深度上更相似的子树会导致更好的相似性得分。 为此，您需要发现闭合子树（作为扩展它的树的基本子树的子树）。 你不想要的是一个包含非常罕见的子树，或者存在于你正在处理的每个文档中的数据集合（如果你不寻找频繁模式，你会得到这个）。
这里有一些提示：
一旦你有了你的频繁子树，你可以像使用 n-gram 一样使用它们进行聚类。
