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

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

基本信息

批准号：
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时，是否可以通过在允许的操作下反复转换s来产生t的问题。在本节中，我们检查了连接的无环引导图（引导树）的过渡问题，并阐明了固定参数的计算难度。该结果是在2016年国际会议LATA会议上选出的（收养率为35％），并进行了口头介绍。