- 商品コード：
-
code:pg_0208_13
PDF/月刊誌論文/code:pg_0208_13 マテリアル インテグレーション 2002年8月号
- 通常価格(税込)：
-
2,200
円
- 販売価格(税込)：
-
2,200
円
ポイント：
0
Pt
- 関連カテゴリ：
-
電子出版物(マテリアルインテグレーション論文)
> 2002
INTER MATERIAL 材料・生体・情報の融合を目指して(2)
グラフ構造データからのマイニング
■著者
大阪大学産業科学研究所 知能システム科学研究部門 教授 元田 浩 他
■要約
構造を持ったデータを一般的に表現するにはグラフを用いるのが自然である.グラフ中のノードがデータの要素に,ノード間のリンクが要素間の関係を表す.本稿ではグラフ構造データから特徴的な部分構造を抽出する技術とそれを発癌性物質と変異原性物質の特性同定に適用した結果の概要を報告する.特徴的な部分構造の意味は問題によって異なるが,ここでは,多くのグラフ中に頻繁に現われる(一般的にはこのようなものは,ある特性に関し識別能力があることが多い)多頻度部分グラフとする.この問題は部分グラフ同型性判定問題に帰着され,数学的にはNP 完全であることが知られている.すなわち,どのよううな工夫をしても,答えを得るために必要な計算量は最悪の場合,グラフの大きの指数関数となってしまう.そのため,2つの手法を開発している.1つは厳密性を犠牲にしてもできるだけ大きなグラフ(ノード数が1万程度のものを想定)を短時間で処理できる 方法,他の1つは小さなグラフ(ノード数が数十以下のものを想定)を対象にするが厳密性を保つ(すなわち,数え落としがないことを保証する)方法である.いずれの手法もノードやリンクにラベルを許す,有向,無向グラフを扱うことができる.とくに,後者は部分グラフとして非連結グラフも扱うことができる.
