树内核（量化树状结构数据之间的相似性）

本文概述

结构化数据的无监督分类
维数的诅咒
内核方法
树仁
采矿网站
总结

网络或图形是节点形式的一种结构化数据, 它们之间的关系由链接或边缘描述。图中的节点和边可能具有多个属性, 这些属性可能是数字的或分类的, 甚至更为复杂。
如今, 以网络或图形的形式提供了大量数据。例如, 万维网及其网页和超链接, 社交网络, 语义网络, 生物网络, 科学文献的引文网络等等。
树是图的一种特殊类型, 自然适合表示多种类型的数据。树木分析是计算机和数据科学的重要领域。在本文中, 我们将研究对树中链接结构的分析。特别是, 我们将专注于树核, 这是一种用于将树图相互比较的方法, 使我们能够获得其相似性或差异的可量化度量。对于许多现代应用程序(例如分类和数据分析)而言, 这是一个重要的过程。

文章图片
结构化数据的无监督分类分类是机器学习和数据分析的重要组成部分。通常, 分类可以是有监督的, 也可以是无监督的。在监督分类中, 类别是已知的, 并且根据训练数据构建分类模型, 其中已经给出了正确的类别。相比之下, 无监督分类尝试识别未知的分类, 并根据某种相似度将数据分组。
可以将无监督分类与图论结合以识别相似树网络的组。树数据结构用于对来自多个域的对象进行建模。例如, 在自然语言处理(NLP)中, 解析树被建模为有序的, 标记的树。在自动推理中, 通过搜索解决了许多问题, 其中搜索空间表示为一棵树, 其顶点与搜索状态相关联, 而边表示推理步骤。同样, 半结构化数据(例如HTML和XML文档)可以建模为有序的, 标记为树的树。
可以通过无监督分类技术对这些域进行有用的分析。在NLP中, 分类可用于将一组句子自动分组为问题, 命令和陈述。同样, 可以通过将分类方法应用于其HTML来源来标识相似网站的组。在上述每种情况下, 我们所需要的只是一种方法来衡量两棵树之间的” 相似度” 。
维数的诅咒大多数分类算法都要求将数据转换为向量化形式, 以表示特征空间中数据特征的值, 以便可以使用线性代数在特征空间中对数据进行分析。在结构化或半结构化数据(如树)中, 结果矢量的维数(即特征空间中的特征数)可能会很高, 因为特征空间必须保留有关结构的信息。
考虑到许多分类技术无法随输入的维数有效缩放, 因此这可能是一个重大缺陷。换句话说, 它们的分类能力随着输入维数的增加而降低。这个问题被称为维数的诅咒。
【树内核（量化树状结构数据之间的相似性）】为了了解性能下降的原因, 请考虑尺寸为d的空间X。假设X包含一组均匀分布的点。如果X的维数增加, 则保持相同密度所需的点数必须成倍增加。换句话说, 输入的维数越大, 该数据稀疏的可能性就越大。通常, 稀疏数据集无法提供足够的信息来构建良好的分类器, 因为数据元素之间的相关性太弱, 以至于算法无法检测到。

文章图片
上方的每个要素空间均包含八个数据点。在一维空间中, 很容易在左侧确定五个点, 在右侧确定三个点。将这些点扩展到更多数量的要素(即尺寸)上会使找到这些组更加困难。在实际应用中, 要素空间可以轻松地具有数百个维度。
当可以有效地使用有关领域的信息来选择一组可管理的特征时, 对结构化数据进行矢量化表示是合适的。当此类信息不可用时, 最好利用可以直接处理结构化数据的技术, 而无需在向量空间中执行操作。
内核方法内核方法避免了将数据转换为矢量形式的需要。他们唯一需要的信息是对数据集中每对项目的相似性的度量。该度量称为内核, 用于确定该度量的函数称为内核函数。内核方法在特征空间中寻找线性关系。从功能上讲, 它们等效于在特征空间中采用两个数据点的点积, 并且实际上, 特征设计可能仍然是内核函数设计中的一个有用步骤。但是, 内核方法避免使用直接在特征空间上的操作, 因为可以证明可以用内核函数替换点积, 只要内核函数是对称的, 正半定函数即可将数据作为输入在其原始空间中。
因此, 使用内核函数的优势在于可以分析庞大的特征空间, 其计算复杂度不取决于特征空间的大小, 而取决于内核函数的复杂度, 这意味着内核方法不会遭受诅咒维度。
如果考虑由n个示例组成的有限数据集, 则可以通过生成大小始终为n×n的核矩阵来获得数据内相似性的完整表示。该矩阵与每个单独示例的大小无关。当要分析具有较大特征空间的小型示例数据集时, 此属性很有用。
通常, 内核方法基于对数据表示问题的不同回答。代替将输入点映射到特征空间中, 而是通过成对比较在内核矩阵K中表示数据, 并且可以在内核矩阵上执行所有相关分析。

