基于树转换成字符串的树核我们可以使用字符串内核来构建一个树内核。这种构建内核的方法是，用系统的方法将树的结构编码从而将两棵树转换成两个字符串，然后用上述的字符串内核的方法来计算。
我们用下边的方法将树转化为字符串：
T表示其中一棵树，label(ns)
是树T中结点ns的标签。tag(ns)是树T中以结点ns为根结点的子树的字符串表示。若nroot表示树T的根结点，那么tag(nroot)就是整个树T的字符串表示了。接下来，令string(T) = tag(nroot)为树T的字符串表示。递归进行下面的步骤，自下而上的得到string(T)：
1、如果结点ns是一个叶子结点，令tag(ns)=“[”+ label(ns)
+“]”（在这里,'+'是字符串串联运算符）。
2、如果结点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，而树的内核定义如下：
在很多应用中，权重参数经常表示为 w|s|，即他的值是根据字符串长度 |s|来决定的。比较典型的权重w|s|设置方法如下：
1、常数加权法（如w|s|=1）
2、k-普频加权法（w|s| = 1 if |s| = k, and w|s| = 0 otherwise）
3、指数加权法（w|s| = λ|s|，其中
0 ≤ λ ≤ 1是衰减率）
为了计算内核，必须得到所有公共子字符串的集合F，以及它们在字符串S1
和
S2中出现的次数。寻找公共子串很容易实现，如果使用后缀树或者后缀数组可以在O(|S1| + |S2|)内实现。如果我们假定描述结点标签所需最多的字母（如位，字节，字符）个数是一定的，那么转换后的字符串长度是
|S1| = O(|T1|)和|S2| = O(|T2|)，所以计算核函数的时间复杂度是O(|T1| + |T2|)，是线性的。
基于子路径的树核上面的树核使用了一个水平的或者广度优先（？）的方法将树转换为字符串。虽然这种方法很简单，但这种转换意味着它不能直接在其原始形式的树上操作。
本节将定义一种树核，这种树核从垂直方向上直接操作原始树。
一条从根结点到叶子结点的路径定义为子路径，子路径集是包含所有子路径的集合（个人感觉定义的可能有点错误）：
假设我们要利用两棵树的子路径集来定义一个树核函数K(T1, T2)，可以定义如下：
nump(T)是子路径p在树T中出现的次数，|p|是子路径p中结点的个数，P是出现在T1和T2中所有子路径的集合，w|p| 和上文介绍的相似，也是权重。
这里，我们使用深度优先搜索简单的实现了一下。虽然该算法是平方时间内完成的，但是有些方法使用后缀树和后缀数组或快速排序的延伸算法，平均时间可达到O(|T1|log|T2|)。
[python] view plain copy
- <span style="font-size:18px;"><span style="font-size:14px;">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</span></span>
在这个例子中，我们使用的加权参数为w|p|
w|s|
= 1。这里所有子路径的权重均相同。然而，在很多情况下使用k-普频加权法或动态加权法会更好些。
挖掘网站 在我们总结之前，让我们简单地看看一个真实的利用树结构进行分类的例子︰
分类网站。在许多数据挖掘上下文中，知道一些来自那种类型的网站可以使我们受益良多。结果表明，由于相同作用的网页会有相似的结构，所以利用树来进行网页分类非常有效。
我们应该怎么做？HTML文档的逻辑嵌套结构很像一棵树。每一个文档包含一个根元素，里面包含了其他元素嵌套。若元素嵌套在HTML标签里，则在逻辑上相当于这个标签的子节点。
下面的代码可以将html文档转换为树结构：
[python] view plain copy
- <span style="font-size:18px;"><span style="font-size:14px;">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</span></span>
它会产生一个类似下边图片的树形图：
这里有几个有用的Python库：networkx可以处理复杂的图结构，Beautiful Soup用来从网页文件中提取数据。
我们要在1000个网站的主页上找到组。通过将每个网页变成这样的一棵树，我们可以相互比较，例如通过使用上一节给出的路径树核。通过这些测量的相似性我们可以发现，例如，电子商务网站，新闻网站，博客和教育网站是很容易确定他们的相似性的。
结论在这篇文章中，我们介绍了树结构数据元素的比较，并显示了如何应用内核的方法，以获得一个可量化的测量他们的相似性。内核的方法已被证明是一个很好的选择时，在高维空间中一个共同情况下，与树结构的工作。这些技术为进一步分析大套树木，使用以及研究的方法，操作过的内核矩阵阶段。
树结构在现实世界中许多领域如XML和HTML文件，遇到化学化合物，自然语言处理，或某些类型的用户行为。作为从HTML构建树的例子证明，这些技术使我们能够在这些领域进行有意义的分析。
原文地址：Tree Kernels: Quantifying Similarity Among Tree-Structured Data
End. |
