Design and Analysis of Efficient Class-oriented Graph Mining Systems

高效的面向类的图挖掘系统的设计与分析

• 批准号: 23500182
• 负责人: SHOUDAI Takayoshi
• 金额: $ 3.33万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23500182/
• 关键词: グラフパターン; グラフマイニング; グラフアルゴリズム; グラフ構造データ; データマイニング; 機械学習; 機械発見; 帰納推論

Our object of this research is to develop an effective graph pattern designing system for efficient data mining from graph-structured data. During this research period, the following results mainly were obtained.(1) A tree contraction pattern (TC-pattern) is an unordered tree-structured pattern common to given unordered trees, which is obtained by merging every uncommon connected substructure into one vertex by edge contraction. We show that an important subclass of TC-patterns is polynomial-time inductively inferable from positive data. Moreover, we discuss the optimization versions of the learning problems for TC-patterns, and give the conditions under which the optimization problems are hard to compute.(2) We introduce context-deterministic regular formal graph systems (FGS) as one of the effective graph pattern designing systems, and propose a polynomial time algorithm for learning the class of context-deterministic regular FGSs in the framework of MAT learning.

我们这项研究的目的是开发一种有效的图形模式设计系统，用于从图形结构数据中进行有效的数据挖掘。本研究期间主要取得了以下成果：(1)树收缩模式(TC-pattern)是给定无序树所共有的一种无序树结构模式，它是通过将每个不常见的连通子结构合并到一个顶点得到的：边缘收缩。我们证明了 TC 模式的一个重要子类是可以从正数据中归纳推断出多项式时间的。此外，我们讨论了TC模式学习问题的优化版本，并给出了优化问题难以计算的条件。（2）我们引入上下文确定性正则形式图系统（FGS）作为有效的方法之一。图模式设计系统，并提出了一种多项式时间算法，用于在 MAT 学习框架中学习上下文确定性常规 FGS 类。

项目成果

Hard Optimization Problems in Learning Tree Contraction Patterns, Applied Computing and Information Technology

学习树收缩模式、应用计算和信息技术中的硬优化问题

• DOI: 10.1007/978-3-319-05717-0_6
• 发表时间: 2014
• 作者: Y. Okamoto;T . Shoudai
• 通讯作者: T . Shoudai

Discovery of Tree Structured Patterns Using Markov Chain Monte Carlo Method

使用马尔可夫链蒙特卡罗方法发现树结构模式

• 发表时间: 2014
• 作者: Yasuhiro Okamoto; Kensuke Koyanagi; Takayoshi Shoudai; Osamu Maruyama
• 通讯作者: Osamu Maruyama

Network Traffic Screening Using Frequent Sequential Patterns

使用频繁序列模式进行网络流量筛选

• DOI: 10.1007/978-1-4614-1695-1_28
• 发表时间: 2012
• 作者: H. Tsuruta; T . Shoudai;J. Takeuchi
• 通讯作者: J. Takeuchi

簡潔データ構造を用いた極大項木パターン枚挙アルゴリズム

使用简洁数据结构的最大项树模式枚举算法

• 发表时间: 2014
• 作者: 佐野 元紀; 内田 智之; 糸川 裕子
• 通讯作者: 糸川 裕子

Ordered Graph Patterns Which Are Polynomial Time Inductively Inferable from Positive Data

从正数据归纳推断多项式时间的有序图模式

• 发表时间: 2014
• 作者: Takahiro Hino; Yusuke Suzuki; Tomoyuki Uchida; Tetsuhiro Miyahara
• 通讯作者: Tetsuhiro Miyahara