Distributed Data Mining Systems for Structured Web Data

在本研究中，我们研究了半结构化Web文档（如HTML/XML文件）中的知识发现。基于图或树的数据挖掘和发现图或树结构数据中的频繁结构已经得到了广泛的研究。我们发现的目标既不是简单的频繁模式，也不是关于模式的语法大小（如顶点数量）的最大频繁模式。为了从异构半结构化Web文档中提取有用的信息，我们的发现目标是语义上和最大程度上的树状结构模式，它代表了半结构化文档中的一个共同特征。作为树形结构模式的表示形式，我们提出了一种有序的树形模式，称为术语树，它是一种由有序子节点和内部结构化变量组成的根树形模式。术语树不同于树结构模式的其他表示形式，因为术语树具有结构化变量，这些变量可以被任意树替换。首先，我们深入研究了术语树语言类的可学习性，给出了多项式时间可学习的术语树语言的基本类。我们证明了几类术语树语言在正数据上是多项式时间归纳推断的，包括具有多子端口变量的线性术语树语言、具有邻近叶的可收缩变量的线性术语树语言和具有高度约束变量且无变量链的线性术语树语言。此外，我们还证明了某些类别的线性词树语言可以在多项式时间内使用查询精确地学习。最后，我们提出了一个元搜索系统，该系统使用了我们对术语树的高效学习算法。我们实现了这个系统，并表明它提供了一个有效的统一访问多个现有的搜索网站。

In this research, we studied knowledge discovery from semistructured Web documents such as HTML/XML files. Graph or tree-based data mining and discovery of frequent structures in graph or tree structured data have been extensively studied. Our target of discovery is neither a simply frequent pattern nor a maximally frequent pattern with respect to syntactic sizes of patterns such as the number of vertices. In order to extract useful information from heterogeneous semistructured Web documents, our target of discovery is a semantically and maximally tree structured pattern which represents a common characteristic in semistructured documents. As a representation of a tree structured pattern, we proposed an ordered tree pattern, called a term tree, which is a rooted tree pattern consisting of ordered children and internal structured variables.A term tree is different from other representations of tree structured patterns in that a term tree has structured variables which can be substituted by arbitrary trees. First of all, we deeply studied the learnabilities of classes of term tree languages and gave fundamental classes of term tree languages which are polynomial time learnable. We proved that some classes of term tree languages are polynomial time inductively inferable from positive data, which include the class of linear term tree languages with multiple child-port variables, the class of linear term tree languages with contractible variables which are adjacent to leaves, and the class of linear term tree languages with height-constrained variables and no variable chain. Moreover, we showed that some classes of linear term tree languages are exactly learnable in polynomial time using queries.Finally, we presented a metasearch system which uses our efficient learning algorithms for term trees. We implemented this system and showed that it provides an effective unified access to multiple existing search sites.