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

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

基本信息

批准号：
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倍高速であるとの良好な結果を得た.

研究结果如下： 1.去年开发的Dryade算法能够完全搜索树结构数据的饱和频繁树，但我们正在考虑是否可以将其扩展到更通用的图结构数据，我们实现了。以下两个改进： (a) 对于不包含循环的图，可以按原样应用作为 Dryade 算法核心的 hooking 操作，并且(b) 由于 (a) 中 Dryade 算法的输出是饱和频繁树，我们开发了一个后处理系统来分析结果并发现饱和频繁非循环图 2. 实现上述 (a) 和 (b)。收集 DNA 微阵列数据（生物数据）。）。可以在不到5分钟的时间内从由约5000个节点组成的非循环图中发现频繁饱和的子图，并证实其具有足够的实用性。 3．对于包括循环在内的一般图结构，我们研究了一种高效的完整子图。搜索算法并得出原理上可行的结论。 4．包含关系是一种通用的关系，不仅允许父子关系，还允许追溯到祖先的包含关系，并且存在一个问题，即性能无法与我创建的单独版本的其他树挖掘算法进行直接比较。可以处理关系的DryadeParent。据悉是目前最快的。以树深度和平均分支数为参数，将已报道的饱和频繁树挖掘算法 CMTreeMiner 与大量人工数据进行比较，发现在平均分支数较高的情况下，DryadeParent 比 CMTreeMiner 大约 10,000 倍我们获得了良好的结果，速度提高了一倍。