翻译：http://www.kdnuggets.com/2016/02 ... tructured-data.html
名称：Tree Kernels: Quantifying Similarity Among Tree-Structured Data
参考 : http://www.36dsj.com/archives/43411
有些地方翻译的不太准确，还望海涵。
网络和图形是一种节点形式的结构化数据类型，它们之间的关系用链接或者边来描述。图中的节点和边可能有多个属性，比如数字或类别，甚至更复杂。
今天，大量的数据是可用的网络或图形的形式。例如，万维网和它的网页和超链接，社会网络，语义网络，生物网络，科学文献的引用网络，等等。
树是一种特殊类型的图形，很适合表示多种类型的数据。树的分析是计算机和数据科学中的一个重要领域。在这篇文章中，我们将分析树的结构。特别的，我们将主要介绍树的内核，这是一种可以比较两棵树相似或差异的方法。对于很多如分类和数据分析的现代应用，这是一个很重要的过程。
结构化数据的无监督分类
分类是机器学习和数据分析的重要组成部分。在一般情况下，分类可以是有监督的或无监督的。在有监督的分类中，数据的类别是已知的，并且会有已经标注好正确类别的训练数据供我们训练分类模型。对比之下，无监督分类是一种试图通过数据之间的相似特征来将数据聚成几类，并且我们并不知道数据的类别。
无监督分类法可以结合图论的知识去识别相似的树网络。多个领域都采用了树结构模型的数据。比如，在自然语言处理(NLP)领域,语法分析树是一种有序和被标记的树。在自动推理中，搜索解决了很多问题，搜索空间被定义成一种树的形式，树的结点代表搜索状态，树的边代表推导过程。另外，半结构化数据，如HTML和XML文档，可以模拟为有序，标记的树。
这些领域可以通过非监督分类技术进行有效的分析。在自然语言处理（NLP）领域，分类可以用来自动将一组句子分成问题，答案和语句。同样的ML源，相似网站群可以通过HT识别分类方法识别。在所有情况下，我们需要的就是一种衡量两个树相似性的方法。
维度灾难大多数分类算法需要将数据转化成向量的形式，将数据的特征表示成特征空间中的值，使数据可以在特征空间利用线性代数分析。结构化或半结构化数据，比如树，由于特征空间必须保留结构信息，所以得到的向量维数（即特征空间中的特征数）可能会很高。
考虑到许多分类技术是不能够有效地扩展维度输入，这可能是一个显著的缺点（不知道该怎么翻译这句话）。换句话说，它们的分类能力随着输入维数的增加而降低。这个问题被称为”维数灾难”。
考虑有一个维度为D的空间中一组数据X。假设X包含一组均匀分布的点。如果X的维度增加（即表示每个样本数据的特征数增加），如果要使样本数据均匀分布且具有D=1时的密度，则需要更多的数据。换句话说，输入的维数越大，数据稀疏的可能性越大。一般情况下，稀疏的数据集并没有给出足够的信息以建立一个良好的分类系统。（翻译者注：令data_num表示样本数据的数量，feature_num表示每个样本点特征的数量。若data_num << feature_num,则样本数据很可能无法覆盖所有的特征，及可能有的特征在样本数据中是找不到的。同时，盲目的增加特征的数目，如果有一些不好的特征，可能会使样本数据在高维空间中看起来都很相似，从而无法训练出好的分类模型）。
每个特征空间上面都包含了八个数据点。在一维空间上，很容易辨认出左边一组5个点，和右边一组3个点。在更高维空间中，数据的分类却不是那么明显了。在实际应用中，特征空间可以很容易地拥有数百个维度。
当一组特征信息可以很好的在这个领域使用时，可以用向量的方式表示结构化的数据。反之，如果这组特征信息是没有用的，则可以使用直接处理结构化数据的方法进行处理。
核方法核方法避免了将数据转换成向量的需要。它们需要的是一种度量数据集合中每对元素相似的方法。这种度量被称为核，度量方法实现的函数成为核函数。特征空间中的核方法就是寻找它们的线性关系。在功能上，它们相当于特征空间中的点积的2个数据点，而真正的功能设计，在内核功能设计可能仍然是一个有用的步骤。然而，内核方法避免直接操作在特征空间，因为它可以表明以取代点产品的内核功能是可能的，只要核函数是对称的，正定函数可以作为输入的原始空间数据。
使用内涵函数的优点是，一个巨大的特征空间，可以分析与计算复杂度不依赖于特征空间的大小，但是内核功能的复杂性，这意味着内核的方法是没有灾难的维数。
我们考虑一个由有限数据组成的n个样本数据，我们能用一个n × n的核矩阵来表示数据之间的相似性，这个矩阵独立于每个样本数据的大小。当样本数据远远小于特征数量时，这种方法是有效的。
在一般情况下，核方法不是将数据点映射到特征空间，而是将数据之间的比较转换成一种核矩阵的形式，数据的相关度分析都可以在矩阵中进行。
许多数据挖掘方法都可以核化。将核方法和一些如支持向量机这样的分类方法相结合来分类树结构的数据定义的有效的函数K: T × T → R的方法也称为树核。当设计一个特殊用途的树核时，若其计算时间在树大小的多项式时间内完成，并且能够检测到同构的图，则称为完全树核（不知道翻译的对不对）。
树核现在，让我们来介绍一些用于测量树的相似性的树核。其主要思想是计算数据集中的每对树的核，从而建立一个核矩阵用来分类。
字符串内核首先，我们先对字符串内核做一个简短的介绍，这有助于帮助我们更好的理解一种将树转换为字符串的核方法。
定义numy(s)为子字符串y在字符串s中出现的次数，|s|为字符串s的长度。字符串内核定义如下：
其中F是
S1
和
S2共同出现的子字符串的集合，ws
是权重参数。我们可以看到，两个字符串的公共子串越多，这个内核计算出的值越高。 |
