权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

从结构数据中发现模式的高效且可扩展的算法研究

基本信息

批准号：
04F04734
负责人：
元田浩
金额：
$ 1.54万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2005
项目状态：
已结题

项目摘要

研究実績は以下のとおり.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倍高速であるとの良好な結果を得た.

The research results are as follows: 1. The previous year's development of Dryade failed to fully explore the possibility of saturation of wood structure, and the following two improvements were implemented. (a)In this case, it is possible to apply a non-cyclic directed graph (DAG : Directed Acyclic Graph) to an efficient process. (b)(a) The output of the Dryade is saturated frequently, and the results are analyzed.(b) The analysis of the DNA is applicable to the analysis of (a) and (b) above. About 5000 samples were found in 5 minutes or less, and the results were very useful. 3. Complete exploration of the efficiency of the general structure was carried out, and the results were obtained. 4. The inclusion relationship of Dryade was found in 5 minutes or less. The ancestors of the two families are related to each other, and their performance is directly compared. The relationship between DryadeParent and the definition of DryadeParent The present situation is the fastest, and the CMTree Miner is about 10,000 times faster.