基于web数据抽取有几种方法优缺点是什么?
发布网友
发布时间：2022-04-23 08:25
共2个回答
懂视网
时间：2022-05-13 17:55
网络和图形是一种节点形式的结构化数据类型，它们之间的关系描述为链接，或边缘。图中的节点和边可能有几个属性，可能是数字或分类，甚至更复杂。
今天，大量的数据是可用的网络或图形的形式。例如，万维网，其网页和超链接，社会网络，语义网络，生物网络，科学文献的引用网络，等等。
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.
热心网友
时间：2022-05-13 15:03
自然语言处理是计算机科学领域与人工智能领域中的一个重要方向。它研究能实现人与
计算机之间用自然语言进行有效通信的各种理论和方法。基于自然语言处理的方法在一定程
度上借鉴了自然语言处理技术，利用子句结构、短语和子句之间的关系，建立基于语法和语
义的抽取规则来实现信息抽取。目前采用这种原理的典型系统有RAPIER[3], WHISK [2]。下
面介绍比较有代表性的WHISK 系统。
WHISK 系统既适用于结构化、半结构化的文本也适用于自由文本。该系统并不需要提
前进行语法分析，它的规则不仅由文本中的一个短语或一系列与某领域相关的短语学习而得
到，还可以由这些短语的约束学习得到。为了尽可能加入人的参与，该系统同时学习和标记
训练数据，而不是随机取实例进行手工标记。系统使用语法分析器和语义类（如人名、机构
名）分析器，分析出用户标记信息的语法成分和对应的语义类，生成基于语法标记和语义类
标记的抽取规则，实现信息抽取。
这种方法的缺点是：没有很好的利用HTML 文档的层次结构；需要大量的人为参与的
工作，很难实现自动的抽取；只支持记录型的语义模式结构，不支持复杂对象的抽取。所以
此方法适用范围较窄。
2 基于HTML 文档结构的Web 信息抽取
这类Web 信息抽取技术的特点是依赖于HTML 文档的内部结构特征。在信息抽取之前，
将HTML 文档解析成能够体现该文档标签层次关系的语法树，通过自动或者半自动的方式
产生抽取规则，将信息抽取转化为对语法树的操作实现信息抽取。采用该类介绍的典型系统
有LIXTO[5]、W4F[6]和DataRover[4]等。
DataRover 利用启发规则发现分类片段中的结构规律。然后利用这些规律将在线目录转
换到数据库中的分类产品。该系统使用了一个页面分割算法将Web 页解析的DOM（文档对
象模型）树作为输入通过该算法找到其中的逻辑段。该系统的不足之处在于：这个方法依赖
于HTML 页解析的DOM树，由于大部分的HTML 页是非良好结构的，所以解析产生的DOM
树也不完全正确；另外，此系统只适用于那些包含明确分类的领域，使用范围比较窄。
LIXTO 可以生成包装器来将HTML 页转换成XML[13]（可扩展标识语言）文档。允许用
户以可视化、交互式的方式对样本页面中的信息进行标记，系统通过记录用户标记的信息生
成信息抽取规则，实现对相似结构网页的信息抽取。它的不足之处是它的抽取规则使用基于
Datalog 的Elog 语言描述的，实现和优化校困难，另外抽取规则中抽取信息的描述不够丰富，
不支持图像信息和文献信息的处理。
