树的内核：量化树结构化数据之间的相似性

一个深入的树内核的信息概述，无论是理论还是实践。包括一个案例和一些代码后的讨论。

网络和图形是一种节点形式的结构化数据类型，它们之间的关系描述为链接，或边缘。图中的节点和边可能有几个属性，可能是数字或分类，甚至更复杂。

今天，大量的数据是可用的网络或图形的形式。例如，万维网，其网页和超链接，社会网络，语义网络，生物网络，科学文献的引用网络，等等。

36大数据专稿，本文由36大数据翻译组-云泥，任何不标明译者和出处以及本文链接http://www.36dsj.com/archives/43411 的均为侵权。

数（数据结构名词）

树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树；

树是一种特殊类型的图形，很自然地适合于表示多种类型的数据。树木的分析是计算机和数据科学中的一个重要领域。在这篇文章中，我们将看看树链接结构的分析。特别是，我们将专注于树的内核，一种方法用来比较树图形彼此，使我们能够量化的测量它们的相似性或差异。这是一个重要的过程，对于很多如分类和数据分析的现代应用。

结构化数据的无监督分类

分类是机器学习和数据分析的重要组成部分。在一般情况下，分类可以监督或无监督。在监督分类中，分类是已知的，一个分类模型是从训练数据中构造的。这个训练数据已经给了正确的分类。通过对比，无监督分类试图找出分类，其中没有已知的部分，分组数据分类基于一些相似性的措施。无监督分类法可以与图的理论相结合去识别相似的树网络。树数据结构用于几个域模型对象。在自然语言处理（NLP），例如，解析树被建模为有序，标记树。在自动推理，许多问题都被搜索解决了，搜索空间被代表为一棵树，其顶点与搜索状态，和边缘代表的推理步骤。另外，半结构化数据，如HTML和XML文档，可以模拟为有序，标记的树。

这些领域可以通过非监督分类技术进行有效的分析。在自然语言处理（NLP），分类可以用来自动将一组句子分成问题，命令和语句。同样的，相似网站群可以通过HTML源识别分类方法识别。在每一种情况下，我们所需要的是一种衡量”相似”的两个树是彼此的方法。

维数灾难

大多数分类算法需要将数据转化成矢量形式，表示在特征空间中的数据的特征值，使数据可以在特征空间利用线性代数分析。在结构化或半结构化数据，如树木，所得到的向量维数（即特征空间中的特征数）可能会很高，由于特征空间必须保留结构信息。

这可能是一个显著的缺点，考虑到许多分类技术是不能够有效地扩展维度输入。换句话说，它们的分类能力随着输入维数的增加而降低。这个问题被称为”维数灾难”。

要想知道这个性能下降的原因，考虑维度D的一个空间X。假设X包含一组均匀分布的点。如果X的维度数量增加，必要的保持相同密度的点的数量必须成倍的增加。换句话说，输入的维数越大，数据稀疏的可能性越大。一般情况下，稀疏的数据集并没有给出足够的信息，以建立一个良好的分类，因为对于检测算法数据元素之间的相关性太弱。

维数灾难

每个特征空间上面都包含了八个数据点。在一维空间上，很容易辨认出左边一组5个点，和右边一组3个点。在更高功能上（例如，维度）伸展这些点使它更难找到这些组。在实际应用中，特征空间可以很容易地拥有数百个维度。

一个结构化的数据矢量化是合适的，当有关该域的信息可以有效地用于选择一个可管理的功能集时。当这些信息不可用时，它是可以用使用的技术直接处理结构化数据，不需要执行在向量空间中的操作。

核方法

核方法避免了将数据转换成矢量形式的需要。它们所需要的唯一信息是一个集合数据中的每一对的相似性的度量。这种度量被称为内核，并确定它的函数称为内核函数。特征空间中的核方法寻找线性关系。在功能上，它们相当于特征空间中的点积的2个数据点，而真正的功能设计，在内核功能设计可能仍然是一个有用的步骤。然而，内核方法避免直接操作在特征空间，因为它可以表明以取代点产品的内核功能是可能的，只要核函数是对称的，正定函数可以作为输入的原始空间数据。

使用内涵函数的优点是，一个巨大的特征空间，可以分析与计算复杂度不依赖于特征空间的大小，但是内核功能的复杂性，这意味着内核的方法是没有灾难的维数。

如果我们考虑一个有限的数据集组成的氮的例子，我们可以得到一个通过生成一个内核矩阵，完整的在数据中的相似性表示，其大小始终是nxn。在每个个性化的例子，这个矩阵是独立的大小。此属性是有用的，当一个小的数据集的例子有一个大的特征空间进行分析。
在一般情况下，内核的方法是基于对数据问题的不同答案。而不是映射到特征空间的输入点，数据表示通过成对比较的内核矩阵，和所有相关的分析可以进行内在矩阵。

许多数据挖掘方法都可以核化。分类树结构的数据情况下用内核的方法，如，支持向量机器，它可以定义一个有效（正定）核函数K：T×T→R，也被称为树核。在设计切实有用的树的内核，一个将需要它们是可计算在多项式时间内的树的大小，并能够检测同结构图。这种树的内核被称为完全树核。

树核

