Polynomial Time Algorithms for Learning Graph Structured Pattern Languages and its Applications

在研究期间，我们重点研究了几类图结构模式，它们代表了现实数据库中图结构数据常见的结构特征。本文的主要研究成果如下：1.为了表示树结构模式，如HTML/XML文件，我们提出了一种新的树结构模式，称为线性有序术语树，它由有序树结构和具有不同变量标签的内部结构变量组成。我们证明了几类线性有序术语树语言是多项式时间可从正数据归纳推断的。2.图是区间图的充要条件是图中的每个顶点都可以与实线上的一个区间相关联，使得当相应的区间有一个非空交时，图中的任意两个顶点都是相邻的。在文献中已经发现了区间图的许多有趣的应用。我们引入了一种新的区间图结构模式，称为线性区间图模式，并证明了这类线性区间图模式语言是多项式时间可从正数据归纳推断的。3.外平面图是一个平面图，它可以以这样的方式嵌入到平面中，使得所有的顶点都位于外边界上。许多化合物都是用外平面图表示的。为了解决从可以用外平面图表示数据的半结构化数据中提取结构特征的数据挖掘问题，提出了一种具有外平面图结构和结构化变量的保块外平面图模式(简称BPO-GRAPH)。我们提出了一种增量多项式时间类Apriori算法，用于枚举给定有限外平面图集合上的所有频繁BPO图模式。

During the research period, we focused on several classes of graph-structured patterns which represent structural features common to graph-structured data in real-world databases.The followings are main results of this research.1.In order to represent tree structured patterns such as HTML/XML files, we proposed a new type of tree-structured patterns, called a linear ordered term tree, which consists of ordered tree structures and internal structured variables with distinct variable labels. We showed that several classes of linear ordered term tree languages are polynomial time inductively inferable from positive data.2.A graph is an interval graph if and only if each vertex in the graph can be associated with an interval on the real line such that any two vertices are adjacent in the graph exactly when the corresponding intervals have a nonempty intersection. A number of interesting applications for interval graphs have been found in the literature. We introduced a new interval graph structured pattern, called a linear interval graph pattern, and showed that the class of linear interval graph pattern languages is polynomial time inductively inferable from positive data.3.An outerplanar graph is a planar graph which can be embedded in the plane in such a way that all of vertices lie on the outer boundary. Many chemical compounds are known to be represented by outerplanar graphs. In order to solve a data mining problem of extracting structural features from semi-structured data whose data can be expressed by outerplanar graphs, we introduced a block preserving outerplanar graph pattern (bpo-graph pattern for short) as a new graph pattern having an outerplanar graph structure and structured variables. We presented an incremental polynomial time Apriori-like algorithm for enumerating all frequent bpo-graph patterns with respect to a given finite set of outerplanar graphs.