超高速列挙アルゴリズムを用いた構造データマイニングアルゴリズムの開発

使用超快速枚举算法开发结构数据挖掘算法

基本信息

批准号：
13J01149
负责人：
和佐州洋
金额：
$ 1.92万
依托单位：
Hokkaido University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2013
资助国家：
日本
起止时间：
2013-04-01 至 2016-03-31
项目状态：
已结题

项目摘要

本研究の目的は，高速な列挙アルゴリズムを利用することで，膨大なデータベースから有用な規則性を発見することである．平成27年度は，申請時に立てた計画に対する研究を行い（3-1, 3-2），さらに，本課題をより深く理解するために新たに追加した研究を行った（3-A, 3-B）．（3-1）本項では，1年目に開発した開発したデータマイニングアルゴリズムを計算機実験により評価した．既存のアルゴリズムに対してその有効性を確認したものの，改良点も見つかったため，その改良方法を現在模索中である．（3-2）本年度のもう一つの目標は，学位論文であり，無事完了した．本論文は，本課題の基盤技術である列挙アルゴリズムに関する論文である．（3-A）本研究の基盤技術である列挙に関して，誘導マッチングと弦二部誘導グラフに着目した．誘導マッチングとは，マッチングをなす誘導グラフのことをいう．また，弦二部誘導グラフとは，長さ6以上のサイクルが少なくとも1本の弦を持つ誘導グラフをいう．ただし，弦とは，サイクル上で距離が2以上離れている2頂点間にある辺のことをいう．誘導マッチングに対しては，短いサイクルを持たない時，最適な列挙アルゴリズムを，また，弦二部誘導グラフに対しては，初の多項式遅延列挙アルゴリズムを提案した．（3-B）昨年度注目した誘導木に対し，本年度は，解空間の構造を解析するためのアプローチとして注目されている遷移問題の下でさらなる考察を行った．遷移問題とは，ある決定問題の解SとTが与えられた時に，許された操作のもとで，Sを繰り返し変形させていくことで，Tを作り出すことができるか，という問題である．本項では，連結非巡回な誘導グラフ（誘導木）に対する遷移問題を考察し，固定パラメータ容易性の観点で，その計算困難性を解明した．本成果は，国際会議LATA2016（採択率35%）に採択され，口頭発表を行った．

这项研究的目的是通过使用高速枚举算法从庞大的数据库中发现有用的规律。 2015财年，我们对申请时制定的计划进行了研究（3-1、3-2），并另外进行了额外的研究以更深入地了解该主题（3-A、3-B）。 (3-1) 在本节中，我们通过计算机实验评估了第一年开发的数据挖掘算法。虽然我们已经确认了现有算法的有效性，但我们也发现了需要改进的地方，所以我们目前正在寻找改进的方法。 (3-2) 今年的另一个目标是我的博士论文，我顺利完成了。本文介绍的是枚举算法，它是解决该问题的基础技术。 (3-A)关于枚举，这是本研究的基本技术，我们重点关注诱导匹配和字符串二部诱导图。归纳匹配是指进行匹配的归纳图。另外，弦二分诱导图是长度为6以上的循环具有至少一个弦的诱导图。然而，弦是一个周期上相距两个或多个距离的两个顶点之间的边。对于诱导匹配，我们提出了不存在短循环时的最优枚举算法，对于字符串二部诱导图，我们提出了第一个多项式延迟枚举算法。 (3-B) 针对去年我们关注的归纳树，今年我们进一步考虑了转换问题，它作为分析解空间结构的方法而受到关注。转移问题是指给定决策问题的解 S 和 T 的情况下，是否可以通过在允许的操作下重复变换 S 来创建 T ．在本节中，我们考虑连通非循环诱导图（诱导树）的转移问题，并从固定参数易用性的角度阐明其计算难度。该成果在国际会议LATA2016上被接受（接受率35%），并进行口头报告。