聚类树结构数据

Question

假设数据以半结构化的格式作为树提供给我们。例如，树可以形成为有效的XML文档或有效的JSON文档。你可以想象它是一个类似lisp的S-表达式，或者是Haskell或Ocaml中的(G)代数数据类型。

我们在树结构中得到了大量的“文档”。我们的目标是对类似的文档进行聚类。通过聚类，我们意味着将文档划分为j组的一种方法，这样每个文档中的元素看起来都是彼此相似的。

我确信有一些论文描述了方法，但是由于我在人工智能/聚类/机器学习领域并不是很熟悉，我想问一个人，谁是寻找什么，在哪里挖掘。

我目前的做法如下：

• 我想把每个文档转换成为K均值聚类而设置的N维向量。
• 为此，我递归地遍历文档树，并为每个级别计算一个向量。如果我在一个树的顶点，我重复所有的颠覆点，然后求和他们的向量。而且，每当我再次出现时，一个功率因数就会被应用，所以我走得越远，它的重要性就越小。文档的最终向量是树的根。
• 根据树叶上的数据，我应用了一个函数，它将数据输入到向量中。

但毫无疑问，有更好的方法。我的方法的一个缺点是，它只会有相似的聚类树，它的顶部结构非常相似。如果相似性存在，但在树下发生，那么我的方法可能不会很好地工作。

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

距离函数

正如建议的那样，需要定义文档之间的距离函数。没有这个函数，我们就不能应用聚类算法。

事实上，这个问题可能是关于这个距离函数及其例子。我希望文档中根目录附近的元素是相同的，以便彼此紧密地聚在一起。我们走得越远，关系就越小。

退一步的观点：

我想从程序中聚集堆栈跟踪。这些是结构良好的树结构，其中靠近根的函数是失败的内部函数。我需要一个很好的堆栈跟踪之间的距离函数，这可能是因为相同的事件发生在代码中。

Answer 1

考虑到问题的本质(堆栈跟踪)，我会将其简化为字符串匹配问题。将堆栈跟踪表示为树有一定的开销:对于堆栈跟踪中的每个元素，只有一个父元素。

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

示例：

制图：

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

医生A: 0-1-2 B: 1-2-3

2克A医生: X0，01，12，2X

2克B医生: X1，12，23，3X

使用n-gram，您将能够对类似的事件序列进行聚类，而不管根节点(在本例中为事件12)。

但是，如果您仍然确信需要树，而不是字符串，则必须考虑以下几点:为树寻找相似点要复杂得多。你会想要找到相似的子树，在更大的深度上相似的子树会得到更好的相似性分数。为此，您需要发现封闭子树(子树是扩展它的树的基本子树)。您不想要的是包含非常罕见的子树的数据集合，或者您正在处理的每个文档中都存在的子树(如果不查找频繁的模式，您将得到这些子树)。

以下是一些提示：

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

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

Answer 2

这里你可能会发现一篇似乎与你的问题密切相关的论文。

从摘要来看：

This thesis presents Ixor, a system which collects, stores, and analyzes stack traces in distributed Java systems. When combined with third-party clustering software and adaptive cluster filtering, unusual executions can be identified.