| 講演名 | 2003/7/10 頻出グラフマイニング手法の一般化に関する研究(パターン抽出)(「夏のデータベースワークショップ(DBWS2003)」一般) 猪口 明博, 鷲尾 隆, 元田 浩, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | グラフデータに埋もれた特徴的なパターンを取り出すグラフマイニングは出力パターンの数の膨大さとNP完全として知られる部分グラフ同型問題を含むので,非常に膨大な計算コストを要する.特徴的なパターンを取り出す手法が幾つか提案されているが,それらの手法はある特定のグラフパターンのみしか取り出すことができない.本稿では,大規模データベースから実用的な時間で様々な多頻度グラフパターンを全て抽出する手法を提案する.提案手法の効率の良さは,グラフのデータ表現と出力パターンを制限するバイアスに由来する.提案手法は実データを用いて,計算時間とデータ量の観点から評価される. |
| 抄録(英) | Data mining to derive frequent subgraphs from a dataset of general graphs has high computational complexity because it includes the explosively combinatorial search for candidate subgraphs and subgraph isomorphism matching. Although some approaches have been proposed to derive characteristic patters from graph structured data, they limit the graphs to be searched within a specific class. In this paper, we propose an approach to conduct a complete search of various classes of frequent subgraphs in a massive dataset of labeled graphs within practical time. The power of our approach comes from the algebraic representation of graphs, its associated operations and well-organized bias constraints to limit the search space efficiently. It performance has been evaluated through real world datasets, and the high scalability of our approach has been confirmed with respect to the amount of data and the computation time. |
| キーワード(和) | グラフマイニング / AGMアルゴリズム / 多頻度グラフ / 正準形 / 隣接行列 / バイアス |
| キーワード(英) | Graph Mining / AGM Algorithm / Frequent Subgraph / Canonical Form / Adjacency Mtrix / Bias |
| 資料番号 | DE2003-49 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DE |
|---|---|
| 開催期間 | 2003/7/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Data Engineering (DE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 頻出グラフマイニング手法の一般化に関する研究(パターン抽出)(「夏のデータベースワークショップ(DBWS2003)」一般) |
| サブタイトル（和） | |
| タイトル（英） | Generalization for Frequent Subgraph Mining |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフマイニング / Graph Mining |
| キーワード(2)（和/英） | AGMアルゴリズム / AGM Algorithm |
| キーワード(3)（和/英） | 多頻度グラフ / Frequent Subgraph |
| キーワード(4)（和/英） | 正準形 / Canonical Form |
| キーワード(5)（和/英） | 隣接行列 / Adjacency Mtrix |
| キーワード(6)（和/英） | バイアス / Bias |
| 第 1 著者 氏名（和/英） | 猪口 明博 / Akihiro INOKUCHI |
| 第 1 著者 所属（和/英） | 日本アイ・ビー・エム(株)東京基礎研究所:大阪大学産業科学研究所 Tokyo Research Laboratory, IBM Japan:Institute of Scientific and Industrial Research, Osaka Univ. |
| 第 2 著者 氏名（和/英） | 鷲尾 隆 / Takashi WASHIO |
| 第 2 著者 所属（和/英） | 大阪大学産業科学研究所 Institute of Scientific and Industrial Research, Osaka Univ. |
| 第 3 著者 氏名（和/英） | 元田 浩 / Hiroshi MOTODA |
| 第 3 著者 所属（和/英） | 大阪大学産業科学研究所 Institute of Scientific and Industrial Research, Osaka Univ. |
| 発表年月日 | 2003/7/10 |
| 資料番号 | DE2003-49 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 191 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |