データマイニングに要する計算量に関する研究

八木 勲(9551114)

近年の計算機技術の進展により，大量の情報を記憶したデータベー スシステムのデータを分析することが可能になった．このような大 規模データベースの内容全体を分析することにより，出現頻度の高 いパターンを見つけて，データベースの利用者にとって有益な情報 を得ることをデータマイニングと呼ぶ．これまでにデー タマイニングの手法はいくつか提案されているが，それに必要な計 算量についてはあまり議論されていない．本稿では，極大頻出系列 問題と呼ばれるデータマイニングの基本的な問題についてその解 （パターン）の個数がデータベースサイズの指数オーダとなる場合 があることを示した．また，データ1個の追加でパターン 数が指数的に増加する場合があるので，インクリメンタルなアルゴ リズムはこの問題に適していないことがわかった．そして，データ がある種の局所性を満たす場合，パターンの集合を受理し， 状態数がデータベースのサイズの多項式オーダのDFAが高い確率で 存在することを示した．