| 講演抄録／キーワード |
| 講演名 |
2004-10-14 16:45
飽和系列パターンの多項式時間列挙アルゴリズム
○有村博紀（北大）・宇野毅明（NII） |
| 抄録 |
（和） |
本稿では，系列データベースにおける飽和パターンの新しいクラスを導入し，頻出飽和系列パターンの列挙問題を考察する．
最近、データマイニング分野で飽和頻出パターン(frequent closed patterns) の効率よい列挙が盛んに研究されている．本稿で導入する「位置出現に関する飽和系列パターン」（position-closed sequence patterns）は，データベース中で同じ出現位置をもつような同値なパターンの中で最も「くわしい」情報をもつ代表元パターンであり，通常の文書出現に関するものよりも弱い概念の飽和系列パターンである．
本稿では，与えられた系列データベース上のすべての頻出飽和系列パターンを一つあたり入力サイズの多項式時間で重複なしに列挙する効率よいアルゴリズム{\sc EnumClosedSeq}を与える．
これにより，出現位置に関する頻出飽和系列パターンの列挙問題が出力多項式時間で解けることが示される．この結果は，未解決の問題である文書出現に関する飽和系列パターンの多項式時間列挙に，一歩近づくものである． |
| （英） |
In this paper, we consider the enumeration problem for
the class of frequent closed sequence patterns, called frequent
position-closed sequences, from a given collection of
sequences, where closed sequence patterns are a generalization of
closed itemsets for sequence databases.
Out notion of closed sequences are are based on the position
occurrences, and thus it is weaker than the
traditional notion of closed patterns based on the document occurrences.
We present an efficient algorithm for enumerating all frequent maximal
sequence patterns without duplicates, which runs in
polynomial time per pattern in the total size of the input sequence
database based on the framework of reverse search.
As a corollary, the enumeration problem for frequent maximal sequence
patterns is shown to be solvable in output polynomial time. |
| キーワード |
（和） |
データマイニング / 列挙アルゴリズム / 系列データベース / 頻出極大系列パターン / 部分系列 / / / |
| （英） |
Data mining / Enumeration algorithms / Sequence databases / Closed pattern mining / Subsequences / / / |
| 文献情報 |
信学技報, vol. 104, no. 339, COMP2004-45, pp. 15-22, 2004年10月. |
| 資料番号 |
COMP2004-45 |
| 発行日 |
2004-10-07 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|