聚类树结构化数据

Question

假设我们以半结构化格式给出数据作为树.例如,树可以形成为有效的XML文档或有效的JSON文档.你能想象它是一个口齿不清状S-表达或(G)的代数数据类型在Haskell或者Ocaml.

我们在树结构中给出了大量的"文档".我们的目标是聚类相似的文档.通过聚类,我们指的是将文档划分为j个组的方法,使得每个元素中的元素看起来彼此相似.

我确信有些论文描述了方法,但由于我在AI/Clustering/MachineLearning领域并不为人所知,我想问一下谁在寻找什么以及在哪里挖掘.

我目前的做法是这样的:

• 我想将每个文档转换为为K-means聚类设置的N维向量.
• 为此,我递归地遍历文档树,并为每个级别计算一个向量.如果我在树顶点,我会重复所有的subvertices,然后将它们的向量相加.此外,每当我再次出现时,都会应用一个功率因数,因此它越往往越不重要.文档最终向量是树的根.
• 根据树叶上的数据,我应用一个将数据转换为向量的函数.

但肯定有更好的方法.我的方法的一个弱点是它只会相似 - 聚类具有顶部结构的树木彼此非常相似.如果相似性存在,但发生在树的更远处,那么我的方法可能不会很好地工作.

我想也有全文搜索的解决方案,但我确实想利用数据中存在的半结构.

距离功能

如建议的那样,需要在文档之间定义距离函数.如果没有此功能,我们就无法应用聚类算法.

实际上,问题可能在于该距离函数及其示例.我希望文档中根目录附近的元素相同,以便彼此靠近聚类.我们去的树越往下越重要.

采取一步退一步的观点:

我想从程序中聚集堆栈跟踪.这些是格式良好的树结构,其中靠近根的函数是失败的内部函数.我需要在堆栈跟踪之间有一个合适的距离函数,这可能是因为代码中发生了同样的事件.

Answer 1

考虑到您的问题的性质（堆栈跟踪），我会将其简化为字符串匹配问题。将堆栈跟踪表示为树会产生一些开销：对于堆栈跟踪中的每个元素，您只有一个父元素。

如果字符串匹配确实更适合您的问题，您可以运行数据，将每个节点映射到哈希上，并为每个“文档”创建其 n 元语法。

例子：

映射：

• 异常 A -> 0
• 例外 B -> 1
• 异常 C -> 2
• 异常 D -> 3

文档 A：0-1-2 文档 B：1-2-3

文档 A 的 2 克：X0, 01, 12, 2X

文档 B 为 2 克：X1、12、23、3X

使用 n 元语法，您将能够对相似的事件序列进行聚类，而不管根节点如何（在此示例中为事件 12）

但是，如果您仍然确信需要树而不是字符串，则必须考虑以下事项：查找树的相似性要复杂得多。您将希望找到相似的子树，其中在更大深度上相似的子树会产生更好的相似性得分。为此，您需要发现闭合子树（作为扩展它的树的基础子树的子树）。您不想要的是包含非常罕见的子树的数据集合，或者包含您正在处理的每个文档中的子树（如果您不查找频繁模式，您将获得这些子树）。

以下是一些提示：

• http://portal.acm.org/itation.cfm?id=1227182
• http://www.springerlink.com/content/yu0bajqnn4cvh9w9/

一旦有了频繁子树，您就可以像使用 n-gram 进行聚类一样使用它们。