A 网络 or 图 一种类型的结构化数据的形式是 节点，它们之间的关系由链接描述，或者 边缘. 图中的节点和边可以有几个属性，这些属性可以是数值的，也可以是分类的, 或者更复杂.

今天，大量的数据以网络或图表的形式可用. 例如, 万维网, 它的网页和超链接, 社交网络, 语义网络, 生物网络, 科学文献引文网络, 等等.......

A 树 是一种特殊类型的图，自然适合表示多种类型的数据. 树的分析是计算机和数据科学的一个重要领域. 在本文中，我们将分析树中的链接结构. 特别是, 我们将关注树核, 一种比较树状图的方法, 让我们可以量化它们的相似或不同之处. 这是许多现代应用程序的重要过程，例如 分类 和 数据分析.

结构化数据的无监督分类

分类 是一个重要的组成部分 机器学习 和 数据分析. 一般来说，分类可以是 监督 or 无人管理的. 在监督分类中, 这些类别是已知的, 并根据已经给出正确类别的训练数据构建分类模型. 非监督分类, 相比之下, 尝试识别未知的类, 根据相似性的度量将数据分组为类别.

无监督分类可以与图论相结合来识别相似树网络的组. 树形数据结构用于对来自多个领域的对象进行建模. 自然语言处理(NLP), 例如, 解析树是按顺序建模的, 标签树. 在自动推理中, 许多问题都是通过搜索解决的, 其中搜索空间表示为树，其顶点与搜索状态相关联, 边表示推理步骤. 同时, 一种数据例如HTML和XML文档，可以建模为有序的标记树.

这些领域可以通过无监督分类技术进行有效的分析. 在NLP, 分类可以用来自动将一组句子分组成问句, 命令, 和声明. 同样的, 可以通过对HTML源应用分类方法来识别相似网站组. 在每种情况下，我们所需要的只是一种方法来衡量两棵树彼此之间的“相似度”.

维度的诅咒

