お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年7月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 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  Online edition: ISSN 2432-6380
PDFダウンロード

研究会情報
研究会 COMP  
開催期間 2004-10-14 - 2004-10-15 
開催地(和) 東北大学 
開催地(英) Tohoku University 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2004-10-COMP 
本文の言語 日本語 
タイトル(和) 飽和系列パターンの多項式時間列挙アルゴリズム 
サブタイトル(和)  
タイトル(英) An Effcient Mining Algorithm for Frequent Closed Sequential Episodes 
サブタイトル(英)  
キーワード(1)(和/英) データマイニング / Data mining  
キーワード(2)(和/英) 列挙アルゴリズム / Enumeration algorithms  
キーワード(3)(和/英) 系列データベース / Sequence databases  
キーワード(4)(和/英) 頻出極大系列パターン / Closed pattern mining  
キーワード(5)(和/英) 部分系列 / Subsequences  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 有村 博紀 / Hiroki Arimura / アリムラ ヒロキ
第1著者 所属(和/英) 北海道大学 (略称: 北大)
Hokkaido University (略称: Hokkaido Univ.)
第2著者 氏名(和/英/ヨミ) 宇野 毅明 / Takeaki Uno / ウノ タケアキ
第2著者 所属(和/英) 国立情報学研究所 (略称: NII)
National Institute of Informatics (略称: NII)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2004-10-14 16:45:00 
発表時間 20 
申込先研究会 COMP 
資料番号 IEICE-COMP2004-45 
巻番号(vol) IEICE-104 
号番号(no) no.339 
ページ範囲 pp.15-22 
ページ数 IEICE-8 
発行日 IEICE-COMP-2004-10-07 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会