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

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

如今，大量数据以网络或图表的形式提供。 例如，万维网及其网页和超链接、社交网络、语义网络、生物网络、科学文献的引用网络等等。

树是一种特殊类型的图，自然适合表示多种类型的数据。 树木分析是计算机和数据科学中的一个重要领域。 在本文中，我们将着眼于树中链接结构的分析。 特别是，我们将关注树核，这是一种将树图相互比较的方法，使我们能够对它们的相似性或差异进行量化测量。 这是许多现代应用程序（例如分类和数据分析）的重要过程。

结构化数据的无监督分类

分类是机器学习和数据分析的重要组成部分。 一般来说，分类可以是有监督的，也可以是无监督的。 在监督分类中，类别是已知的，并且分类模型是根据已经给出正确类别的训练数据构建的。 相比之下，无监督分类试图识别未知的类别，根据某种相似性度量将数据分组。

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

这些领域可以通过无监督分类技术进行有用的分析。 在 NLP 中，分类可用于自动将一组句子分组为问题、命令和语句。 同样，可以通过将分类方法应用于其 HTML 源来识别相似网站组。 在每种情况下，我们所需要的只是一种衡量两棵树彼此“相似”程度的方法。

维度的诅咒

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

考虑到许多分类技术无法根据输入的维度有效地扩展，这可能是一个重大缺陷。 换句话说，它们的分类能力随着输入维度的增加而降低。 这个问题被称为维度灾难。

要了解这种性能下降的原因，请考虑维度为d的空间X。 假设X包含一组均匀分布的点。 如果X的维数增加，则保持相同密度所需的点数必须呈指数增加。 换句话说，输入的维度越多，该数据就越有可能是稀疏的。 通常，稀疏数据集无法提供足够的信息来构建良好的分类器，因为数据元素之间的相关性太弱以至于算法无法检测到。

上面的每个特征空间都包含八个数据点。 在一维空间上，很容易识别出一组左边五个点，右边三个点。 将这些点扩展到更多数量的特征（即维度）上会使找到这些组变得更加困难。 在实际应用中，特征空间很容易拥有数百个维度。

当有关域的信息可以有效地用于选择一组可管理的特征时，结构化数据的矢量化表示是合适的。 当此类信息不可用时，最好使用可以直接处理结构化数据的技术，而无需在向量空间中执行操作。

内核方法

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

因此，使用核函数的优点是可以分析巨大的特征空间，计算复杂度不取决于特征空间的大小，而是取决于核函数的复杂度，这意味着核方法不会受到诅咒的维度。

如果我们考虑一个由n 个示例组成的有限数据集，我们可以通过生成一个大小始终为n × n的核矩阵来获得数据内相似性的完整表示。 该矩阵与每个单独示例的大小无关。 当要分析具有大特征空间的小样本数据集时，此属性很有用。

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

许多数据挖掘方法可以被内核化。 要使用核方法（例如使用支持向量机）对树结构数据实例进行分类，只需定义一个有效（对称正定）核函数k : T × T → R ，也称为树核。 在实际有用的树核的设计中，人们会要求它们在树的大小上在多项式时间内是可计算的，并且能够检测同构图。 这样的树核称为完整树核。

树核

现在，让我们介绍一些有用的树核来测量树的相似性。 主要思想是为数据集中的每对树计算核，以构建核矩阵，然后可以将其用于对树集进行分类。

字符串内核

首先，我们将从对字符串内核的简短介绍开始，这将有助于我们介绍另一种基于将树转换为字符串的内核方法。

让我们将num y (s)定义为字符串s中子字符串y的出现次数，其中| 小号| 表示字符串的长度。 我们将在这里描述的字符串内核定义为：

K串(S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 )w s

其中F是同时出现在S 1和S 2中的子串集合，参数w s用作权重参数（例如，强调重要的子串）。 正如我们所看到的，当一对字符串共享许多公共子字符串时，该内核赋予它们更高的值。

基于树转字符串的树核

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

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

令T表示目标树之一， label(n s )表示T中节点n s的字符串标签。 tag(n s )表示以n s为根的T的子树的字符串表示。 因此，如果n root是T的根节点，则tag(n root )是整个树T的字符串表示形式。

接下来，让string(T) = tag(n root )表示T的字符串表示。 我们将以自下而上的方式递归地应用以下步骤来获得string(T) ：

• 如果节点n s是叶节点，让tag(n s ) = “[” + label(n s ) + “]” （这里的+是字符串连接运算符）。
• 如果节点n s不是叶节点并且有c个子节点 n 1 , n 2 , ... , n c , 对tag(n 1 ), tag(n 2 ), ... , tag(n c )进行词法排序以获得tag (n 1* ), tag(n 2* ), ... , tag(n c* )和 let tag(n s ) = “[” + label(n s ) + tag(n 1* ) + tag(n 2* ) + ... + 标签(n c* ) + “]” 。

下图显示了这种树到字符串转换的示例。 结果是一个以“[”之类的开始分隔符开头并以“]”结尾的字符串，每个嵌套的分隔符对对应于以特定节点为根的子树。

