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

图结构化模式语言学习的多项式时间算法及其应用

• 批准号: 17500009
• 负责人: SHOUDAI Takayoshi
• 金额: $ 2.39万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17500009/
• 关键词: Learning of graph languages; Computational learning theory; Inductive inference; Graph-structured patterns; Graph grammar; Tree-structured data; Graph-structured data; Graph algorithms

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.

在研究期间，我们专注于几类的图形结构模式，这些模式代表了现实世界数据库中图形结构数据共有的结构特征。以下是这项研究的主要结果。1。在表示树结构的模式中，我们提出了一种新的类型的树结构的模式，称为“树结构”类型，称为“树结构序列”，该模式的变化序列有序树结构，并构成树结构的各种形式的树结构，并构成树的结构，这些构造构成了树结构的构造，并构成了树的结构，并构成了树结构的构造序列。我们表明，几类线性排序的项树语言是从正数据中推断的多项式时间。2.A图是一个间隔图，并且仅当图中的每个顶点才能与实际线路上的每个顶点相关联，以便在相应间隔间隔不空时，任何两个顶点在图形中与图形完全相邻。文献中发现了许多间隔图的有趣应用。我们引入了一个新的间隔图结构图，称为线性间隔图模式，并表明线性间隔图模式语言类是可以从正数据中推断的多项式时间。3.ANEPLANPLANAR图是一个平面图，可以将其嵌入平面中，以至于所有的Vertices都位于外部边界上。已知许多化合物由外平面图表示。为了解决一个数据挖掘问题，即从半结构化数据中提取结构特征，该数据可以通过外平面图表示，我们引入了一个保留外平面图模式的块（简短的BPO图形模式），为具有外平面图结构和结构变量的新图形模式。我们提出了一种增量多项式时间类似Apriori样算法，用于列举所有频繁的BPO-graph模式，相对于给定的有限外平面图。

项目成果

TTSP項グラフ言語の正データからの多項式時間帰納推論可能性について

论TTSP术语图语言中从正数据进行多项式时间归纳推理的可能性

• 发表时间: 2005
• 作者: 鈴木 祐介;高味 亮司;内田 智之;正代 隆義;中村 泰明
• 通讯作者: 中村 泰明

PC 木を用いた制限付き円弧グラフのための同型性判定アルゴリズム

基于PC树的受限弧图同构判定算法

• 发表时间: 2007
• 作者: 川本 哲;山崎 仁志;正代 隆義
• 通讯作者: 正代 隆義

Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data

TTSP图语言从正数据的多项式时间归纳推理

• 发表时间: 2005
• 期刊: Proc.ILP-2005, Springer, Lecture Notes in Artificial Intelligence 3625
• 作者: R.Takami;Y.Suzuki;T.Uchida;T.Shoudai;and Y.Nakamura
• 通讯作者: and Y.Nakamura

Ordered from tree languages which are polynomial time inductively inferable from positive data

从树语言排序，这些语言是可以从正数据归纳推断出来的多项式时间

• 发表时间: 2006
• 期刊: Theoretical Computer Science 350
• 作者: K.;Inata;T.;Miyahara;H.;Ueda;K.;Takahashi;Hitoshi Yamasaki;Hidenori Hirashima;Akihiro Mikoda;Yusuke Suzuki
• 通讯作者: Yusuke Suzuki

Mining of Frequent Block Preserving Outerplanar Graph Structured Patterns

频繁块保留外平面图结构化模式的挖掘

• 发表时间: 2008
• 期刊: Proc. ILP-2007, Springer, Lecture Notes in Artificial Intelligence 4894
• 作者: Y.;Sasaki;H.;Yamasaki;T.;Shoudai;T.;Uchida
• 通讯作者: Uchida