効率良く頻出集合をデータマイニング可能なデータベースクラスについて

概要

論文の詳細を見る
従来は, CPUや外部記憶が低速かつ高価だったため, データベース中のデータの解析は, ランダムサンプリング等により取り出した一部のデータに対してしか行えなかった.これに対して, 近年は計算機技術の進展により, 大量の情報を記憶したデータベース中の全てのデータを見て解析することが可能になった.このように大規模データベースの内容全体を解析することにより, データベースの利用者にとって有益な情報を得ることをデータマイニング(情報発掘)と呼ぶ.データマイニングでもっとも得たい情報の一つとして, 大規模データベースから属性やデータ間に成り立つ有意な連想規則(association rule)を求めることが挙げられる.有意な連想規則を求める一つの手法として, 頻出集合(large itemset)を用いる方法が考えられている.しかし, この方法では一般のデータベースに対して有意な連想規則を多項式時間で効率良く求められることができない.そこで本研究では, 全ての頻出集合および有意な連想規則が効率良く求められるデータベースの部分クラスを提案した。また, 高共起度集合の要素数の最大値を求める問題がNP完全であることを示した.
社団法人電子情報通信学会の論文
1998-05-29