现在我们可以将上述转换应用于两棵树T 1和T 2 ，以获得两个字符串S 1和S 2 。 从那里，我们可以简单地应用上面描述的字符串内核。

通过两个字符串S 1和S 2在T 1和T 2之间的树内核现在可以给出为：

K tree (T 1 , T 2 ) = K string ( string(T 1 ), string(T 2 ) ) = K string (S 1 , S 2 ) = Σ s∈F num s (S 1 )num s (S 2 ) w

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

• 恒权重（ w | s | = 1 ）
• k -频谱加权（ w | s | = 1 if | s | = k ， w | s | = 0否则）
• 指数加权（ w | s | = λ | s |其中0 ≤ λ ≤ 1是衰减率）

要计算内核，确定所有公共子串F并计算它们在S 1和S 2中出现的次数就足够了。 这个寻找公共子串的额外步骤是一个经过充分研究的问题，可以在O( | S 1 | + | S 2 | )中完成，使用后缀树或后缀数组。 如果我们假设描述节点标签所需的最大字母数（例如位、字节或字符）是恒定的，则转换后的字符串的长度为| S 1 | = O( | T 1 | )和| S 2 | = O( | T 2 | ) 。 因此，计算核函数的计算复杂度为O( | T 1 | + | T 2 | ) ，是线性的。

基于子路径的树内核

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

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

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

假设我们要在两棵树T 1和T 2之间定义一个树核K(T 1 , T 2 ) 。 通过使用子路径集，我们可以将此树内核定义为：

K(T 1 , T 2 ) = Σ p∈P num p (T 1 )num p (T 2 )w | p |

其中num p (T)是子路径p在树T中出现的次数， | p | 是子路径p中的节点数， P是T 1和T 2中所有子路径的集合。 w | p | 是权重，与上一节介绍的类似。

在这里，我们展示了一个使用深度优先搜索的内核的简单实现。 尽管该算法以二次时间运行，但使用后缀树或后缀数组或多键快速排序算法的扩展存在更有效的算法，平均可以达到线性时间（ O( | T 1 | log | T 2 | ) ）：

 subpath_track = {} def generate_subpaths(path, l): if l == len(path): if tuple(path) not in subpath_track: subpath_track[tuple(path)] = 1 else: subpath_track[tuple(path)] += 1 else: index = 0 while l+index-1 < len(path): if tuple(path[index: l+index]) not in subpath_track: subpath_track[tuple(path[index: l+index])] = 1 else: subpath_track[tuple(path[index: l+index])] += 1 index += 1 generate_subpaths(path, l+1) def get_subpaths(graph, root, track, path): track[root] = True if graph.degree(root) == 1: generate_subpaths(path, 1) else: for node in graph.neighbors(root): if node not in track: get_subpaths(graph, node, track, path + [node, ]) def kernel_subpath(t1, t2, common_track): kernel_v = 0 for p in subpath_track: kernel_v += common_track[t1][p]*common_track[t2][p] return kernel_v

在这个例子中，我们使用了加权参数 w | 小号| w | p | = 1 。 这使所有子路径具有相同的权重。 但是，在许多情况下，使用k谱加权或某些动态分配的权重值是合适的。

挖矿网站

在结束之前，让我们简要地看一下树分类的一个实际应用：网站分类。 在许多数据挖掘环境中，了解某些数据来自什么“类型”网站是有益的。 事实证明，由于类似服务的网页结构相似，因此可以使用树非常有效地对来自不同网站的页面进行分类。

我们如何做到这一点？ HTML 文档有一个逻辑嵌套结构，它非常像一棵树。 每个文档包含一个根元素，其中嵌套了其他元素。 HTML 标签中的嵌套元素在逻辑上等同于该标签的子节点：

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

 def html_to_dom_tree(root): node_id = 1 q = deque() graph = nx.Graph() q.appendleft({'element': root, "root_id": node_id}) while len(q): node = q.pop() if node and node['element'].name == "body": graph.add_node(node_id, element=node['element'].name) node_id += 1 root_id = node['root_id'] labels[root_id] = node['element'].name for t in node['element'].contents: if t and t.name: graph.add_node(node_id, element=t.name) graph.add_edge(root_id, node_id) q.appendleft({"element": t, "root_id": node_id}) node_id += 1 return graph

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

上面的实现使用了几个有用的 Python 库：NetworkX，用于处理复杂的图形结构，Beautiful Soup，用于从 Web 中提取数据和操作文档。

调用html_to_dom_tree(soup.find("body"))将返回一个以网页的<body>元素为根的 NetworkX 图形对象。

假设我们想在一组 1,000 个网站主页中查找组。 通过将每个主页转换成这样的树，我们可以比较每个主页，例如使用上一节中给出的子路径树内核。 通过这些相似性测量，我们可以发现，例如，电子商务网站、新闻网站、博客和教育网站很容易通过它们彼此的相似性来识别。

结论

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

在许多实际领域中都会遇到树结构，例如 XML 和 HTML 文档、化合物、自然语言处理或某些类型的用户行为。 正如从 HTML 构建树的示例中所展示的，这些技术使我们能够在这些域中执行有意义的分析。