大多数分类算法要求将数据转换为 矢量化形式，表示数据的值 特性 在 特征空间，以便在特征空间中使用线性代数对数据进行分析. 在结构化或半结构化数据中, 像树, 结果向量的维数(即, 特征空间中的特征数量可能相当高, 因为特征空间必须保留有关结构的信息.

这可能是一个重大的缺点, 考虑到许多分类技术不能有效地随输入的维数进行缩放. 换句话说, 它们的分类能力随着输入维数的增加而降低. 这个问题被称为 维度的诅咒.

要了解这种性能下降的原因，请考虑一个空间 X 的维度 d. 假设 X 包含一组均匀分布的点. 的维数 X 增加，保持相同密度所需的点的数量必须呈指数增长. 换句话说，输入的维度越多，数据越可能稀疏. 在一般情况下, 稀疏数据集不能提供足够的信息来构建一个好的分类器，因为数据元素之间的相关性太弱，算法无法检测到.

上面的每个特征空间包含8个数据点. 在一维空间上, 在左边很容易识别一组5个点, 右边有三个. 将这些点扩展到更多的特征上(例如.e. 维度)使得找到这些组变得更加困难. 在实际应用中，特征空间很容易具有数百个维度.

当有关领域的信息可以有效地用于选择一组可管理的特征时，结构化数据的向量化表示是合适的. 当没有这种资料时, 最好使用能够直接处理结构化数据的技术, 不需要在向量空间中进行运算.

内核的方法

内核的方法 避免将数据转换为矢量形式的需要. 它们需要的唯一信息是测量数据集中每对项目的相似性. 这个测量称为a 内核，确定它的函数称为 核函数. 核方法在特征空间中寻找线性关系. 功能, 它们等价于取特征空间中两个数据点的点积, 事实上，特征设计在核函数设计中仍然是一个有用的步骤. 然而, 核函数方法避免直接对特征空间进行操作，因为可以证明可以用核函数代替点积, 只要核函数是a 对称的, 半正定 函数，可以将其原始空间中的数据作为输入.

因此，使用核函数的优点是可以对巨大的特征空间进行分析，其计算复杂度不依赖于特征空间的大小, 而是基于核函数的复杂度, 这意味着核方法不会遭受维度的诅咒.

如果我们考虑一个有限数据集，由 n 例如，我们可以通过生成a来得到数据中相似度的完整表示 内核矩阵 它的大小总是 n × n. 这个矩阵与每个单独样本的大小无关. 当要分析具有大特征空间的小样本数据集时，此属性非常有用.

一般来说，核方法基于对数据表示问题的不同回答. 而不是将输入点映射到特征空间, 数据通过核矩阵中的两两比较来表示 K，所有相关的分析都可以在核矩阵上进行.

许多数据挖掘方法都可以实现内核化. 使用内核方法对树结构数据实例进行分类，例如 支持向量机定义一个有效的(对称正定的)核函数就足够了 k: T × T→ R，也被称为a 树的内核. 在设计中实际有用的树核, 一种是要求它们在树大小的多项式时间内可计算, 并且能够发现 同构图形. 这样的树核叫做 完整的 树内核.

树内核

现在，让我们引入一些有用的树核来度量树的相似性. 其主要思想是计算数据集中每对树的核，以构建核矩阵, 哪些可以用来对树进行分类.

字符串的内核

第一个, 我们将从字符串内核的简短介绍开始, 这将帮助我们介绍另一种基于将树转换为字符串的核方法.

让我们来定义 全国矿工工会y(s) 作为子字符串出现的次数 y 在一个字符串中 s, |s| 表示字符串的长度. 我们将在这里描述的字符串内核定义为:

K字符串(S1, S2) = Σs∈F 全国矿工工会s(S1全国矿工工会)s(S2)ws

在哪里 F 子字符串的集合是否同时出现在两者中 S1 和 S2，参数为 ws 用作权重参数(例如，强调重要的子字符串). 我们可以看到, 当一对字符串共享许多公共子字符串时，该内核会给它们一个更高的值.

基于将树转换为字符串的树核

我们可以使用这个字符串内核来构建一个树内核. 这个内核背后的思想是以系统的方式将两个树转换为两个字符串，并对树的结构进行编码, 然后将上面的字符串核应用于它们.

我们将这两个树转换为两个字符串，如下所示:

让 T 表示一个目标树，和 标签(ns) 节点的字符串标签 ns in T. 标签(ns) 的子树的字符串表示形式 T 扎根在 ns. 因此,如果 n根 的根节点是 T, 标签(n根) 字符串表示整个树吗 T.

接下来,我们 字符串(T) =标签(n根) 的字符串表示形式 T. 我们将以自底向上的方式递归地应用以下步骤来获得 字符串(T):

• 如果节点 ns 是一片叶子，让 标签(ns) = " [" + 标签(n .s) + “]” ( + 这是字符串连接操作符).
• 如果节点 ns 不是一片叶子又有什么 c 孩子们 n1, n2, … , nc、排序 标签(n1(n),标签2标签;标签;标签c) 在词汇顺序上获得 标签(n1*(n),标签2*标签;标签;标签c*)，让 标签(ns) = " [" + 标签(n .s) +标签(n .1*) +标签(n .2*+…+标签(n .c*) + “]”.

下图显示了这种树到字符串转换的示例. 结果是一个字符串，以“[”等开始分隔符开始，以结束分隔符结束, “]”, 每个嵌套的分隔符对对应于扎根于特定节点的子树.

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

之间的树核 T1 和 T2 通过两个字符串 S1 和 S2 现在可以表示为:

K树(T1, T2) = K字符串(字符串 (T1(T),字符串2) ) = K字符串(S1, S2) = Σs∈F 全国矿工工会s(S1全国矿工工会)s(S2)ws

在大多数应用中，权重参数变为 w|s|，根据子字符串的长度对子字符串进行加权 |s|. 典型加权方法 w|s| 是:

• 恒权(w|s| = 1)
• k-频谱加权(w|s| = 1 if |s| = k, w|s| = 0 否则)
• 指数加权(w|s| = λ|s| 在哪里 0 ≤ λ ≤ 1 是衰减速率)

要计算内核，确定所有公共子字符串就足够了 F，并计算它们出现的次数 S1 和 S2. 查找公共子字符串这一额外步骤是一个研究得很好的问题, 并且可以在 O(|S1| + |S2|),采用 后缀树 or 后缀数组. 如果我们假设最大的字母数(位), 字节, 或字符, 例如，描述节点的标签是常量, 转换后的字符串的长度为 |S1| = O(|T1|) 和 |S2| = O(|T2|). 因此，计算核函数的计算复杂度是 O(|T1| + |T2|)，它是线性的.

基于子路径的树核

上面的树内核使用水平或宽度优先的方法将树转换为字符串. 虽然这种方法非常简单, 这种转换意味着它不能以原始形式直接对树进行操作.

本节将定义一个对树中的垂直结构进行操作的树内核, 允许内核直接对树进行操作.

从根结点到其中一个叶结点的路径的一部分称为A 子路径，和 子路径集 是树中包含的所有子路径的集合:

