>웹 프론트엔드 >HTML 튜토리얼 >树的内核:量化树结构化数据之间的相似性_html/css_WEB-ITnose

树的内核:量化树结构化数据之间的相似性_html/css_WEB-ITnose

WBOY
WBOY원래의
2016-06-24 11:24:211514검색

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

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

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

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.

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.