データマイニングにおける頻出集合問題の計算複雑さ

巽 知厳 (9651069)


近年の計算機の高速化や記憶装置の発達に伴い, 大量の情報を記憶したデータ ベースシステムのデータの全てを(ランダムサンプリングなどによってではな く)分析することが可能になった. このような大規模データベースの内容全体 を分析することにより, データベースの利用者にとって有益な情報を得ること をデータマイニング(情報発掘)と呼ぶ.

本研究では, 以下のような場合を扱う. 商店などで各顧客が同時に購入する品物を トランザクションと呼ばれる集合で表す. データベースはトランザクションの多重集合である. このようなデータベースから データマイニングで求めたい情報の一つとして, 頻出集合がある. 集合Xが頻出集合であるとは, データベースD, および最小サポート数と呼ばれる整数sに対して, D中のトランザクションうち$ X$を包含するものがs個以上存在すること をいう. これまでにデータベースから頻出集合を全て求める手法は いくか提案されているが, それに必要な計算量については, あまり議論されていない.

データベースD, 正整数s, kが与えられたとき, 要素数k以上の 頻出集合が存在するかどうかを判定する問題を頻出集合問題と呼ぶ. 本研究では, データマイニングの基本的な問題である 頻出集合問題がNP完全 であることを示した. また関連する問題である, 高共起度集合問題及び最大集合積問題がNP完全であることを示した.