| 講演名 | 2003/7/24 大規模木構造データからの高速な部分構造発見(「21世紀の知識情報科学に向けて」,及び一般) 浅井 達哉, 有村 博紀, 宇野 毅明, 中野 眞一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では,XML文書に代表される半構造データからのデータマイニング問題を考察する.我々は,半構造データのモデルとしてラベルつき無順序木を採用し,与えられた半構造データの集積から出現頻度の高い部分構造を発見するアルゴリズムUNOTを開発した.このアルゴリズムは,逆探索に基づいて無順序木パターンを高速に列挙し,各パターンの出現リストを漸増的に計算することにより,パターン1つあたりO(kb^2m)時間ですべての頻出無順序木パダーンTを計算する.ここに,kはTの大きさであり,bはデータ木の最大枝分かれ数,mはTのデータ木への総出現数である. |
| 抄録(英) | In this paper, we study a data mining problem of discovering frequent substructures in a large collectionof semi-structured data, where both of the patterns and the data are modeled by labeled unordered trees. The keys ofthe algorithm are efficient enumerating all unordered trees and incrementally computation of the occurrences basedon a powerful design technique known as the reverse search. We present an efficient algorithm called UNOT thatcomputes all labeled unordered trees appearing in a collection of data trees with frequency above a user-specifiedthreshold. We prove that the algorithm enumerates each frequent pattern T in O(kb2n] per pattern, where A; is thesize of T, b is the branching factor of the data tree, and n is the total number of occurrences of T in the data trees. |
| キーワード(和) | 半構造データマイニング / グラフマイニング / 頻出パターン発見 / ラベルつき無順序木 / 逆探索 |
| キーワード(英) | semi-structured data mining / graph mining / frequent pattern discovery / labeled unordered trees / reverse search |
| 資料番号 | AI2003-15 |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 2003/7/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 大規模木構造データからの高速な部分構造発見(「21世紀の知識情報科学に向けて」,及び一般) |
| サブタイトル（和） | |
| タイトル（英） | Efficiently Mining Frequent Substructures from Large Unordered Trees |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 半構造データマイニング / semi-structured data mining |
| キーワード(2)（和/英） | グラフマイニング / graph mining |
| キーワード(3)（和/英） | 頻出パターン発見 / frequent pattern discovery |
| キーワード(4)（和/英） | ラベルつき無順序木 / labeled unordered trees |
| キーワード(5)（和/英） | 逆探索 / reverse search |
| 第 1 著者 氏名（和/英） | 浅井 達哉 / Tatsuya ASI |
| 第 1 著者 所属（和/英） | 九州大学大学院システム情報科学府・研究院 Department of Informatics, Kyushu University |
| 第 2 著者 氏名（和/英） | 有村 博紀 / Hiroki ARIMURA |
| 第 2 著者 所属（和/英） | 九州大学大学院システム情報科学府・研究院 Department of Informatics, Kyushu University |
| 第 3 著者 氏名（和/英） | 宇野 毅明 / Takeaki UNO |
| 第 3 著者 所属（和/英） | 国立情報学研究所 Natinal Institute of Informatics |
| 第 4 著者 氏名（和/英） | 中野 眞一 / Shin-ichi NAKANO |
| 第 4 著者 所属（和/英） | 群馬大学工学部 Faculty of Engineering, Gunma University |
| 発表年月日 | 2003/7/24 |
| 資料番号 | AI2003-15 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 243 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |