構造データからパタン発見に関する効率的で大規模化可能なアルゴリズムに関する研究

点击翻译按钮获取中文摘要

研究実績は以下のとおり.1.前年度開発したDryadeアルゴリズムは木構造データに対して飽和頻出木を完全探索可能であるが,より一般的なグラフ構造データへの拡張が可能かどうかを検討し,以下の2点の改良を実施した.(a)ループを含まないグラフに対しては,Dryadeアルゴリズムの要であるフッキング操作をそのまま適用可能であり,非循環有向グラフ(DAG : Directed Acyclic Graph)を効率的に処理出来るよう拡張した.(b)(a)のDryadeアルゴリズムの出力は飽和頻出木なので,その結果を分析して飽和頻出非循環グラフを発見するポストプロセッシングシステムを開発した.2.上記(a),(b)を実装し,DNAマイクロアレイデータ(バイオデータ)の解析に適用した.約5000個のノードからなる非循環グラフから多頻度飽和部分グラフを5分以下で発見出来,十分実用的であることを確認した.3.ループを含む一般グラフ構造に対する効率的な完全探索アルゴリズムを検討し原理的には可能であるとの結論を得た.4.Dryadeの木の包含関係は親子関係だけでなく,祖先まで遡る包含関係を許す一般なものであり,他の木マイニングアルゴリズムと性能を直接比較出来ないという問題があった.そのため,他のアルゴリズムと同じ定義の包含関係を扱えるようなバージョンDryadeParentを別に作成した.現状最速であると報告されている飽和頻出木マイニングアルゴリズムCMTreeMinerと多くの人工データで,木の深さと木の平均分岐数をパラメータとして比較した結果,高平均分岐数の場合には,DryadeParentの方がCMTreeMinerより約10,000倍高速であるとの良好な結果を得た.