现在，让我们来介绍一些有用的树核，用于测量树的相似性。其主要思想是计算每一对树的内核，以便建立一个内核矩阵，然后可用于分类组的树。

字符串内核

首先，我们就爱你过要开始一个简短的介绍字符串的内核，这将有助于我们引入另一个内核的方法，是基于转换成字符串树。

让我们来定义numy（S）为一个字符串中的子串出现的次数与Y，|s|表示字符串的长度。我们将在这里描述的字符串内核被定义为：

其中F是在S1和S2出现的子字符串的集合，参数作为一个权重参数（如，强调重要的子字符串）。我们可以看到，这个内核对他们有许多共同的子字符串时提供了更高的价值。

基于树转换成字符串的树核

我们可以使用这个字符串内核来构建一个树内核。这个内核背后的想法是，将两根树转换成2个字符串，用系统的方法将树的结构编码，然后将上面的字符串内核应用到它们中。

我们将两根树转换成两根弦：

让T表示一个目标树和标签（NS）在T标签节点。NS字符串标签（NS）是指T扎根在NS的子树的字符串表示。所以如果是T的根节点，tag（nroot）是整个树T的字符串的表现形式。

接下来，让字符串（t）=tag（nroot）表示T的字符串。我们将递归地应用下面的步骤，在一个自下而上的方式获得字符串（T）：

如果节点NS是一个叶状结构，让tag(ns) = “[” + label(ns) + “]”（在这里+是字符串串联运算符）。

如果节点NS不是叶状结构，并且有C子n1, n2, … , nc, sort tag(n1), tag(n2), … , tag(nc)在词汇以获得tag(n1*), tag(n2*), … , tag(nc*), 让let tag(ns) = “[” + label(ns) + tag(n1*) + tag(n2*) + … + tag(nc*) + “]”。

下面的图，显示了这课树对字符串转换的一个例子。其结果是一个字符串的起始开口分隔符如”[“和结束的结束一样，”]”,每一个嵌套的双对应子树扎根在一个特定的节点的分隔符。

现在我们可以应用上述转换的两颗树，T1和T2，获得两个字符串S1和S2.从那里，我们可以简单地应用上面描述的字符串内核。

树核的T1和T2之间通过两个字符串S1和S2可以给予如下：

基于子路径的树核

上面的树核使用了一个水平的，或者第一个宽度将树转换成字符串的方法。虽然这种方法很简单，但这种转换意味着它不能直接在其原始形式的树上操作。

本节将定义一个在树上操作的树内核，允许内核在树上直接操作。

一款一条路径从根到众多叶子之一的子路径集，包含在树所有子路径的设置：

让我们假设我们要定义一个树核函数K（T1,T2）两树之间的T1和T2.利用子路径集，我们可以定义这棵树的内核：

在数量（T）是子路径P数发生在树T，P是P子节点的数目，和P是在T1和T2的所有子路径的设置。W | P |是权重，类似于前一节介绍。

这里，我们提出了一个简单的实现这一内核使用的深度有限搜索。虽然该算法那运行在二次时间，更有效的算法存在使用后缀树和后缀数组，或延伸的多条快速排序算法，可以平均实现线性时间

（O(|T1|log|T2|)）

在这个例子中，我们使用的加权参数w|s| w|p| = 1。这给所有的子路径并重。然而，在许多情况下使用K谱线的权重时，或一些动态分配的权重值，是适当的。

深挖网站

在我们结束之前，让我们简要地看一个真实的树分类：分类网站。在许多数据挖掘的背景下，它是有益的，知道什么”类型”来自哪些数据网站。它从不同的网站的网页上可以相当有效低分类使用树，因为相似的网页相似的服务是结构化的。

我们怎么做？HTML文档的逻辑嵌套结构，它很像一棵树。每一个文档包含一个根元素，里面包含了其他元素嵌套。元素嵌套在HTML标签在逻辑上相当于这个标签的子节点。

让我们看一些代码，可以将一个HTML文档放到树上看：

这将产生一个树的数据结构，可能看起来像这样的：

实际上述利用几个有用的Python库：networkx，对复杂的图形结构把数据从网络上取下和操作文件。

我们要在1000个网站的主页上找到组。通过将每个网页变成这样的一棵树，我们可以相互比较，例如通过使用上一节给出的路径树核。通过这些测量的相似性我们可以发现，例如，电子商务网站，新闻网站，博客和教育网站是很容易确定他们的相似性的。

结论

在这篇文章中，我们介绍了树结构数据元素的比较，并显示了如何应用内核的方法，以获得一个可量化的测量他们的相似性。内核的方法已被证明是一个很好的选择时，在高维空间中一个共同情况下，与树结构的工作。这些技术为进一步分析大套树木，使用以及研究的方法，操作过的内核矩阵阶段。

树结构在现实世界中许多领域如XML和HTML文件，遇到化学化合物，自然语言处理，或某些类型的用户行为。作为从HTML构建树的例子证明，这些技术使我们能够在这些领域进行有意义的分析。

原文地址：Tree Kernels: Quantifying Similarity Among Tree-Structured Data

End.

转载请注明来自36大数据（36dsj.com)：36大数据 » 树的内核：量化树结构化数据之间的相似性