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.