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

本研究の目的は，高速な列挙アルゴリズムを利用することで，膨大なデータベースから有用な規則性を発見することである．平成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%）に採択され，口頭発表を行った．

本研究の目的は，高速な列挙アルゴリズムを利用することで，膨大なデータベースから有用な規則性を発見することである．平成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%）に採択され，口頭発表を行った．