树的内核：量化树结构化数据之间的相似性
|
网络和图形是一种节点形式的结构化数据类型，它们之间的关系描述为链接，或边缘。图中的节点和边可能有几个属性，可能是数字或分类，甚至更复杂。 今天，大量的数据是可用的网络或图形的形式。例如，万维网，其网页和超链接，社会网络，语义网络，生物网络，科学文献的引用网络，等等。 36大数据专稿，本文由36大数据翻译组-云泥，任何不标明译者和出处以及本文链接http://www.36dsj.com/archives/43411 的均为侵权。
树是一种特殊类型的图形，很自然地适合于表示多种类型的数据。树木的分析是计算机和数据科学中的一个重要领域。在这篇文章中，我们将看看树链接结构的分析。特别是，我们将专注于树的内核，一种方法用来比较树图形彼此，使我们能够量化的测量它们的相似性或差异。这是一个重要的过程，对于很多如分类和数据分析的现代应用。
结构化数据的无监督分类分类是机器学习和数据分析的重要组成部分。在一般情况下，分类可以监督或无监督。在监督分类中，分类是已知的，一个分类模型是从训练数据中构造的。这个训练数据已经给了正确的分类。通过对比，无监督分类试图找出分类，其中没有已知的部分，分组数据分类基于一些相似性的措施。无监督分类法可以与图的理论相结合去识别相似的树网络。树数据结构用于几个域模型对象。在自然语言处理（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.
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