假设我们想要定义一个树核 K(T1, T2) 两棵树之间 T1 和 T2. 通过使用子路径集，我们可以将这个树核定义为:

K(T1, T2) = Σp∈P 全国矿工工会p(T1全国矿工工会)p(T2)w|p|

在哪里 全国矿工工会p(T) 子路径的次数是多少 p 出现在树中 T, |p| 子路径中的节点数是多少 p, P 所有子路径的集合在 T1 和 T2. w|p| 权重是否与前一节中介绍的相似.

在这里，我们使用深度优先搜索给出了这个内核的一个简单实现. 虽然这个算法的运行时间是二次的, 使用后缀树或后缀数组存在更有效的算法, 或者是多键快速排序算法的扩展, 可以实现线性时间( O(|T1|日志|T2|) )平均:

Subpath_track = {}

Def generate_子路径s(path, l):
  如果l == len(path):
    如果tuple(path)不在子路径_track中:
      Subpath_track [tuple(path)] = 1
    其他:
      Subpath_track [tuple(path)] += 1
  其他:
    指数= 0
    while l+index-1 < len(path):
      如果tuple(path[index: l+index])不在子路径_track中:
        Subpath_track [tuple(path[index: l+index])] = 1
      其他:
        Subpath_track [tuple(path[index: l+index])] += 1
      索引+= 1

    generate_子路径s(路径,l + 1)


Def get_子路径s(图，根，轨道，路径):
  track[根] = True

  如果图.度(根)== 1:
    generate_子路径s(路径,1)
  其他:
    对于图中的节点.邻居(根):
      如果节点不在轨道上:
        Get_子路径s (图, node, track, path + [node，])


Def 内核_子路径(t1, t2, common_track):
  Kernel_v = 0
  对于子路径_track中的p:
    Kernel_v += common_track[t1][p]*common_track[t2][p]

  返回内核_v

在本例中，我们使用加权参数w|s| w|p| = 1. 这给了所有子路径相同的权重. 但是，在使用的时候有很多情况 k-频谱加权，或一些动态分配的权重值，是适当的.

矿业网站

在我们结束之前, 让我们简单看一下树分类的一个实际应用:网站分类. 在许多数据挖掘环境中，知道一些数据来自什么“类型”的网站是有益的. 事实证明，由于类似服务的网页结构相似，来自不同网站的页面可以使用树状结构进行相当有效的分类.

我们怎么做呢? HTML文档具有逻辑嵌套结构，非常类似于树. 每个文档包含一个根元素，其中嵌套了其他元素. HTML标签中的嵌套元素在逻辑上等同于该标签的子节点:

让我们来看一些可以将HTML文档转换为树的代码:

def html_to_dom_树(根):
  Node_id = 1
  Q = deque()
  图= nx.图()

  q.Appendleft ({'element': 根， "根_id": node_id})
  虽然len(问):
    节点= q.pop ()

    如果节点和节点['element'].Name == "body":
      图.add_node (node_id元素=节点(“元素”).名称)
      Node_id += 1

    Root_id = node[' Root_id ']
    标签[根_id] = node['element'].名字

    对于节点['element']中的t.内容:
      如果t和t.名称:
        图.add_node (node_id元素= t.名称)
        图.add_edge (根_id node_id)
        q.Appendleft ({"element": t， "根_id": node_id})
        Node_id += 1

  返回图

这将产生一个树数据结构，看起来像这样:

上面的实现使用了几个有用的Python库: NetworkX，用于处理复杂的图结构，以及 美丽的汤，用于从网络中提取数据和操作文档.

调用 html_to_dom_树(汤.找到(“身体”)) 将返回一个NetworkX图形对象，根在 网页元素.

假设我们想要在一组1000个网站主页中找到组. 通过将每个主页转换成这样的树, 我们可以进行比较, 例如，通过使用前一节给出的子路径树内核. 通过这些相似性的测量, 我们可以找到, 例如, 电子商务网站, 新闻网站, 博客, 教育网站很容易通过彼此的相似性来识别.

结论

在本文中, 我们介绍了比较树结构数据元素的方法, 并展示了如何将核方法应用于树，以获得它们相似度的可量化度量. 当在高维空间中操作时，核方法已被证明是一个很好的选择, 使用树形结构时的常见情况. 这些技术为进一步分析大量树木奠定了基础, 使用经过充分研究的方法对核矩阵进行操作.

树形结构在许多实际领域(如XML和HTML文档)都会遇到, 化合物, 自然语言处理, 或者特定类型的用户行为. 如从HTML构造树的示例所示, 这些技术使我们能够在这些领域中执行有意义的分析.