许多数据挖掘方法可以被内核化。为了用诸如支持向量机之类的内核方法对树状数据实例进行分类, 定义一个有效的(对称正定)内核函数k：T×T→R, 也称为树内核就足够了。在设计实用的树核时, 可能要求它们在树大小的多项式时间内是可计算的, 并且能够检测同构图。这样的树内核称为完整树内核。
树仁现在, 让我们介绍一些有用的树核, 以测量树的相似度。主要思想是为数据集中的每对树计算内核, 以构建内核矩阵, 然后将其用于对树集进行分类。
字符串内核
首先, 我们将从字符串内核的简短介绍开始, 这将帮助我们引入另一种基于将树转换为字符串的内核方法。
让我们将numy(s)定义为字符串s中子字符串y的出现次数, 用| s |表示字符串的长度。我们将在此处描述的字符串内核定义为：
Kstring(S1, S2)=Σs∈Fnums(S1)nums(S2)ws
其中F是在S1和S2中都出现的子字符串集, 参数ws用作权重参数(例如, 强调重要的子字符串)。如我们所见, 当内核共享许多公共子字符串时, 该内核会为一对字符串提供更高的值。
基于将树转换为字符串的树内核
我们可以使用此字符串内核来构建树内核。该内核背后的想法是, 以一种对树的结构进行编码的系统方式将两棵树转换为两个字符串, 然后将上述字符串内核应用于它们。
我们将两棵树转换为两个字符串, 如下所示：
令T表示目标树之一, 并且label(ns)表示T中节点ns的字符串标签。tag(ns)表示以ns为根的T子树的字符串表示形式。因此, 如果nroot是T的根节点, 则tag(nroot)是整个树T的字符串表示形式。
接下来, 让string(T)= tag(nroot)表示T的字符串表示形式。我们将以自底向上的方式递归应用以下步骤以获得string(T)：

如果节点ns是叶, 则让tag(ns)=” [” + label(ns)+” ]” (其中+这里是字符串串联运算符)。
如果节点ns不是叶并且有c个子节点n1, n2, … , nc, 按词法顺序对tag(n1), tag(n2), … , tag(nc)进行排序以获得tag(n1 *), tag( n2 *), …, tag(nc *), 然后让tag(ns)=” [” + label(ns)+ tag(n1 *)+ tag(n2 *)+…+ tag(nc *)+” ] “ 。

下图显示了此树到字符串转换的示例。结果是一个字符串, 该字符串以诸如” [“ 之类的开始定界符开始, 并以其闭合对应项” ]” 结束, 每个嵌套的定界符对都对应于以特定节点为根的子树。

现在, 我们可以将上述转换应用于两个树T1和T2, 以获得两个字符串S1和S2。从那里, 我们可以简单地应用上述字符串内核。
现在可以通过两个字符串S1和S2在T1和T2之间建立树内核：
Ktree(T1, T2)= Kstring(字符串(T1), 字符串(T2))= Kstring(S1, S2)=Σs∈Fnums(S1)nums(S2)ws
在大多数应用中, 权重参数变为w | s |, 根据其长度| s |对子字符串进行加权。 w | s |的典型加权方法是：

恒定权重(w | s | = 1)
k频谱加权(如果| s | = k, 则w | s | = 1, 否则, w | s | = 0)
指数加权(w | s | =λ| s |, 其中0≤λ≤1是衰减率)

要计算内核, 只需确定所有公共子字符串F, 并计算它们在S1和S2中出现的次数即可。查找公共子字符串的这一额外步骤是一个经过充分研究的问题, 可以使用后缀树或后缀数组在O(| S1 | + | S2 |)中完成。如果我们假设描述节点标签所需的最大字母数(例如位, 字节或字符)是恒定的, 则转换后的字符串的长度为| S1 |。 = O(| T1 |)和| S2 | = O(| T2 |)。因此, 计算内核函数的计算复杂度为O(| T1 | + | T2 |), 它是线性的。
基于子路径的树内核
上面的树内核使用水平或广度优先的方法将树转换为字符串。尽管这种方法非常简单, 但是这种转换意味着它不能直接以其原始形式对树进行操作。
本节将定义一个在树的垂直结构上运行的树内核, 从而允许该内核直接在树上运行。
从根到叶子之一的路径的子部分称为子路径, 子路径集是树中包含的所有子路径的集合：

让我们假设我们要在两棵树T1和T2之间定义一个树核K(T1, T2)。通过使用子路径集, 我们可以将此树内核定义为：
K(T1, T2)=Σp∈Pnump(T1)nump(T2)w | p |
其中nump(T)是子路径p在树T中出现的次数, | p |。是子路径p中的节点数, P是T1和T2中所有子路径的集合。 w | p |是重量, 类似于上一节介绍的重量。
在这里, 我们使用深度优先搜索介绍了该内核的简单实现。尽管此算法以二次时间运行, 但是存在使用后缀树或后缀数组或多键快速排序算法的扩展的更有效的算法, 它们平均可以实现线性运算时间(O(| T1 | log | T2 |))：

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 += 1generate_subpaths(path, l+1)def get_subpaths(graph, root, track, path): track[root] = Trueif 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 | s |。 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 += 1root_id = node['root_id'] labels[root_id] = node['element'].namefor 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 += 1return graph

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

上面的实现利用了两个有用的Python库：用于处理复杂图形结构的NetworkX和用于从Web提取数据并处理文档的Beautiful Soup。
调用html_to_dom_tree(soup.find(” body” ))将返回一个以网页的< body> 元素为根的NetworkX图形对象。
假设我们要在一组1, 000个网站首页中查找组。通过将每个主页转换成这样的树, 我们可以比较每个树, 例如, 使用上一节中给出的子路径树内核。通过这些相似性度量, 我们可以发现, 例如, 电子商务站点, 新闻站点, 博客和教育站点可以通过彼此的相似性轻松识别。
总结在本文中, 我们介绍了用于将树结构数据元素彼此进行比较的方法, 并展示了如何将核方法应用于树以对它们的相似性进行量化的度量。事实证明, 内核方法是在高维空间中进行操作的绝佳选择, 这是使用树结构时的常见情况。这些技术使用在核矩阵上运行的经过充分研究的方法, 为进一步分析大型树奠定了基础。
在许多实词领域(例如XML和HTML文档, 化合物, 自然语言处理或某些类型的用户行为)中都会遇到树结构。如从HTML构造树的示例所示, 这些技术使我们能够在这些领域中进行有意义的分析。